Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng

Cấu trúc dữ liệu và giải thuật
Tổng quan
TS. Ngô Hữu Dũng
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
Dẫn nhập
Cấu trúc dữ liệu và giải thuật - Tổng quan
 Data structures and algorithms
 Data structures?
 Array
 Struct
 Linked list
 Stack
 Queue
 Tree
 Graph
 Algorithm?
 Search
 Sort
 Recursion
Blog ngohuudung.blogspot.com
Email ngohuudung@iuh.edu.vn
2
Nội dung
 Tổng quan
 Ôn tập căn bản
 Độ phức tạp thuật toán
 Giải thuật tìm kiếm
 Giải thuật sắp xếp
 Danh sách liên kết
 Ngăn xếp – stack
 Hàng đợi – Queue
 Cấu trúc cây – Tree
 Cấu trúc nâng cao
Cấu trúc dữ liệu và giải thuật - Tổng quan3
Tài liệu
Cấu trúc dữ liệu và giải thuật - Tổng quan
 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.
 Slide bài giảng
 Bài tập thực hành
 Đề tài bài tập lớn
 Tham khảo thêm
 Robert L.Kruse, Alexander J.Ryba, Data Structures And
Program Design In C++, PrenticeHall International Inc., 1999.
 Nguyễn Ngô Bảo Trân, Giáo trình cấu trúc dữ liệu và giải thuật 
– Trường Đại học Bách Khoa TP.HCM, 2005.
 Internet
4
Lịch trình
Cấu trúc dữ liệu và giải thuật - Tổng quan
Tuần Nội dung
Lý
thuyết
Thực
hành
Kiểm tra
1 Giới thiệu môn học- Tổng quan 3
2 Giải thuật tìm kiếm 3
3 Giải thuật sắp xếp 3 3
4 Bài toán tìm kiếm, sắp xếp 3 3
5-6 Danh sách liên kết 6 6 TK
7 Bài toán danh sách liên kết 3 3 GK
8-9 Ngăn xếp & Hàng đợi 6 6
10 Bài toán ngăn xếp & Hàng đợi 3 3
11 Cấu trúc cây 3 3 TK
12 Bài toán cấu trúc cây 3 3 Bài tập lớn
13-14 Bài toán tổng hợp 6
15 Ôn tập 3 CK
45 30
5
Kiểm tra đánh giá
Cấu trúc dữ liệu và giải thuật - Tổng quan
 Lý thuyết
 Kiểm tra thường kỳ
 Thi cuối kỳ
 Thực hành
 Kiểm tra thường kỳ
 Thi giữa kỳ
 Bài tập lớn
 Điểm liệt: <3
 Số tín chỉ: 4
 Lý thuyết: 45
 Thực hành: 30
 Tự học: 105
6
Tìm kiếm – search
Cấu trúc dữ liệu và giải thuật - Tổng quan7
 Tìm kiếm nhị phân
 Binary search
 Tìm kiếm tuyến tính
 Sequential search (Linear search)
1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
a
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
low mid high
Start here
1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
a
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Start here 
Binary vs Sequential search
Cấu trúc dữ liệu và giải thuật - Tổng quan8
Binary search – worst case
Cấu trúc dữ liệu và giải thuật - Tổng quan9
Binary search – best case
Cấu trúc dữ liệu và giải thuật - Tổng quan10
Binary search tree
Cấu trúc dữ liệu và giải thuật - Tổng quan11
 Viết mã giả cho thuật toán tìm kiếm nhị phân?
1
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
mid
low
high
How’s binary search tree work?
Cấu trúc dữ liệu và giải thuật - Tổng quan12
Sắp xếp – sort
Cấu trúc dữ liệu và giải thuật - Tổng quan13
 Selection Sort
 Insertion Sort và Shell Sort
 Interchange Sort
 Bubble sort và Shaker Sort
 Quick Sort
 Heap Sort
 Merge Sort
Các thuật toán sắp xếp
Cấu trúc dữ liệu và giải thuật - Tổng quan14
 https://www.toptal.com/developers/sorting-algorithms/
Độ phức tạp của thuật toán?
Cấu trúc dữ liệu và giải thuật - Tổng quan15
Algorithm Best case Average case Worst case
Linear search O(1) O(n) O(n)
Binary search O(1) O(log n) O(log n)
Selection sort O(n2) O(n2) O(n2)
Insertion sort O(n) O(n2) O(n2)
Bubble sort O(n) O(n2) O(n2)
Shell sort O(n) O((nlog(n))2) O((nlog(n))2)
Merge sort O(nlogn) O(nlogn) O(nlogn)
Heap sort O(nlogn) O(nlogn) O(nlogn)
Quick sort O(nlogn) O(nlogn) O(n2)
Độ phức tạp big Oh
Cấu trúc dữ liệu và giải thuật - Tổng quan16
Danh sách liên kết – Linked list
Cấu trúc dữ liệu và giải thuật - Tổng quan17
 Một dãy tuần tự các nút (Node)
 Giữa hai nút có con trỏ liên kết
 Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ
 Có thể mở rộng tuỳ ý
 
42
data next
head
pre.
42
data nextpre.
42
data nextpre.
NULLNULL
tail
42
data next
29
data next
76
data next
NULL
head
tail
Các thao tác cơ bản trên danh sách liên kết
Cấu trúc dữ liệu và giải thuật - Tổng quan18
 Thêm một nút
 Vào đầu danh sách
 Vào cuối danh sách
 Vào sau một vị trí được chỉ ra (chèn)
 Xóa một nút
 Ở đầu, cuối hoặc vị trí xác định trên danh sách
 Duyệt danh sách
 Xuất, trích xuất, đếm, tính toán
 Tìm kiếm
 Max, min, giá trị x
 Sắp xếp danh sách
Ngăn xếp và hàng đợi – Stack & Queue
Cấu trúc dữ liệu và giải thuật - Tổng quan19
34 56 45 37 19 28
34 56 45 37 19 28 EnqueueDequeue
Queue – First in, first out
Stack – Last in, first out
Push
Pop
Front Rear
Top
Ví dụ về Stack và Queue
Cấu trúc dữ liệu và giải thuật - Tổng quan20
Cấu trúc cây
Cấu trúc dữ liệu và giải thuật - Tổng quan21
Củng cố kiến thức qua bài tập ví dụ
Cấu trúc dữ liệu và giải thuật - Tổng quan22
 Đề bài: Để quản lý sinh viên gồm các thông tin: ID, Tên, Điểm 
thường kỳ, Điểm giữa kỳ, Điểm cuối kỳ, và Điểm tổng kết 
(20%ĐTK + 30%ĐGK + 50%ĐCK) bạn hãy xây dựng các tác 
vụ theo mô tả sau:
1. Nhập thông tin một sinh viên
2. Xuất thông tin một sinh viên
3. Thêm một sinh viên vào danh sách
4. Xuất tất cả danh sách sinh viên
5. Tìm kiếm sinh viên theo mã
6. Xóa một sinh viên tại vị trí chỉ ra
7. Cập nhật (sửa) thông tin một sinh viên
8. Hiển thị sinh viên có số điểm cao nhất
9. Sắp xếp sinh viên theo điểm tổng kết
10. Menu thực hiện các tác vụ trên
Cấu trúc dữ liệu và giải thuật
Giải thuật tìm kiếm
TS. Ngô Hữu Dũng
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
Tìm kiếm – Searching
Cấu trúc dữ liệu và giải thuật - Tìm kiếm24
 Tìm kiếm tuần tự - Sequential search
 Còn gọi là tuyến tính – Linear search
 Danh sách chưa sắp xếp hoặc đã sắp xếp
 Thời gian tỉ lệ với n (số phần tử)
 Độ phức tạp O(n)
 Tìm kiếm nhị phân – Binary search
 Danh sách đã sắp xếp
 Thời gian tỉ lệ với log2 n
 Độ phức tạp O(log n)
Sequential search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm25
 Duyệt danh sách từ đầu đến cuối
 Dừng khi tìm thấy hoặc kết thúc danh sách
 Nếu tìm thấy: Trả về kết quả tìm thấy
 True hoặc vị trí được tìm thấy hoặc thông báo
 Nếu không tìm thấy: Trả về kết quả không tìm thấy
 False hoặc một giá trị như -1 hoặc thông báo
Sequential search – Vòng lặp
Cấu trúc dữ liệu và giải thuật - Tìm kiếm26
 Trả về vị trí khi tìm thấy
 Trả về -1 khi không tìm thấy
 Lưu ý: Các code chỉ mang tính minh hoạ cho giải thuật
 Có nhiều cách diễn đạt và cải tiến thuật toán
1. int linearSearch(int a[], int n, int x)
2. {
3. int i;
4. for(i=0; i<n; i++)
5. if(a[i] == x)
6. return i;
7. return -1;
8. }
Sequential search – Vòng lặp
Cấu trúc dữ liệu và giải thuật - Tìm kiếm27
 Trả về kiểu bool
 True: Tìm thấy
 False: Không tìm thấy
1. bool linearSearch(int a[], int n, int x)
2. {
3. int i;
4. for(i=0; i<n; i++)
5. if(a[i] == x)
6. return true;
7. return false;
8. }
Sequential search – Thông báo
Cấu trúc dữ liệu và giải thuật - Tìm kiếm28
 Xuất ra màn hình kết quả
1. void linearSearch(int a[], int n, int x)
2. {
3. int i;
4. for(i=0; i<n; i++)
5. if(a[i] == x)
6. {
7. printf("Tim thay o vi tri %d", i);
8. break;
9. }
10. if(i==n)
11. printf("Khong tim thay");
12.}
Sequential search – Cờ hiệu
Cấu trúc dữ liệu và giải thuật - Tìm kiếm29
 Dùng cờ hiệu: Chương trình rõ ràng, dễ hiểu
1. void linearSearch(int a[], int n, int x)
2. {
3. int i, flag = 0; // Chưa tìm thấy
4. for(i=0; i<n; i++)
5. if(a[i] == x){
6. printf("Tim thay o vi tri %d", i);
7. flag = 1; // Đã tìm thấy
8. break;
9. }
10. if(!flag)
11. printf("Khong tim thay");
12.}
Sequential search – Đệ quy
Cấu trúc dữ liệu và giải thuật - Tìm kiếm30
 Dùng đệ quy
 Thực hiện gọi hàm nhiều lần
