"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết" trình bày giới thiệu chung, danh sách liên kết đơn, danh sách liên kết vòng, danh sách liên kết kép, một số ví dụ về danh sách liên kết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết
- Cấu trúc dữ liệu và giải thuật
Bài 15. Danh sách liên kết
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- Bài 15: Danh sách liên kết
Nội dung:
15.1. Giới thiệu chung.
15.2. Danh sách liên kết đơn.
15.2.1. Khái niệm về danh sách liên kết đơn.
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn.
15.3. Danh sách liên kết vòng.
15.3.1. Khái niệm về danh sách liên kết vòng.
15.3.2. Các thao tác cơ bản của danh sách liên kết vòng.
15.4. Danh sách liên kết kép.
15.4.1. Khái niệm về danh sách liên kết kép.
15.4.2. Các thao tác cơ bản của danh sách liên kết kép.
15.5. Một số ví dụ về danh sách liên kết.
Tham khảo:
1. Deshpande Kakde: C and Data structures.chm, Chapter 20: Linked Lists
2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists
3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 5 Linked Lists.
4. Bài giảng TS Nguyễn Nam Hồng
2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.1. Giới thiệu chung (1/2)
Với CTDL dạng mảng, bộ nhớ được sử dụng là một dãy liền
kề và có kích thước cố định.
Tuy nhiên, CTDL này có m ột số nhược điểm:
Thời gian cho việc thêm hay bớt phần tử trong mảng khá lâu vì
phải thay đổi cả các phần tử còn lại trong mảng.
Ngay cả khi khai báo một lượng lớn các phần tử cho mảng để có
thể áp dụng được cho nhiều bài toán, chúng ta cũng thấy khả năng
dư thừa bộ nhớ xuất hiện.
3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.1. Giới thiệu chung (2/2)
Để khắc phục nhược điểm trên, có thể sử dụng danh sách liên
kết như là cấu trúc dữ liệu thay thế.
Trong cấu trúc này, không cần xác định kích thước cho các
phần tử trước.
Ta có thể định nghĩa phần tử bất cứ lúc nào, sau đó liên kết
phần tử đó với danh sách đã có trước đó.
Như vậy, mỗi phần tử sẽ bao gồm thông tin cần lưu trữ và liên
kết với các phần tử khác.
4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (1/23)
Trong rất nhiều trường hợp cần sử dụng đến danh sách liên kết
động, danh sách liên kết động cần dùng đến khi kích thước
danh sách chưa biết tại thời điểm biên dịch chương trình.
Khi đó, danh sách có thể mở rộng hoặc thu hẹp lại tại thời
điểm chạy chương trình.
Cấu trúc dữ liệu linked list sử dụng mô hình liên kết động.
Một số dạng của danh sách liên kết:
Danh sách liên kết đơn.
Danh sách liên kết vòng.
Danh sách liên kết kép.
5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (2/23)
15.2.1. Khái niệm về danh sách liên kết đơn
Danh sách liên kết đơn là một
Link
cấu trúc dữ liệu bao gồm một tập Data Add
các nút, mà mỗi nút bao gồm:
Dữ liệu cần lưu trữ Node
Liên kết đến nút tiếp theo
60 800 45 90 55 0 NULL
1000 800 90
6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (3/23)
15.2.1. Khái niệm về danh sách liên kết đơn
Để quản lý danh sách liên kết, thông thường cần:
• Start là con trỏ chỉ đến phần tử đầu tiên của danh sách liên kết.
• Phần tử cuối của danh sách liên kết với vùng liên kết có nội dung
NULL.
start
60 800 45 90 55 0 NULL
1000 800 90
7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (4/23)
15.2.1. Khái niệm về danh sách liên kết đơn
Khai báo cấu trúc một Node của danh sách:
template
struct node
{
ListEntry data;
struct node *link;
};
8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (5/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
1. Khởi tạo danh sách.
2. LAdd: Thêm một node vào đầu danh sách.
3. LInsert: Chèn một node vào danh sách.
4. LAppend: Thêm một node vào cuối danh sách.
5. LFind: Tìm một node trong danh sách.
6. LDelete: Xóa một node trong danh sách.
7. LLength: Số phần tử trong danh sách.
8. LMakeEmpty: Làm rỗng danh sách.
9. LGet: Lấy thông tin về một phần tử trong danh sách.
9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (6/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
class LList {
public:
LList();
int LAdd(ListEntry entry);
int LInsert(ListEntry value, ListEntry entry);
int LAppend(ListEntry entry);
int LFind(ListEntry value);
int LDelete(ListEntry value);
int LLength();
void LMakeEmpty();
int LGet(int pos, ListEntry *value);
template friend void LPrint(LList list);
private:
node *start;
};
10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (7/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Khởi tạo danh sách:
template
LList::LList() start
{
start = NULL;
NULL
}
11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (8/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Thêm một node đầu danh sách:
Nếu danh sách rỗng, cấp phát ô nhớ và start temp 1
cho start trỏ vào ô nhớ đó.
Nếu danh sách không rỗng:
Cấp phát ô nhớ cho biến temp. data link NULL
Phần liên kết của temp trỏ vào đầu danh
sách. 2
Con trỏ start trỏ vào temp.
temp start
data link data link NULL
12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (9/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Thêm một node đầu danh sách: else {
template temp=(node *)
int LList::LAdd(ListEntry entry) {
malloc(sizeof(node));
int kt=0;
if(temp==NULL) {
node *temp;
printf("Loi cap phat bo nho!\n");
if(start==NULL) {
start=(node *) return kt; }
malloc(sizeof(node)); kt=1;
if(start==NULL) { temp->data=entry;
printf("Loi cap phat bo nho!\n"); temp->link=start;
return kt; }
start=temp;
kt=1;
}
start->data=entry;
return kt;
start->link=NULL;
} }
13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (10/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Chèn 1 node vào danh sách:
Nhập thông tin về node đứng trước node thêm mới.
Sử dụng con trỏ temp để đến được node đứng trước đó.
Cấp phát ô nhớ cho biến temp1.
Phần liên kết của temp1 trỏ vào phần liên kết của con trỏ temp.
Phần liên kết của con trỏ temp trỏ vào temp1.
start temp
data link data link data link data link NULL
2 1
temp1 data link
14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (11/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Chèn 1 node vào danh sách : if(temp!=NULL) {
template temp1=(node *)
int LList::LInsert(ListEntry value, malloc(sizeof(node));
ListEntry entry) {
if(temp1==NULL) {
int kt=0;
node *temp, *temp1; printf("Loi cap phat bo nho!\n");
if(start==NULL) printf("Danh sach rong!"); return kt; }
else { kt=1;
temp=start; temp1->data=entry;
while(temp!=NULL) {
temp1->link=temp->link;
if(temp->data==value)
temp->link=temp1;
break;
}
else
temp=temp->link; }
} return kt; }
15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (12/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Thêm một node cuối danh sách:
Nếu danh sách rỗng, cấp phát ô nhớ và start temp 1
cho start trỏ vào ô nhớ đó.
Nếu danh sách không rỗng:
Sử dụng con trỏ temp đi đến cuối danh data link NULL
sách.
Cấp phát ô nhớ cho temp->link.
2
Phần liên kết của temp->link trỏ vào
NULL.
start temp
data link data link data link NULL
1 data link 2
16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (13/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Thêm một node cuối danh sách: else {
template temp=start;
int LList::LAppend(ListEntry entry) { while(temp->link!=NULL)
int kt=0;
temp=temp->link;
node *temp;
temp->link=(node *)
if(start==NULL) {
start=(node *) malloc(sizeof(node));
malloc(sizeof(node)); if(temp->link==NULL) {
if(start==NULL) { printf("Loi cap phat bo nho!\n");
printf("Loi cap phat bo nho!\n"); return kt; }
return kt; } kt=1; temp=temp->link;
kt=1;
temp->data=entry;
start->data=entry;
temp->link=NULL; }
start->link=NULL;
} return kt;
}
17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (14/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Tìm một node trong danh sách:
Sử dụng con trỏ temp để duyệt qua
danh sách.
Sử dụng thêm biến pos để lưu vị trí
của node trong danh sách. Nếu danh
sách rỗng hoặc không tìm thấy trả về
0, ngược lại trả về vị trí của node.
start temp pos = 3
data link data link data link data link NULL
18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (15/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Tìm một node trong danh sách:
template
int LList::LFind(ListEntry value) {
int pos=0;
node *temp=start;
while(temp!=NULL) {
pos++;
if(temp->data==value)
break;
temp=temp->link;
}
if(temp!=NULL)
return pos;
else return 0;
}
19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
- 15.2. Danh sách liên kết đơn (16/23)
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn
Xóa một node trong danh sách: prev curr
Sử dụng 2 con trỏ prev và curr để tìm 1
node cần xóa. Con trỏ prev trỏ vào node start
trước node cần xóa. Con trỏ curr trỏ vào
node cần xóa.
NULL data link data link NULL
Nếu curr = start, cho start trỏ vào
start->link và giải phóng ô nhớ của curr.
Nếu không, prev->link trỏ tới
curr->link và giải phóng ô nhớ của curr.
2
start prev curr
data link data link data link data link NULL
20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
