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

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 (490.23 KB, 48 trang )

Danh sách liên kết đôi

1

Mục tiêu
 Khái niệm DSLK đôi.

 Biểu diễn, quản lý DSLK đôi.
 Các thao tác trên DSLK đôi.

 Sao chép DSLK đôi.
 Sắp xếp trên DSLK đôi.

2

1. Khái niệm
 Mỗi phần tử có 2 mối liên kết với các phần
tử khác trong danh sách.
A

B

C

D

pTail
pHead
Previous

data

Next

3

2. Biểu diễn, quản lý DSLK đôi
 Cấu trúc một nút:
struct DNode
{
T data;
DNode * Next;
DNode * Prev;
};

Khai báo:
Node *p;

 Quản lý danh sách liên kết đôi:
struct DList
{
DNode* pHead;
DNode* pTail;
};

Khai báo:
DList l;
4

3. Các thao tác trên DSLK đôi
Tạo danh sách rỗng

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

5

3.1 Khởi tạo danh sách
Thuật toán:
• Đầu vào: Danh sách cần khởi tạo.
• Đầu ra: Danh sách sau khi khởi tạo.
B1: Gán con trỏ pHead = NULL.
B2: Gán con trỏ pTail = NULL.
BKT: Kết thúc ;

Cài đặt thuật toán:
void KhoiTao(DList &l) {
l.pHead = NULL;
l.pTail = NULL;
}

6

3.2 Tạo mới một nút
Thuật toán:
• Đầu vào: Phần tử dữ liệu x.
• Đầu ra: Nút p chứa dữ liệu x.
B1: p = new DNode ;//cấp phát bộ nhớ cho con trỏ p
B2: IF(p == NULL); // cấp phát không thành công
Thực hiện BKT;
B3: p->Next = NULL;
B4: p->data=x;
B5: p->Prev=NULL;
BKT: Kết thúc và trả về con trỏ đến nút vừa tạo;
7

3.2 Tạo mới một nút
Cài đặt thuật toán:
DNode* TaoNut (T x)
{
Node *p;
p = malloc (sizeof (DNode));
if (p != NULL) {
p ->Next = NULL;
p ->data = x;
p ->Prev = NULL;
}
return (p);
}

8

3.3 Thêm 1 nút vào danh sách
 Thêm vào đầu danh sách.

 Thêm vào cuối danh sách.
 Thêm vào sau một nút q bất kỳ.

9

3.3 Thêm 1 phần tử vào danh sách
Thêm vào đầu danh sách

10

3.3 Thêm 1 phần tử vào danh sách
Thuật toán thêm phần tử vào đầu danh sách:
• Đầu vào: Danh sách l; nút cần thêm p.
• Đầu ra: Danh sách sau khi đã thêm nút p.
B3: Nếu danh sách rỗng thì:

3.1: Đặt pHead = pTail = p;
3.2: Thực hiện BKT;
B4: Nếu danh sách không rỗng thì:

4.1: Điều chỉnh liên kết p ->Next = pHead
4.2: pHead ->Prev = p;

4.3: pHead = p;
BKT: Kết thúc

11

3.3 Thêm 1 phần tử vào danh sách
Cài đặt thuật toán:
Void ThemDau (DList &l, DNode *p) {
if (l.pHead == NULL)
l.pHead = L.pTail = p;

else {
p ->Next = l.pHead;
l.pHead ->Prev = p;
l.pHead = p;
}
}

12

Bài tập ứng dụng
Bài tập 1: Trên ngôn ngữ C, viết chương trình
thực hiện các yêu cầu sau:
1) Tạo một cấu trúc danh sách liên kết đôi, với
các thao tác:
 Khởi tạo danh sách.
 Tạo mới 1 nút trong danh sách.
 Chèn một nút vào đầu danh sách.

2) Sử dụng cấu trúc danh sách liên kết đôi vừa
tạo để lưu n số nguyên bất kỳ được nhập từ
bàn phím:
13

3.3. Thêm 1 phần tử vào danh sách
Thêm phần tử vào cuối danh sách

14

3.3. Thêm 1 phần tử vào danh sách
Thuật toán thêm phần tử vào cuối danh sách:
• Đầu vào: Danh sách l; nút cần thêm p.
• Đầu ra: Danh sách sau khi đã thêm nút p vào cuối.
B3: Nếu danh sách rỗng thì:

