CHƯƠNG 3

DANH SÁCH LIÊN KẾT

1

Tài Liệu Tham Khảo

 Bài giảng CTDL, ĐH Công nghệ thông tin TPHCM  Bài giảng CTDL, Khoa Công nghệ thông tin, ĐH

 Nhập môn CTDL, Dương Anh Đức, Trần Hạnh Nhi,

KHTN TPHCM

ĐH KHTN TPHCM

2

Nội dung

 Danh sách liên kết đơn

 Danh sách liên kết kép

 Stack

 Queue

3

Con trỏ

 Kiểu con trỏ dùng lưu địa chỉ của một đối tượng dữ liệu khác.

 Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nó là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL.

 Bản thân biến con trỏ là không động

 Dùng biến con trỏ để lưu giữ điạ chỉ của biến động => truy

xuất biến động thông qua biến con trỏ

4

Con trỏ

5

Con trỏ

6

Con trỏ

7

Con trỏ

8

Kiểu danh sách

 Danh sách = { các phần tử có cùng kiểu}

 Danh sách là một kiểu dữ liệu tuyến tính :

 Mỗi phần tử có nhiều nhất 1 phần tử đứng trước

 Mỗi phần tử có nhiều nhất 1 phần tử đứng sau

 Là kiểu dữ liệu quen thuộc trong thực tế :

 Danh sách học sinh

 Danh mục sách trong thư viện

 Danh bạ điện thoại

 Danh sách các nhân viên trong công ty

9

 …

Các hình thức tổ chức danh sách

 CTDL cho mỗi phần tử ?

 Thể hiện liên kết của các phần tử ?

 Hai hình thức cơ bản :

Mảng

 Liên kết ngầm :

Danh sách liên kết  Liên kết tường minh :

10

Danh sách liên kết ngầm(mảng)

 Mối liên hệ giữa các phần tử được thể hiện ngầm:

 xi : phần tử thứ i trong danh sách  xi , xi+1 là kế cận trong danh sách

 Phải lưu trữ liên tiếp các phần tử trong bộ nhớ  công thức xác định địa chỉ phần tử thứ i:

address(i) = address(1) + (i-1)*sizeof(T)

 Ưu điểm : Truy xuất trực tiếp, nhanh chóng

 Nhược điểm:

x0

…

xi

xi+1

 Sử dụng bộ nhớ kém hiệu quả  Kích thước cố định  Các thao tác thêm vào , loại bỏ không hiệu quả

11

Liên kết tuờng minh(Danh sánh liên kết)

 CTDL cho một phần tử

 Thông tin bản thân  Địa chỉ của phần tử kế trong danh sách

x2

x0

x3

x1

 Mỗi phần tử là một biến động

 Ưu điểm

+ Sử dụng hiệu quả bộ nhớ + Linh động về số lượng phần tử

12

Các loại danh sách liên kết

 Danh sách liên kết đơn: Mỗi phần tử liên kết với phần

tử đứng sau nó trong danh sách

A

B

C

D

 Danh sách liên kết kép: Mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách

A

B

C

D

13

Các loại danh sách liên kết

 Danh sách liên Vòng: Phần tử cuối danh sách liên với

phần tử đầu danh sách

 Danh sách liên kết đơn vòng

A

B

C

D

 Danh sách liên kết đôi vòng

A

B

C

D

14

Cấu tạo nút trên danh sách liên kết

15

Cấu tạo nút trên danh sách liên kết

16

Cấu tạo nút trên danh sách liên kết

17

Cấu tạo nút trên danh sách liên kết

18

Cấu tạo của danh sách liên kết

19

Cấu tạo của danh sách liên kết

20

Cấu tạo của danh sách liên kết

21

Tổ Chức Của DSLK Đơn

x2

x0

x3

x1

 Mỗi phần tử liên kết với phần tử đứng liền sau trong danh

 Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc

sách

có hai thành phần  Thành phần dữ liệu: Lưu trữ thông tin về bản thân

phần tử

 Thành phần liên kết: Lưu địa chỉ phần tử đứng sau

trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách.

22

CTDL của DSLK đơn

 Cấu trúc dữ liệu của 1 nút trong List đơn

typedef { Data struct tagNode Info; // Lưu thông tin bản thân

pNext

struct tagNode *pNext; //Lưu địa chỉ của Node đứng sau

}Node;

Info

 Cấu trúc dữ liệu của DSLK đơn

struct tagList

typedef { Node *pHead;//Lưu địa chỉ Node đầu tiên trong List

// kiểu danh sách liên kết đơn

}LIST;

Node *pTail; //Lưu địa chỉ của Node cuối cùng trong List

23

Ví dụ tổ chức DSLK đơn trong bộ nhớ

pHead

pTail

3f 4

4f 7

5f 6

4f 5f NULL

Trong ví dụ trên thành phần dữ liệu là 1 số nguyên

24

Các thao tác cơ bản trên DSLK đơn

 Tạo 1 danh sách liên kết đơn rỗng

 Tạo 1 nút có trường Infor bằng x

 Tìm một phần tử có Info bằng x

 Thêm một phần tử có khóa x vào danh sách

 Kiểm tra số phần tử của danh sách

 Hủy một phần tử trong danh sách

 Duyệt danh sách

 Sắp xếp danh sách liên kết đơn

25

Khởi tạo danh sách liên kết

 Địa chỉ của nút đầu tiên, địa chỉ của nút cuối

cùng đều không có

{

void CreateList(List &l)

l.pHead=NULL;

l.pTail=NULL;

}

26

Tạo 1 phần tử mới

 Hàm trả về địa chỉ phần tử mới tạo

Node* CreateNode(Data x) // trong bài học là int

{ Node *p;

p = new Node;//Cấp phát vùng nhớ cho phần tử

//gán dữa liệu cho nút

if ( p==NULL) exit(1);

p->pNext = NULL;

p ->Info = x;

return p;

}

