CẤU TRÚC DỮ LIỆU
CẤU

TRÚC

DỮ

LIỆU

VÀ GIẢITHUẬT
VÀ

GIẢI

THUẬT
Lý thuyết
Ph
ầ
n 2
(
Chươn
g
3
)
( g)
Danh sách, Ngăn xếp và Hàng đợi
 Giới thiệu khái niệm ADT (Kiểu dữ liệu
trừutượng
–
Abstract Data Type)
trừu

tượng

Abstract

Data

Type)
 Danh sách
N ă ế

Ngă
n x
ế
p
 Hàng đợi
Vũ Anh Dũng - Khoa CNTT 2
Kiểu dữ liệu trừu tượng
 Là tập các đối tượng tương ứng với tập các
thao tác
thao

tác
 Danh sách, tập hợp,… có thể coi là kiểu dữ
liệutrừutượng
liệu

trừu

tượng

 C++ cho phép viết các thao tác và được gọi
là á hươ thứ
là
c
á
c p
hươ
n
g

thứ
c
 Ví dụ : Tập hợp là một ADT với các thao
Vũ Anh Dũng - Khoa CNTT 3
tác : add, remove, find, union,…
Danh sách (List)
 Danh sách tổng quát có dạng A
0
,A
1
,
A
2
,
…
,
A
N
-
1

2
,,
N
-
1
 Kích thước N và nếu N=0 : danh sách rỗng
Một ố th tá hổ biế

Một
s
ố

th
ao
tá
c p
hổ

biế
n :
 printList : in danh sách

makeEmpty
:
làm rỗng danh sách

makeEmpty
:

làm


rỗng

danh

sách
 find : trả về vị trí lần đầu tiên một phần tử xuất
hiện tron
g
danh sách
Vũ Anh Dũng - Khoa CNTT 4
g
Danh sách (List)
 Một số thao tác phổ biến (tiếp) :
 findKth : trả v
ề

p
h
ầ
n tử ở v
ị
trí c
ụ
th
ể
p ị ụ
 insert : thêm 1 phần tử vào danh sách
 remove : xóa 1
p

h
ầ
n tử khỏi danh sách
p
Vũ Anh Dũng - Khoa CNTT 5
Sử dụng mảng để
cài đặt danh sách
 Các thao tác :

printList
:
thực
hiện
trong
thời
gian
tuyến
tính

printList
:

thực
hiện
trong
thời
gian
tuyến
tính
 findKth : chiếmthờigianhằng số


insert
và
remove
đòi
hỏi
tốn
kém

insert

và
remove

đòi
hỏi
tốn
kém
nhiềuthời gian (Ví dụ : trường
hợp thêm vào vị trí đầu tiên là
tốn kém thời gian nhất)
 Trườn
g
h
ợp
dùn
g
mản
g
lưutrữ danh sách

Vũ Anh Dũng - Khoa CNTT 6
g
ợp
g
g
không phảilàlựachọntốtnhất
Danh sách liên kết(LinkedList)
 Hình ảnh về danh sách liên kết
ế
 Danh sách liên k
ế
t tránh được việc chèn và
xóa phần tử theo chi phí tuyến tính (dịch
ể ế ố ầ
chu
yể
n liên ti
ế
p 1 s
ố
ph
ầ
n tử)
Vũ Anh Dũng - Khoa CNTT 7
Danh sách liên kết(LinkedList)
 Danh sách liên kết :

Chuỗi các nút (node)

Chuỗi


các

nút

(node)
 Không cần lưu trữ liền kề trong bộ nhớ

Mỗi nút chứaphầntử và liên kết đến nút tiếp

Mỗi

nút

chứa

phần

tử

và

liên

kết

đến

nút


tiếp

theo (next link)

Nút cuối cùng có next link là NULL

Nút

cuối

cùng

có

next

link

là

NULL
Vũ Anh Dũng - Khoa CNTT 8
Danh sách liên kết(LinkedList)
 Phép xóa phần tử (remove):
ầ
 Phép thêm ph
ầ
n tử (insert):
Vũ Anh Dũng - Khoa CNTT 9
Danh sách liên kết(LinkedList)

 Loạibỏ mụccuối cùng :

P
hải tìm
mục
phía
trước
mục
cuối
cùng

P
hải

tìm

mục
phía
trước
mục
cuối
cùng
 Đổi liên kếtnext của nó thành NULL

Cập
nhật
liên
kết
duy
trì

