Cau truc du lieu va giai thuat

CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
Giảng viên : Hồ Sĩ Đàm
Email [email protected]
Mob. 0913580373
Giới thiệu
Thời lượng: 4 buổi
Mục tiêu:
- Giới thiệu đề cương phần cấu trúc dữ liệu và thuật toán ( môn Tin học cơ sở);
- Giải đáp thắc mắc của thi sinh.

Tài liệu tham khảo

Thomas H. Cormen, Introduction to Algorithms, MIT Press, 1990

R. Sedgevick,Algorithms Addison- Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán ( tập 1, 2).
Hồ Sĩ Đàm, Nguyễn Việt, Hà Bùi Thế Duy
Đinh Mạnh Tường, Đỗ Xuân Lôi
Nội dung
Chương I : Thuật toán và phân tích thuật toán
Chương II : Đệ quy
Chương III : Các dữ liệu có cấu trúc
Chương IV : Danh sách
Chương V : Cây
Chương VI : Bảng băm
Chương VII : Sắp xếp
Chương VIII : Tìm kiếm
Chương IX : Đồ thị
Chương X : Các kỹ thuật thiết kế thuậ toán
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN

Giải bài toán trên máy tính
Mô hình dữ liệu
Cấu trúc dữ liệu
Bài toán và thuật toán
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
Bước 1. Xác định bài toán:
Xác định tập Input và Output
Bước 2. Lựa chọn hoặc thiết kế thuật toán
a) Lựa chọn hoặc thiết kế thuật toán
Giải bài toán  nhiều thuật toán
Không gian ?
Thời gian ?;
Cài đặt ?
b) Mô tả thuật toán
 Input: Hai số nguyên dương a và b;
 Output: q và r : a= bq+r.
 Ý tưởng:
- Nếu a < b thì q = 0 và r = a. Kết thúc.
- Nếu a > b thì a giảm đi b và q tăng lên 1. Lặp cho đến khi a < b.
CHƯƠNG I:
TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
*) Cách liệt kê
B1: Nhập a và b;
B2: q  0;
B3: Nếu a < b thì r  a rồi chuyển đến B5;
B4: a  a - b, q  q + 1 rồi quay về B3;
B5: Đưa ra r và q. Kết thúc.

*) Sơ đồ khối
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
Bước 3. Viết chương trình:
Chọn CTDL;
Ngôn ngữ lập trình

Bước 4. Hiệu chỉnh:
Xây dựng các bộ input (test) tiêu biểu;
Chạy thử.
Uses Crt;
Var a, b, q, r: integer;
Begin
Clrscr;
Writeln (‘Chuong trinh chia Euclid’);
Write (‘Nhap so a: ’);
Readln (a);
Write (‘Nhap so b: ’);
Readln (b);
q:=0;
While a >= b Do
Begin
Dec(a,b);
Inc(q);
End;
r:= a;
Writeln (‘Thuong q = ’, q);
Writeln (‘Phan du r = ’, r);
Readln;
End.
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
Bước 5. Viết tài liệu:
Hướng dẫn sử dụng;
Thuật toán, Cấu trúc dữ liệu;
…….

CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
2. Mô hình dữ liệu (Data model)
Là các trừu tượng :đồ thị, tập hợp, danh sách, cây...
Hai khía cạnh:
Giá trị (kiểu dữ liệu)
Các phép toán ( operation)
Chương trình có thể truy xuất đến các vùng lưu trữ.
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
3. Cấu trúc dữ liệu (Data structures)
Là các đơn vị cấu trúc (construct) của NNLT dùng để biểu diễn các mô hình dữ liệu
Ví dụ: mảng, bản gi, file,xâu,..
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
4.1. Bài toán
Xác định rõ Input và Output
Ví dụ:
Kiểm tra xem N có phải là số nguyên tố hay không?
- Input : Số nguyên dương N
- Output : Trả lời N là số nguyên tố hay không?
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
4.2. Thuật toán
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đươc sắp xếp theo một trật tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.
Ví dụ: Tìm giá trị lớn nhất của dãy số a1, a2,..…,aN,
Input : Số nguyên dương N và dãy a1, a2, ,..., aN.
Output : Tìm Max là giá trị lớn nhất của dãy đã cho.
Ý tưởng:
Khởi tạo Max=a1. Với mỗi i, nếu ai > Max thì thay giá trị Max= ai.

CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
4.3. Mô tả thuật toán
a) Cách liệt kê
B1. Nhập N và dãy a1, ..., aN
B2. Đặt Max = a1, i = 2.
B3. Nếu i > N thì đến b. 5.
B4.
4.1. N ếu ai > Max thì Max = ai.
4.2. Đặt i=i+1 rồi quay b.3.
B5. Đưa ra Max rồi kết thúc.
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
b) Sơ đồ khối
Dùng: Ovan, Chữ nhật, Hình thoi,Mũi tên,…
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
c) Ngôn ngữ điều khiển
Dùng các ký hiệu và quy tắc
Cách thiết lập thứ tự các thao tác
cấu trúc điều khiển.



CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
4.4. Các đặc trưng chính
a)Tính kết thúc (tính đóng)
b)Tính xác định (đơn nghĩa)
Có đúng một thao tác để được thực hiện hoặc dừng.
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
c)Tính chi tiết
Phụ thuộc vào đối tượng thực hiện
d)Tính phổ dụng
với input thay đổi
e) Đại lượng vào
f) Đại lượng ra
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán

g) Tính hiệu quả
Thời gian: Tốc độ xử lý
Không gian: Dung lượng cần để lưu trữ
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
4.5. Độ phức tạp thuật toán
Lựa chọn thuật toán
Dễ hiểu, dễ cài đặt và dễ ghi chép ?
Sử dụng các tài nguyên hiệu quả?
Tùy đặc tính của bài toán
Phân tích theo kinh nghiệm
Thực hiện và kết luận  dễ mắc lỗi
Kích thước dữ liệu đầu vào là quan trọng: T(n)

CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán

b) Ký pháp
Giả sử T(n) là thời gian thực hiện TT và f(n), g(n), h(n) là các hàm xác định dương
Hàm O lớn: O(g(n)) nếu  c và n0 sao cho T(n) <= c.g(n) với mọi n>= n0
g(n) là giới hạn trên của T(n).


Ví dụ, nếu T(n) = n2 + 1 thì T(n) = O(n2).
Chọn c=2 và n0 =1, khi đó với mọi n>=1, ta có T(n)= n2+1 <= 2n2 =2g(n).
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán

c) Các tính chất
(i) Tính bắc cầu: nếu f(n)= O(g(n)) và g(n)= O(h(n)) thì f(n)= O(h(n))
(ii) Tính phản xạ: f(n)=O(f(n))
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán

d) Xác định độ phức tạp
Quy tắc hằng số
Nếu P có T(n)= O(c1f(n)) P có độ phức tạp O(f(n)).

CM: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0 >0 để T(n) <= c0.c1 f(n) với mọi n>= n0.
Đặt c=c0.c1 ta có điều cần CM

CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Quy tắc lấy Max
Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O( max ( f(n), g(n))).

CM: T(n) = O( f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) <= cf(n) + cg(n), với mọi n>= n0 vậy T(n) <= cf(n) +cg(n) <= 2c max (f(n),g(n)) với mọi n>=n0.
Từ đó suy điều cần CM.
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Quy tắc cộng
Nếu P1 có T1 (n) = O( f(n) và P2 có T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)).

CM: Vì T1(n)= O(f(n)) nên  các hàng số c1 và n1 sao cho T(n) <= c1.f(n) n: n>= n1.
Vì T2(n) =O(g(n)) nên  các hàng số c2 và n2 sao cho T(n) <= c1.g(n) n: n>= n2
Chọn c= max (c1,c2) và n0 = max(n1,n2) ta có n: n n>= n0:
T(n) = T1(n) + T2(n) <= c1f(n) + c2g(n)
<= cf(n) +cg(n) = c(f(n)+g(n)).
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Quy tắc nhân
Nếu P có T(n)= O(f(n)). Khi đó nếu thực hiện k(n) lần P với k(n)=O(g(n)) thì độ phức tạp la O(f(n) g(n)).

