Tải bản đầy đủ (.pdf) (5 trang)

Chương 3 tập hợp phần 2

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (327.87 KB, 5 trang )

NỘI DUNG

CÁC PHÉP TOÁN CƠ BẢN
TRÊN TẬP HỢP







Khái niệm tập hợp
Các kiểu dữ liệu trừu tượng trên tập hợp
Cài đặt tập hợp
Từ điển
Bảng băm

Bộ môn Công nghệ phần mềm,
Khoa CNTT&TT, Đại học Cần Thơ

BĂM ĐÓNG

CÀI ĐẶT TỪ ĐIỂN BẰNG BẢNG BĂM
Chỉ
số

• BĂM ĐÓNG
• BĂM MỞ

0


20

1
2
3
4

34

5
6

26

H(x)=x%B


B-1

19

1


BĂM ĐÓNG

BĂM ĐÓNG
• Tạo từ điển rỗng

• Khai báo


// Tao tu dien rong
void MakeNullDic(Dictionary D)
for (int i=0;iD[i]=Empty;
}

#define B 100
#define Deleted –1000
//Gia dinh gia tri cho o da bi xoa
#define Empty 1000
//Gia dinh gia tri cho o chua su dung
typedef int ElementType;
typedef struct Dictionary[B];

BĂM ĐÓNG

BĂM ĐÓNG
Thêm vào giá trị 29
Chỉ
số

Thêm vào giá trị 30
H(x)=x%B
0

20

20


1

29

1

29

2

12

i=1 H(30) = 1

2

E

3

D30

3

E

4

34


i=2 H(30)=2

4

34

5

E

5

E

26

6

26

i=1 H(29) = 0

6


E



E


i=2 H(29)=1

0

E
B-1 (9)

i=0 H(29) = 9

i=0 H(30) = 0

i=3 H(30)=3

E
B-1

19

19

Hi(x) = (H(x)+i)%B

2


BĂM ĐÓNG
• Kiểm tra sự tồn tại của phần tử trong từ điển
int Member(ElementType X, Dictionary D) {
Position P = H(X); // ham bam

int i=0;
Found = 0;
while ((i < B) && (D[P]!=Empty) && (!Found))
if (D[P] == X) Found = 1;
else {
P=(P+1)%B;
i++;
}
return Found;
}

BĂM ĐÓNG
• Kiểm tra bảng băm có đầy?
int FullSet(Dictionary D) {
int i=0;
int Full=1;
while ((iif ((D[i] == Deleted)||(D[i] == Empty))
Full = 0;
else
i++;
return Full;
}

BĂM ĐÓNG

BĂM ĐÓNG

Xóa giá trị 30


• Thêm phần tử vào từ điển
void InsertSet(ElementType X, Dictionary D) {
Position P;
if (FullSet(D))
printf("\nBang bam day\n");
else if (!Member(X,D)){
P = H(X);
int i = 0;
while((ii++;
P=(P+1)%B;
}
D[P]=X;
}
else
printf("\nPhan tu da ton tai");
}

0

20

1

29

2

12


i=1 H(30) = 1

3

30
Deleted

4

34

i=2 H(30)=2

5

E

6

26



E

i=0 H(30) = 0

i=3 H(30)=3

E

B-1

19

3


BĂM ĐÓNG
• Xóa từ ra khỏi từ điển
void DeleteSet(ElementType X,Dictionary D){
int i=0;
Position P = H(X);
while ((ii++;
P=(P+1)%B;
}
if (D[P]==X)
D[P]=Deleted;
}

BĂM MỞ
• Khởi tạo bảng băm mở rỗng
void MakeNullSet(Dictionary *D){
for(int i=0;i(*D)[i]=NULL;
}

BĂM MỞ
• Khai báo
#define B ...

typedef ... ElementType;
typedef struct Node* NodeType;
struct Node {
ElementType Data;
NodeType
Next;
};
typedef Node*
Position;
typedef Position Dictionary[B];

BĂM MỞ
• Kiểm tra một thành viên trong từ điển
int Member(ElementType X, Dictionary D){
Position P;
int Found=0;
P=D[H(X)]; //Tim o muc H(X)
//Duyet tren ds thu H(X)
while((P!=NULL) && (!Found))
if (P->Data==X) Found=1;
else P=P->Next;
return Found;
}

4


BĂM MỞ
• Thêm một phần tử vào từ điển
void InsertSet(ElementType X,Dictionary *D){

if (!Member(X,*D)){
NodeType temp;
temp=(NodeType)malloc(sizeof(struct Node));
temp->Data = X;
temp-> Next = (*D)[H(X)];
(*D)[H(X)] = temp;
}
}

• Xoá một phần tử trong từ điển
void DeleteSet(ElementType X, Dictionary *D) {
Position P, Q;
if((*D)[H(X)]!=NULL) {
if ((*D)[H(X)]->Data==X) {
Q=(*D)[H(X)];
(*D)[H(X)]=(*D)[H(X)]->Next;
free(Q); }
else {
int Found = 0;
P=(*D)[H(X)];
while ((P->Next!=NULL) && (!Found))
if (P->Next->Data==X) Found=1;
else P=P->Next;
if (Found) {
Q=P->Next;
P->Next=Q->Next;
free(Q);
}
}
}

}

Hết chương

5



Tài liệu bạn tìm kiếm đã sẵn sàng tải về

Tải bản đầy đủ ngay
×