Bài Tập Cây Nhị Phân Tìm Kiếm

/* Cấu Trúc Dữ Liệu & Giải Thuật Phòng Máy B40a

Bài Tập : Cây Nhị Phân Tìm Kiếm

|-------------------------------------------------------------|

| Họ Tên Sinh Viên : Nguyễn Thị Nhung |

| Mã Số Sinh Viên : 1261098 |

| Lớp : 12CK1 |

|-------------------------------------------------------------|

*/

/* Đề Bài :

viết chương trình cho phép lưu trữ & đo đạc số lượng kí tự trong văn bản ko dấu,xây dựng cây lưu trữ văn bản đó sao cho mỗi kí tự là 1 Node cùng lúc làm chủ được số lần hiện ra các kí tự đó .

Yêu Cầu Bài Cần Xây Dựng Các Tính Năng:

+ Thêm

+ Xóa

+ Tìm Kiếm

1 kí tự bất cứ & ghi nó xuống File

__________________________________________________________________

File input:

Tạo đc hình cái cây (max 10đ) ko thì in ra theo kiểu mục lục (max 9đ)

------------------------------------------------------------------

1. in cây:

2. cây sau khoảng thời gian thêm:

3. cây sau khoảng thời gian xóa:

4. kết quả tìm kiếm

P/s: nếu nhập: "hoeoe iaia" thì cây lưu các giá trị: h o e i a

khi xóa "i" thì vẫn sót lại 1 "i" xóa 2 lần mới hết "i"

*/

/* ============================================= BÀI LÀM =========================================================== */

/* Yêu Cầu Để Chạy Được Chương Trình : Bạn phải Sao chép 2 file : gioithieuchuongtrinh.txt va file InPut.txt (có sẵn trong file đính kèm) vào trong ổ đĩa C */

/* ==================================== Các Thư Viện Sử Dụng Trong Chương Trình ==================================== */

#include "stdio.h"

#include "conio.h"

#include "time.h"

#include "Windows.h"

#define n 4000

/* ================================================================================================================= */

/* ============================= Khai Báo Cấu Trúc Cây Nhị Phân Tìm Kiếm =========================================== */

typedef

struct

tagNODE

{

char

key

;

// Kiểu dữ liệu ký tự (char) ứng với thông tin lưu tại nút .

struct

tagNODE

*

pLeft

,

*

pRight

;

// Lưu trữ thông tin địa chỉ nút gốc của cây con trái,cây con phải trong bộ nhớ lưu trữ .

int

Dem

;

// Số lần hiện ra của ký tự .

}

NODE

;

typedef

NODE

*

Tree

;

/* ================================================================================================================= */

/* ===================================== Khởi Tạo Cây ============================================================== */

void

INit

(

NODE

*

&

Tree

)

{

Tree

=

NULL

;

}

/* ================================================================================================================= */

/* ================================= (Lặp) Thêm Nút Vào Cây Nhị Phân Tìm Kiếm ====================================== */

bool

InsertNode

(

Tree

&

pRoot

,

char

x

)

{

if

(

pRoot

!=

NULL

)

{

if

(

pRoot

->

key

>

x

)

InsertNode

(

pRoot

->

pLeft

,

x

);

// Quan niệm đệ quy :Lợi dụng đặc thù của cây nhị phân tìm kiếm nếu Node cần thêm vào bé hơn nút gốc thì duyệt qua nhánh trái .

else

if

(

pRoot

->

key

<

x

)

InsertNode

(

pRoot

->

pRight

,

x

);

// Quan niệm đệ quy :Lợi dụng đặc thù của cây nhị phân tìm kiếm nếu Node cần thêm vào to hơn nút gốc thì duyệt qua nhánh phải .

else

if

(

pRoot

->

key

==

x

)

// Nếu bằng nhau (đã có)

{

pRoot

->

Dem

++

;

// Đếm số lần hiện ra tăng trưởng .

return

true

;

// Trả về true .

}

}

else

{

pRoot

=

new

NODE

;

if

(

pRoot

==

NULL

)

return

false

;

pRoot

->

key

=

x

;

pRoot

->

Dem

=

1

;

pRoot

->

pLeft

=

pRoot

->

pRight

=

NULL

;

return

true

;

// Thêm vào thành công .

}

}

