CHAPTER 6: DANH SÁCH LIÊN KẾT
(LINKED LISTS)
1
Chương 6: Danh sách liên kết
Nội dung

Giới thiệu

Danh sách liên kết đơn (Single Linked List)

Danh sách liên kết đôi (Double Linked List)

Danh sách liên kết vòng (Circular Linked List)
2
Chương 6: Danh sách liên kết
Giới thiệu - Cấu trúc dữ liệu tĩnh

Cấu trúc dữ liệu tĩnh:

Khái niệm: Các đối tượng dữ liệu không thay đổi được kích
thước, cấu trúc, … trong suốt quá trình sống thuộc về kiểu dữ liệu
tĩnh

Một số kiểu dữ liệu tĩnh: các cấu trúc dữ liệu được xây dựng từ
các kiểu cơ sở như: kiểu số thực, kiểu số nguyên, kiểu ký tự ...
hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng ...
3
Chương 6: Danh sách liên kết
Giới thiệu - Cấu trúc dữ liệu tĩnh

Một số hạn chế của CTDL tĩnh:

n-2
n-1
chèn
Chương 6: Danh sách liên kết
Giới thiệu - Cấu trúc dữ liệu động

Cần xây dựng cấu trúc dữ liệu đáp ứng được các yêu cầu:

Linh động hơn

Có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống
 Cấu trúc

dữ liệu động
6
Chương 6: Danh sách liên kết
Giới thiệu - Cấu trúc dữ liệu động

Cấu trúc dữ liệu động: Ví dụ: Danh sách liên kết, cây

Cấp phát động lúc chạy chương trình

Các phần tử nằm rải rác ở nhiều nơi trong bộ nhớ

Kích thước danh sách chỉ bị giới hạn do RAM

Tốn bộ nhớ hơn (vì phải chứa thêm vùng liên kết)

Không thể truy cập ngẫu nhiên



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
Chương 6: Danh sách liên kết
Giới thiệu - Danh sách liên kết

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:

Danh sách liên kết kép: 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:
10
A B X Z Y
A B C D
Chương 6: Danh sách liên kết
Giới thiệu - Danh sách liên kết
11

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 X Z Y
A B C D
Chương 6: Danh sách liên kết
Nội dung

Giới thiệu

DataType data;
// DataType là ki u ã nh ngh a tr cể đ đị ĩ ướ
Node *pNext;
// c o n tr c h n c u trú c No deỏ ỉ đế ấ
};
14
data
pNext
Node* tên_nút;
Chương 6: Danh sách liên kết
DSLK n – Khai b á ođơ

Ví dụ 1: Khai báo node lưu số
nguyên:
struct Node
{
int data;
Node *pNext;
};

Ví dụ 2: Khai báo node lưu
thông tin của một sinh viên:
struct SinhVien {
char Ten[30];
int MaSV;
};
struct Node {
SinhVien data;
Node *pNext;
};

};
// kiểu danh sách liên kết
struct List
{
Node* pHead;
Node* pTail;
};
17
Khai báo biến kiểu danh sách:
List tên_biến;
Chương 6: Danh sách liên kết
DSLK đơn – Khai báo

Tạo một node mới

Viết hàm getNode để tạo ra một nút cho danh sách với dữ liệu
là x
18
Node* getNode ( DataType x)
{
Node *p;
p = new Node; // Cấp phát vùng nhớ cho node
if (p==NULL)
{
cout<<“Khong du bo nho!”; return NULL;
}
p->data = x; // Gán dữ liệu cho phần tử p
p->pNext = NULL;
return p;
}

…
20
Chương 6: Danh sách liên kết
DSLK đơn – Các thao tác cơ sở

Tạo danh sách rỗng
21
pHead
pTail
void Init(List &l)
{
l.pHead = l.pTail = NULL;
}
Chương 6: Danh sách liên kết
DSLK đơn

Các thao tác cơ bản

Tạo danh sách rỗng

Thêm một phần tử vào danh sách

Duyệt danh sách

Tìm kiếm một giá trị trên danh sách

Xóa một phần tử ra khỏi danh sách

Hủy toàn bộ danh sách


Thêm một phần tử

Gắn node vào đầu danh sách
25
A B C D E
pHead
pTail
X
new_node
new_node->pNext = pHead;
pHead = new_node;

Trích đoạn DSLK đơn – Các thao tác cơ sở Cài đặt: Chèn một phần tử vào sau nút q

---