27

Thêm 1 phần tử vào DSLK

 Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có

 Các vị trí cần thêm 1 phần tử vào List:

làm cho pHead, pTail thay đổi?

 Thêm vào cuối List

 Thêm vào đầu List đơn

 Thêm vào sau 1 phần tử q trong list

28

Thuật toán thêm 1 phần tử vào đầu DSLK

 Thêm nút p vào đầu danh sách liên kết đơn

Nếu List rỗng thì

Bắt đầu:

+ pHead = p;

+ pTail = pHead;

Ngược lại

+ pHead = p

+ p->pNext = pHead;

29

Minh họa thuật toán thêm vào đầu

pHead

4f

2f 3 3f 3f 4 4f

8 …

9f

10 2fN

pHead=P

P->pNext=pHead

P

30

Hàm thêm 1 phần tử vào đầu List void AddHead(LIST &l, Node* p) {

if (l.pHead==NULL) {

l.pHead = p; l.pTail = l.pHead;

} else {

p->pNext = l.pHead; l.pHead = p;

}

31

}

Thuật toán thêm vào cuối DSLK

 Ta cần thêm nút p vào cuối list đơn

Bắt đầu:

Nếu List rỗng thì

+ pHead = p;

Ngược lại

+ pTail = pHead;

+ pTail->pNext=p;

+ pTail=p

32

Minh họa thuật toán thêm vào cuối

pTail

5f 3f

4 4f

5 N9f

pTail=P

4f 8 5f

pTail->pNext=P

9f

6 N

P

33

Hàm thêm 1 phần tử vào cuối DSLKD

void AddTail(LIST &l, Node *p) {

if (l.pHead==NULL) {

l.pHead = p; l.pTail = l.pHead;

} else {

}

l.pTail->Next = p; l.pTail = p;

}

34

Thuật toán phần tử p vào sau phần tử q

 Ta cần thêm nút p vào sau nút q trong list đơn

Bắt đầu:

B1: p->pNext = q->pNext

Nếu (q!=NULL) thì

B2:

+ q->pNext = p

+ nếu q = pTail thì

pTail=p

35

Minh họa thuật toán

q

4f 3f

5f 5 ..

4 4f

8 5f9f

q->pNext=P

P->pNext=q->pNext

5fN 9f 7

P

36

Cài đặt thuật toán

void InsertAfterQ(List &l, Node *p, Node *q) {

if(q!=NULL) {

p->pNext=q->pNext; q->pNext=p; if(l.pTail==q) l.Tail=p;

AddHead(l,q);// thêm q vào đầu list

} else

}

37

Hủy phần tử trong DSLK đơn

 Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy.

 Các vị trị cần hủy

 Hủy phần tử đứng đầu List

 Hủy phần tử có khoá bằng x

 Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete.

 Huỷ phần tử đứng sau q trong danh sách liên kết đơn

38

Thuật toán hủy phần tử đầu trong DSLK

 Bắt đầu:

 Nếu (pHead!=NULL) thì

 B1: p=pHead

+ pHead = pHead->pNext

 B2:

+ delete (p)

 B3:

Nếu pHead==NULL thì pTail=NULL

39

Cài đặt thuật toán  Hủy được hàm trả về 1, ngược lại hàm trả về 0

int RemoveHead(List &l, int &x) { Node *p;

if(l.pHead!=NULL) p=l.pHead; { x=p->Info; //lưu Data của nút cần hủy l.pHead=l.pHead->pNext; delete p; if(l.pHead==NULL) l.pTail=NULL;

} return 0;

return 1;

40

}

Minh hoạ thuật toán

pHead=pHead->pNext

pHead

2f

3f

4f

2f

6

3f

3

4f

1f 7

…8

P=pHead

P

41

Hủy phần tử sau phần tử q trong List

 Bắt đầu

Nếu (q!=NULL) thì //q tồn tại trong List

 B1: p=q->pNext;// p là phần tử cần hủy

 B2: Nếu (p!=NULL) thì // q không phải là phần tử cuối

+ q->pNext=p->pNext;// tách p ra khỏi xâu

+ nếu (p== pTail) // nút cần hủy là nút cuối

pTail=q;

+ delete p;// hủy p

42

Cài đặt thuật toán int RemoveAfterQ(List &l, Node *q, int &x) { Node *p;

if(q!=NULL) {

p=q->pNext; //p là nút cần xoá if(p!=NULL) // q không phài là nút cuối {

if(p==l.pTail) //nút cần xoá là nút cuối cùng l.pTail=q;// cập nhật lạ pTail q->pNext=p->pNext; x=p->Info; delete p;

} else

} return 1;

43

return 0; }

Minh họa thuật toán

p-=q->pNext

p

q 2f

3f

4f

pHead

3f4f

1f 7

2f

6

3

4f

…8

q->pNext=p->pNext

44

Thuật toán hủy phần tử có khoá x Bước 1:

Tìm phần tử p có khoá bằng x, và q đứng trước p

Nếu (p!=NULL) thì //tìm thấy phần tử có khoá bằng x

Bước 2:

Hủy p ra khỏi List bằng cách hủy phần tử

đứng sau q

Ngược lại

Báo không tìm thấy phần tử có khoá x

45

Cài đặt thuật toán int RemoveX(List &l, int x) { Node *p,*q = NULL; p=l.Head;

while((p!=NULL)&&(p->Info!=x)) //tìm phần tử có khóa x và phần tử q đứng trước nó {

q=p; p=p->pNext;

} if(p==NULL) //không tìm thấy phần tử có khoá bằng x

return 0;

DeleteAfterQ(l,q,x);

if(q!=NULL)//tìm thấy phần tử có khoá bằng x

else //phần tử cần xoá nằm đầu List

RemoveHead(l,x);

46

return 1;}

Tìm 1 phần tử trong DSLK đơn

