Thiết kế CSDL chương 3(2009)
Chia sẻ bởi Nguyễn Minh Hùng |
Ngày 19/03/2024 |
15
Chia sẻ tài liệu: Thiết kế CSDL chương 3(2009) thuộc Công nghệ thông tin
Nội dung tài liệu:
CHƯƠNG III: TẬP HỢP
1. TẬP HỢP & MÔ HÌNH DỮ LIỆU TẬP HỢP
TẬP HỢP
Các phép toán trên tập hợp:
Giao
Hợp
Trừ
Tích Đề-Cac
MÔ HÌNH DỮ LIỆU TẬP HỢP
Các phép toán trên mô hình dữ liệu tập hợp
1. Phép hợp:
Procedure Union (A, B : set; var C : set);
2. Phép giao:
Procedure Intersection(A, B : set; var C : set);
3. Phép trừ:
Procedure Difference(A, B: set ;var C : set);
Mô hình dữ liệu tập hợp
Các phép toán trên mô hình dữ liệu tập hợp
4. Xác định một phần tử có thuộc tập hợp hay không
Function Member(x:element; A : set) : boolean;
5. Phép xen vào
Procedure Insert(x:element; var A : set);
6. Phép loại bỏ
Procedure Delete(x : element; var A : set);
7. Tìm phần tử nhỏ nhất (phần tử lớn nhất)
Procedure Min (A : set; var x: element);
3. CÀI ĐẶT TẬP HỢP
Bằng vecto bit
Bằng danh sách (mảng, con trỏ)
Bằng danh sách được sắp thứ tự
Cài đặt tập hợp bởi vectơ bit
Const n= 100;
Type set = array[1..n] of boolean;
Var A, B, C : set;
x: 1..n;
Khởi tạo tập hợp
Procedure Initialize ( var A: Set);
Var i: integer;
Begin
For i:= 1 to n do
a[i]:= fasle;
End;
Phép lấy hợp của hai tập Avà B.
Procedure Union(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=A[i] or B[i];
End;
Procedure Intersection(A, B : set; var C : set);
Procedure Intersection(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=A[i] and B[i];
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=(A[i] and not B[i]);
End;
Function Member(x:element; A : set) : boolean;
Function Member(x:element; A : set) : boolean;
Begin
Menber:=a[x];
End;
Procedure Insert(x:element; var A : set);
Procedure Insert(x:element; var A : set);
Begin
A[x]:=true;
End;
7. Tìm phần tử nhỏ nhất
Function Min (A : set; x: element):element;
Var i:integer; ok:boolean;
Begin
i:=1;
ok:=true;
While (i<=n) and not ok do
If a[i]=true then ok:=true
Else i:=i+1;
if i<=n then Min:=i
else Min:=0;
End;
Cài đặt tập hợp bởi danh sách
1. Cài đặt tập hợp bởi mảng:
Const maxsize=.;
Type SET = Record
last : integer;
element: array[1 .. maxsize] of elementtype;
End;
Khởi tạo tập hợp rỗng
Procedure Initialize(Var A:Set);
Begin
a.last := 0;
End;
Kiểm tra một phần tử x có trong tập hợp không?
Function Member(x:elementtype; A : set) : boolean;
Var i:integer; ok:boolean;
Begin
i:=1; ok:=false;
while (i<=a.last) and not ok do
if a.element[i]=x then ok:=true
Else i:=i+1;
Member:=ok;
End;
Thêm một phân tử x vào tập hợp
Procedure Insertion(x:elementtype; Var A:Set);
Begin
If (a.last = maxsize) and ( not member(x, A)) then
Begin
A.last:=a.last+1;
a.Element[a.last]:= x;
End
Else write(`Khong them duoc`)
End;
Phép lấy hợp của hai tập Avà B.
Procedure Union(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to a.last do Insertion(A.element[i], C);
For i:=1 to b.last do
if not member(b.element[i], C) then
Insertion(b.element[i], C)
End;
Phép toán tìm giao của hai tập hợp
Procedure Intersection(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to b.last do
if member(b.element[i], A) then
Insertion(b.element[i], C)
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to a.last do
If not member(a.element[i], B) then
Insertion(a.element[i], C);
End;
Phép toán tìm phần tử nhỏ nhất của tập hợp
Function Min(A:set):elementtype;
Var i:integer;
Begin
Min:=0;
For i:=1 to a.last do
If min >a.element[i] then Min:=a.element[i];
End;
2. Cài đặt tập hợp bởi danh sách liên kết.
Type pointer = ^ Cell;
Cell = record
element : elementtype;
Next : pointer;
End;
Khởi tạo tập hợp rỗng
Procedure Initialize(var S: pointer);
Begin
S := nil;
End;
Kiểm tra một phần tử x có trong tập hợp không?
Function Member(x:elementtype; S: Pointer) : boolean;
Var p: pointer; ok:boolean;
Begin
p: = s; ok:=false;
while (p<> nil) and not ok do
if p^.element=x then ok:=true
Else p:= p^.next;
Member:=ok;
End;
Thêm một phân tử x vào tập hợp
Procedure Insertion(x:elementtype; Var S: pointer);
Var p: pointer;
Begin
If not member(x, S) then
Begin
new(p);
p^.elememt:=x;
p^.next:=s^.next;
s^.next:=p;
End
Else write(`Khong them duoc`)
End;
Phép lấy hợp của hai tập Avà B
Procedure Union(A, B: Pointer; var C : Pointer);
Var p, q: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do Insertion(p^.elememt, C);
q:=b;
while (q<> nil) do
if not member(q^.elememt, C) then
Insertion(q^.elememt, C)
End;
Phép toán tìm giao của hai tập hợp
Procedure Intersection(A, B: Pointer; var C : Pointer);
Var p: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do
If member(p^.elememt, B) then
Insertion(p^.elememt, C);
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B: Pointer; var C : Pointer);
Var p, q: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do
If not member(p^.elememt, B) then
Insertion(p^.elememt, C)
End;
4. TỪ ĐIỂN
Từ điển:
Mô hình dữ liệu tập hợp, nhưng chỉ xét đến những phép toán Insert, Delete và Member được gọi là kiểu dữ liệu trừu tượng từ điển (Dictionary)
Các phương pháp đơn giản để cài đặt từ điển
Từ điển là một tập hợp, do đó đương nhiên ta có thể sử dụng các phương pháp cài đặt tập hợp để cài đặt từ điển.
Cài đặt từ điển bởi vectơ bit.
Các phép toán được cài đặt đơn giản với thời gian hằng.
Tuy nhiên, ta chỉ có thể áp dụng được nếu từ điển là một tập hợp có thể dùng làm tập chỉ số cho mảng.
Cài đặt từ điển bằng danh sách
Cài đặt các phép toán tương đối đơn giản
Thời gian thực hiện các phép toán Insert, Delete, Member nói chung là O(n) với từ điển có n phần tử.
5. CẤU TRÚC DỮ LIỆU BẢNG BĂM.
CÀI ĐẶT TỬ ĐIỂN BẰNG BẢNG BĂM
Có hai phương pháp băm: băm đóng và băm mở.
Băm mở (open hashing) cho phép sử dụng một không gian không hạn chế để lưu giữ các phần tử của tập hợp.
Băm đóng (closed hashing) sử dụng một không gian cố định và do đó tập hợp được cài đặt phải có cỡ không vượt quá không gian cho phép.
Băm là phương pháp rất thích hợp để cài đặt tập hợp có số phần tử lớn.
5.1 BẢNG BĂM MỞ
Tư tưởng:
Phân chia tập hợp đã cho thành một số cố định các lớp. (N lớp được đánh số 0, 1, . N-1.).
Sử dụng mảng T với chỉ số từ 0 đến N-1. Mỗi thành phần T[i] như một "rổ" đựng các phần tử lớp thứ i.
Các phần tử thuộc mỗi lớp được tổ chức dưới dạng một danh sách liên kết. Do đó T[i] sẽ chứa con trỏ trỏ đến danh sách của lớp i. Ta gọi mảng T là bảng băm (hash table).
Hàm băm (hash function) h
Hàm băm sẽ phân chia các phần tử vào các lớp.
Nếu x là giá trị khoá của phần tử nào đó của tập hợp thì h(x) là một chỉ số của mảng T và ta gọi h(x) là giá trị băm (hash value) của x.
Như vậy h là ánh xạ của tập hợp các khoá K vào tập hợp {0, 1, , .N-1}.
Tiêu chuẩn để đánh giá một hàm băm
Một, cho phép tính được dễ dàng và nhanh chóng giá trị băm của mỗi khoá.
Hai, phải phân bố đều các khoá vào các rổ.
1. Phương pháp cắt bỏ
Giả sử khoá là số nguyên, ta sẽ bỏ đi một phần nào đó của khoá và lấy phần còn lại làm giá trị băm của khoá.
Ví dụ: Nếu khoá là các số nguyên 10 chữ số và bảng băm gồm 1000 thành phần, khi đó ta có thể lấy chữ số thứ nhất, thứ ba và thứ bảy từ bên trái làm giá trị băm. Chẳng hạn�: h(7103592810)=702.
1. Phương pháp cắt bỏ
Phương pháp cắt bỏ rất đơn giản, nhưng nó thường không phân bố đều các khoá .
2. Phương pháp gấp
Giả sử khoá là số nguyên. Ta phân chia khoá thành một số phần, sau đó kết hợp các phần lại bằng một cách nào đó (chẳng hạn, dùng phép cộng hoặc phép nhân) để nhận giá trị băm.
Ví dụ:
Nếu khoá là số nguyên 10 chữ số ta phân thành các nhóm ba , ba, hai và hai chữ số từ bên trái.
Cộng các nhóm với nhau, sau đó cắt cụt nếu cần thiết, ta sẽ nhận được giá trị của hàm băm.
Chẳng hạn: 7103592810 được biến đổi thành 710+359+28+10 =1107, do đó ta có giá trị băm là 107.
2. Phương pháp gấp
Vì mọi thông tin trong khoá đều được phản ánh vào giá trị băm, nên phương pháp gấp cho phân bố đều các khoá tốt hơn phương pháp cắt bỏ.
3. Phưiơng pháp sử dụng phép toán lấy phần dư
Giả sử khoá là số nguyên, và giả sử ta muốn chia tập hợp các khoá thành N lớp. Chia số nguyên cho N (tốt nhất chọn n là số nguyên tố) rồi lấy phần dư làm giá trị băm.
Cài đặt hàm băm với khóa là một chuỗi có 10 ký tự
Type keytype = string[10];
Function h(x:keytype) :0 .. N-1;
Var i, sum :integer;
Begin
Sum :=0;
For i:=1 to 10 do
Sum:= sum +ord(x[i]);
h:=Sum mod N;
end;
Cấu trúc dữ liệu bảng băm mở
Khai báo bảng băm mở biểu diễn từ điển
Const N = .
Type pointer = ^ element;
Element = record
Key : keytype;
Next:pointer;
end;
Dictionary =array[0.. N-1] of pointer;
Var T: Dictionary;
Khởi tạo một từ điển rỗng
Procedure Initialize(var T: Dictionary);
Begin
For i:=0 to N -1 do T[i]= nil;
End;
Kiểm tra một phần tử có thuộc từ điển hay không?
Function Member(x : keytype; Var T : Dictionary): boolean;
Var p : pointer; found :boolean;
Begin
P:=T[h(x)];
Found:=false;
While (P<> nil) and (not found ) do
If P^.key =x then found :=true
Else P:=P^.next;
Member :=found;
End;
Thêm một phần tử vào từ điển
Procedure Insert (x : keytype; Var T : Dictionary);
Var i : 1.. N-1;
P : pointer;
Begin
If not member(x, T) then
Begin
i:=h(x);
New(P);
P^.key:=x;
P^.next:=T[i];
T[i]:=P;
End;
End;
Xóa một phần tử khỏi từ điển
Procedure Delete(x : keytype; var T : Dictionary);
Var i : 0 .. N-1; P, Q : pointer; Found :boolean;
Begin
i:=h(x);
If T[i]<> nil then
If T[i]^.key = x then {loai x khoi danh sach}
T[i]:=T[i]^.next;
Else Begin
Q:=T[i];
P:=Q^.next;
Found:=false;
Xóa một phần tử khỏi từ điển
While (P<> nil) and (not found) do
If P^.key=x then
Begin{loai x khoi danh sach }
Q^.next:=P^.next;
Found :=true;
End else
Begin
Q:=P;
P:=q^.next;
End;
End;
End;
5.2. BẢNG BĂM ĐÓNG
Mỗi phần tử của tập hợp đựơc lưu giữ trong chính các thành phần T[i] của mảng.
Khai báo kiểu dữ liệu từ điển được cài đặt bởi bảng băm đóng:
Type Dictionary = array[0 .. N-1] of keytype;
Hàm băm là một ánh xạ
H : K ? {0,1, .., N-1}
BẢNG BĂM ĐÓNG
Hàm băm là ánh xạ từ tập hợp các khoá K vào tập hợp các chỉ số 0,1 ,., N-1 của mảng.
Đây là một ánh xạ nhiều - vào - một nên có thể xảy ra một số khoá khác nhau được ánh xạ vào cùng một chỉ số.
Tình huống này được gọi là sự va chạm (collision). Để giải quyết vấn đề bằng cách băm lại (rehasing).
Băm lại tuyến tính
Đây là phương pháp đơn giản nhất. Các hàm hi(x) được xác định: hi(x) =(h(x) +i) mod N
Tức là ta xem mảng là mảng vòng tròn và lần lượt xem xét các vị trí h(x)+1, h(x) +2, ..
Chẳng hạn, N=10 và các khoá a, b, c, d, e có các giá trị băm như sau: h(a)=7, h(b)=1, h(c)=4, h(d)=3, h(e)=3.
Băm lại bình phương
Phương pháp này tốt hơn, tránh được sự tích tụ trong bảng các giá trị xung quanh các giá trị đưa vào bảng ban đầu, hàm băm lại được là:
hi(x)=(h(x) +i2) mod N
Khai báo cấu trúc dữ liệu bảng băm đóng biểu diễn từ điển
Const N=..;
Empty=.;
Delete=...;
(empty và deleted là hai hằng khác với tất cả các giá trị khoá của các phần tử của từ điển)
Type Dictionary = array[0..N-1] of keytype;
Var T : Dictionary;
Thủ tục location
Xuất phát từ h(x) dò tìm lần lượt qua các h1(x), h2(x). cho đến khi tìm được vị trí chứa x hoặc vị trí trống đầu tiên.
k là vị trí mà tại đó quá trình tìm kiếm dừng lại.
j là vị trí bị xóa hay trống đầu tiên.
Procedure Location (x: keytype; var k, j : integer);
Var i : integer;
Begin
i:=h(x);
j:=i;
if (T[i]=x ) or (T[i] =empty) then k:=i
else Begin
k =(i+1) mod N
while (k<> i) and( T [k]<> x ) and(T[k]<> empty) do
Begin
if (T[k]= deleted) and(T[j]<> deleted) then j:=k;
k:=(k+1) mod N;
End;
if (T[k] = empty) and (T[j]<> deleted) then j:=k;
End;
End;
Xác định xem một phần tử có trong từ điển
hay không?
Function Member(x : keytype; var T : Dictionary) : boolean;
Var k, j : integer;
Begin
Location(x, k, j);
If T[k]=x then Member:=true
Else Member :=false;
End;
Thêm một phần tử vào từ điển
Procedure Insert(x : keytype; var T : Dictionary);
Var k, j : integer;
Begin
Location(x, k, j);
If T[k]<>x then
If (T[j] = deleted ) or (T[j]=empty ) then T[j]:=x
Else writeln (`bảng day`)
Else writeln (`bảng đã có x`);
End;
Xóa một phần tử khỏi từ điển
Procedure Delete (x : keytype; var T : Dictionary);
Var k, j : integer;
Begin
Location (x, k, j);
If T [k]=x then T[k]=deleted;
End;
6. HÀNG ƯU TIÊN
Hàng ưu tiên là tập hợp cùng với hai phép toán Insert và DeleteMin.
Phép toán Insert có ý nghĩ thông thường xen phần tử mới vào tập hợp.
Phép toán DeleteMin trên tập hợp A là tìm trên tập hợp A phần tử a có Pri nhỏ nhất và loại nó khỏi tập A.
Cài đặt hàng ưu tiên
Ta có thể biểu diễn hàng ưu tiên bởi danh sách được sắp tăng dần theo giá trị ưu tiên của các phần tử hoặc không được sắp.
Nếu cài đặt hàng ưu tiên bởi danh sách được sắp xếp thì phép toán DeleteMin chỉ là xóa phần tử đầu tiên trong danh sách => thời gian là O(1). Nhưng phép toán Insert đòi hỏi phải có thời gian 0(n)
Nếu ta cài đặt hàng ưu tiên bởi danh sách không được sắp xếp, thì khi xen phần tử mới vào hàng, ta chỉ cần đưa nó vào đầu danh sách. Nhưng việc thực hiện phép toán DeleteMin lại chậm.
7. CÂY THỨ TỰ BỘ PHẬN VÀ CÀI ĐẶT HÀNG ƯU TIÊN BỞI CÂY THỨ TỰ BỘ PHẬN
Cây thứ tự bộ phận là một cây nhị phân thỏa các điều kiện sau:
1. Tất cả các mức của cây đều đầy, trừ mức thấp nhất có thể thiếu.
2. Ở mức thấp nhất, tất cả các lá đều xuất hiện liên tiếp từ bên trái.
3. Giá trị của mỗi đỉnh không lớn hơn giá trị của các đỉnh con của nó.
Ví dụ:
Phép toán Insert
Thêm một lá mới liền kề với các lá ở mức thấp nhất, nếu mức thấp nhất chưa đầy; ngược lại, thì ta thêm vào một lá ở mức mới sao cho các điều kiện của 1 và 2.
Nếu sau khi thêm vào lá mới cây không còn là cây thứ tự bộ phận, thì ta theo đường từ lá mới tới gốc cây. Nếu một đỉnh có giá trị ưu tiên nhỏ hơn đỉnh cha của nó, thì ta trao đổi đỉnh đó với cha của nó.
Ví dụ:
Ví dụ:
2
5
8
9
7
10
11
10
12
8
3
Ví dụ:
2
3
8
5
7
10
11
10
12
8
9
Ví dụ:
2
5
8
3
7
10
11
10
12
8
9
Phép toán DeleteMin
Thay giá trị của gốc bởi giá trị nút lá ngoài cùng bên phải ở mức thấp nhất.
Loại bỏ lá này khỏi cây.
Đi từ gốc xuống. Giả sử tại một bước nào đó ta đang ở đỉnh a và hai con của nó là b và c. Thì hoán vị pri(a) và pri(d), đi xuống đỉnh d (với pri(d)=min (pri(a), pri(b))..
Quá trình cho đến khi gặp nút lá hay đỉnh được xét thỏa điều kiện 3.
Ví dụ:
Ví dụ:
10
5
8
9
7
10
11
12
8
Ví dụ:
5
10
8
9
7
10
11
12
8
Ví dụ:
5
7
8
9
10
10
11
12
8
Cài đặt cây thứ tự bộ phận bởi mảng
Giả sử ta đánh số các đỉnh của cây thứ tự bộ phận từ trên xuống dưới và từ trái qua phải (trong cùng một mức ), bắt đầu từ gốc có số hiệu là 1
Const N = ...;
Type PriQueue =Record
Element : array [1..N] of item;
Last : integer;
End;
Var H : PriQueue;
Việc khởi tạo một hàng rỗng được thực hiện bởi lệnh:
H.last:= 0 ;
Xem tài liệu
Procedure Insert(x:item; Var H : PriQueue );
Procedure DeleteMin(Var H : PriQueue; Var x: item);
1. TẬP HỢP & MÔ HÌNH DỮ LIỆU TẬP HỢP
TẬP HỢP
Các phép toán trên tập hợp:
Giao
Hợp
Trừ
Tích Đề-Cac
MÔ HÌNH DỮ LIỆU TẬP HỢP
Các phép toán trên mô hình dữ liệu tập hợp
1. Phép hợp:
Procedure Union (A, B : set; var C : set);
2. Phép giao:
Procedure Intersection(A, B : set; var C : set);
3. Phép trừ:
Procedure Difference(A, B: set ;var C : set);
Mô hình dữ liệu tập hợp
Các phép toán trên mô hình dữ liệu tập hợp
4. Xác định một phần tử có thuộc tập hợp hay không
Function Member(x:element; A : set) : boolean;
5. Phép xen vào
Procedure Insert(x:element; var A : set);
6. Phép loại bỏ
Procedure Delete(x : element; var A : set);
7. Tìm phần tử nhỏ nhất (phần tử lớn nhất)
Procedure Min (A : set; var x: element);
3. CÀI ĐẶT TẬP HỢP
Bằng vecto bit
Bằng danh sách (mảng, con trỏ)
Bằng danh sách được sắp thứ tự
Cài đặt tập hợp bởi vectơ bit
Const n= 100;
Type set = array[1..n] of boolean;
Var A, B, C : set;
x: 1..n;
Khởi tạo tập hợp
Procedure Initialize ( var A: Set);
Var i: integer;
Begin
For i:= 1 to n do
a[i]:= fasle;
End;
Phép lấy hợp của hai tập Avà B.
Procedure Union(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=A[i] or B[i];
End;
Procedure Intersection(A, B : set; var C : set);
Procedure Intersection(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=A[i] and B[i];
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B:set; var C : set);
Var i:integer;
Begin
For i:=1 to n do C [i]:=(A[i] and not B[i]);
End;
Function Member(x:element; A : set) : boolean;
Function Member(x:element; A : set) : boolean;
Begin
Menber:=a[x];
End;
Procedure Insert(x:element; var A : set);
Procedure Insert(x:element; var A : set);
Begin
A[x]:=true;
End;
7. Tìm phần tử nhỏ nhất
Function Min (A : set; x: element):element;
Var i:integer; ok:boolean;
Begin
i:=1;
ok:=true;
While (i<=n) and not ok do
If a[i]=true then ok:=true
Else i:=i+1;
if i<=n then Min:=i
else Min:=0;
End;
Cài đặt tập hợp bởi danh sách
1. Cài đặt tập hợp bởi mảng:
Const maxsize=.;
Type SET = Record
last : integer;
element: array[1 .. maxsize] of elementtype;
End;
Khởi tạo tập hợp rỗng
Procedure Initialize(Var A:Set);
Begin
a.last := 0;
End;
Kiểm tra một phần tử x có trong tập hợp không?
Function Member(x:elementtype; A : set) : boolean;
Var i:integer; ok:boolean;
Begin
i:=1; ok:=false;
while (i<=a.last) and not ok do
if a.element[i]=x then ok:=true
Else i:=i+1;
Member:=ok;
End;
Thêm một phân tử x vào tập hợp
Procedure Insertion(x:elementtype; Var A:Set);
Begin
If (a.last = maxsize) and ( not member(x, A)) then
Begin
A.last:=a.last+1;
a.Element[a.last]:= x;
End
Else write(`Khong them duoc`)
End;
Phép lấy hợp của hai tập Avà B.
Procedure Union(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to a.last do Insertion(A.element[i], C);
For i:=1 to b.last do
if not member(b.element[i], C) then
Insertion(b.element[i], C)
End;
Phép toán tìm giao của hai tập hợp
Procedure Intersection(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to b.last do
if member(b.element[i], A) then
Insertion(b.element[i], C)
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B:set; var C : set);
Var i:integer;
Begin
Initialize(C);
For i:=1 to a.last do
If not member(a.element[i], B) then
Insertion(a.element[i], C);
End;
Phép toán tìm phần tử nhỏ nhất của tập hợp
Function Min(A:set):elementtype;
Var i:integer;
Begin
Min:=0;
For i:=1 to a.last do
If min >a.element[i] then Min:=a.element[i];
End;
2. Cài đặt tập hợp bởi danh sách liên kết.
Type pointer = ^ Cell;
Cell = record
element : elementtype;
Next : pointer;
End;
Khởi tạo tập hợp rỗng
Procedure Initialize(var S: pointer);
Begin
S := nil;
End;
Kiểm tra một phần tử x có trong tập hợp không?
Function Member(x:elementtype; S: Pointer) : boolean;
Var p: pointer; ok:boolean;
Begin
p: = s; ok:=false;
while (p<> nil) and not ok do
if p^.element=x then ok:=true
Else p:= p^.next;
Member:=ok;
End;
Thêm một phân tử x vào tập hợp
Procedure Insertion(x:elementtype; Var S: pointer);
Var p: pointer;
Begin
If not member(x, S) then
Begin
new(p);
p^.elememt:=x;
p^.next:=s^.next;
s^.next:=p;
End
Else write(`Khong them duoc`)
End;
Phép lấy hợp của hai tập Avà B
Procedure Union(A, B: Pointer; var C : Pointer);
Var p, q: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do Insertion(p^.elememt, C);
q:=b;
while (q<> nil) do
if not member(q^.elememt, C) then
Insertion(q^.elememt, C)
End;
Phép toán tìm giao của hai tập hợp
Procedure Intersection(A, B: Pointer; var C : Pointer);
Var p: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do
If member(p^.elememt, B) then
Insertion(p^.elememt, C);
End;
Phép toán tìm hiệu của tập hợp A và B
Procedure Diference(A, B: Pointer; var C : Pointer);
Var p, q: pointer;
Begin
Initialize(C);
p:= a;
while (p<> nil) do
If not member(p^.elememt, B) then
Insertion(p^.elememt, C)
End;
4. TỪ ĐIỂN
Từ điển:
Mô hình dữ liệu tập hợp, nhưng chỉ xét đến những phép toán Insert, Delete và Member được gọi là kiểu dữ liệu trừu tượng từ điển (Dictionary)
Các phương pháp đơn giản để cài đặt từ điển
Từ điển là một tập hợp, do đó đương nhiên ta có thể sử dụng các phương pháp cài đặt tập hợp để cài đặt từ điển.
Cài đặt từ điển bởi vectơ bit.
Các phép toán được cài đặt đơn giản với thời gian hằng.
Tuy nhiên, ta chỉ có thể áp dụng được nếu từ điển là một tập hợp có thể dùng làm tập chỉ số cho mảng.
Cài đặt từ điển bằng danh sách
Cài đặt các phép toán tương đối đơn giản
Thời gian thực hiện các phép toán Insert, Delete, Member nói chung là O(n) với từ điển có n phần tử.
5. CẤU TRÚC DỮ LIỆU BẢNG BĂM.
CÀI ĐẶT TỬ ĐIỂN BẰNG BẢNG BĂM
Có hai phương pháp băm: băm đóng và băm mở.
Băm mở (open hashing) cho phép sử dụng một không gian không hạn chế để lưu giữ các phần tử của tập hợp.
Băm đóng (closed hashing) sử dụng một không gian cố định và do đó tập hợp được cài đặt phải có cỡ không vượt quá không gian cho phép.
Băm là phương pháp rất thích hợp để cài đặt tập hợp có số phần tử lớn.
5.1 BẢNG BĂM MỞ
Tư tưởng:
Phân chia tập hợp đã cho thành một số cố định các lớp. (N lớp được đánh số 0, 1, . N-1.).
Sử dụng mảng T với chỉ số từ 0 đến N-1. Mỗi thành phần T[i] như một "rổ" đựng các phần tử lớp thứ i.
Các phần tử thuộc mỗi lớp được tổ chức dưới dạng một danh sách liên kết. Do đó T[i] sẽ chứa con trỏ trỏ đến danh sách của lớp i. Ta gọi mảng T là bảng băm (hash table).
Hàm băm (hash function) h
Hàm băm sẽ phân chia các phần tử vào các lớp.
Nếu x là giá trị khoá của phần tử nào đó của tập hợp thì h(x) là một chỉ số của mảng T và ta gọi h(x) là giá trị băm (hash value) của x.
Như vậy h là ánh xạ của tập hợp các khoá K vào tập hợp {0, 1, , .N-1}.
Tiêu chuẩn để đánh giá một hàm băm
Một, cho phép tính được dễ dàng và nhanh chóng giá trị băm của mỗi khoá.
Hai, phải phân bố đều các khoá vào các rổ.
1. Phương pháp cắt bỏ
Giả sử khoá là số nguyên, ta sẽ bỏ đi một phần nào đó của khoá và lấy phần còn lại làm giá trị băm của khoá.
Ví dụ: Nếu khoá là các số nguyên 10 chữ số và bảng băm gồm 1000 thành phần, khi đó ta có thể lấy chữ số thứ nhất, thứ ba và thứ bảy từ bên trái làm giá trị băm. Chẳng hạn�: h(7103592810)=702.
1. Phương pháp cắt bỏ
Phương pháp cắt bỏ rất đơn giản, nhưng nó thường không phân bố đều các khoá .
2. Phương pháp gấp
Giả sử khoá là số nguyên. Ta phân chia khoá thành một số phần, sau đó kết hợp các phần lại bằng một cách nào đó (chẳng hạn, dùng phép cộng hoặc phép nhân) để nhận giá trị băm.
Ví dụ:
Nếu khoá là số nguyên 10 chữ số ta phân thành các nhóm ba , ba, hai và hai chữ số từ bên trái.
Cộng các nhóm với nhau, sau đó cắt cụt nếu cần thiết, ta sẽ nhận được giá trị của hàm băm.
Chẳng hạn: 7103592810 được biến đổi thành 710+359+28+10 =1107, do đó ta có giá trị băm là 107.
2. Phương pháp gấp
Vì mọi thông tin trong khoá đều được phản ánh vào giá trị băm, nên phương pháp gấp cho phân bố đều các khoá tốt hơn phương pháp cắt bỏ.
3. Phưiơng pháp sử dụng phép toán lấy phần dư
Giả sử khoá là số nguyên, và giả sử ta muốn chia tập hợp các khoá thành N lớp. Chia số nguyên cho N (tốt nhất chọn n là số nguyên tố) rồi lấy phần dư làm giá trị băm.
Cài đặt hàm băm với khóa là một chuỗi có 10 ký tự
Type keytype = string[10];
Function h(x:keytype) :0 .. N-1;
Var i, sum :integer;
Begin
Sum :=0;
For i:=1 to 10 do
Sum:= sum +ord(x[i]);
h:=Sum mod N;
end;
Cấu trúc dữ liệu bảng băm mở
Khai báo bảng băm mở biểu diễn từ điển
Const N = .
Type pointer = ^ element;
Element = record
Key : keytype;
Next:pointer;
end;
Dictionary =array[0.. N-1] of pointer;
Var T: Dictionary;
Khởi tạo một từ điển rỗng
Procedure Initialize(var T: Dictionary);
Begin
For i:=0 to N -1 do T[i]= nil;
End;
Kiểm tra một phần tử có thuộc từ điển hay không?
Function Member(x : keytype; Var T : Dictionary): boolean;
Var p : pointer; found :boolean;
Begin
P:=T[h(x)];
Found:=false;
While (P<> nil) and (not found ) do
If P^.key =x then found :=true
Else P:=P^.next;
Member :=found;
End;
Thêm một phần tử vào từ điển
Procedure Insert (x : keytype; Var T : Dictionary);
Var i : 1.. N-1;
P : pointer;
Begin
If not member(x, T) then
Begin
i:=h(x);
New(P);
P^.key:=x;
P^.next:=T[i];
T[i]:=P;
End;
End;
Xóa một phần tử khỏi từ điển
Procedure Delete(x : keytype; var T : Dictionary);
Var i : 0 .. N-1; P, Q : pointer; Found :boolean;
Begin
i:=h(x);
If T[i]<> nil then
If T[i]^.key = x then {loai x khoi danh sach}
T[i]:=T[i]^.next;
Else Begin
Q:=T[i];
P:=Q^.next;
Found:=false;
Xóa một phần tử khỏi từ điển
While (P<> nil) and (not found) do
If P^.key=x then
Begin{loai x khoi danh sach }
Q^.next:=P^.next;
Found :=true;
End else
Begin
Q:=P;
P:=q^.next;
End;
End;
End;
5.2. BẢNG BĂM ĐÓNG
Mỗi phần tử của tập hợp đựơc lưu giữ trong chính các thành phần T[i] của mảng.
Khai báo kiểu dữ liệu từ điển được cài đặt bởi bảng băm đóng:
Type Dictionary = array[0 .. N-1] of keytype;
Hàm băm là một ánh xạ
H : K ? {0,1, .., N-1}
BẢNG BĂM ĐÓNG
Hàm băm là ánh xạ từ tập hợp các khoá K vào tập hợp các chỉ số 0,1 ,., N-1 của mảng.
Đây là một ánh xạ nhiều - vào - một nên có thể xảy ra một số khoá khác nhau được ánh xạ vào cùng một chỉ số.
Tình huống này được gọi là sự va chạm (collision). Để giải quyết vấn đề bằng cách băm lại (rehasing).
Băm lại tuyến tính
Đây là phương pháp đơn giản nhất. Các hàm hi(x) được xác định: hi(x) =(h(x) +i) mod N
Tức là ta xem mảng là mảng vòng tròn và lần lượt xem xét các vị trí h(x)+1, h(x) +2, ..
Chẳng hạn, N=10 và các khoá a, b, c, d, e có các giá trị băm như sau: h(a)=7, h(b)=1, h(c)=4, h(d)=3, h(e)=3.
Băm lại bình phương
Phương pháp này tốt hơn, tránh được sự tích tụ trong bảng các giá trị xung quanh các giá trị đưa vào bảng ban đầu, hàm băm lại được là:
hi(x)=(h(x) +i2) mod N
Khai báo cấu trúc dữ liệu bảng băm đóng biểu diễn từ điển
Const N=..;
Empty=.;
Delete=...;
(empty và deleted là hai hằng khác với tất cả các giá trị khoá của các phần tử của từ điển)
Type Dictionary = array[0..N-1] of keytype;
Var T : Dictionary;
Thủ tục location
Xuất phát từ h(x) dò tìm lần lượt qua các h1(x), h2(x). cho đến khi tìm được vị trí chứa x hoặc vị trí trống đầu tiên.
k là vị trí mà tại đó quá trình tìm kiếm dừng lại.
j là vị trí bị xóa hay trống đầu tiên.
Procedure Location (x: keytype; var k, j : integer);
Var i : integer;
Begin
i:=h(x);
j:=i;
if (T[i]=x ) or (T[i] =empty) then k:=i
else Begin
k =(i+1) mod N
while (k<> i) and( T [k]<> x ) and(T[k]<> empty) do
Begin
if (T[k]= deleted) and(T[j]<> deleted) then j:=k;
k:=(k+1) mod N;
End;
if (T[k] = empty) and (T[j]<> deleted) then j:=k;
End;
End;
Xác định xem một phần tử có trong từ điển
hay không?
Function Member(x : keytype; var T : Dictionary) : boolean;
Var k, j : integer;
Begin
Location(x, k, j);
If T[k]=x then Member:=true
Else Member :=false;
End;
Thêm một phần tử vào từ điển
Procedure Insert(x : keytype; var T : Dictionary);
Var k, j : integer;
Begin
Location(x, k, j);
If T[k]<>x then
If (T[j] = deleted ) or (T[j]=empty ) then T[j]:=x
Else writeln (`bảng day`)
Else writeln (`bảng đã có x`);
End;
Xóa một phần tử khỏi từ điển
Procedure Delete (x : keytype; var T : Dictionary);
Var k, j : integer;
Begin
Location (x, k, j);
If T [k]=x then T[k]=deleted;
End;
6. HÀNG ƯU TIÊN
Hàng ưu tiên là tập hợp cùng với hai phép toán Insert và DeleteMin.
Phép toán Insert có ý nghĩ thông thường xen phần tử mới vào tập hợp.
Phép toán DeleteMin trên tập hợp A là tìm trên tập hợp A phần tử a có Pri nhỏ nhất và loại nó khỏi tập A.
Cài đặt hàng ưu tiên
Ta có thể biểu diễn hàng ưu tiên bởi danh sách được sắp tăng dần theo giá trị ưu tiên của các phần tử hoặc không được sắp.
Nếu cài đặt hàng ưu tiên bởi danh sách được sắp xếp thì phép toán DeleteMin chỉ là xóa phần tử đầu tiên trong danh sách => thời gian là O(1). Nhưng phép toán Insert đòi hỏi phải có thời gian 0(n)
Nếu ta cài đặt hàng ưu tiên bởi danh sách không được sắp xếp, thì khi xen phần tử mới vào hàng, ta chỉ cần đưa nó vào đầu danh sách. Nhưng việc thực hiện phép toán DeleteMin lại chậm.
7. CÂY THỨ TỰ BỘ PHẬN VÀ CÀI ĐẶT HÀNG ƯU TIÊN BỞI CÂY THỨ TỰ BỘ PHẬN
Cây thứ tự bộ phận là một cây nhị phân thỏa các điều kiện sau:
1. Tất cả các mức của cây đều đầy, trừ mức thấp nhất có thể thiếu.
2. Ở mức thấp nhất, tất cả các lá đều xuất hiện liên tiếp từ bên trái.
3. Giá trị của mỗi đỉnh không lớn hơn giá trị của các đỉnh con của nó.
Ví dụ:
Phép toán Insert
Thêm một lá mới liền kề với các lá ở mức thấp nhất, nếu mức thấp nhất chưa đầy; ngược lại, thì ta thêm vào một lá ở mức mới sao cho các điều kiện của 1 và 2.
Nếu sau khi thêm vào lá mới cây không còn là cây thứ tự bộ phận, thì ta theo đường từ lá mới tới gốc cây. Nếu một đỉnh có giá trị ưu tiên nhỏ hơn đỉnh cha của nó, thì ta trao đổi đỉnh đó với cha của nó.
Ví dụ:
Ví dụ:
2
5
8
9
7
10
11
10
12
8
3
Ví dụ:
2
3
8
5
7
10
11
10
12
8
9
Ví dụ:
2
5
8
3
7
10
11
10
12
8
9
Phép toán DeleteMin
Thay giá trị của gốc bởi giá trị nút lá ngoài cùng bên phải ở mức thấp nhất.
Loại bỏ lá này khỏi cây.
Đi từ gốc xuống. Giả sử tại một bước nào đó ta đang ở đỉnh a và hai con của nó là b và c. Thì hoán vị pri(a) và pri(d), đi xuống đỉnh d (với pri(d)=min (pri(a), pri(b))..
Quá trình cho đến khi gặp nút lá hay đỉnh được xét thỏa điều kiện 3.
Ví dụ:
Ví dụ:
10
5
8
9
7
10
11
12
8
Ví dụ:
5
10
8
9
7
10
11
12
8
Ví dụ:
5
7
8
9
10
10
11
12
8
Cài đặt cây thứ tự bộ phận bởi mảng
Giả sử ta đánh số các đỉnh của cây thứ tự bộ phận từ trên xuống dưới và từ trái qua phải (trong cùng một mức ), bắt đầu từ gốc có số hiệu là 1
Const N = ...;
Type PriQueue =Record
Element : array [1..N] of item;
Last : integer;
End;
Var H : PriQueue;
Việc khởi tạo một hàng rỗng được thực hiện bởi lệnh:
H.last:= 0 ;
Xem tài liệu
Procedure Insert(x:item; Var H : PriQueue );
Procedure DeleteMin(Var H : PriQueue; Var x: item);
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Nguyễn Minh Hùng
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)