Bài giảng Cấu trúc dữ liệu chương 3: ThS. Võ Quang Hoàng Khang

CHƯƠNG 3. DANH SÁCH LIÊN KẾT

Võ Quang Hoàng Khang Email: vqhkhang@gmail.com

Mục tiêu

 Nắm vững khái niệm về kiểu dữ liệu tĩnh

và động

 Nắm vững cách tổ chức dữ liệu động bằng

danh sách liên kết và minh họa được các

thao tác xử lý trên danh sách liên kết đơn

 Cài đặt minh họa được các thao tác của

danh sách đơn bằng ngôn ngữ C/ C++

2

Vấn đề kiểu dữ liệu tĩnh

6

15

10

9

7

5

3

4 1 2 3 5

2 6

1 8

? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng

3

Vấn đề kiểu dữ liệu tĩnh

6

Giả sử cần thêm tiếp 1 phần tử

?

15

10

9

7

5

3

1 2 3 4 5

2 6

1 8

4

Bổ sung thêm

Bài tập

Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theo mẫu hàm như sau:

void ChenX(int a[], int &n, int x, int vt);

5

Vấn đề kiểu dữ liệu tĩnh

15

10

9

7

5

3

1 2 3 4 5

2 6

1 8

? Làm sao để xóa phần tử 9

6

Vấn đề kiểu dữ liệu tĩnh

15

10

9

7

5

3

1 2 3 4 5

2 6

1 8

7

Bài tập

Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau:

void XoaX (int a[], int &n, int x);

8

Vấn đề kiểu dữ liệu tĩnh

Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n)

i

9

Vấn đề kiểu dữ liệu tĩnh  Giải quyết vấn đề phức tạp khi chèn/ xóa?  Giải quyết vấn đề giới hạn kích thước vùng

nhớ tối đa?

 Giải quyết vấn đề vùng nhớ không liên tục?  Giải quyết vấn đề giải phóng vùng nhớ khi

không cần dùng đến?

DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG

10

Biến tĩnh và biến động trong C++

 Biến tĩnh

tên biến;

 Vd: int a; float y; char s[20];  Tồn tại trong phạm vi khai báo  Được cấp phát vùng nhớ trong vùng dữ liệu  Kích thước cố định

11

Biến tĩnh và biến động trong C++

 Biến động

*tên biến;

 Vd: int *a; float *y;

 Chứa địa chỉ của một đối tượng dữ liệu  Được cấp phát hoặc giải phóng bộ nhớ tùy

thuộc vào người lập trình  Kích thước có thể thay đổi

12

Biến tĩnh và biến động trong C++

 Biến động

 Cấp phát bộ nhớ: new int [kích thước]  Giải phóng bộ nhớ: delete vùng nhớ

 Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng

13

Danh sách liên kết (DSLK)

Các phần tử kết dính với nhau bằng “sợi dây liên kết”

7 2 6

14

3 10 8 5 9 4

Để đơn giản hơn trong việc minh họa

7 2 6

3 10 8 5 9 4

15

Đặc điểm DSLK

Một dãy tuần tự các nút (Node) Giữa hai nút có con trỏ liên kết Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)

16

Đặc điểm DSLK

Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết Quản lý phần tử đầu tiên bằng con trỏ pHead Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết

17

Cấu tạo của DSLK

Node

List

pHead

pTail

18

Cấu tạo của DSLK

Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail) pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi

19

Cấu tạo của nút

Tạo lập bằng cách cấp phát bộ nhớ động Mỗi nút có 2 thông tin:

Dữ liệu (data) Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)

Nếu không trỏ đến phần tử nào thì con trỏ Next = NULL

20

Thao tác chèn thêm node vào DSLK

“Kết nối” lại sợi dây liên kết theo trình tự

List

pHead

pTail

21

Thao tác xóa node khỏi DSLK

Cần xóa

List

pHead

pTail

22

Các loại DSLK

DSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới”

A

B

X

Z

Y

23

Các loại hình DSLK

DSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui”

D

A

B

C

24

Các loại hình DSLK

Danh sách liên kết vòng: Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách

A

B

X

Z

Y

A

B

C

D

25

So sánh Mảng và DSLK

Mảng

Kích thước cố định

Danh sách liên kết Số phần tử thay đổi tùy ý

Các phần tử liên kết với nhau bằng con trỏ