1. int linearSearch(int a[], int n, int x)
2. {
3. if(n<0)
4. return -1;
5. else if(a[n-1] == x)
6. return n-1;
7. else 
8. return linearSearch(a, n-1, x);
9. }
Sequential search – Cầm canh
Cấu trúc dữ liệu và giải thuật - Tìm kiếm31
 Dùng phần tử cầm canh
 Giảm bớt số lần so sánh
1. int linearSearch(int a[], int n, int x)
2. {
3. int i = 0;
4. a[n]=x; // Phần tử cầm canh
5. while(a[i]!=x)
6. i++;
7. if(i<n)
8. return i;
9. return -1;
10.}
Sequential search – Rút gọn
Cấu trúc dữ liệu và giải thuật - Tìm kiếm32
 Giảm thiểu số phép toán
1. int linearSearch(int a[], int n, int x)
2. {
3. do{
4. n--;
5. }while(a[n]!=x && n>=0);
6. return n;
7. }
Sequential search – Hai chiều
Cấu trúc dữ liệu và giải thuật - Tìm kiếm33
 Tìm cả hai chiều
1. int doubleSearch(int a[], int n, int x)
2. {
3. int i=-1;
4. do{
5. if(a[--n]==x) return n;
6. if(a[++i]==x) return i;
7. }while(i<n);
8. return -1;
9. }
So sánh thực nghiệm
Cấu trúc dữ liệu và giải thuật - Tìm kiếm34
 Thực hiện 1 triệu phép lặp cho mỗi hàm
 Cơ bản
 Đệ quy
 Cầm canh
 Rút gọn
 Hai chiều
 Phần tử cần tìm nằm ở vị trí trong trường hợp xấu nhất 
(worst case)
 Đo thời gian thực hiện của mỗi hàm để so sánh kết quả
1. for(int i=0;i<1000; i++)
2. for(int j=0;j<1000; j++)
3. k = linearSearch(a, n, x);
Cách đo thời gian
Cấu trúc dữ liệu và giải thuật - Tìm kiếm35
 Một số IDE có sẵn chức năng đo thời gian
1. #include 
2. #include 
3. int main()
4. {
5. clock_t t = clock();
6. // Đoạn code cần đo thời gian
7. t = clock()-t;
8. printf("Time: %.2fs\n",(float)t/CLOCKS_PER_SEC);
9. return 0;
10.}
Đánh giá
Cấu trúc dữ liệu và giải thuật - Tìm kiếm36
Bài tập vận dụng
Cấu trúc dữ liệu và giải thuật - Tìm kiếm37
 Viết hàm tìm kiếm phần tử x trong khoảng từ left đến right
trong mảng.
 Nguyên mẫu hàm?
 Sử dụng hàm?
Binary search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm38
 Danh sách đã được sắp xếp, giả sử tăng dần
 So sánh X với phần tử ở giữa danh sách
 Nếu bằng nhau: Tìm kiếm thành công
 Nếu X nhỏ hơn: Tiếp tục tìm bên trái danh sách
 Nếu X lớn hơn: Tiếp tục tìm bên phải danh sách
Binary search – Iteration
Cấu trúc dữ liệu và giải thuật - Tìm kiếm39
1. int binarySearch(int a[],int left,int right,int x)
2. {
3. while(left<=right)
4. {
5. int mid = (left + right)/2;
6. if(x==a[mid])
7. return mid;
8. if(x<a[mid])
9. right = mid-1;
10. else
11. left = mid+1;
12. }
13. return -1;
14.}
Binary search – Recursion
Cấu trúc dữ liệu và giải thuật - Tìm kiếm40
1. int binarySearch(int a[],int left,int right,int x)
2. {
3. if (left <= right)
4. {
5. int mid = left + (right - left)/2; //?
6. if (x == a[mid])
7. return mid;
8. if (x < a[mid]) 
9. return binarySearch(a, left, mid-1, x);
10. else
11. return binarySearch(a, mid+1, right, x);
12. }
13. return -1;
14.}
Exponential Search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm41
 Bao gồm hai bước
 Xác định vùng chứa X trong mảng
 Lần lượt so sánh X với các phần tử i bắt đầu từ 1, 2, 4, 8, 16 tăng 
dần theo lũy thừa 2.
 Khi tìm được vị trí của phần tử i có giá trị lớn hơn X, vùng cần tìm là 
từ i/2 đến min(i,n)
 Dùng binary search để tìm trong vùng đã xác định
1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
0
20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
21 22 23
1
Exponential Search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm42
1. int exponentialSearch(int a[], int n, int x)
2. {
3. if (a[0] == x)
4. return 0;
5.
6. int i=1;
7. while (i < n && a[i] <= x)
8. i = i*2;
9. return binarySearch(a, i/2, (i<n)?i:n, x);
10.}
Interpolation Search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm43
 Điểm mid không nhất thiết chính giữa
 Cách tính điểm ở giữa
