DANH SÁCH NỐI ĐƠN
CHƯƠNG 3 (tiếp)
KHÁI NIỆM DANH SÁCH NỐI ĐƠN

Nguyên tắc tạo thành danh sách

Danh sách được tạo thành từ các phần tử gọi là nút
(Node)

Các
node
có thể nằm bất kỳ đâu trong bộ nhớ

Mỗi
node
là một cấu trúc gồm 2 thành phần

infor chứa thông tin của 1 phần tử của danh sách L

next là một con trỏ, nó trỏ vào node đứng sau.
A
infor next
Một node trong danh sách
KHÁI NIỆM DANH SÁCH NỐI ĐƠN

Ví dụ
Tran Lan Anh
32
7.8
1089
infor

2038
Ha Anh Lan
23
8.7
1089
Ta Bach Lan
23
8.7
1547
Vu Hoa Lan
23
8.7
3452
L=2038
Bui Nhu Lan
23
8.7
NULL
1032
1089
1547
3452
1032
Ví dụ
ƯU VÀ NHƯỢC ĐIỂM CỦA DSNĐ

Ưu điểm:

Tiết kiệm bộ nhớ



Khai báo Cấu trúc dữ liệu sinh viên
struct SINHVIEN {
char hoten[30];
int tuoi;
float diemtb;
};
Khai báo kiểu dữ liệu SV
struct Node {
SINHVIEN infor;
Node *next;
};
Khai báo kiểu dữ liệu Node
KB con trỏ trỏ vào Node đầu tiên
TRO L;
typedef Node * TRO;
Khai báo kiểu con trỏ của Node

Khởi tạo danh sách rỗng

Kiểm tra danh sách rỗng

Duyệt danh sách

Tìm kiếm một node trên danh sách

Bổ sung node mới vào đầu danh sách

Bổ sung node mới vào sau một node


B
C
E
L
Q
Q
Q
Q
Q
2. Nếu Q != NULL thì (thực
hiện yêu cầu) và chuyển Q
xuống node ngay sau nó:
Q=Q->next;
3. Lặp lại bước 2
Q
Q = NULL
DUYỆT DANH SÁCH

Hàm duyệt danh sách như sau
void travel(TRO L)
{
TRO Q;
if (!empty(L))
{
Q = L;
while (Q != NULL)
{
//Statement
Q = Q->next;
}

C
E
L
Q
Q
Q
Q
Q
3. Giả sử cần tìm node có
infor là K trong danh sách
Q
Không tìm thấy
TRO Search(TRO L) {
Q = L;
while (Q != NULL && (ĐKTK chưa thỏa))
Q = Q->next;
return Q;
}
Hàm Search trả về NULL nếu
không tìm thấy, ngược lại trả
về con trỏ trỏ vào node tìm
được
BỔ SUNG VÀO ĐẦU DANH SÁCH
P
B
C
D
E
L
Danh sách có phần tử đầu tiên

được trỏ bởi con trỏ L
E
X
Dữ liệu lưu trong biến X
Khai báo con trỏ P: TRO P;
Cấp phát bộ nhớ cho con trỏ P:
P = new Node;
next của node mới trỏ vào node đứng
sau node trỏ bởi Q: P->next = Q->next;
next của node trỏ bởi Q trỏ vào
node mới: Q->next = P;
Đưa dữ liệu vào node mới:
P ->infor = X;
A
H
B
C
F
L
E
C
Q trỏ vào node mà node mới
được bổ sung vào sau nó
BỔ SUNG VÀO SAU MỘT NODE

Hàm thực hiện việc bổ sung
void Insert(TRO &L, TRO Q, Item X)
{ TRO P;
P = new Node;
P->infor = X;

}
C
XÓA NODE SAU NODE TRỎ BỞI M
Q
A
F
B
C
E
L
1. Khai báo con trỏ Q: TRO Q;
2. Cho Q trỏ vào node ở sau
node trỏ bởi M: Q = M->next;
3. next của M trỏ vào node sau
node trỏ bởi Q:
M->next = Q->next;
4. Xóa node trỏ bởi con trỏ Q:
delete Q;
M
XÓA NODE SAU NODE TRỎ BỞI M

Hàm xóa node sau con trỏ M
void M_Delete(TRO &L, TRO M)
{
TRO Q;
Q = M->next;
M->next = Q->next;
delete Q;
}
TẠO MỘT DANH SÁCH MỚI

TRO P, Q; Item X; char tieptuc; //Bước 1
L = NULL;
do{
nhap(X); //Bước 2
P = new Node;
P->infor = X; P->next = NULL; //Bước 3
if (L==NULL) L = P; //Bước 4
else Q->next = P;
Q = P; //Bước 5
cout<<“Co nhap nua khong(C/K)?:”; cin>>tieptuc;
}while (toupper(tieptuc) == ‘C’); //Bước 6
}