CHAPTER 6: LINKED
LISTS
Cấu trúc dữ liệu động 3

Mục
Mụctiêu
tiêu

Giới
Giớithiệu
thiệukhái
kháiniệm
danh
danhsách
sáchliên
liênkết
kết
:
:

Các
Cáckiểu
kiểutổ
tổ


liên
liênkết
kếtđơn
đơn
:
:
tổ
tổchức
chức
,
,
các
cácthuật
thuậttoán
toán

được kích thước, cấu trúc, … trong suốt quá trình sống.
Các đối tượng dữ liệu thuộc những kiểu dữ liệu gọi là kiểu
Các đối tượng dữ liệu thuộc những kiểu dữ liệu gọi là kiểu
dữ liệu tĩnh.
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
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 thực, kiểu nguyên, kiểu
dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu
ký tự hoặc từ các cấu trúc đơn giản như mẩu tin, tập
ký tự hoặc từ các cấu trúc đơn giản như mẩu tin, tập
hợp, mảng
hợp, mảng

Các đối tượng dữ liệu được xác định thuộc những kiểu dữ
Các đối tượng dữ liệu được xác định thuộc những kiểu dữ
liệu này thường cứng ngắt, gò bó
liệu này thường cứng ngắt, gò bó


khó diễn tả được thực
khó diễn tả được thực
tế vốn sinh động, phong phú.
tế vốn sinh động, phong phú.
5



số
sốđối
đốitượng
tượngdữ
dữliệu
liệutrong
trongchu
chukỳ


về
vềcấu
cấutrúc
trúc
,
,
độ
độlớn
lớn
,
,
như
nhưdanh
danhsách


có
cóthể
thểtăng
tăngthêm
thêm
,
,
giảm
giảmđi
điNếu
Nếudùng


biết
biếtnhư
nhưmảng
mảngđể
đểbiểu
biểudiễn
diễn
Những



chương
chươngtrình
trìnhkhó
khóđọc
đọc
,
,
khó
khóbảo
bảotrì


dụng
dụngbộ
bộnhớ
nhớmột
mộtcách
cáchcó
cóhiệu
hiệuquả
đã
đãdành
dànhcho
chochúng
chúngsuốt
suốtquá
quátrình
trìnhbộ
bộnhớ
nhớkém
kémhiệu
hiệuquả
quả
.
.
6

CTDL tĩnh
CTDL tĩnh

Mảng 1 chiều
Mảng 1 chiều


Cấp phát động lúc chạy chương trình
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ớ
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
Kích thước danh sách chỉ bị giới hạn do RAM

Thao tác thêm xoá đơn giản
Thao tác thêm xoá đơn giản
Insert,
Delete
8

Hướng
Hướnggiải
giảiquyết
quyết

Cần
Cầnđược
đượccác
cácyêu
yêucầu
cầu
:
:

Linh
Linhđộng
độnghơn
hơn
.

trúc
trúctrong
trongsuốt
suốtthời
thờigian
giansống
sống
.
.

Cấu
Cấu