Tìm tuần tự (hàm trả về), các bước của thuật toán tìm nút có Info bằng x trong list đơn

Bước 2:

Bước 1: p=pHead;// địa chỉ của phần tử đầu trong list đơn

Trong khi p!=NULL và p->Info!=x

p=p->pNext;// xét phần tử kế

Bước 3:

Info = x

+ Nếu p!=NULL thì p lưu địa chỉ của nút có

47

+ Ngược lại : Không có phần tử cần tìm

Hàm tìm 1 phần tử trong DSLK đơn  Hàm tìm phần tử có Info = x, hàm trả về địa chỉ của nút

có Info = x, ngược lại hàm trả về NULL

Node *Search(LIST l, Data x)

Node *p;

{

p = l.pHead;

while((p!= NULL)&&(p->Info != x))

p = p->pNext;

return p;

48

}

Minh họa thuật toán tìm phần tử trong DSLK

4f 5f 2f 3f

pHead

56

1f 34

3

4

8 8

P

X = 8

Tìm thấy, hàm trả về địa chỉ của nút tìm thấy là 4f

49

Duyệt danh sách

Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu cần xử lý các phần tử trong danh sách như:

 Đếm các phần tử trong danh sách

 Tìm tất cả các phần tử trong danh sách thỏa điều kiện

 Hủy toàn bộ danh sách

50

Thuật toán duyệt danh sách

 Bước 1:

p = pHead;// p lưu địa chỉ của phần tử đầu trong List

 Bước 2:

Trong khi (danh sách chưa hết) thực hiện

+ p=p->pNext;// qua phần tử kế

+ xử lý phần tử p

51

Cài đặt in các phần tử trong List

void PrintList(List l)

{

Node *p;

while(p!=NULL)

p=l.pHead;

{ printf(“%d ”, p->Info);

p=p->pNext;

}

}

52

Hủy danh sách liên kết đơn  Bước 1:

Trong khi (danh sách chưa hết) thực hiện

p = pHead;

• B11:

pHead = pHead->pNext;// cập nhật pHead

• B12:

 Bước 2:

Hủy p

pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng

53

Cài đặt thuật toán void RemoveList(List &l)

{

while(l.pHead!=NULL)//còn phần tử trong List

Node *p;

{

p = l.pHead;

l.pHead = p->pNext;

delete p;

}

54

}

Minh họa thuật toán

pTail

pHead

2f

3f

4f

5f

3f

5f N9

2f

6

3

4f

1f 7

8

p

55

Sắp xếp danh sách

 Có hai cách tiếp cận  Cách 1: Thay đổi thành phần Info

pHead

pTail

5f

3f 4

4f

4f 7

5f

6

N

pHead

pTail

5f

3f 4

4f

4f 6

5f 7 N

56

Sắp xếp danh sách

Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn) pHead

pTail

5f

3f 4

4f 6 N

4f 7

5f

pHead

pTail

5f

4f

3f 4

5f 6 4f N7

57

Ưu, nhược điểm của 2 cách tiếp cận

 Thay đổi thành phần Info (dữ liệu)

 Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử ->

chỉ phù hợp với những xâu có kích thước Info nhỏ

 Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị thành

phần Info lớn

Làm cho thao tác sắp xếp chậm

 Thay đổi thành phần pNext

 Ưu:

 Kích thước của trường này không thay đổi, do đó không phụ

thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút.

Thao tác sắp xếp nhanh  Nhược: Cài đặt phức tạp

 Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng  Nhược:

58

Dùng thuật toán SX SelectionSort để SX List void SelectionSort(LIST &l) {

Node *p,*q,*min; p=l.pHead; while(p!=l.pTail) {

min=p; q=p->pNext;

while(q!=NULL) { if(q->InfoInfo) min=q; q=q->pNext; } HV(min->Info,p->Info); p=p->pNext; }

}

59

Các thuật toán sắp xếp hiệu quả trên List

 Các thuật toán sắp xếp xâu (List) bằng các thay đổi

thành phần pNext (thành phần liên kết) có hiệu quả cao như:

 Thuật toán sắp xếp Merge Sort

 Thuật toán sắp xếp Quick Sort

 Thuật toán sắp xếp Radix Sort

60

Thuật toán sắp xếp Quick Sort

 Bước 1:

Chọn X là phần tử đầu xâu L làm phần tử cầm canh

Loại X ra khỏi L

 Bước 2:

Tách xâu L ra làm 2 xâu L1(gồm các phần tử nhỏ hơn hoặc

bằng x) và L2 (gồm các phần tử lớn hơn X)  Bước 3: Nếu (L1 !=NULL) thì QuickSort(L1)  Bước 4: Nếu (L2!=NULL) thì QuickSort(L2)  Bước 5: Nối L1, X, L2 lại theo thứ tự ta có xâu L đã được sắp

xếp

61

Minh họa thuật toán

Cho danh sách liên kết gồm các phần tử sau:

pHead

pTail

4

6

5

1

8

2

4

X =

pTail

pHead

1

2

L1 (X)

pTail

pHead

L2 (>X)

6

5

8

62

Minh họa thuật toán (tt)

pTail

pHead

L2 (>X)

6

5

8

 Sắp xếp L1  Sắp xếp L2

6

 Chọn x=6 cầm canh, và tách L2 thành L21 và L22

X2 =

pTail

pHead

5

L21 (X)

pTail

pHead

L22 (>X)

8

63

Minh họa thuật toán (tt)

 Nối L21, X2, L22 thành L2

pTail

pHead

L2

5

6

8

Nối L1, X, L2 thành L

pHead

pTail

1

2

4

5

6

8

64

