Cấu Trúc Dữ Liệu Và Giải Thuật Chapter 3.2Singlelist

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 (867.37 KB, 65 trang )

Phần 2: Danh sách liên kết

1

Danh sách liên kết
DSLK là cấu trúc dữ liệu động.

Các phần tử trong danh sách (node) nằm rải
rác trong bộ nhớ.
Cấu trúc mỗi node:
 Vùng dữ liệu.
 Vùng liên kết (chứa địa chỉ node kế tiếp hoặc
node liền trước).

Thao tác thêm/xóa nút chỉ cần điều chỉnh lại
các liên kết.
2

Danh sách liên kết (List)
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

X

Z

Y

Danh sách liên kết đôi: mỗi phần tử liên kết
với các phần tử đứng trước và sau nó trong
danh sách:
A

B

C

3

D

Danh sách liên kết (List)
Danh sách liên kết vòng : phần tử cuối danh
sách liên kết với phần tử đầu danh sách:

A

B

A

X

B

Z

C

4

Y

D

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

5

Mục tiêu
 Khái niệm DSLK đơn.

 Biểu diễn, quản lý DSLK đơn.
 Các thao tác trên DSLK đơn.

 Sao chép DSLK đơn.
 Sắp xếp trên DSLK đơn.

6

1. Khái niệm
DSLK đơn là chuỗi các node (nút), được tổ

chức theo thứ tự tuyến tính
Mỗi node gồm 2 phần:
 Phần Data: Lưu trữ dữ liệu.
 Phần liên kết: 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 cùng trong danh sách.
Data

Next

Node
7

2. Biểu diễn nút trong DSLK đơn

DataType ?

struct Node
{
DataType
data;
struct node *Next;
};

struct Node
{
int
data;
Node *Next;

};

Cấu trúc
node

typedef struct Node
{
SinhVien data;
struct node *Next;
};
8

3. Biểu diễn, quản lý DSLK đơn
Để quản lý một DSLK đơn chỉ cần biết địa chỉ
phần tử đầu danh sách.
Con trỏ pHead sẽ được dùng để lưu trữ địa chỉ
phần tử đầu danh sách:
NODE* pHead;
Để tiện lợi, có thể sử dụng thêm một con trỏ
pTail lưu địa chỉ phần tử cuối danh sách:
NODE* pTail;
pTail
pHead
A

B

X
9

Z

Y

4. Các thao tác trên DSLK đơn
Khởi tạo danh sách

Thêm một phần tử vào danh sách
Tìm kiếm một giá trị trên danh sách

Trích một phần tử ra khỏi danh sách
Duyệt danh sách
Hủy toàn bộ danh sách

10

4.1. Khởi tạo danh sách
Là thao tác gán giá trị con trỏ quản lý địa chỉ đầu
và cuối của danh sách về con trỏ NULL.
pTail
pHead

Thuật toán:
B1. Gán con trỏ pHead = NULL
B2. Gán con trỏ pTail = NULL
BKT: Kết thúc

Cài đặt:
void KhoiTao (List &l){
l. pHead = NULL;
l.pTail = NULL;
}
11

4.2. Tạo mới 1 nút trong danh sách
Thuật toán
+ Đầu vào: Thành phần dữ liệu x
+ Đầu ra: Nút chứa dữ liệu x.
B1: p = new node; //cấp phát bộ nhớ cho con trỏ p
B2: if (p == NULL) // cấp phát không thành công
Thực hiện BKT;
B3: p->data=x;
B4: p->next=NULL;
BKT: Kết thúc;

12

4.2. Tạo mới 1 nút trong danh sách
Cài đặt:
Node* TaoNut (int x) {
Node *p;
p = (Node*) malloc (sizeof(Node));
if (p==NULL) {
printf (“Khong du bo nho!”);
return NULL;

}
p->data=x;
p->next=NULL;
return p;
}
13

4.3. Thêm 1 phần tử vào danh sách
 Thêm vào đầu danh sách.

 Thêm vào cuối danh sách.
 Thêm vào sau một nút q bất kỳ.

14

4.3. Thêm 1 phần tử vào danh sách
Thêm vào đầu danh sách

15

4.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào đầu danh sách
Thuật toán
 Đầu vào: Danh sách l, Nút p cần thêm vào l
 Đầu ra: Danh sách l sau khi đã thêm nút p
Kiểm tra nếu DS rỗng thì:
+ Gán pHead = p;

+ Gán pTail = p;
Ngược lại:
+ Điều chỉnh liên kết p->next = pHead;
+ Gán pHead = p;
16

4.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào đầu danh sách
Cài đặt
void ChenDau (list &l, node *p) {
if (l.pHead==NULL){
l.pHead = p;
l.pTail = p;
}
else {
p->next = l.pHead;
l.pHead = p;
}
}
17

Bài tập áp dụng
Bài tập 1: Viết chương trình tạo 1 danh sách liên
kết để lưu các số nguyên được nhập từ bàn phím.

18

Bài tập áp dụng
Thuật toán tạo 1 danh sách liên kết đơn:
• Đầu vào: các phần tử dữ liệu X = {x1, x2, x3, …xn}
• Đầu ra: Danh sách liên kết l.
B1. Khai báo danh sách: List l;
B2. Khởi tạo danh sách
B3. Bước lặp:
Xét từng phần tử xi trong X, thực hiện:
+ Tạo mới một nút chứa xi;
+ Chèn nút vừa tạo vào danh sách;

19

4.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào sau phần tử q

20

4.3. Thêm 1 phần tử vào danh sách
Thêm vào sau phần tử q
Thuật toán
• Đầu vào: Danh sách l, nút q, nút p (nút cần thêm
• Đầu ra: Danh sách l sau khi đã thêm nút p.
B1. Kiểm tra nếu q!=NULL;
1.1: p->next = q->next;
1.2: q->next = p
1.3: Kiểm tra nếu q = pTail thì
+ Điểu chỉnh lại Tail = p;

Ngược lại, thực hiện B2
B2. Thêm vào đầu DS
21

4.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào sau phần tử q
void ChenSau(List &l, node *q, Node *p)
{
if (q!=NULL){
p->next=q->next;
q->next=p;
if (q==l.pTail) l.pTail=p;
}
else ChenDau(l, p);
}

22

4.3. Thêm 1 phần tử vào danh sách
Thêm vào cuối danh sách

23

4.3. Thêm 1 phần tử vào danh sách
Thêm vào cuối danh sách
Thuật toán:
B1. Kiểm tra nếu DS rỗng thì:

1.1: Gán pHead = p;
1.2: Gán pTail = p;
Ngược lại, thực hiện B2.
B2: Chèn p vào cuối danh sách:
2.1: pTail->next = p;
2.2: Gán pTail=p;
BKT: Kết thúc;
24

4.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào cuối danh sách
Cài đặt:
void ChenCuoi (List &l, node *p)
{
if (l.pHead==NULL) {
l.pHead=p;
l.pTail=p;
}
else {
l.pTail->next=p;
l.pTail=p;
}
}

25

Cấu Trúc Dữ Liệu Và Giải Thuật Chapter 3.2Singlelist

Tài liệu liên quan

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