<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

CH

ƯƠ

NG 3

DANH SÁCH LIÊN K

Ế

T

1. Gi

ớ

i thi

ệ

u v

ề

danh sách liên k

ế

t

2. Danh sách liên k

ế

t

đơ

n

3. Danh sách liên k

ế

t vòng

4. Danh sách liên k

ế

t kép

5. Cài

đặ

t ng

ă

n x

ế

p và hàng

đợ

i b

ằ

ng danh

sách liên k

ế

t

đơ

n

3.1

1. Gi

ớ

i thi

ệ

u v

ề

danh sách liên k

ế

t

l

Danh sách liên k

ế

t là danh sách tuy

ế

n tính

khi s

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán. Các

ph

ầ

n t

ử

d

ữ

li

ệ

u c

ủ

a danh sách

đượ

c l

ư

u

tr

ữ

trong các ph

ầ

n t

ử

nh

ớ

mà ta g

ọ

i là nút

(node). Trong m

ỗ

i nút nh

ớ

, ngoài ph

ầ

n t

ử

d

ữ

li

ệ

u cịn có

đị

a ch

ỉ

c

ủ

a nút lân c

ậ

n. N

ế

u

gi

ữ

a các nút nh

ớ

có 1 liên k

ế

t thì ta có

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2. Danh sách liên k

ế

t

đơ

n

2.1. Quy t

ắ

c t

ổ

ch

ứ

c danh sách liên k

ế

t

đơ

n

l

M

ỗ

i nút trong danh sách có hai tr

ườ

ng,

tr

ườ

ng INFOR ch

ứ

a thơng tin c

ủ

a ph

ầ

n t

ử

và tr

ườ

ng LINK ch

ứ

a

đị

a ch

ỉ

c

ủ

a nút

đứ

ng

sau (

đ

ây chính là

đị

a ch

ỉ

liên k

ế

t).

INFOR

LINK

3.3

2.1. Quy t

ắ

c t

ổ

ch

ứ

c danh sách

liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

l

Nút cu

ố

i cùng trong danh sách khơng có

nút

đứ

ng sau nên tr

ườ

ng

đị

a ch

ỉ

LINK là

r

ỗ

ng (

∅

).

l

Để

truy nh

ậ

p vào t

ấ

t c

ả

nút trong danh

sách thì ph

ả

i có con tr

ỏ

F tr

ỏ

t

ớ

i nút

đầ

u

tiên.

l

Khi danh sách r

ỗ

ng thì F =

∅

A1

A2

A3

A4

∅

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2.1. Quy t

ắ

c t

ổ

ch

ứ

c danh sách

liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

l

Để

t

ổ

ch

ứ

c l

ư

u tr

ữ

m

ộ

t danh sách liên k

ế

t thì ph

ả

i

có:

l Phải có phương tiện chia bộ nhớ ra thành các nút và ở
mỗi nút có thể truy nhập vào từng trường.

l Phải có cơ chế để xác định một nút đang được sử
dụng hoặc chưa được sử dụng (nút trống).

l Phải có cơ chế cung cấp các nút trống khi có yêu cầu
sử dụng và thu hồi lại các nút khi không cần dùng nữa.

l

Ta ký hi

ệ

u:

l P ⇐ AVAIL là phép lấy ra một nút trống có địa chỉ là P
(cấp phát một nút)

l P ⇒ AVAIL là phép thu hồi một nút có địa chỉ là P

3.5

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n

l

Ký hi

ệ

u: M

ộ

t nút có

đị

a ch

ỉ

là p (

đượ

c tr

ỏ

b

ở

i p) thì INFOR(p) và LINK(p) t

ươ

ng

ứ

ng

ch

ỉ

tr

ườ

ng INFOR và LINK c

ủ

a nút

đ

ó.

a) B

ổ

sung m

ộ

t nút m

ớ

i vào danh sách

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

a) B

ổ

sung m

ộ

t nút m

ớ

i vào danh sách:

- Vào: F, M, x

- Ra: Khơng có

{Th

ủ

t

ụ

c này b

ổ

sung ph

ầ

n t

ử

x vào sau nút

tr

ỏ

b

ở

i M trong danh sách liên k

ế

t

đơ

n F}

Procedure SLPostInsert(Var F; M,x)

1. {T

ạ

o nút m

ớ

i}

