Tài liệu Cấu trúc dữ liệu động

CẤU TRÚC DỮ LIỆU ĐỘNG MỞ ĐẦU Cấu trúc dữ liệu là một lĩnh vực nghiên cứu lâu đời của khoa học máy tính. Hầu hết các chương trình được viết ra, chạy trên máy tính, dù lớn hay nhỏ, dù đơn giản hay phức tạp, đều phải sử dụng cấu trúc dữ liệu. Việc hiểu biết về các cấu trúc dữ liệu giúp các lập trình viên có nhiều lựa chọn hơn trong việc đưa ra các giải pháp hiệu quả giải quyết các bài toán tin. Với các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu ký tự... hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng... lập trình viên có thể giải quyết hầu hết các bài toán đặt ra. Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này có đặc điểm chung là không thay đổi được kích thước, cấu trúc trong quá trình sống, do vậy thường cứng nhắc, gò bó khiến đôi khi khó diễn tả được thực tế vốn sinh động, phong phú. Các kiểu dữ liệu kể trên được gọi là các kiểu dữ liệu tĩnh. Một số đối tượng dữ liệu trong chu kỳ sống của nó có thể thay đổi về cấu trúc, độ lớn, như danh sách các học viên trong một lớp học có thể tăng thêm, giảm đi... Khi đó nếu cố tình dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn những đối tượng đó lập trình viên phải sử dụng những thao tác phức tạp, kém tự nhiên khiến chương trình trở nên khó đọc, do đó khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả. Do bản chất của các dữ liệu tĩnh, chúng sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình. Tuy nhiên, trong thực tế, có thể xảy ra trường hợp một dữ liệu nào đó chỉ tồn tại nhất thời hay không thường xuyên trong quá trình hoạt động của chương trình. Vì vậy việc dùng các CTDL tĩnh sẽ không cho phép sử dụng hiệu quả bộ nhớ. Do vậy, nhằm đáp ứng nhu cầu thể hiện sát thực bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, cần phải tìm cách tổ chức kết hợp dữ liệu với những hình thức mới linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu trúc dữ liệu động. Trong khuôn khổ tài liệu này, tác giả sẽ giới thiệu về một số cấu trúc dữ liệu động đặc biệt như danh sách liên kết, ngăn xếp và hàng đợi và một số ứng dụng của chúng đặc biệt trong việc khử đệ qui. Tác giả rất mong nhận được những đóng góp của các thầy, cô giáo và học sinh để chuyên đề này được hoàn thiện hơn. Xin trân trọng cảm ơn.! MỤC LỤC 1. DANH SÁCH LIÊN KẾT.......................................................................................................4 1.1 Khái niệm..........................................................................................................................4 1. 2 Cấu tạo của danh sách liên kết.........................................................................................5 1.3 Các thao tác cơ bản với danh sách liên kết........................................................................5 1.3.1 Khai báo.....................................................................................................................5 1.3.2 Khởi tạo danh sách.....................................................................................................5 1.3.3 Bổ sung một nút vào đầu danh sách..........................................................................5 1.3.4. Bổ sung một nút vào cuối danh sách.........................................................................6 1.3.5 Duyệt danh sách.........................................................................................................6 1.3.6 Bổ sung một nút vào sau nút được trỏ bởi p..............................................................6 1.3.7. Xoá một nút khỏi danh sách......................................................................................7 1.4. Mảng hay danh sách liên kết?..........................................................................................7 1.5. Ví dụ làm việc với danh sách liên kết..............................................................................8 2. NGĂN XẾP – STACK..........................................................................................................15 2.1. Khái niệm.......................................................................................................................15 2.2 Các thao tác cơ bản của ngăn xếp...................................................................................15 2.4. Ứng dụng Stack..............................................................................................................16 2.4.1 Ứng dụng Stack khử đệ quy.....................................................................................16 2.4.2 Tính giá trị một biểu thức dạng hậu tố.....................................................................23 2.4.3 Chuyển biểu thức từ trung tố sang hậu tố.................................................................26 3. HÀNG ĐỢI – QUEUE..........................................................................................................28 3.1. Khái niệm.......................................................................................................................28 3.2 Các thao tác cơ bản của hàng đợi....................................................................................29 3.3. So sánh việc cài đặt Queue bằng mảng và danh sách liên kết........................................32 3.4 Ứng dụng.........................................................................................................................32 2 1. DANH SÁCH LIÊN KẾT Danh sách là một dãy hữu hạn các phần tử thuộc cùng một lớp đối tượng nào đó. Ví dụ : danh sách sinh viên, danh sách vật tư, danh sách các hoá đơn, danh sách các số thực. Chúng ta đã dùng mảng để biểu thị một danh sách, cách này có các nhược điểm: kích thước của mảng phải định trước nên tốn bộ nhớ (số phần tử thực tế dùng nhiều khi rất ít so với khai báo), khi thêm một phần tử vào mảng hoặc xoá một phần tử ra khỏi mảng ta phải mất nhiều thời gian để dồn mảng. Danh sách liên kết dùng để cài đặt một danh sách sẽ khắc phục được các nhược điểm trên của mảng. 1.1 Khái niệm R. Sedgewick (Alogrithms in Java – 2002) định nghĩa danh sách liên kết như sau: Danh sách liên kết là một cấu trúc dữ liệu bao gồm một tập các phần tử, trong đó mỗi phần tử là một phần của một nút có chứa liên kết đến phần tử kế tiếp. “Mối phần tử là một phần của một nút” vì mỗi nút có ít nhất hai trường, một trường gọi là dữ liệu (data), trường còn lại là trường liên kết trỏ đến nút tiếp theo trong danh sách. Trường liên kết của phần tử thứ i của danh sách sẽ trỏ tới phần tử thứ (i+1) của danh sách. Tuy nhiên nó cũng có thể trỏ đến chính nó. Có thể nói danh sách liên kết là một cấu trúc dữ liệu được định nghĩa kiểu đệ quy, vì trong định nghĩa một nút của danh sách có tham chiếu tới khái niệm nút. Có nhiều loại danh sách liên kết khác nhau tùy thuộc vào cấu trúc của mỗi phần tử trong danh sách (số trường liên kết với các phần tử khác trong danh sách) nhưng cơ bản nhất là danh sách liên kết đơn (single linked list), mỗi phần tử có một trường liên kết như trên hình vẽ minh họa, và khi chúng ta nói đến danh sách liên kết, nếu không có các chú giải đi kèm thì ngầm hiểu đó là danh sách liên kết đơn. Danh sách liên kết kép: mỗi phần tử liên kết với các phần tử đứng trước và sau nó trong danh sách: Danh sách liên kết vòng : phần tử cuối danh sách liên kết với phần tử đầu danh sách: 3 1. 2 Cấu tạo của danh sách liên kết Cấu tạo của danh sách liên kết: có một con trỏ First chứa địa chỉ của phần tử đầu tiên của danh sách, phần tử đầu có phần dữ liệu và một con trỏ Next để chứa địa chỉ của phần tử thứ hai, tổng quát phần tử thứ i có phần dữ liệu và một con trỏ next để chứa địa chỉ của phần tử thứ i+1, đối với phần tử cuối cùng giá trị của con trỏ next bằng NIL. Để thuận tiện khi thêm phần tử mới vào cuối danh sách liên kết ta dùng một con trỏ Last chứa địa chỉ của phần tử cuối cùng. Khởi tạo một danh sách rỗng first = NIL. Nhắc lại 2 thủ tục cơ bản với biển trỏ: + Cấp phát vùng nhớ cho biến trỏ p: New(p) + Giải phóng vùng nhớ cho biến trỏ p: Dispose(p) 1.3 Các thao tác cơ bản với danh sách liên kết 1. 3. 1 Khai báo Để khai báo một danh sách động trước hết ta khai báo kiểu của mỗi nút trong danh sách. Type = ^ ; = Record Data: DataType; Next: ; End; Var First: ; First là địa chỉ của nút đầu tiên trong danh sách, dựa vào trường next của nút này ta bết được địa chỉ của nút thứ hai, cứ như vậy ta biết được địa chỉ của tất cả các nút trong danh sách. 1.3.2 Khởi tạo danh sách First : =Nil; 1.3.3 Bổ sung một nút vào đầu danh sách +Tạo ra nút mới New(p); p^.Data :=X; + Bổ sung vào đầu danh sách p^.Next :=First; 4 First :=p; 1.3.4. Bổ sung một nút vào cuối danh sách Xuất phát danh sách không có nút nào cả. Nút mới thêm vào sẽ nằm cuối danh sách. Khi đó ta cần hai biến con trỏ First và Last lần lượt trỏ đến các nút đầu và cuối danh sách. Procedure Khoitao; var p: TroNut; Begin First := nil; Last:= nil; While do Begin New(p); Readln(p^.data); p^.Next := Nil; If First = Nil then First := p Else Last^.next := p; Last := p; End; End; 1.3.5 Duyệt danh sách Duyệt danh sách là thăm và xử lý từng nút trong danh sách. Procedure Duyet; Var p: TroNut; Begin P := First; While p <> nil do Begin ; P := p^.Next; {duyệt qua nút tiếp theo} End; End; 1.3.6 Bổ sung một nút vào sau nút được trỏ bởi p Thủ tục sau thực hiện việc bổ sung một nút có nội dung x vào sau nút được trỏ bởi p. Procedure Bosung(p,x); Var q: TroNut; Begin New(q); q^.data:=x; if first = nil then begin q^.next := nil; 5 end else begin first := q; q^.next:= p^.next; p^.next:= q; End; end; 1.3.7. Xoá một nút khỏi danh sách Thủ tục sau thực hiện việc xóa một nút trỏ bởi p ra khỏi danh sách. Procedure Xoa(p); Var q: TroNut; Begin if First = nil then exit; if p = First then First := First^.next else begin q:= First; While q^.next <> p do q:= q^.next; q^.next:= p^.next; end; Dispose(p); End; 1.4. Mảng hay danh sách liên kết? Chúng ta đã từng làm quen với kiểu mảng, lưu danh sách gồm nhiều thành phần có cùng kiểu. Mỗi thành phần là một biến tĩnh và số lượng thành phần của danh sách là cố định. Tuy nhiên việc sử dụng mảng có các nhược điểm: kích thước của mảng phải định trước nên tốn bộ nhớ (số phần tử thực tế dùng nhiều khi rất ít so với khai báo), khi thêm một phần tử vào mảng hoặc xoá một phần tử ra khỏi mảng ta phải mất nhiều thời gian để dồn mảng. Danh sách liên kết dùng để cài đặt một danh sách sẽ khắc phục được các nhược điểm trên của mảng. Tuy nhiên không thể kết luận phương pháp cài đặt nào hiệu quả hơn, mà nó hoàn toàn tuỳ thuộc vào từng ứng dụng hay tuỳ thuộc vào các phép toán trên danh sách. Tuy nhiên ta có thể tổng kết một số ưu nhược điểm của từng phương pháp làm cơ sở để lựa chọn phương pháp cài đặt thích hợp cho từng ứng dụng: Cài đặt bằng mảng đòi hỏi phải xác định số phần tử của mảng, do đó nếu không thể ước lượng được số phần tử trong danh sách thì khó áp dụng cách cài đặt này một cách hiệu quả vì nếu khai báo thiếu chỗ thì mảng thường xuyên bị đầy, không thể làm việc được còn nếu khai báo quá thừa thì lãng phí bộ nhớ. 6 Cài đặt bằng con trỏ thích hợp cho sự biến động của danh sách, danh sách có thể rỗng hoặc lớn tuỳ ý chỉ phụ thuộc vào bộ nhớ tối đa của máy. Tuy nhiên ta phải tốn thêm vùng nhớ cho các con trỏ (trường next). Cài đặt bằng mảng thì thời gian xen hoặc xoá một phần tử tỉ lệ với số phần tử đi sau vị trí xen/ xóa. Trong khi cài đặt bằng con trỏ các phép toán này mất chỉ một hằng thời gian. Phép truy nhập vào một phần tử trong danh sách chỉ tốn một hằng thời gian đối với cài đặt bằng mảng, trong khi đối với danh sách cài đặt bằng con trỏ ta phải tìm từ đầu danh sách cho đến vị trí trước vị trí của phần tử hiện hành. Nói chung danh sách liên kết thích hợp với danh sách có nhiều biến động, tức là ta thường xuyên thêm, xoá các phần tử. 1.5. Ví dụ làm việc với danh sách liên kết Xét danh sách liên kết đơn biểu diễn một dãy số nguyên. Nút đầu tiên trong danh sách được trỏ bởi First. Cho khai báo mỗi nút trong danh sách như sau: Type TroNut = ^ Nut; Nut = Record Data: Integer; Next: TroNut; End; Var First: TroNut; Viết chương trình thực hiện các yêu cầu sau: a. Nhập dãy các số nguyên và lưu vào danh sách có nút đầu trỏ bởi First, quá trình nhập dừng khi dữ liệu đưa vào không phải là số nguyên. Program Vi_du_1; Type TroNut = ^ Nut; Nut = Record Data: Integer; Next: TroNut; End; Var First: TroNut; p: pointer; Procedure Nhap; Var n:integer; kq:boolean; last,p: tronut; begin first:=nil; last:= nil; repeat 7 write(‘Nhap gia tri mot nut – Ket thuc bang ky tu Q: ‘); {$I-} readln(n); {$I+} kq:= IOResult=0; if kq then begin new(p); p^.Data:=n; p^.Next:=nil; if first = nil then first:= p; else last^.Next:= p; last:=p; end; until not kq; end; b. In ra màn hình giá trị các nút lớn hơn 0. Procedure In_so_duong; Var p: Tronut; begin p:= first; while p <> nil do begin if p^.Data > 0 then write(p^.Data:8); p:=p^.Next; end; end; Begin Mark(p); Nhap; In_so_duong; Release(p); Readln; End. c. Viết thủ tục đếm số nút có giá trị lớn hơn 0 và tính giá trị trung bình cộng của các nút đó. Procedure Nut_duong(var dem: word; tb:real); 8 Var p: Tronut; tong:longint; begin dem:=0; tong:=0; p:= first; while p <> nil do begin if p^.Data > 0 then begin inc(dem); tong:=tong+p^.Data; end; p:=p^.Next; if dem = 0 then tb:=0 else tb:= tong /dem; end; d. Giả sử dãy giá trị các nút trong danh sách đã được sắp tăng dần. Viết các thủ tục và hàm sau: Procedure Insert(var first: TroNut; m: integer) thực hiện việc bổ sung một nút vào danh sách sao cho tính tăng dần được bảo toàn. Procedure Insert(var first: TroNut; m: integer); Var p,q: Tronut; begin new(p); p^.Data:= m; if (first = nil) or (first^.Data < m ) then begin p^.Next:=nil; first:= p; end else begin q:= first; while (q^.Next <> nil) and ((q^.Next)^.Data < m) do q:= q^.Next; p^.Next:= q^.Next; 9 q^.Next:= p; end; end; Procedure InitList thực hiện việc tạo danh sách có tính chất trên bằng cách nhập dữ liệu từ bàn phím và quá trinh nhập dừng khi nhấn phím ESC (yêu cầu: sử dụng thủ tục Insert). Procedure InitList; Var m: integer; Begin first:= nil; repeat write(‘Nhap gia tri cua mot nut: ‘); readln(m); insert(first,m); until readkey = #27; end; Procedure List(First: TroNut) in dãy giá trị các nút trong danh sách. Procedure List(First: Tronut); Var p:Tronut; begin p:= first; while p <> nil do begin write(p^.Data); p:=p^.Next; end; end; Procedure DeleteZero( Var First: TroNut) thực hiện việc xoá tất cả các nút có giá trị 0 trong danh sách. Procedure DeleteZero(Var First: TroNut); var p,q: Tronut; begin p:= first; while (p <> nil) and (p^.Data < 0) do begin q:= p; p:= p^.Next; end; 10 while (p <> nil) and (p^.Data = 0) do begin q^.Next:= p^.Next; dispose(p); p:= q^.Next; end; end; Function TroMax(First: TroNut): TroNut trả về địa chỉ của nút đầu tiên đạt giá trị lớn nhất (tính từ đầu danh sách, nếu có, ngược lại hàm trả về giá trị Nil). Function Tromax(First: TroNut); var p.q: Tronut; m:integer; begin if first = nil then TroMax:= nil else begin p:= first; m:= p^.Data; q:= p^.Next; while (q <> nil) do begin if q^.Data > m then begin p:= q; m:= p^.Data; end; q:= q^.Next; end; TroMax:=p; end; end; e. Giả sử danh sách khác rỗng. Viết các thủ tục và hàm sau: Function DataMax(First: TroNut): integer trả về giá trị lớn nhất của nút có trong danh sách. Function DataMax(First: TroNut): integer; var m: integer; p, q: Tronut; begin p:= first; 11 m:= p^.Data; q:= p^.Next; while q<> nil do begin if q^.Data > m then m:=q^.Data; q:= q^.Next; DataMax:= m; end; Function DataMin(First: TroNut): Integer trả về giá trị nhỏ nhất của nút có trong danh sách. Function DataMax(First: TroNut): integer; var m: integer; p,q: Tronut; begin p:= first; m:= p^.Data; q:= p^.Next; while q<> nil do begin if q^.Data < m then m:=q^.Data; q:= q^.Next; DataMin:= m; end; f. Cho danh sách liên kết đơn có nút đầu trỏ bởi First, được khai báo như sau Type TroNut = ^nut; Nut = Record Data: real; Next: TroNut; End; Var First: Tronut; Viết các thủ tục và hàm sau: Function Search(First: TroNut; k: word): TroNut trả về địa chỉ của nút thứ k (nếu có, ngược lại, hàm trả về giá trị Nil). Function Search(First: TroNut; k: word): Tronut; Var d: word; p: Tronut; Begin 12 d:=0; p:=first; while (p <> nil) do begin inc(d); if d = k then break; p:= p^.next; end; Search:= p; End; Procedure Delete_K(Var First: TroNut; k: word) thực hiện việc xoá nút thứ k trong danh sách (nếu có). Procedure Delete_K(Var first: Tronut; k:word); var d: word; p,q: Tronut; begin d:=1; p:= first; while (p<> nil) and (d nil then begin if p = first then first:= first^.next else q^.next:= p^.next; dispose(p); end; end; Procedure DeleteList thực hiện việc xoá tất cả các nút trong danh sách. Procedure DeleteList; var p: Tronut; begin while first <> nil do begin p:= first; first:= first^.next; 13 dispose(p); end; end; 2. NGĂN XẾP – STACK 2.1. Khái niệm Stack là một danh sách theo đó tất cả các công việc chèn và huỷ đều được thực hiện ở một đầu của danh sách (gọi là đỉnh của ngăn xếp). Stack giống như một chồng đĩa, đĩa nào đặt cuối cùng lên đỉnh chồng thì đĩa đó sẽ được lấy ra đầu tiên. Do đó Stack còn có tên gọi là LIFO (last in first out – vào sau ra trước). Việc thêm một phần tử vào stack có tên gọi là đẩy (Push) vào stack, còn việc huỷ một phần tử khỏi stack gọi là lấy (Pop) khỏi stack. 2.2 Các thao tác cơ bản của ngăn xếp Đối với một ngăn xếp chỉ có hai thao tác cơ bản: thao tác thêm một phần tử vào Stack và thao tác loại bỏ một phần tử khỏi Stack. Trong khuôn khổ tài liệu này tác giả chỉ đưa ra cách cài đặt Stack bằng DSLK. Stack dùng danh sách liên kết hoàn toàn giống danh sách liên kết thuận, nhưng chỉ có điều khác là khi thêm phần tử mới hay huỷ một phần tử ta luôn luôn làm ở đầu danh sách. Do đó ta phải duy trì một con trỏ Top để trỏ vào phần tử đầu tiên của danh sách (đỉnh của stack) type stack=^TroNut; TroNut=record Data:Datatype; next:stack; end; Var S:Stack; Khởi tạo Stack procedure Khoitao(var s:stack); begin s:=nil; end; 14 Kiểm tra danh sách rỗng function kiemtra(s:stack):boolean; begin if s=nil then kiemtra:=true else kiemtra:=false; end; Thêm một phần tử vào Stack procedure Push(var x:Datatype; var s:stack); var p:stack; begin new(p); p^.data:=x; p^.next:=s; s:=p; end; Lấy một phần tử ra khỏi Stack Procedure Pop(var x:Datatype; var s:stack); var p:stack; begin if Kiemtra(s) then writeln('Stack empty.') else begin p:=s; x:=s^.Data; s:=s^.next; dispose(p); end; end; 2.4. Ứng dụng Stack 2.4.1 Ứng dụng Stack khử đệ quy Stack có nhiều ứng dụng: khử đệ quy, tổ chức lưu vết các quá trình tìm kiếm theo chiều sâu và quay lui, vét cạn, ứng dụng trong các bài toán tính toán biểu thức, … Nếu một chương trình con đệ quy P được gọi từ chương trình chính ta nói chương trình con được thực hiện ở mức 1. Chương trình con này gọi chính nó, ta nói nó đi sâu vào mức 2... cho đến một mức k. Rõ ràng mức k phải thực hiện xong thì mức k-1 mới được thực hiện tiếp tục, hay ta còn nói là chương trình con quay về mức k-1. Trong khi một chương trình con từ mức i đi vào mức i+1 thì các biến cục bộ của mức i và địa chỉ của mã lệnh còn dang dở phải được lưu trữ, địa chỉ này gọi là địa chỉ trở về. Khi từ mức i+1 quay về mức i các giá trị đó được sử dụng. Như vậy những biến cục bộ và địa chỉ lưu sau được dùng trước. Tính chất này 15 gợi ý cho ta dùng một ngăn xếp để lưu giữ các giá trị cần thiết của mỗi lần gọi tới chương trình con. Mỗi khi lùi về một mức thì các giá trị này được lấy ra để tiếp tục thực hiện mức này. a) Bài toán tính giai thừa: Cho số nguyên N, Tính N! Function GT(N:integer) Begin If (N=0) or (N=1) then GT:=1 Else GT:=N*GT(N-1); End; Ý tưởng khử đệ quy bằng Stack: Trong khi N khác 1 thì Push(N,S) vào Stack, giảm N đi 1. Trong khi Stack chưa rỗng thì N:=N* Top(S). Pop(S). Top(S) là giá trị phần tử đầu tiên của S. Procedure GiaiThua; S: Stack; N:integer; Begin Khoitao; If (N=0) or (N=1) then GT:=1 Else While N <> 1 Do Begin Push(N,S); N:=N-1; End; GT:=1; While S < > Nil Do Begin GT:=GT* Top(S); Pop(S); End; Writeln (GT); End; b) Bài toán tính số Fibonaci Dãy số Fibonaci xác định như sau: Bắt đầu từ 2 số 0 và 1 tiếp sau đó là các số Fibonaci sau bằng tổng của 2 số Fibonaci trước đó. F1=0; F2=1; FN = FN-1+ FN-2  N �2 Ví dụ dãy số Fibonaci: 0 1 1 2 3 5 8… Đệ quy hàm Fibonaci như sau: Function Fibo(N:Integer): Longint; Begin If N=1 then Fibo:=0 Else If N=2 then Fibo:=1 Else Fibo:=Fibo(N-1) * Fibo(N-2); 16 End; Khử đệ quy bằng Stack: S: Stack; Fibo: Longint; Khoitao(S); If (N=0) or (N=1) then Fibo:=N Else Begin Push(N,S); While N<>0 Do Begin N:=N-1; Push(N,S); End; If Top(S) <> 2 then Begin T:=0; Pop(S); K:= 1; Pop(S); End; Whike Not Stack_empty Do Begin Fibo:=T+K; T:=K; K:=Fibo; Pop(S); End; End; Writeln(Fibo); c) Khử đệ quy thuật toán sắp xếp Quicksort B1: Khởi tạo một stack rỗng B2: Mảng A ta đang xét từ phần tử thứ 1 đến phần tử thứ N, gán L:=1, R:=N, đẩy hai giá trị 1 và N vào Stack. B3: Lấy lại L, R từ Stack ra B4: Phân hoạch dãy A[L]..A[R] thành hai dãy: A[L]..A[j-1] và dãy A[j+1]...A[R] B5: Nếu j+1 < R thì đẩy (j+1) và R vào Stack. B6: Nếu L< j-1 thì quay lại bước 4 để phân hoạch dãy A[L]..A[j-1] nếu không chuyển sang bước 7. B7: Nếu Stack khác rỗng thì quay lại B3 để phân hoạch tiếp, nếu Stack rỗng thì kết thúc. 17 Const Nmax=5000; Var n, i, j, x, l, r, tg:Integer; s:0.. Nmax; A: Array[1..Nmax] of Integer; Stack: Array [1.. Nmax] of Record 1, r : Integer;End; Procedure Sort; Begin S:=1; Stack[s].1:=1; Stack[s].r :=n ; Repeat 1:=Stack[s].1; r: = Stack[s].r; Dec(s); Repeat i:=1; j:=r;x:=A[(1+r)div 2] Repeat While a[i] < x Do Inc(i); While a [j] > x Do Dec (j); if i < = j then Begin Tg := a[i]; a[i] : = a[j]; a[j] : = tg; Inc(i); Dec(j); End; Until i >j; If i < r then Begin S : = s+1 ; Stack[s].1: = 1; Stack [s].r:=r; End; r:=j; Until 1>r ; Until S=0; End; e) Cài đặt thuật toán Tìm kiếm theo chiều sâu bằng ngăn xếp Cho đơn đồ thị vô hướng G=(V,E) gồm N đỉnh, M cạnh. Các đỉnh được đánh số thứ tự từ 1 đến N. Xuất phát tại đỉnh S, Tìm đường đi từ đỉnh xuất phát S đến đỉnh kết thúc F; Tư tưởng dùng đệ quy của thuật toán tìm kiếm theo chiều sâu (DFS): Trước hết, mọi đỉnh x kề với S tất nhiên sẽ đến được từ S. Với mỗi đỉnh x kề với S đó thì tất nhiên những đỉnh y kề với x cũng đến được từ S. Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông 18 báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v), với v là một đỉnh chưa thăm kề với u. Để không một đinh nào bị liệt kê tới 2 lần, ta sử dụng kĩ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dẫu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa. Để lưu lại đường đi từ đỉnh xuất phát S, trong thủ tục DFS(u), trước khi gọi đệ quy DFS(v), với v kề với u mà chưa đánh dấu, ta lưu lại vết đường đi từ u->v bằng cách Trace[v]:=u, tức là trước khi đến đỉnh v là đỉnh u. Procedure DFS(u:integer); Var v: Integer; Begin <Đánh dấu đã thăm u> Begin Trace[v]:=u; DFS(v); End; End; Khi mô tả quá trình đệ quy bằng ngăn xếp, ta luôn luôn để cho ngăn xếp để lưu lại dây chuyền duyệt sâu từ nút gốc (đỉnh xuất phát S). < Thăm S, đánh dấu S đã thăm> < Đẩy S vào ngăn xếp> Repeat < Lấy u khỏi ngăn xếp> If < u có đỉnh kề chưa thăm> then Begin < Chỉ chọn một đỉnh v, là đỉnh đầu tiên kề với u mà chưa thăm> < Thông báo thăm v> < Đẩy u trở lại ngăn xếp> < Đẩy tiếp v vào ngăn xếp> End; Until < Ngăn xếp rỗng> Chương trình cài đặt Program Depth_First_Search; 19 const max = 100; var a: array[1..max, 1..max] of Boolean; Free: array[1..max] of Boolean; Trace: array[1..max] of Integer; Stack: array[1..max] of Integer; n, S, F, Last: Integer; procedure Enter; var i, u, v, m: Integer; begin FillChar(a, SizeOf(a), False); Readln(n, m, S, F); for i := 1 to m do begin Readln(u, v); a[u, v] := True; a[v, u] := True; end; end; procedure Init; begin FillChar(Free, n, True); Last := 0; end; procedure Push(V: Integer); begin Inc(Last); Stack[Last] := V; end; function Pop: Integer; begin 20