Cài đặt thuật toán void QuickSort(List &l) { Node *p,*X;//X lưu địa chỉ của phần tử cầm canh

List l1,l2; if(l.pHead==l.pTail) return;//đã có thứ tự CreateList(l1); CreateList(l2); X=l.pHead; l.pHead=X->pNext; while(l.pHead!=NULL)//tách L = L1 va L2 {

p=l.pHead; l.pHead=p->pNext; p->pNext=NULL; if(p->Info<=X->Info)

AddHead(l1,p);

else

AddHead(l2,p);} 65

Cài đặt thuật toán (tt)

QuickSort(l1);//Gọi đệ quy sắp xếp L1 QuickSort(l2);//Gọi đệ quy sắp xếp L2 if(l1.pHead!=NULL)//nối l1, l2 va X vao l {

l.pHead=l1.pHead; l1.pTail->pNext=X;//nối X vào

} else

l.pHead=X; X->pNext=l2.pHead; if(l2.pHead!=NULL) //l2 có trên một phần tử

l.pTail=l2.pTail; else //l2 không có phần tử nào

l.pTail=X;

66

}

1.

Cài đặt hàm main()  Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó thành phần dữ liệu của mỗi nút là 1 số nguyên dương. Liệt kê tất cả thành phần dữ liệu của tất cả các nút trong xâu

2. Tìm 1 phần tử có khoá bằng x trong xâu. 3. Xoá 1 phần tử đầu xâu 4. Xoá 1 phần tử có khoá bằng x trong xâu

5. 6. Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu

Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info)

vẫn tăng dần theo trường dữ liệu

67

Cài đặt hàm main() (tt)

void main() { LIST l1; Node *p; int x;

printf(“nhap x=”); scanf(“%d”,&x); if(x>0) {

CreateList(l1); do{

p = CreateNode(x); AddHead(l1,x);

} }while(x>0); printf(“Danh sách mới thành lập là\n”); PrintList(l1); printf(“nhập x cần tìm x=”); scanf(“%d”,&x);

68

Cài đặt hàm main() (tt)

p = Search(l1,x);

if(p==NULL) printf(“không tìm thấy”);

else printf(“tìm thấy”);

RemoveHead(l1,x);

PrintList(l1);

printf(“danh sách sau khi xóa\n”);

printf(“nhập khoá cần xoá\n”);

scanf(“%d”,&x);

RemoveX(l1,x);

69

Cài đặt hàm main() (tt)

printf(“danh sách sau khi xoá”);

PrintfList(l1);

SelectionSort(l1);

printf(“Danh sách sau khi sắp xếp”);

PrintfList(l1);

RemoveList(l1);

}

70

Vài ứng dụng danh sách liên kết đơn

 Dùng xâu đơn để lưu trữ danh sách các học viên trong

lớp học

 Dùng xâu đơn để quản lý danh sách nhân viên trong

 Dùng xâu đơn để quản lý danh sách các cuốn sách

một công ty, trong cơ quan

 Dùng xâu đơn để quản lý các băng đĩa trong tiệm cho

trong thư viện

 ..vv

thuê đĩa.

71

Giới thiệu các loại DSLK khác

 Danh sách liên kết kép (Doubly-Linked List)

 Danh sách liên kết vòng (Circular-Linked List)

72

Định Nghĩa

 Mỗi phần tử liên kết với phần tử đứng trước và

sau nó trong danh sách

 Hình vẽ minh họa danh sách liên kết kép:

A

B

C

D

73

Danh sách liên kết kép

 Xaâu ñoâi veà maët cô baûn coù tính chaát gioáng

nhö xaâu ñôn.

 Tuy nhieân noù coù moät soá tính chaát khaùc xaâu

ñôn nhö sau: ◦ Xaâu ñoâi coù moái lieân keát hai chieàu neân töø moät

phaàn töû baát kyø coù theå truy xuaát moät phaàn töû baát kyø khaùc. Trong khi treân xaâu ñôn ta chæ coù theå truy xuaát ñeán caùc phaàn töû ñöùng sau moät phaàn töû cho tröôùc. Ñieàu naøy daãn ñeán vieäc ta coù theå deã daøng huûy phaàn töû cuoái xaâu ñoâi, coøn treân xaâu ñôn thao taùc naøy toàn chi phí O(n).

74

Danh sách liên kết kép

◦ Buø laïi, xaâu ñoâi toán chi phí gaáp ñoâi so vôùi xaâu

ñôn cho vieäc löu tröõ caùc moái lieân keát. Ñieàu naøy khieán vieäc caäp nhaät cuõng naëng neà hôn trong moät soá tröôøng hôïp. Nhö vaäy ta caàn caân nhaéc löïa choïn CTDL hôïp lyù khi caøi ñaët cho moät öùng duïng cuï theå.

75

DSLK kép

76

Cấu Trúc Dữ Liệu  Cấu trúc dữ liệu 1 nút

typedef struct tagDnode { Data Info;

}DNode;

 Cấu trúc List kép

struct tagDnode *pPre; struct tagDnode *pNext;

Typedef struct tagDList { DNode *pHead; DNode *pTail;

}DList;

77

Các Thao Tác Trên List Kép

 Khởi tạo danh sách liên kết kép rỗng  Tạo 1 nút có thành phần dữ liệu = x  Chèn 1 phần tử vào danh sách

 Tìm 1 phần tử trong danh sách  Sắp xếp danh sách

◦ Chèn vào đầu ◦ Chèn sau phần tử Q ◦ Chèn vào trước phần tử Q ◦ Chèn vào cuối danh sách  Huỷ 1 phần tử trong danh sách ◦ Hủy phần tử đầu danh sách ◦ Hủy phần tử cuối danh sách ◦ Hủy 1 phần tử có khoá bằng x

78

Tạo 1 Danh Sách Rỗng

void CreateDList(DList &l) {

l.DHead=NULL; l.DTail=NULL;

}

79

Tạo 1 Nút Có Thành Phần Dữ Liệu = X

DNode *CreateDNode(int x) { DNode *tam;

printf("khong con du bo nho"); exit(1);

tam=new DNode; if(tam==NULL) {

tam->Info=x; tam->pNext=NULL; tam->pPre=NULL; return tam;

} else {

}

80

}

Thêm 1 Nút Vào Đầu Danh Sách

• Minh họa hình vẽ

pHead

A

B

C

D

pTail

X

81

Cài Đặt Thêm 1 Nút Vào Đầu Danh Sách

void AddFirst(DList &l, DNode *tam) {

l.pHead=tam; l.pTail=l.pHead;

if(l.pHead==NULL)//xau rong {

} else {

tam->pNext=l.pHead; l.pHead->pPre=tam; l.pHead=tam;

}

82

}

Thêm Vào Cuối Danh Sách

 Minh họa thêm 1 phần tử vào sau danh sách

pTail

pHead

A

B

C

D

X

83

Cài Đặt Thêm 1 Nút Vào Cuối Danh Sách

if(l.pHead==NULL) {

void AddEnd(DList &l,DNode *tam) {

} else {

tam->pPre=l.pTail; l.pTail->pNext=tam; tam=l.pTail;

l.pHead=tam; l.pTail=l.pHead;

}

84

}

Thêm Vào Sau Nút Q

 Minh họa thêm nút X vào sau nút q

pTail

pHead

q

A

B

C

D

X

85

Cài Đặt Thêm 1 Nút Vào Sau Nút Q void AddLastQ(DList &l,DNode *tam, DNode *q) {

DNode *p; p=q->pNext; if(q!=NULL)//them vao duoc {

tam->pNext=p; tam->pPre=q; q->pNext=tam; if(p!=NULL)

p->pPre=tam;

if(q==l.pTail) //them vao sau danh sach lien ket.

l.pTail=tam;

} else

AddFirst(l,tam);

86

}

Thêm 1 Nút Vào Trước Nút Q

 Minh hoạ thêm 1 nút vào trước nút q

pTail

pHead

q

A

B

C

D

X

87

Cài Đặt Thêm 1 Nút Vào Trước Nút Q

void AddBeforeQ(DList &l,DNode *tam,DNode *q) { DNode *p; p=q->pPre; if(q!=NULL) {

tam->pNext=q; q->pPre=tam; tam->pPre=p; if(p!=NULL)

p->pNext=tam;

if(q==l.pHead)

l.pHead = tam;

} else

AddEnd(l,tam);

88

}

Xoá Phần Tử Đầu Danh Sách

void DeleteFirst(DList &l) {

DNode *p; if(l.pHead!=NULL) {

}

p=l.pHead; l.pHead=l.pHead->pNext; l.pHead->pPre=NULL; delete p; if(l.pHead==NULL) l.pTail=NULL;

}

89

Xoá 1 Phần Tử Cuối Danh Sách

DNode *p; if(l.pHead!=NULL) //tuc xau co hon mot phan tu {

void DeleteEnd(DList &l ) {

p=l.pTail; l.pTail=l.pTail->Pre; l.pTail->pNext=NULL; delete p; if(l.pTail==NULL)

l.pHead=NULL;

}

}

90

Hủy 1 Nút Sau Nút Q

void DeleteLastQ(DList &l,DNode *q) {

DNode *p;//luu node dung sau node q if(q!=NULL) {

p=q->pNext; if(p!=NULL) {

q->pNext=p->pNext; if(p==l.pTail)//xoa dung nu't cuoi

else

l.pTail=q; //Nut xoa khong phai nut cuoi p->pNext->pPre=q;

delete p;

}

} else

DeleteFirst(l);

91

}

Huỷ 1 Nút Đứng Trước Nút Q

void DeleteBeforeQ(DList &l,DNode *q) {

DNode *p; if(q!=NULL) //tuc ton tai node q {

p=q->pPre; if(p!=NULL) {

q->pPre=p->pPre; if(p==l.pHead)//p la Node dau cua danh sach

l.pHead=q; else //p khong phai la node dau

p->pPre->pNext=q;

delete p;

}

} else

DeleteEnd(l);

92

}

Xoá 1 Phần Tử Có Khoá = X

int DeleteX(DList &l,int x) {

DNode *p; DNode *q; q=NULL; p=l.pHead; while(p!=NULL) {

if(p->Info==x) break;

q=p;//q la Node co truong Info = x p=p->pNext;

} if(q==NULL) return 0;//khong tim thay Node nao co truong Info =x if(q!=NULL)

DeleteLastQ(l,q);

else

DeleteFirst(l);

93

return 1;

}

Sắp Xếp

void DoiChoTrucTiep(DList &l) { DNode *p,*q; p=l.pHead; while(p!=l.pTail) {

if(p->Info>q->Info) HV(p,q);

q=p->pNext; while(q!=NULL) {

} p=p->pNext;

q=q->pNext;

94

}}

Danh sách liên kết vòng

 Danh saùch lieân keát voøng (xaâu voøng) laø moät danh saùch ñôn (hoaëc ñoâi) maø phaàn töû cuoái danh saùch thay vì mang giaù trò NULL, troû tôùi phaàn töû ñaàu danh saùch.

 Ñoái vôùi danh saùch voøng, coù theå xuaát phaùt töø moät phaàn töû baát kyø ñeå duyeät toaøn boä danh saùch.

95

Danh sách liên kết vòng

 Ñeå bieåu dieãn, coù theå söû duïng caùc kyõ thuaät bieåu dieãn nhö danh saùch ñôn (hoaëc ñoâi).

Tail

Head

A

B

X

Z

Y

Tail

Head

D

A

B

C

96

Danh sách liên kết vòng Tìm phaàn töû treân danh saùch voøng  Danh saùch voøng khoâng coù phaàn töû ñaàu danh saùch roõ reät, nhöng ta coù theå ñaùnh daáu moät phaàn töû baát kyø treân danh saùch xem nhö phaân töû ñaàu xaâu ñeå kieåm tra vieäc duyeät ñaõ qua heát caùc phaàn töû cuûa danh saùch hay chöa.