nút
cuối
cùng

Cập
nhật
liên
kết
duy

trì
nút
cuối
cùng
 Có thể dùng ds liên kết đôi (nốikép):
Vũ Anh Dũng - Khoa CNTT 10
GiớithiệuSTL
 Ba thành phần chính của STL :

Container (Collection) :
các
cấu
trúc
dữ
liệu
sẵn

Container

(Collection)


:

các
cấu
trúc
dữ
liệu
sẵn
có như List, Vector, Set,….

Iterator
:
giống
con
trỏ
,
dùng
để
truy
cập
các
Iterator
:

giống
con

trỏ
,


dùng
để
truy
cập
các
phầntử trong Container
 Al
g
orithms : Các thu
ậ
t toán thao tác d
ữ
li
ệ
u
,

g
ậ
ệ
,
tìm kiếm, sắpxếp, …
Vũ Anh Dũng - Khoa CNTT 11
Vector
 Lợi thế củaviệcsử dụng vector là nó có thể
đánh
chỉ
số
trong

thời
gian
hằng
.
đánh
chỉ
số
trong
thời
gian
hằng
.
 Bấtlợicủacủa nó là thao tác chèn thêm các
mục
mới
và
loại
bỏ
các
mục
hiện
có
là
tốn
mục
mới
và
loại
bỏ
các

mục
hiện
có
là
tốn
kém, trừ khi những thay đổinàyđượcthực
hiện
ở
cuối
vector
hiện
ở

cuối
vector
.
Vũ Anh Dũng - Khoa CNTT 12
List
 Lợi thế củaviệcsử dụng list là việcchèn
thêm
mục
mới
và
việc
loại
bỏ
các
mục
hiện
thêm

mục
mới
và
việc
loại
bỏ
các
mục
hiện
có là chi phí thờigianthấp

Bất
lợi
là
danh
sách
không
dễ
dàng
có
thể

Bất
lợi
là
danh
sách
không
dễ
dàng

có
thể
đánh chỉ số.
Vũ Anh Dũng - Khoa CNTT 13
Vector và List trong STL
 Cả vector và list đềucómộtsố phương thức
chung
:
chung
:
 int size( ): trả về kích thướchiệntạicủa
đ
ố
itư
ợ
n
g
chứa
(
container
)
.
ợ g
()
 void clear( ): xóa toàn bộ container.

bool
empty( )
:
trả về true nếu đốitượng

bool
empty(

)
:

trả

về

true

nếu

đối

tượng

chứa không bao chứa phần tử nào, và false nếu
ngược lại.
Vũ Anh Dũng - Khoa CNTT 14
Vector và List trong STL
 void push_back( const Object & x ): thêm x vào cuối danh
sách.
ố ố
 void pop_back( ): loại bỏ đ
ố
i tượng ở cu
ố
i danh sách.

 const Object & back( ) const: trả về đối tượng ở cuối của
