Bài giảng Cấu trúc dữ liệu và giải thuật - Phân loại cấu trúc dữ liệu

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Phân loại cấu trúc dữ liệu

1. ðHSP Bài ging CTDL> tosonnguyen@gmail.com
2. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 2 Bài gi ng CTDL>
3. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 3 Bài gi ng CTDL>
4. Phân loi cu trúc d liu
   Da vào mi quan h gia các phn t
   Phân loi:  Cu trúc d li u tuy n tính  Cu trúc d li u phân c p  Cu trúc đ th  Cu trúc t p h p Nh ĩm 2 4 Bài gi ng CTDL>
5. Phân loi cu trúc d liu
   Da vào mi quan h gia các phn t
   Phân loi:  Cu trúc d li u tuy n tính  Cu trúc d li u phân c p  Cu trúc đ th  Cu trúc t p h p Nh ĩm 2 5 Bài gi ng CTDL>
6. Cu trúc d liu tuyn tính
   Các phn t cĩ quan h 1:1
   Nghĩa là:  Ph i cĩ ph n t đu tiên  Ph i cĩ ph n t cu i cùng  Mi ph n t (ngồi hai ph n t trên) cĩ đúng m t ti n b i và mt h u b i Nh ĩm 2 6 Bài gi ng CTDL>
7. Cu trúc d liu tuyn tính Ph n t đ u tiên Ph n t đ u tiên Ph n t cu i c ùng Cĩ duy nh t Cĩ duy nh t mt ti n b i mt h u b i Nh ĩm 2 7 Bài gi ng CTDL>
8. Phân loi cu trúc d liu
   Da vào mi quan h gia các phn t
   Phân loi:  Cu trúc d li u tuy n tính  Cu trúc d li u phân c p  Cu trúc đ th  Cu trúc t p h p Nh ĩm 2 8 Bài gi ng CTDL>
9. Cu trúc d liu phân cp
   Các phn t cĩ quan h 1:n
   Nghĩa là:  Mi ph n t cĩ nhi u h u b i nh ưng ch cĩ mt ti n b i  ði t trên xu ng d ưi: m i nút cĩ th dị đn nhi u nút khác  ði t dưi lên trên: m i nút (tr đnh) ch cĩ quan h vi 1 nút Nh ĩm 2 9 Bài gi ng CTDL>
10. Cu trúc d liu phân cp Duy nh t mt Ph n t đ nh ti n b i (Top) Cĩ th nhi u hu b i Nh ĩm 2 10 Bài gi ng CTDL>
11. Phân loi cu trúc d liu
    Da vào mi quan h gia các phn t
    Phân loi:  Cu trúc d li u tuy n tính  Cu trúc d li u phân c p  Cu trúc đ th  Cu trúc t p h p Nh ĩm 2 11 Bài gi ng CTDL>
12. Cu trúc đ th
    Các phn t cĩ quan h n:n
    Nghĩa là:  Mi ph n t cĩ quan h vi m t ho c nhi u ph n t khác  Là cu trúc phong phú và ph c t p nh t Nh ĩm 2 12 Bài gi ng CTDL>
13. Cu trúc đ th Nhi u ti n b i E B E Nhi u h u b i A D C D Nh ĩm 2 13 Bài gi ng CTDL>
14. Phân loi cu trúc d liu
    Da vào mi quan h gia các phn t
    Phân loi:  Cu trúc d li u tuy n tính  Cu trúc d li u phân c p  Cu trúc đ th  Cu trúc t p h p Nh ĩm 2 14 Bài gi ng CTDL>
15. Cu trúc tp hp
    Trong tp hp thì các phn t:  Khơng cĩ mi quan h tr c ti p v i nhau  Ch cĩ mi quan h thành viên c a t p h p  Khơng c n quan tâm đn v trí chính xác ca ph n t nào trong t p h p Nh ĩm 2 15 Bài gi ng CTDL>