CM: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n) T(n), theo định nghĩa:
ck>=0 và nk >0 để k(n) <= ck(g(n)) với mọi n>= nk
cT>=0 và nT >0 để T(n) <= cTf(n) với mọi n>= nT
Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) <= ckcT(f(n)g(n)).
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
e) Áp dụng đánh giá chương trình
Câu lệnh đơn thực hiện một thao tác
QT hằng số
Câu lệnh hợp thành là dãy các câu lệnh
QT tổng
Câu lệnh rẽ nhánh dạng If ..then..else.
QT Max
Các câu lệnh lặp QT Nhân

CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Ví dụ 1
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Ví dụ 2
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Ví dụ 3
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
Một số dạng hàm
Đa thức bậc k: P(n), O (nk).
logaf(n), O(log f(n)).
Hằng số, O(1)
Hàm mũ O(2n.)
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán

g) Độ phức tạp tính toán và dữ liệu vào
Trường hợp tốt nhất: T(n) là thời gian ít nhất
Trường hợp xấu nhất: T(n) là thời gian lớn nhất Trường hợp trung bình: dữ liệu vào tuân theo một phân bố xác suất nào đó
CHƯƠNG I:
THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
4. Bài toán và thuật toán
h) Phép toán tích cực
Các phép toán thực hiện nhiều nhất
Quy tắc ‘10-90’
CHƯƠNG II
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
Phép lặp, quy nạp và đệ quy
Thuật toán đệ quy
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
1. Phép lặp, quy nạp và đệ quy
Lặp (interation): biến thể của cùng một thao tác.
Quy nạp(induction): kĩ thuật chứng minh các mệnh đề thuộc dạng với mọi n thì P(n) là đúng.
Ví dụ: với mọi n, tổng n số lẻ đầu tiên bằng n2.
Bước cơ sở: Chỉ ra P(1) là đúng , vì 12=1.
Bước quy nạp: Chứng minh nếu P(n) là đúng thì kéo theo P(n+1) cũng đúng

CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
1. Phép lặp, quy nạp và đệ quy
Tổng n số lẻ là n2, cần cm tổng (n+1) số lẻ là (n+1)2.
Tổng n số lẻ: 1+3+5+….+ (2n-1)= n2.
Khi đó: [1+3+5+….+ (2n-1)] +(2n+1) = n2+2n+1= (n+1)2.
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
1. Phép lặp, quy nạp và đệ quy
Đệ quy (recursion): là một kĩ thuật định nghĩa một khái niệm trực tiếp hoặc gián tiếp theo chính nó.
CHƯƠNG II : ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
a) Định nghĩa
Nếu lời giải P được thực hiện bằng lời giải P’ có dạng như P thì ta nói đó là lời giải đệ quy  thuật toán đệ quy
Chú ý:
P’ giống P
P’ “nhỏ hơn” P theo nghĩa nào đó
HƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
Định nghĩa một hàm hay thủ tục đệ quy gồm hai phần:
(i)   Phần neo (anchor)
(ii)  Phần đệ quy

Như vậy:
- Phần đệ quy thể hiện tính “quy nạp”
- Phần neo đảm bảo cho tính dừng.
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
b) Ví dụ
Tính giai thừa: N!= N(N-1)!
Int fact ( int n) {
If ( n <= 1 )
Return 1; /* cơ sở*/
Else
Return n*fact (n-1); /* quy nạp*/
}
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
b) Ví dụ:
Dãy số Fibonacci: F(n)= F(n-1)+F(n-2) ( phần đệ quy)
với n<=2 thì F(n)=1 ( phần neo).
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
Bài toán tháp Hà nội. Ngôi đền Benares có n đĩa bằng vàng:
- Có bán kính khác nhau
- Chồng lên nhau ở một chiếc cọc
- Theo thứ tự đĩa lớn ở dưới, đĩa nhỏ ở trên. Các nhà sư lần lượt chuyển các đĩa sang một cọc khác theo quy tắc sau:
CHƯƠNG II : ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
Khi chuyển một đĩa phải đặt vào một trong 03 cọc
Mỗi lần chỉ chuyển đúng một đĩa trên cùng tại một cọc và đặt vào trên cùng ở cọc chuyển đến.
Đĩa lớn hơn không được phép đặt lên đĩa nhỏ hơn.
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
Ví dụ, với trường hợp n=2 ta có thể chuyển như sau:
Chuyển đĩa nhỏ sang cọc 3
Chuyển đĩa lớn sang cọc 2
Chuyển đĩa từ cọc 3 sang cọc 2
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
Nếu n=1 thì chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2. Kết thúc.
Giả thiết ta có cách chuyển (n-1) đĩa từ cọc 1 sang cọc 2:
Cách chuyển (n-1) đĩa từ cọc 2 sang cọc 3 cũng làm tương tự.
Chuyển đĩa lớn nhất đang ở cọc 1 sang cọc 2
Chuyển (n-1) đĩa từ cọc 3 sang cọc 2.
Kết thúc.
CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
c) Đánh giá về đệ quy
Ưu điểm:
Mạnh, rõ ràng, chặt chẽ
Thiết kế TT đơn giản
Nhược điểm:
Lời gọi hàm tốn rất nhiều thời gian.
Dễ phát sinh chạy vô hạn.