N

⇐

AVAIL

infor(N):=x; link(N):=

∅

;

3.7

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

2. {N

ố

i nút m

ớ

i vào sau nút M}

If F=

∅

then F:=N

Else begin

link(N) := link(M);

link(M) := N;

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

b) Lo

ạ

i b

ỏ

m

ộ

t nút kh

ỏ

i danh sách

- Vào: F, M

- Ra: Không

{Th

ủ

t

ụ

c này lo

ạ

i b

ỏ

nút tr

ỏ

b

ở

i M kh

ỏ

i danh sách

liên k

ế

t

đơ

n F}

Procedure SLDelete(Var F; M)

1. { Tr

ườ

ng h

ợ

p danh sách r

ỗ

ng}

If F=

∅

then begin

Write(‘danh sách r

ỗ

ng’)

Return

end

3.9

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

b) Lo

ạ

i b

ỏ

m

ộ

t nút kh

ỏ

i danh sách

2. {Ng

ắ

t k

ế

t n

ố

i v

ớ

i nút M}

{Nút M là nút

đầ

u tiên c

ủ

a danh sách }

If M=F then

F:=link(F)

Else begin

{Tìm

đế

n nút

đứ

ng tr

ướ

c nút M }

P:=F;

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

3. {H

ủ

y nút M}

M

⇒

AVAIL

Return

3.11

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

c) Duy

ệ

t danh sách

- Vào: F

- Ra: Không

{Th

ủ

t

ụ

c này duy

ệ

t danh sách liên k

ế

t

đơ

n F và

đư

a ra các ph

ầ

n t

ử

d

ữ

li

ệ

u trong ds}

Procedure SLDisplay(F)

1) P := F;

2) While P #

∅

do

begin

Write(infor(P)); P := link(P);

end;

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

d) Ghép hai danh sách liên k

ế

t

đơ

n

Cho 2 danh sách liên k

ế

t

đơ

n l

ầ

n l

ượ

t tr

ỏ

b

ở

i p

và q, ghép 2 danh sách tr

ở

thành m

ộ

t danh sách

và cho p tr

ỏ

t

ớ

i. Thu

ậ

t tốn có các b

ướ

c sau:

Procedure SLConcat(Var p, q)

1. {Danh sách trỏ bởi q rỗng}
If q = ∅ then Return

2. {Trường hợp danh sách trỏ bởi p rỗng}
If p = ∅ then begin

p:=q
return
end

3.13

2.2. M

ộ

t s

ố

phép toán trên

danh sách liên k

ế

t

đơ

n (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

d) Ghép hai danh sách liên k

ế

t

đơ

n

3. {Tìm

đế

n nút cu

ố

i danh sách p}

p1:= p

While link(p1) #

∅

do p1:=link(p1);

4. {Ghép}

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

Ư

u nh

ượ

c

đ

i

ể

m c

ủ

a danh sách liên k

ế

t

đơ

n

l

V

ớ

i danh sách tuy

ế

n tính

độ

ng, trong q

trình x

ử

lý ln có b

ổ

sung, lo

ạ

i b

ỏ

thì t

ổ

ch

ứ

c danh sách liên k

ế

t là h

ợ

p lý, t

ậ

n

d

ụ

ng

đượ

c các vùng nh

ớ

n

ằ

m r

ả

i rác

trong b

ộ

nh

ớ

.

l

Ch

ỉ

có ph

ầ

n t

ử đầ

u tiên là truy nh

ậ

p tr

ự

c

ti

ế

p, các ph

ầ

n t

ử

khác ph

ả

i truy nh

ậ

p qua

ph

ầ

n t

ử đứ

ng tr

ướ

c nó.

l

T

ố

n b

ộ

nh

ớ

do ph

ả

i l

ư

u c

ả

2 tr

ườ

ng infor

và link

ở

m

ỗ

i nút.

3.15

3. Danh sách liên k

ế

t vòng

l

Danh sách liên k

ế

t vòng (Circularly Linked

List) là m

ộ

t d

ạ

ng c

ả

i ti

ế

n c

ủ

a danh sách

liên k

ế

t

đơ

n.

l

Trong danh sách liên k

ế

t vòng, tr

ườ

ng

đị

a

ch

ỉ

c

ủ

a nút cu

ố

i cùng không ph