97

Danh saùch lieân keát voøng Tìm phaàn töû treân danh saùch voøng NODE* Search(LIST &l, Data x)

{ NODE *p;

p = l.pHead; do { if ( p->Info == x) return p;

p = p->pNext;

} while (p != l.pHead); // chöa ñi giaùp voøng return p;

}

98

Danh saùch lieân keát voøng Theâm phaàn töû ñaàu xaâu

Void AddHead(LIST &l, NODE *new_ele) {

if(l.pHead == NULL) //Xaâu roãng {

l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead;

} else {

new_ele->pNext = l.pHead; l.pTail->pNext = new_ele; l.pHead = new_ele;

}

}

99

AddTail(LIST &l, NODE *new_ele)

Danh saùch lieân keát voøng Theâm phaàn töû cuoái xaâu void {

if(l.pHead == NULL) //Xaâu roãng {

l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead;

} else {

new_ele->pNext = l.pHead; l.pTail->pNext = new_ele; l.pTail = new_ele;

}

100

}

Danh saùch lieân keát voøng Theâm phaàn töû sau nuùt q void AddAfter(LIST &l, NODE *q, NODE *new_ele) {

if(l.pHead == NULL) //Xaâu roãng {

l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead;

} else {

new_ele->pNext = q->pNext; q->pNext = new_ele; if(q == l.pTail)

l.pTail = new_ele;

}

}

101

Danh saùch lieân keát voøng Huûy phaàn töû ñaàu xaâu

void RemoveHead(LIST &l) {

NODE *p = l.pHead; if(p == NULL) return; if (l.pHead = l.pTail) l.pHead = l.pTail = NULL; else {

l.pHead = p->Next; if(p == l.pTail)

l.pTail->pNext = l.pHead;

} delete p;

102

}

Danh saùch lieân keát voøng Huûy phaàn töû ñöùng sau nuùt q

void RemoveAfter(LIST &l, NODE *q) { NODE *p;

if(q != NULL) {

p = q ->Next ; if ( p == q) l.pHead = l.pTail = NULL; else {

q->Next = p->Next; if(p == l.pTail) l.pTail = q;

} delete p;

103

} }

So sánh Mảng và DSLK

104

So sánh DSLK và Mảng

105

So sánh DSLK đơn và kép

106

So sánh DSLK tuyến tính và vòng

107

Các cấu trúc đặc biệt của danh sách đơn

 Stack (ngăn xếp): Là 1 vật chứa các đối tượng làm việc theo cơ chế LIFO (Last In First Out), từ việc thêm 1 đối tượng vào Stack hoặc lấy 1 đối tượng ra khỏi Stack được thực hiện theo cơ chế “vào sau ra trước”

 Queue (hàng đợi): Là 1 vật chứa các đối tượng làm việc theo cơ chế FIFO (First In First Out), tức việc thêm 1 đối tượng vào hàng đợi hay lấy 1 đối tượng ra khỏi hàng đợi thực hiện theo cơ chế “vào trước ra trước”.

108

Ngăn xếp (Stack)

 Một số ví dụ

109

Ngăn xếp (Stack)

110

Định nghĩa

111

Các thao tác trên Stack

 Push(o): Thêm đối tượng o vào Stack

 Pop(): Lấy đối tượng từ Stack

 isEmpty(): Kiểm tra Stack có rỗng hay không

 Top(): Trả về giá trị của phần tử nằm đầu Stack

mà không hủy nó khỏi Stack.

112

Minh họa thao tác Push

113

Minh họa thao tác Pop

114

Minh họa thao tác Stack Top

115

Cài đặt Stack

 Dùng mảng 1 chiều

Data S [N]; int

t;

 Dùng danh sách liên kết đơn S

4

6

5

1

8

2

List S

116

 Thêm và hủy cùng phía

Cài Stack bằng mảng 1 chiều

Cấu trúc dữ liệu của Stack

int a[max]; int t; }Stack;

Khởi tạo Stack:

typedef struct tagStack {

void CreateStack(Stack &s) {

s.t=-1;

}

117

Kiểm tra tính rỗng và đầy của Stack

if(s.t==-1)

int IsEmpty(Stack s)//Stack có rỗng hay không {

return 1;

else

} int IsFull(Stack s) //Kiểm tra Stack có đầy hay không {

if(s.t>=max) return 1;

return 0;

else

return 0;}

118

Thêm 1 phần tử vào Stack

int Push(Stack &s, int x) {

if(IsFull(s)==0) {

s.t++; s.a[s.t]=x; return 1;

} else

return 0;

}

119

Lấy 1 phần tử từ Stack

int Pop(Stack &s, int &x) {

if(IsEmpty(s)==0) {

x=s.a[s.t]; s.t--; return 1;

} else

return 0;

120

}

Stack (hàm main)

void main() {

Stack s; int x, tv,i; CreateStack(s); for(i=2;i<=5;i++)

Push(s,i);

tv=Pop(s,x); if(tv==1) printf(“gia tri lay duoc tu Stack

%d”, x);

}

121

Cài Stack bằng danh sách liên kết

 Kiểm tra tính rỗng của Stack

int IsEmpty(List &s) {

if(s.pHead==NULL)//Stack rong

return 1;

else

return 0;

}

122

Thêm 1 phần tử vào Stack

void Push(List &s, Node *Tam) {

if(s.pHead==NULL) {

s.pHead=Tam; s.pTail=Tam;

} else {

Tam->pNext=s.pHead; s.pHead=Tam;

}

}

123

Lấy 1 phần tử từ Stack

int Pop(List &s,int &trave) { Node *p;

if(IsEmpty(s)!=1) {

p=s.pHead; trave=p->Info; s.pHead=s.pHead->Next; if(s.pHead==NULL)

s.pTail=NULL;

delete p; return 1;

} return 0;

124

}

