dc1
Đề cương ôn tập
12 Đồ thị
a) Mô tả và so sánh hai phương pháp biểu diễn (cài đặt) đồ thị. Làm trên đồ thị ví dụ.
Mô tả :
- Ma trận kề: trong đồ thị đồ thị N đỉnh được lưu trong mảng A hai chiều cỡ N, trong đó
A[u][v] = 1 nếu có cung (u,v)
A[u][v] = 0 nếu không có cung (u,v)
- Danh sách liên kết: với mỗi đỉnh ta lập một danh sách các đỉnh kề đỉnh đó Trong đó mỗi thành phần của danh sách này sẽ chứa số hiệu của một đỉnh kề và con trỏ trỏ tới thành phần đi sau. Chúng ta sẽ sử dụng một mảng A lưu các con trỏ trỏ tới đầu mỗi danh sách, trong đó A[i] lưu con trỏ trỏ tới đầu danh sách các đỉnh kề với đỉnh i.
So sánh:
Ma trận kề
Danh sách kề
- - truy cập tới thành phần A[i][j] của mảng ta biết ngay được có cung (i,j) hay không và độ dài của cung đó (nếu là đồ thị có trọng số).
- - Tốn dung lượng bộ nhớ
- Vd:
0
1
2
3
4
0
0
1
0
1
0
1
0
0
1
0
1
2
1
0
0
1
1
3
0
0
0
0
0
4
0
0
0
1
0
- muốn biết có cung (i,j) hay không và độ dài của nó bằng bao nhiêu, ta lại phải tiêu tốn thời gian để duyệt danh sách các đỉnh kề của đỉnh i.
- Tốn ít dung lượng bộ nhớ
b) Các thuật toán trên đồ thị: ý tưởng, giả mã, phân tích, ứng dụng,
· Đi qua theo bề rộng ((Breadth-First Search)
Ý tưởng: Tại mỗi bước, từ một đỉnh đã được thăm, ta đi thăm tất cả các đỉnh kề đỉnh đó (tức là thăm theo bề rộng).
- Trật tự các đỉnh được thăm là: đỉnh nào được thăm trước thì các đỉnh kề của nó cũng phải được thăm trước.
- Để lưu lại vết của các đỉnh đã được thăm, chúng ta sử dụng một hàng đợi Q. Mỗi khi đến thăm một đỉnh thì đỉnh đó được xen vào đuôi hàng đợi Q. Thuật toán tìm kiếm theo bề rộng xuất phát từ đỉnh v được biểu diễn bởi hàm BFS(v)
Giả mã:
BFS(v)
//Tìm kiếm theo bề rộng xuất phát từ v.{
(1) Khởi tạo hàng đợi Q rỗng;
(2) Đánh dấu đỉnh v đã được thăm;
(3) Xen v vào hàng đợi Q;
(4) while (hàng đợi Q không rỗng ){
(5) Loại đỉnh w ở đầu hàng đợi Q;
(6) for (mỗi đỉnh u kề w)
(7) if ( u chưa được thăm{
(8) Đánh dấu u đã được thăm;
(9) Xen u vào đuôi hàng đợi Q;
}
} // hết vòng lặp while.
}
BFS-Traversal (G)
// Đi qua đồ thị G=(V, E) theo bề rộng
{
(10) for (mỗi v ÎV)
(11) Đánh dấu v chưa được thăm;
(12) for (mỗi v ÎV)
(13) if (v chưa được thăm)
(14) BFS(v);
}
Phân tích :Thời gian thực hiện các dòng lệnh (10), (11) là O(|V|).
Thời gian thực hiện (12) – (14) là tổng thời gian thực hiện các lời gọi hàm BFS(v).
Thời gian chạy của BFS(v) là thời gian thực hiện vòng lặp (4). Khi thực hiện các lời gọi hàm BFS(v), thời gian truy cập tới các cung của đồ thị là O(|E|). -> Tổng thời gian thực hiện là O(|V| + |E|). (|V| số đỉnh, |E| là số cung.
Ứng dụng: Sử dụng trong sắp xếp Topo ;Vấn đề đạt tới: Giả sử v và w là hai đỉnh bất kỳ, ta muốn biết từ
đỉnh v có đường đi tới đỉnh w hay không?; Tính liên thông và thành phần liên thông của đồ thị vô hướng
· Đi qua theo độ sâu (Depth-First Search).
Ý tưởng: – Từ đỉnh u ta đến thăm một đỉnh v kề đỉnh u. Rồi lại từ đỉnh v ta đến thăm đỉnh w kề v. Cứ thế tiếp tục chừng nào có thể được.
– Khi đạt tới đỉnh v mà tại v ta không đi thăm tiếp được thì
• quay lại đỉnh u và từ đỉnh u ta đi thăm đỉnh v’ khác kề u (nếu có), rồi từ v’ lại đi thăm tiếp đỉnh kề v’,…
• Quá trình trên sẽ tiếp diễn cho tới khi ta không thể tới thăm đỉnh nào nữa.
Giả mã :
Algorithm DFS(v)
// Tìm kiếm theo độ sâu xuất phát từ v.
Input: Đỉnh v chưa được thăm
for (mỗi đỉnh u kề v)
if ( u chưa được thăm)
Đánh dấu u đã được thăm;
DFS(u)
Algorithm DFSTraversal(G)
// Đi qua đồ thị G=(V, E) theo độ sâu
for (mỗi v ∈V) Đánh dấu v chưa được thăm;
for (mỗi v ∈V)
if (v chưa được thăm)
Thăm v và đánh dấu v đã được thăm
DFS(v);
Phân tích: Dễ dàng thấy rằng, thời gian chạy của thuật toán đi qua đồ thị theo độ sâu cũng là O(|V|+|E|). Bởi vì với mỗi đỉnh u Î V, hàm DFS(u) được gọi 1lần, và khi gọi DFS(u) ta cần xem xét tất cả các cung (u,v) (vòng lặp for (mỗi đỉnh v kề u).
Ứng dụng: Sử dụng sự phân lớp các cung của đồ thị sẽ giúp ta phát hiện ra nhiều tính chất quan trọng của đồ thị, chẳng hạn, phát hiện ra đồ thị có chu trình hay không.
· Sắp xếp topo
Ý tưởng:. Cho G = (V,E) là đồ thị định hướng không có chu trình, ta cần sắp xếp các đỉnh của đồ thị thành một danh sách (topo), sao cho nếu có cung (u,v) thì u cần phải đứng trước v trong danh sách đó. Cần lưu ý rằng, danh sách topo không phải là duy nhất.
Giả mã:
Algorithm DFS(v)
// Tìm kiếm theo độ sâu xuất phát từ v.
Input: Đỉnh v chưa được thăm
for (mỗi đỉnh u kề v)
if ( u chưa được thăm)
Đánh dấu u đã được thăm;
DFS(u)
Algorithm DFSTraversal(G)
// Đi qua đồ thị G=(V, E) theo độ sâu
for (mỗi v ∈V) Đánh dấu v chưa được thăm;
for (mỗi v ∈V)
if (v chưa được thăm)
Thăm v và đánh dấu v đã được thăm;
DFS(v);
Phân tích: thời gian thực hiện O(|E|+|V|)
Ứng dụng là lập kế hoạch cho một chuỗi các công việc; Trong khoa học máy tính, các ứng dụng tương tự phát sinh trong lập kế hoạch thực thi lệnh, xác định thứ tự biên dịch trong makefile, xác định quan hệ phụ thuộc giữa các biểu tượng trong chương trình liên kết.http://www.vnschool.net/modules.php?name…
· Tìm đường đi ngắn nhất single-source (Dijkstra)
Ý tưởng:được thiết kế dựa vào kỹ thuật tham ăn. Xác định đường đi ngắn nhất từ đỉnh nguồn a tới các đỉnh còn lại qua các bước– Mỗi bước ta xác định đường đi ngắn nhất từ a tới một đỉnh
– Lưu các đỉnh đã xác định đường đi ngắn nhất từ a tới chúng vào tập S
– Ban đầu tập S chỉ chứa một đỉnh nguồn a
Giả mã:
{
(1) for (mỗi đỉnh v Î V)
D[v] = c(s,v);
D[s] = 0;
(2) Khởi tạo hàng ưu tiên P chứa các đỉnh v ¹ s với khoá là D[v];
(3) while (P không rỗng)
{
(4) u = DeleteMin(P);
(5) for (mỗi đỉnh v kề u)
if (D[u] + c(u,v) < D[v])
{
D[v] = D[u] + c(u,v);
(6) DecreaseKey(P,v,D[v]);
}
}
}
Phân tích: (1) cần thời gian O(|V|). Ta có thể khởi tạo ra hàng ưu tiên P (lệnh(2)) với thời gian là O(|V|). Số lần lặp trong lệnh lặp (3) là |V|. Trong mỗi lần lặp, phép toán DeleteMin đòi hỏi thời gian O(log|V|); do đó, tổng thời gian thực hiện các lệnh (4) là O(|V|log|V|). Tổng số lần lặp trong các lệnh lặp (5) trong tất cả các lần lặp của lệnh lặp (3) tối đa là số cung của đồ thị |E|. Lệnh (6) cần thời gian O(log(|V|) khi ta cài đặt hàng ưu tiên P bởi cây thứ tự bộ phận. Vì vậy, thời gian thực hiện các lệnh lặp (5) trong các lần lặp của lệnh lặp (3) là O(|E|log|V|). Tổng kết lại, thời gian chạy của thuật toán Dijkstra, là O(|V|log|V| + |E|log|V|).
Ứng dụng Tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại của đồ thị
· Tìm đường đi ngắn nhất all-pairs
Ý tưởng:, thuật toán này được thiết kế dựa trên kỹ thuật quy hoạch động. Giả sử đồ thị có n đỉnh được đánh số từ 0 đến n-1, V = {0,1,..,n-1}, và độ dài cung (i,j) là c(i,j). Ta ký hiệu Sk là tập các đỉnh từ 0 đến k, Sk = {0,1, …,k}, k <= n-1. Gọi Ak(i,j) là độ dài đường đi ngắn nhất từ đỉnh i tới đỉnh j nhưng chỉ đi qua các đỉnh trong tập Sk. Khi k = n-1, thì Sk-1 = V và do đó An-1(i,j) chính là đường đi ngắn nhất từ i tới j trong đồ thị đã cho.
Giả mã:
Floyd (G)
// Thuật toán tìm đường đi ngắn nhất giữa mọi cặp
// đỉnh trên đồ thị G = (V,E), V = {0,1,…,n-1} {
(1) for ( i = 0 ; i < n ; i++)
for ( j = 0 ; j < n ; j++)
(2) A[i][j] = c[i][j];
(3) for ( k = 0 ; k < n ;
for ( i = 0 ; i < n ; i++)
for ( j = 0 ; j < n ; j++)
(4) if (A[i][k] + A[k][j] < A[i][j] )
A[i][j] = A[i][k] + A[k][j];
}
Phân tíchSố gán lần lặp của lệnh (2) trong lệnh lặp (1) là O(|V|2). Số lần lặp của lệnh (4) trong lệnh lặp (3) là n3, và do đó thời gian chạy của lệnh lặp (3) là O(|V|3). Vì vậy thuật toán Floyd đòi hỏi thời gian O(|V|3)
Ứng dụng tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị.
· Tìm cây bao trùm ngắn nhất bằng thuật toán Prim
Ý tưởng:được thiết kế theo kỹ thuật tham ăn. Ý tưởng chung của các thuật toán này là: ta xây dựng tập T các cạnh dần từng bước xuất phát từ T rỗng. Trong mỗi bước lặp, ta sẽ chọn cạnh (u,v) ngắn nhất trong các cạnh còn lại để đưa vào tập T. Có hai phương pháp chọn trong mỗi bước lặp. Trong phương pháp thứ nhất (thuật toán Prim), cạnh được chọn ở mỗi bước là cạnh ngắn nhất trong các cạnh còn lại, sao cho nó cùng với các cạnh đã chọn tạo thành đồ thị liên thông, không có chu trình (tức là tạo thành một cây
Giả mã:
Prim(G,T)
//Xây dựng cây bao trùm ngắn nhất T của đồ thị G{
U = {s}; //Khởi tạo tập U chỉ chưa một đỉnh s
T = Æ; // Khởi tạo tập cạnh T rỗng.
while ( U ¹ V ){
chọn (u,v) là cạnh ngắn nhất với u Î U và v Î V - U;
U = U È {v};
T = T È {(u,v};
}
}
Phân tích Chúng ta có nhận xét rằng Prim trên là giống hệt thuật toán Dijkstra, do đó ta có thể kết luận rằng, nếu sử dụng hàng ưu tiên trên được cài đặt bởi cây thứ tự bộ phận, thì thời gian chạy của thuật toán Prim là O(|V|log|V| + |E|log|V|). Nhưng G = (V,E) là đồ thị vô hướng liên thông, nên |E| >= |V| - 1. Do đó, thời gian chạy của thuật toán Prim là O(|E|log|V|).
Ứng dụng trong việc thiết kế mạng truyền thông. Khi đó, có thể mô hình hoá các địa điểm là các đỉnh của đồ thị, các cạnh của đồ thị biểu diễn các đường truyền nối các địa điểm. Giá đường nối với tổng giá thấp nhất của các cạnh là giá thi công các đường nối. Việc tìm các chính là tìm cây bao trùm ngắn nhất
· Tìm cây bao trùm ngắn nhất bằng thuật toán Kruskal
Ý tưởng:Thuật toán Kruskal cũng được thiết kế theo kỹ thuật tham ăn. Tập T các cạnh được xây dựng dần từng bước xuất phát từ T rỗng. Nhưng khác với thuật toán Prim, tại mỗi bước trong thuật toán Kruskal, cạnh (u,v) được chọn thêm vào T là cạnh ngắn nhất trong các cạnh còn lại và không tạo thành chu trình với các cạnh đã có trong T Giả mã:
Kruskal(G,T)
//Xây dựng cây bao trùm ngắn nhất T của đồ thị G = (V,E).{
T = Æ;
Sắp xếp các cạnh (u,v)ÎE thành một danh sách L không giảm theo độ dài;
Khởi tạo một họ tập con, mỗi tập con chứa một đỉnh vÎV;
k = 0; //Biến đếm số cạnh được đưa vào T
do {
Loại cạnh (u,v) ở đầu danh sách L (tức là cạnh ngắn nhất trong các cạnh còn lại);
i = Find(u); // i là đại biểu của tập con chứa u
j = Find(v);
if ( i ¹ j )
{
T = T È {(u,v)};
Union(u,v); //Lấy hợp của các tập con chứa u và v.
k++;
}
}
while ( k < |V| - 1);
}
Phân tích: Thời gian sắp xếp các cạnh (lệnh (1)) là O(|E|log|E|). Thời gian thực hiện lệnh (2) là O(|V|). (3) tối đa các lần lặp là O(|E|). Trong mỗi lần lặp ta cần thực hiện các phép tìm (4), (5) và phép hợp (6). thời gian thực hiện lệnh lặp (3) là O(|E|log*|V|). Do đó thời gian chạy của thuật toán Kruskal là O(|E|log|V| + |E|log*|V|) = O(|E|log|V|).
· Ứng dụng tương tự phần trên
1 Phân tích thuật toán
• Định nghĩa và phân biệt thời gian chạy tốt nhất, trung bình, xấu nhất của thuật toán. Vận dụng: cho một thuật toán (ví dụ thuật toán tìm kiếm nhị phân), xác định trường hợp chạy tốt nhất, xấu nhất.
Tốt nhất
Trung bình
Xấu nhất
Là thời gian chạy nhỏ nhất của thật toán trên tất cả các dữ liệu vào cùng cỡ .
Là số trung bình cộng của thời gian chạy của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ.
Ký hiệu Ttb(n).
là thời gian chạy lớn nhất của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ .
Ký hiệu là T(n).
• Ký hiệu ô lớn: định nghĩa và sử dụng. Các cấp độ thời gian chạy. Vận dụng: xác định độ phức tạp thời gian của một thuật toán sử dụng ký hiệu ô lớn.
Định nghĩa. Giả sử f(n) và g(n) là các hàm thực không âm của đối số nguyên không âm n. Ta nói “f(n) là ô lớn của g(n)” và viết là f(n) = O( g(n) ) nếu tồn tại các hằng số dương c và n0 sao cho f(n) <= cg(n) với mọi n >= n0.
Như vậy, f(n) = O(g(n)) có nghĩa là hàm f(n) bị chặn trên bởi hàm g(n) với một nhân tử hằng nào đó khi n đủ lớn. Tổng quát nếu f(n) là một đa thức bậc k của n: f(n) = aknk + ak-1nk-1 + ... + a1n + a0 thì f(n) = O(nk)
Biểu diễn thời gian chạy của thuật toán
Thời gian chạy của thuật toán là một hàm của cỡ dữ liệu vào: hàm T(n). Chúng ta sẽ biểu diễn thời gian chạy của thuật toán bởi ký hiệu ô lớn: T(n) = O(f(n)), biểu diễn này có nghĩa là thời gian chạy T(n) bị chặn trên bởi hàm f(n). Thế nhưng như ta đã nhận xét, một hàm có vô số cận trên. Trong số các cận trên của thời gian chạy, chúng ta sẽ lấy cận trên chặt (tight bound) để biểu diễn thời gian chạy của thuật toán.
Định nghĩa. Ta nói f(n) là cận trên chặt của T(n) nếu
· T(n) = O(f(n)), và Nếu T(n) = O(g(n)) thì f(n) = O(g(n)).
· Sau này khi nói thời gian chạy của thuật toán là O(f(n)), chúng ta cần hiểu f(n) là cận trên chặt của thời gian chạy.
Các cấp độ thời gian chạy của thuật toán và tên gọi của chúng được liệt kê trong bảng sau:
Ký hiệu ô lớn
Tên gọi
O(1)
O(logn)
O(n)
O(nlogn)
O(n2)
O(n3)
O(2n)
hằng
logarit
tuyến tính
nlogn
bình phương
lập phương
mũ
• Cho ví dụ minh họa vấn đề đánh đổi thời gian và không gian của thuật toán.
Ma trận kề
Danh sách kề
- - truy cập tới thành phần A[i][j] của mảng ta biết ngay được có cung (i,j) hay không và độ dài của cung đó (nếu là đồ thị có trọng số).
- - Tốn dung lượng bộ nhớ
- muốn biết có cung (i,j) hay không và độ dài của nó bằng bao nhiêu, ta lại phải tiêu tốn thời gian để duyệt danh sách các đỉnh kề của đỉnh i.
- Tốn ít dung lượng bộ nhớ
• Phân tích độ phức tạp thời gian của một thuật toán đệ quy.
Các hàm đệ quy là các hàm có chứa lời gọi hàm đến chính nó. Trong mục này, chúng ta sẽ trình bầy phương pháp chung để phân tích các hàm đệ quy, sau đó sẽ đưa ra một số kỹ thuật phân tích một số lớp hàm đệ quy hay gặp.
Giả sử ta có hàm đệ quy F, thời gian chạy của hàm này là T(n), với n là cỡ dữ liệu vào. Khi đó thời gian chạy của các lời gọi hàm ở trong hàm F sẽ là T(m) với m < n. Trước hết ta cần đánh giá thời gian chạy của hàm F trên dữ liệu cỡ nhỏ nhất n = 1, giả sử T(1) = a với a là một hằng số nào đó. Sau đó bằng cách đánh giá thời gian chạy của các câu lệnh trong thân của hàm F, chúng ta sẽ tìm ra quan hệ đệ quy biểu diễn thời gian chạy của hàm F thông qua lời gọi hàm, tức là biểu diễn T(n) thông qua các T(m), với m < n. Chẳng hạn, giả sử hàm đệ quy F chứa hai lời gọi hàm với thời gian chạy tương ứng là T(m1) và T(m2), trong đó m1, m2 <n, khi đó ta thu được quan hệ đệ quy có dạng như sau:
T(1) = 1
T(n) = f(T(m1),T(m2))
Trong đó, f là một biểu thức nào đó của T(m1) và T(m2). Giải quan hệ đệ quy trên, chúng ta sẽ đánh giá được thời gian chạy T(n). Nhưng cần lưu ý rằng, giải các quan hệ đệ quy là rất khó khăn, chúng ta sẽ đưa ra kỹ thuật giải cho một số trường hợp đặc biệt.
2 Trừu tượng hoá dữ liệu
• Đặc tả một KDLTT : Trong giai đoạn đặc tả, chúng ta cần mô tả chính xác các dữ liệu vào (inputs) và các dữ liệu ra (outputs) của chương trình. Gồm hai phần: đặc tả đối tượng dữ liệu và đặc tả các phép toán.
· Đặc tả đối tượng dữ liệu. Mô tả bằng toán học các đối tượng dữ liệu. Thông thường các đối tượng dữ liệu là các đối tượng trong thế giới hiện thực, chúng là các thực thể phức hợp, có cấu trúc nào đó. Để mô tả chúng, chúng ta cần sử dụng sự trừu tượng hoá (chỉ quan tâm tới các đặc tính quan trọng, bỏ qua các chi tiết thứ yếu). Nói cụ thể hơn, để mô tả chính xác các đối tượng dữ liệu , chúng ta cần sử dụng các khái niệm toán học, các mô hình toán học như tập hợp, dãy, đồ thị, cây, … Chẳng hạn, đối tượng dữ liệu là sinh viên, thì có thể biểu diễn nó bởi một tập các thuộc tính quan trọng như tên, ngày sinh, giới tính, …
Đặc tả các phép toán. Việc mô tả các phép toán phải đủ chặt chẽ, chính xác nhằm xác định đầy đủ kết quả mà các phép toán mang lại, nhưng không cần phải mô tả các phép toán được thực hiện như thế nào để cho kết quả như thế. Cách tiếp cận chính xác để đạt được mục tiêu trên là khi mô tả các phép toán, chúng ta xác định một tập các tiên đề mô tả đầy đủ các tính chất của các phép toán. Chẳng hạn, các phép toán cộng và nhân các số nguyên phải thoả mãn các tiên đề: giao hoán, kết hợp, phân phối, … Tuy nhiên, việc xác định một tập đầy đủ các tiên đề mô tả đầy đủ bản chất của các phép toán là cực kỳ khó khăn, do đó chúng ta mô tả các phép toán một cách không hình thức. Chúng ta sẽ mô tả mỗi phép toán bởi một hàm (hoặc thủ tục), tên hàm là tên của phép toán, theo sau là danh sách các biến. Sau đó chỉ rõ nhiệm vụ mà hàm cần phải thực hiện
3 Danh sách
• Mô tả và cho ví dụ về KDLTT danh sách
Đặc tả dữ liệu
A = (a0, a1, …, an)
trong đó ai
là phần tử thứ i của danh sách A
Ví dụ: A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tuấn’, ‘Ánh’)
Đặc tả các phép toán
1. Kiểm tra danh sách có rỗng hay không: empty(A)
2. Đếm số phần tử của danh sách: length(A)
3. Trả về phần tử ở vị trí thứ i của danh sách: element(A,
4. Thêm phần tử x vào vị trí i trong danh sách: insert(A, i,
5. Thêm phần tử x vào đuôi danh sách: append(A, x)
6. Loại phần tử ở vị trí thứ i trong danh sách: del (A, i)
• Giải thích khái niệm bộ công cụ lặp : Làcác phép toán được sử dụng thường và các phép toán sẽ được sử dụng để cài đặt nhiều KDLTT khác như tập động, từ điển, ngăn xếp, hàng đợi, hàng ưu tiên. Để cho quá trình xử lý chương trình được thực hiện thuận tiện, hiệu quả, chúng ta xác định các phép toán đó vàcác phép toán này tạo thành bộ công cụ lặp (iteration).
• So sánh các CTDL cài đặt KDLTT danh sách
Mảng
Mảng động
– Một phần tử cụ thể trong mảng sẽ được xác định và truy cập bởi một chỉ số
– Các phần tử được sắp xếp gần nhau theo thứ tự ; có 1 hoặc nhiều chiều
– Mảng này do trình biên dịch chỉ giới hạn kích thước mảng.
Hàm cơ bản: kiến tạo, thêm, xóa..
cho phép truy cập trực tiếp tới từng phần tử của danh sách.-> có thể cài đặt rất thuận tiện phép toán tìm kiếm trên danh sách nhưng khi mảng đầy ko thể thêm được
– Một phần tử cụ thể trong mảng sẽ được xác định và truy cập bởi một chỉ số
Các phần tử sắp xếp gần nhau theo thứ tự ; có 1 hoặc nhiều chiều
Do người lập trình cấp phát và nó có : Hàm kiến tạo sao chép ;Toán tử gán ; Hàm hủy
Ngoài hàm của mảng Tĩnh cần 2 hàm kiến tạo(biên kích thước mảng,copy), hàm hủy.
4 Danh sách liên kết
• Dùng CTDL danh sách liên kết đơn để cài đặt các KDLTT danh sách, danh sách được sắp, tập động DSLK được tạo thành từ các nút– mỗi nút gồm 2 phần: phần dữ liệu: chứa phần tử dữ liệu, phần con trỏ: chứa 1 địa chỉ
– các nút liên kết với nhau thông qua con trỏ
· Xen một thành phần mới vào DSLK.
· Loại một thành phần khỏi DSLK.
Một phần tử mới
Đầu danh sách
Sau phần P
Trước phần P
Xen 1 thành phần
Node* Q;
Q = new Node ; Q à data = value;
Q à next = Head;
Head = Q;
Qànext =Pà next;
P à next = Q;
Qànext = P; (hoặc Qànext = Preà next)
Pre à next = Q;
Loại 1 thành phần
Pre à next = P à next;
delete P;(ko phải đầu)
Head=Headànext;
delete P;
· Đi qua DSLK (duyệt DSLK).
Node* cur ;
for (cur = Head; cur ! = NULL; cur = cur à next)
{ các xử lý với dữ liệu trong thành phần được trỏ bởi cur}
Ví dụ. Để in ra tất cả các dữ liệu trong DSLK, bạn có thể viết
for (cur = Head; cur ! = NULL; cur = cur à next)
cout << cur à data << endl;
Phép toán
Danh sách cài
đặt bởi mảng
Danh sách cài
đăt bởi DSLK
Insert (x, i)
Delete (i)
Append (x)
Element (i)
Add (x)
Remove ( )
Current ( )
O(n – i)
O(n – i)
O(1)
O(1)
O(n)
O(n)
O(1)
O(i)
O(i)
O(1)
O(i)
O(1)
O(1)
O(1)
èCài đặt danh sách bằng DSLK sẽ giúp tiết kiệm bộ nhớ nhất. Với mảng tĩnh thì O(1) còn DSLK là O(i)
• Giải quyết vấn đề trên bằng DSLK kép
Trong DSLK đơn, giả sử bạn cần loại một thành phần được định vị bởi con trỏ P, bạn cần phải biết thành phần đứng trước, nếu không biết bạn không có cách nào khác là phải đi từ đầu DSLK. Một hoàn cảnh khác, các xử lý với dữ liệu trong một thành phần lại liên quan tới các dữ liệu trong thành phần đi sau và cả thành phần đi trước. Trong các hoàn cảnh như thế, để thuận lợi người ta thêm vào mỗi thành phần của DSLK một con trỏ mới: con trỏ trước precede, nó trỏ tới thành phần đứng trước. Và khi đó ta có một DSLK kép, như trong hình 5.8a. Mỗi thành phần của DSLK kép chứa một dữ liệu và hai con trỏ: con trỏ next trỏ tới thành phần đi sau, con trỏ precede trỏ tới thành phần đi trước. Giá trị của con trỏ precede ở thành phần đầu tiên và giá trị của con trỏ next ở thành phần sau cùng là hằng NULL.
5 Ngăn xếp
• Mô tả và cho ví dụ về KDLTT ngăn xếp
• So sánh các CTDL cài đặt KDLTT ngăn xếp
• Ứng dụng trong các thuật toán trên biểu thức số học
6 Hàng đợi
• Mô tả và cho ví dụ về KDLTT hàng đợi
• So sánh các CTDL cài đặt KDLTT hàng đợi
7 Cây
• Ba phương pháp duyệt cây: preorder, inorder, postorder
• CTDL cây tìm kiếm nhị phân: đặc tả, ví dụ, cài đặt, ứng dụng
• KDLTT cây thứ tự bộ phận (heap): đặc tả, ví dụ, cài đặt, ứng dụng
8 Bảng băm
• KDLTT từ điển: đặc tả, ví dụ
• Liên hệ giữa KDLTT và bảng băm
• 2 chiến lược giải quyết va chạm: thăm dò và tạo dây chuyền. Cho ví dụ.
9 Hàng ưu tiên
• Mô tả và cho ví dụ về KDLTT hàng ưu tiên
• So sánh các CTDL cài đặt KDLTT hàng ưu tiên
• Thuật toán dựng mã Huffman
10 Thiết kế thuật toán
• Nắm được cách tiếp cận của từng chiến lược: chia để trị, quy hoạch động, tham ăn, quay lui.
Cho ví dụ bài toán có thể giải hiệu quả bằng mỗi chiến lược.
• Các bài tập về 4 chiến lược này trong Chương 16 giáo trình.
11 Sắp xếp
• 6 thuật toán sắp xếp của Chương 17 giáo trình:
o ý tưởng
o cài đặt
o trường hợp xấu nhất, tốt nhất
o phân tích độ phức tạp
• Sắp xếp cơ số: ý tưởng, ví dụ
Bạn đang đọc truyện trên: AzTruyen.Top