Thực hành Cấu trúc dữ liệu và giải thuật 1

Insertion Sort 
e) Thực hiện lần lượt thêm vào danh sách m phần tử sao cho phần tử được thêm vào 
vị trí sao cho nhỏ hơn hoặc bằng phần tử trước nó và lớn hơn hoặc bằng phần tử 
sau nó. Nếu nó không tìm được vị trí như vậy sẽ được thêm vào cuối danh sách. 
Nếu có nhiều hơn 1 vị trí thích hợp thì chọn vị trí đầu tiên. 
3) Xây dựng cấu trúc dữ liệu biễu diễn đa thức. Viết các thao tác trên đa thức: tính giá 
trị, tính đạo hàm, cộng trừ đa thức. 
P(x) = 01
1
1 ... cxcxcxc
k
k
k
k ++++ −− 
4) Tính toán số lớn: Viết cấu trúc số nguyên lớn ( > 50 chữ số ) dùng danh sách liên kết. 
Thực hiện các thao tác cơ bản tính toán số nguyên: cộng, trừ, nhân 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 23 
BÀI THỰC HÀNH SỐ 8 
Các Thao Tác Trên Stack – Queue 
(8 tiết) 
Mục tiêu 
- Làm việc với Stack và Queue 
- Cài đặt Stack và Queue 
Nội dung lý thuyết 
1. NGĂN XẾP (STACK) 
Ngăn xếp là một danh sách mà 2 phép thêm và loại bỏ đều được thực hiện trên 
một đầu. 
Như vậy, phần tử nào thêm vào sau sẽ bị loại bỏ trước, nên ngăn xếp còn được 
gọi là danh sách LIFO ( Last In First Out list) hoặc Pushdown list. 
Ngăn xếp có nhiều ứng dụng. Ví dụ: chương trình A gọi chương trình B, chương 
trình B gọi chương trình C. Khi chương trình C được thực hiện xong thì sự điều khiển 
chương trình sẽ trở về thực hiện chương trình B, rồi khi chương trình B được thực hiện 
xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình A. Như vậy 
chương trình B được gọi sau sẽ được trở về thực hiện trước chương trình A. Đó là nhờ 
điểm nhập (entry point) trở về của các chương trình được chứa trong ngăn xếp. 
Ngăn xếp có thể được tổ chức theo danh sách liên kết. Vì phép thêm vào và phép 
loại bỏ chỉ được thực hiện ở cùng một đầu nên ta chỉ cần một con trỏ giữ đỉnh của 
stack. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 24 
Cấu trúc dữ liệu của Stack 
typedef .... ElementType; // Kiểu dữ liệu của nút 
typedef struct node 
{ 
ElementType Data; 
 struct node *Next; 
 } NodeType; 
typedef NodeType *NodePointer; 
NodePointer Stack; 
Các phép thao tác cơ bản 
a) Thao tác Push đẩy một mục dữ liệu x vào đỉnh ngăn xếp 
b) Thao tác Pop lấy ra một phần tử ở đỉnh ngăn xếp 
c) Thao tác Top xem một phần tử ở đỉnh ngăn xếp 
2. HÀNG ĐỢI (QUEUE) 
Hàng đợi là một danh sách mà phép thêm vào được thực hiện ở đầu này và loại bỏ 
được thực hiện ở đầu kia. 
Như vậy, phần tử nào vào trước sẽ được loại bỏ trước, phần tử nào vào sau sẽ 
được loại bỏ sau, nên hàng đợi còn được gọi là danh sách FIFO (First In First Out list). 
Cấu trúc dữ liệu 
typedef int ElementType; 
 typedef struct node 
{ 
ElementType Data; 
 struct node *Next; 
 }NodeType; 
 typedef NodeType *NodePointer; //Định nghĩa kiểu con trỏ nút 
 typedef struct 
{ 
NodePointer Head, Tail; 
} LL; 
Stack 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 25 
 LL Queue; 
