bài giảng cấu trúc dữ liệu và giải thuật TIẾN SĨ KIM
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (616.41 KB, 36 trang )
Bài gi ng c u trúc d li u và gi i thu t
Trang 71
Bài gi ng c u trúc d li u và gi i thu t
Trang 0
KHOA CÔNG NGH THÔNG TIN
B
MÔN KHOA H C MÁY TÍNH
-----------o0o---------
Tài li u tham kh o
[1]
Xuân Lôi, C u trúc d li u và gi i thu t,
[2]Nguy)n
HBK Hà N i
c Ngh-a, C u trúc d li u và gi i thu t, HBK Hà N i, 2012
[3]Tr n H nh Nhi–D
ng Anh
c, Nh p môn c u trúc d li u và gi i thu t,
HKHTN-
HQG TPHCM.
[4]Jhon Bentley, Nh ng viên ng c trong k thu t l p trình.
[5]Robert L. Kruse, Alexander J. Ryba, Data Structures and Program Design in C++,
Prentice Hall, 2000.
[6]Mark Allen Weiss, Data Structures and Algorithm Analysis in Java, PEARSON, 2012.
BÀI GI NG
C U TRÚC D LI U VÀ GI I THU T
(l u hành n i b )
Bài gi ng c u trúc d li u và gi i thu t
Trang 1
Bài gi ng c u trúc d li u và gi i thu t
H4C PH5N C U TRÚC D
Trang 70
LI U VÀ GI I THU T ( 6 S7 17)
Th"i gian làm bài: 90 phút
Câu 1: (3 i m).
L i gi i thi u
a. Cho dãy n s nguyên ao, a1,…,an-1 và m t s nguyên x. Hãy vi t gi i thu t tìm ki m nh
phân ki m tra giá tr x có trong dãy s trên hay không ?
C u trúc d li u và gi i thu t là h c ph n b t bu c thu c kh i ki n th c c s ngành
c a sinh viên các chuyên ngành công ngh thông tin và c ng là n i dung quan tr ng các k
thi t t nghi p, thi hoàn ch nh i h c các chuyên ngành công ngh thông tin.
T p bài gi ng này trình bày các ch
bài t p v :T ng quan v c u trúc d li u và
gi i thu t, tìm ki m, s p x p, c u trúc danh sách liên k t và c u trúc cây theo ngôn ng
C/C++. M i ch
c thi t k g m các ph n: Tóm t t lý thuy t, m t s d ng bài t p i n
hình và m t s bài t p ch n l c. Ph n cu i c a t p bài gi ng có b sung m t s
thi sinh
viên t rèn luy n k n ng phân tích v n bài toán.
T p bài gi ng này
c biên so n
làm tài li u tham kh o khi gi ng các h c ph n
c u trúc d li u và gi i thu t h
i h c. Chúng tôi xin trân tr ng gi i thi u v i b n c t p
bài gi ng này và hy v ng r ng nó s! giúp cho vi c h c t p h c ph n c u trúc d li u và gi i
thu t c a sinh viên khoa công ngh thông tin tr "ng # i h c Sài Gòn
c thu n l i h n.
b. Hãy vi t gi i thu t Quick Sort
c. Cho dãy s : 2 8 5
s(p x p dãy n s nguyên ao, a1,…,an-1 theo th t t ng.
7 4 3 6
Hãy minh h a quá trình x p t ng d n dãy s trên theo gi i thu t Quick Sort.
Câu 2: (4 i m).
Cho danh sách liên k t
a. Hãy
n L; m i nút ch a m t s nguyên.
nh ngh-a c u trúc d li u c a danh sách liên k t L.
b. Hãy vi t gi i thu t s(p x p các ph n t l8 n'm v phía tr
c c a danh sách và các ph n t
ch7n n'm v phía cu i c a danh sách.
c. Cho hai danh sách liên k t
n L1 và L2 mà các giá tr c a nó ã
gi i thu t tr n hai danh sách L1, L2 thành m t danh sách L c&ng
c s(p t ng; hãy vi t
c s(p t ng.
Câu 3: (3 i m).
Thành ph H Chí Minh, ngày 06 tháng 09 n m 2009
TÁC GI$
Cho m t cây nh phân tìm ki m T mà m i nút ch a m t s nguyên; là khóa c a nút ó.
a. Hãy
nh ngh-a c u trúc d li u c a cây T.
b. Hãy vi t gi i thu t tính t!ng giá tr c a các nút ch có m t con.
c. Hãy vi t gi i thu t tìm m c c a nút có khóa k (gi s s k ã có trong cây).
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 69
Bài gi ng c u trúc d li u và gi i thu t
Ch
H4C PH5N C U TRÚC D
LI U VÀ GI I THU T ( 6 S7 16)
Th"i gian làm bài: 90 phút
Trang 2
ng 1
T NG QUAN
V C U TRÚC D
LI U VÀ GI I THU T
Câu 1: (3.0 )
a. Vi t gi i thu t s(p x p dãy n s th c ao, a1, a2,...,an-1 gi m d n theo gi i thu t Quick sort.
b. Cho dãy s : 3 9 6 8 5 4 7
Hãy minh h a quá trình s(p t ng d n dãy s trên theo gi i thu t Quick sort.
c. Ch ng minh gi i thu t Merge sort có
ph c t p O(n log n) v i n là s ph n t c a dãy.
d. Hãy tr l i ng(n g n các câu h"i sau:
- M t cây nh phân có chi u cao h có t i a bao nhiêu nút ?
- M t cây nh phân có chi u cao h có t i a có bao nhiêu nút lá ?
- M t cây nh phân thì * m c i có t i a bao nhiêu nút ?
- Cây nh phân y (m i nút u có 2 cây con) có chi u cao h thì có bao nhiêu nút ?
1.1.BÀI TOÁN
Khái ni m bài toán
•
Trong ph m vi tin h c, ta quan ni m bài toán là m t công vi c nào ó mà ta mu n
•
Khi dùng máy tính gi i bài toán, ta c n quan tâm
máy tính th c hi n.
n ba y u t :
gì (Input), c n l y ra thông tin gì (Output) và quá trình ó
a vào máy thông tin
c x lý nh th nào ?
Ví d v m t s bài toán tin h c
ng trình d ng ax2 + bx + c = 0
•
Gi i ph
Câu 2: (3.0 )
•
Tìm t t c ph
Cho danh sách liên k t n L, m i nút ch a m t phân s g m t s và m%u s (gi s t s và
m%u s c a các phân s là các s nguyên d ng).
a. Hãy nh ngh-a c u trúc d li u danh sách liên k t n bi u di)n các phân s .
b. Vi t gi i thu t tìm phân s có giá tr l n nh t.
c. Vi t gi i thu t m s l ng phân s có giá tr n'm trong kho ng (0,1).
•
Cho dãy n s , tìm dãy con t ng dài nh t (dãy con này có th không g m các ph n t
•
Tính 21000.
Câu 3: (4.0 )
Cho cây nh phân tìm ki m T m i nút ch a m t s nguyên; là khóa c a nút ó.
a. Hãy nh ngh-a c u trúc d li u cho cây T
b. Vi t gi i thu t tính t!ng giá tr các nút trong cây.
c. Vi t gi i thu t m xem cây T có bao nhiêu nút có úng hai con.
d. Vi t gi i thu t in khóa c a các nút trên
ng i t nút g c n nút có khóa k (gi s giá
tr k ã có trong cây).
--------------------------------------------------H t-----------------------------------------
ng án
t n quân h u trên bàn c n x n.
liên ti p nhau).
Các b
c gi i m t bài toán
•
Xác
•
Thi t k gi i thu t
•
Vi t ch
•
Ki m th ch
•
Vi t tài li u (G m: n i dung bài toán, gi i thu t, toàn v n ch
nh bài toán
ng trình
ng trình
ng trình, các b ki m
th , thông tin v các tác gi c a các công o n trên và th i i m ch nh s a cu i cùng
các công o n,…).
1.2.GI I THU T
Khái ni m gi i thu t (thu t gi i/thu t toán)
Gi i thu t gi i bài toán là m t th t c xác
th c hi n
thu
c
u ra cho m t
nh bao g m m t dãy h u h n các b
u vào cho tr
cc n
c c a bài toán.
c tr ng c a gi i thu t
•
•
•
u vào (Input): Gi i thu t nh n d li u vào t m t t p nào ó.
u ra (Output): V i m i t p các d li u u vào, gi i thu t a ra các d li u t
ng v i l i gi i c a bài toán.
Chính xác (Precision): Các b c c a gi i thu t
c mô t chính xác.
ng
Bài gi ng c u trúc d li u và gi i thu t
•
•
•
Trang 3
Bài gi ng c u trúc d li u và gi i thu t
H u h n (Finiteness): Gi i thu t c n ph i a
c u ra sau m t s h u h n (có th
r t l n) b c v i m i u vào.
n tr (Uniqueness): Các k t qu trung gian c a t ng b c th c hi n gi i thu t
c
xác nh m t cách n tr và ch ph thu c vào u vào và các k t qu c a các b c
tr c.
T!ng quát (Generality): Gi i thu t có th áp d ng
c xác
nh nh là l
ng tài nguyên các lo i
•
Có hai lo i tài nguyên quan tr ng ó là th i gian và b nh .
•
Ta
n ánh giá th i gian c n thi t
th c hi n gi i thu t mà ta s#
b'ng m t s quy t(c
c nh p theo th t sau: 7 (g c), 34, 2, 1, 15, 9,
d. Cho dãy ch a n s nguyên a0,a1,…,an-1 ã
c (NLR) và th t sau (LRN)
c s(p t ng và m t s nguyên x. S d ng
qui vi t gi i thu t tìm ki m nh phân.
ph c t p tính toán c a m t gi i thu t b t k$ có th d%n t i nh ng bài toán
ph c t p. Tuy nhiên trong th c t ,
b. Minh h a quá trình bi n !i dãy s 26, 8, 24, 16, 4, 20, 12, 34, 2, 10 thành m t heap.
41, 6, 16, 40, 12, 45. Duy t cây T theo th t tr
g i là th i gian tính c a gi i thu t.
nh
a. Minh h a quá trình s(p t ng d n dãy s 26, 8, 24, 16, 4, 20, 12, 34, 2, 10 theo gi i thu t
c. V# cây nh phân tìm ki m T v i các nút
mà gi i thu t òi h"i s d ng.
xác
Th"i gian làm bài: 90 phút
Merge sort.
ph c t p tính toán c a gi i thu t
c bi t quan tâm
LI U VÀ GI I THU T ( 6 S7 15)
Câu 1: (4 i m)
gi i m i bài toán có d ng ã cho.
ph c t p c a gi i thu t
•
H4C PH5N C U TRÚC D
Trang 68
i v i m t s gi i thu t ta c&ng có th phân tích
c
n gi n là Quy t(c c ng và quy t(c nhân.
e. Cho dãy ch a n s nguyên a0,a1,…,an-1. Vi t gi i thu t s(p dãy s trên theo th t t ng
theo gi i thu t Heap sort.
Câu 2: (3 i m)
a. Cho danh sách liên k t
M t s l p gi i thu t
n L; m i nút ch a m t s nguyên. Hãy
li u cho danh sách liên k t
•
O(1):
H'ng s (constant)
b. Vi t gi i thu t
•
O(log n):
Logarithmic
Câu 3: (3.0 i m)
•
O(n):
Tuy n tính (linear)
•
O(n log n):
Trên tuy n tính (superlinear)
•
O(n2):
Bình ph
•
O(n3):
B c 3 (cubic)
qui
nh ngh-a c u trúc d
n L. Vi t gi i thu t tìm giá tr l n nh t c a danh sách L.
chuy n !i m t s t h
m th p phân sang h
m c s b.
Cho cây nh phân tìm ki m T; m i nút ch a m t s nguyên; là khóa c a nút ó.
a. Hãy
ng (quadratic)
•
O(nk):
a th c (polynomial) (k ≥ 1)
•
O(an):
Hàm m& (exponential) (a > 1)
nh ngh-a c u trúc d li u cho cây T
b. Vi t gi i thu t
m xem cây T có bao nhiêu nút lá ?
c. Vi t gi i thu t tính chi u cao c a cây.
d. Vi t gi i thu t tìm m c c a nút có khóa k (gi s s k ã có trong cây).
--------------------------------------------------H t-----------------------------------------
Bài toán d gi i – khó gi i-không gi i
•
M t bài toán
c
c g i là d) gi i n u nh nó có th gi i
c b*i gi i thu t a th c
(Bài toán tìm dãy con liên ti p có t!ng l n nh t, s(p x p dãy n s ,…)
•
M t bài toán
c g i là khó gi i n u nh nó không th gi i
c b*i gi i thu t a
th c (bài toán li t kê các hoán v c a n s , bài toán li t kê các dãy nh phân chi u dài
n,...). Nh ng bài toán cho
(bài toán cái túi, bài toán ng
•
Bai toán không gi i
n hi n t i v%n ch a tìm
c gi i thu t a th c
gi i
i i du l ch,…)
c n u nh không t n t i gi i thu t
d ng, bài toán v nghi m nguyên c a a th c,…).
gi i (bài toán v tính
Bài gi ng c u trúc d li u và gi i thu t
Trang 67
Bài gi ng c u trúc d li u và gi i thu t
Trang 4
Ví d 1.1. M t s gi i thu t s h c c b n
H4C PH5N C U TRÚC D
LI U VÀ GI I THU T ( 6 S7 14)
a. Ki m tra xem s t nhiên n có ph i là s nguyên t hay không ? (S chính ph
hoàn ch nh, S
Th"i gian làm bài: 90 phút
b. Tìm
Câu 1 (2 ):
c s chung l n nh t c a hai s t nhiên a,b. Tìm b i s chung nh" nh t
c. Tìm USCLN, BSCNN c a n s nguyên d
Hãy vi t hàm
quy( s d ng mã gi )
g n ý t *ng và
hi n th hoán v b n s 1,2,3,4. Hãy trình bày ng(n
ph c t p gi i thu t.
ng, S
i x ng, S Armstrong, S fibonacci).
ng.
d. Phân tích m t s t nhiên n thành tích các th a s nguyên t .
e.
ms l
ng các
c s và tính t!ng các
c s c a m t s t nhiên n.
Câu 2 (2.0 ):
Cho procedure nh sau:
Ví d 1.2.
Procedure P(n,a,b,c,d)
a. Dãy con có t!ng l n nh t
Begin
Cho dãy n s nguyên {a} Dãy con liên ti p là dãy mà thành ph n c a nó là các thành ph n
if n=1 then <chuy n t c c a sang c c c>
liên ti p nhau trong {a}, ta g i t!ng c a dãy con là t!ng t t c các thành ph n c a nó. Tìm
else
t!ng l n nh t trong t t c các t!ng c a các dãy con c a {a}
P(n-1,a,b,c,d);
Ch+ng h n n = 7 s sau:
P(1,a,b,c,d);
4 –5
b.
end
các
Hãy vi t hàm s d ng C/C++ tr n hai danh sách (g m hai thành ph n: Int Inf và ListNode*
c cho b*i hai con tr" head1, head2- s(p x p t ng d n theo tr
t là n và m thành m t danh sách
ng Inf, có
c cho b*i head 3- s(p x p gi m d n theo tr
dài n + m. Hãy trình bày ng(n g n cách tính
dài l n
ph c t p gi i thu t.
o ng
c các ch s c a nó ta
ng (<=1 tri u) sao t!ng các
c th c s c a x b'ng y và t!ng
c th c s c a y b'ng x.
c a chúng là l n nh t.
H
ng d n gi i câu a.
Gi i thu t 1:
c ch y c a gi i thu t s(p x p tr n (Merge sort) cho dãy:
51,20,11,1,10,29,15,6,7.
Hãy vi t ch
-7
d. Cho dãy ch a n s nguyên ai (i=0..n-1), n<=30000, |ai|<=10000. Tìm ba s sao cho tích
ng Inf có
Câu 4 (3.0 ):
Mô t t ng b
3
c s nguyên t ? (Ví d s 5, 13,131 là th"a). (Thu t toán sàng nguyên t )
c. Tìm các s x,y nguyên d
Câu 3 (3.0 ):
l
2
m xem có bao nhiêu s nguyên t <=100 tri u mà khi
c&ng thu
quy khi g i hàm P(4,x,y,z,w)
next) –
–4
Thì k t qu t!ng dãy con c n tìm là 7.
P(n-1,b,d,c,a);
V# cây
6
ng trình s(p x p t ng d n gi i s theo gi i thu t s(p x p tr n.
--------------------------------------------------H t-----------------------------------------
Gi i thu t
L ≤ U ≤ n;
n gi n nh t có th vi t ngay là: xét t t c các c p s nguyên L và U th"a mãn 1 ≤
i v i m i c p nh v y ta tính t!ng c a dãy con a[L..U] và so sánh t!ng này v i
giá tr l n nh t hi n có:
for (L=1;L<=n;L++)
for (U=L;U<=n;U++)
{ sum=0;
for (int I=L;I<=U;I++)
sum=sum+a[I];
maxsofar=max(maxsofar,sum);
}
ch
ng trình này tuy ng(n và d) hi u, tuy nhiên gi i thu t này có
ph c t p là O(n3)
Bài gi ng c u trúc d li u và gi i thu t
Trang 5
Bài gi ng c u trúc d li u và gi i thu t
Trang 66
Gi i thu t 2:
Ta có th c i ti n gi i thu t trên
H4C PH5N C U TRÚC D
ph c t p là O(n2) b'ng cách s d ng
có gi i thu t v i
LI U VÀ GI I THU T ( 6 S7 13)
Th"i gian làm bài: 90 phút
h th c :
T!ng a[L..U]= T!ng a[L..U-1]+a[U]
Câu 1(2 ):
maxsofar=0;
Hãy vi t hàm
for (L=1;L<=n;L++)
m ng và
{
quy (s d ng mã gi )
dài c a nó là tham s
tìm và tr v giá tr ch7n và l n nh t trong m t
u vào c a hàm.
Câu 2(2 ):
sum=0;
Hãy vi t hàm tính t!ng dãy con l n nh t trong m t dãy cho tr
for (U=L;U<=n;U++)
trong m t m ng ) s d ng C/ C++ v i m ng và
{
Trình bày ng(n g n ý t *ng và
sum=sum+a[U];
c (dãy cho tr
dài c a nó là tham s
ph c t p c a gi i thu t. Mô t t ng b
c
c l u tr
u vào c a hàm.
c ch y v i b d
li u sau : 10 -12 2 23 -6 30 20 -13 (bi t r'ng t!ng dãy con l n nh t c a b d li u này là 69).
maxsofar=max(maxsofar,sum);
Câu 3(2 ):
}
Cho procedure nh sau:
}
Procedure P(n,a,b,c,d)
Begin
Gi i thu t 3:
if n=1 then <chuy n t c c a sang c c c>
T!ng l n nh t trong dãy con a[1..i] là t!ng l n nh t trong dãy con a[1..i-1](g i là maxsofar)
ese
ho c t!ng l n nh t trong t t c các t!ng c a các dãy con k t thúc t i i (g i là maxendinghere).
P(n-1,a,b,c,d);
Chúng ta có nh n xét r'ng: Dãy con l n nh t k t thúc t i i là dãy con l n nh t k t thúc t i v
c b! sung thêm ph n t a[i] * cu i ho c là dãy con r ng trong tr
trí i-1
dãy con nh n
P(1,a,b,c,d);
ng h p t!ng c a
P(n-1,b,d,c,a);
c là s âm. Ta có gi i thu t nh sau:
end
maxsofar=0;
maxendinghere=0;
V# cây
for (i=1; i<=n;i++)
Câu 4 (2.0 ):
{
Hãy vi t hàm s d ng C/C++ tr n hai danh sách (g m hai thành ph n: Int Inf và ListNode*
maxendinghere=max(maxendinghere+a[i],0);
next) –
maxsofar=max(maxsofar,maxendinghere);
l
quy khi g i hàm P(4,x,y,z,w)
c cho b*i hai con tr" head1, head2- s(p x p t ng d n theo tr
t là n và m thành m t danh sách-
c cho b*i head 3- s(p x p t ng d n theo tr
dài n+m. Hãy trình bày ng(n g n cách tính
}
1
2
3
4
5
6
7
a[i]
4
-5
6
-4
2
3
-7
maxendinghere
4
0
6
2
4
7
0
maxsofar
4
4
6
6
6
7
7
Gi i thu t 3 này có
dài l n
ng Inf có
ph c t p gi i thu t.
Câu 5 (2.0 ):
Minh h a cho gi i thu t 3:
i
ng Inf có
ph c t p là O(n).
Mô t
t ng b
c ch y c a gi i thu t s(p x p ki u chèn (Insertion sort) cho dãy:
41,10,51,3,1,9,21,6,5.
Hãy vi t ch ng trình s(p x p t ng d n gi i s theo gi i thu t s(p x p chèn.
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 65
Bài gi ng c u trúc d li u và gi i thu t
1.3.GI I THU T
H4C PH5N C U TRÚC D
LI U VÀ GI I THU T ( 6 S7 12)
Th"i gian làm bài: 90 phút
Trang 6
QUI
Gi i thu t
qui là gi i thu t t g i
Phân lo i
quy
n chính mình v i d li u vào có kích th
c nh" h n.
•
Câu 1 (2 i m)
a. Hãy vi t các hàm s(p x p theo gi i thu t chèn tr c ti p và n!i b t.
b. Cho dãy g m các s nguyên sau:
99
52
33
84
Hãy mô ph"ng các b
21
75
68
c s(p x p t ng d n dãy s trên b'ng các gi i thu t chèn tr c ti p và
n!i b t.
Câu 2 (2 i m)
a. Hãy v# l i cây nh phân T bi t khi duy t cây T ta
NLR:
15 1 2 4 7 10 21 3 9 19
LNR:
2 1 7 4 21 10 15 9 19 3
c dãy s sau:
Ví d 1.3.
b. N u ta xóa 1 ph n t kh"i cây BST và sau ó thêm nó vào l i cây. H"i: hình d ng c a cây
ó b thay !i không? Gi i thích?
n
ng án
1.4.C U TRÚC D
ng a và b (có th có hàng ngàn ch s ). S d ng danh sách liên k t
bi u di)n cho s nguyên a và s nguyên b. Hãy vi t hàm tính t!ng a + b.
c. Cho hai danh sách liên k t
vào l3
l3 c&ng
vào l1
l1 sau ó c&ng
n l1,l2 ch a các s nguyên. Hãy tr n các ph n t c a l1 và l2
c s(p x p t ng (hãy l i gi i bài toán b'ng cách chèn các ph n t c a l2
c s(p t ng (l1 ch a các ph n t c a l1 và l2 tr
c ó).
Câu 4 (3 i m)
Cho cây nh phân tìm ki m T, m i nút ch a m t s nguyên. Hãy vi t các hàm th c hi n các
yêu c u sau:
a.
a. Tìm t t c các dãy nh phân chi u dài n.
b. Tìm t t c ph
Câu 3 (3 i m)
c. Cho hai s nguyên d
quy tuy n tính (còn g i là quy n)
M t hàm
c g i là
quy tuy n tính n u m t l n g i hàm nó ch phát sinh t i a
m t l i g i quy.
•
quy nh phân
M t hàm
c g i là
quy nh phân n u m i l n g i hàm nó phát sinh t i a hai l i
g i quy.
•
quy h t ng
Hai hàm P,Q
c g i là
quy h t ng n u hàm P có l i g i n hàm Q và ng c
l i m t cách t ng minh hay ti m ,n.
•
quy phi tuy n ( quy ph c)
M t hàm
c g i là quy phi tuy n n u m i l n g i hàm thì nó phát sinh ra kho ng
n l n g i quy - thông th ng l i g i quy
c t trong các vòng l p.
m các nút là có giá tr > n1 và < n2
b. Xóa t t c các nút mang giá tr là s nguyên t .
--------------------------------------------------H t-----------------------------------------
Ki u d li u
•
•
•
c
t n quân h u trên bàn c n x n.
LI U
c tr ng b*i:
T p các giá tr
Cách bi u di)n d li u
c s d ng chung cho t t c các giá tr này
T p các phép toán có th th c hi n trên t t c giá tr
C u trúc d li u (data structures) là m t h các bi n, có th có các ki u d li u khác nhau,
c liên k t l i theo m t cách th c nào ó. Các c u trúc d li u
•
•
•
C u trúc d li u c s*: int, double, float,…
C u trúc d li u tuy n tính: m ng, danh sách liên k t, ng n x p, hàng
C u trúc d li u phi tuy n: Cây,
th , b ng b m,…
i,…
Ch n c u trúc d li u nào ?
•
•
Bài toán c n gi i quy t có nh ng thao tác nào là th ng xuyên nh t ? T ó mà ch n
c u trúc d li u phù h p.
Tùy theo bài toán mà ch n l a c u trúc d li u thích h p
t i u v th i gian ho c
t i u v b nh .
Ví d 1.4.
a. Tính t!ng, hi u, tích, th ng hai phân s .
b. Cho dãy các phân s (gi s các t s và m%u s c a các phân s là các s nguyên). Tính
t!ng giá tr c a các phân s trong m ng (k t qu là phân s * d ng t i gi n).
c. Cho m ng m t chi u g m n t a
i m (gi s hoành
và tung
c a các i m là các
s nguyên). Tìm m t c p i m g n nhau nh t.
d. Tính t!ng và tích hai a th c P,Q (trên tr ng s nguyên).
e. Tính t!ng hai s nguyên l n A,B (m i s có th có hàng ngàn ch s ).
Bài gi ng c u trúc d li u và gi i thu t
Trang 7
Bài gi ng c u trúc d li u và gi i thu t
Bài t p
Vi t ch
Trang 64
LI U VÀ GI I THU T ( 6 S7 11)
H4C PH5N C U TRÚC D
Th"i gian làm bài: 90 phút
ng trình hoàn ch nh cho các bài toán sau ây
BT1-1.
Cho dãy n s nguyên d ng a0,a1,...,an-1 có giá tr trong ph m vi 0..32767.
a. Tìm ph n t l n nh t (tính t!ng, m s nguyên t , tìm s nguyên t l n nh t,…)
b. Xóa m t ph n t t i v trí th k,
c. Chèn m t ph n t x vào v trí k,
d. Tìm dãy con liên ti p t ng dài nh t.
e. Tìm giá tr l n th k c a dãy.
f. Tìm t n s xu t hi n c a các s .
g. Hãy chuy n k ph n t
u tiên c a dãy v cu i dãy.
BT1-2.Cho hai s nguyên l n a và b; trong ó a có m ch s và s b có n ch s . Vi t ch
Câu 1 (2 i m)
a. Nêu các
nh ngh-a v cách t! ch c danh sách liên k t sau: Danh sách liên k t
n, danh
sách liên k t kép, danh sách liên k t vòng, danh sách có nhi u m i liên k t.
b. Hãy cài
t gi i thu t tìm ki m nh phân b'ng
qui.
c. Hãy cho bi t s l n so sánh c a gi i thu t tìm ki m nh phân trong tr
t t nh t, trung bình. Hãy cho bi t
ng h p x u nh t,
ph c t p c a gi i thu t này.
Câu 2 (2 i m)
ng
S d ng Stack, vi t ch
màn hình s
BT1-3.Vi t ch
Ví d': - Nh p vào m t s nguyên: 10245
ng trình tính n! V i n <=1000
BT1-4.
c cho nh sau :
a. Dãy An
A1=1
An=n(A1+A2+…+An-1)
Vi t hàm tính An có s d ng quy
b. Cho dãy s xn
c nh ngh-a nh sau:
x0 = 1; x1 = 2; xn = nx0 + (n - 1)x1 + … + xn-1
Vi t hàm quy tính xn (v i n ≥ 0).
c. Dãy An
c cho nh sau :
A1=1; A2n=n + An + 2; A2n+1=n2 + An.An+1 +1
Vi t hàm tính An b'ng quy
Viêt hàm tính An b'ng cách không s d ng quy.
BT1-5. t n quân H u lên bàn c Vua sao cho chúng không kh ng ch l%n nhau.
o ng
ng trình nh p vào m t s nguyên, không âm b t k$, sau ó xu t ra
trình th c hi n các phép c ng, tr , nhân, chia (l y ph n nguyên) hai s nguyên l n.
c th t các ch s c a s nh p vào.
- S nguyên * d ng
c: 54201
Câu 3 (3 i m)
a. Cho hai danh sách liên k t
n l1,l2 ch a các s nguyên. Hãy n i danh sách l2 vào sau
danh sách l1.
b. Khai báo m t danh sách liên k t
n trong ó, m i ph n t l u tr d li u g m: Giá tr
c a nút ó (ki u s nguyên) và t n s xu t hi n c a giá tr (ki u s nguyên). Hãy vi t hàm
rút g n danh sách liên k t
n theo d ng sau: N u các ph n t có cùng giá tr thì ch gi
l i m t ph n t và t n s c a giá tr
ó thì
c c ng thêm 1.
Câu 4 (3 i m)
Gi s ta có m t t p h p g m n ph n t ki u s nguyên c n l u tr b'ng c u trúc cây nh phân
tìm ki m (BST). L u ý r'ng các ph n t có th trùng nhau. Hãy trình bày m t
a.
trúc cây BST sao cho:
b.
a. L u tr và tìm ki m
Tìm t t c m i l i gi i khi n=8.
Có bao nhiêu l i gi i khi n=16, n=32 ?
BT1-6.
a. Vi t ch ng trình tìm các dãy hoán v c a n ph n t {1,2,3,…,n}
b. Bài toán tìm t t c các dãy nh phân chi u dài n.
c. Tìm các t! h p ch p k c a n ph n t
d. Tìm các ch nh h p không l p ch p k c a n ph n t .
BT1-7.
a. Tìm các b k s có t!ng b'ng m cho tr c (k,m là các s nguyên d ng).
b. Tìm m t t p con có t!ng l n nh t không l n h n m cho tr c (m là s nguyên d ng).
c. Tìm m t cách chia n s trên thành hai ph n sao cho t!ng các ph n t c a m i ph n chênh
l ch nhau là ít nh t.
o ng
hi n
cs l
c các ph n t . V i các tr
xu t v c u
ng h p ph n t trùng nhau, c n th
ng ph n t trùng l p.
b. Mô t c u trúc b'ng C/C++
c. Vi t hàm cho hai thao tác chính: Thêm ph n t , xóa ph n t .
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 63
Bài gi ng c u trúc d li u và gi i thu t
Ch
LI U VÀ GI I THU T ( 6 S7 10)
H4C PH5N C U TRÚC D
Trang 8
ng 2
TÌM KI M VÀ S P X P
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
a. Nêu các
2.1.PH
NG PHÁP TÌM KI M
nh ngh-a sau: Cây nhi phân, cây nh phân tìm ki m, cây nh phân cân b'ng hoàn
2.1.1.Bài toán tìm ki!m
toàn, cây nh phân cân b'ng.
b. b.Hãy cài
t gi i thu t tìm ki m tuy n tính
c. Hãy cho bi t s l n so sánh c a gi i thu t tìm ki m tuy n tính trong tr
t t nh t, trung bình. Hãy cho bi t
ng h p x u nh t,
ph c t p c a gi i thu t này.
Câu 2 (2 i m)
Vi t các hàm sau ây:
Cho dãy n s nguyên a0,a2,...,an-1 và m t s nguyên x. Hãy tìm xem x có thu c vào dãy s trên
hay không ? N u tìm
c * v trí th i thì xu t k t qu là i, ng c l i n u không tìm th y thì
xu t k t qu là –1 (chú ý dãy b(t u t ch s 0, n u dãy có nhi u s b'ng x thì xu t v trí i
nh" nh t).
Sau ây là hai gi i thu t tìm ki m th ng
c s d ng nh t.
a. Thêm m t ph n t x vào stack S b'ng cách dùng danh sách liên k t.
2.1.2.Tìm ki!m tuy!n tính
b. Xem thông tin c a ph n t *
B(t u t ph n t th nh t a[0], ta l n l t so sánh x v i các giá tr a[i]. N u có a[i] b'ng x
thì i chính là k t qu c n tìm và k t thúc gi i thu t. N u trong dãy không có s a[i] nào b'ng x
nh stack S b'ng cách dùng danh sách liên k t.
c. Thêm m t ph n t x vào cu i hàng
d. Xem thông tin c a ph n t *
i Q b'ng cách dùng danh sách liên k t.
u hàng
i Q b'ng cách dùng danh sách liên k t.
Câu 3 (3 i m)
Cho m t danh sách liên k t
n trong ó, m i ph n t ch a m t s nguyên
a. Vi t hàm xóa t t c các s nguyên t trong danh sách.
b. Hãy tìm t n s xu t hi n c a các giá tr .
Câu 4 (3 i m)
Cho cây nh phân tìm ki m T có khóa là các s nguyên.
a. Vi t hàm tìm m c c a m t nút có giá tr x.
b. Vi t hàm in các nút * m c k c a cây.
--------------------------------------------------H t-----------------------------------------
thì xu t k t qu là –1 và c&ng k t thúc gi i thu t.
int LinearSearch ( int a[], int n, int x )
{
int i = 0;
while ( i
if( i==n)
return -1; // tìm h t nh ng không có x
return i; //
tìm th y a[i] là ph n t có khóa x
}
Hi u qu c a gi i thu t
c nâng cao b'ng cách t thêm ph n t c m canh (sentinel)
* cu i m ng (a[n]=x) b o m r'ng trong dãy a[i] lúc này luôn có ph n t b'ng x và vòng
l p while luôn k t thúc. Do ó không c n ki m tra i u ki n (i
{int i = 0; // m ng g m n ph n t t a[0]...a[n-1]
a[n] = x; // thêm ph n t th n+1
while (a[i]!=x)
i++;
if( i==n)
return -1; // tìm h t nh ng không có x
return i; // tìm th y x t i v trí i
}
Gi i thu t tìm ki m tuy n tính có
ph c t p tính toán là O(n).
Bài gi ng c u trúc d li u và gi i thu t
Trang 9
Bài gi ng c u trúc d li u và gi i thu t
Trang 62
2.1.3.Tìm ki!m nh" phân
(v i ph
ó là th t không gi m).
Gi s dãy tìm ki m hi n hành bao g m các ph n t aleft,…,ar ght.
G i midle=(left+right)/2
Nh n xét r'ng n u x > a[i] thì x ch có th xu t hi n bên ph i a[i] - ngh-a là trong
o n [amidle+1, aright] c a dãy, ng c l i n u x < a[i] thì x ch có th xu t hi n bên trái a[i] trong o n [aleft, amidle-1] c a dãy, nh v y gi i thu t s# thu g n ph m vi tìm ki m m t cách
áng k . M i l n so sánh lo i
c m t n a thông tin không có ích.
Ví d 2.1: Cho dãy s
1
3
4
5
6
7
8
9
10 12
C n tìm ph n t x=3
B c 1: left=0, right=9, mid=4, a[mid]= 6
Do x < a[mid] nên right=3.
Do left<=right ti p t c qua b c 2.
B c 2: left=0, right=3, mid=1, a[mid]= 3
Do x = a[mid] nên v trí c n tìm là mid =1.
Gi s c n tìm ph n t x=11
B c 1: left=0, right=9, mid=4, a[mid]= 6
Do x > a[mid] nên left=5.
Do left<=right ti p t c qua b c 2.
B c 2: left=5, right=9, mid=7, a[mid]= 9
Do x > a[mid] nên left=8.
Do left<=right ti p t c qua b c 3.
B c 3: left=8, right=9, mid=8, a[mid]= 10
Do x > a[mid] nên left=9.
Do left<=right ti p t c qua b c 4.
B c 4: left=9, right=9, mid=9, a[mid]= 12
Do x < a[mid] nên right=8.
Do left> right vòng l p k t thúc và k t qu tr v là -1
Cài %t theo ki u quy
int BinarySearch_Recursive(int a[],int n,int x,int left,int right)
{ if (left>right) return -1;
int mid=(left+right)/2;
if (x==a[mid]) return mid;
if (x
return BinarySearch_Recursive(a,n,x,mid+1,right);
}
LI U VÀ GI I THU T ( 6 S7 9)
H4C PH5N C U TRÚC D
ng pháp tìm ki m nh phân thì dãy n s a0,a1,a2,..,an-1 ph i có th t - gi s
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
a. Hãy
nh ngh-a m t heap và nêu các tính ch t c a m t heap
b. Hãy hi u ch nh dãy s sau ây thành m t heap
12
2
8
5
1
6
4
15
Câu 2 (2 i m)
a. Hãy vi t hàm s(p x p ch n tr c ti p b'ng cách s d ng danh sách liên k t
n.
Yêu c u thay !i các m i liên k t (thao tác trên vùng next).
b. B'ng các thao tác c b n trên hàng
i sau ây, hãy vi t hàm tính t!ng các ph n t c a
m ng m t chi u n ph n t .
int Qisempty(List Q) :
ki m tra hàng
void Qpush(List &Q, int x)
:Thêm m t ph n t vào cu i hàng
int Qpop(List &Q)
Trích/h y ph n t * âu hàng
:
i r ng
i
i
Câu 3 (3 i m)
a. Cho m t danh sách liên k t
nguyên x vào danh sách l
n l ch a các s nguyên ã có th t t ng. Hãy chèn m t s
l v%n có th t t ng.
b. b.Cho m t danh sách liên k t
n l ch a các s nguyên. Hãy gi l i m t giá tr trong các
giá tr trùng nhau c a l.
Câu 4 (3 i m)
a. Hãy vi t ph n khai báo c u trúc d li u
mô t m t danh sách liên k t
n l mà m i
ph n t là m t s nguyên. Hãy vi t hàm s(p x p các ph n t trong danh sách l theo chi u
t ng d n.
b. Hãy vi t ph n khai báo c u trúc d li u
mô t m t cây nh phân tìm ki m mà m i ph n
t là m t s nguyên. Hãy vi t hàm tìm chi u cao c a cây.
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
H4C PH5N C U TRÚC D
Trang 61
LI U VÀ GI I THU T ( 6 S7 8)
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
Hãy vi t hàm s(p x p danh sách t ng d n b'ng cách thay !i m i liên k t.
Câu 2 (2 i m)
Hãy vi t các hàm tìm ki m m t ph n t x trong các tr
Danh sách c n tìm
ng h p:
c bi u di)n b'ng m t m ng m t chi u, danh sách c n tìm
di)n b'ng m t danh sách liên k t
n, danh sách c n tìm
c bi u
c bi u di)n b'ng m t cây nh
phân tìm ki m.
(Các hàm này n u tìm th y tr v giá tr 1, n u không tìm th y tr v giá tr 0).
Câu 3 (3 i m)
a. Cho m t danh sách liên k t
n trong ó, m i ph n t ch a m t s nguyên. Hãy vi t hàm
xóa ph n t có giá tr l n nh t trong danh sách (l u ý: Ch
l n và n u có nhi u ph n t l n nh t gi ng nhau, xóa ph n t
c phép duy t danh sách m t
u tiên).
b. Dùng ng n x p các s nguyên v i các phép toán push,pop. Hãy l p ch
ng trình !i m t
Bài gi ng c u trúc d li u và gi i thu t
Trang 10
Cài %t theo ki u không quy
int BinarySearch(int a[],int n,int x)
{
int left=0,right=n-1,mid;
do
{
mid=(left+right)/2;
if (x==a[mid])
return mid;
else
if (x
else
left=mid+1;
}
while (left<=right);
return -1;
}
Gi i thu t tìm ki m nh phân có ph c t p tính toán là O(log2n)
s th p phân thành s nh phân.
2.2.PH
Câu 4 (3 i m)
Cho cây nh phân tìm ki m T có khóa là các s nguyên.
NG PHÁP S#P X P
2.2.1.Bài toán s$p x!p
a. Li t kê t t c các ph n t c a m t cây nh phân tìm ki m th"a i u ki n giá tr c a ph n t
n'm trong kho ng [Min, Max] cho tr
c.
b. Tìm cây con T có t!ng l n nh t (ch tìm m t cây th"a)
--------------------------------------------------H t-----------------------------------------
Cho m t dãy n s , hãy s(p x p dãy s theo th t t ng d n (ho c gi m d n).
Trong bài gi ng này gi thi t r'ng khi nói m t dãy có th t ngh-a là dãy ó có th t không
gi m.
Ví d dãy ban u :
S1 = {5 6 1 9 8 6}
Dãy sau khi bi n !i:
S2 = {1 5 6 6 8 9}
•Khái ni m ngh ch th
Xét m t m ng n s a0, a1,.., an-1. N u có i < j và ai > aj, thì ta g i ó là m t ngh ch th .
M ng ch a s(p x p s# có ngh ch th , và ng c l i m ng ã có th t s# không ch a ngh ch
th .
s(p x p m t m ng, ta có th tìm cách làm gi m s các ngh ch th trong m ng này
b'ng cách hoán v các ph n t ai,aj n u có i < j và ai > aj theo m t quy lu t nào nào ó.
Sau ây là m t s ph ng pháp s(p x p th ng dùng nh t.
2.2.2.Ph ng pháp %i ch% tr&c ti!p
Ý t *ng chính c a gi i thu t !i ch tr c ti p là xu t phát t
u dãy, tìm t t c
ngh ch th ch a ph n t này, tri t tiêu chúng b'ng cách !i ch ph n t này v i ph n t t ng
ng trong c p ngh ch th . L p l i quá trình trên v i các ph n t ti p theo trong dãy.
Bài gi ng c u trúc d li u và gi i thu t
Trang 11
Bài gi ng c u trúc d li u và gi i thu t
Ví d 2.2:
Cho dãy s 5 6 1 9 8 6
Thì k t qu t ng b c nh sau:
H4C PH5N C U TRÚC D
Trang 60
LI U VÀ GI I THU T ( 6 S7 7)
Th"i gian làm bài: 90 phút
dòng
i
j
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
0
0
2
5
6
1
9
8
6
Cho cây nh phân tìm ki m T g m 12 s nguyên v i th t các nút
1
1
2
1
6
5
9
8
6
sau: 11 (nút g c), 7, 5, 1, 6, 8, 10, 9, 18, 12, 13, 19.
2
3
4
1
5
6
9
8
6
3
3
5
1
5
6
8
9
6
4
4
5
1
5
6
6
9
8
1
5
6
6
8
9
5
Câu 1 (2 i m)
c chèn vào cây nh
a. Hãy v# cây nh phân tìm ki m T.
b. Hãy duy t cây T trên theo th t NLR.
c. Hãy duy t cây T trên theo th t RNL.
d. Hãy v# l i cây sau khi xoá nút 11 sao cho T v%n là cây nh phân tìm ki m.
Câu 2 (2 i m)
void interchangesort(int a[], int n)
{
for (int i=0; i
swap(a[i],a[j]);
}
a. Hãy nêu s khác nhau c a cây nh phân tìm ki m (BST) và Heap?
b. Có th li t kê n ph n t c a heap theo th t t ng d n v i chi phí O(n) không? Vì sao?
Câu 3 (3 i m)
Cho danh sách liên k t
là các s nguyên d
n l, m i nút là m t phân s (gi s t s và m%u s c a các phân s
ng). C u trúc c a danh sách liên k t l
c cho nh sau:
struct Phanso {int tu; int mau;};
ph c t p tính toán c a gi i thu t là: O(n2)
2.2.3.Ph
struct Node {Phanso info; struct Node *next;};
struct List
ng pháp ch n tr&c ti!p
Ch n ph n t nh" nh t trong n ph n t kh*i t o, a ph n t này v v trí úng là u
dãy hi n hành; sau ó không quan tâm n nó n a, xem dãy hi n hành m i ch còn n-1 ph n
t c a dãy ban u, b(t u t v trí th hai; l p l i quá trình trên cho dãy hi n hành... cho
khi dãy hi n hành ch còn m t ph n t .
n
a. Hãy
ms l
ng phân s có giá tr l n h n 1 c a danh sách l.
b. Hãy t o danh sách l1 ch ch a các phân s t i gi n t danh sách l (phân s t i gi n là phân
s mà
c.
Ví d 2.3:
Cho dãy s 5 6 1 9 8 6
N u dãy c n
c s(p theo th t t ng d n,
{Node *head,*tail;};
Hãy vi t các hàm th c hi n các yêu c u sau:
c s chung l n nh t c a t s và m%u s c a nó b'ng 1).
ms l
ng phân s t i gi n c a danh sách l (phân s t i gi n là phân s mà
chung l n nh t c a t s và m%u s c a nó b'ng 1).
Câu 4 (3 i m)
Hãy vi t ph n khai báo c u trúc d li u
dòng
i
j
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
0
0
2
5
6
1
9
8
6
là m t s nguyên d
mô t m t cây nh phân tìm ki m mà m i ph n t
ng. Hãy vi t các hàm th c hi n các yêu c u sau:
1
1
2
1
6
5
9
8
6
a. Vi t hàm
2
2
2
1
5
6
9
8
6
b. Vi t hàm tính t!ng các nút có giá tr nguyên t trong cây.
3
3
5
1
5
6
9
8
6
4
4
4
1
5
6
6
8
9
1
5
6
6
8
9
5
cs
m xem trong cây có bao nhiêu nút có úng 2 cây con ?
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
H4C PH5N C U TRÚC D
Trang 59
Bài gi ng c u trúc d li u và gi i thu t
void selectionsort(int a[],int n)
{
for(int i = 0;i < n -1; i++)
{
int min = i;
for ( int j = i+1; j < n; j++)
if (a[j] < a[min])
min = j;
swap( a[min], a[i] );
}
}
ph c t p tính toán c a gi i thu t là: O(n2)
LI U VÀ GI I THU T ( 6 S7 6)
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
Hãy v# cây nh phân tìm ki m T bi t r'ng khi duy t cây T theo th t
left – right - node thì
c dãy nh sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8
a. Hãy duy t cây T trên theo th t
node - left - right.
b. Cây T có chi u cao là bao nhiêu ? Tìm các
ng i t g c có
dài là 4 trên cây.
Câu 2 (2 i m)
a. Trong gi i thu t Quick sort c b n, ph n t pivot
c ch n là: pivot=a[r]. Hãy cho bi t
u/khuy t i m c a cách ch n này.
b. V i cách ch n pivot=a[(l+r)/2], hãy cho bi t chi phí c n thi t
quick sort s(p x p m t
m ng g m có n ph n t b'ng nhau.
Câu 3 (3 i m)
Hãy khai báo ki u d li u danh sách liên k t
viên bao g m các tr
n mà m i ph n t ch a thông tin v m t sinh
ng: mã s sinh viên (chu i, 12 ký t ), h lót sinh viên (chu i, t i a 12
ký t ), tên sinh viên (chu i, t i a 12 ký t ), i m trung bình tích l&y (s th c).
2.2.4.Ph
Ví d 2.4:
Cho dãy s 5 6 1 9 8 6
N u dãy c n
c s(p theo th t t ng d n,
dòng
j-1
j
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
0
4
5
5
6
1
9
8
6
1
3
4
5
6
1
9
6
8
2
1
2
5
6
1
6
9
8
3
0
1
5
1
6
6
9
8
4
4
5
1
5
6
6
9
8
1
5
6
6
8
9
a.Hàm x p lo i t t nghi p cho sinh viên. Trong ó x p lo i X(xu t s(c) n u có i m trung
bình tích l&y ( TB) >=9.0; Lo i G(Gi"i) n u có i m trung bình tích l&y 8<= ( TB)<9.0;
TB < 8; Lo i T (trung bình) n u có iêm
trung bình tích l&y 5<= TB <7.
b.Hàm s(p x p danh sách theo i m trung bình tích l&y.
c.Hàm s(p x p danh sách
t lo i X, danh sách c n
ng pháp n%i b t (Bubble Sort)
Xu t phát t cu i dãy (ho c u dãy), !i ch b t k$ hai ph n t k c n nào ng c th
t
a ph n t nh" nh t (ho c l n nh t) trong các c p ph n t ó v v trí úng là u
(cu i) dãy hi n hành, k ti p không xét n nó n a * b c ti p theo, do v y * l n x lý th i
s# có v trí u dãy là i. L p l i quá trình trên cho n khi không còn c p ph n t nào xét.
V i các ki u d li u v a khai báo, hãy xây d ng các hàm sau:
Lo i K(khá) n u có i m trung bình tích l&y 7<=
Trang 12
5
c s(p theo tên t ng d n, n u tên trùng
thì s(p theo h t ng d n.
void bubblesort(int a[],int n)
Câu 4 (3 i m)
{
Gi s T là m t cây nh phân tìm ki m mà t i m i nút l u m t s nguyên. Hãy khai báo ki u
for (int i=1;i
d li u T và xây d ng các hàm sau:
for (int j=n-1;j>=i;j--)
if (a[j]
a. Hàm thêm m t node có khóa X vào T.
b. Hàm
swap(a[j],a[j-1]);
m s nút có khóa l n h n X nh ng nh" h n Y (X < Y).
}
--------------------------------------------------H t----------------------------------------*Ph
ph c t p tính toán c a gi i thu t là: O(n2)
ng pháp này trong th c t không
c khuy n khích s d ng.
Bài gi ng c u trúc d li u và gi i thu t
Trang 13
Bài gi ng c u trúc d li u và gi i thu t
Trang 58
2.2.5.S$p x!p chèn tr&c ti!p
Dãy
u tiên ch có m t th t a0 là dãy ã
c s(p. Ta t ng b
c m* r ng dãy
s(p b'ng cách l n l t thêm ph n t ai (i=1..n-1) vào. Khi chèn ai vào dãy ã
c s(p thì ta
l u giá tr c n chèn. Th hai tìm v trí
ti n hành các công o n sau: Th nh t là t x=ai
pos thích h p trong o n a0 n ai-1 chèn ai vào. Th ba là chèn x vào v trí pos.
dòng
pos+1
i
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
0
1
1
5
6
1
9
8
6
1
0
2
5
6
1
9
8
6
2
3
3
1
5
6
9
8
6
3
3
4
1
5
6
9
8
6
4
3
5
1
5
6
8
9
6
1
5
6
6
8
9
void insertionsort(int a[], int n)
{
int pos,x;
for(int i=1; i
{
x=a[i]; pos=i-1;
while(pos>=0 && a[pos]>x)
a[pos+1] = a[pos--];
a[pos+1]=x;
}
}
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
I
0
1
2
3
4
5
6
7
8
9
A[i]
5
1
2
8
6
10
3
9
4
7
-Hãy cho bi t k t qu sau khi hi u ch nh m ng A thành (binary) heap?
-V# (binary) heap * d ng cây nh phân.
b.Cho bi t s ph n t t i thi u và t i a c a m t (binary) heap có chi u cao là h ?
Câu 2 (2 i m)
a. Hãy minh h a cách s(p x p t ng d n dãy s sau ây theo gi i thu t Quick sort:
28, 9, 25, 19, 5, 21, 14, 31.
b. Ch ng minh gi i thu t merge sort có
ph c t p là O(n log2n)
Câu 3 (3 i m)
Cho danh sách liên k t
c. Hãy
n, m i nút là m t phân s (t s và m%u s là các s nguyên)
m xem trong danh sách có bao nhiêu phân s có giá tr l n h n 1.
d. Hãy xóa các phân s không ph i là phân s t i gi n trong danh sách.
Câu 4 (3 i m)
Cho cây nh phân tìm ki m T có khóa là các s nguyên.
a. In các khóa theo chi u gi m d n.
b. Tìm giá tr nút lá * m c sâu nh t (ch tìm 1 giá tr th"a)
ph c t p tính toán c a gi i thu t là: O(n2)
2.2.6.S$p x!p phân ho ch (Quick sort)
Quick Sort
c th c hi n b'ng cách phân ho ch dãy ã cho thành hai ph n sau ó
s(p các ph n này riêng bi t nhau nh sau:
t
LI U VÀ GI I THU T ( 6 S7 5)
a.Cho m ng A ch a các ph n t :
Ví d 2.5:
Cho dãy s 5 6 1 9 8 6
N u dãy c n
c s(p theo th t t ng d n,
5
H4C PH5N C U TRÚC D
c
u tiên ch n ph n t tùy ý; th ng
c ch n là x=a[(l+r)/2] làm m c, k ti p quét
u trái c a m ng cho n khi g p m t ph n t l n h n x và quét t
u ph i c a m ng cho
n khi g p m t ph n t bé h n x, hai ph n t d ng vi c quét d- nhiên là không úng ch
trong m ng k t qu cu i cùng nên ph i hoán v chúng.
Sau khi th c hi n b c này thì b o m r'ng t t c các ph n t * bên trái c a x s# nh"
h n x và các ph n t bên ph i c a x s# l n h n x.
Sau b c này ta ã chia dãy thành hai dãy con; ta l i ti p t c phân ho ch theo ki u
qui cho m i dãy con này.
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
H4C PH5N C U TRÚC D
Trang 57
LI U VÀ GI I THU T ( 6 S7 4)
Th"i gian làm bài: 90 phút
Bài gi ng c u trúc d li u và gi i thu t
Trang 14
Ví d 2.6:
Cho dãy s 5 6 1 9 8 6
N u dãy c n
c s(p theo th t t ng d n,
dòng
l
r
x
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
0
0
5
1
5
6
1
9
8
6
Câu 1 (2 i m)
1
0
1
1
1
6
5
9
8
6
a. N u ta xóa m t ph n t kh"i cây BST và sau ó thêm nó vào l i cây. H"i: hình d ng c a
2
1
5
9
1
6
5
9
8
6
3
1
4
5
1
6
5
6
8
9
4
2
4
6
1
5
6
6
8
9
5
3
4
6
1
5
6
6
8
9
6
4
5
8
1
5
6
6
8
9
1
5
6
6
8
9
cây ó b thay !i không? Gi i thích?
h
b. Ch ng minh r'ng m t cây nh phân v i chi u cao h s# có t i a 2 -1 nút.
Câu 2 (2 i m)
a. S d ng Stack, vi t ch
ng trình chuy n !i m t s nguyên n trong h th p phân (h 10)
sang bi u di)n h nh phân (h 2).
b. Hãy áp d ng gi i thu t Balan ng
c
bi n !i bi u th c sau thành d ng postfit:
(a+b/(c-d))*e. Trình bày tr ng thái c a stack sau m i l n có s thay !i.
Câu 3 (3 i m)
Hãy qu n lý các s thuê bao i n tho i b'ng danh sách liên k t
thông tin: h tên,
a ch , s
Hãy vi t hàm tìm ki m
i n tho i c
a ch c a m t s
n. M i ph n t ch a các
i n tho i cho tr
c.
Cho cây nh phân tìm ki m T, m i nút ch a m t s nguyên. Hãy vi t các hàm th c hi n các
yêu c u sau:
ng i t g c
{
int x=a[(l+r)/2]; int i=l;int j=r;
do
{
while (a[i]
nh.
Câu 4 (3 i m)
a. In
7
void quicksort(int a[],int l,int r)
n nút có giá tr l n nh t.
b. Tìm m t cây con không ch a s nguyên t nào.
--------------------------------------------------H t-----------------------------------------
if (i<=j)
swap(a[i++],a[j--]);
}
while (i
ph c t p tính toán c a gi i thu t là: O(n log n)
2.2.7.S$p x!p vun
ng (Heap sort)
tìm ph n t nh" nh t * b c i, ph ng pháp s(p x p ch n tr c ti p ã không t n
d ng
c các thông tin ã có
c do các phép so sánh * b c i-1. Ph ng pháp Heap Sort
kh(c ph c
c nh c i m này.
nh ngh a heap:
Gi s xét tr ng h p s(p x p t ng d n, khi ó Heap
c
nh ngh-a là m t dãy các ph n t
al,..,ar thoã các quan h sau v i m i i∈ [l,r]
ai ≥ a2i
ai ≥ a2i+1
(ai,a2i), (ai,a2i+1) là các c p ph n t liên
i
Bài gi ng c u trúc d li u và gi i thu t
Trang 15
Tính ch t c a heap:
Tính ch t 1: N u al,.,ar là m t Heap thì khi c(t b" m t s ph n t * hai u c a Heap thì
dãy con còn l i v%n là m t Heap .
Tính ch t 2: N u các ph n t a1,..,an là m t Heap thì ph n t a1 ( u heap) luôn là ph n t
l n nh t trong Heap.
Tính ch t 3: M i dãy al,al+1,…,ar v i 2l > r là m t Heap
•Gi i thu t
Giai o n 1:
Giai o n 2:
B c 1:
LI U VÀ GI I THU T ( 6 S7 3)
H4C PH5N C U TRÚC D
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
a. Vi t hàm cài
t gi i thu t Selection-Sort b'ng
qui và không
qui.
Câu 2 (2 i m)
Hi u ch nh dãy s ban u thành Heap
S(p x p dãy s d a trên Heap
a ph n t l n nh t v v trí ng * cu i dãy
Vi t gi i thu t d ng mã gi
c 2: Lo i b" ph n t l n nh t ra kh"i Heap r=r-1;
Hi u ch nh ph n còn l i c a dãy t al n ar thành m t Heap.
c 3:N u r >1 ( heap còn ph n t ) : l p l i b
Ng c l i: d ng
chuy n các ph n t trong stack S1 sang stack S2 v i nh ng yêu
c u nh sau:
r = n;
Hoán v (a1,ar)
B
Trang 56
b. Hãy cho bi t s l n so sánh và s l n gán c a gi i thu t Selection-Sort.
Gi i thu t heap sort g m hai giai o n sau:
B
Bài gi ng c u trúc d li u và gi i thu t
c2
•
Th t các ph n t trong S2 gi ng nh trong S1
•
Không
c dùng thêm stack ph , ch
c dùng thêm vài bi n ph .
Câu 3 (3 i m)
a. Cho hai danh sách liên k t
n l1,l2 có các ph n t là các s nguyên và ã
c m t danh sách l3 c&ng
d n. Hãy tr n hai danh sách này
c s(p t ng
c s(p t ng d n (không
c s(p x p).
D a vào tính ch t 3, ta có th th c hi n giai o n 1 b'ng cách b(t
u t heap m c nhiên
an/2+1, an/2+2,…,an, l n l t thêm vào các ph n t an/2, an/2-1,…,a1. ta s# nh n
c Heap
theo mong mu n. Nh v y gi i o n 1 t ng
ng v i n/2 l n th c hi n b c 2 c a giai
o n 2.
i v i các thao tác c b n. Hãy vi t các hàm th c hi n các công vi c sau
ây:
-L y ra ph n t cu i cùng c a hàng
-L y ra ph n t th n c a hàng
(gi i thu t này minh h a theo d ng cây thì ng
void insertheap(int a[],int l,int r)
i
c d) hình dung h n).
Cài
i
i, v i n là s nguyên d
ng.
t c th các gi i thu t trên b'ng ng n x p các s nguyên v i cách t! ch c hàng
i b'ng danh sách liên k t.
Câu 4 (3 i m)
{
int j;
Cho cây nh phân tìm ki m T, m i nút ch a m t s nguyên. Hãy vi t các hàm th c hi n các
j=l*2;
while (j<=r)
yêu c u sau:
{
if (j
swap(a[l],a[j]);
output(a,n);
l=j;
j=l*2;
}
}
b. Cho m t hàng
a. In ra t t c các nút * m c th k c a cây T
j++;
return;
b. In ra t t c các nút theo th t t ng 0
n t ng th h-1 c a cây T (h là chi u cao c a cây)
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 55
H4C PH5N C U TRÚC D
LI U VÀ GI I THU T ( 6 S7 2)
Th"i gian làm bài: 90 phút
Câu 1 (2 i m)
a. Vi t hàm s(p x p dãy n s nguyên ao, a1, a2,...,an-1 t ng d n theo gi i thu t Quick sort.
b. Hãy minh h a cách s(p x p t ng d n dãy s sau ây theo gi i thu t Quick sort:
28, 9, 25, 19, 5, 21, 14, 31.
Câu 2 (2 i m)
Cho m t m ng các giá tr nguyên nh sau:
i
0
1
2
3
4
5
6
7
8
9
a[i]
10
3
16
7
1
4
9
14
2
8
a. Cho bi t k t qu sau khi bi n !i m ng trên thành dãy heap.
Bài gi ng c u trúc d li u và gi i thu t
Trang 16
void heapsort(int a[],int n)
{
int l=n/2;
int r=n;
while (l>0)
insertheap(a,l--,r);
while (r>0)
{
swap(a[1],a[r]);
output(a,n);
r--;
insertheap(a,1,r);
}
}
ph c t p tính toán c a gi i thu t là: O(nlog2n)
b. Th hi n dãy heap ó theo d ng cây nh phân.
2.2.8.S$p x!p tr n (Merge sort)
Câu 3 (3 i m)
Hãy khai báo ki u c u trúc d li u liên k t
quy n sách bao g m các tr
n mà m i ph n t ch a thông tin v m t
ng: Mã s sách (s nguyên 4 byte), tên sách (chu i, t i a 40 ký
t ), tác gi (chu i, t i a 30 ký t ), n m xu t b n (s nguyên 4 byte).
a.
m s sách xu t b n n m X.
b. S(p x p danh sách theo mã s sách.
Câu 4 (3 i m)
Gi s T là m t cây nh phân tìm ki m mà t i m i nút l u m t s nguyên. Hãy khai
báo ki u d li u T và xây d ng các hàm sau:
a. Hàm tìm ki m m t node có khóa X (tr v con tr" tr" d n nút tìm
b. Hàm
B
c 1: Chu,n b
k=1;// k là chi u dài c a dãy con trong b c hi n hành
B c 2:Tách dãy a0,a1,…an-1 thành hai dãy b,c theo nguyên t(c luân phiên t ng nhóm k ph n
t .
B c 3:Tr n t ng c p dãy con g m k ph n t c a hai dãy b,c vào dãy a.
B c 4:
k=k*2;
N u k
c).
m s nút có khóa l n h n X.
c. Hãy tìm cây con có t!ng l n nh t.
--------------------------------------------------H t-----------------------------------------
ph c t p tính toán c a gi i thu t là: O(nlog2n)
Ví d 2.7:
Cho dãy s
8
Dãy c n
5
1
3
6
c s(p theo th t t ng d n,
9
12
4
7
10
9
4
12
7
k=1;
B c tách a thành b,c
Dãy b: 8
Dãy c: 5
1
3
6
9
12
4
7
10
Tr n : 5
8
1
3
6
10
Bài gi ng c u trúc d li u và gi i thu t
Trang 17
Bài gi ng c u trúc d li u và gi i thu t
Trang 54
k=2;
B c tách a thành b,c
Dãy b: 5
8
6
Dãy c: 1
3
4
9
12
7
10
Tr n : 1
8
4
6
3
5
M TS
9
12
7
10
H4C PH5N C U TRÚC D
THI M U
LI U VÀ GI I THU T ( 6 S7 1)
Th"i gian làm bài: 90 phút
k=4;
B c tách a thành b,c
Dãy b: 1
3
5
8
7
10
Dãy c: 4
Tr n : 1
12
5
6
8
6
3
9
4
Câu 1 (2 i m)
a. Vi t hàm s(p x p dãy n s nguyên ao,a1,a2,...,an-1 t ng d n theo gi i thu t Heap sort.
9
12
7
10
k=8;
b. Hãy minh h a cách s(p x p t ng d n dãy s sau ây theo gi i thu t Heap sort:
26, 7, 22, 15, 1, 18, 11, 27
B c tách a thành b,c
Dãy b: 1
3
4
Dãy c: 7
10
Tr n : 1
3
4
5
6
8
9
Câu 2 (2 i m)
12
Cho cây nh phân tìm ki m T g m 12 s nguyên v i phép duy t LRN cho k t qu nh sau: 1,
5
6
7
8
9
10
12
3, 2, 6, 7, 5, 4, 10, 9, 12, 11, 8
a. Hãy v# cây nh phân tìm ki m T.
b. Duy t cây T theo th t NLR
Ví d 2-8. Cho dãy n s nguyên sau:
Hãy mô ph"ng các b
c s(p x p t ng d n dãy s trên theo các gi i thu t s(p x p ã h c
c. V# l i cây sau khi xoá nút 8 sao cho T v%n cây nh phân tìm ki m.
Câu 3 (3 i m)
8
5
1
3
6
9
12
4
7
10
Ví d 2-9.
Cho dãy n s nguyên ai.
a. Vi t hàm tìm xem x có thu c dãy ai hay không ? N u có tr v 1, n u không có tr v 0.
b. Vi t hàm tìm giá tr l n nh t, l n th nhì c a dãy.
c. Tìm các giá tr xu t hi n nhi u l n nh t
Cho m t danh sách liên k t
n l; m i nút là m t s nguyên d
ng.
a. Vi t hàm t o danh sách l1 ch ch a các s nguyên t t danh sách l.
b. Vi t hàm xóa các s nguyên t trong danh sách l.
Câu 4(3 i m)
Cho cây nh phân tìm ki m T; m i nút là m t s nguyên.
a. Vi t hàm tìm m c c a nút có giá tr l n nh t.
Ví d 2-10.
Cho dãy n s nguyên d
b. Vi t hàm tìm t t c các
ng ai.
c. Vi t hàm
a. Hãy s(p các s nguyên t v
u dãy, các s khác v cu i dãy.
b. Hãy cho bi t k giá tr khác nhau l n nh t c a dãy.
c. Vi t hàm tìm giá tr l n th k c a dãy.
CÁC PH./NG PH0P S0P X1P
2C BI3T tham kh o thêm t i [2] trang 199
ng i t g c có
dài là 4 trên cây.
m s cây con ch ch a toàn là s nguyên t .
--------------------------------------------------H t-----------------------------------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 53
BÀI T P
Bài gi ng c u trúc d li u và gi i thu t
Trang 18
BÀI T P
BT4-1.Cho cây nh phân tìm ki m T, m i nút ch a m t s nguyên. Hãy vi t các hàm th c
BT2-1. Cho dãy n s nguyên a0,a1,…,an-1.
hi n các yêu c u sau:
a. Chèn nút vào cây, duy t cây theo các th t
L p trình hoàn ch nh các gi i thu t ã trình bày trong ch
ãh c
b.
m xem trong cây có bao nhiêu nút có giá tr âm? bao nhiêu nút có giá tr d
c.
m xem trong cây có bao nhiêu nút lá ? nút nhánh ? nút có 1 cây con ? nút có 2 cây con?
d. Tìm ph n t d
ng?
ng nh" nh t c a cây.
i. In
ng i t g c
ng i t g c có
BT2-2.Cho dãy n s nguyên a0,a1,…,an-1
b. S(p x p các ph n t t ng d n theo t!ng các ch s c a t ng ph n t .
l ch c a cây.
g. In ra t t c các nút * m c th k c a cây T.
h. Tìm t t c các
m
a. Hãy cho bi t v trí c a k ph n t có giá tr l n nh t c a dãy.
e. Tìm m c c a nút có giá tr l n nh t.
f. Cho bi t chi u cao c a cây,
ng này và gi i thu t s(p x p
(2 gi i thu t tìm ki m và 8 gi i thu t s(p x p).
c. Tìm h ng c a các ph n t (s l n có h ng cao) theo cách (xem ví d ). Ví d dãy s 3 2 2
dài là k trên cây.
5 5 6 4 6 thì x p h ng là 6 7 7 3 3 1 5 1
n nút có giá tr l n nh t.
BT4-2.Cho cây nh phân tìm ki m T, m i nút ch a m t s nguyên. Hãy vi t các hàm th c
hi n các yêu c u sau:
BT2-3.Cho hai t p X và Y; m i t p g m n s nguyên và s nguyên k. H"i có tìm
cm ts
x thu c X và m t s y thu c Y sao cho x + y = k hay không ?
a. Chèn ph n t x vào cây.
BT2-4.Cho dãy n s nguyên không âm và s nguyên k. H"i dãy ã cho có ch a hai s v i
b. Xóa ph n t có giá tr x trong cây.
t!ng là b'ng k hay không ? N u có hãy
BT4-3.Gi s ta có m t t p h p g m n ph n t ki u s nguyên c n l u tr b'ng c u trúc cây
BT2-5.Cho m ng g m n s nguyên.
nh phân tìm ki m (BST). L u ý r'ng các ph n t có th trùng nhau. Vi t ch
ng trình hoàn
a ra hai s
ó (n <=106, k<=109).
a. Tìm m ng g m các ph n t riêng bi t (gi l i m t s trong các s trùng nhau).
ch nh cho hai thao tác chính: Thêm ph n t , xóa ph n t .
BT4-4.Xây d ng c u trúc cây sao cho m i nút c a cây l u tr
m t phân s
b. Tìm hai s g n nhau nh t trong m ng ã cho
(t s và m%u s là các s nguyên).
BT2-6.Cho hai file ch a các s nguyên ã
a. Hãy tìm phân s có giá tr l n nh t
m t file c&ng
b. Tính t!ng giá tr các phân s trong cây.
BT2-7.Cho dãy n s nguyên (yêu c u
BT4-5. Cho cây nh phân tìm ki m T; m i nút là m t s nguyên.
a.
c s(p t ng d n.
ph c t p tuy n tính).
a. Trình bày gi i thu t tìm ph n t trung v c a dãy.
m xem trong cây có bao nhiêu nút mà gia tr c a nó cùng v i giá tr c a hai cây con
b. Trình bày gi i thu t tìm ph n t có giá tr th k c a dãy.
tr c ti p c a nó c&ng là s nguyên t ?
b. Tìm cây con T có t!ng l n nh t (chi tìm m t cây th"a).
c.
c s(p t ng d n, hãy tr n hai file này
m s cây con ch ch a toàn là s nguyên t .
BT4-6.Cho m t cây nh phân bi u di)n m t bi u th c toán h c. Bi t r'ng g c c a cây là root,
m i nút có thu c tính key (ki u char) , ch a m t phép tính(+,- , *,/) hay m t giá tr nguyên
(các nút lá). Hãy vi t hàm tính giá tr bi u th c ch a trong cây.
BT4-7.Vi t ch
ng trình qu n lý m t danh b
thuê bao, h tên ch thuê bao,
xóa i m t s thuê bao nào ó.
a ch . Ch
i n tho i
n gi n bao g m các thông tin: s
ng trình cho phép tìm ki m thông tin, thêm ho c
c
Bài gi ng c u trúc d li u và gi i thu t
Ch
Trang 19
Bài gi ng c u trúc d li u và gi i thu t
Ví d 4.7
3ng i trên cây
//------------In các nút trên
ng i t g c
void duongditugoc(tree root, int x)
{
ng 3
DANH SÁCH LIÊN K T
Trong ph n l p trình C, b n c ã
c gi i thi u các ki u d li u c s* nh : ki u s , ki u
ký t ho c các ki u d li u có c u trúc n gi n nh : ki u m%u tin, ki u m ng. Các i t ng
c bi u di)n b*i các ki u d li u này có kích th c không !i trong su t quá trình s ng c a
nó –g i là các ki u d li u t-nh. Tuy nhiên m t i t ng trong quá trình s ng c a nó có th
thay !i
l n; khi ó n u dùng các ki u d li u t-nh
bi u di)n thì vi c gi i quy t v n
tr* nên ph c t p, không
c t nhiên và không hi u qu . Trong ch ng 3 này, chúng tôi gi i
thi u m t cách th c t! ch c d li u linh ng h n nh'm kh(c ph c
c các khuy t i m trên
– ó là c u trúc d li u ng – mà d ng n gi n và quan tr ng nh t là danh sách liên k t.
3.1.DANH SÁCH LIÊN K T (LINK LIST)
3.1.1.Ð"nh ngh'a
ki u T
Cho T là m t ki u
c nh ngh-a tr c, ki u danh sách Tx g m các ph n t thu c
c nh ngh-a là: Tx = <Vx, Ox> ,trong ó:
c móc n i v i nhau theo trình t tuy n
Vx = {t p h p có th t các ph n t ki u T
tính};
Ox = {t o danh sách; Tìm m t ph n t trong danh sách; chèn m t ph n t vào danh
sách; hu4 m t ph n t kh"i danh sách ; li t kê các ph n t c a danh sách, s(p
x p danh sách,...}
3.1.2.Các hình th c t% ch c danh sách
Có nhi u ki u t! ch c liên k t gi a các ph n t trong danh sách nh
-Danh sách liên k t n
-Danh sách liên k t kép,…
:
Hình th c liên k t này cho phép các thao tác thêm, hu4 ph n t trên danh sách
th c hi n d) dàng h n, ph n ánh
c b n ch t linh ng c a danh sách.
Trang 52
n nút có giá tr x----------
if (timkiem01(root,x))
{
while (root->info!=x)
{
cout<<root->info<<" ->";
if (root->info>x)
root=root->left;
else
if (root->info
}
cout<<root->info;
}
else
cout<<"Khong co duong di tu goc den "<
//In
ng i t g c n nút có m c sâu nh t
void duongdidennucsaunhat(tree root)
{
if (root!=NULL)
{
duongdidennucsaunhat(root->right);
if (muccuanut(root1,root->info)==chieucao(root1)-1)
duongditugoc(root1,root->info);
duongdidennucsaunhat(root->left);
}
}
c
CÂY NH; PHÂN TÌM KI1M CÂN B
3.2.1.T% ch c danh sách
N
n theo cách c p phát liên k!t
C u trúc d li u c a m t ph n t trong danh sách n:
M i ph n t c a danh sách n là m t c u trúc ch a hai thông tin :
-Thành ph n d li u: l u tr các thông tin v b n thân ph n t .
trang 230
B=NG B>M tham kh o thêm t i [2] trang 249
Bài gi ng c u trúc d li u và gi i thu t
Trang 51
Hàm xoanut tr v giá tr 1, 0 khi h y thành công ho c không có k trong cây:
H y toàn b CNPTK
Vi c toàn b cây có th
c th c hi n thông qua thao tác duy t cây theo th t sau. Ngh-a là
ta s# h y cây con trái, cây con ph i r i m i h y nút g c.
//--------Hàm tìm ph n t th m ng-----------------------void phantuthemang(tree &p,tree &q)
{
if (q->left) phantuthemang(p,q->left);
else
{
p->info=q->info;
p=q;
q=q->right;
}
}
//---------------Xóa nút có giá tr là k---------------------int xoanut(tree &root,int k)
{
if (root==NULL)
return 0;
if (root->info>k)
return xoanut(root->left,k);
if (root->info
else
{
node *p=root;
if (root->right==NULL)
root=root->left;
else
if (root->left==NULL)
root=root->right;
else
{
node *q=root->right;
phantuthemang(p,q);
}
delete(p);
}
return 1;
}
Bài gi ng c u trúc d li u và gi i thu t
Trang 20
-Thành ph n m i liên k t: l u tr
a ch c a ph n t k ti p trong danh sách, ho c l u tr
giá tr NULL n u là ph n t cu i danh sách.
Ta có nh ngh-a t!ng quát
struct Node
{
Data Info;//data là ki u d li u ã nh ngh-a tr
Node* Next;//con tr" ch n c u trúc Node
c
};
M t ph n t trong danh sách n là m t bi n ng s#
c yêu c u c p phát khi c n. Và
danh sách n chính là s liên k t các bi n ng này v i nhau do v y t
c s linh
ng khi thay !i s l ng các ph n t .
• N u bi t
c a ch c a ph n t
u tiên trong danh sách n thì có th d a vào thông
tin next c a nó
truy xu t n ph n t th hai trong xâu, và l i d a vào thông tin next
c a ph n t th 2
truy xu t n ph n t th 3,...Ngh-a là qu n lý m t xâu n ch
c n bi t a ch ph n t
u xâu. Th ng m t con tr" head s#
c dùng
l u tr
a
ch ph n t
u xâu, ta g i head là u xâu. Ta có khai báo:
Node
*head;
• Tuy v nguyên t(c ch c n qu n lý xâu thông qua
u xâu head, nh ng th c t có nhi u
tr ng h p c n làm vi c v i ph n t cu i xâu, khi ó m i l n mu n xác nh ph n t cu i
xâu l i ph i duy t t
u xâu. Ð ti n l i, có th s d ng thêm m t con tr" tail gi
a
ch ph n t cu i xâu. Khai báo tail nh sau :
Node *tail;
•
3.2.2. Các thao tác c b n trên danh sách
Gi s có các
n
nh ngh-a:
struct node
{
int
info;
node *next;
};
struct list
{
list
node
};
head,tail;
*head,*tail;
Và ã xây d ng th t c t onút (getnode(x))
v i thông tin ch a trong x:
t o ra m t ph n t cho danh sách
Bài gi ng c u trúc d li u và gi i thu t
Trang 21
node* taonut (int x)
{
p=new node;
if (p==NULL)
exit(1);
p->info=x;
p->next=NULL;
return p;
}
•
c tr" b*i con tr" new_elelment vào danh sách:
Gi i thu t :
n u danh sách r ng thì
l.head = new_elelment;
l.tail = new_elelment;
ng
cl i
p->next = l.head;
}
//In các nút c a cây theo t ng m c t m c 0 m c h-1 (v i h là chi u cao c a cây)
void duyetnuttheotungmuc(tree root)
{
int h=chieucao(root);
for (int i=0;i
duyetnutmuck(root,i);
cout<
}
//--------------- l ch c a cây--------------int dolech(tree root)
{
return abs(chieucao(root->left) - chieucao(root->right));
}
Ví d 4.6: Xóa nút trên cây
Vi c h y m t ph n t k ra kh"i cây ph i b o
tr ng h p khi h y nút k có th x y ra:
l.head = new_elelment;
void
{
chennutvaodau(List &l,Node *p)
•
•
if (l.head==NULL)
{
•
l.head=p; // new_elelment nh mô t trên
l.tail=p;
Tr
Tr
}
else
Tr
{ p->next=l.head;
l.head=p;
}
m i u ki n ràng bu c c a CNPTK. Có 3
k là nút lá.
k ch có 1 con (trái ho c ph i).
k có
c 2 con
ng h p th nh t:
Ch
n gi n h y k vì nó không móc n i n ph n t nào khác.
ng h p th hai:
Tr c khi h y k ta móc n i cha c a k v i con duy nh t c a nó.
ng h p cu i cùng:
Ta không th h y tr c ti p do k có
2 con
Ta s# h y gián ti p. Thay vì h y k, ta
s# tìm m t ph n t th m ng k’. Ph n t này có t i a m t con. Thông tin l u t i k’ s#
chuy n lên l u t i k. Sau ó, nút b h y th t s s# là k’ gi ng nh 2 tr ng h p
V n là ph i ch n k’ sao cho khi l u k’ vào v trí c a k, cây v%n là CNPTK.
}
Nh v y
Trang 50
cout<<root->info<<" ";
duyetnutmuck(root->right,k);
}
3.2.2.1.Chèn m t ph(n t vào danh sách:
Có 3 lo i thao tác chèn m t ph n t x
Chèn vào u danh sách
Bài gi ng c u trúc d li u và gi i thu t
t o m t danh sách b'ng cách chèn
u ta có th vi t hàm nh sau:
c
u.
Có 2 ph n t th"a mãn yêu c u:
•
Ph n t nh" nh t (trái nh t) trên cây con ph i.
• Ph n t l n nh t (ph i nh t) trên cây con trái.
Vi c ch n l a ph n t nào là ph n t th m ng hoàn toàn ph thu c vào ý thích c a ng i l p
trình. : ây, chúng tôi s# ch n ph n t (ph i nh t trên cây con trái làm phân t th m ng.
Bài gi ng c u trúc d li u và gi i thu t
Trang 49
Bài gi ng c u trúc d li u và gi i thu t
int demnut2connt(tree root)
{
if (root==NULL) return 0;
else
{
if (root->left!=NULL && root->right!=NULL && nguyento(root->info) &&
nguyento(root->left->info) && nguyento(root->right->info))
return 1+demnut2connt(root->left)+demnut2connt(root->right);
return demnut2connt(root->left)+demnut2connt(root->right);
}
}
void danhsachchendau(List &l)
{
int x,n;
cout<<"Nhap vao so n = ";cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x;
chennutvaodau(l,taonut(x));
}
}
Ví d 4.5: Chi u cao c a cây, m c c a nút
//---------------Chi u cao c a cây--------------int chieucao(tree root)
{
if (root==NULL) return 0;
else
{
long hl=chieucao(root->left);
long hr=chieucao(root->right);
return 1+((hl
}
//---------------Tìm m c c a nút có giá tr là x---------------int muccuanut(tree root, int x)
{
if (root!=NULL)
{
if (root->info==x) return 0;
if (root->info>x)
return 1+muccuanut(root->left,x);
if (root->info
}
return 0;
}
//---------------In các nút * m c k c a cây--------------void duyetnutmuck(tree root, int k)
{
if (root!=NULL)
{
duyetnutmuck(root->left,k);
if (muccuanut(root1,root->info)==k)
Chèn new_elelment vào cu i danh sách
•
Gi i thu t :
N u danh sách r ng thì
l.head = new_elelment;
l.tail = head;
ng c l i
l.tail ->next = new_elelment;
l.tail = new_elelment ;
Cài t
void
{
Trang 22
chennutvaocuoi(List &l,Node *p)
if (l.head==NULL)
{
l.head=p;
l.tail=p;
}
else
{
l.tail->next=p;
l.tail=p;
}
}
Nh v y
t o m t danh sách b'ng cách chèn cu i ta có th vi t hàm nh sau:
Bài gi ng c u trúc d li u và gi i thu t
Trang 23
void danhsachchencuoi(List &l)
{
int x,n;
cout<<"Danh sach co bao nhieu phan tu : ";cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x;
chennutvaocuoi(l,taonut(x));
}
}
Chèn vào danh sách sau m t ph n t q
•
Gi i thu t :
N u ( q != NULL) thì
new_ele -> next = q->next;
q->next = new_ele ;
void chensaunutq(List &l,Node *q,int x)
{
Node *p=taonut(x);
if (p==NULL) exit(1);
if (q!=NULL)
{
p->next=q->next;
q->next=p;
if (q==l.tail)
l.tail=p;
}
else
chennutvaodau(l,p);
}
3.2.2.2. Tìm m t ph(n t trong danh sách
n
Gi i thu t :
Xâu n òi h"i truy xu t tu n t , do ó ch có th áp d ng gi i thu t tìm tuy n tính
xác nh ph n t trong xâu có khoá k. S d ng m t con tr" ph tr p
l n l t tr" n
các ph n t trong xâu. Gi i thu t
c th hi n nh sau :
•
Bài gi ng c u trúc d li u và gi i thu t
Trang 48
//--------------- m s nút có úng m t cây con --------------int demnut1caycon(tree root)
{
if (root==NULL) return 0;
else
{
if ((root->left!=NULL && root->right==NULL) ||
(root->left==NULL && root->right!=NULL))
return 1+demnut1caycon(root->left)+demnut1caycon(root->right);
return demnut1caycon(root->left)+demnut1caycon(root->right);
}
}
//--------------- m s nút có hai cây con--------------int demnut2caycon(tree root)
{
if (root==NULL) return 0;
else
{
if (root->left!=NULL && root->right!=NULL)
return 1+demnut2caycon(root->left)+demnut2caycon(root->right);
return demnut2caycon(root->left)+demnut2caycon(root->right);
}
}
int nguyento(int n)
{
if (n<2) return 0;
int k=sqrt(n);
for (int i=2;i<=k;i++)
if (n%i==0) return 0;
return 1;
}
//---------------- m xem có bao nhiêu nút có giá tr nguyên t ?---------------int demnutnguyento(tree root)
{
if (root==NULL) return 0;
return nguyento(root->info)+demnutnguyento(root->left)+demnutnguyento(root->right);
}
//---------------Dem so nut co dung 2 cay con
u là s nguyên t ---------------
Bài gi ng c u trúc d li u và gi i thu t
Trang 47
L u ý: Hãy vi t l i hàm trên b'ng cách không s d ng ph ng pháp quy.
Ki m tra xem k có trong cây root hay không ? N u có thì tr v giá tr 1; n u không có thì tr
v giá tr 0.
int timkiem01(tree root,int k)
{
if (root==NULL)
return 0;
else
if (root->info==k)
return 1;
if (k>root->info)
return timkiem01(root->right,k);
else
return timkiem01(root->left,k);
}
D) dàng th y r'ng s l n so sánh t i a ph i th c hi n tìm ph n t k là h, v i h là chi u cao
c a cây. Nh v y thao tác tìm ki m trên CNPTK có n nút t!ng chi phí trung bình kho ng
O(log2n) .
Ví d 4.4:
2ng d ng phép duy t cây
//----------Tính t!ng giá tr c a các nút trong cây ---------int tong(tree root)
{
if (root==NULL) return 0;
return root->info+tong(root->left)+tong(root->right);
}
//-----------------Tìm giá tr l n nh t c a cây ----------int giatrilonnhat(tree root)
{
while (root->right!=NULL)
root=root->right;
return root->info;
}
//------------ m s nút c a cây---------------int demnut(tree root)
{
if (root==NULL)
return 0;
return demnut(root->left)+demnut(root->right)+1;
}
//------------- m s nút lá c a cây------------int demnutla(tree root)
{
if (root==NULL) return 0;
if ((root->left==NULL) && (root->right==NULL)) return 1;
else return demnutla(root->left)+demnutla(root->right);
}
Bài gi ng c u trúc d li u và gi i thu t
Trang 24
B
c 1:
p = Head; //Cho p tr" n ph n t
u danh sách
B c 2:
Trong khi (p != NULL) và (p->next != k ) th c hi n:
p:=p->next;// Cho p tr" t i ph n t k
c 3:
N u p != NULL thì p tr" t i ph n t c n tìm
Ng c l i: không có ph n t c n tìm.
Cài t:
Node* Search(List l,int x)
{
p=l.pH;
while ((p!=NULL)&&(p->Info!=x))
p=p->next;
return p;
}
B
3.2.2.3. Duy t danh sách
Duy t danh sách là thao tác th ng
c th c hi n khi có nhu c u x lý các ph n t c a
danh sách theo cùng m t cách th c ho c khi c n l y thông tin t!ng h p t các ph n t c a
danh sách nh :
Ð m các ph n t c a danh sách,
-
Tìm t t c các ph n t thoã i u ki n,
Hu4 toàn b danh sách (và gi i phóng b nh )
Ð duy t danh sách (và x lý t ng ph n t ) ta th c hi n các thao tác sau:
•
Gi i thu t :
B
B
c 1:
p = Head; //Cho p tr"
n ph n t
u danh sách
c 2:
Trong khi (Danh sách ch a h t) th c hi n
B21 : X lý ph n t p;
B22 : p:=p->pNext;
// Cho p tr" t i ph n t k
Cài t:
void ProcessList(List &l)
{
p=l.pH;
while (p!=NULL)
{
cout<
p=p->pNext;
}
cout<
