ươ
Ổ
Ch
ng 1:
Ữ Ệ Ề Ấ T NG QUAN V C U TRÚC D LI U
o0o
ữ ệ ệ ề ấ 1.1. Khái ni m v c u trúc d li u.
ấ ổ ứ ữ ệ ủ ể C u trúc d li u (CTDL) là m t cách t ch c d li u c a bài toán. CTDL có th do
ữ ậ ể ặ
ữ ệ ộ ướ ngôn ng l p trình đ nh nghĩa tr c ho c có th do ng ậ ấ ườ ử ụ ớ ố ư ị i s d ng đ nh nghĩa. ậ ị C u trúc d li u t ử t thì thu t toán x lý bài toán m i t i u. Chính vì v y, Niklaus
ậ ươ .
ễ ố ư ng trình” ữ ệ ớ ượ ộ ữ ệ ố ế ổ wirth đã t ng k t: ữ ệ ấ “C u trúc d li u + thu t toán = Ch ể Cách bi u di n t
ộ ấ ể ề ấ
ữ ấ ư ấ ọ c g i là c u trúc l u ộ ấ ươ ữ ệ ớ ộ ữ ệ ươ ớ ộ ớ ọ ư ư ữ ữ ứ ớ
ư ộ c đ nh nghĩa nh sau:
i u m t c u trúc d li u trong b nh đ tr (storage structure). Có th có nhi u c u trúc l u tr cho cùng m t c u trúc d li u. ứ C u trúc d li u t ng ng v i b nh ng ng v i b nh g i là l u tr trong hay t ữ ư ngoài g i là l u tr ngoài. ườ ể ữ ệ ọ Thông th ộ
ậ ượ ộ ể ế c.
ợ ộ ậ ậ
Integer =
Boolean =
ữ ệ nh ng ki u d li u đã
ượ
ươ ứ ữ ệ
ợ ể
ộ ườ ế ừ
c xây d ng t
ộ ữ
ể
ể ữ ệ ự
ớ ể ữ ệ ượ ị
ng m t ki u d li u đ
ộ ặ
M t ki u d li u T là m t c p T =
ữ ệ ấ ả 1.2. Các c u trúc d li u căn b n.
ả ể ữ ệ 1.2.1. Các ki u d li u căn b n.
ồ ậ ể ố
ủ ữ ệ ợ ắ ố ọ ử ấ (nguyên – 2 byte, 32768 .. 32767). G m t p h p con các s nguyên. T t ẩ chu n
ố ọ ơ ả ừ ộ
ố ự ủ ậ ợ ồ (th c – 6 byte,2.9E39 .. 1.7E38). G m t p h p con c a các s th c, các
ừ ố
ậ true (đúng) và false (sai). Các
Ki u Integer ề ả c các phép toán trên d li u integer đ u tuân th các qui t c s h c. Các toán t ố ồ g m b n phép toán s h c c b n: c ng (+), tr (), nhân (*), chia nguyên (div). ự ể Ki u Real ồ ẩ ử ố ọ ơ ả toán t chu n g m b n phép toán s h c c b n là: công (+), tr (), nhân (/). ồ ể Ki u Boolean (lu n lý – 1 bit). G m hai giá tr luân lý ơ ả ồ ử ậ toán t ế ị ậ ị ủ ị lu n lý g m ba phép toán c b n: not (ph đ nh), and (và) và or (hay). ộ ả Các phép toán so sánh cho k t qu là m t giá tr lu n lý. Các phép toán so sánh
g m:ồ
1
= b ngằ
ặ ằ
ặ ằ ợ ậ ể ự ự ượ Ki u char – 1 byte): G m t p h p các kí t in đ c. Các kí t ng dùng là:
ự ườ th ố ộ + Ki u char g m 26 ch Latin ((‘A’<=x) and (x<=’Z’)), 10 ký s ( 0 .. 9) và m t
ự ắ ệ ằ <> khác b ng (khác) ỏ ơ < nh h n ỏ ơ <= nh h n ho c b ng ơ ớ > l n h n ơ ớ >= l n h n ho c b ng ồ ữ tr ng.
ồ t, ký t (Enuerated Types) ồ ộ ậ ( kí t ể ự ặ ố s ký t đ c bi ệ ể t kê Ki u li ể Ki u li t kê các
danh hi uệ ư ệ ị ệ ỉ ị ợ t kê g m m t t p h p các giá tr b ng cách li ứ ự ủ (identifier) ch đ nh các giá tr này. Th t ị ằ ể c a các ki u li
t kê đ ệ ệ ượ ị c đ nh nghĩa nh sau: ị ủ ị ỉ Type T = (c1,c2,…, cn) trong đó c1,c2,…, cn là các danh hi u ch đ nh các giá tr c a
ể ki u li t kê.
ề ộ ị
ệ Ví d : ụ Type shape = (rectange, square, ellipse, circle) ể ợ ả ể ộ ễ ị ị
ủ ề ế ể ạ ộ ộ ỉ ằ ế ườ Ki u mi n con ng h p m t bi n có giá tr ch n m trong m t (Subrange Types) là tr ằ ể ể ượ ề kho ng xác đ nh nào đó c a m t ki u. Đi u này có th đ c bi u di n b ng cách đ nh nghĩa bi n thu c ki u mi n con theo d ng:
ự ồ ợ
ượ này đ ọ ự ủ ự ỗ . Các chu i kí t ỗ ượ c a chu i đ c ghi trong ề c g i là chi u dài . S ký t ộ ậ i đa 255 ký t
ỗ (string). G m m t t p h p các kí t ố ự ố ư Type T= min … max ể Ki u chu i ơ ấ hai d u nháy đ n (‘) và có t ượ ủ c khai báo nh sau: c a chu i, đ
ỗ Var s : string[10] ;
ấ ể ữ ệ 1.2.2. Các ki u d li u có c u trúc.
ể ả a. Ki u m ng.
ả ộ ả ể ộ
ượ ị ỉ ố ứ ữ ệ ộ ề ề ộ đ
ồ
ả ề ả ố ị
ị ủ ữ ệ M ng là m t b ng ch a d li u có cùng ki u, trên các hàng c t, giá tr c a d li u ả ạ c xác đ nh theo ch s hàng, c t. Có hai lo i m ng: M t chi u, hai chi u. ỉ ố ươ ứ ủ Bao g m có tên c a m ng và ch s t ng ng ố Ví d :ụ M ng m t chi u a(n) v i n là s nguyên nào đó, cho xác đ nh s ph n t ớ ộ ầ ử ứ ầ ử ủ ượ ẳ ạ ị ả ỉ ố c xác đ nh theo ch s , ch ng h n ph n t ầ ử ủ c a ủ th 3 c a
ả ả m ng, ph n t m ng a ta ghi a[3] (d u ngo c vuông).
ề ả ộ ộ , g m có n hàng, m c t, m t ph n t ầ ử
ứ ứ c a m ng đ ặ ấ ườ M ng hai chi u a(n,m) th ầ ử ở th i,j nào đó có nghĩa là ph n t ng có nxm ph n t ộ ầ ử ồ ứ hàng th i, c t th j.
ộ ề ả * M ng m t chi u.
2
Cú pháp:
+ Khai báo gián ti p:ế
ả ể ể ữ ệ ỉ ố Ki u TYPE
ả ể VAR
+ Khai báo tr c ti p:
ỉ ố ả VAR
ả ượ ố ớ ị ế
ả
ự ế
ể ữ ệ ;
ế
ặ ỉ ố Chú ý: Ch s trong khai báo đ i v i Pascal ph i đ ụ ể ho c ghi c th .
ề ả * M ng hai chi u.
Cú pháp:
+ Khai báo gián ti p:ế
ể ữ ệ ỉ ố ỉ ố
ả ả ể ả TYPE VAR
ể
ể ữ ệ ỉ ố ỉ ố ế ả VAR
Ví d :ụ
TYPE Mangnguyen = Array[1..100] of Integer;
Matrix = Array[1..10,1..10] of Integer; MangKytu = Array[Byte] of Char;
VAR A: Mangnguyen; M: Matrix; C: MangKytu;
Ho c:ặ
VAR A: Array[1..100] of Integer;
C: Array[Byte] of Char;
ể b. Ki u xâu ký t ự .
Chúng ta gọi kiểu dữ liệu có giá trị là tập những kí tự là kiểu xâu kí tự hay nói một
cách ngắn gọn là kiểu xâu.
Pascal có từ khoá STRING để người dùng khai báo cho dữ liệu có giá trị là tập
những kí tự.
Ví dụ ta khai báo biến A có kiểu là tập những kí tự như sau: VAR A : STRING ; máy dành cho biến A có thể lưu giữ được một tập có không
quá 255 kí tự.
Hằng văn bản phải để trong cặp dấu nháy cao (‘).
* Khai báo.
ể TYPE TênKi u = STRING[Max];
ế ể VAR
3
ế ặ Tên bi n : TênKi u; ự ế ho c khai báo bi n tr c ti p:
ế VAR Tên bi n : STRING[Max];
(cid:0) ố ể ứ ỗ ế [0,255]). N u không có
ố ỗ i đa có th ch a trong chu i (Max m m c đ nh trong chu i là 255.
ự ố t Trong đó Max là s ký t ự ặ ặ ị khai báo [Max] thì s ký t Ví d :ụ
Type Hoten = String[30];
St80 = String[80];
ố
Var
ự i đa là 255 ký t }
Name : Hoten; Line : St80; St : String; {St có t
ấ * Truy xu t ph n t ầ ử .
ể ử ụ ủ ụ ể ấ ấ ậ ế Có th s d ng các th t c xu t nh p Write, Writeln, Readln đ truy xu t các bi n
ể
ấ ế ự ứ ự ử ụ ki u String. ể ủ th k c a xâu ký t , ta s d ng cú pháp sau: ế Tênbi n[k] . Đ truy xu t đ n ký t
ủ ụ ự
ủ ự ề ấ * Các th t c và hàm trên xâu ký t Hàm l y chi u dài c a xây ký t
LENGTH(St : String):Integer;
Hàm COPY(St : String; Pos, Num: Byte): String;
ấ ừ ộ ự ắ ầ ừ ị ộ L y ra m t xâu con t trong xâu St có đ dài Num ký t b t đ u t v trí Pos .
Hàm POS(SubSt, St :String):Byte;
ể ế ằ ằ Ki m tra xâu con SubSt có n m trong xâu St hay không? N u xâu SubSt n m trong xâu
ả ề ị ầ ủ St thì hàm tr v v trí đ u tiên c a xâu con SubSt trong xâu St, ng ượ ạ c l i hàm tr v ả ề
ị giá tr 0.
ủ ụ Th t c DELETE(Var St:String; Pos, Num: Byte);
ự ắ ầ ừ ị Xoá trong xâu St Num ký t b t đ u t v trí Pos.
ủ ụ Th t c INSERT(SubSt: String; Var St: String; Pos: Byte);
ắ ầ ạ ị Chèn xâu SubSt vào xâu St b t đ u t i v trí Pos.
ủ ụ Th t c STR(Num; Var St:String);
ổ ố ự ạ ự ế ả ư ế Đ i s nguyên hay th c Num thành d ng xâu ký t , k t qu l u vào bi n St.
ủ ụ Th t c VAL(St:String; Var Num; Var Code:Integer);
ả ư ế ệ ế ế ể ố ố ổ ổ Đ i xâu s St thành s và gán k t qu l u vào bi n Num. N u vi c chuy n đ i thành
ế ị ủ ỗ ế ị công thì bi n Code có giá tr là 0, ng ượ ạ c l ị i bi n Code có giá tr khác 0 (v trí c a l i).
ể ả c. Ki u b n ghi.
ế ư ế ể ạ ộ Nh ta đã bi
ỉ ể ữ ệ ể ộ ể ả ẳ
ư ự ở ộ ệ ế ả
ả ộ ậ ứ ạ ể ạ ợ
4
ị ằ ượ ể ộ ị ỗ ộ t các ki u d li u đã có, m i bi n thu c m t lo i ki u nào đó thì giá tr ể ố ạ ộ ủ c a chúng ch thu c m t ki u đó: Ch ng h n ki u s nguyên, ki u m ng…Trong khi ể đó ki u b n ghi có th coi nh s m r ng các khái ni m bi n và m ng, nó cho phép ữ ế ơ ử ư và x lý các d ng thông tin ph c t p h n. RECORD là m t t p h p các bi n, l u tr ấ ả c hi n th b ng m t tên duy nh t. các m ng và đ
* Khai báo.
ể TYPE TênKi u = RECORD
Field1 : Ki u1;ể Field2 : Ki u2;ể
... FieldN: Ki uN;ể
END;
ể ế VAR Bi n : TênKi u;
Ví dụ: TYPE HocSinh = Record
Hoten : String[20]; Tuoi : Integer; DiemTB : real;
End;
VAR HS : HocSinh;
ỏ ể 1.2.3. Ki u con tr .
ể ủ ể ế ỏ ộ
* Khai báo Type Var
ế ể ỏ
Ví d 1ụ :
Type
TroNguyen = ^integer;
Var
p, q: TroNguyen;
ế ế
ể ể ỏ ế ỏ ế ỏ ộ ế Sau khai báo này các bi n p và q là các bi n con tr có th tr đ n các bi n đ ng có ớ ủ ỗ ng trình s c p phát 4 byte cho m i bi n con tr . Còn vùng nh c a
ươ ư ượ ấ ẽ ấ c c p phát.
ki u integer. Ch ộ ế các bi n đ ng ch a đ Ví d 2ụ :
Type
TroSv = ^ Sinhvien; Sinhvien = Record
5
Hoten: String[20];
Diem: real; Tiep: TroSv;
End;
Var
p: TroSv;
ế ả
ể ỏ ế ỏ ể ỏ ế ỏ ộ ể ộ ườ ế ế Trong ví d này, p là bi n tr có th tr đ n các b n ghi có ki u Sinhvien, trong ng Tiep là m t bi n tr có th tr đ n bi n đ ng khác cũng có ụ i có tr
ạ ả b n ghi này l ể ki u Sinhvien.
ệ ớ ế ộ * Làm vi c v i bi n đ ng
ấ ớ C p phát vùng nh
ủ ụ
ỏ
Dùng th t c New theo cú pháp:
ế
New(
i phóng vùng nh Dùng th t c ủ ụ Dispose(p);
ủ ụ ả ạ ộ ế ỏ Trong đó p là m t bi n con tr . Th t c Dispose cho phép tr l ớ ộ i b nh đ ng đã
ượ ấ ộ ủ ụ đ ở c c p phát b i th t c New.
ộ ứ ạ ậ ậ . 1.3. Thu t toán và đánh giá đ ph c t p thu t toán
ậ 1.3.1. Thu t toán.
ệ ậ ả ậ a. Khái ni m thu t toán (hay Gi i thu t).
ậ ặ Thu t toán hay gi
ậ ộ ộ ố ữ ố ượ ắ ạ ằ ẽ i thu t là m t h th ng ch c ch và rõ ràng các quy t c nh m xác ự ướ c th c ng, sao cho sau m t s h u h n b
ế ộ ệ ố ả ị ữ đ nh m t dãy các thao tác trên nh ng đ i t ả ệ hi n các thao tác thì cho k t qu .
ư ủ ặ ả ậ b. Các đ c tr ng c a gi i thu t.
ướ ả ủ ệ ế ộ * Tính xác đ nhị ả ậ ồ i thu t bao g m các b ỗ ề c rõ ràng. Trong cùng m t đi u ki n thì k t qu c a m i
Gi ướ b c là xác đ nh. * Tính h u h n d ng
ộ ố ữ ạ ả ướ ế ị ữ ạ ừ ậ i thu t sau m t s h u h n b Gi ả c thì cho k t qu .
* Tính đúng đ n.ắ
ả ả ượ ế ả ố c c a gi i thu t ph i cho đ ế c k t qu mong mu n, k t
ướ ủ ị ệ ị ự Sau khi th c hi n các b ả c xác đ nh theo đ nh nghĩa có tr ậ ướ c.
qu đó đ * Tính ph d ng
ả ế ượ ộ ớ Gi i quy t đ c cho m t l p bài toán.
ả ữ ệ ệ ế ậ ậ ả ậ i thu t là vi c nh n d li u vào (Input) – k t thúc gi ộ i thu t là m t
6
ượ ổ ụ ả ậ ả i thu t ph i gi ạ ượ * Tính có đ i l ng vào và ra ộ ắ ầ B t đ u m t gi ả ữ ệ ố ế s k t qu (d li u ra Output).
ệ
ự ẩ ả ủ ậ ượ c đánh giá d a trên các tiêu chu n sau:
i thu t đ ế t
ệ
ầ ả * Tính hi u qu . ả ộ Tính hi u qu c a m t gi ượ ộ ầ ng b c n thi ầ ự ng phép tính c n th c hi n. ế ể ạ t đ ch y.
ễ ặ ệ Dung l ố ượ S l ờ Th i gian c n thi ễ ể D hi u và d cài đ t.
ể ễ ậ c. Bi u di n thu t toán
ườ ễ ậ ấ ả ướ ng có hai cách bi u di n m t thu t toán, cách th nh t là mô t các b ự c th c
Th ệ ủ ộ ử ụ ơ ồ ả ứ ậ ể hi n c a thu t toán, cách th hai là s d ng s đ gi ứ ậ i thu t.
ả ướ ự ệ Mô t các b c th c hi n.
ậ ả ự ể ể chính xác các b
ể ướ ữ ự i ta mô t ậ ủ ộ
ữ ậ ộ ớ
ướ ố ả ậ ớ ố ấ ủ c s chung l n nh t c a hai s nguyên. thu t toán tìm
ấ ủ
ậ ệ ườ ễ Đ bi u di n thu t toán ng c th c hi n c a thu t ặ ể ả ữ nhiên ho c m t ngôn toán, ngôn ng dùng đ mô t thu t toán có th là ngôn ng t ữ ạ ọ ữ ự ữ ng lai ghép gi a ngôn ng t nhiên v i m t ngôn ng l p trình nào đó g i là các đo n ệ ả mã l nh. gi Ví d 1:ụ mô t ố Input: Hai s nguyên a, b. ớ Ướ ố Output: c s chung l n nh t c a a, b. ậ
́
́ ́ ́ ́ ạ ướ i b ạ ướ i b B c 1: N u a=b th USCLN(a, b)=a. ủ B c 2: N u a > b th tm USCLN c a ab và b, quay l ủ B c 3: N u a < b th tm USCLN c a a và ba, quay l
2 + bx +c = 0, ta có th mô t
c 1; c 1; ể ươ ả ậ ằ ậ ng trình b c hai ax thu t toán b ng
ữ ệ
ệ ố
ể
Thu t toán: ế ướ ế ướ ế ướ ể ả Ví d 2:ụ Đ gi ngôn ng li ướ ướ ế ự ạ i ph ư t kê nh sau: ị B c 1: Xác đ nh các h s a,b,c. ệ ố B c 2 :Ki m tra xem các h s a,b,c có khác 0 hay không ? ệ ướ N u a=0 quay l c 1.
i th c hi n b ể ứ ướ
b a *2
ướ = b2 – 4*a*c. ươ ệ ể ướ B c 3: Tính bi u th c ế D B c 4:N u <0 thông báo ph ng trình vô nghi m và chuy n sang b c 8. (cid:0) ướ ướ B c 5:N u ế D =0,tính x1=x2= ể và chuy n sang b c 7.
1=
a
b *2
b a *2 1 , x2 .
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ướ ướ B c 6: Tính x , x2= ể và chuy n sang b c 7.
ướ ướ ế ậ ệ B c 7: Thông báo các nghi m x B c 8: K t thúc thu t toán.
ử ụ ồ ả ậ S d ng l u ư đ gi i thu t.
́ ử ụ ứ mang tính hnh th c
7
ả S d ng các k hi u hnh kh i c b n đ t o thành m t mô t ậ ố ơ ả ả ệ ể ạ ướ ộ ệ ự ơ ́ ớ ư ệ ơ (cách này r ràng h n so v i vi c mô t c th c hi n thu t toán). các b
5
ắ ầ B t đ u
Câu l nhệ
1
3
ậ
ấ Nh p, Xu t
4
Đúng
2
Đi u ề ki nệ
K t ế thúc
Sai
ỉ ấ ộ ườ ố ắ ầ ng ra.
ể ố ế ng vào.
ệ ự ộ ườ ề ể ệ ặ ồ ộ Th c hi n câu l nh (có th là m t ho c nhi u câu l nh); g m m t đ ng vào
ộ ườ ng ra. ẽ ứ ứ ề ể ể ể ể ế
ứ ẽ ế ể ẽ ậ
ấ ữ ệ ệ ậ ậ Kh i 1:ố Kh i b t đ u thu t toán, ch có duy nh t m t đ Kh i 2:ố Kh i k t thúc thu t toán, có th có nhi u đ ề ườ ậ Kh i 3:ố ệ và m t đ Kh i 4:ố ứ ệ R nhánh, ki m tra bi u th c đi u ki n (bi u th c Boolean), n u bi u th c ậ đúng thu t toán s đi theo nhánh Đúng (True), n u bi u th c sai thu t toán s đi theo nhánh Sai (False). Kh i 5:ố Các câu l nh nh p và xu t d li u.
ự ờ ệ ả ậ d. Phân tích th i gian th c hi n gi i thu t.
ỏ ả ộ ờ ố ớ ả ỏ i gi ộ M t gi i thu t cho m t l ộ i th a đáng đ i v i m t bài toán ph i th a:
ả ườ ướ ệ Th ng là th i gian mà máy s d ng đ gi
ờ ướ ử ụ ướ
ệ ớ ộ ị c xác đ nh. Th ị ầ ớ ướ ộ ả ng b nh đòi h i đ th c hi n gi ể ả ế i quy t ứ c đo th hai là dung c xác i thu t ng v i giá tr đ u vào có kích th
ả ậ Đúng. ả ệ Hi u qu . ề c đo v tính hi u qu th ị ầ bài toán, khi các giá tr đ u vào có m t kích th ượ ậ ứ ỏ ể ự l ị đ nh.
ầ ự ướ
ộ ờ S phân tích th i gian c n thi ế ủ ờ ộ ế ủ i m t bài toán có kích th ớ ầ i thu t. S phân tích b nh c n thi c nào đó, liên t c a máy
ậ
ữ ệ ượ ể ự c dùng đ th c
8
ứ ạ quan đ n đ ph c t p th i gian c a gi ộ ứ ạ ế tính liên quan đ n đ ph c t p không gian c a gi ứ ạ ộ ầ ộ ế ể ả t đ gi ự ậ ả ả ủ i thu t. ắ ớ ấ ộ ứ ạ ế ậ ờ ự S xem xét đ ph c t p không gian g n v i c u trúc d li u đ ả i thu t. Trong ph n này ta xét đ n đ ph c t p th i gian. ệ hi n gi
ỷ ệ ớ ướ ữ ệ ệ v i kích th l c d li u, ký hi u là T(n),
Đ ph c t p th i gian là m t hàm t ướ ữ ệ ứ ạ ộ trong đó n là kích th
ờ ộ c d li u vào. ể ể ơ ị ờ
ấ ễ ệ ố ặ ậ
ượ ự
ờ ờ ậ ậ
1(n) = an2 2(n) = kn ả
1(n) >=T2(n). V y gi
Tuy nhiên T(n) không th bi u di n thành đ n v th i gian là giây, phút…(do các máy tính có c u hình khác nhau, h th ng khác nhau…). M c dù v y, chúng ta hoàn ị ủ ể ụ toàn có th so sánh đ c d a vào các giá tr c a hàm. Ví d : ả ộ ứ ạ i thu t 1: Đ ph c t p th i gian T ộ ứ ạ ả i thu t : Đ ph c t p th i gian T ậ ậ ả ớ ơ Gi Gi Khi n l n rõ ràng là T ậ i thu t 1 ch m h n gi ậ i thu t 2.
ộ ứ ạ ủ ả ậ 1.3.2. Đánh giá đ ph c t p c a gi i thu t.
3). Gi
ớ ự ệ ươ ả
su t tăng là n
i thu t P1 và P2 v i th i gian th c hi n t su t tăng là n ướ ữ ệ ộ ơ ự s ta có hai gi ớ ỷ ấ ệ ậ 2) và T2(n) = 5n 3(v i t ả ờ ờ ớ ỷ ấ i ph thu c vào kích th
ệ ố ủ ẽ
3 (2<3).
ỏ ơ ỏ ơ ố ủ ủ ư
ờ ươ ạ c l ế
ữ ệ ề ườ ự
ươ ự ệ ờ ứ ng ng là T1(n) = ẽ ậ ả i thu t nào s ớ c d li u vào. V i n < 20 thì 2 (5<100). 3 nh h n h s c a 100n 2 nh h n s mũ c a 5n ố đâyỞ ệ ủ ự ng h p n>20 vì khi n<20 thì th i gian th c hi n c a ư ậ ể Nh v y t gi a T1 và T2 là không đáng k . ng trình thay vì su t tăng c a hàm th i gian th c hi n ch
ờ ợ ả
0 sao cho
ế ồ ạ ộ ằ i các h ng C, N
ệ ọ ỷ ấ su t tăng là f(n)) và kí hi u T(n) là O(f(n)) ệ ộ ứ ạ 0 (t c là T(n) có t
ọ
ỷ ấ su t tăng là n
2 nên T(n)= (n+1)2 là O(n2) ố Ð c bi ặ ậ
ệ ằ ớ t O(C)=O(1)
ộ ặ i thu t là m t hàm ch n trên c a hàm th i
ủ ặ ủ ể ỏ
ạ ườ ể ệ
ờ C trong hàm ch n trên không có ý nghĩa nên ta có th b qua vì ặ ng g p sau: ộ ứ ạ ộ ứ ạ ộ ứ ạ ộ ứ ạ Đ ph c t p nlogn. ứ Đ ph c t p đa th c. Đ ph c t p hàm mũ. Đ ph c t p n!.
ằ
9
ả ử
Gi
100n2 (v i t
ụ
th c hi n nhanh h n? Câu tr l
ệ ố ủ
ơ
P2 s nhanh h n P1 (T2
ị ộ ứ ạ . Xác đ nh đ ph c t p tính toán
ắ ộ * Quy t c c ng:
ả ử ươ ạ ờ Gi
s T1(n) và T2(n) là th i gian th c hi n c a hai đo n ch ệ ệ ủ ờ ự ồ
ự ng trình P1 ế và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì th i gian th c hi n P1 r i P2 ti p theo s là:ẽ
ươ ướ ộ ự ự ệ ệ ờ c th c hi n mà th i gian th c hi n
n) thì th i gian th c hi n 2 b
ự ệ ờ ướ T1(n) + T2(n) = O(Max(f(n),g(n)). ng trình có 3 b 2), O(n3) và O(nlog2 t là O(n c
Ví d 1ụ : Trong m t ch ướ ầ ượ ừ t ng b c l n l ầ đ u là:
ệ
n) = O(n3). ớ ≤ f(n) v i m i n
ng trình s là ắ O(max(n2,n3) = O(n3). ẽ : O(n3,nlog2 ươ ự ờ Th i gian th c hi n ch ế ủ ụ ộ ứ M t ng d ng khác c a quy t c này là n u g(n)
ẳ ạ : O(n4 + n2) = O(n4) và O(n+Log2 ọ ≤ no thì n) =
ộ ằ ệ ệ ố ờ ọ
ự ệ ả ậ ờ ờ
ố ố ế O(f(n) = g(n)) cũng là O(f(n)). Ch ng h n O(n). Ví d 2ụ : L nh gán x:=15 t n m t h ng th i gian hay O(1), L nh đ c d li u ữ ệ ệ ộ ằ READ(x) t n m t h ng th i gian hay O(1).V y th i gian th c hi n c hai l nh trên n i ti p nhau là O(max(1,1))=O(1).
ắ * Quy t c nhân :
ế ươ ủ ờ
ạ N u T1(n) và T2(n) là th i gian th c hi n c a hai đo n ch ệ ủ ệ ờ ự ạ ự ng trình P1và ạ P2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì th i gian th c hi n c a đo n hai đo n
ươ ch ng trình đó là T(n) = O(f(n).g(n)). ồ l ng nhau
ắ ổ ộ ươ ể Qui t c t ng quát đ phân tích m t ch ng trình:
ờ ờ ỗ ệ ộ ệ các l nh đ
ệ ủ Th i gian th c hi n c a m i l nh gán, READ, WRITE là O(1). ủ ệ Th i gian th c hi n c a m t chu i tu n t ờ ắ ầ ự ờ ượ ộ ệ ộ
ỗ ệ ấ ự ằ ị ỗ ự c xác đ nh b ng ư ậ qui t c c ng. Nh v y th i gian này là th i gian thi hành m t l nh nào đó lâu nh t trong chu i l nh.
ờ ự ệ ờ
ớ ệ ườ ề ể ệ ệ ự Th i gian th c hi n c u trúc IF là th i gian l n nh t th c hi n l nh sau ể ờ ng th i gian ki m
ề ấ ấ ặ ờ THEN ho c sau ELSE và th i gian ki m tra đi u ki n. Th ệ tra đi u ki n là O(1).
ờ ự ấ ả
ổ ế ặ ờ ờ ệ ệ ặ
ớ ờ ặ ệ ệ ự ự ự ờ Th i gian th c hi n vòng l p là t ng (trên t ệ ự ủ ố ầ ặ
ượ ự ệ ằ ằ ờ ố c đánh
ự ệ ậ ả i thu t là O(n.1) = O(n).
ầ ặ ổ t c các l n l p) th i gian ặ th c hi n thân vòng l p. N u th i gian th c hi n thân vòng l p không đ i thì th i gian th c hi n vòng l p là tích c a s l n l p v i th i gian th c hi n thân vòng l p. ặ Ví d 3ụ : ệ 1. Câu l nh gán: x:=x+1 có th i gian th c hi n b ng c (h ng s ) nên đ giá là O(1). 2. Câu l nh:ệ For i:=1 to n do x:=x+1; ờ Có th i gian th c hi n gi 3. Câu l nh:ệ For i:=1 to n do
2)
ậ ượ c đánh giá là O(n.n) = O(n i thu t đ
ệ ệ
For j:=1 to n do x:=x+1; ả ự ờ Có th i gian th c hi n gi ả ử s có hàm đ qui: 4. Gi Function Vidu(n:integer):Real; Begin
If n=1 then Vidu:=K {1} Else
Vidu:=K/(2*n3)+Vidu(n1). {2}
ự ự ệ ệ ờ End ; ờ G i th i gian th c hi n phép gán {1} là a, th i gian th c hi n phép chi {2} là
ọ b thì :
T(n) = b+T(n1)
= b+b+T(n2) = b+b+...+T(1)
T(n) = b(n1)+a.
(cid:0) ấ T(n) ≤ Cn, (cid:0) n. V yậ
L y C = Max(a,b) T(n) là O(n).
ươ
Ch
ng 2: DANH SÁCH
o0o
ị 2.1. Đ nh nghĩa danh sách.
ạ ộ ậ (element) a
ố ữ ệ ươ ế ố ượ
ầ ử i thì s đ nh đ ộ a ộ ữ 1, a2, …, an, gi a các ị ẽ ị c v trí t ph n t ể ắ thu c m t danh sách có th s p
ụ ộ
ầ ử Danh sách là m t t p h u h n các ph n t ế ầ ử ng đ i: N u bi ph n t có m i quan h t ầ ử ơ ầ ử i+1. Nói cách khác h n, các ph n t ph n t a ế ế x p tuy n tính. Ví d 1: Danh sách sinh viên là m t danh sách. ộ ể ữ ệ ả Ki u d li u m ng trong pascal là m t danh sách.
2.2. Danh sách đ c.ặ
ị 2.2.1. Đ nh nghĩa.
ộ ế ế ế ầ ử ượ ắ đ c s p x p k ti p nhau
ặ Danh sách đ c là m t danh sách mà các ph n t ớ ộ trong b nh .
ổ ứ ấ ữ ệ 2.2.2. T ch c c u trúc d li u.
ầ ử ễ ể ặ ộ Ta bi u di n danh sách đ c là m t dãy n ph n t
a[1]
a[2]
...
a[n]
ư ặ ộ ố ộ Ta khai báo m t danh sách đ c là m t dãy s nguyên a[1], a[2],..., a[n] nh sau:
const
elemno = 100;
var
a: aray [1..elemno] of integer;
2.2.3. Các phép toán trên danh sách:
ở ạ a. Kh i t o danh sách :
ầ ử ằ ế ố ỗ Khi kh i t o danh sách, n u danh sách là r ng ta cho s ph n t b ng 0
ở ạ ậ * Thu t toán
Procedure Initialize;
Begin n :=0;
End;
ầ ử ộ b. Thêm m t ph n t vào danh sách:
ộ ầ ử ứ ừ cũ t a[i]
ầ ử ể vào danh sách t ướ ề c di chuy n v phía sau 1 b ạ ị i v trí th i thì các ph n t c.
Khi thêm m t ph n t ượ ế đ n a[n] đ ậ Thu t toán:
Procedure Insert_element(i : integer; Newinfo : integer); Var
j : integer ;
Begin
For j:= n downto i do a[j+1] := a[j]; a[j] := Newinfo ; n:= n +1 ;
end;
ạ ỏ ộ ầ ử ủ c. Lo i b m t ph n t c a danh sách:
ầ ử a[i] c a danh sách, các ph n t còn l ạ ừ i t ế a[i+1] đ n
ạ ỏ Khi lo i b ph n t ể ượ ầ ử ề ộ ướ c di chuy n v phía tr ủ ướ c m t b c.
a[n] đ ậ Thu t toán:
Procedure Delete_element( i : integer); Var j: integer; Begin
For j:= i to n do a[j] :=a[j+1]; n := n1;
end;
ầ ử ộ ế d. Tìm ki m m t ph n t trong danh sách:
ộ ặ ể
ầ ử ầ ự ớ ế ậ ứ ự ư ế Khi tìm ki m m t ph n t thu t toán tìm ki m tu n t trong danh sách đ c có khoá là k, ta có th dùng ậ , hay thu t toán tìm
ế ớ ị ứ ự ẽ ơ ki m nh phân v i danh sách đã có th t v i danh sách ch a có th t ứ . Ta s nghiên c u kĩ h n trong bài 4.
ượ ể Ư 2.2.4. u nh ụ . ứ c đi m và ng d ng
Ư ể u đi m:
ậ ộ ử ụ ễ ử ụ ờ ị ỉ a[i] nh đ a ch . ế ể ầ ử ệ ấ ế ậ ế ậ + M t đ s d ng là 100%. + D dàng truy xu t đ n ph n t + S d ng các thu t toán hi u năng đ tìm ki m (thu t toán tìm ki m nh ị
phân).
ể ế Khuy t đi m:
ụ ớ ố ị
ệ ự ờ vào danh sách th i gian th c hi n t ệ ỷ ệ l
ớ ố ượ v i s l ng ph n t
ị ng các ph n t có cùng giá tr cao.
ớ + Không gian nh c đ nh, vùng nh liên t c. ạ ỏ ộ ầ ử + Vi c thêm là lo i b m t ph n t ầ ử ủ c a danh sách. T(n)max = O(n). ầ ử ố ượ ộ ả ớ ượ ộ + Lãng phí khi s l + B nh đ c qu n lý kém linh đ ng.
ế 2.3. Danh sách liên k t, các phép toán.
ị 2.3.1. Đ nh nghĩa.
ế ầ ử ượ ố ế ph n t đ c n i k t nhau nh ờ Danh sách liên k t là danh sách mà các
ế ủ vào vùng liên k t c a chúng.
ạ ấ ả ớ ơ ợ
ế ạ ỏ ề Danh sách liên k t là m t lo i c u trúc đ n gi n và thích h p v i các các phép toán này
ợ ộ phép thêm vào, phép lo i b , phép ghép nhi u danh sách mà ạ l ặ . i không thích h p cho danh sách đ c
ế ơ 2.3.2. Danh sách liên k t đ n.
ổ ứ ấ ữ ệ 2.3.2.1. T ch c c u trúc d li u.
ỗ ầ ử ủ ượ ư Danh sách liên k t là danh sách mà m i ph n t c a danh sách đ
ầ ử ọ ế c l u tr nh mà ta g i là nút (node). Các nút này có th n m b t k
ầ ộ ớ
ầ ử ỗ ủ ữ ấ ỳ ứ còn có đ ng sau nó trong danh sách. Qui cách c a m i nút có
INFO LINK
ư ớ ể ằ ộ trong m t ph n t ớ ộ ỗ trong b nh . Trong m i nút, ngoài ph n thông tin ng v i m t ph n t ầ ử ứ ỉ ủ ứ ị ch a đ a ch c a ph n t ể th hình dung nh sau:
ủ .
ườ ườ ầ ử ế ứ ứ ị ỉ ủ Tr Tr ng INFO ch a thông tin c a ph n t ng LINK ch a đ a ch c a nút ti p theo.
ứ
ế ỉ ị
ộ nút này ph i là m t “đ a ch đ c bi ư ấ ố ố ỉ ặ ỉ ở ể ọ ị ố Riêng nút cu i cùng trong danh sách thì không có nút đ ng sau nó nên m i ệ t” đ dùng đ đánh d u nút k t thúc các nút khác ta g i là “m i n i không” và
ệ ố ả ố ở n i ứ danh sách ch không nh các đ a ch ký hi u là nill.
ậ ể ấ
ượ ầ đ
ỏ ớ ả ỏ ộ ể
A
D
First
B
C
ậ ả ọ ể t nhiên là ph i truy nh p Đ có th truy nh p vào m i nút trong danh sách, t ầ ộ ầ c vào nút đ u tiên, nghĩa là c n có m t con tr First tr t i nút đ u tiên này. ố ẽ ỉ ố ố ế N u dùng mũi tên đ ch m i n i, ta s có m t hình nh danh sách móc n i ư ơ đ n nh sau:
ỉ ố ố ườ ướ ế ỗ ch m i n i không. Ng i ta quy c: N u danh sách r ng thì
D uấ First= null.
Type
Tro=^nut; Nut=Record
Info:Element; Link:Tro;
End;
Var First:Tro;
ồ ỗ
ư ể Ví dụ: Danh sách sinh viên bao g m nh ng sinh viên mà m i sinh viên có ki u ữ ữ ệ record nh sau: d li u
Type
Tro = ^sinhvien; sinhvien = record; mssv : integer; hoten : string[30] ;
tenlop : string[8]; link : tro;
end; Trong đó các vùng (field): mssv, hoten, tenlop là các vùng info và vùng link
là vùng liên k t.ế
ộ ầ ử ặ ệ ế
ể ữ ề ồ đ c bi ế ề ể t (bi n ki u ư t v danh sách nh
ầ ử ủ ế Ngoài ra, danh sách liên k t có th có m t ph n t ể record) bao g m nhi u vùng đ ghi nh ng thông tin c n thi ề ố s ph n t ầ , tên danh sách, chi u dài c a các vùng,…v.v.
ế ơ 2.3.2.2 Các thao tác trên danh sách liên k t đ n.
ở ạ a. Kh i t o danh sách.
ở ạ ỗ ế Khi kh i t o danh sách liên k t, danh sách là r ng, ta cho First là nil.
Procedure khoitao; Begin
First:=nil;
End;
ầ ử ộ ế . b. Tìm ki m m t ph n t trong danh sách
ầ ử ế ộ ế ượ Tìm ki m m t ph n t có vùng c b t đ u t
ầ ử ầ ầ ự ồ ầ ử ế ế đ u tiên r i tu n t
ph n t ế ấ Info là x. Phép tìm ki m đ ế ể ế theo vùng liên k t đ đ n ph n t ầ ử ặ toán k t thúc khi tìm th y ph n t
ấ có vùng ứ ự ệ ơ
ỉ ủ ớ ả ề ế ầ ầ ử ấ ắ ầ ừ ậ k ti p. Thu t ế Info là x ho c đi h t danh sách mà ẽ ế thì vi c tìm ki m s k t thúc s m h n. ị ặ tìm th y đ u tiên ho c tr v giá tr
ế không tìm th y. N u danh sách có th t ả ề ị Hàm Search tr v đ a ch c a ph n t ế ấ nil n u không tìm th y.
ườ ư ợ * Tr ng h p danh sách ch a có th t ứ ự:
ả ắ ầ ừ ầ ử ầ ế Ta ph i tìm ki m
ế khoá x b t đ u t ế ph n t ế đ u tiên cho đ n khi tìm ế ặ
ấ th y khoá này trong danh sách ho c cho đ n khi h t danh sách n u không tìm th y.ấ
ỉ ủ ầ ử ầ ộ đ u tiên có n i dung là x (tìm
ả ề ặ ả ề ị Hàm Search tr v đ a ch c a ph n t ị nil (không tìm th y)ấ . th y)ấ ho c tr v giá tr
ậ Thu t toán :
Function Search (x:Element) : tro; Var
p:tro; found : boolean;
begin
found := false; p := first; while ( p<> nil) and ( not found) do if p^.info = x then found := true else p := p^.Link;
Search := p;
end;
ườ ợ ứ ự :
ng h p có th t ặ * Tr ạ D ng l p:
ứ ự ế Vì danh sách đã có th t
ặ ầ ử ệ ạ ỉ ầ ế nên ta ch c n tìm ki m khoá x cho đ n khi tìm ủ i luôn ế hi n t
ế ấ ơ ấ th y khoá này trong danh sách ho c cho đ n khi khoá c a ph n t ớ l n h n x n u không tìm th y.
ầ ử ầ ộ ả ề ị ủ ặ đ u tiên có n i dung là x (tìm g p)
Hàm Search tr v giá tr c a ph n t ặ ả ề ặ ị ho c tr v giá tr nil (không tìm g p).
ậ Thu t toán :
Function Search (i: Element):tro;
Var
p:tro;
Begin
p:= First;
while (p<> nil) and (p^.info
End;
ầ ử ộ c. Thêm m t ph n t vào danh sách :
ườ ầ ử ượ . Ta cho vùng liên ợ 1 : Ph n t p đ ầ c thêm vào đ u danh sách
ng h p ỉ ỉ Tr ế ủ k t c a p ch vào First, sau đó cho First ch vào p.
ậ Thu t toán:
Procedure Insert_First(Newinfo: element; var First:Tro); Var
p : tro;
Begin
New(p); p^.info := Newinfo; p^.Link := First; First := p;
ườ ầ ử ượ ữ ố Tr end; ợ ng h p 2: Ph n t p đ ặ . c thêm vào gi a ho c cu i danh sách
ầ ử ứ ướ ế ủ ỉ ế c p. Ta cho vùng liên k t c a p ch vào liên k t
đ ng ngay tr ế ủ ỉ ọ G i q là ph n t ủ c a q, sau đó vùng liên k t c a q ch vào p.
ậ Thu t toán :
Procedure Insert_element (q:Tro; NewInfo:Element); Var
p : tro;
Begin
New(p); p^.info := NewInfo; p^.Link := q^. Link; q^.Link := p;
End;
ườ ộ ẫ Tr ợ ng h p 3: ứ ự
ầ Chèn m t nút vào danh sách sau cho danh sách v n có th t ả ầ tăng d n hay gi m d n:
ỉ ủ ầ ử ớ ộ m i có n i dung là NewInfo
ứ ự ả ề ị Hàm Insert_list tr v đ a ch c a ph n t c thêm vào m t danh sách liên k t đã có th t
ướ tăng d n. ế ượ đ before – ph n t ộ ầ ử ứ đ ng ngay tr ế ầ ử c ph n t ầ p theo liên k t.
ậ Thu t toán :
Function Insert_list (NewInfo: element): tro; Var
q,p,before : tro;
Begin
before}
New(p);
p^.info := NewInfo;
ầ ử
{tìm ph n t
q := First;
While (q <> nil) and (q^.Info Begin before := q;
q := q^.Link; End; If q = First then First := p else before^. Link := p;
p^.Link :=q;
Insert_list :=p; End; ạ ỏ ộ ầ ử ủ d. Lo i b m t ph n t c a danh sách. ợ ườ ầ ử ầ ử ầ ng h p . Ta cho chỉ ủ
đ u tiên c a danh sách Tr
ể p là ph n t
ả ế ủ ồ 1 : Ph n t
ỉ
đi m First ch vào liên k t c a p r i gi i phóng p. ầ ử ầ ự ệ ủ
đ u tiên c a danh sách: Th t củ ụ Delete_First th c hi n xoá ph n t Procedure Delete_First(Var First:Tro);
Var p : tro ;
Begin If first <> nil then
Begin P:= first;
First := p^.Link; Dispose(p); End; ườ ầ ử ầ ử ữ Tr p là ph n t Ph n t
ướ ố ủ
gi a hay cu i c a danh sách
ế ủ ế ủ ỉ End;
ợ
ng h p
2 :
ầ ử ứ
đ ng tr c p. Ta cho vùng liên k t c a q ch vào liên k t c a p và gi ọ
. G i q là
ả
i ph n t
phóng p. ế ế ứ ự ệ Th t c ủ ụ Delete_element th c hi n xoá nút đ ng k ti p sau nút q: Procedure Delete_element(q: tro);
Var P : tro; Begin If q^.Link <> nil then Begin p := q^.Link;
q^.Link := p^.Link;
Dispose(p); End; End;
ộ ộ e. Ghép m t danh sách vào m t danh sách khác. ủ ự ệ ế ủ ụ Insert th c hi n ghép danh sách First2 vào k sau nút q c a danh sách Th t c
First1: Procedure Insert(q:tro);
Var p : tro;
Begin ầ ử ố cu i danh sách First2} {tìm ph n t
If First2 <> nil then Begin p:= First2;
While p^.Link <> nil do p:=p^.Link;
p^.Link:=q^.Link; {1}
q^.Link :=First2; {2} End; End; ệ f. Duy t danh sách. ừ ử
Duy t danh sách là thăm và x lý t ng nút trong danh sách. p: Tro; ệ
Procedure Duyet;
Var
Begin p:= First;
While p <> nil do
Begin ử ế ệ
p:= p^.link; {duy t qua nút ti p theo} End; End; Ư ượ ụ ứ ế ể c đi m và ng d ng danh sách liên k t. 2.3.2.3. u nh
Ư ể
u đi m: ữ
c không gian nh đ l u tr . ạ ỏ ượ ễ ớ ể ư
ệ
ự
c th c hi n d dàng. ể ượ
ậ ụ
+ T n d ng đ
ệ ổ
+ Vi c b sung hay lo i b đ
ế ố
ễ
+ D dàng k t n i hay phân rã danh sách.
ấ
ượ
c đi m: Truy xu t tu n t ầ ự
. Nh ữ ế ả 2.3.2.4. So sánh gi a danh sách liên k t và m ng. ầ ổ ỉ ướ ủ ả ầ ử
ố
ế
Danh sách liên k t có s ph n t
c. Ng
i đa c a danh sách tr ể
có th thay đ i và không c n ch rõ kích
ướ
ấ
ượ ạ
c
i m ng là các c u trúc có kích th
c l ướ ố
c t
th
ố ị
c đ nh. ế ạ ầ ử ỏ i, thêm và xóa các ph n t ớ ả ế
kh i danh sách liên k t
ươ
ườ
ng ng t ớ ế ầ ộ ớ ể ắ
Chúng ta có th s p x p l
ộ ố ố ị
ỉ ớ
ch v i m t s c đ nh các thao tác. V i m ng các thao tác này th
ướ
ả
ươ
c m ng.
đ
ả
ầ ử ứ
th i trong m t danh sách liên k t chúng ta c n ph i đi
ả
ướ
c nó trong danh sách (i1 thao tác) trong khi v i m ng ự ủ c c a m t danh sách không ph i hi n nhiên mà bi ầ ử ứ
ề
ng t ả
ộ ế
t
ươ
ng ề ộ ng v i kích th
ế
ể
Đ tìm đ n ph n t
đ ng tr
qua i1 ph n t
ỉ ấ
ể
đ làm đi u này ch m t 1 thao tác.
ể
ộ
ướ
ươ
kích th
T
ả
ướ ủ
ế ơ
ượ
c c a m t m ng trong ch
t r kích th
đ
c trong khi chúng ta luôn bi
ụ
ắ
ể
ả
ơ
trình (tuy nhiên có m t cách đ n gi n đ kh c ph c đi u này). ế 2.3.3. Danh sách liên k t kép. ể ễ 2.3.3.1. Bi u di n danh sách. ỉ ớ ế ơ ệ ể
ệ ẫ ấ ộ ố ứ
ầ ụ
ả ặ ở ỗ ầ
ộ ả ộ ỏ ớ ề
ộ
V i danh sách liên k t đ n ta ch có th duy t danh sách theo m t chi u.
ể ượ
ượ ạ
c l
i. Đ đ
c
ứ
ỏ ỏ ớ
ỏ
m i nút hai con tr , m t con tr tr t
i nút đ ng
ộ
ủ
ư ậ
ứ
i nút đ ng sau nó. Nh v y nghĩa là qui cách c a m t nút c nó và m t tr t Left INFO Right Trong m t s ng d ng đôi khi v n xu t hi n yêu c u đi ng
hai kh năng, c n ph i đ t
ướ
tr
ẽ ư
s nh sau: ớ ỏ ỏ ớ ướ ứ
i nút đ ng tr c. ỏ ớ ứ ỏ i nút đ ng sau nó. ả
ư ế ơ ứ ẫ ố ị V i Left là con tr trái, tr t
Còn Right là con tr ph i, tr t
Còn INFO v n gi ng nh danh sách liên k t đ n (ch a giá tr ). Type Tro=^Nut; Nut = Record Info: Element; Left, Right:Tro; End; Var First, Last: Tro; 2.3.3.2. Các thao tác trên danh sách. ầ ử ộ
1. Chèn m t ph n t trong danh sách Last First A B C D 2 3 (1) P ầ
Chèn vào đ u danh sách: Procedure ChenDau(X:Element; Var First,Last:Tro);
Var p:Tro;
Begin New(p);
P^.info:=X;
P^.left:=nil;
P^.Right:=Nil;
If First=nil then Begin First:=Nil;
Last:=nil; End Else Begin P^.Right:=First;
First^.Left:=p;
First:=p; End; End; 3 Last First A B C D (1) 2 P ố
Chèn vào cu i danh sách: Procedure ChenCuoi(X:Element; Var First,Last:Tro);
Var p:Tro;
Begin New(p);
P^.info:=X;
P^.left:=nil;
P^.Right:=Nil;
If First=nil then
Begin First:=Nil;
Last:=nil; End Else Begin Last^.Right:=p;
P^.Left:=Last; Last:=p; End; End; Last q r First A D B C 4 2 3 (1) P ầ ử ữ ộ
Chèn m t ph n t vào gi a danh sách: Procedure ChenGiua(X:Element; q:Tro);
Var p,r:Tro;
Begin New(p);
P^.Info:=X;
P^.Left:=Nil; P^.Right:=Nil;
r:=Q^.Right;
If r=Nil then
Begin q^.Right:=p;
p^.left:=q;
Last:=p; End Else Begin p^.Right:=r; r^.left:=p;
q^.Right:=p; P^.Left:=q; End; End; ệ 2. Duy t qua các nút trong danh sách. Procedure duyet(First:Tro);
var p:Tro;
Begin
P:=First;
While (p<>nil) do
begin ử end; End; ầ ử ộ ế 3. Tìm ki m m t ph n t trong danh sách. Function TimKiem(X:Element;First:Tro):Tro;
Var P:Tro;Found:Boolean;
Begin P:=First; found:=False;
While (P<>Nil) and (not found) do Begin If X=P^.Info then Begin TimKiem:=P;
found:=True; End Else P:=P^.Right; End; If (not thoat) then TimKiem:=Nil;
End; ạ ỏ ộ ầ ử 4. Lo i b m t ph n t trong danh sách. ạ ỏ ầ ử ầ Lo i b ph n t đ u danh sách: Procedure XoaDau(Var First,Last:Tro); Var P:Tro;
Begin If First<>Nil Then Begin P:=First;
First:=First^.Right;
First^.Left:=Nil;
Dispose(P);
If First=Nil then Last:=Nil
Else First^.Left:=Nil; End; End; ạ ỏ ầ ử ố Lo i b ph n t cu i danh sách: Procedure XoaCuoi(Var First,Last:Tro);
Var P:Tro;
Begin If Last<>Nil then Begin P:=Last;
Last:=Last^.Left;
Last^.Right:=Nil;
Dispose(P);
If First=Nil then Last:=Nil
Else First^.Left:=Nil; End; End; ạ ỏ ầ ử ở ữ Lo i b ph n t gi a danh sách: Procedure XoaGiua(P:Tro;Var First,Last:Tro);
Var
Begin If (P^.Left=Nil) and (P^.Right=Nil) then Begin First:=Nil; Last:=Nil; End Else If P^.left=Nil then Begin First:=First^.Right;
First^.Left:=Nil; End Else If P^.Right=Nil then Begin Last:=Last^.Left;
Last^.Right:=Nil; End Else Begin P^.Left^.Right:=P^.Right;
P^.Right^.Left:=P^.Left; End;
P^.Right:=Nil;
P^.Left:=Nil;
Dispose(P); End; Ư ượ ụ ể 2.3.3.3. u nh ứ
c đi m và ng d ng ế ề ố ế ừ ộ Ư ể Danh sách liên k t kép có m i liên k t hai chi u nên t ầ
m t ph n
b t k khác. Trong khi danh sách liên ấ
ấ ỉ u đi m:
ử ấ ỳ
ộ
ể
b t k có th truy xu t m t ph n t
t
ầ ử ứ
ể
ế ơ
k t đ n ch có th truy xu t ph n t
ế ố ầ ử ấ ỳ
đ ng sau nó.
ấ ượ ớ ệ ậ ế ế ề ậ ố ữ
ộ ố ườ ế
ể Danh sách liên k t t n chi phí g p đôi so v i danh sách liên k t
c đi m:
Nh
ặ
ệ ư
ơ
đ n cho vi c l u tr các m i liên k t. Đi u này khi n vi c c p nh t cũng n ng
ề ơ
n h n trong m t s tr
Ứ ợ
ng h p.
ế ợ ử ụ ệ ả ụ Danh sách liên k t kép thích h p s d ng cho vi c qu n lý danh ng d ng:
ọ
sách h c sinh – sinh viên. ạ ế
2.4. Danh sách h n ch . ế 2.4.1. Ngăn x p (Stack). ị
2.4.1.1. Đ nh nghĩa. ế ả ộ Ngăn x p (Stack) là m t danh sách tuy n tính mà c hai phép thêm vào và ầ ủ đ u ti n hành 1 đ u c a danh sách. ế
ầ ử ề
ầ ử ạ ỏ
ư ậ ượ ạ ỏ ướ ậ c thêm vào sau, thì lo i b tr c, vì v y Stack còn Thêm hay
lo i bạ ỏ Đ nhỉ Đ nhỉ Đáy Cu iố Đ uầ Lo i bạ ỏ Thêm Đáy ụ ả ộ ồ ế
lo i b ph n t
nào đ
Nh v y ph n t
ọ
g i là danh sách LIFO (Last In First Out).
ủ
Vi d : Hình nh c a m t ch ng đĩa. ỉ ộ ủ ầ ử ỏ ạ ỏ ộ ơ ầ ử ủ ứ ẽ ơ
ấ ả ị ạ ỏ ầ ử ộ
ế kh i stack.
Đ nh (top) c a m t stack là n i thêm vào hay lo i b m t ph n t
ấ
ấ
Đáy (Bottom) c a m t stack là n i ch a ph n t
khó truy xu t nh t, và nó s
ị ạ ỏ
khác b lo i b .
không b lo i b cho đ n khi t t c các ph n t ễ ể ế 2.4.1.2. Bi u di n ngăn x p. ễ ể ả a. Bi u di n Stack dùng m ng ể ạ ề ả ằ ộ ộ ớ Ta có th t o m t stack b ng cách khai báo m t m ng 1 chi u v i kích ể ằ ụ th ướ ố
c t i đa là N (ví d , N có th b ng 1000). VD: ỉ ả ạ ỉ ủ ế ế ư ậ ủ
ỗ ổ
ổ ẽ
ộ ơ ả ị ị
ầ ử
ằ
T o stack S và qu n lý đ nh stack b ng bi n T. N u T là đ a ch c a ph n t
ẽ
ạ ộ
ỉ
đ nh c a stack thì T s có giá tr bi n đ i khi stack ho t đ ng. Nh v y khi
ộ
ộ
c b sung vào Stack thì T s tăng lên m t
stack r ng thì T=0. M t ph n t
ỏ
ơ
đ n v . Khi m t ph n t s1 s2 s3 s4 sn T Đáy c a ủ
stack ị ế
ầ ử ượ
đ
ầ ử ị ạ ỏ
ị
b lo i b kh i stack thì T se gi m đi m t đ n v .
ữ ủ
ư ộ
ể ấ ấ ư Có th th y c u trúc l u tr c a stack nh hình sau: ế ơ ể ễ b. Bi u di n Stack dùng danh sách liên k t đ n. ằ ặ ự ớ ổ ố ơ
ộ ố
ể
ổ ộ ỏ ỏ ớ ỉ
ầ ủ ỏ ủ ầ ố ể ả ằ
ộ ng Tràn nh đ i v i stack t
ề
i h n v kích th ả
c, nó ch ph thu c vào gi ệ
nhiên.
Vi c cài đ t stack b ng cách dùng danh sách móc n i là khá t
ư
ỏ ở
ạ
ẳ
Ch ng h n v i danh sách móc n i đ n tr b i First thì có th coi first nh con
i đ nh stack. B sung m t nút vào stack chính là b sung m nút vòa
tr tr t
ạ ỏ
ạ ỏ ộ
thành nút đ u tiên c a danh sách, lo i b m t nút ra kh i stack chính là lo i b
ớ
ổ
ủ ụ
nút đ u tiên c a danh sách. Trong th t c b sung v i stack móc n i ta không
ổ ứ
ư ố ớ
ệ ượ
ch c b ng m ng, vì stack
ph i ki m tra hi n t
ớ ạ ủ
ỉ ụ
ướ
ề ị ớ ạ
ố
i h n c a
móc n i không h b gi
ớ
ộ
b nh . ế ượ ư Stack là m t danh sách liên k t đ c khai báo nh sau: ộ
Type Tro = ^nut;
Nut = record Info : element;
Link : tro; End; Var ế ầ ỏ ế
Sp : Tro;{Sp tr đ n đ u ngăn x p} 2.4.1.3. Các thao tác. ể ể ễ ế ấ ả a. Dùng c u trúc m ng đ bi u di n ngăn x p. Khai báo stack ỉ ị ỉ ầ ử ố ượ ư Type Stack = array[1..n] of element;
Var T:integer; {T là đ nh stack, ch v trí ph n t cu i cùng đ c l u vào stack} ướ ộ ằ ố ượ S:Stack;
X:element; { chú ý n là kích th c là m t h ng s đã đ c khai báo} ở ạ Kh i t o stack Procedure khoitao; Begin T:=0; End; ầ ử ộ
Thêm m t ph n t vào stack Pocedure Push(Var S:Stack;Var T:integer;X:element); Begin If T=n then Write(‘Tran stack’) Else Begin T:=T+1;
S[T]:=X;
End; End; ạ ỏ ộ ầ ử ầ ử ừ ộ ấ Lo i b m t ph n t (hay l y m t ph n t t stack ra) Pocedure Pop(Var S:Stack;Var T:integer;X:element); Begin If T=0 then Write(‘Stack can’) Else Begin X:=S[T];
T:=T1; End; End; ế ơ ể ễ b. Bi u di n Stack dùng danh sách liên k t đ n. ở ạ Kh i t o stack : ở ạ ỗ ị Khi kh i t o, stack là r ng, ta cho sp có giá tr là nil. ậ
Thu t toán : Procedure Initialize;
begin Sp:= nil ; end; ầ ử ộ
Thêm m t ph n t vào stack: ủ ụ ầ ử ẩ ộ ị có giá tr NewInfo vào ngăn Th t c Insert_stack sau cho phép đ y m t ph n t
ỉ
ế
x p có đ nh là Sp. ậ
:
Thu t toán Procedure Insert_stack (NewInfo : Element; Var Sp:Tro);
var p : Tro; begin New(p);
p^.Info := NewInfo;
p^.Link := Sp;
Sp:= p; end; ạ ỏ ộ ầ ử ủ ấ Lo i b m t ph n t c a stack (l y ra) : ế ế ấ ộ ỗ Bi n succ có giá tr true n u stack khác r ng và n i dung l y ra là Infor. ị
ế ị ế ỗ Bi n succ có giá tr false n u stack r ng.
ấ ủ ụ ộ ế ầ ử ở ỉ ứ
đ nh ngăn x p và ch a Th t c DeleteStack cho phép l y m t ph n t
ế
vào bi n Infox. ậ
Thu t toán : Procedure Delete_stack(var Infox:Element; var succ :boolean);
var p: tro; begin succ := false;
if Sp <> nil then
begin succ := true ;
p := Sp;
sp := p^. Link ;
Infox := p^.Info ;
Dispose (p) ; end end; Ứ ụ 4. ng d ng. ể ổ ừ ố ậ ệ ị a. Chuy n đ i t s th n phân sang h nh phân. ọ ố ầ ể ậ ả G i s c n chuy n là n Thu t gi i: kq=0 d ngừ ố ư ủ ế ử ể ỗ đ nh stack: Pop(S,T,V) ế
1. N u N=0
2. While N<>0 do
Tính s d c a N chia cho 2:R
G i R vào ngăn x p: Push(S,T,R)
Thay n:=n div 2
ị
ị ố
3. Hi n th s nh phân
While stack không r ng do
ừ ỉ
ấ
L y R t
ị
ể
Hi n th V: write(V) ệ ể ậ ổ ươ ư ậ {vi c chuy n đ i thu t toán thành ch ng trình xem nh bài t p. ả ị
b. Ký pháp ngh ch đ o balan ầ ể ế ữ ậ ứ ố ọ ượ c vi t d ố ệ ữ ạ ộ ị
ậ ứ ể ể ơ ọ ể ễ ạ ề ố ậ ố ế
ứ ọ ế ướ
Trong h u h t ngôn ng l p trình, các bi u th c s h c đ
i
ủ
ỗ
ạ
(infix notation), nghĩa là m i ký hi u c a phép toán hai
d ng ký pháp trung t
ặ
ầ ạ
ươ
ượ
ng trình c n t o
ngôi đ
c đ t gi a các toán h ng. Tuy nhiên các b d ch ch
ứ ố ọ ầ
ỉ
ể
ị
ra các ch th máy đ đánh giá các bi u th c, do v y các bi u th c s h c c n
ể
ơ
ể ệ
ổ ạ
bi n đ i d ng bi u di n đ vi c đánh giá c h c là d dàng h n. D ng bi u
th c này còn g i là ký pháp h u t ễ
(prefix). (Postfix) hay ti n t Ví d 1:ụ ố ứ
Bi u th c trung t : 7*(95)
ễ ướ ạ ậ ố i d ng h u t (RPNReverse Polish Notationký pháp ư ả ngh ch đ o Balan) nh sau: 7 9 5 * ễ ướ ạ ề ố ể
ể ể
+ Có th bi u di n d
ị
ể ể
+ Có th bi u di n d i d ng ti n t : * 7 – 9 5 Ví d 2:ụ ứ ể ư ử ạ ộ ố
: (1+5)*(8(41))
ng ng: 1 5 + 8 4 1 *
ứ ậ ố
này nh sau:
ế
trái sang ph i cho đ n khi g p m t toán t ế ặ
ở ử ử ố
. Hai toán h ng cu i
ả này, (1+5=6) thay k t qu c toán t ả
ẽ ượ ế ợ
này s đ
ớ
ứ
ể c 1 ta có RPN: 6 8 3 * ể
Xét bi u th c trung t
ứ ậ ố ươ ứ
t
Bi u th c h u t
ể
ứ
Cách th c tính bi u th c h u t
ọ ừ
+ Đ c t
ướ
cùng tr
c k t h p b i toán t
ể
ứ
vào bi u th c ta có bi u th c RPN m i 6 8 4 1 *
ự ư ướ
ươ
ng t
+ T
nh b
ế ụ
+ Ti p t c ta có RPN: 6 5 *
ủ
+ giá tr cu i cùng c a RPN s là 6*5 = 30. Ph ờ ạ ử
ả ế vào sau ra tr
ượ ữ
các toán
ể
i m t th i đi m này 2
ư ậ
này. Nh v y,
ể
ừ ẽ ượ ọ
ử ị ố
ươ
ng pháp đánh giá bi u th c RPN này đòi h i ph i l u tr
ử ượ
ế
ạ
đ
h ng cho đ n khi 1 toán t
ả ượ
ố
toán h ng cu i cùng ph i đ
ả
ạ ộ
ơ
ph i ho t đ ng theo c ch «
ứ ỗ ầ
ữ
ư
l u tr
các toán h ng. C m i l n đ c đ
ở
ộ
ế
ngăn x p, s đ ẽ
ả ư
ứ
ể
ỏ
ộ
ọ ừ
ả ạ
c đ c t
trái sang ph i, t
ế ợ
ớ
c tìm ra và k t h p v i toán t
cướ », nghĩa là ph i dùng stack đ
ị ấ
, hai giá tr l y ra t
c m t toán t
ế
c đ a vào stack. ử
ộ
ả ượ ư
này, xong k t qu đ ạ
c tác đ ng b i toán t ả ậ Các gi i thu t liên quan. ể ừ ể ố ậ ố ậ ứ
bi u th c trung t sang h u t RPN ở ộ i) and (ch a k t thúc bi u th c) do ư ế
ể ứ ố ỗ
ầ ử ủ ọ ể
c a bi u th c trung t ứ
: pt * Thu t toán chuy n t
ỗ
1. Kh i đ ng 1 stack r ng
2. While not(l
ộ
đ c m t ph n t
Case pt of ể ể ị ị
ạ
+ Toán h ng: hi n th
: ử
+ Toán t
(cid:0) N u stack <> r ng ỗ : L y và hi n th ph n t ầ ử ở ơ ớ ế
đ nh stack. ư ẩ ỗ ơ ấ
ế
ầ ử ở ỉ
đ nh stack n u ph n t
ầ ử ở ỉ
ế ụ
ỉ ư
đ nh u tiên h n, ti p t c so sánh pt v i ph n t
(cid:0) N u stack = r ng hay pt u tiên h n ph n t ầ ử ở ỉ đ nh stack thì đ y pt vào ế
stack.
ấ
ấ ặ
ặ ế
ị ầ ử ủ ế ặ
c a stack cho đ n khi g p ể
ế ỗ ả
ế ặ ẩ
+ D u ngo c trái thì đ y vào ngăn x p.
ấ
+ D u ngo c ph i thì l y và hi n th các ph n t
ấ
d u ngo c trái. N u ngăn x p r ng thì l
ứ ố ể ỗ
ị ế ể ầ ử ủ ế i.
hi n th các ph n t c a stack cho đ n khi ỗ 3. Khi k t thúc bi u th c trung t
stack r ng. Ví d 3ụ : ứ ể ể ể ả ọ
ứ
Bi u th c Minh h a chuy n bi u th c 7*8(2+3).
k t quế stack 7*8(2+3) 7 *8(2+3) 7 * 8(2+3) * 7 8 7 8 * (2+3) ( 7 8 * 2 2+3) ( 7 8 * 2 +3) + 7 8 * 2 3 + 3) ( 7 8 * 2 3 * ậ ể ứ ứ ể * Thu t toán đánh giá bi u th c RPN
ở ạ
1 Kh i t o Stack
ế
ặ ạ
ế
2. L p l
i cho đ n khi k t thúc bi u th c RPN
ầ ử ủ
ọ
ứ
ể
c a bi u th c RPN
Đ c ph n t
ạ
ầ ử
ế
N u ph n t
là toán h ng
ẩ
ạ
+ Toán h ng thì đ y nó vào stack
+ Toán tử : (cid:0) ầ ử ế ứ ủ đ nh stack 2 ph n t (n u không ch a đ hai ph n t ầ ử ỗ ấ ừ ỉ
L y t
ừ
i và d ng) thì l (cid:0) ụ ử ị ừ ấ Áp d ng toán t cho hai giá tr v a l y ra (cid:0) ế ẩ ả
Đ y k t qu vào stack. ị ể ứ ở ỉ ế ặ ấ 3. Khi g p d u k t thúc, giá tr bi u th c đ nh stack. ợ 2.4.2. Hàng đ i (Queue) ị
2.4.2.1. Đ nh nghĩa. ượ c ti n hành Hàng đ iợ là m t danh sách tuy n tính mà phép thêm vào đ ế
ạ ỏ ượ ộ ầ ế ở ầ c ti n hành 1 đ u còn l ở
ế
ạ ủ
i c a danh ộ
m t đ u danh sách và phép lo i b đ
sách. ứ ệ ố ượ
ộ ố ượ ộ ố ượ Hàng đ iợ ợ
ệ
ợ ượ ự ệ ng làm vi c theo c ch FIFO (First In First Out)
ỏ
ng vào hàng đ i ho c l y m t đ i t
ng ra kh i
ơ ế ơ ế
ặ ấ
ướ ợ
ướ Hàng đ i ch a các đ i t
nghĩa là vi c thêm m t đ i t
hàng đ i đ c ra tr c". c th c hi n theo c ch "Vào tr ợ ể ễ 2.4.2.2. Bi u di n hàng đ i. ể ễ ả a. Bi u di n dùng m ng: ể ạ ợ ằ ộ ộ ớ ụ Ta có th t o m t hàng đ i b ng cách s d ng m t m ng 1 chi u v i kích
ầ ề
ể ỏ ế ả
ế ể ằ ử ụ
i đa là N (ví d , N có th b ng 1000). Dùng 2 bi n F, R đ tr đ n đ u ướ ố
c t
ạ ỏ ủ ầ th
ổ
lo i b và đ u b sung c a queue. ầ ử ố ế ả ả ợ ợ ợ ầ
Q – bi n hàng đ i, f qu n lý đ u hàng đ i, r qu n lý ph n t cu i hàng đ i. ạ ợ ườ Tr ng thái hàng đ i lúc bình th ng: b. Dùng danh sách liên k tế ế ơ ợ ằ ử ụ ể ạ ộ ộ Ta có th t o m t hàng đ i b ng cách s d ng m t danh sách liên k t đ n. Ta khai báo:
Type Tro = ^ nut;
Nut = record info : Element;
Link : tro; End; Var Front, Rear :ref; 2.4.2.3. Các thao tác. ể ể ợ ễ ả ấ a. Dùng c u trúc m ng đ bi u di n hàng đ i. * Các phép toán. ằ ấ ả Khai báo c u trúc queue b ng m ng. Const N=100;
Type Queue:Array[1..n] of element; Var Q:queue;
F,R:Byte; ở ạ Kh i t o Queue Procedure khoitao; Begin F:=0;
R:=0; End; ầ ử ộ
Thêm m t ph n t vào queue: ỗ ầ ầ ử ộ ị M i l n thêm m t ph n t vào Queue thì R tăng lên m t đ n v . Tuy nhiên, ả ạ ấ ủ ả ị ộ ơ
t o khi F>1, R=N do tính ch t c a queue, queue có kh năng b tràn gi 1 2 3 4 5 n R F ế ụ
ng pháp kh c ph c tình tr ng trên
ể ị
ể ộ ổ ươ
ạ
ắ
ng pháp di chuy n t nh ti n.
ng pháp di chuy n vòng.
ầ ử ố ầ ử ệ ạ ủ
hi n t ầ ử Có hai ph
ươ
Ph
ươ
Ph
ỗ ầ
M i l n b sung m t ph n t
ầ ử , ki m tra s ph n t
ể
ị i c a queue (R
ầ ử
F sao cho các ph n t ể
queue < n, d ch chuy n các ph n t ể ị ế ng pháp di chuy n t nh ti n. ế ố
F+1). N u s ph n t
ỉ ố
có ch s là 1.
ươ
+ Ph
Procedure Insert1(Var Q:Queue;Var F,R:Byte; X:element);
Var i:Byte;
Begin If RF+1 =n then Write(‘TRAN’)
Else If F=0 then F:=1
Else If R=n then
Begin For i:=F to R do q[iF+1]:=q[i];
R:=nF+1;
F:=1; End;
R:=R+1;
Q[R]:=X; R End; ể + Ph 1
2 ầ ử ứ ẽ ể ữ ươ
Sau khi l u tr
ầ ử ng pháp di chuy n vòng.
xong ph n t
ế 1 r ng không, n u có thì s ti n hành b F 3
4 ẽ ế
ư ế ụ ư
ỗ
ầ ử th n s ki m tra
ổ
1 (R=1). Ti p t c nh trên, trong 5 ườ ị ầ ợ ph n t
sung vào ph n t
tr ng h p này queue b đ y khi: 6
7 8 RF+1=0 Ho cặ
RF+1=n Procedure Insert2(Var Q:Queue;Var F,R:Byte; X:element); Begin If (RF+1 =0) or (RF+1 =n) then Write(‘TRAN’)
Else If F=0 then F:=1
Else Begin If R=n then R:=0;
R:=R+1;
Q[R]:=X; End; End; ạ ỏ ộ ầ ử ỏ Lo i b m t ph n t kh i queue: ươ ế ng pháp di chuy n t nh ti n. ể ị
+ Ph
Procedure Del_Queue(Var Q:Queue;Var X:element); Begin If F=0 then Write(‘CAN’)
Else Begin X:=Q[F];
F:=F+1;
If F>R then
Begin F:=0;
R:=0; End; End; ể End;
ươ ng pháp di chuy n vòng. + Ph
Procedure Del_Queue(Var Q:Queue;Var X:element); Begin If F=0 then Write(‘CAN’)
Else Begin X:=Q[F];
If F=R then
Begin F:=0;
R:=0; End Else Begin F:=F+1;
If F>n then F:=1; End; End; End; ế ể ể ợ ễ b. Dùng danh sách liên k t đ bi u di n hàng đ i. ạ ỏ ầ ầ Rear là đ u thêm vào và Front là đ u lo i b * Các phép toán. ở ạ ợ :
Kh i t o hàng đ i ở ạ ợ ỗ ị Khi kh i t o, hàng đ i là r ng, ta cho Front và Rear có giá tr là nil. ậ
Thu t toán : Procedure Initialize;
Begin Front := nil;
Rear := nil; end; ầ ử ộ
Thêm m t ph n t ợ :
vào hàng đ i ợ ế ể ể
ầ ử ự ư ươ ế ộ ố ợ
ễ
Khi dùng danh sách liên k t đ bi u di n hàng đ i thì phép thêm vào hàng đ i
thì t vào cu i danh sách liên k t. nh thêm m t ph n t ng t ả ử ầ ộ ộ Gi s ta c n m t ph n t m i ầ ử ớ p có n i dung là NewInfo vào hàng đ i.ợ ậ
Thu t toán : Procedure Insert_queue ( NewInfo : Element; Var Front, Rear:Tro );
Var q,p :tro; Begin New(p) ;
p^.Info := NewInfo ;
P^. Link := nil;
If Front = nil then Begin Front := p;
Rear:=p; End; Else Begin Rear^.Link := p;
Rear := p; End; End; ạ ỏ ộ ầ ử ủ Lo i b m t ph n t c a hàng . ế ấ ộ ị ợ ỗ ế
ế ế ộ ỗ
ợ
Bi n succ có giá tr là true n u hàng đ i khác r ng và n i dung l y ra là Infox.
Bi n succ có n i dung là false n u hàng đ i r ng. : ậ
Thu t toán
Procedure Delete_queue (Var Infox : Element; Var succ :boolean; Var Front,
Rear:Tro);
Var P:Tro; Begin succ := false ;
If Front <> nil then Begin succ := true; p := Front;
Front := p^.Link ;
Infox := p^.Info ; if Front = nil then Rear := nil ; Dispose(p); End; End; ụ Ứ
2.4.2.4. ng d ng. ề ứ ụ Queue có nhi u ng d ng ự ế
Trong th c t
ộ ệ ộ ệ B đ m bàn phím.
ợ ệ
Hàng đ i l nh trong CPU.
ữ
B đ m gi a máy tính và máy in. ươ ổ ố ể ạ ơ ị ế t ch ng trình chuy n đ i s nguyên (đ n v giây) sang d ng Vi ờ ể ư ạ Bài t p 1:ậ
gi …phút…giây.
ạ
ư ẫ ủ
ố ng trình khi ch y có th nh sau:
ơ ị ờ ươ
D ng m u c a ch
Đ a vào s nguyên (đ n v giây): 3812
3812 giây = 1 gi 3 phút 32 giây. ộ ố ể ồ ọ ế ươ ị
ng trình đ c m t s nguyên r i hi n th Vi ữ ố ủ ổ ớ ố ả ượ Bài t p 2:ậ
t ch
ữ ố ủ ố ấ
a. Các ch s c a s y, và t ng c a các ch s đó.
ố ả
ượ
b. S đ o ng
c.
ệ ủ ố
c. Hi u c a s đó v i s đ o ng c ế ươ ộ ố ể ồ ị ị t ch ng trình đ c m t s nguyên, r i hi n th giá tr sau: ọ
Bài 3: Vi
S = 12+34+56+…+(1)n*n ế ươ ể ị ấ ả ữ ố ố t ch ồ
t c các s nguyên g m có 3 ch s sao cho ấ ả ng trình hi n th t
ủ
ữ ố ằ Bài 4: Vi
ổ
t ng t t c các ch s b ng tích c a chúng. ế ươ ữ ậ ồ ộ ỗ t ch ươ ữ ệ ỗ ể
ứ
ng trình nh p vào m t chu i ch a ho, tên và ch lót r i chuy n
ọ
ng ạ
ẽ ể ệ Bài 5: Vi
ụ ế
sang d ng tên, h và ch lót. Ví d , n u chu i là “Hoàng Nguy t Kim” ch
trình s chuy n thành “Nguy t Hoàng Kim”. ế ị ỗ ừ ươ ể ả ọ ỗ ộ ộ ồ t ch ng trình đ c m t chu i (m t dòng văn b n) r i hi n th m i t
ố ừ ấ ộ Bài 6: Vi
trên m t hàng và s các t trong câu y. ế ươ ố ự ậ ộ ố ự
ng trình nh p vào m t dãy s th c và s th c x. Thông báo t ch
ố ượ ầ ử ủ ằ ị Bài t p 7ậ : Vi
lên màn hình s l ng các ph n t trong dãy b ng x và v trí c a chúng. ậ ả ố ộ
Bài t p 8ậ : Nh p vào m t m ng các s nguyên.
ầ ả ộ ố ứ ự ả
ừ ả ố gi m d n.
bàn phím. Chèn s đó vào m ng sao cho ứ ự ả ầ gi m d n. (không đ ượ ế ạ
c x p l ả
i m ng) ế ạ
a/ X p l
i m ng đó theo th t
ậ
b/ Nh p vào m t s nguyên t
ẫ
ả
m ng v n có th t
G i ýợ : ẩ ớ ị v trí i t ả
i n sang ph i 1 v trí. ầ
ị
Tìm v trí c n chèn: i.
ầ ử ừ ị
Đ y các ph n t
t
Gán: A[i]=x; ầ ử ả ả ố ả : Cho 2 m ng s nguyên: M ng A có m ph n t ầ
, m ng B có n ph n Bài t p 9ậ
.ử
t ứ ự ả i các m ng đó theo th t ầ
ả ả ẫ ứ ự ả
gi m ả
gi m d n.
ạ
i thành m ng C sao cho m ng C v n có th t
ả i m ng C). ế ạ
ắ
a/ S p x p l
ả
ộ
b/ Tr n 2 m ng đó l
ượ ế ạ
ầ
d n (Không đ
c x p l
G i ýợ : ầ ử ủ ỉ ố ệ ả ể
Dùng 2 ch s i,j đ duy t qua các ph n t c a 2 m ng A, B và k là ch ỉ ả ố
s cho m ng C. ệ ế ứ ồ ờ ả ề Trong khi (i<=m) và (j<=n) thì:
{T c là khi đ ng th i c 2 dãy A, B đ u ch a duy t h t} ạ ủ ầ ư
ế
+ N u A[i]>B[j] thì: C[k]:=A[i]; i:=i+1;
ượ ạ
c l
+ Ng
ế ướ
N u dãy nào h t tr i: C[k]:=B[j]; j:=j+1;
c thì đem ph n còn l ố
ổ
i c a dãy kia b sung vào cu i ế
dãy C. ế ươ ệ ậ ả ạ ố
ng trình nh p vào 2 m ng s nguyên A, B đ i di n cho 2 : Vi t ch
ể ộ ậ ợ ế ậ ả ậ ả ầ ử ừ trùng nhau trong m t t p h p). Trong quá trình
ổ
v a nh p vào đã có trong m ng thì không b Bài t p 10ậ
ầ ử
ợ
ậ
t p h p (không th có 2 ph n t
ể
nh p, ph i ki m tra: n u ph n t
sung vào m ng.ả ậ
ậ ợ
ợ ợ ủ
a/ In ra màn hình h p c a 2 t p h p A, B.
ệ ủ
b/ In ra màn hình hi u c a 2 t p h p A, B. G i ýợ : ấ ả a/ In ra màn hình t t c các ph n t c a t p h p A. ấ ả ệ
Duy t qua t t c các ph n t ợ
ầ ử ủ ậ
i(cid:0) A thì in bi ra màn
ầ ử i(cid:0) B. N u bế b hình. ấ ả ệ
b/ Duy t qua t t c các ph n t ầ ử i(cid:0) A. N u aế i(cid:0) B thì in ai ra màn hình. a ứ ủ ế ươ ng trình tính t ng c a 2 đa th c h(x) = f(x) + g(x). Trong t ch ạ ổ
0 + a1x + a2x2 + ... + anxn. ậ
Vi
Bài t p 11:
ứ
ỗ
đó, m i đa th c có d ng: a
G i ýợ : ể ư ữ ủ ứ ả Dùng các m ng A, B, C đ l u tr các h s a ệ ố i c a các đa th c f(x), g(x) và h(x). ự ỏ ầ ồ ầ ử ộ ả
là m t b n ghi t tr bao g m các thành ph n sau : ậ
Bài t p 12 :
Cho DSLK m i ph n t ỗ
Mã sinh viên.
ọ
H sinh viên
L pớ ể Đi m TB (ĐTB)
ế ồ ứ ươ : ng trình bao g m các ch c năng sau t ch ấ ạ ừ ọ ượ bàn phím. c nh p t ớ ọ ậ ừ
vào trong DSLK có mã sinh viên, h sinh viên, l p, ĐTB ự ể ế ầ ắ Yêu c uầ : Vi
ế
1. T o DSLK cho đ n khi nh n phím escape thì d ng.
ừ
ậ
2. In DSLK v a nh p.
ầ ử
trong DSLK có h tên đ
3. Xóa 1 ph n t
ầ ử
ộ
4. Thêm m t ph n t
ừ
ậ
ượ
c nh p vào t
bàn phím.
đ
ầ ử
trong DSLK d a vào mã sinh viên.
5. Tìm 1 ph n t
ầ ử
6. S p x p các ph n t trong DSLK tăng d n theo đi m trung bình. ế ươ ứ ồ t ch ng trình bao g m các ch c năng sau: Bài 13: Vi
ạ ậ ừ ứ a. T o danh sách liên k t, ch a các s nguyên nh p t ộ
bàn phím trên m t ố
ậ ố ế
ậ ừ
hàng, quá trình nh p d ng khi nh p s 0. ầ ử trong danh sách nói trên. ể
ế ị ế
ầ ử ủ trong danh sách. ị ố ướ c. ầ ử ứ ướ ớ ị
b. Hi n th các ph n t
ố
c. Đ m s nút trong danh sách liên k t.
d. Tính giá tr trung bình c a các ph n t
ố
e. Xác đ nh nút cu i cùng trong danh sách.
ộ
f. Thêm m t nút vào cu i danh sách.
ộ
ứ
g. Chèn m t nút vào sau nút th n trong danh sách, v i n cho tr
ộ
h. Xóa m t ph n t ớ
th n trong danh sách v i n cho tr c. ế ươ ộ ế ứ ự t ch ườ ợ ạ
ầ
tăng d n và t o
ầ
ng h p: 2 danh sách ban đ u ả Bài 14: Vi
thành danh sách th 3 cũng tăng d n (trong hai tr
ượ ả
đ ng trình tr n hai danh sách liên k t có th t
ầ
ứ
c b o toàn và không b o toàn). ả ử ế ướ ế s L1 và L2 là hai danh sách liên k t cho tr c. Vi ậ
t thu t toán ể Bài 15: Gi
ị
hi n th : ầ
ầ
ệ ủ ủ
a. Ph n giao c a hai danh sách.
ộ ủ
b. Ph n h i c a hai danh sách.
c. Hi u c a hai danh sách. ế ươ ộ ố ậ ể ể ế t ch ng trình dùng ngăn x p đ chuy n m t s th p phân sang Bài 16: Vi
ị
ạ
d ng nh phân. ơ ả ể ấ ế ộ ầ ử ở đáy ể ạ ư ế ộ Bài 17: Dùng các phép toán c b n trên ngăn x p đ l y ra m t ph n t
ngăn x p nh ng đ l i nguyên n i dung.ƯƠ
Ậ
BÀI T P CH
NG 2