Các thao tác cơ bản 
a) EnQueue(O): thêm một đối tượng O vào đuôi hàng đợi; 
b) DeQueue(): lấy ra một đối tượng ở đầu hàng đợi và trả về trị của nó, nếu hàng đợi 
rỗng sẽ gặp lỗi; 
c) EmptyQueue(): kiểm tra xem hàng đợi có rỗng hay không; 
d) Front(): Trả về trị của phần tử ở đầu hàng đợi mà không loại nó khỏi hàng đợi, 
nếu hàng đợi rỗng sẽ gặp lỗi. 
BÀI TẬP 
1) Cho 1 chuỗi mô tả các thao tác trên stack/queue gồm các ký tự chữ cái và dấu * với 
quy tắc như sau: 
• Chữ cái tượng trưng cho thao tác thêm chữ cái tương ứng vào stack/queue. 
• Dấu * tượng trưng cho thao tác lấy nội dung một phần tử ra khỏi stack/queue. 
Thực hiện chuỗi thao tác này trên stack/queue theo thứ tự từ trái sang phải.Sau khi hoàn 
tất, tiến hành lấy lần lượt tất cả các phần tử còn lại trong stack/queue, hãy cho biết nội 
dung lấy được. 
Ví dụ 
AAA**BCC*D 
Kết quả khi thao tác trên Stack là DCBA 
Kết quả khi thao tác trên Queue là BCCD 
2) Viết chương trình dùng ngăn xếp thực hiện chuyển đổi và biểu diễn số nguyên dương 
N ở dạng cơ số b (b = 2, 8,16). 
3) Viết chương trình tính giá trị biểu thức bằng dãy Balan ngược Thực hiện qua 2 bước 
Bước 1: Chuyển biểu thức từ dạng trung tố (dạng gốc do người dùng nhập vào) sang dạng 
hậu tố. 
Bước 2: Tính giá trị của biểu thức dạng hậu tố, ta sẽ được kết quả. 
Thuật toán chuyển từ dạng trung tố sang hậu tố 
™ Khởi động stack rỗng (Stack chứa toán tử) 
™ While (không có lỗi và chưa hết biểu thức) 
o Đọc Token (Token = hằng/biến/toán tử số học /ngoặc trái/ngoặc phải). 
o Nếu Token là 
ƒ Ngoặc trái (: Push vào stack. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 26 
ƒ Ngoặc phải ): Pop và hiển thị các phần tử của stack đến khi gặp 
ngoặc trái (pop ngoặc trái nhưng không hiển thị ngoặc trái). 
ƒ Toán tử: Nếu stack rỗng hay Token được ưu tiên hơn phần tử ở đỉnh 
stack thì Push vào Stack .Ngược lại (ưu tiên bằng hoặc ít ưu tiên 
hơn) pop và hiển thị 1 phần tử ở đỉnh stack .Lặp lại việc so sánh 
Token với 1 phần tử ở đỉnh stack. 
ƒ Toán hạng : hiển thị nó. 
™ Khi hết biểu thức trung tố Pop và hiển thị toàn bộ stack còn lại. 
Thuật toán tính giá trị biểu thức hậu tố: 
™ Khởi động stack rỗng. 
™ Lặp lại các bước sau đến khi hết biểu thức: 
o Đọc Token (Hằng, biến, toán tử) 
o Nếu Token là : 
ƒ Toán hạng: Push vào stack 
ƒ Toán tử: 
• Pop 2 giá trị 
• Áp dụng toán tử cho 2 giá trị lấy ra. 
• Push kết quả vào stack. 
Lặp đến hết biểu thức ,giá trị ở đỉnh stack là giá trị của biểu thức. 
Độ ưu tiên của các toán tử 
‘(’ < {‘+’,’-‘} < {‘*’,’/’} 
VD: 
(2+3)*5 Æ 2 3 + 5 * : Sau khi chuyển từ trung tố sang hậu tố. 
4*12/3+1 Æ 4 12 * 3 / 1: Sau khi chuyển từ trung tố sang hậu tố. 
5*(2+3) Æ5 2 3 + * : Sau khi chuyển từ trung tố sang hậu tố. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 27 
Chương 4: CẤU TRÚC CÂY 
BÀI THỰC HÀNH SỐ 9 
Cây Nhị Phân, Cây Nhị Phân Tìm kiếm 
(8 tiết) 
Mục tiêu 
Cài đặt cây nhị phân, cây tìm kiếm nhị phân và các thao tác. 
Nội dung lý thuyết 
1. CẤU TRÚC DỮ LIỆU CỦA CÂY NHỊ PHÂN 
typedef ..... ElementType; /* Kiểu mục dữ liệu của nút */ 
 typedef struct TN 
{ 
 ElementType Data; //Để đơn giản, ta xem Data là trường khóa 
của dữ liệu 
 struct TN * LChild, *RChild; 
 } TreeNode; 
 typedef TreeNode *TreePointer; 
2. CÁC THAO TÁC CƠ BẢN 
a) Tạo một nút của cây 
b) Chèn một phần tử vào cây 
c) Duyệt cây: NLR, LNR, LRN 
d) Tìm một phần tử có trên cây 
e) Xóa phần tử của cây. 
BÀI TẬP 
1) Viết một chương trình có các tác dụng sau: 
a. Nhập từ bàn phím các số nguyên vào một cây nhị phân tìmkiếm (BST) mà nút gốc 
được trỏ bởi con trỏ Root. 
b. Xuất các phần tử trên cây BST trên theo thứ tự: đầu, giữa, cuối. 
c. Tìm và xóa (nếu có thể) phần tử trên cây Root có dữ liệu trùng với một mục dữ 
liệu Item cho trước được nhập từ bàn phím. 
d. Sắp xếp n mục dữ liệu (được cài đặt bằng mảng hay DSLK) bằng phương pháp cây 
nhị phân tìm kiếm BSTSort. 
Yêu cầu: viết các thao tác trên bằng 2 phương pháp: đệ quy và lặp (*). 
2) Cho cây nhị phân T. Viết chương trình chứa các hàm có tác dụng xác định: 
a. Tổng số nút của cây. 
b. Số nút của cây ở mức k 
c. Chiều cao của cây. 
d. Tổng giá trị trường dữ liệu (số!) trên các nút của cây. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 28 
e. Kiểm tra xem nó có phải là một cây nhị phân chặt (là cây nhị phân mà mỗi nút 
khác nút lá đều có đúng 2 con) hay không? 
f. Kiểm tra xem T có phải là cây cân bằng hoàn toàn hay không ? 
g. Số nút có đúng 2 con khác rỗng. 
h. Số nút có đúng 1 con khác rỗng. 
i. Số nút có khóa nhỏ hơn x trên cây nhị phân hoặc cây BST. 
j. Số nút có khóa lớn hơn x trên cây nhị phân hoặc cây BST. 
k. Số nút có khóa nhỏ hơn x và lớn hơn y (y ≤ x) trên cây nhị phân hoặc cây BST 
l. Duyệt cây theo chiều rộng. 
m. Duyệt cây theo chiều sâu. 
n. Độ lệch lớn nhất của các nút trên cây (độ lệch của một nút là trị tuyệt đối của hiệu 
số giữa chiều cao của cây con phải và cây con trái của nó). 
o. Đảo nhánh trái và phải của mọi nút trên một cây nhị phân. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 29 
BÀI THỰC HÀNH SỐ 10 
Các thao tác trên cây nhị phân tìm kiếm cân bằng 
(4 tiết) 
Mục tiêu 
Cài đặt cây nhị phân, cây nhị phân tìm kiếm cân bằng. 
BÀI TẬP 
Cài đặt các thao tác trên cây AVL. Cho phép người dùng lựa chọn thực hiện các thao tác 
sau: 
1. Kiểm tra một node có thuộc cây hay không? 
2. Insert một node vào cây. 
3. Delete một node trong cây. Nếu node có hai cây con thì cho phép chọn phần tử thế 
chỗ thuộc: 
a. Cây con trái. 
b. Cây con phải. 
4. Duyệt cây để in ra các node, theo thứ tự: 
a. NLR. 
b. LNR. 
c. LRN. 
Để tiện dụng, yêu cầu 2, 3 cần thực hiện vòng while cho đến khi người dùng không 
muốn insert hay delete nữa. 
Thực hành Cấu trúc dữ liệu và Giải thuật 1 30 
CÁC BÀI KIỂM TRA 
(4 tiết) 
Bài kiểm tra số 1: 
− Thời gian: 2 tiết (90 phút) 
− Hình thức: Thực hành trên máy 
− Nội dung: 
ο Kiểu dữ liệu có cấu trúc 
ο Áp dụng các phương pháp tìm kiếm và sắp xếp 
Bài kiểm tra số 2: 
− Thời gian: 2 tiết (90 phút) 
− Hình thức: Thực hành trên máy 
− Nội dung: 
ο Các kiểu danh sách và ứng dụng 
TÀI LIỆU THAM KHẢO 
[1] Trương Chí Tín, Cấu trúc dữ liệu và Giải thuật 1 (Giáo trình tóm tắt), Đại học Đà Lạt, 
2008 
[2] A.V. AHO , J.E. HOPCROFT , J.D. ULMANN: Data structures and algorithms. 
Addition Wesley - 1983. 
[3] DONALD KNUTH: The Art of Programming. (vol.1: Fundamental Algorithms, vol. 
3: Sorting and Searching). Addition Wesley Puplishing Company - 1973. 
[4] ĐINH MẠNH TƯỜNG: Cấu trúc dữ liệu và thuật toán. NXB KHKT - 2001. 
[5] ĐỖ XUÂN LÔI: Cấu trúc dữ liệu và thuật toán. NXB KHKT - 1995. 
[6] LARRY N. HOFF, SANFORD LEESTMA: Lập trình nâng cao bằng Pascal với các 
cấu trúc dữ liệu. Bản dịch của Lê Minh Trung. Công ty Scitec - 1991. 
[7] NGUYỄN TRUNG TRỰC: Cấu trúc dữ liệu. Trung tâm điện toán, trường ĐH Bách 
khoa TP. HCM – 1992. 
[8] NIKLAUS WIRTH: Cấu trúc dữ liệu + Giải thuật = Chươngtrình (Nguyễn Quốc 
Cường dịch). NXB ĐH và THCN – 1991 
[9] TRẦN HẠNH NHI & DƯƠNG ANH ĐỨC: Nhập môn cấu trúc dữ liệu và thuật toán. 
Khoa Công nghệ thông tin, ĐH KHTN TP HCM – 2000.