danh sách (mộthàmbiến đổitrả về một tham chiếucũng
danh

sách

(một

hàm

biến

đổi

trả

về

một

tham

chiếu

cũng

được cung cấp).
 const Object & front ( ) const: trả về đối tượng ở đầu của
ế ổ ề ế
danh sách (một hàm bi

ế
n đ
ổ
i trả v
ề
một tham chi
ế
u cũng
được cung cấp).
Vũ Anh Dũng - Khoa CNTT 15
Vector và List trong STL
 Hai phương thứcsauđây chỉđược cung cấp
cho
list (
nối
kép
):
cho
list

(
nối
kép
):
 void push_front( const Object & x ): thêm x vào
đ
ầ
u danh sách.
 void pop_front ( ): loạibỏđốitượng ở đầucủa
danh sách.

Vũ Anh Dũng - Khoa CNTT 16
Vector và List trong STL
 Các phương thứccủa Vector:
 v.
[
idx
]
: trả vềđốitư
ợ
n
g
ở v
ị
trí idx tron
g
[
]
ợ g
ị
g
vector, không có sự kiểm tra ranh giới.
 v.at(int idx): trả vềđốitượng ở vị trí idx
trong vector
 int capacity( ): kích thướccóthể lưutrữ
t ớ
khi
ấ
hát
l i
ấ

hát
l i
ẽ
tă
ấ
đôi
t
rư
ớ
c
khi
c
ấ
p
phát
l
ạ
i
, c
ấ
p
phát
l
ạ
i
s
ẽ
tă
ng g
ấ

p
đôi
.
 void reserve(int newCapacity): thiết
lập
dung
lượng
mới
Vũ Anh Dũng - Khoa CNTT 17
lập
dung

lượng
mới
.
Iterator
 Trên danh sách đòi hỏi khái niệmvề vị trí,
trong
STL
vị
trí
được
đại
diện
bởi
iterator
trong
STL

vị

trí
được
đại
diện
bởi
iterator
 Trong list<string>, vị trí đượcthể
hiện
bởi
list<string>::
iterator
hiện
bởi
list<string>::
iterator
 Trong vector<int>, vị trí đượcthể hiện
bởi
vector<
int
>::
iterator
bởi
vector<
int
>::
iterator
Vũ Anh Dũng - Khoa CNTT 18
Iterator
 Trong STL list và các containers class trong
TLD,

đều
có
hai
phương
thức
:
TLD,

đều
có
hai

phương
thức
:
 iterator begin( ) trả về iterator
đầu
tiên
đầu
tiên
 iterator end( ) trả về iterator
ối
ù
cu
ối
c
ù
n
g
Vũ Anh Dũng - Khoa CNTT 19

Iterator
 Các phép toán trên iterator

itr
++
và
++
itr
:
chuyển
iterator
itr
tới

itr
++

và
++
itr
:

chuyển
iterator
itr
tới
vị trí tiếptheo
*
itr
:

truy
cập
đến
phần
tử
được
trỏ
tới

*
itr
:

truy
cập
đến
phần
tử
được
trỏ
tới
ở vị trí của iterator itr
 Ví dụ :
for( vector<int>::iterator itr = v.begin( ); itr !=
v.end
();++
itr
)
Vũ Anh Dũng - Khoa CNTT 20
v.end

(

);

++
itr
)
cout << *itr << endl;
Iterator
 Ba thao tác phổ biếnnhất đòi hỏi các
iterator đólàthêmvàlo
ạ
i
b
ỏ khỏidanh
ạ
sách (hoặc vector hoặc list)

iterator
insert(
iterator
pos,
iterator
insert(
iterator
pos,

const Object &x): thêm x vào danh sách,
trướcvị trí được đưarabởi iterator pos.
 iterator erase( iterator pos ):

loại bỏ đối tượng ở vị trí được cho bởi iterator,
ề ế
Vũ Anh Dũng - Khoa CNTT 21
trả v
ề
iterator là vị trí ti
ế
p theo
Iterator
 Ba thao tác phổ biếnnhất đòi hỏi các
iterator đólàthêmvàlo
ạ
i
b
ỏ khỏidanh
ạ
sách (hoặc vector hoặc list) (tiếp)

iterator erase(iterator
start,
iterator

erase(iterator

start,

iterator end):loại bỏ tất cả các mục bắt
đầu ở vị trí start, cho tới nhưng không bao gồm
end
Vũ Anh Dũng - Khoa CNTT 22

Xóa các phầntử lẻ sử dụng
Iterator
1 template <typename Container>
2 void removeEveryOtherItem( Container & lst )
3
{
{
4 typename Container:iterator itr = lst.begin( );
5 while ( itr != lst.end( ) )
6
{
{
7 itr = lst.erase( itr );
9 if( itr != lst.end( ) )
10
++
itr
;
10

itr
;
11 }
12 }
Vũ Anh Dũng - Khoa CNTT 23
Const_Iterator
• iterator begin( )
• const_iterator begin( ) const
• iterator end
(


)
()
• const_iterator end( ) const
void print( const list < int> & lst, ostream & out = cout )
{
typename Container::iterator itr = lst.begin( );
while( itr != lst.end( ) )
{
*
i
dl
out <<
*
i
tr << en
dl
;
*itr = 0; // Chỗ này có thể bị lỗinếu dùng const_iterator
itr++;
}
Vũ Anh Dũng - Khoa CNTT 24
}
}
In một Collection
1 template <typename Container>
2 void printCollection( const Container & c, ostream & out = cout )
3 {
i
4

i
f( c.empty( ) )
5 out << "(empty)";
6 else
7 {
8 typename Container::const_iterator itr = c.begin( );
9 out << "[ " << *itr++; // In ra mục đầu tiên
10
11 while ( itr != c.end( ) )
12 out << ", " << *itr++;
13 out << " ]" << endl;
14 }
15
}
Vũ Anh Dũng - Khoa CNTT 25
}
In một đốitượng chứabấtkỳ