mid = low+(x-a[low])*(high-low)/(a[high]-a[low]);
 mid sẽ gần điểm low khi x gần a[low] hơn
 mid sẽ gần điếm high khi x gần a[high] hơn
Interpolation Search
Cấu trúc dữ liệu và giải thuật - Tìm kiếm44
1. int interpolationSearch(int a[], int size, int x)
2. {
3. int low = 0, high = size – 1, mid;
4. while(high>=low && x>=a[low] && x<=a[high]) 
5. {
6. mid = low+(x-a[low])*(high-low)/(a[high]-a[low]);
7. if (a[mid] < x)
8. low = mid + 1;
9. else if (x < a[mid])
10. high = mid - 1;
11. else
12. return mid;
13. }
14. return -1;
15.}
Một kết quả so sánh
Cấu trúc dữ liệu và giải thuật - Tìm kiếm45
Độ phức tạp?
Cấu trúc dữ liệu và giải thuật - Tìm kiếm46
 Một trường hợp so sánh không đánh giá đầy đủ về các 
thuật toán
 Cần nhiều trường hợp hơn
Algorithm Best case Average case Worst case
Linear search O(1) O(n) O(n)
Binary search O(1) O(log n) O(log n)
Exponential Search O(1) O(log i) O(log i)
Với i là vị trí cần tìm 
Interpolation Search O(1) O(log(log n)) O(n)
Bài tập vận dụng
Cấu trúc dữ liệu và giải thuật - Tìm kiếm47
 Viết chương trình
 Phát sinh ngẫu nhiên một mảng tăng dần
 Cài đặt các hàm tìm kiếm
 Tìm giá trị x nhập từ bàn phím
 Xuất ra số lần so sánh của mỗi phương pháp
 Đánh giá các phương pháp
 Tìm hiểu hoặc đề xuất phương pháp mới
Cấu trúc dữ liệu và giải thuật
Giải thuật sắp xếp
TS. Ngô Hữu Dũng
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
Sắp xếp – sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp49
 Selection Sort
 Insertion Sort
 Bubble sort
 Shell Sort
 Merge Sort
 Heap Sort
 Quick Sort
 Lưu ý: Các code ở đây chỉ mang tính chất minh hoạ 
cho giải thuật
 Có nhiều cách diễn đạt và cải tiến thuật toán
Các thuật toán sắp xếp
Cấu trúc dữ liệu và giải thuật - Sắp xếp50
 https://www.toptal.com/developers/sorting-algorithms/
Interchange sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp51
1. void interchangeSort(int a[], int n)
2. {
3. for(int i=0; i<n-1; i++)
4. for(int j=i+1; j<n; j++)
5. if(a[i]>a[j])
6. swap(&a[i], &a[j]);
7. }
 51 90 26 23 63
 26 90 51 23 63 Thừa vô ích
 23 90 51 26 63
 23 51 90 26 63
 23 26 90 51 63
 23 26 51 90 63 Luôn lặp n2 lần
 23 26 51 63 90 Có nhiều hoán vị thừa
Insertion sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp52
 for i = 2:n,
 for (k = i; k > 1 and a[k] < a[k-1]; k--)
 swap a[k,k-1]
 → invariant: a[1..i] is sorted
 end
 51 90 26 23 63
 26 51 90 23 63 Dịch chuyển nhiều phần tử
 23 26 51 90 63 Dịch chuyển nhiều lần
 23 26 51 63 90 Luôn lặp n2 lần
Insertion sort – Minh hoạ
Cấu trúc dữ liệu và giải thuật - Sắp xếp53
1. void insertionSort(int a[], int n)
2. {
3. int i, key, j;
4. for (int i = 1; i < n; i++)
5. {
6. int temp = a[i];
7. int j = i-1;
8.
9. while (j >= 0 && a[j] > temp)
10. {
11. a[j+1] = a[j];
12. j = j-1;
13. }
14. a[j+1] = temp;
15. }
16.}
Selection sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp54
 for i = 1:n,
 k = i
 for j = i+1:n, if a[j] < a[k], k = j
 → invariant: a[k] smallest of a[i..n]
 swap a[i,k]
 → invariant: a[1..i] in final position
 end
Selection sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp55
 51 90 26 23 63
 23 90 26 51 63
 23 26 90 51 63
 23 26 51 90 63
 23 26 51 63 90
 Loại những hoán vị thừa ở thuật toán cơ bản
Selection sort – Minh hoạ
Cấu trúc dữ liệu và giải thuật - Sắp xếp56
1. void selectionSort(int a[], int n)
2. {
3. for(int i=0; i<n; i++)
4. {
5. int k = i;
6. for(int j=i+1; j<n; j++)
7. if (a[j]<a[k])
8. k=j;
9. if(i!=k)
10. swap(&a[i], &a[k]);
11. }
12.}
Bubble Sort
Cấu trúc dữ liệu và giải thuật - Sắp xếp57
 for i = 1:n,
 swapped = false
 for j = n:i+1,
 if a[j] < a[j-1],
 swap a[j,j-1]
 swapped = true
 → invariant: a[1..i] i ... pNext;
} STACK_NODE;
typedef struct STACK 
{
int StkCount;
STACK_NODE *StkTop;
};
193
Stack – Sử dụng DSLK
 VD: Thực hiện một số thao tác trên stack
