DANH SÁCH LIÊN KẾT

G V : L Ê T H Ị N G Ọ C H Ạ N H

1

9/10/2015 Data structure & Algorithms

NỘI DUNG

 Cấp phát động và cấp phát tĩnh  Con trỏ và cấp phát động  Danh sách liên kết

9/10/2015 Data structure & Algorithms 2

BIẾN TĨNH

 Được khai báo tường minh  Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này.  Được cấp phát vùng nhớ trong vùng dữ liệu

(data segment) hoặc là Stack.

 Kích thước không thay đổi trong suốt quá trình

sống.

9/10/2015 Data structure & Algorithms 3

BIẾN ĐỘNG

 Không được khai báo tường minh  Có thể được cấp phát hoặc giải phóng bộ nhớ

khi người sử dụng yêu cầu.

 Các biến này không theo quy tắc phạm vi (tĩnh)  Vùng nhớ của biến được cấp phát trong Heap.  Kích thước có thể thay đổi trong quá trình sống

9/10/2015 Data structure & Algorithms 4

CON TRỎ VÀ CẤP PHÁT ĐỘNG

9/10/2015 Data structure & Algorithms 5

CON TRỎ VÀ CẤP PHÁT ĐỘNG

9/10/2015 Data structure & Algorithms 6

CON TRỎ VÀ CẤP PHÁT ĐỘNG

9/10/2015 Data structure & Algorithms 7

DANH SÁCH LIÊN KẾT (LINKED LIST)

 Mảng là một hình thức liên kết ngầm  Các phần tử trong mảng được cấp phát vùng nhớ một cách liên tiếp nhau  Với T là kiểu dữ liệu cho trước, xét mảng các phần tử kiểu T. Ta có:

Address(i)=Address(0)+(i-1)*sizeof(T)

9/10/2015 Data structure & Algorithms 8

DANH SÁCH LIÊN KẾT

 Một số loại danh sách liên kết (DSLK):

• Danh sách liên kết đơn • Danh sách liên kết kép • Danh sách liên kết vòng • …..

9/10/2015 Data structure & Algorithms 9

DANH SÁCH LIÊN KẾT

9/10/2015 Data structure & Algorithms 10

DANH SÁCH LIÊN KẾT

 Mỗi phần tử của danh sách đơn là một cấu trúc

chứa 2 thành phần chính:

- data: lưu trữ các thông tin về bản thân phần tử. - link: lưu trữ địa chỉ của phần tử kế tiếp trong

danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh sách.

 Con trỏ Head: dùng để lưu trữ địa chỉ phần tử

đầu ds, nên ta gọi Head là đầu xâu(ds).  Con trỏ Tail: giữ địa chỉ phần tử cuối xâu.

Data structure & Algorithms 9/10/2015 11

DANH SÁCH LIÊN KẾT

9/10/2015 Data structure & Algorithms 12

DANH SÁCH LIÊN KẾT

9/10/2015 Data structure & Algorithms 13

KHAI BÁO DSLK

int data; NODE* next;

NODE* pHead; NODE* pTail;

typedef struct NODE { }NODE; typedef struct LIST { }LIST;

9/10/2015 Data structure & Algorithms 14

CÁC THAO TÁC TRÊN DSLK

 Khai báo danh sách  Tạo một phần tử cho danh sách  Chèn một phần tử vào danh sách  Tìm một phần tử trong danh sách đơn  Huỷ một phần tử khỏi danh sách  Duyệt danh sách  Sắp xếp danh sách

9/10/2015 Data structure & Algorithms 15

TẠO PHẦN TỬ TRONG DSLK

void Initial(LinkList &l) { l.head = l.tail = NULL; }

9/10/2015 Data structure & Algorithms 16

THÊM 1 NÚT VÀO ĐẦU DSLK

9/10/2015 Data structure & Algorithms 17

THÊM 1 NÚT VÀO CUỐI DSLK

9/10/2015 Data structure & Algorithms 18

THÊM 1 NÚT VÀO SAU 1 NÚT

9/10/2015 Data structure & Algorithms 19

THÊM 1 NÚT VÀO TRƯỚC 1 NÚT

9/10/2015 Data structure & Algorithms 20

HỦY 1 NÚT ĐẦU DSLK

 Danh sách rỗng: không làm gì cả  Danh sách không rỗng (nếu sau khi hủy mà pHead = NULL thì pTail = NULL)

9/10/2015 Data structure & Algorithms 21

HỦY 1 NÚT SAU 1 NÚT

 q == NULL: hủy nút đầu danh sách  q != NULL

9/10/2015 Data structure & Algorithms 22