3.1: Đặt pHead = pTail = p;
3.2: Thực hiện BKT;
B4: Nếu danh sách không rỗng thì:

4.1: Điều chỉnh liên kết l.pTail ->Next = p
4.2: p->Prev = l.pTail;
4.3: l.pTail = p;
BKT: Kết thúc

15

3.3. Thêm 1 phần tử vào danh sách
Cài thuật toán:
void ChenCuoi (DList &l, DNode*p){
if (l.pHead == NULL)
L.pHead = L.pTail = p;

else{
l.pTail ->Next = p;
p ->Prev = l.pTail;
l.pTail = p;
}

}

16

Bài tập ứng dụng
Bài tập 2: Mở rộng chương trình vừa viết bằng
cách:
1) Bổ sung thêm thao tác chèn phần tử vào cuối
danh sách :
2) Tạo danh sách n số nguyên sử dụng thao tác
chèn phần tử vào cuối danh sách.

17

3.3. Thêm 1 phần tử vào danh sách

Thêm phần tử vào giữa danh sách (sau nút q)

18

3.3. Thêm 1 phần tử vào danh sách
Thuật toán thêm phần tử vào sau phần tử q:
• Đầu vào: Danh sách l; nút q, nút cần thêm p.
• Đầu ra: Danh sách sau khi đã thêm nút p sau nút q.
B3: Nếu q là nút cuối trong danh sách thì:

3.1: Thực hiện thao tác ChenCuoi();
3.2: Thực hiện BKT;
B4: Nếu danh sách không rỗng thì:

4.1: Điều chỉnh liên kết l.pTail ->Next = p
4.2: p->Prev = l.pTail;
4.3: l.pTail = p;
BKT: Kết thúc

19

3.3. Thêm 1 phần tử vào danh sách
Cài đặt thuật toán:
void ChenSau (DList &l, DNode *q, DNode *p) {
if (q ->Next == NULL){
q ->Next = p;
p ->Prev = q;
l.pTail = p;

}
else{
p ->Next = q ->Next;
q ->Next ->Prev = p;
q ->Next = p;
p ->Prev = q;
}
}

20

Bài tập ứng dụng
Bài tập 3: Mở rộng chương trình vừa viết:
Cho phép người dùng nhập:
- Giá trị y của một nút q bất kỳ có trong danh sách.
- Tìm kiếm nếu nút q có tồn tại trong danh sách thì:
+ Tạo nút p chứa giá trị x.
+ Chèn nút p vào sau nút q.

21

3.4. Duyệt danh sách
Thuật toán:
Đầu vào: Danh sách cần duyệt l.
Đầu ra: Tùy thuộc vào yêu cầu của bài toán.
B1. Cho con trỏ p trỏ đến phần tử đầu danh sách;
B2: Bước lặp (thực hiện cho đến khi danh sách rỗng):
2.1: Xử lý phần tử p;

2.2: Cho p trỏ đến phần tử kế tiếp;
BKT: Kết thúc;
22

3.3. Duyệt danh sách
Cài đặt thuật toán:
void DuyetDS (DList l)
{
DNode* P = l.pHead;
while (P!= NULL)
{
//Các lệnh xử lý nút;
P = P ->Next;
}
}
23

Bài tập ứng dụng
Bài tập 4: Mở rộng chương trình vừa viết:
- Bổ sung thêm thao tác duyệt danh sách.
- Sử dụng thao tác duyệt danh sách:
+ Danh sách tạo bằng thao tác chèn đầu.

+ Danh sách tạo bằng thao tác chèn cuối.

24

3.5. Tìm kiếm phần tử
Thuật toán
• Đầu vào: Danh sách l, khóa tìm kiếm x.
• Đầu ra: Con trỏ tới nút chứa khóa cần tìm.
B1: p=pHead // p trỏ đến đầu danh sách
B2: Trong khi (p!= NULL) và (p->data != x)
Thực hiện p = p->next; // p trỏ tới phần tử kế
BKT:
Nếu p!=NULL thi p trỏ tới phần tử cần tìm;
Ngược lại: không có phần tử cần tìm;

25

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

Tài liệu liên quan

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