STACK s;
InitStack(s);
Push(s, 7);
Push(s, 4);
Pop(s, x); // x = ?
N
StkCnt StkTop
7
Data Link
4
194
Stack số nguyên – Sử dụng DSLK
void InitStack(STACK &s)
{
s.StkTop = NULL;
s.StkCount = 0;
}
195
Stack số nguyên – Sử dụng DSLK
bool IsEmpty(const STACK &s)
{
if (s.StkTop == NULL)
return true;
return false;
}
196
Stack số nguyên – Sử dụng DSLK
bool IsFull (const STACK s)
{
STACK_NODE* temp = new STACK_NODE;
if (temp == NULL)
return true;
delete temp;
return false;
}
197
Stack số nguyên – Sử dụng DSLK
bool Push(STACK &s, int newitem)
{
if (IsFull(s))
return false;
STACK_NODE *pNew = new STACK_NODE;
pNew->Data = newitem;
pNew->pNext = s.StkTop;
s.StkTop = pNew;
s.StkCount++;
return true;
}
N
StkCnt StkTop
7
Data Link
4
198
Stack số nguyên – Sử dụng DSLK
bool Pop(STACK &s, int &outitem)
{
if (IsEmpty(s))
return false;
STACK_NODE *temp = s.StkTop;
outitem = s.StkTop->Data;
s.StkTop = s.StkTop->pNext;
delete temp;
s.StkCount--;
return true;
}
N
StkCnt StkTop
7
Data Link
4
Data Link
temp
outitem = 4
199
Stack – Ứng dụng
 Stack có nhiều ứng dụng:
 Lưu vết trong thuật toán “back-tracking” (theo dõi
dấu vết)
 Tính giá trị biểu thức toán học (thuật toán Balan
ngược)
 Khử đệ quy
 
200
Stack – Quick Sort
 Để khử đệ quy cho Quick Sort, ta sử dụng một stack để
lưu lại các partition (phân hoạch) cần tiến hành sắp xếp.
 Ý tưởng:
 Push phân hoạch đầu tiên (0, n-1) vào stack
 Trong khi stack chưa rỗng
 Pop một phân hoạch từ stack
 Chọn phần tử trục trên phân hoạch này
 Điều chỉnh phân hoạch tương ứng với trục
 Push 2 phân hoạch bên trái và phải trục vào stack
201
Stack – Quick Sort
 Push phân hoạch đầu tiên (0, n-1) vào stack
 Trong khi stack chưa rỗng
 Pop một phân hoạch từ stack
 Chọn phần tử trục trên phân hoạch này
 Điều chỉnh phân hoạch tương ứng với trục
 Push 2 phân hoạch bên trái và phải trục vào stack
(0,4)
1 5 4 7 3
0 1 2 3 4
i j
t
3 5
1
(3,4)
5 7
Stack rỗng
Stop
202
Queue
Hàng đợi
Cấu trúc dữ liệu và giải thuật - Stack&Queue203
34 56 45 37 enQueuedeQueue
Front Rear
Queue – First in, first out
Queue
Phòng vé
204
Queue – Định nghĩa
 Hàng đợi là một cấu trúc:
 Gồm nhiều phần tử có thứ tự
 Hoạt động theo cơ chế “Vào trước, ra trước” (FIFO - First In 
First Out)
205
Queue – Định nghĩa
 Các thao tác cơ bản trên hàng đợi:
 InitQueue: khởi tạo hàng đợi rỗng
 IsEmpty: kiểm tra hàng đợi rỗng?
 IsFull: kiểm tra hàng đợi đầy?
 EnQueue: thêm 1 phần tử vào cuối hàng
đợi, có thể làm hàng đợi đầy
 DeQueue: lấy ra 1 phần tử từ đầu Queue, 
có thể làm Queue rỗng
206
Queue
 Minh họa thao tác EnQueue
 Minh họa thao tác DeQueue
207
Cách xây dựng Queue
 Sử dụng mảng một chiều
 Sử dụng danh sách liên kết đơn
208
Queue – Sử dụng mảng
 Dùng 1 mảng (QArray) để chứa các phần tử.
 Dùng 1 số nguyên (QMax)để lưu số phần tử tối
đa trong hàng đợi
 Dùng 2 số nguyên (QFront, QRear) để xác định
vị trí đầu, cuối hàng đợi
 Dùng 1 số nguyên (QNumItems) để lưu số phần
tử hiện có trong hàng đợi
209
Queue – Sử dụng mảng
0 1 2 3 4 5 6
Qarray 37 22 15 3
QMax = 7
QNumItems = 4
QFront = 1
QRear = 4
210
Queue số nguyên – Sử dụng mảng
typedef struct QUEUE 
{
int* QArray;
int QMax;
int QNumItems;
int QFront;
int QRear;
};
211
Queue số nguyên – Sử dụng mảng
 Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả”
 Giải pháp? Nối dài mảng (mảng động) hay sử dụng một
mảng vô cùng lớn?
0 1 2 3 4 5 6
Qarray 37 22 15 3 7 9
QMax = 7
QNumItems = 6
QFront = 1
QRear = 6
212
Queue số nguyên – Sử dụng mảng
 Xử lý mảng như một danh sách liên kết vòng
0 1 2 3 4 5 6
Qarray 37 22 15 3 7 9
QMax = 7
QNumItems = 6
QFront = 1
QRear = 6
213
Chỉ số mảng 0 1 2 3 4 5 6
QArray 11 7 19 21 81
QMax 7
QNumItems 5
QFront 1
QRear 5
VD: Cho queue như sau
Queue số nguyên – Sử dụng mảng
1. Thêm giá trị 123 vào hàng đợi
Queue số nguyên – Sử dụng mảng
Chỉ số mảng 0 1 2 3 4 5 6
QArray 11 7 19 21 81 123
QMax 7
QNumItems 6
QFront 1
QRear 6
2. Lấy một phần tử khỏi hàng đợi
Queue số nguyên – Sử dụng mảng
Chỉ số mảng 0 1 2 3 4 5 6
QArray 11 7 19 21 81 123
QMax 7
QNumItems 5
QFront 2
QRear 6
3. Thêm giá trị 456 vào hàng đợi
Queue số nguyên – Sử dụng mảng
Chỉ số mảng 0 1 2 3 4 5 6
QArray 456 11 7 19 21 81 123
QMax 7
QNumItems 6
QFront 2
QRear 0
Queue số nguyên – Sử dụng mảng
bool InitQueue(QUEUE &q, int MaxItem)
{
q.QArray = new int[MaxItem];
if (q.QArray == NULL)
return false;
q.QMax = MaxItem;
q.QNumItems = 0;
q.QFront = q.QRear = -1;
return true;
}
218
Queue số nguyên – Sử dụng mảng
bool IsEmpty(QUEUE q)
{
if (q.QNumItems == 0)
return true;
return false;
}
219
Queue số nguyên – Sử dụng mảng
bool IsFull(QUEUE q)
{
if (q.QMax == q.QNumItems)
return true;
return false;
}
220
Queue số nguyên – Sử dụng mảng
bool EnQueue(QUEUE &q, int newitem)
{
if (IsFull(q))
return false;
q.QRear++;
if (q.QRear==q.QMax)
q.QRear = 0;
q.QArray[q.QRear] = newitem;
if (q.QNumItems==0)
q.QFront = 0;
q.QNumItems++;
return true;
}
221
Queue số nguyên – Sử dụng mảng
bool DeQueue(QUEUE &q, int &itemout)
{
if (IsEmpty(q))
return false;
itemout = q.QArray[q.QFront];
q.QFront++;
q.QNumItems--;
if (q.QFront==q.QMax)
q.QFront = 0;
if (q.QNumItems==0)
q.QFront = q.QRear = -1;
return true;
}
222
Queue số nguyên – Sử dụng mảng
bool QueueFront(const QUEUE &q, int &itemout)
{
if (IsEmpty(q))
return false;
itemout = q.QArray[q.QFront];
return true;
}
223
Queue số nguyên – Sử dụng mảng
bool QueueRear(const QUEUE &q, int &itemout)
{
if (IsEmpty(q))
return false;
itemout = q.QArray[q.QRear];
return true;
}
224
Queue – Ví dụ ứng dụng
 Quản lý việc thực hiện các tác vụ (task) trong môi
trường xử lý song song
 Hàng đợi in ấn các tài liệu
 Vùng nhớ đệm (buffer) dùng cho bàn phím
 Quản lý thang máy
225
Queue – Sử dụng DSLK
typedef struct tagNODE
{
int data;
tagNODE* pNext;
} NODE, *PNODE;
typedef struct tagQUEUE
{
int NumItems;
PNODE pFront, pRear;
} QUEUE;
226
Queue – Sử dụng DSLK
 Các thao tác cơ bản
bool InitQueue(QUEUE &q);
bool IsEmpty(const QUEUE &q);
bool IsFull(const QUEUE &q);
bool EnQueue(QUEUE &q, int newitem);
bool DeQueue(QUEUE &q, int& itemout);
227
Queue – Sử dụng DSLK
bool InitQueue(QUEUE &q)
{
q.NumItems = 0;
q.pFront = q.pRear = NULL;
return true;
}
228
Queue – Sử dụng DSLK
bool IsEmpty(const QUEUE& q)
{
return (q.NumItems==0);
}
229
Queue – Sử dụng DSLK
bool IsFull(const QUEUE &q)
{
PNODE tmp = new NODE;
if (tmp==NULL)
return true;
delete tmp;
return false;
}
230
Queue – Sử dụng DSLK
bool EnQueue(QUEUE &q, int newitem)
{
if (IsFull(q))
return false;
PNODE p = new NODE;
p->data = newitem;
p->pNext = NULL;
if (q.pFront==NULL && q.pRear==NULL)
q.pFront = q.pRear = p;
else
{
q.pRear->pNext = p;
q.pRear = p;
}
q.NumItems++;
return true;
}
231
Queue – Sử dụng DSLK
bool DeQueue(QUEUE &q, int &itemout)
{
if (IsEmpty(q))
return false;
PNODE p = q.pFront;
q.pFront = p->pNext;
itemout = p->data;
q.NumItems--;
delete p;
if (q.NumItems==0)
InitQueue(q);
return true;
}
232
Data structures and algorithms
Tree structure
INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY
Nội dung
1. Khái niệm
2. Đặc điểm
3. Hình dạng
4. Định nghĩa kiểu dữ liệu
5. Các lưu ý khi cài đặt
6. Các thao tác
234
Khái niệm
 Bậc của một nút: là số cây