Các phần tử lưu trữ tuần tăng dần) tự (địa chỉ trong bộ nhớ

Phải dịch chuyển các phần tử khi Thêm/Xóa Truy xuất ngẫu nhiên

Chỉ cần thay đổi con trỏ liên kết khi Thêm/Xóa Truy xuất tuần tự

DSLK đơn

pNext

Data

Cấu trúc 1 node

List

pHead

pTail

Data : Dữ liệu của node pNext : Con trỏ đến node kế tiếp pHead: Con trỏ đến node đầu pTail: Con trỏ đến node cuối

Khai báo cấu trúc node

pNext

Data

Data; struct tNODE *pNext;

struct tNODE {

}; typedef struct tNODE NODE;

Khai báo cấu trúc node lưu số nguyên

pNext

20

struct tNODE {

int Data; struct tNODE *pNext;

}; typedef struct tNODE NODE;

Khai báo cấu trúc node lưu thông tin SV

pNext

ID, hoten, dtb

struct tSinhVien {

}; typedef struct tSinhVien SINHVIEN;

char ID[10], hoten[30]; float dtb;

struct tNODE {

SINHVIEN Data; struct tNODE *pNext;

}; typedef struct tNODE NODE;

Khai báo cấu trúc DSLK đơn

List

pHead

pTail

struct tList {

NODE *pHead, *pTail;

}; typedef struct tList LIST;

Khai báo cấu trúc DSLK đơn

list

pHead

pTail

struct tList {

NODE *pHead, *pTail;

struct tNODE {

}; typedef struct tList LIST;

int Data; struct tNODE *pNext;

}; typedef struct tNODE NODE;

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

 Thêm 1 nút vào danh sách: đầu, cuối, sau ptử q  Duyệt danh sách  Xóa 1 nút: đầu, cuối, nút có giá trị x  Tìm 1 phần tử  Sắp xếp danh sách

33 Khai báo thư viện hàm

h n

1

ì r t

Khai báo cấu trúc danh sách liên kết

2

Khai báo các nguyên mẫu hàm

3

g n ơ ư h c t

4

á u q g n ổ

void main() {

t c ú r t

Tạo lập danh sách rỗng Nhập dữ liệu vào danh sách Các thao tác xử lý trên danh sách Hủy danh sách

}

34 Cài đặt các hàm con

5

u ấ C

Tạo lập danh sách rỗng pHead và pTail chưa xác định

pHead và pTail trỏ vào NULL (rỗng)

List

? pHead

? pTail

Trước khi tạo lập

pTail pHead Sau khi tạo lập

void CreateEmptyList(LIST &L) {

L.pHead = L.pTail = NULL;

}

35

Kiểm tra danh sách rỗng

List

pHead

pTail

Danh sách rỗng

bool IsEmptyList(LIST L) {

return ((L.pHead==NULL) && (L.pTail==NULL));

}

36

Thêm một nút vào danh sách

TH danh sách rỗng

list.pHead = pNew

30 list

pHead

pTail

pNew

if(IsEmptyList(list)) {

list.pHead = list.pTail = pNew;

}

list.pTail = pNew

37

Thêm một nút vào danh sách

TH danh sách đã có phần tử

30

25 list

pHead

pTail

pNew

Có 2 trường hợp để thêm pNew 1.Thêm pNew vào đầu (AddHead) 2.Thêm pNew vào cuối (AddTail)

38

TH Thêm một nút vào đầu danh sách

1

30 25

list

pHead

pTail

pNew

39

TH Thêm một nút vào đầu danh sách

30 25

list

pHead

pTail

Vẽ lại

25 30

list

pHead

pTail

40

TH Thêm một nút vào đầu danh sách

Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew

?

vào đầu danh sách

25 30 42

list

pHead

pTail

pNew

41

TH Thêm một nút vào đầu danh sách

1

pNew->pNext = list.pHead

2

list.pHead = pNew

42

TH Thêm một nút vào đầu danh sách

?

Hãy viết hàm thêm phần tử pNew vào đầu danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void AddHead(LIST &L, NODE *pNew)

43

TH Thêm một nút vào cuối danh sách

30 25

1 list

pHead

pTail

pNew

list.pTail->pNext = pNew

list.pTail = pNew

44

TH Thêm một nút vào cuối danh sách

?

Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào cuối danh sách

30 25 42

list

pHead

pTail

pNew

45

TH Thêm một nút vào cuối danh sách

?

Hãy viết hàm thêm phần tử pNew vào cuối danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void AddTail (LIST &list, NODE *pNew)

46

Nhập dữ liệu vào danh sách

Nhập dữ liệu cho node

Tạo con trỏ node

Thêm node vào danh sách

47

Nhập dữ liệu vào danh sách

Để tạo node mới từ dữ liệu x có sẵn Đưa dữ liệu có giá trị x vào phần Data Con trỏ pNext trỏ đến NULL

pNew->Data = x

Data

x

pNew->pNext = NULL

pNew

48

Nhập dữ liệu vào danh sách VD hàm tạo và trả về con trỏ node có chứa giá trị nguyên x bằng ngôn ngữ C++ NODE *CreateNode (int x) {

NODE *p; p = new NODE; if(p == NULL) {

cout<<“Loi cap phat duoc vung nho!"; exit(0);

} p->Data = x; p->pNext=NULL; return p;

49

}

Nhập dữ liệu vào danh sách VD hàm nhập dữ liệu cho danh sách số nguyên và đưa vào đầu danh sách void Input(LIST &list) {

int x; NODE *pNew; CreateEmptyList(list); do{

cout<<"Nhap gia tri (Nhap 0 ket thuc): "; cin>>x; if(x==0)

break; pNew=CreateNode(x); AddHead(list, pNew);

}while(true);

50

}

Xuất dslk

p

List

pHead

pTail

51

Chèn node vào DSLK đơn

pNew

Chèn vào sau node p Chèn vào trước node p p

list

52 pHead

pTail

Chèn node vào sau node p

pNew

p

list

53 pHead

pTail

Các thao tác trên DSLK (tt)

 …

 Xóa phần tử trong danh sách (đầu, cuối, giữa)

 Sắp xếp danh sách

Chèn node vào trước node p – Cách 1

pNew

p

pPrev

list

55 pHead

pTail

Chèn node vào trước node p – Cách 1

?

Hãy viết hàm tìm và trả về con trỏ node đứng trước con trỏ node p (bằng ngôn ngữ C/C++), theo mẫu sau: NODE *PrevNode (LIST list, NODE *p)

56

Chèn node vào trước node p – Cách 2 Bước 1. Chèn pNew vào sau q Bước 2. Hoán vị giá trị pNew và q

pNew

q

list

57 pHead

pTail

Xóa một nút trong danh sách

Xóa nút đầu của danh sách  Ảnh hưởng

pHead

Xóa nút cuối của danh sách  Ảnh hưởng

pTail

Xóa nút giữa danh sách

58

Xóa một nút trong danh sách

Xóa nút đầu của danh sách

Cần xóa

30

25

41

78 list

pHead

pTail

pDel

59

NODE *pDel = list.pHead list.pHead = list.pHead->pNext delete pDel

Xóa một nút trong danh sách

Hãy viết hàm xóa nút đầu của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau:

?

void DeleteHead (LIST &list)

(lưu ý trường hợp danh sách chỉ còn 1 node

trước khi xóa)

60

Xóa một nút trong danh sách

Cần xóa

Xóa nút cuối của danh sách

pPrev

pDel

30 25 41 78

list

pHead

pTail

61

NODE *pDel = list.pTail NODE *pPrev = “Tìm node trước pTail” pPrev->pNext = NULL list.pTail = pPrev delete pDel

Xóa một nút trong danh sách

Hãy viết hàm xóa nút cuối của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau:

?

void DeleteTail (LIST &list)

(lưu ý trường hợp danh sách chỉ còn 1 node

trước khi xóa)

62

Xóa một nút trong danh sách

Xóa nút giữa của danh sách

Cần xóa

pDel

pPrev

30 25 41 96 78

list

pHead

pTail

63

NODE *pPrev = “Tìm node trước pDel” pPrev->pNext = pDel->pNext delete pDel

Xóa một nút trong danh sách

?

Hãy viết hàm xóa một node bất kỳ trong danh sách (bằng ngôn ngữ C/C++), theo mẫu sau:

void DeleteNode (LIST &L, NODE *pDel)

64

Xóa một nút trong danh sách

?

Hãy viết hàm hủy toàn bộ danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void DestroyList (LIST &list)

65

Bài tập

Cài đặt các hàm sau trên dslk đơn số nguyên: 1. Đếm số lượng node trong dslk int DemSL(LIST list); 2. Tìm node có giá trị lớn nhất

NODE* TimMax(LIST list);

3. Tìm node có giá trị x

NODE* TimX(LIST list, int x);

4. In những node có giá trị chẵn void InChan(LIST list);

5. Tính giá trị trung bình các node lẻ

66

float TBLe(LIST list);

6. Chèn node có giá trị x vào phía sau node có giá trị lớn nhất

void ChenXSauMax(LIST &list, int x);

7. Xóa node có giá trị x

bool XoaX(LIST &list, int x);

8. Sắp tăng dslk

void SapTang(LIST &list);

67

Sắp xếp

void Doichotructiep ( LIST &L ) {

Node *p,*q; for (p=L.DAU ; p!=L.CUOI ; p=p->tiep ) for (q=p->tiep; q!=NULL ; q=q->tiep) if ( p->dulieu > q->dulieu)

Hoanvi( p->dulieu , q->dulieu );

}

Bài giảng Cấu trúc dữ liệu: Chương 3 - ThS. Võ Quang Hoàng Khang

Chủ đề:

Cấu trúc dữ liệu