16. Cu trúc đ th Khơng c ĩ ti n b i Khơng c ĩ hu b i Nh ĩm 2 16 Bài gi ng CTDL>
17. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 17 Bài gi ng CTDL>
18. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 18 Bài gi ng CTDL>
19. Khái nim mng
    Mng là mt tp hp trong đĩ:  Các ph n t cĩ cùng m t ki u  S ph n t là c đnh
    Các phép tính trên mng:  To l p m ng  Ly n i dung c a m t ph n t  Ghi vào m t ph n t ni dung nào đĩ
    Chú ý:  Khơng cĩ phép thêm vào m t ph n t  Khơng cĩ phép b t m t ph n t Nh ĩm 2 19 Bài gi ng CTDL>
20. Lưu tr mng
    Lưu tr trong máy bi mt vùng nh liên tc  Mng m t chi u  Mng hai chi u Nh ĩm 2 20 Bài gi ng CTDL>
21. Lưu tr mng
    Lưu tr trong máy bi mt vùng nh liên tc  Mng m t chi u  Mng hai chi u Nh ĩm 2 21 Bài gi ng CTDL>
22. Mng mt chiu
    Dùng mt ch s đ xác đnh phn t ca mng
    Khai báo: A: array [MinIndex MaxIndex] of ElementType
    Nu mi phn t kiu ElementType chim s t máy thì phi dành ra (MaxIndex – MinIndex + 1)*s t máy đ lưu tr Nh ĩm 2 22 Bài gi ng CTDL>
23. Mng mt chiu A1 A2 Ai An s t máy ða ch ca A[i] là: Loc(A[i]) = Loc(A[MaxIndex]) + (i – MinIndex)*s Nh ĩm 2 23 Bài gi ng CTDL>
24. Lưu tr mng
    Lưu tr trong máy bi mt vùng nh liên tc  Mng m t chi u  Mng hai chi u Nh ĩm 2 24 Bài gi ng CTDL>
25. Mng hai chiu
    Dùng hai ch s đ xác đnh phn t ca mng
    Khai báo: B: array[1 M, 1 N] of ElementType; { M hàng, N ct }
    C th: M = 3, N = 2, ElementType = integer thì: B: array[1 3, 1 2] of integer; { 6 x 2 = 12 byte }
    Lưu tr:  Lưu tr theo hàng  Lưu tr theo c t Nh ĩm 2 25 Bài gi ng CTDL>
26. Mng hai chiu
    Dùng hai ch s đ xác đnh phn t ca mng
    Khai báo: B: array[1 M, 1 N] of ElementType; { M hàng, N ct }
    C th: M = 3, N = 2, ElementType = integer thì: B: array[1 3, 1 2] of integer; { 6 x 2 = 12 byte }
    Lưu tr:  Lưu tr theo hàng  Lưu tr theo c t Nh ĩm 2 26 Bài gi ng CTDL>