con của nút đó
 Nút gốc: là nút không có nút
cha
 Nút lá: là nút có bậc bằng 0
 Nút nhánh: là nút có bậc khác
0 và không phải là gốc
235
2
22
110
0
0
0
Mức 3
Mức 2
Mức 1
Mức 0
Khái niệm
 Độ dài đường đi từ
gốc đến nút x: là số
nhánh cần đi qua kể
từ gốc đến x
 Độ cao của cây: Độ
dài đường đi từ gốc
đến nút lá ở mức thấp
nhất
236
Đặc điểm cây nhị phân tìm kiếm
 Là cây nhị phân
 Giá trị của một node bất kỳ
luôn lớn hơn giá trị của tất cả
các node bên trái và nhỏ hơn
giá trị tất cả các node bên
phải
 Nút có giá trị nhỏ nhất nằm ở
trái nhất của cây
 Nút có giá trị lớn nhất nằm ở
phải nhất của cây
237
7
3 36
1 6 15 40
234
Định nghĩa kiểu dữ liệu
238
typedef struct TNODE
{
 Key;
struct TNODE *pLeft, *pRight;
} *TREE; 
Nút
Giá trị
Trỏ trái Trỏ phải
TNODE
Key
pLeft pRight
Ví dụ khai báo
typedef struct TNODE
{
int Key;
struct TNODE *pLeft, *pRight;
} *TREE;
239
Các lưu ý khi cài đặt
Bước 1: Khai báo kiểu dữ liệu biểu diễn cây
Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây
Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, 
240
Cấu trúc chương trình
241
Khai báo cấu trúc cây
Khởi tạo cây rỗng
Xây dựng cây
Các thao tác
Hủy cây
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
242
Tạo cây
243
401546136
7 36 3 1 6 4 15 40
7  Nếu node cần thêm
nhỏ hơn node đang
xét thì thêm về bên
trái
 Ngược lại thì thêm
về bên phải
Hàm tạo cây
244
int ThemNut (TREE & t, int x)
{ if(t!=NULL)
{ if(x==t->Key) return 0; // x đã có trong cây
else
{ if(xKey) return ThemNut(t->pLeft, x);
else return ThemNut(t->pRight, x);
}
}
else
{ t=new TNODE;
if(t==NULL) return -1; //không đủ bộ nhớ
t->Key=x;
t->pLeft=t->pRight=NULL;
return 1; //thêm x thành công
}
}
Duyệt cây
Thứ tự trước (NLR)
Thứ tự giữa (LNR)
Thứ tự sau (LRN)
245
246
Bước Kết quả duyệt theo thứ tự NLR
1 7 L7 R7
2 3 L3 R3 R7
3 1 R3 R7
4 6 L6 R7
5 4 R7
6 36 L36 R36
7 15 R15 R36
8 23 R36
9 40
KQ 7 3 1 6 4 36 15 23 40
7
3 36
1 6 15 40
234
Hàm duyệt NLR
Tại node t đang xét, nếu khác
rỗng thì
 In giá trị của t
 Duyệt cây con bên trái của t
theo thứ tự NLR
 Duyệt cây con bên phải của
t theo thứ tự NLR
247
void NLR (TREE t)
{
if(t!=NULL)
{
coutKey<<“\t”;
NLR(t->pLeft);
NLR(t->pRight);
}
}
Bài tập
Vẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang
phải và duyệt cây theo thứ tự trước:
a. 27; 19; 10; 21; 35; 25; 41; 12; 46; 7
b. H; B; C; A; E; D; Z; M; P; T
c. Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc
Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang;
Tiền Giang; Bình Dương; Hải Dương
248
249
Bước Kết quả duyệt theo thứ tự LNR
1 L7 7 R7
2 L3 3 R3 7 R7
3 1 3 R3 7 R7
4 3 R3 7 R7
5 L6 6 7 R7
6 4 6 7 R7
7 6 7 R7
8 7 R7
9 L36 36 R36
10 15 R15 36 R36
11 23 36 R36
12 36 R36
13 40
KQ 1 3 4 6 7 15 23 36 40
7
3 36
1 6 15 40
234
Hàm duyệt LNR
Tại node t đang xét, nếu khác
rỗng thì
 Duyệt cây con bên trái của t
theo thứ tự LNR
 In giá trị của t
 Duyệt cây con bên phải của