ả

i là r

ỗ

ng

mà l

ạ

i ch

ứ

a

đị

a ch

ỉ

c

ủ

a nút

đầ

u tiên c

ủ

a

danh sách.

A1

A2

A3

A5

</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

3. Danh sách liên k

ế

t vòng (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

l

Ư

u nh

ượ

c

đ

i

ể

m c

ủ

a danh sách n

ố

i vòng:

l

Danh sách n

ố

i vòng làm cho vi

ệ

c truy nh

ậ

p

vào các nút trong danh sách linh ho

ạ

t h

ơ

n. Ta

có th

ể

truy nh

ậ

p vào danh sách b

ắ

t

đầ

u t

ừ

m

ộ

t nút nào c

ũ

ng

đượ

c, không nh

ấ

t thi

ế

t ph

ả

i

t

ừ

nút

đầ

u tiên. Nút nào c

ũ

ng có th

ể

là nút

đầ

u tiên và con tr

ỏ

F tr

ỏ

vào nút nào c

ũ

ng

đượ

c.

l

Nh

ượ

c

đ

i

ể

m c

ủ

a danh sách n

ố

i vịng là trong

x

ử

lý n

ế

u khơng c

ẩ

n th

ậ

n s

ẽ

d

ẫ

n t

ớ

i m

ộ

t chu

trình khơng k

ế

t thúc.

3.17

3. Danh sách liên k

ế

t vòng (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

l

Để

kh

ắ

c ph

ụ

c nh

ượ

c

đ

i

ể

m c

ủ

a danh sách

n

ố

i vòng ta

đư

a thêm vào m

ộ

t nút

đặ

c bi

ệ

t

g

ọ

i là “nút

đầ

u danh sách” (list head

node). Tr

ườ

ng Infor c

ủ

a nút này không

ch

ứ

a d

ữ

li

ệ

u, con tr

ỏ

HEAD tr

ỏ

t

ớ

i nút

đầ

u

danh sách này cho phép ta truy nh

ậ

p vào

danh sách.

A1

A2

A3

</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

3. Danh sách liên k

ế

t vòng (

<i>ti</i>

<i>ế</i>

<i>p</i>

)

l

Vi

ệ

c dùng thêm nút

đầ

u danh sách

đ

ã làm cho

danh sách ln có ít nh

ấ

t 1 nút nên khơng bao

gi

ờ

r

ỗ

ng. Danh sách có 1 nút HEAD có

LINK(Head)= Head.

l

Các phép tốn b

ổ

sung và lo

ạ

i b

ỏ

nút trong

danh sách liên k

ế

t vòng t

ươ

ng t

ự

danh sách liên

k

ế

t

đơ

n .

Head

3.19

4. Danh sách liên k

ế

t kép

4.1. Gi

ớ

i thi

ệ

u

l

Trong danh sách liên k

ế

t kép (double linked list)

m

ỗ

i nút có c

ấ

u trúc g

ồ

m 3 tr

ườ

ng:

LEFT: Con trỏ trỏ tới nút đứng trước
RIGHT: Con trỏ trỏ tới nút đứng sau
INFOR: Chứa phần tử dữ liệu

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

4.1. Gi

ớ

i thi

ệ

u (ti

ế

p)

l

LEFT c

ủ

a nút c

ự

c trái và RIGHT c

ủ

a nút

c

ự

c ph

ả

i có giá tr

ị

là

∅

.

l

Để

truy nh

ậ

p vào danh sách c

ả

2 chi

ề

u ta

ph

ả

i dùng 2 con tr

ỏ

: Con tr

ỏ

L tr

ỏ

vào nút

c

ự

c trái, con tr

ỏ

R tr

ỏ

vào nút c

ự

c ph

ả

i.

l

Khi danh sách r

ỗ

ng thì L = R =

∅

.

A B C

L _R

3.21

4.2. Các phép toán trên danh sách

liên k

ế

t kép

a) Chèn thêm m

ộ

t nút vào danh sách

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

4.2. Các phép toán trên danh sách

liên k

ế

t kép

- Vào: (L,R),M,x
- Ra: Không có

{Thủ tục này bổ sung phần tử x <b>vào trước nút M</b> trong
DSLK kép L, R}

Procedure DLPreInsert(Var L, R; M, x)
1. {Tạo nút mới}

N ⇐ AVAIL;

{Đưa dữ liệu vào trong nút mới và cho các trường con trỏ rỗng}

infor(N) := x;

left(N) := right(N) := ∅;

3.23

a) Chèn thêm m

