Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 93
Để quản lý một danh sách liên kết chúng ta có thể sử dụng nhiều phương pháp khác
nhau và tương ứng với các phương pháp này chúng ta sẽ có các cấu trúc dữ liệu
khác nhau, cụ thể:
- Quản lý đòa chỉ phần tử đầu danh sách:
SLL_Type SLList1;
Hình ảnh minh họa:
SLList1 NULL
15 10 20 18 40 35 30

- Quản lý đòa chỉ phần tử đầu và cuối danh sách:
typedef struct SLL_PairNode
{ SLL_Type SLLFirst;
SLL_Type SLLLast;
} SLLP_Type;
SLLP_Type SLList2;
Hình ảnh minh họa:
SLLFirst SLLLast NULL
15 10 20 18 40 35 30

- Quản lý đòa chỉ phần tử đầu, đòa chỉ phần tử cuối và số phần tử trong danh sách:
typedef struct SLL_PairNNode
{ SLL_Type SLLFirst;
SLL_Type SLLLast;
unsigned NumNode;
} SLLPN_Type;
SLLPN_Type SLList3;
Hình ảnh minh họa:
SLLFirst SLLLast NULL
15 10 20 18 40 35 30

d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e

}
Hình ảnh minh họa:
SLList1 NULL

b. Tạo mới một phần tử / nút:
Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData.
- Thuật toán:
B1: First = new SLL_OneNode
B2: IF (First = NULL)
Thực hiện Bkt
B3: First->NextNode = NULL
B4: First->Key = NewData
Bkt: Kết thúc
- Cài đặt thuật toán:
Hàm SLL_Create_Node có prototype:
SLL_Type SLL_Create_Node(T NewData);
Hàm tạo mới một nút có thành phần dữ liệu là NewData, hàm trả về con trỏ trỏ
tới đòa chỉ của nút mới tạo. Nếu không đủ bộ nhớ để tạo, hàm trả về con trỏ
NULL.
SLL_Type SLL_Create_Node(T NewData)
{ SLL_Type Pnode = new SLL_OneNode;
if (Pnode != NULL)
{ Pnode->NextNode = NULL;
Pnode->Key = NewData;
}
return (Pnode);
}
- Minh họa thuật toán:
Giả sử chúng ta cần tạo nút có thành phần dữ liệu là 20: NewData = 20
Pnode = new SLL_OneNode

u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r

B3: NewNode->NextNode = SLList // Nối SLList vào sau NewNode
B4: SLList = NewNode // Chuyển vai trò đứng đầu của NewNode cho SLList
Bkt: Kết thúc
- Minh họa thuật toán:
Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25: NewData = 25
NewNode
25 NULL
NULL
SLList 10 20 18 40 35 30

NewNode->NextNode = SLList:
NewNode
25
NULL
SLList 10 20 18 40 35 30

SLList = NewNode:
NewNode
25
SLList NULL
10 20 18 40 35 30

Kết quả sau khi chèn:
SLList NULL
25 10 20 18 40 35 30

- Thuật toán thêm phần tử vào cuối danh sách liên kết đơn:
B1: NewNode = SLL_Create_Node (NewData)
B2: IF (NewNode = NULL)
Click to buy NOW!

c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d

NULL
NewNode 25
SLList CurNode
15 10 20 18 40 35 NULL

CurNode->NextNode = NewNode:
NULL
NewNode 25
SLList CurNode
15 10 20 18 40 35

Kết quả sau khi chèn:
SLList NULL
15 10 20 18 40 35 25

- Thuật toán thêm phần tử vào giữa danh sách liên kết đơn:
Giả sử chúng ta cần thêm một phần tử có giá trò thành phần dữ liệu là NewData
vào trong danh sách SLList vào ngay sau nút có đòa chỉ InsNode. Trong thực tế
nhiều khi chúng ta phải thực hiện thao tác tìm kiếm để xác đònh đòa chỉ InsNode, ở
đây giả sử chúng ta đã xác đònh được đòa chỉ này.
B1: NewNode = SLL_Create_Node (NewData)
B2: IF (NewNode = NULL)
Thực hiện Bkt
B3: IF (InsNode->NextNode = NULL)
B3.1: InsNode->NextNode = NewNode
B3.2: Thực hiện Bkt
Click to buy NOW!
P
D
F

c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u

InsNode->NextNode = NewNode:
NewNode 25
SLList
15 10 20 18 40 35 NULL
InsNode
Kết quả sau khi chèn:
SLList NULL
15 10 20 25 18 40 35

- Cài đặt thuật toán:
Các hàm thêm phần tử tương ứng với các trường hợp có prototype như sau:
SLL_Type SLL_Add_First(SLL_Type &SList, T NewData);
SLL_Type SLL_Add_Last(SLL_Type &SList, T NewData);
SLL_Type SLL_Add_Mid(SLL_Type &SList, T NewData, SLL_Type &InsNode);
Hàm thực hiện việc chèn phần tử có giá trò thành phần dữ liệu NewData vào trong
danh sách liên kết đơn quản lý bởi con trỏ đầu danh sách SList tương ứng với 3
trường hợp: Thêm đầu, thêm cuối, thêm giữa. Các hàm trả về giá trò là đòa chỉ của
nút đầu tiên nếu việc thêm thành công. Trong trường hợp ngược lại, các hàm trả
về con trỏ NULL.
Riêng đối với trường hợp thêm giữa, hàm SLL_Add_Mid thực hiện việc thêm vào
ngay sau nút có đòa chỉ InsNode. Nội dung của các hàm như sau:
Click to buy NOW!
P
D
F
-
X
C
h
a

D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c