[email protected]
New Member
Download miễn phí Bài giảng tóm tắt Cấu trúc dữ liệu và thuật giải 1
MỤC LỤC
MỤC LỤC
LỜI NÓI ĐẦU
CHƯƠNG 1:
GIỚI THIỆU CẤU TRÚC DỮLIỆU VÀ PHÂN TÍCH THUẬT GIẢI . 5
1.1 Từbài toán đến chương trình . 5
1.1.1 Mô hình hóa bài toán thực tế. 5
1.1.2 Thuật giải (algorithms) . 8
1.2 Kiểu dữliệu trừu tượng (Abstract Data Type - ADT) . 13
1.2.1 Khái niệm trừu tượng hóa . 13
1.2.2 Trừu tượng hóa chương trình . 13
1.2.3 Trừu tượng hóa dữliệu . 14
1.2.4 Kiểu dữliệu, cấu trúc dữliệu và kiểu dữliệu trừu tượng (Data Types, Data
Structures, Abstract Data Types) . 15
1.3 PHÂN TÍCH THUẬT GIẢI . 16
1.3.1 Thuật giải và các vấn đềliên quan . 16
1.3.2 Tính hiệu quảcủa thuật giải . 17
1.3.3 Ký hiệu O và biểu diễn thời gian chạy bởi ký hiệu O . 20
1.3.4 Đánh giá thời gian chạy của thuật giải . 24
CHƯƠNG 2:
TÌM KIẾM VÀ SẮP XẾP TRONG . 33
2.1 Các phương pháp tìm kiếm trong . 33
2.1.1 Phương pháp tìm kiếm tuyến tính . 33
2.1.2 Tìm kiếm nhịphân . 35
2.2 Các phương pháp sắp xếp trong . 37
2.2.1 Thuật giải sắp xếp chọn (Selection Sort) . 38
2.2.2 Thuật giải sắp xếp chèn (Insertion Sort) . 41
2.2.3 Thuật giải sắp xếp đổi chỗtrực tiếp (Interchange Sort) . 44
2.2.4 Thuật giải sắp xếp nổi bọt (Bubble Sort) . 46
2.2.5 Thuật giải shaker (Shaker Sort) . 48
2.2.6 Thuật giải Shell (Shell Sort) . 49
2.2.7 Thuật giải vun đống (Heap Sort) . 51
2.2.8 Thuật giải sắp xếp nhanh (Quick Sort) . 55
2.2.9 Thuật giải sắp xếp trộn (Merge Sort) . 59
2.2.10 Phương pháp sắp xếp theo cơsố(Radix Sort) . 64
CHƯƠNG 3:
CẤU TRÚC DANH SÁCH LIÊN KẾT . 72
3.1 Giới thiệu đối tượng dữliệu con trỏ. 72
3.1.1 Cấu trúc dữliệu tĩnh và cấu trúc dữliệu động . 72
3.1.2 Kiểu con trỏ. 72
3.2 Danh sách liên kết . 75
3.2.1 Định nghĩa . 75
3.2.2 Tổchức danh sách liên kết . 76
3.3 Danh sách liên kết đơn . 77
3.3.1 Tổchức danh sách theo cách cấp phát liên kết. . 77
3.3.2 Định nghĩa cấu trúc danh sách liên kết . 79
3.3.3 Các thao tác cơbản trên danh sách liên kết đơn . 80
3.4 Sắp xếp danh sách . 94
3.5 Một sốcấu trúc đặc biệt của danh sách liên kết đơn . 97
3.5.1 Ngăn xếp (Stack) . 97
3.5.2 Hàng đợi (Queue) . 103
3.6 Một sốcấu trúc dữliệu dạng danh sách liên kết khác . 108
3.6.1 Danh sách liên kết vòng . 108
3.6.2 Danh sách liên kết kép . 112
TÀI LIỆU THAM KHẢO
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
xét thứ tự tăng) nghĩa là aki > aki-1.
Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy, cần
dựa vào kết quả của một loạt phép so sánh. Chính vì vậy, hai thao tác so sánh và gán là
các thao tác cơ bản của hầu hết các thuật giải sắp xếp .
Khi xây dựng một thuật giải sắp xếp cần chú ý tìm cách giảm thiểu những phép so sánh
và đổi chỗ không cần thiết để tăng hiệu quả của thuật giải.
Ðối với các dãy số được lưu trữ trong bộ nhớ chính, nhu cầu tiết kiệm bộ nhớ được đặt
nặng, do vậy những thuật giải sắp xếp đòi hỏi cấp phát thêm vùng nhớ để lưu trữ dãy
kết quả ngoài vùng nhớ lưu trữ dãy số ban đầu thường ít được quan tâm.
Phần này giới thiệu một số thuật giải sắp xếp từ đơn giản đến phức tạp có thể áp dụng
thích hợp cho việc sắp xếp trong.
2.2.1 Thuật giải sắp xếp chọn (Selection Sort)
Ý tưởng
Ta thấy rằng, nếu mảng có thứ tự, giả sử xét thứ tự tăng, phần tử ai luôn là min(ai , ai+1 ,
., aN-1 ). Ý tưởng của thuật giải chọn trực tiếp mô phỏng một trong những cách sắp xếp
tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử
này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy
hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình
trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N
phần tử, vậy tóm tắt ý tưởng thuật giải là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất
trong dãy hiện hành về vị trí đúng ở đầu dãy.
Các bước tiến hành như sau :
Mô tả thuật giải:
- Bước 1: i = 0;
Cấu trúc dữ liệu và thuật giải 1
39
- Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a đến
a[N-1].
- Bước 3 : Hoán vị a[min] và a
- Bước 4 : Nếu i < N-1 thì
i = i+1;
Lặp lại Bước 2
Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị trí.
Ví dụ:
Cho mảng a như sau:
i 0 1 2 3 4 5 6 7
a 25 7 15 8 18 6 4 0
Các bước thuật giải chạy để sắp xếp mảng a có thứ tự tăng như sau:
i = 0: 0 7 15 8 18 6 4 25
i = 1: 0 4 15 8 18 6 4 25
i = 2: 0 4 6 8 18 15 7 25
i = 3: 0 4 6 7 18 15 8 25
i = 4: 0 4 6 7 8 15 18 25
i = 5: 0 4 6 7 8 15 18 25
i = 6: 0 4 6 7 8 15 18 25
i = 7: Dừng
Cài đặt
Cấu trúc dữ liệu và thuật giải 1
40
Cài đặt thuật giải sắp xếp chọn trực tiếp thành hàm SelectionSort
void SelectionSort(int a[],int N )
{
int i, j, Cs_min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (i=0; i
Cs_min = i;
for( j = i+1; j
Cs_min = j; // ghi nhận vị trí phần tử hiện nhỏ nhất
Hoanvi(a[Cs_min], a);
}
}
Ðánh giá thuật giải
Ðối với thuật giải chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (N-i)
lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không
phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết
luận :
Số lần so sánh là
2
1)N(Nii)(N
1N
1i
1N
1i
−==− ∑∑ −
=
−
=
Số lần hoán vị (một phép hoán vị cần ba phép gán) phụ thuộc vào tình trạng ban đầu
của dãy, ta có thể ước lượng trong từng trường hợp như sau:
Trường hợp Số lần so sánh Số phép gán
Cấu trúc dữ liệu và thuật giải 1
41
Tốt nhất N(N-1)/2 0
Xấu nhất N(N-1)/2 3N(N-1)/2
2.2.2 Thuật giải sắp xếp chèn (Insertion Sort)
Ý tưởng
Giả sử có một dãy a0, a1 ,... ,aN-1 trong đó i phần tử đầu tiên a0, a1 ,... ,ai-1 đã có thứ tự. Ý
tưởng chính của phương pháp chèn trực tiếp là tìm cách chèn phần tử ai vào vị trí thích
hợp của đoạn đã được sắp để có dãy mới a0, a1,... ,ai có thứ tự.
Vị trí này có thể là:
• Trước a0
• Sau ai-1
• Giữa hai phần tử ak-1 và ak thỏa ak-1 ≤ ai < ak (1≤ k ≤ i-1).
Cho dãy ban đầu a0, a1,... ,aN-1, ta có thể xem như đã có đoạn gồm một phần tử a0 đã
được sắp, sau đó thêm a1 vào đoạn a0 sẽ có đoạn a0 a1 được sắp; tiếp tục thêm a2 vào
đoạn a0 a1 để có đoạn a0 a1 a2 được sắp; tiếp tục cho đến khi thêm xong aN-1 vào đoạn a0
a1 ... aN-2 sẽ có dãy a0 a1.... aN-1 được sắp. Các bước tiến hành như sau:
Mô tả thuật giải:
Bước 1: i = 1; // đoạn có 1 phần tử a[0] đã được sắp
Bước 2: x = a; Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn x vào.
Bước 3: Dời các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a.
Bước 4: a[pos] = x; // có đoạn a[0]..a đã được sắp
Bước 5: i = i+1;
Nếu i < N-1 : Lặp lại Bước 2.
Ngược lại : Dừng.
Ví dụ
Xét dãy a trong ví dụ trên. Chạy thuật giải sắp xếp chèn
Cấu trúc dữ liệu và thuật giải 1
42
i = 1: 7 25 15 8 18 6 4 0
i = 2: 7 15 25 8 18 6 4 0
i = 3: 7 8 15 25 18 6 4 0
i = 4: 7 8 15 18 25 6 4 0
i = 5: 6 7 8 15 18 25 4 0
i = 6: 4 6 7 8 15 18 25 0
i = 7: 0 4 6 7 8 15 18 25
Cài đặt
Cài đặt Thuật giải sắp xếp chèn trực tiếp thành hàm InsertionSort
void InsertionSort(int a[], int N )
{
int pos, i, x;
for( i=1 ; i
x = a; //lưu giá trị a tránh bị ghi đè khi dời chỗ các phần tử.
pos = i-1;
// tiến về trái tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{// dời chỗ các phần tử sẽ đứng sau x
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;// chèn x vào dãy
}
}
Nhận xét
Cấu trúc dữ liệu và thuật giải 1
43
Khi tìm vị trí thích hợp để chèn a vào đoạn a[0] đến a[i-1], do đoạn đã được sắp, nên
có thể sử dụng thuật giải tìm nhị phân để thực hiện việc tìm vị trí pos, khi đó có thuật
giải sắp xếp chèn nhị phân:
void BInsertionSort(int a[], int N )
{
int l,r,m;
int i,j;
int x;
for(i=1 ; i
x = a; l = 0; r = i-1;
while(l<=r)
{
m = (l+r)/2;
if(x < a[m])
r = m-1;
else
l = m+1;
}
for( j = i-1 ; j >=l ; j--) // dời các phần tử sẽ đứng sau x
a[j+1] = a[j];
a[l] = x; // chèn x vào dãy
}
}
Cấu trúc dữ liệu và thuật giải 1
44
Đánh giá thuật giải
Ðối với thuật giải chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while tìm
vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ
phần tử a[pos] tương ứng. Thuật giải thực hiện tất cả N-1 vòng lặp while , do số lượng
phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể
ước lược trong từng trường hợp như sau:
2.2.3 Thuật giải sắp xếp đổi chỗ trực tiếp (Interchange Sort)
Để sắp xếp một dãy số, ta có thể xét các nghịch thế (tức là các cặp phần tử a[j], a với
a[j]i ) có trong dãy và làm triệt tiêu dần chúng đi.
Ý tưởng
Xuất phát từ đầu dãy, tìm tất cả các nghịch thế chứa phần tử này, triệt tiêu chúng bằng
cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại việc xử lý
trên với các phần tử tiếp theo trong dãy.
Mô tả thuật giải:
Bước 1: i=0; // bắt đầu từ đầu dãy
Bước 2: j=i+1;//tìm các phần tử a[j]i
Bước 3:
Trong khi j
Cấu trúc dữ liệu và thuật giải 1
45
j = j+1;
Bước 4: i=i+1;
Nếu i