/* 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
();
}