27. Mng hai chiu Lưu tr theo hàng
    Lưu tr ht hàng này đn hàng khác B11 B12 B21 B22 B31 B32 ` ` ` Hàng 1 Hàng 2 Hàng 3 ða ch phn t B[i, j] là: Loc(B[i, j]) = Loc(B[1, 1]) + ((i – 1)*N + (j – 1))*s Nh ĩm 2 27 Bài gi ng CTDL>
28. Mng hai chiu
    Dùng hai ch s đ xác đnh phn t ca mng
    Khai báo: B: array[1 M, 1 N] of ElementType; { M hàng, N ct }
    C th: M = 3, N = 2, ElementType = integer thì: B: array[1 3, 1 2] of integer; { 6 x 2 = 12 byte }
    Lưu tr:  Lưu tr theo hàng  Lưu tr theo c t Nh ĩm 2 28 Bài gi ng CTDL>
29. Mng hai chiu Lưu tr theo ct
    Lưu tr ht ct này đn ct khác B11 B21 B31 B12 B22 B32 ` ` Ct 1 Ct 2 ða ch phn t B[i, j] là: Loc(B[i, j]) = Loc(B[1, 1]) + ((j – 1)*M + (i – 1))*s Nh ĩm 2 29 Bài gi ng CTDL>
30. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 30 Bài gi ng CTDL>
31. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 31 Bài gi ng CTDL>
32. ðnh nghĩa hình thc Stack
    Là cu trúc d liu tuyn tính vào sau ra trưc LIFO (Last In – First Out)
    Phép thêm và bt đưc thc hin mt đu gi là đnh (Top) Top Bottom Nh ĩm 2 32 Bài gi ng CTDL>
33. ðnh nghĩa hình thc Stack Z Top Y LyThêm ra m mtt W X phnphn tt vào Stack Nh ĩm 2 33 Bài gi ng CTDL>
34. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 34 Bài gi ng CTDL>
35. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 35 Bài gi ng CTDL>
36. Cài đt Stack bng mng
    Khai báo const MaxStack = 100; type ElementType = KiuPhnTCaStack; Stack = record Element: array [1 MaxStack] of ElementType; Top: integer; end; Nh ĩm 2 36 Bài gi ng CTDL>
37. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 37 Bài gi ng CTDL>
38. Cài đt Stack bng mng
    StackInit(S): Khi to Stack S mi, rng bng cách gán đnh ca Stack (Top) giá tr 0 (khơng cĩ phn t nào)
    procedure StackInit(var S: Stack); begin S.Top:= 0; end; Nh ĩm 2 38 Bài gi ng CTDL>
39. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 39 Bài gi ng CTDL>
40. Cài đt Stack bng mng
    Empty(S): Kim tra S cĩ rng khơng bng cách kim tra xem đnh ca S (Top) cĩ bng 0 hay khơng
    function Empty(S: Stack): boolean; begin Empty:= (S.Top = 0); end; Nh ĩm 2 40 Bài gi ng CTDL>
41. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 41 Bài gi ng CTDL>
42. Cài đt Stack bng mng
    Full(S): Kim tra S đã đy chưa bng cách kim tra xem đnh ca S (Top) đã bng s phn t ti đa ca S (Max Stack) chưa
    function Full(S: Stack): boolean; begin Full:= (S.Top = MaxStack); end; Nh ĩm 2 42 Bài gi ng CTDL>
43. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 43 Bài gi ng CTDL>
44. Cài đt Stack bng mng
    Push(x, S): ðưa phn t x vào S bng cách tăng đnh ca S (Top) lên 1 đơn v và gán giá tr phn t đnh mi ca S này là x
    procedure Push(x: ElementType; var S: Stack); begin if Full(S) then writeln('Stack tran') else begin inc(S.Top); S.Element[S.Top]:= x; end; end; Nh ĩm 2 44 Bài gi ng CTDL>
45. Cài đt Stack bng mng
    Các thao tác trên Stack  Khai báo  Kh i t o: • StackInit(S)  Ki m tra: • Empty(S) • Full(S)  Bi n đi: • Push(S) • Pop(S) Nh ĩm 2 45 Bài gi ng CTDL>
46. Cài đt Stack bng mng
    Pop(S, x): Ly mt phn t ra khi S bng cách gán phn t đnh ca S cho x đng thi giám đnh ca S (Top) đi 1 đơn v
    procedure Pop(var S: Stack;var x: ElementType); begin if Empty(S) then writeln('Stack rong') else begin x:= S.Element[S.Top]; dec(S.Top); end; end; Nh ĩm 2 46 Bài gi ng CTDL>
47. ng dng trên Stack
    Bài tốn: Bin mt s nguyên khơng âm t h thp phân sang h nh phân.
    Ví d: chuyn 9 sang h nh phân 9 2 1 4 2 9 = (1001) 0 2 2 2 0 1 2 1 0 Nh ĩm 2 47 Bài gi ng CTDL>
48. ng dng trên Stack write('Nhap so can chuyen doi: '); readln(Number); if Number = 0 then write('Bien dien co so 2: 0') else begin StackInit(S); while Number > 0 do begin x:= Number mod 2; Number:= Number div 2; Push(x, S); end; write('Bieu dien co so 2: '); while not Empty(S) do begin Pop(S, x); write(x); end; end; Nh ĩm 2 48 Bài gi ng CTDL>
49. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 49 Bài gi ng CTDL>
50. Ni dung chính 1 Phân lo i c u trúc d li u 2 Mng 3 Stack 4 Queue Nh ĩm 2 50 Bài gi ng CTDL>
51. ðnh nghĩa hình thc Queue
    Là cu trúc d liu tuyn tính vào trưc ra trưc FIFO (First In – First Out)
    Thao tác xĩa đưc thc hin mt đu, gi là li trưc (Front)
    Thao tác b sung đưc thc hin mt đu khác, gi là li sau (Rear) Nh ĩm 2 51 Bài gi ng CTDL>
52. ðnh nghĩa hình thc Queue Xĩa mt D Thêm vào mt phnphn tt A B C Front Rear Nh ĩm 2 52 Bài gi ng CTDL>
53. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 53 Bài gi ng CTDL>
54. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 54 Bài gi ng CTDL>
55. Cài đt Queue bng mng
    Khai báo const MaxQueue = 100; type ElementType = KiuPhnTCaQueue; Queue = record Element: array [1 MaxQueue] of ElementType; Front, Rear: integer; end; Nh ĩm 2 55 Bài gi ng CTDL>
56. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 56 Bài gi ng CTDL>
57. Cài đt Queue bng mng
    QueueInit(Q): Khi to Queue Q mi, rng bng cách cho li trưc (Front) giá tr 1 và li sau (Rear) giá tr 0 (khơng cĩ phn t nào – li trưc (Front) li ch đn phn t đng sau li sau (Rear))
    procedure QueueInit(var Q: Queue); begin Q.Front:= 1; Q.Rear:= 0; end; Nh ĩm 2 57 Bài gi ng CTDL>
58. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 58 Bài gi ng CTDL>
59. Cài đt Queue bng mng
    Empty(Q): Kim tra Q cĩ rng khơng bng cách kim tra xem li trưc ca Queue (Front) cĩ ln hơn li sau (Rear) khơng (li trưc (Front) li ch đn phn t đng sau li sau (Rear))
    function Empty(Q: Queue): boolean; begin Empty:= (Q.Front > Q.Rear); end; Nh ĩm 2 59 Bài gi ng CTDL>
60. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 60 Bài gi ng CTDL>
61. Cài đt Queue bng mng
    Full(Q): Kim tra hàng đi cĩ đy khơng bng cách kim tra li sau (Rear) đã bng s phn t ti đa ca Queue (MaxQueue) chưa
    function Full(Q: Queue): boolean; begin Full:= (Q.Rear = MaxQueue); end; Nh ĩm 2 61 Bài gi ng CTDL>
62. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 62 Bài gi ng CTDL>
63. Cài đt Queue bng mng
    Push(x, Q): ðưa phn t x vào Queue bng cách tăng li sau ca Queue (Rear) lên mt đơn v và gán giá tr phn t li sau mi ca Queue này là x
    procedure Push(x: ElementType; var Q: Queue); begin if Full(Q) then writeln('Queue tran') else begin inc(Q.Rear); Q.Element[Q.Rear]:= x; end; end; Nh ĩm 2 63 Bài gi ng CTDL>
64. Cài đt Queue bng mng
    Các thao tác trên Queue  Khai báo  Kh i t o • QueueInit(Q)  Ki m tra: • Empty(Q) • Full(Q)  Bi n đi • Push(x, Q) • Pop(Q, x) Nh ĩm 2 64 Bài gi ng CTDL>
65. Cài đt Queue bng mng
    Pop(Q, x): Ly mt phn t ra khi Queue. Cơng vic này đưc thc hin bng cách gán giá tr ca phn t li trưc ca Queue cho x đng thi tăng li trưc (Front) lên mt đơn v
    procedure Pop(var Q: Queue; var x: ElementType); begin if Empty(Q) then writeln('Queue rong') else begin x:= Q.Element[Q.Front]; inc(Q.Front); end; end; Nh ĩm 2 65 Bài gi ng CTDL>
66. Queue vịng
    Nhn xét: Sau khi hot đng mt thi gian thì khơng gian b nh ht, trong khi các v trí t 1 đn Front – 1 cịn trng
    ð khc phc nhưc đim này ta dùng Queue vịng  Các ph n t ca m ng đưc s p x p theo chi u kim đng h  Các ph n t t Front đn Rear là ca Queue  Cĩ thêm bi n n l ưu s ph n t ca Queue  Vi c lo i b th c hi n b ng cách d ch Front theo chi u kim đng h Nh ĩm 2 66 Bài gi ng CTDL>
67. Queue vịng Rear Front Nh ĩm 2 67 Bài gi ng CTDL>
68. Cài đt Queue vịng bng mng const MaxQueue = 100; type ElementType = KiuPhnTCaQueue; Queue = record Element: array [1 MaxQueue] of ElementType; Front, Rear: integer; n: integer; end; procedure QueueInit(var Q: Queue); begin Q.Front:= 1; Q.Rear:= 0; Q.n:= 0; end; Nh ĩm 2 68 Bài gi ng CTDL>
69. Cài đt Queue vịng bng mng function Empty(Q: Queue): boolean; begin Empty:= (Q.n = 0); end; function Full(Q: Queue): boolean; begin Full:= (Q.n = MaxQueue); end; Nh ĩm 2 69 Bài gi ng CTDL>
70. Cài đt Queue vịng bng mng procedure Push(x: ElementType; var Q: Queue); begin if Full(Q) then writeln('Queue tran') else begin inc(Q.n); if Q.Rear = MaxQueue then Q.Rear:= 1 else inc(Q.Rear); Q.Element[Q.Rear]:= x; end; end; Nh ĩm 2 70 Bài gi ng CTDL>
71. Cài đt Queue vịng bng mng procedure Pop(var Q: Queue; var x: ElementType); begin if Empty(Q) then writeln('Queue rong') else begin dec(Q.n); x:= Q.Element[Q.Front]; if Q.Front = MaxQueue then Q.Front:= 1 else inc(Q.Front); end; end; Nh ĩm 2 71 Bài gi ng CTDL>
72. ng dng trên Queue
    Bài tốn: Bin đi phn thp phân ca mt s thc khơng âm t h thp phân sang h nh phân
    Ví d: Chuyn 0.875 sang h nh phân Phn l Nhân đơi Phn nguyên 0.875 1.75 1 0.75 1.5 1 0.875 = (0.111) 2 0.5 1 1 Nh ĩm 2 72 Bài gi ng CTDL>
73. ng dng trên Queue write('Nhap so thap phan: '); readln(Number); PhanLe:= Frac(Number); if PhanLe = 0 then write('Bieu dien co so 2: 0') else begin QueueInit(Q); dem:= 0; while (PhanLe <> 0) and (dem < 10) do begin Push(trunc(PhanLe*2), Q); PhanLe:= frac(PhanLe*2); inc(dem); end; Nh ĩm 2 73 Bài gi ng CTDL>
74. ng dng trên Queue write('Bieu dien co so 2: 0.'); while not Empty(Q) do begin Pop(Q, x); write(x); end; end; Nh ĩm 2 74 Bài gi ng CTDL>
75. Bài tp
    Bài tp 1 : Chuyn ma trn tam giác dưi M thành mng mt chiu. Tính đa ch phn t M[i, j] vi đa ch cơ s ca M là b
    Gii:  V trí ph n t M[i, j] trong m ng m t chi u là: [1 + 2 + + (i – 1)] + j = (i – 1)*i/2 + j  Tính đa ch ph n t này theo cơng th c c a mng m t chi u b + ((i – 1)*i/2 + j – 1) = b + (i – 1)*i/2 + j - 1 Nh ĩm 2 75 Bài gi ng CTDL>
76. Bài tp
    Bài tp 2 : Kim tra mt xâu kí t cĩ cha các du ngoc tương xng khơng?
    Thut tốn:  S dng Stack l ưu tr các d u ngo c  Duy t xâu l n l ưt qua các d u ngo c nh ư sau: •Nu g p ‘(‘ thì np ‘(‘ vào Stack •Nu g p ‘)’ thì xĩa m t ph n t ra kh i Stack  Nu Stack r ng tr ưc khi duy t xong xâu ho c duy t xong mà Stack v n cịn ph n t thì xâu đã cho khơng tha mãn, ngưc l i th a mãn Nh ĩm 2 76 Bài gi ng CTDL>
77. Bài tp write('Nhap xau: '); readln(str); n:= length(str); d:= 1; KiemTra:= true; while (d <= n) and KiemTra do begin if str[d] = '(' then Push(str[d], S) else if not Empty(S) then Pop(S, x) else KiemTra:= false; inc(d); end; if Empty(S) and KiemTra then writeln(‘Thoa man') else writeln(‘Khong thoa man'); Nh ĩm 2 77 Bài gi ng CTDL>
78. Bài tp
    Bài tp 3 : Dùng các phép tốn ca hàng đi và ngăn xp, vit thut tốn đo ngưc các phn t ca hàng đi
    Thut tốn:  Ly t ng ph n t ca Queue n p vào Stack  Hi n th các ph n t trong Stack Nh ĩm 2 78 Bài gi ng CTDL>
79. Bài tp Sau đây là chương trình trên ngơn ng ta Pascal Procedure DoiNguoc(Q: Queue); var S: Stack; x: ElementType; begin StackInit(S); while not Empty(Q) do begin Pop(Q, x); Push(S, x); end; Nh ĩm 2 79 Bài gi ng CTDL>
80. Bài tp writeln('Hien thi Q theo thu tu dao nguoc: '); while not Empty(S) do begin Pop(S, x); writeln(x); end; end; Nh ĩm 2 80 Bài gi ng CTDL>
81. Bài tp
    Bài tp 4 : ðc các kí t ca xâu kí t vào Stack và Queue. Dùng các phép tốn ca Stack và Queue kim tra xem xâu đĩ cĩ đi xng khơng?
    Thut tốn:  ðc các kí t vào Stack và Queue  Duy t Stack •Ly ph n t ra kh i Stack và Queue •Nu hai ph n t va l y ra khơng b ng nhau thì xâu khơng đi x ng, thốt  Khi duy t xong n u khơng cĩ vn đ gì thì xâu đã cho đi x ng Nh ĩm 2 81 Bài gi ng CTDL>
82. Bài tp Function DoiXung(xau: string): boolean; var S: Stack; Q: Queue; ch1, ch2: char; begin StackInit(S); QueueInit(Q); while xau <> '' do begin Push(xau[1], S); Push(xau[1], Q); delete(xau, 1, 1); end; Nh ĩm 2 82 Bài gi ng CTDL>
83. Bài tp while not Empty(S) do begin Pop(S, ch1); Pop(Q, ch2); if ch1 <> ch2 then begin DoiXung:= false; exit; end; end; DoiXung:= true; end; Nh ĩm 2 83 Bài gi ng CTDL>
84. Tài liu tham kho [1] ð Xuân Lơi, Cu trúc d liu và gii thut. NXB ði hc quc gia Hà Ni, 2004 [2] Nguyn Th Tĩnh, Nguyn Xuân My, Hà ðng Cao Tùng, H Cm Hà, Cu trúc d liu và gii thut. NXB ði hc sư phm, 2007 [3] ð Trung Kiên: Giáo án: Cu trúc d liu và gii thut. Ebook [4] Lê Minh Hồng, Bài ging chuyên đ. Ebook [5] Vũ ðình Hịa, ð Trung Kiên: Cu trúc d liu và gii thut. SCROM Nh ĩm 2 84 Bài gi ng CTDL>
85. ðHSP tosonnguyen@gmail.com
86. Hiu ng hot hình ThêmXĩa vàophn Stack t A B C Nh ĩm 2 86 Bài gi ng CTDL>
87. Hiu ng hot hình Nh ĩm 2 87 Bài gi ng CTDL>
88. Hiu ng hot hình 1 2 Nh ĩm 2 88 Bài gi ng CTDL>
89. B mơn nào hay nht A. Tốn B. Lí C. Hĩa D. Tin Nh ĩm 2 89 Bài gi ng CTDL>
90. Nưc anh qua nhng lá c Nh ĩm 2 90 Bài gi ng CTDL>