Stack (hàm main)

void main() {

Stack s; int tv,i; Node *p; CreateStack(s); for(i=2;i<=5;i++) {

p=CreateNode(i); Push(s,p);

} tv=Pop(s,x); if(tv==1)

printf(“gia tri lay duoc tu Stack %d”, x);

}

125

Ứng dụng của Stack

126

ÖÙng duïng cuûa Stack

 Stack thích hôïp löu tröõ caùc loaïi döõ lieäu maø trình töï truy xuaát ngöôïc vôùi trình töï löu tröõ

 Moät soá öùng duïng cuûa Stack:

◦ Trong trình bieân dòch (thoâng dòch), khi thöïc hieän

◦ Löu döõ lieäu khi giaûi moät soá baøi toaùn cuûa lyù thuyeát

caùc thuû tuïc, Stack ñöôïc söû duïng ñeå löu moâi tröôøng cuûa caùc thuû tuïc.

ñoà thò (nhö tìm ñöôøng ñi)

◦ Khöû ñeä qui ◦ ...

127

ÖÙng duïng cuûa Stack

Ví du:ï thuû tuïc Quick_Sort duøng Stack ñeå khöû ñeä qui:  1. l:=1; r:=n;  2. Choïn phaàn töû giöõa x:=a[(l+r) div 2];  3. Phaân hoaïch (l,r) thaønh (l1,r1) vaø (l2,r2) baèng caùch

xeùt: ◦ y thuoäc (l1,r1) neáu yx; ◦ y thuoäc (l2,r2) ngöôïc laïi;

128

ÖÙng duïng cuûa Stack

 4. Neáu phaân hoaïch (l2,r2) coù nhieàu hôn 1 phaàn töû thöïc

 l=l1;  r=r1;  Goto 2; ◦ Ngöôïc laïi

 Laáy (l,r) ra khoûi Stack neáu Stack khaùc roãng vaø Goto 2;  Neáu khoâng döøng;

hieän: ◦ Caát (l2,r2) vaøo Stack; ◦ Neáu (l1,r1) coù nhieàu hôn 1 phaàn töû thöïc hieän:

129

Đổi cơ số (10 sang x)

 57 = ???2

130

16/03/2015 Nhập môn CTDL và Thuật toán

130

Đổi cơ số

2

57 = 1110012

57 1 28 2

0 14 2

0 7 2

1 3 2

1 1 2

1 0

131

16/03/2015 Nhập môn CTDL và Thuật toán

131