ộ

t nút vào danh sách

2. {Trường hợp danh sách rỗng}

If L=R=∅ then begin
L := R:=N;

Return;
end

3. {M trỏ tới nút cực trái}
If M=L then begin

right(N) := L;
left(L) := N;
L := N;

</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

a) Chèn thêm m

ộ

t nút vào danh sách

4. {B

ổ

sung vào nút m

ớ

i vào tr

ướ

c M}

right(left(M)) := N;

left(N) := left(M);

right(N) := M;

left(M) := N;

5. {K

ế

t thúc}

Return

3.25

b) Lo

ạ

i b

ỏ

m

ộ

t nút ra kh

ỏ

i danh

sách liên k

ế

t kép

l Cho danh sách liên kết kép L, R. M là con trỏ trỏ tới một
nút trong danh sách cần loại bỏ.

- Vào: (L,R), M
- Ra: Khơng có

{Thủ tục này loại bỏ nút trỏ bởi M trong DSLK kép L, R}
Procedure DLDelete(Var L, R; M)

1. { Trường hợp danh sách rỗng }
If L=R=∅ then begin

Write(‘ danh sach rong ‘)
Return

</div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

b) Lo

ạ

i b

ỏ

m

ộ

t nút ra kh

ỏ

i danh

sách liên k

ế

t kép

2. {Thay

đổ

i liên k

ế

t}

Case

L= R=M: Begin {Danh sach ch

ỉ

còn 1 nút M}

L :=

∅

;

R :=

∅

;

end

M=L: Begin { Nút c

ự

c trái b

ị

lo

ạ

i }

L := right(L);

left(L) :=

∅

;

end

3.27

b) Lo

ạ

i b

ỏ

m

ộ

t nút ra kh

ỏ

i danh

sách liên k

ế

t kép

M=R: Begin { Nút cực phải bị loại }
R := left(R);

right(R) := ∅;
end

ELSE

right(left(M)) := right(M);
left(right(M)) := left(M);
End Case

</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

c) Duy

ệ

t danh sách liên k

ế

t kép và

đư

a ra các ph

ầ

n t

ử

c

ủ

a danh sách

- Vào: L, R
- Ra: Khơng có

{Thủ tục này duyệt DSLKK L,R từ trái sang phải}
Procedute DLDisplay(L, R);

1) P:= L;

2) While P # ∅ do
begin

Write(infor(P));
P := right(P);
end;

Return

3.29

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

5.1. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho

ng

ă

n x

ế

p

l

Các ph

ầ

n t

ử

d

ữ

li

ệ

u c

ủ

a ng

ă

n x

ế

p l

ư

u tr

ữ

trong các nút nh

ớ

n

ằ

m r

ả

i rác kh

ắ

p n

ơ

i

trong b

ộ

nh

ớ

, m

ỗ

i nút nh

ớ

có c

ấ

u tr

ự

c

g

ồ

m 2 tr

ườ

ng

</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

- Vào: T, x
- Ra: Không có

{Thủ tục này bổsung phần tử x vào ngăn xếp T lưu trữphân tán}

Procedure push(Var T; x)
1) {Tạo nút mới}

N <= AVAIL; infor(N) := x; link(N) := ∅;
2) {Nối nút mới vào trên nút T}

link(N) := T;

3) {Cho T trỏ tới nút mới}
T := N;

Return

3.31

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

- Vào: T

- Ra: Phần tử dữ liệu loại bỏ

</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

Function pop(Var T)

1) {Kiểm tra ngăn xếp rỗng}
If T = ∅ then begin

write(‘Ngan xep da rong’); return; end;
2) {Giữ lại phần tử đỉnh sẽ loại bỏ}

tg := infor(T); P:=T;

3) {Cho T trỏ xuống nút bên dưới}
T := link(T);

4) {Hủy nút đỉnh và trả về phần tử đỉnh}
P => AVAIL; pop := tg;

Return

3.33

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

- Vào: T