CHƯƠNG II :
ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY
2. Thuật toán đệ quy
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
Các kiểu dữ liệu chuẩn
Kiểu mảng (array) và biến chỉ số
Kiểu xâu (string)
Kiểu cấu trúc (struct)
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
1. Các kiểu dữ liệu chuẩn
Kiểu dữ liệu chuẩn: nguyên, thực, lôgic, xâu.
Ví dụ,
Khai báo biến int x, float y,….
Với kiểu nguyên có các phép toán: cộng, trừ, nhân, chia x div y ( chia nguyên ), x mod y ( lấy phần dư của phép chia).
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
2. Kiểu mảng (array) và biến chỉ số
2.1. Kiểu mảng một chiều
Là dãy liên tiếp các phần tử cùng kiểu dữ liệu.
Đặt tên và mỗi phần tử của nó có một chỉ số.
Tham chiếu: tên mảng và chỉ số tương ứng [ ] ).
Số lượng các phần tử của mảng là cho trước.
Ví dụ
int a[10] , float b[20]
CHƯƠNG III :
CÁC DỮ LIỆU CÓ CẤU TRÚC
2. Kiểu mảng (array) và biến chỉ số
2.2. Kiểu mảng hai chiều
Bảng nxm các phần tử cùng kiểu dữ liệu.
Tham chiếu: tên mảng và hai chỉ số, [ ].
Ví dụ: int a[10][15] ,float b[20][10]
CHƯƠNG III :
CÁC DỮ LIỆU CÓ CẤU TRÚC
2. Kiểu mảng (array) và biến chỉ số
2.3. Chú ý
Địa chỉ các phần tử mảng là liên tiếp nhau.
Mảng hai chiều được sắp xếp theo hàng.
Dung lượng bộ nhớ là cố định
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
2. Kiểu mảng (array) và biến chỉ số
Chỉ số không được vượt quá kích thước chiều
Ví dụ: a[5] * b[8][3]
Cấu trúc đơn giản, truy nhập nhanh, kích thước cố định.
Thiếu mềm dẻo trong các phép toán như xóa, chèn.
Có thể dùng phép gán cho cả mảng.
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
3. Kiểu xâu (chuỗi – string)
Kiểu mảng đặc biệt mà kiểu phần tử của mảng này là ký tự. Thông thường xâu được đặt trong cặp dấu ‘ và ’,
Ví dụ: S=‘Tin hoc’
Các ký tự trong xâu được viết liên tiếp và có thể xuất hiện nhiều lần
Số lượng các ký tự là độ dài của xâu, có xâu rỗng
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
3. Kiểu xâu (chuỗi – string)
Phép toán trên xâu:
Phép ghép xâu: Char*strcat(char* s1, char s2)
Phép Copy (S,M,N): giá trị là xâu con của sâu S gồm các ký tự từ vị trí M đến N
Phép xoá Delete (S,M,N): Giá trị là xâu con của xâu S sau khi đã xóa liên tiếp N kí tự của S bắt đầu từ kí tự thứ M
Phép chèn Insert (S1, S2, N): Chèn xâu S1 vào trước ký tự N của sâu S2
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
4. Kiểu cấu trúc (struct)
Tập các đối tượng có cùng một số thuộc tính có thể có các kiểu dữ liệu khác nhau.
Mỗi đối tượng- một cấu trúc.
Mỗi thuộc tính- một thành phần.
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
4. Kiểu cấu trúc (struct)
Khai báo kiểu cấu trúc:
STRUCT tên_kiểu_cấu trúc {
Khai báo các thành phần
};
CHƯƠNG III : CÁC DỮ LIỆU CÓ CẤU TRÚC
4. Kiểu cấu trúc (struct)
Truy nhập:
Xác định: viết tên cấu trúc, dấu chấm (.) và sau cùng là tên thành phần.
Thành phần có thể là một cấu trúc.
CHƯƠNG IV: DANH SÁCH (LIST)


Khái niệm danh sách
Biểu diễn danh sách trong máy tính.
Một số nhận xét.
Kiểu dữ liệu con trỏ (pointer) và việc cấp phát/thu hồi bộ nhớ động.
CHƯƠNG IV: DANH SÁCH (LIST)
1. Khái niệm danh sách
a) Định nghĩa
DS là một tập sắp thứ tự các phần tử cùng kiểu.
Các phần tử có thứ tự “trước- sau”
DS con: các phần tử liên tiếp từ ai đến aj:
Nếu i=1 gọi là phần đầu (prefix)
Nếu j=n gọi là phần cuối (postfix).
CHƯƠNG IV: DANH SÁCH (LIST)
1. Khái niệm danh sách
Dãy con là một danh sách tạo thành bằng cách loại từ danh sách một số phần tử. Ví dụ, DS = (a,b,c,d,e,f). Khi đó:
(c,d,e) là DS con của DS
(a, b) là một phần đầu của DS
(c,d,e,f) là một phần cuối của DS
(a,c,f) là một dãy con của DS
CHƯƠNG IV: DANH SÁCH (LIST)
1. Khái niệm danh sách
b) Các phép toán
Phép khởi tạo tạo ra một danh sách rỗng.
Xác định độ dài
Xóa
Chèn
Tìm kiếm
Kiểm tra tính trạng thái rỗng
Kiểm tra trạng thái tràn
Duyệt danh sách.
Sắp xếp
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.1. Cài đặt bằng mảng một chiều
Ví dụ, DS = ( A, B, C, D, E, F, G, H, I, J, K)
Mảng M gồm 11 phần tử:

P
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.1. Cài đặt bằng mảng một chiều
Chèn
- Dồn tất cả các phần tử từ vị trí P đến cuối sang phải một vị trí:
- Đặt V vào vị trí P
P
- Tăng n lên 1
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
b) Xóa
- Mảng ban đầu
P
- Chuyển tất cả các phần tử từ vị trí P+1 đến cuối sang trái 1 vị trí
Giảm n đi 1.
Nếu không cần bảo lưu thứ tự các phần tử sau khi xóa thì chỉ cần tráo đổi giá trị phần tử cần xóa cho phần tử cuối cùng và giảm n đi 1.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
c) Nhận xét
Truy cấp trực tiếp
Chèn và xóa đều phải dịch chuyển
Kích thước trong mọi NNLT đều cố định
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.2. DS nối đơn
DS các phần tử được nối với nhau theo một chiều.
Mỗi phần tử là một Struct (bản ghi)
Có một trường con trỏ chứa thông tin liên kết
Các trường chứa thông tin
Đầu (Head) và cuối (Tail)
Trường NEXT của phần tử cuối chứa giá trị đặc biệt (Nill, Null)
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
a) Chèn
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
b) Xóa
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
C) Xác định
Tìm kiếm bắt đầu từ Head,
Theo con trỏ đến khi xác định được vị trí cần thiết
 duyệt tuần tự.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.3. DS nối kép
DS gồm các phần tử được nối với nhau theo hai chiều.
Mỗi phần tử là một STRUCT có hai trường liên kết (LINK) liên kết tới 2 phần tử trước và sau nó và trường DATA (INFO) lưu trữ thông tin.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Có hai cách duyệt:
Bắt đầu từ nút First, dựa vào NEXT để đi đến khi duyệt qua nút Last;
Hoặc bắt đầu từ nút Last dựa vào Prev để đi đến khi duyệt qua nút First.

CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
- Chèn/xóa bằng cách chỉnh lại các liên kết của các nút liên quan.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.4. DS nối vòng một hướng
Phần tử cuối trỏ về phần tử đầu tiên
Chỉ cần xác định được một phần tử nào đó
Chèn/xóa bằng cách chỉnh lại các liên kết của các nút liên quan.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.5. DS nối vòng hai hướng
Tạo từ DS nối kép, PREV của nút First trỏ tới nút Last, NEXT của nút Last trỏ tới First.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.6. Ngăn xếp và hàng đợi
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
2.6. Ngăn xếp và hàng đợi
a) Ngăn xếp (Stack)
Một kiểu DS
Bổ sung thêm và lấy ra một phần tử cũng ở cuối DS.
Hoạt động theo nguyên tắc “vào sau-ra trước” (LIFO)
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính


Mô tả Stack bằng mảng
(i) Thêm (Push) vào Stack = thêm vào cuối mảng
(ii) Lấy ra (Pop) khỏi Stack = loại bỏ cuối mảng.
(iii) Overstack khi mảng đã đầy
(iv) EmptyStack khi trong mảng không có phần tử thực sự nào cả.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Mô tả Stack bằng DS nối đơn
Stack chỉ tràn khi vùng không gian nhớ dùng cho các biến động không còn đủ
Không gian bộ nhớ dùng cho các biến động là rất lớn nên bỏ qua việc kiểm tra tràn Stack.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Minh họa
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
b) Hàng đợi (Queue)
Một kiểu danh sách
Thêm một phần tử vào cuối danh sách (Rear) và Lấy ra một phần tử ở đầu danh sách.
Hoạt động theo nguyên tắc vào trước-ra trước (FIFO - First In First Out).
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Cài đặt Queue bằng mảng
Sử dụng hai chỉ số Front để lưu chỉ số đầu và Rear để lưu chỉ số cuối. Khởi tạo đặt Front là 1 còn Rear là 0.

(i) Thêm ( Push) vào Queue: tăng Rear lên 1 và đưa giá trị của phần tử cần bổ sung vào phần tử có chỉ số là Rear.

CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
ii) Lấy ra (Pop) :lấy giá trị phần tử có chỉ số là Front và sau đó tăng Front lên 1.
(iii) Khi tăng chỉ số Rear lên hết khoảng cho phép thìOverQueue
(iv) Khi Front > Rear thì EmptyQueue

CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Queue vòng tròn
Các phần tử xếp quanh vòng tròn theo một hướng.
Các phần tử nằm trên cung tròn từ vị trí Front đến Rear là thuộc Queue.
CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính


Khi thêm :dịch chuyển chỉ số Rear theo vòng tròn 1 ví trí rồi đặt giá trị cần thêm vào đó.
- Khi lấy ra : lấy phần tử có chỉ số là Front rồi dịch chuyển chỉ số Front theo vòng tròn 1 vị trí.

CHƯƠNG IV: DANH SÁCH (LIST)
2. Biểu diễn danh sách trong máy tính
Để cài đặt :
(i) Một phương tiện để chia bộ nhớ thành các nút, mỗi nút có phần lưu trữ data, phần lưu trữ các liên kết (con trỏ) và cách cài đặt cho con trỏ
(ii) Cài đặt các thao tác để truy nhập giá trị (cả data và pointer).
(iii) Một phương tiện nào đó để “đánh dấu” vùng bộ nhớ
CHƯƠNG IV: DANH SÁCH (LIST)
3. Một số nhận xét
Cài đặt danh sách bằng mảng tạo ra hạn chế:
Độ dài của danh sách.
Kiểm tra “tràn” và “rỗng” khi thực hiện chèn và xóa.
Khi thực hiện “chèn“ và “Xóa” đều phải thực hiện phép “dịch chuyển”.
CHƯƠNG IV: DANH SÁCH (LIST)
3. Một số nhận xét
Trong các cấu trúc DS, để thực hiện các thao tác cơ bản cần các thao tác tối thiểu:
Định vị phần tử đầu tiên của DS
Cho trước vị trí của một phần tử bất kì trong DS, xác định được phần tử tiếp theo.
CHƯƠNG IV: DANH SÁCH (LIST)
4. Kiểu dữ liệu con trỏ và việc cấp phát/thu hồi bộ nhớ động
Để khắc phục, cần
Một thủ tục tiền định để cấp phát bộ nhớ (thủ tục New (p) trong TP) và một thủ tục để giải phóng bộ nhớ (thủ tục Dispose(p) trong Tp).
Dùng biến con trỏ để truy cập đến vùng nhớ này. Kiểu của biến con trỏ đã có đặc tả kiểu dữ liệu của nó.
Khi không quan tâm tới kiểu dữ liệu của dữ liệu chứa trong vùng nhớ sử dụng con trỏ không định kiểu.
CHƯƠNG V BĂM
Bảng băm mở
1.1. Bảng băm
1.2. Hàm băm
1.3. Xung đột
1.4. Một số hàm băm thông dụng
Bảng băm đóng
2.1. Băm lại tuyến tính.
2.2. Băm lại bình phương
2.3. Băm lại bằng cách tạo vùng mới
CHƯƠNG VI: BĂM
1. Bảng băm mở
Bảng băm (Hash Table):
- Mảng B gồm m phần tử
-Lưu trữ chỉ số định vị phần tử dữ liệu có khóa phân biệt thuộc tập số nguyên { 0,1,2…m-1}
CHƯƠNG VI: BĂM
1. Bảng băm mở
Hàm băm
(Hash function):
H(x) cho giá trị là một chỉ số phần tử của B
CHƯƠNG VI: BĂM
1. Bảng băm mở
Xung đột (collision):
x1<>x2 nhưng H(x1)=H(x2)
CHƯƠNG VI: BĂM
1. Bảng băm mở
Xung đột:
CHƯƠNG VI: BĂM
1. Bảng băm mở
Xung đột:
Giải quyết:
liên kết các danh sách có các khóa khác nhau nhưng có cùng giá trị hàm băm thành một danh sách
liên kết trong bẳng băm B sẽ trỏ tới danh sách đầu tiên.
CHƯƠNG VI: BĂM
1. Bảng băm mở
Một số hàm băm thông dụng:
Hàm cắt bỏ bỏ bớt một phần nào đó của khóa.
Ví dụ: x=842615, bỏ bớt chẳng hạn các chữ số hàng lẻ (1,3,5…), số còn lại sẽ là 821. Vậy H(x) = H(842615) = 821.
Nhận xét: khó có phân bố đều.
CHƯƠNG VI: BĂM
1. Bảng băm mở
Hàm phần dư của phép chia x/m
Nên chọn m là số nguyên tố.
Nhận xét: Các cách lấy phần dư cho khả năng tránh hiện tượng xung đột
CHƯƠNG VI: BĂM
1. Bảng băm mở
Một số hàm băm thông dụng…
Hàm gấp chia số nguyên đó thành một số đoạn tùy chọn, sau đó kết hợp
Ví dụ: Số các hàng lẻ: 465 và số các hàng chẵn: 821, vậy H(x)=465+821=1286.
Nhận xét: Tính chất thứ hai có thể thỏa mãn tốt hơn
CHƯƠNG VI: BĂM
1. Bảng băm mở
CHƯƠNG VI: BĂM
2. Bảng băm đóng
Bảng băm mở: lưu trữ các liên kết trỏ đến các thành phần dữ liệu.
Bảng băm đóng: lưu trữ chính dữ liệu.
CHƯƠNG VI: BĂM
2. Bảng băm đóng
Các phương pháp xử lý:
a) Băm lại tuyến tính
Hi (x) = (H(x)+i) mod m
Nhận xét Các giá trị hàm băm xếp thành từng đoạn con, nên việc tìm kiếm ví trí rỗng sẽ rất chậm.
CHƯƠNG VI: BĂM
2. Bảng băm đóng
CHƯƠNG VI: BĂM
2. Bảng băm đóng
b) Băm lại bình phương
Hi(x) = ( H(x)+i2) mod m
CHƯƠNG VI: BĂM
2. Bảng băm đóng
c) Băm lại bằng cách tạo vùng mới
Ngoài bảng B cần tạo ra một vùng không gian mới