/* ================================================================================================================= */

/* ======================================== Nhập Dữ Liệu Vào Cho Cây =============================================== */

void

CreatTree

(

Tree

&

pRoot

,

FILE

*

pFile

)

{

rewind

(

pFile

);

// Dời địa điểm đọc ghi về đầu (byte 0) của tập tin pFile .

char

c

;

INit

(

pRoot

);

// Khởi tạo lại cây nhị phân tìm kiếm .

while

(

!

feof

(

pFile

))

c

==

EOF

)

break

;

// Thoát ra khỏi vòng lặp .

if

(

c

==

' '

)

// Nếu bằng ký tự rỗng thì chương trình tiếp tục duyệt xuống tiếp để thực hiện việc thêm ký tự .

continue

;

InsertNode

(

pRoot

,

c

);

// Cuối cùng sau khoảng thời gian thỏa hết thì sẽ thực hiện việc thêm ký tự vào cây .

}

/* ================================================================================================================= */

/* =================================== In Các Nút Của Cây Nhị Phân Tìm Kiếm ======================================== */

// Duyệt theo thứ tự giữa (Left - Node - Right):Kiểu duyệt này trước hết thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải .

void

LNR

(

Tree

pRoot

,

FILE

*

FileOutPut

)

{

if

(

pRoot

!=

NULL

)

{

LNR

(

pRoot

->

pLeft

,

FileOutPut

);

// Duyệt trái .

fprintf

(

FileOutPut

,

"<%c>(%d) "

,

pRoot

->

key

,

pRoot

->

Dem

);

// Ghi dữ liệu các ký tự phân biệt & tần suất hiện ra của chúng vào file OutPut.txt .

LNR

(

pRoot

->

pRight

,

FileOutPut

);

// Duyệt phải .

}

}

/* ================================================================================================================= */

/* ================================== Tìm Kiếm Node Thay Thế Cho Node Bị Xóa ======================================= */

void

SearchStandFor

(

Tree

&

p

,

Tree

&

q

)

{

// Tìm phần tử thế mạng cho nút p .

if

(

q

->

pLeft

)

SearchStandFor

(

p

,

q

->

pLeft

);

// Quan niệm đệ quy .

else

{

p

->

key

=

q

->

key

;

p

=

q

;

q

=

q

->

pRight

;

}

}

/* ================================================================================================================= */

/* ====================================== Xóa Đi Một Node Trong Cây ================================================ */

bool

DeleteNode

(

Tree

&

T

,

char

x

)

{

if

(

T

==

NULL

)

// Cây rỗng thì trả về giá trị false .

return

false

;

if

(

T

->

key

>

x

)

DeleteNode

(

T

->

pLeft

,

x

);

// Quan niệm đệ quy - dựa theo thuộc tính của cây nhị phân tìm kiếm nếu Node x cần xóa bé hơn nút gốc của cây thì duyệt qua nhánh trái của cây .

if

(

T

->

key

<

x

)

DeleteNode

(

T

->

pRight

,

x

);

// Quan niệm đệ quy - dựa theo thuộc tính của cây nhị phân tìm kiếm nếu Node x cần xóa to hơn nút gốc của cây thì duyệt qua nhánh phải của cây .

else

// T->key==x

{

if

(

T

->

Dem

==

1

)

{

NODE

*

p

=

T

;

// Các trường hợp T có 1 con .

if

(

T

->

pLeft

==

NULL

)

T

=

T

->

pRight

;

// Nhánh trái rỗng thì tiếp tục duyệt qua nhánh phải .

else

if

(

T

->

pRight

==

NULL

)

T

=

T

->

pLeft

;

// Nhánh phải rỗng thì tiếp tục duyệt qua nhánh trái .

else

// T có cả 2 con

{

NODE

*

q

=

T

->

pRight

;

SearchStandFor

(

p

,

q

);

// Tìm phần tử thế mạng .

}

delete

p

;

// Xóa đi p .

return

true

;

// Trả về true .

}

else

{

T

->

Dem

--

;

return

true

;

// Trả về true .

}

}

}

/* ================================================================================================================= */

/* ========================================== Xóa Đi Ký Tự Trong File ============================================== */

bool

DeleteCharactersInFile

(

Tree

&

pRoot

,

FILE

*

FileInPut

,

FILE

*

FileOutPut

)

{

rewind

(

FileInPut

);

// Dời địa điểm đọc ghi về đầu (byte 0) của tập tin InPut.txt .

char

s

[

n

];

// Khai báo chuỗi s tối đa 4000 ký tự .

for

(

int

i

=

;

i

<

2

;

i

++

)

{

fgets

(

s

,

n

,

FileInPut

);

// Ý Nghĩa : Đọc một dãy ký tự từ tập tin InPut.txt vào vùng nhớ s,chấm dứt khi đủ n-1 ký tự hoặc gặp ký tự xuống dòng,lưu ký tự xuống dòng vào chuỗi s nếu dòng thấp hơn n-1 ký tự,auto thêm ký tự chấm dứt chuỗi .

// Gía trị trả về : Thành công -> trả về địa chỉ vùng nhớ s . Thất bại -> trả về NULL khi gặp lỗi hoặc gặp ký tự EOF .

}

char

c

;

while

(

!

feof

(

FileInPut

))

{

c

=

fgetc

(

FileInPut

);

// Đọc một ký tự từ tập tin InPut.txt được mở bởi hàm fopen trong hàm main . Giá trị trả về nếu thất bại trả về EOF khi chấm dứt tập tin InPut.txt hoặc gặp lỗi .

if

(

c

==

'n'

||

c

==

EOF

)

break

;

// Thoát ra khỏi vòng lặp .

if

(

c

==

' '

)

// Nếu bằng ký tự rỗng thì chương trình tiếp tục duyệt xuống tiếp để thực hiện việc xóa ký tự .

continue

;

// Thực hiện việc xóa ký tự .

if

(

DeleteNode

(

pRoot

,

c

)

==

true

)

{

fprintf

(

FileOutPut

,

" %c Da Xoa Duoc

t

"

,

c

);

// Kết quả trả về trong File OutPut.txt

}

else

{

fprintf

(

FileOutPut

,

"<%c> Khong Xoa Duoc

t

"

,

c

);

// Kết quả trả về trong File OutPut.txt

}

}

return

true

;

// Trả về true .

}

/* ================================================================================================================= */

/* ============================================== Thêm Ký Tự ======================================================= */

void

AddCharacters

(

NODE

*

&

Tree

,

FILE

*

FileInPut

)

{

rewind

(

FileInPut

);

// Dời địa điểm đọc ghi về đầu (byte 0) của tập tin InPut.txt .

char

s

[

n

];

// Khai báo chuỗi s tối đa 4000 ký tự .

fgets

(

s

,

n

,

FileInPut

);

// Ý Nghĩa : Đọc một dãy ký tự từ tập tin InPut.txt vào vùng nhớ s,chấm dứt khi đủ n-1 ký tự hoặc gặp ký tự xuống dòng,lưu ký tự xuốn dòng vào chuỗi s nếu dòng thấp hơn n-1 ký tự,auto thêm ký tự chấm dứt chuỗi .

// Gía trị trả về : Thành công -> trả về địa chỉ vùng nhớ s . Thất bại -> trả về NULL khi gặp lỗi hoặc gặp ký tự EOF .

char

c

;

while

(

!

feof

(

FileInPut

))

}

/* ================================================================================================================= */

/* =================================== Tìm Kiếm Một Node Trong Cây ================================================= */

NODE

*

SearchNode

(

Tree

T

,

char

x

)

{

if

(

T

)

{

if

(

T

->

key

==

x

)

return

T

;

if

(

T

->

key

>

x

)

return

SearchNode

(

T

->

pLeft

,

x

);

// Quan niệm đệ quy:Dựa trên thuộc tính của cây nhị phân tìm kiếm nếu Node x bé hơn nút gốc => Ta sẽ duyệt qua nhánh trái của cây .

else

if

(

T

->

key

<

x

)

return

SearchNode

(

T

->

pRight

,

x

);

// Quan niệm đệ quy:Dựa trên thuộc tính của cây nhị phân tìm kiếm nếu Node x to hơn nút gốc => Ta sẽ duyệt qua nhánh phải của cây .

}

return

NULL

;

}

/* ================================================================================================================= */

/* ================================= Tìm Kiếm Ký Tự Với Dữ Liệu Từ File ============================================ */

void

SearchCharactersInFile

(

NODE

*

TREE

,

FILE

*

FileInPut

,

FILE

*

FileOutPut

)

{

rewind

(

FileInPut

);

// Dời địa điểm đọc ghi về đầu (byte 0) của tập tin InPut.txt .

char

s

[

n

];

// Khai báo chuỗi s tối đa 4000 ký tự .

for

(

int

i

=

;

i

<

3

;

i

++

)

{

fgets

(

s

,

n

,

FileInPut

);

// Ý Nghĩa : Đọc một dãy ký tự từ tập tin InPut.txt vào vùng nhớ s,chấm dứt khi đủ n-1 ký tự hoặc gặp ký tự xuống dòng,lưu ký tự xuốn dòng vào chuỗi s nếu dòng thấp hơn n-1 ký tự,auto thêm ký tự chấm dứt chuỗi .

// Gía trị trả về : Thành công -> trả về địa chỉ vùng nhớ s . Thất bại -> trả về NULL khi gặp lỗi hoặc gặp ký tự EOF .

}

char

c

;

while

(

!

feof

(

FileInPut

))

}

/* ================================================================================================================= */

/* ============================================ Các Hàm Đồ Họa ===================================================== */

// Hàm tăng kích thước của khung CMD

void

resizeConsole

(

int

width

,

int

height

)

{

HWND

console

=

GetConsoleWindow

();

RECT

r

;

GetWindowRect

(

console

,

&

r

);

MoveWindow

(

console

,

r

.

left

,

r

.

top

,

width

,

height

,

TRUE

);

}

// Hàm lấy tọa độ địa điểm .

void

gotoxy

(

int

x

,

int

y

)

{

HANDLE

hstdout

=

GetStdHandle

(

STD_OUTPUT_HANDLE

);

COORD

position

=

{

x

,

y

};

SetConsoleCursorPosition

(

hstdout

,

position

);

}

// Hàm tô màu .

void

textcolor

(

int

x

)

{

HANDLE

mau

;

mau

=

GetStdHandle

(

STD_OUTPUT_HANDLE

);

SetConsoleTextAttribute

(

mau

,

x

);

}

/* ================================================================================================================= */

/* ======================================== Lời Giới Thiệu Đầu Chương Trình ======================================== */

int

gioithieu

()

{

FILE

*

f

=

fopen

(

"C:

gioithieuchuongtrinh.txt"

,

"rt"

);

if

(

f

!=

NULL

)

{

while

(

1

)

{

if

(

feof

(

f

))

break

;

if

(

kbhit

())

key

==

27

)

return

;

char

x

;

x

=

fgetc

(

f

);

printf

(

"%c"

,

x

);

Sleep

(

35

);

// Bố trí vận tốc chạy dữ liệu trong file : Sleep càng nhỏ thì vận tốc chạy chữ càng nhanh & trái lại .

}

fclose

(

f

);

}

else

printf

(

"Khong co File gioithieuchuongtrinh.txt"

);

getch

();

}

/* ================================================================================================================= */

/* ================================= Hiển Thị Lời Chào Khi Kết Thúc Chương Trình =================================== */