- Ra: TRUE nếu ngăn xếp rỗng, FALSE nếu không rỗng
{Hàm kiểm tra ngăn xếp T lưu trữ phân tán, trả về TRUE

nếu n.xếp rỗng và FALSE nếu chưa rỗng}
Function isEmpty(T)

If T = ∅ then isEmpty:=TRUE;
Else isEmpty:=FALSE;

</div>
<span class='text_page_counter'>(18)</span><div class='page_container' data-page=18>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

5. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho ng

ă

n x

ế

p và hàng

đợ

i

- Vào: T

- Ra: Phần tử dữ liệu đỉnh ngăn xếp

{Hàm này trả về phần tử đỉnh ngăn xếp T lưu trữ phân tán}

Function top(T)

1) {Kiểm tra ngăn xếp rỗng}
If T = ∅ then begin

write(‘Ngan xep da rong’); return; end;
2) {Trả về phần tử đỉnh}

top := infor(T);
Return

3.35

5.2. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho hàng

đợ

i

</div>
<span class='text_page_counter'>(19)</span><div class='page_container' data-page=19>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

5.2. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho hàng

đợ

i

- Vào: (F, R), x
- Ra: Không có

{Thủ tục này bổ sung phần tử x vào lối sau của hàng đợi (F, R)
sử dụng cấu trúc lưu trữ phần tán}

Procedure QInsert(Var F,R; x)
1) {Tạo nút mới}

N <= AVAIL;

infor(N) := x; link(N) := ∅;
2) {Nối nút mới vào sau R}

If F=R=∅ Then begin F:=R:=N; return; end
Else link(R) := N;

3) {Cho R trỏ tới nút mới}
R := N;

Return

3.37

5.2. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho hàng

đợ

i

- Vào: (F, R)

- Ra: Ph

ầ

n t

ử

d

ữ

li

ệ

u lo

ạ

i b

ỏ

{Hàm này lo

ạ

i b

ỏ

ph

ầ

n t

ử

ở

l

ố

i tr

ướ

c c

ủ

a hàng

đợ

i

(F, R) l

ư

u tr

ữ

phân tán và tr

ả

v

ề

ph

ầ

n t

ử

lo

ạ

i b

ỏ

}

Function QDelete(Var F, R)

1){Ki

ể

m tra hàng

đợ

i r

ỗ

ng}

If F=R=

∅

then begin

write(‘Hàng

đợ

i

đ

ã r

ỗ

ng.’);

return;

</div>
<span class='text_page_counter'>(20)</span><div class='page_container' data-page=20>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

5.2. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho hàng

đợ

i

2) {Gi

ữ

l

ạ

i nút l

ố

i tr

ướ

c (nút

đầ

u hàng)}

tg := tnfor(F); P := F;

3) {Cho F tr

ỏ

t

ớ

i nút

đứ

ng sau}

If F=R then F:=R:=

∅

Else F := link(F);

4) {H

ủ

y nút và tr

ả

v

ề

ph

ầ

n t

ử

d

ữ

li

ệ

u}

P => AVAIL;

QDelete := tg;

Return

3.39

5.2. S

ử

d

ụ

ng c

ấ

u trúc l

ư

u tr

ữ

phân tán cho hàng

đợ

i

- Vào: (F, R)

- Ra: True - r

ỗ

ng, False - không r

ỗ

ng

{Hàm này ki

ể

m tra hàng

đợ

i r

ỗ

ng}

Function QIsEmpty(F, R)

If F=R=

∅

then QIsEmpty := True

Else QIsEmpty := False;

</div>
<span class='text_page_counter'>(21)</span><div class='page_container' data-page=21>

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03

Bài t

ậ

p

1. Thế nào là danh sách nối vòng. Nêu ưu nhược điểm của
nó.

2. Để khắc phục hạn chế của danh sách nối vòng người ta
làm thế nào.

3. Thế nào là danh sách nối kép? Qui ước biểu diễn một
nút của danh sách nối kép.

4. Nêu ưu nhược điểm của danh sách nối kép.

5. Cài đặt Stack bằng danh sach nối đơn như thế nào. Cần
chú ý gì khi thực hiện các phép bổ sung, loại bỏ phần tử.
6. Cài đặt Queue bằng danh sach nối đơn như thế nào.

Cần chú ý gì khi thực hiện các phép bổ sung, loại bỏ
phần tử.

</div>


<!--links-->