t theo thứ tự LNR
250
void LNR (TREE t)
{
if(t!=NULL)
{
LNR(t->pLeft);
coutKey<<“ “;
LNR(t->pRight);
}
}
251
Bước Kết quả duyệt theo thứ tự LRN
1 L7 R7 7
2 L3 R3 3 R7 7
3 1 R3 3 R7 7
4 L6 6 3 R7 7
5 4 6 3 R7 7
6 6 3 R7 7
7 3 R7 7
8 L36 R36 36 7
9 R15 15 R36 36 7
10 23 15 R36 36 7
11 15 R36 36 7
12 40 36 7
13 36 7
14 7
KQ 1 4 6 3 23 15 40 36 7
7
3 36
1 6 15 40
234
Hàm duyệt LRN
Tại node t đang xét, nếu
khác rỗng thì
 Duyệt cây con bên trái của
t theo thứ tự LRN
 Duyệt cây con bên phải
của t theo thứ tự LRN 
 In giá trị của t 
252
void LRN (TREE t)
{
if(t!=NULL)
{
LRN(t->pLeft);
LRN(t->pRight);
coutKey<<“ “;
}
}
Bài tập
 Bài 4 Vẽ cây nhị phân tìm kiếm theo thứ tự
nhập:
27, 19, 10, 21, 3, 15, 41, 50, 30, 27
Hãy duyệt cây trên theo thứ tự giữa
 Bài 5 Vẽ cây nhị phân tìm kiếm theo thứ tự
nhập:
H, B, C, A, E, D, T, M, X, O
Hãy duyệt cây trên theo thứ tự sau
253
Vấn đề cần quan tâm
Tạo cây từ kết quả duyệt NLR
Chọn giá trị đầu tiên làm node gốc
Lần lượt đưa các giá trị còn lại từ trái sang
phải vào cây theo nguyên tắc tạo cây
Tạo cây từ kết quả duyệt LRN
Chọn giá trị cuối cùng làm node gốc
Lần lượt đưa các giá trị còn lại từ phải sang
trái vào cây theo nguyên tắc tạo cây
254
Vấn đề cần quan tâm
Tạo cây từ kết quả duyệt LNR
 Gọi r: Số lượng giá trị cho trước
 Gọi m = r div 2: Giá trị ở giữa
 Chọn giá trị thứ m làm node gốc
 Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về
trái vào cây theo nguyên tắc tạo cây
 Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến
cuối vào cây theo nguyên tắc tạo cây
255
Bài tập
Bài 6 Vẽ cây nhị phân tìm kiếm T biết rằng
khi duyệt cây T theo thứ tự NLR thì được dãy
sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19
 Hãy duyệt cây T trên theo thứ tự LRN
 Liệt kê các nút lá của cây. Liệt kê các nút
nhánh của cây
256
Bài 7 Vẽ cây nhị phân tìm kiếm T biết rằng
khi duyệt cây T theo thứ tự LRN thì được
dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30,
20, 8
 Hãy duyệt cây T trên theo thứ tự NLR
 Cây T có chiều cao là bao nhiêu? Tìm các
đường đi từ gốc có độ dài là 4 trên cây
257
Bài tập
Hàm nhập dữ liệu vào cây
void Nhap(TREE &t)
{
int x;
do{
cout<<“Nhap gia tri: “;
cin>>x;
int kq=ThemNut(t, x);
if(kq==0||kq==-1)
break;
}while (true);
}
258
Hàm main gọi thao tác duyệt LNR
void main()
{
TREE t;
t=NULL;
Nhap(t);
cout<<“Duyet cay theo thu tu giua: “;
LNR(t);
Huy(t);
}
259
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
260
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
261
Cho biết các thông tin của cây
1. Số node lá (node bậc 0) 
2. Số node có 1 cây con (node bậc 1) 
3. Số node chỉ có 1 cây con phải
4. Số node chỉ có 1 cây con trái
5. Số node có 2 cây con (node bậc 2)
6. Độ cao của cây
7. Số node của cây
8. Các node trên từng mức của cây
9. Độ dài đường đi từ gốc đến node x 
262
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
263
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
264
Tìm kiếm
1. Tìm x
2. Tìm min
3. Tìm min của cây con bên phải
4. Tìm max
5. Tìm max của cây con bên trái
265
Ví dụ tìm x = 23
266
7
3 36
1 6 15 40
234
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
267
Các thao tác
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
268
Xóa node trên cây
1. Node lá
2. Node có 1 cây con
3. Node có 2 cây con 
269
7
3 36
1 6 15 40
234
Xóa node lá
Xóa 1
Xóa 23
270
7
3 36
1 6 15 40
234
Xóa node 1 cây con
Xóa 6
Xóa 15
271
7
3 36
1 6 15 40
234
4 23
Xóa node 2 cây con
Tìm node thế mạng
 Cách 1: Tìm node trái nhất
của cây con phải
(min của T->Right)
 Cách 2: Tìm node phải nhất
của cây con trái
(max của T->Left)
Xóa 36 (Cách 2)
272
7
3 36
1 6 15 40
234
16
23
Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15,
35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14
 Vẽ cây nhị phân tìm kiếm cho dãy số trên
 Cho biết kết quả duyệt cây trên theo thứ tự trước,
giữa và sau
 Cho biết độ cao của cây, các nút lá, các nút có bậc 2
 Vẽ lại cây sau khi thêm nút: 25 và 91
 Trình bày từng bước và vẽ lại cây sau khi lần lượt
xoá các nút: 11 và 35
273