Đổi cơ số void main() {

stack s; int coso, so, sodu; init(s); while (so != 0)

{

sodu = so % coso; push(s, sodu); // push so du vao stack so = so / coso;

} printf(“Kết quả: "); while(!empty(s))

cout<

}

132

16/03/2015 Nhập môn CTDL và Thuật toán

132

Thuật toán Ba Lan ngược (Reverse Polish Notation - RPN)

 Định nghĩa RPN : Biểu thức toán học trong đó các toán tử được viết sau toán hạng và không dùng dấu ngoặc

Phát minh bởi Jan Lukasiewics một nhà khoa học Ba Lan vào nhưng năm 1950

133

16/03/2015 Nhập môn CTDL và Thuật toán

133

RPN :

toán tử viết giữa toán hạng toán tử viết sau toán hạng toán tử viết trước toán hạng Infix Postfix (RPN): : Prefix

RPN (POSTFIX)

PREFIX + A B

Examples: INFIX A + B A * B + C A * (B + C) A - (B - (C - D)) A - B - C - D

A B + A B * C + A B C + * A B C D - - - A B - C - D -

+ * A B C * A + B C - A - B - C D - - - A B C D

134

16/03/2015 Nhập môn CTDL và Thuật toán

134

Thuật toán tính giá trị 1. Khởi tạo Stack rỗng (chứa hằng hoặc biến). 2. Lặp cho đến khi kết thúc biểu thức:

Đọc 01 phần tử của biếu thức (hằng, biến, phép toán). Nếu phần tử là hằng hay biến: đưa vào Stack. Ngược lại:

Lấy ra 02 phần tử của Stack. Áp dụng phép toán cho 02 phần tử vừa lấy ra. Đưa kết quả vào Stack. 3. Giá trị của biểu thức chính là phần tử cuối cùng của Stack.

135

16/03/2015 Nhập môn CTDL và Thuật toán

135

Example: 2 3 4 + 5 6 - - *

2*((3+4)-(5-6))

4 3 2

Push 2 Push 3 Push 4 Read +

Pop 4, Pop 3,

3 + 4 = 7

6 5 7 2

Push 7 Push 5 Push 6 Read -

Pop 6, Pop 5,

5 - 6 = -1

Push -1 Read -

-1 7 2

Pop -1, Pop 7,

7 - -1 = 8

Push 8 Read *

8 2

2 * 8 = 16

Pop 8, Pop 2,

16

Push 16

136

16/03/2015 Nhập môn CTDL và Thuật toán

136

Chuyển infix thành postfix

1. Khởi tạo Stack rỗng (chứa các phép toán). 2. Lặp cho đến khi kết thúc biểu thức:

Đọc 01 phần tử của biếu thức

(01 phần tử có thể là hằng, biến,phép toán, “)” hay “(” ).

Nếu phần tử là: 2.1 “(”: đưa vào Stack. 2.2 “)”: lấy các phần tử của Stack ra

cho đến khi gặp “(” trong Stack.

137

16/03/2015 Nhập môn CTDL và Thuật toán

137

Chuyển infix thành postfix 2.3 Một phép toán: + - * /

Nếu Stack rỗng: đưa vào Stack. Nếu Stack khác rỗng và phép toán có độ ưu tiên cao hơn phần

tử ở đầu Stack: đưa vào Stack. Nếu Stack khác rỗng và phép

toán có độ ưu tiên thấp hơn hoặc bằng phần tử ở đầu Stack:

- lấy phần tử từ Stack ra; - sau đó lặp lại việc so sánh với phần tử ở đầu Stack.

138

16/03/2015 Nhập môn CTDL và Thuật toán

138

Chuyển infix thành postfix

2.4 Hằng hoặc biến: đưa vào kết quả. 3. Lấy hết tất cả các phần tử của Stack ra.

139

16/03/2015 Nhập môn CTDL và Thuật toán

139

Độ ưu tiên

 + , _  *, /  ^

1 2 3

140

16/03/2015 Nhập môn CTDL và Thuật toán

140

(A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F))

Output A

AB

* + (

ABC

Example: Push ( Display A Push + Display B Push * Display C Read )

+ (

(

Pop *, Display *, Pop +, Display +, Pop (

ABC* ABC*+

ABC*+D

ABC*+DE

- ( - ( /

ABC*+DEF

Push / Push ( Display D Push - Push ( Display E Push - Display F Read )

Pop -, Display -, Pop (

ABC*+DEF-

Read )

- ( /

Pop -, Display -, Pop (

/

Pop /, Display /

ABC*+DEF-- ABC*+DEF--/

141

16/03/2015 Nhập môn CTDL và Thuật toán

141

Hàng đợi (Queue)

142

Các thao tác trên Queue

 EnQueue(O): Thêm đối tượng O vào cuối

hàng đợi.

 DeQueue(): Lấy đối tượng ở đầu hàng đợi  isEmpty(): Kiểm tra xem hàng đợi có rỗng hay

không?

 Front(): Trả về giá trị của phần tử nằm đầu

hàng đợi mà không hủy nó.

143

Các thao tác trên Queue

144

Thao tác EnQueue

145

Thao tác DeQueue

146

Thao tác QueueFront

147

Thao tác QueueRear

148

Cài đặt hàng đợi

149

Cài đặt hàng đợi bằng con trỏ

150

Cài đặt hàng đợi bằng mảng

151

Cài đặt hàng đợi bằng mảng

152

Cài đặt Queue

• Dùng mảng 1 chiều

Data S [N]; int

f,r;

• Dùng danh sách liên kết đơn

4

6

5

1

8

2

List Q

pHead

pTail

153

* Thêm và hủy Khác phía

Cài đặt Queue bằng mảng 1 chiều  Cấu trúc dữ liệu:

typedef struct tagQueue {

int a[max]; int Front; //chỉ số của phần tử đầu trong Queue int Rear; //chỉ số của phần tử cuối trong Queue

 Khởi tạo Queue rỗng

}Queue;

void CreateQueue(Queue &q) { q.Front=-1; q.Rear=-1;}

154

Lấy 1 phần tử từ Queue int DeQueue(Queue &q,int &x) {

//queue khong rong

if(q.Front!=-1) {

x=q.a[q.Front]; q.Front++; if(q.Front>q.Rear)//truong hop co mot phan tu {

q.Front=-1; q.Rear=-1;

} return 1;

} else //queue trong {

printf("Queue rong"); return 0;

155

}}

Thêm 1 phần tử vào Queue

int EnQueue(Queue &q,int x) { int i;

int f,r; if(q.Rear-q.Front+1==max)//queue bi day khong the them vao duoc nua

return 0;

else {

q.Front=0; q.Rear=-1;

if(q.Front==-1) {

156

}

Thêm 1 phần tử vào Queue (tt)

f=q.Front; r=q.Rear; for(i=f;i<=r;i++)

if(q.Rear==max-1)//Queue đầy ảo {

q.Front=0; q.Rear=r-f;

q.a[i-f]=q.a[i];

} q.Rear++; q.a[q.Rear] = x; return 1;

}

157

}

Queue (hàm main()) void main() {

Queue q; int tv,i,x; CreateQueue(q); for(i=2;i<=5;i++)

EnQueue(q,i);

tv=DeQueue(q,x); if(tv==1)

printf(“gia tri lay duoc tu Stack

%d”,x);

158

}

Cài đặt Queue bằng List

 Kiểm tra Queue có rỗng?

int IsEmpty(List &Q) {

if(Q.pHead==NULL)//Queue rỗng

return 1;

else

return 0;

}

159

Thêm 1 phần tử vào Queue

void EnQueue(List &Q, Node *Tam) {

if(Q.pHead==NULL) {

} else {

Q.pHead=Tam; Q.pTail=Tam;

Q.pTail->Next=tam; Q.pTail=tam;

}

}

160

Lấy 1 phần tử từ Queue

int DeQueue(List &Q,int &X) { Node *p;

if(IsEmpty(Q)!=1) {

p=Q.pHead; X=p->Info; Q.pHead=Q.pHead->Next; if(Q.pHead==NULL) Q.pTail=NULL;

delete p; return 1;

} return 0;

161

}

Queue (hàm main())

void main() {

Queue q; int tv,i; Node *p; CreateQueue(q); for(i=2;i<=5;i++) {

} tv=DeQueue(q,x); if(tv==1)

printf(“gia tri lay duoc tu Queue %d”, x);

p=CreateNode(i); EnQueue(q,p);

}

162

Ứng dụng của hàng đợi

163

Ứng dụng của hàng đợi

 Haøng ñôïi coù theå ñöôïc söû duïng trong moät soá

baøi toaùn: ◦ Baøi toaùn ‘saûn xuaát vaø tieâu thuï’ (öùng duïng trong caùc

heä ñieàu haønh song song).

◦ Boä ñeäm (ví duï: Nhaán phím  Boä ñeäm  CPU xöû

lyù).

◦ Xöû lyù caùc leänh trong maùy tính (öùng duïng trong

HÑH, trình bieân dòch), haøng ñôïi caùc tieán trình chôø ñöôïc xöû lyù, ….

164