void

Thanks

()

{

system

(

"cls"

);

// Xóa đi mọi dữ liệu đã làm trước đây .

srand

(

time

(

NULL

));

for

(

int

j

=

1

;

j

<=

20

;

j

++

)

{

int

color

=

rand

()

%

15

+

1

;

// Khởi tạo màu chạy đột nhiên trong đoạn thang màu [1,15].

Sleep

(

300

);

gotoxy

(

j

-

1

,

40

);

printf

(

" "

);

gotoxy

(

j

,

40

);

textcolor

(

color

);

printf

(

"

n

Thanks You For Using The Program ! Goodbye And See You Later !

n

"

);

// Khi người dùng thoát chương trình sẽ hiển thị lời chào !

}

textcolor

(

15

);

getch

();

gotoxy

(

3

,

42

);

}

/* ================================================================================================================= */

/* ========================================= MeNu ================================================ */

void

MeNu

()

{

resizeConsole

(

1000

,

550

);

// Tăng kích thước của khung CMD lên thành chiều rộng 1000,chiều cao 550 .

textcolor

(

14

);

// Tô màu vàng cho chữ .

gioithieu

();

// In ra lời giới thiệu từ File .

textcolor

(

7

);

// Trả về màu chữ bình bình .

remove

(

"C:

OutPut.txt"

);

// Xóa đi các dữ liệu trong file OutPut.txt .

NODE

*

TREE

;

FILE

*

FileInPut

,

*

FileOutPut

;

// Khởi tạo File nhị phân InPut.txt để chứa dữ liệu đầu vào & OutPut.txt để ghi kết quả .

FileInPut

=

fopen

(

"C:

InPut.txt"

,

"r"

);

// Mở tập tin InPut.txt ở trong ổ đĩa C để đọc dữ liệu . Trả về NULL còn nếu không tìm ra tập tin .

int

luachon

;

if

(

FileInPut

!=

NULL

)

{

FileOutPut

=

fopen

(

"C:

OutPut.txt"

,

"a+"

);

// Mở tập tin OutPut.txt để thêm dữ liệu vào cuối tập tin & đọc tập tin . Tập tin sẽ đơợc tạo mới nếu chưa có .

// In Cây là mặc định bắt buộc cần có của chương trình . Sau thời điểm công cuộc in cây thực hiện xong thì bảng MeNu sẽ đặt ra cho người dùng các sự lựa chọn tùy vào nhu cầu là thêm - xóa - tìm kiếm hay song song cả thêm,xóa,tìm kiếm luôn .

printf

(

"

n

>>>>>>>>>>>>>>>>>>> In Cay <<<<<<<<<<<<<<<<<<<<<

n

"

);

CreatTree

(

TREE

,

FileInPut

);

LNR

(

TREE

,

FileOutPut

);

fprintf

(

FileOutPut

,

"

n

"

);

printf

(

"

n

------------------------------------------------

n

"

);

printf

(

"

n

------------ Bang Lua Chon --------------

n

"

);

printf

(

"

n

2.Cay Sau Khi Them "

);

printf

(

"

n

3.Cay Sau Khi Xoa "

);

printf

(

"

n

4.Ket Qua Tim Kiem "

);

printf

(

"

n

5.Them - Xoa - Tim Kiem "

);

printf

(

"

n

0.Thoat "

);

printf

(

"

n

-----------------------------------------

n

"

);

printf

(

"

n

"

);

quaylai:

printf

(

"

n

Nhap vao lua chon cua ban:"

);

scanf

(

"%d"

,

&

luachon

);

printf

(

"

n

"

);

printf

(

"

n

Ket Qua:"

);

if

(

luachon

==

2

)

{

printf

(

"

n

>>>>>>>>>>>>>>>>>>> Cay Sau Khi Them <<<<<<<<<<<<<<<<<

n

"

);

AddCharacters

(

TREE

,

FileInPut

);

LNR

(

TREE

,

FileOutPut

);

fprintf

(

FileOutPut

,

"

n

"

);

printf

(

"

n

-------------------------------------------------------

n

"

);

printf

(

"

n

Loading...."

);

printf

(

"

n

"

);

printf

(

"

n

Yeu Cau Cua Ban Da Duoc Thuc Hien Xong.Xin Moi Vao C:

OutPut.txt De Xem Ket Qua!"

);

fcloseall

();

// Đóng toàn bộ File lại .

}

else

if

(

luachon

==

3

)

{

printf

(

"

n

>>>>>>>>>>>>>> Cay Sau Khi Xoa <<<<<<<<<<<<<<<<<<<<<

n

"

);

DeleteCharactersInFile

(

TREE

,

FileInPut

,

FileOutPut

);

fprintf

(

FileOutPut

,

"

n

"

);

printf

(

"

n

----------------------------------------------------

n

"

);

printf

(

"

n

Loading...."

);

printf

(

"

n

"

);

printf

(

"

n

Yeu Cau Cua Ban Da Duoc Thuc Hien Xong.Xin Moi Vao C:

OutPut.txt De Xem Ket Qua!"

);

fcloseall

();

// Đóng toàn bộ File lại .

}

else

if

(

luachon

==

4

)

{

printf

(

"

n

>>>>>>>>>>>>>>> Tim Kiem Ky Tu <<<<<<<<<<<<<<<<<<<<<<

n

"

);

SearchCharactersInFile

(

TREE

,

FileInPut

,

FileOutPut

);

printf

(

"

n

----------------------------------------------------------------

n

"

);

printf

(

"

n

Loading...."

);

printf

(

"

n

"

);

printf

(

"

n

Yeu Cau Cua Ban Da Duoc Thuc Hien Xong.Xin Moi Vao C:

OutPut.txt De Xem Ket Qua!"

);

fcloseall

();

// Đóng toàn bộ File lại .

}

else

if

(

luachon

==

5

)

{

printf

(

"

n

>>>>>>>>>>>>>>>>>>>>> Them - Xoa - Tim Kiem <<<<<<<<<<<<<<<<<<<<<<"

);

/* ============ Thêm Ký Tự ================= */

AddCharacters

(

TREE

,

FileInPut

);

LNR

(

TREE

,

FileOutPut

);

fprintf

(

FileOutPut

,

"

n

"

);

/* ========================================= */

/* =============== Xóa Ký Tự =============== */

DeleteCharactersInFile

(

TREE

,

FileInPut

,

FileOutPut

);

fprintf

(

FileOutPut

,

"

n

"

);

/* ========================================= */

/* ============= Tìm Kiếm Ký Tự ============ */

SearchCharactersInFile

(

TREE

,

FileInPut

,

FileOutPut

);

printf

(

"

n

----------------------------------------------------------------

n

"

);

/* ========================================= */

printf

(

"

n

Loading...."

);

printf

(

"

n

"

);

printf

(

"

n

Yeu Cau Cua Ban Da Duoc Thuc Hien Xong.Xin Moi Vao C:

OutPut.txt De Xem Ket Qua!"

);

fcloseall

();

// Đóng toàn bộ File lại .

}

else

if

(

luachon

==

)

{

Thanks

();

}

if

(

luachon

!=

2

&&

luachon

!=

3

&&

luachon

!=

4

&&

luachon

!=

5

&&

luachon

!=

)

{

printf

(

"

n

Lua chon ban nhap vao khong hop le!Xin vui long nhap lai!"

);

goto

quaylai

;

}

}

else

{

printf

(

"

n

Khong Tim Thay File InPut.txt Trong O Dia C!"

);

printf

(

"

n

"

);

printf

(

"

n

Ban Can Phai Tao 1 File Co Ten La: InPut.txt Trong O Dia C Va Nhap Du Lieu Vao Do!"

);

}

}

/* =================================================================================================== */

/* ========================================= Main ==================================================== */

void

main

()

{

MeNu

();

}

Xem Thêm  h4

Viết một bình luận