›
›

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

pdf 90 trang hapham 1210
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_co_so_du_lieu_va_giai_thuat.pdf

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>