không
khôngđộng
độngBiến
Biếnkhông
khôngđộng
động
(
(
biến
biếntĩnh
tĩnh
,
,
biến
khai
khaibáo
báotường
tườngminh
minh
,
,

Tồn
Tồntại
tạikhi
khi


mấtkhi
khira
rakhỏi
khỏiphạm
phạmvi
vinày
này
,
,

Được
Được

liệu
liệu
(
(
Data
Datasegment
segment
)
)
hoặc
hoặclà
làStack
Stack
(
(
đối
đốivới
với


Kích
Kíchthước
thướckhông
khôngthay
thayđổi
đổitrong
trongsuốt
suốtquá
minh
minh
,
,
các
cácbiến
biếnkhông
khôngđộng
độngcó
cómột
mộtchỉ
chỉvùng
vùngnhớ
nhớlưu
lưutrữ
trữbiến
biếnvà
vàdanh
danhđó
đó
.
.

Ví
Vídụ
dụ
:
:
int a; // a, b là các biến không động
char b[10];
11

Biến
Biếnđộng
động


biên
biêndịch
dịchkhông
khôngthể
thểxác
xácđịnh
địnhtrước
trướckích
kích

tượng
tượngdữ
dữliệu
liệudo
dosự
sựtồn
tồntại
tạivà
và

ngữ
ngữcảnh
cảnhcủa
củaviệc
việcthực
thựchiện
hiệnchương
chươngtrình
trình


điểm
điểmkể
kểtrên
trênnên
nênđược
đượckhai
khaibáo
báonhư


thỏa
thỏa
:
:

Biến
Biếnkhông
khôngđược
đượckhai
khaibáo
báotường
tường
giảiphóng
phóngbộ
bộnhớ
nhớkhi
khingười
ngườisử
sửdụng
dụng

qui
quitắc
tắcphạm
phạmvi
vi
(
(
tĩnh
tĩnh
).
).

Vùng
Vùngnhớ
nhớ


Kích
Kíchthước
thướccó
cóthể
thểthay
thayđổi
đổitrong
trongquá
quá

đượckhai
khaibáo
báotường
tườngminh
minhnên
nêncác
cácbiến
biến


kếtbuộc
buộcvới
vớiđịa
địachỉ
chỉvùng
vùngnhớ
nhớcấp
cấp


khănkhi
khitruy
truyxuất
xuấtđến
đếnmột
mộtbiến
biếnđộng
động
.

trỏ
trỏ
(
(
là
làbiến
biếnkhông
khôngđộng
động
)
)
được
đượcsử
sửdụng
dụng


ra
ramột
mộtbiến
biếnđộng
động
,
,
phải
phảidùng
dùngmột
mộtcon


này
nàyvà
vàsau
sauđó
đó
,
,
truy
truyxuất
xuấtđến
đếnbiến


biết
biếtđịnh
địnhdanh
danh
.
.
13

Biến
Biếnđộng
động
Hai
Haithao
thao

tạo
tạovà
vàhủy
hủymột
mộtbiến
biếnđộng
độngdo
dobiến
biến


một
mộtbiến
biếnđộng
độngvà
vàcho
chocon
contrỏ
trỏ‘p’
do
dop
pchỉ
chỉđến
đến
14

Biến
Biếnđộng
động
Tạo
Tạo


trỏ‘p’
‘p’chỉ
chỉđến
đếnnó
nóvoid* malloc(size);//
//
trả
trảvề
về

sizebyte
bytevừa
vừađược
đượccấp
cấpphát
phát
.
.
void* calloc(n,size);
//
//
trả
trả
vừa
vừađược
đượccấp
cấpphát
phátgồm
gồmn
nphần
phầntử
tử

size
sizebyte
byte
new //
//
toán
toántử
tửcấp
cấpphát
phátbộ
bộ


vùng
vùngnhớ
nhớcấp
cấpphát
phátbởi
bởihàm
hàmmalloc
mallochoặc
hoặc


p
phuỷ
huỷvùng
vùngnhớ
nhớcấp
cấpphát
phátbởi
bởitoán

động–
–Ví
Vídụ
dụint *p1, *p2;
// cấp phát vùng nhớ cho 1 biến động kiểu int
p1 = (int*)malloc(sizeof(int));
*p1 = 5; // đặt giá trị 5 cho biến động đang
được p1 quản lý
// cấp phát biến động kiểu mảng gồm 10 phần tử kiểu
int
p2 = (int*)calloc(10, sizeof(int));
*(p2+3) = 0; // đặt giá trị 0 cho phần tử thứ 4
của mảng p2
free(p1);
free(p2);
16

Kiểu

là
làkiểu
kiểucơ
cơsở
sởdùng
dùnglưu
lưuđịa
địachỉ
chỉ


Biến
Biếnthuộc
thuộckiểu
kiểucon
contrỏ
trỏTp
Tplà
làbiến


chỉ
chỉcuả
cuảmột
mộtvùng
vùngnhớ
nhớứng
ứngvới
vớimột


NULL
NULL
.
.
17

Con
Contrỏ
trỏ–
–Khai
Khaibáo
báo

Cú
Cúngôn
ngônngữ
ngữC
C
:
:
typedef <kiểu cơ sở> * < kiểu con trỏ>;

Ví
Vídụ
dụ
:
:
typedef int *intpointer;
intpointer p;
hoặc
hoặc
int *p;
là

trỏ–
–Thao
Thaotác
táccăn
cănbản
bản

Các
Cácthao
thaohọa
họabằng
bằngC
C
)
)

Khi
Khi
1
1
biến
biếncon
contrỏ
trỏ


x
,
,
ta
tanói
nói‘p
‘ptrỏ
trỏđến
đếnx’
x’
.
.

Gán
Gán

trỏ
trỏp
p
:
:
p
p
= <
= <
địa
địachỉ
chỉ
>;
>;
ví duï :
ví duï :int i,*
int i,*
p;
p;

do
dop
ptrỏ
trỏđến
đến
(*
(*
p
p
)
)
19

Danh
Danhsách
sách


Có hai cách cài đặt danh sách là :

Cài đặt theo kiểu kế tiếp : ta có danh sách
Cài đặt theo kiểu kế tiếp : ta có danh sách
kề hay danh sách đặc.
kề hay danh sách đặc.

Cài đặt theo kiểu liên kết : ta có danh sách
Cài đặt theo kiểu liên kết : ta có danh sách
liên kết.
liên kết.
20

Danh
Danhsách
sáchliên
liênkết
kết
(
(
List

của danh sách kề cố đònh sau khi cấp phát nên số node
của danh sách kề cố đònh sau khi cấp phát nên số node
cần dùng có khi thừa hay thiếu. Ngoài ra danh sách kề
cần dùng có khi thừa hay thiếu. Ngoài ra danh sách kề
không phù hợp với các thao tác thường xuyên như thêm
không phù hợp với các thao tác thường xuyên như thêm
hay xóa phần tử trên danh sách,
hay xóa phần tử trên danh sách,
21

Danh
Danhsách
sáchliên
liênkết
kết
(
(
List
List
)
)

thêm vùng liên kết. Ngoài ra việc truy xuất node thứ I
trong danh sách liên kết chậm hơn vì phải duyệt từ đầu
trong danh sách liên kết chậm hơn vì phải duyệt từ đầu
danh sách.
danh sách.
22


Có
Cónhiều
nhiềukiểu
kiểutổ
tổchức
chứcliên
liên

sách
sáchnhư
như
:
:
Danh
Danhsách
sáchliên
liênkết
kếtđơn
đơn



liên
liênkết
kếtvòng
vòng
…
…
Danh
Danhsách
sáchliên
liênkết
kết

Danhsách
sáchliên
liênkết
kếtđơn
đơn
:
:mỗi
mỗiphần
phầntử


nó
nótrong
trongdanh
danhsách
sách
:
:
Danh
Danhsách
sáchliên
liên
với
vớicác
cácphần
phầntử
tửđứng
đứngtrước
trướcvà
và
sách
sáchliên
liênkết
kết
(
(
List
List
)
)

Danh
Danhsách
sáchliên
liênkết

liênkết
kếtvới
vớiphần
phầntử
tửđầu
đầudanh
danhsách
sách
: