Lập trình bằng Turbo Pascal part 8

Chia sẻ: Ashfjshd Askfaj | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

102
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Duyệt một danh sách lμ thao tác truy cập đến tất cả các phần tử của danh sách để thực hiện một xử lí nμo đó sao cho đảm bảo không sót vμ không lặp. Không sót nghĩa lμ mọi phần tử đều đ−ợc xử lí, không lặp nghĩa lμ không phần tử nμo bị xử lí quá một lần. Phép duyệt có thể thực hiện nhờ một vòng lặp For For i:= 1 to L.kt do " xử lí L.PhanTu[i]" ; Ví dụ Thay toμn bộ tên bằng chữ in hoa For i:= 1 to L.kt do L.PhanTu[i]:= upper(L.PhanTu[i]);...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập trình bằng Turbo Pascal part 8

LËp tr×nh b»ng Turbo Pascal 1.3.2 DuyÖt danh s¸ch. DuyÖt mét danh s¸ch lμ thao t¸c truy cËp ®Õn tÊt c¶ c¸c phÇn tö cña danh s¸ch ®Ó thùc hiÖn mét xö lÝ nμo ®ã sao cho ®¶m b¶o kh«ng sãt vμ kh«ng lÆp. Kh«ng sãt nghÜa lμ mäi phÇn tö ®Òu ®−îc xö lÝ, kh«ng lÆp nghÜa lμ kh«ng phÇn tö nμo bÞ xö lÝ qu¸ mét lÇn. PhÐp duyÖt cã thÓ thùc hiÖn nhê mét vßng lÆp For For i:= 1 to L.kt do " xö lÝ L.PhanTu[i]" ; VÝ dô Thay toμn bé tªn b»ng ch÷ in hoa For i:= 1 to L.kt do L.PhanTu[i]:= upper(L.PhanTu[i]); 1.3.3 T×m kiÕm T×m kiÕm mét phÇn tö trong danh s¸ch lμ nh»m ph¸t hiÖn phÇn tö cã chøa mét thμnh phÇn d÷ liÖu trïng khíp víi mÉu ®· cho. MÉu nμy th−êng ®−îc gäi lμ khãa t×m kiÕm. Tuú theo danh s¸ch cã ®−îc s¾p xÕp thø tù theo kho¸ ®· cho hay kh«ng mμ cã c¸c c¸ch t×m kiÕm kh¸c nhau. T×m kiÕm tuÇn tù - Sequential Searching Khi danh s¸ch ch−a ®−îc s¾p xÕp th× c¸ch duy nhÊt ®Ó thùc hiÖn t×m kiÕm lμ duyÖt tõ ®Çu, cho ®Õn khi t×m thÊy hoÆc ph¸t hiÖn kh«ng cã. T×m kiÕm nhÞ ph©n - Binary Searching Khi danh s¸ch ®· ®−îc s¾p xÕp ®óng thø tù theo kho¸ cÇn t×m th× cã thÓ tiÕn hμnh t×m kiÕm theo c¸ch chia ®«i dÇn. §©y lμ thñ tôc t×m kiÕm nhÞ ph©n ®· xÐt ®Õn trong phÇn thñ tôc ®Ö quy. 1.3.4 Thªm phÇn tö. - HoÆc nèi vμo cuèi, khi ®ã danh s¸ch kh«ng ®−îc s¾p theo thø tù. Thùc hiÖn ®¬n gi¶n nh−ng sÏ ph¶i chi phÝ nhiÒu khi t×m kiÕm. - HoÆc chÌn ®óng chç, theo c¸ch nμy buéc ph¶i t×m ®óng vÞ trÝ vμ sau ®ã dÞch chuyÓn c¶ phÇn ®u«i. Thùc hiÖn phøc t¹p h¬n nh−ng bï l¹i khi t×m kiÕm sÏ nhanh h¬n. 1.3.5 Gì bá phÇn tö - T×m ®Õn phÇn tö cÇn gì bá vμ huû phÇn tö nμy b»ng c¸ch chÐp dån lªn 1.4 C¸c −u, nh−îc ®iÓm. Danh s¸ch thÓ hiÖn b»ng cÊu tróc m¶ng cã c¸c −u nh−îc ®iÓm sau. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 189
LËp tr×nh b»ng Turbo Pascal - §¬n gi¶n, cã thÓ cμi ®Æt ®Ô dμng b»ng kiÓu m¶ng ®· quen biÕt. - BÊt tiÖn khi th−êng xuyªn cã thao t¸c thªm bít phÇn tö ë gi÷a danh s¸ch. 1.5 VÝ dô minh ho¹ §Ó thÊy ®−îc c¸c −u nh−îc ®iÓm cña danh s¸ch m¶ng h·y c¶i tiÕn ch−¬ng tr×nh qu¶n lÝ hå s¬ cña sinh viªn ®· ph¸t triÓn trong ch−¬ng 3. Ch−¬ng tr×nh nμy ®· cho phÐp tiÕn hμnh c¸c thao t¸c t¹o lËp, liÖt kª, t×m kiÕm vμ thªm mét hå s¬ vμo cuèi danh s¸ch. CÇn bæ xung thªm chøc n¨ng thø 5 lμ cho phÐp huû mét hå s¬. 1.5.1 Ph©n tÝch, thiÕt kÕ. Chøc n¨ng huû mét hå s¬ trong danh s¸ch sinh viªn lμ thñ tôc phøc t¹p h¬n c¶ v× b¶n ghi cÇn huû cã thÓ n»m ë gi÷a tÖp. CÇn cã thao t¸c dån lÊp chç trèng. Néi dung tÖp ph¶i viÕt l¹i hoμn toμn. Do ®ã cÇn ®äc toμn bé th«ng tin ra mét m¶ng trong bé nhí ®Ó tiÖn xö lÝ. ChØ viÕt l¹i vμo tÖp ë thêi ®iÓm cuèi cïng, khi mäi thay ®æi ®· hoμn tÊt. Mét danh s¸ch c¸c hå s¬ ®−îc thùc hiÖn b»ng m¶ng c¸c b¶n ghi. Ta cÇn khai b¸o mét danh s¸ch m¶ng nh− sau. Type DSHoso = Record PhanTu: array [1..max_kt] of Hoso; Kt: word; End; Var L: DSHoso Chi tiÕt dÇn tõng b−íc thñ tôc huû mét hå s¬ khái danh s¸ch nh− sau. 5. Huû mét hå s¬. - §Çu vμo: tÖp ®· më s½n, m· sè cña hå s¬ cÇn huû gâ tõ bμn phÝm - §Çu ra: tÖp kh«ng cßn chøa b¶n ghi cÇn huû. Chi tiÕt dÇn tõng b−íc. 5.1 ChÐp toμn bé néi dung tÖp ra m¶ng c¸c b¶n ghi. 5.2.1 §−a cöa sæ tÖp vÒ ®Çu tÖp; g¸n chØ sè ®Çu tiªn cña m¶ng. 5.2.2 §äc tõ tÖp ra phÇn tö m¶ng 5.2.3 T¨ng chØ sè m¶ng lªn mét 5.2.4 Dõng khi hÕt tÖp. 5.2 NhËp m· sè cña hå s¬ cÇn huû. 5.3 T×m kiÕm phÇn tö m¶ng lμ b¶n ghi cã m· sè ®· cho: 5.3.1 Gäi thñ tôc T×m kiÕm. 5.4 Xö lÝ kÕt qu¶ t×m kiÕm. 5.4.1 Tr−êng hîp kh«ng thÊy, hiÓn thÞ th«ng b¸o kh«ng thÊy. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 190
LËp tr×nh b»ng Turbo Pascal 5.4.2 Tr−êng hîp thÊy, tiÕn hμnh gì bá b¶n ghi khái m¶ng: 5.4.2.1 ChÐp dån c¸c phÇn tö m¶ng lªn mét vÞ trÝ lÊp vμo chç phÇn tö m¶ng bÞ gâ bá, 5.4.2.2 hiÓn thÞ th«ng b¸o thμnh c«ng. 5.5 Hái l¹i ng−êi dïng cã cÇn huû tiÕp hay kh«ng. 5.6 Xö lÝ tr¶ lêi cã: lÆp l¹i tõ b−íc 5.2; 5.7 ViÕt néi dung cña m¶ng ra tÖp 5.8 §ãng tÖp vμ kÕt thóc. 1.5.2 TriÓn khai chi tiÕt. Tõ b¶ng ph©n tÝch chi tiÕt dÇn tõng b−íc ë trªn, dÔ dμng chuyÓn thμnh mét thñ tôc Pascal nh− d−íi ®©y. L−u ý r»ng ®Ó nhÊn m¹nh cÊu tróc danh s¸ch vμ dÔ theo dâi ta kh«ng sö dông c©u lÖnh with mμ viÕt ®Çy ®ñ c¸c cÊp cña kiÓu b¶n ghi lång nhau. procedure Huy; var TimThay:boolean; CoHuy:boolean; traloi:char; i, csTimThay: integer; begin CoHuy:= false; reset(TepHoso); i:=0; {chep lai vao danh sach de xu ly thao tac huy} while not eof(TepHoso) do begin read(TepHoso,L.PhanTu[i]); i:=i+1; end; L.kt:= i-1; repeat write('Ma so SV can huy thong tin: '); readln(ma); TimThay:= false; i:= 0; while (not TimThay) do begin if L.PhanTu[i].maso=ma then begin TimThay:=true; CoHuy:=true; csTimThay:=i; end; i:=i+1; end; if TimThay then begin {chep lai mang, tru SV can huy} L.kt:= L.kt - 1; for i:= csTimThay to L.kt do begin L.PhanTu[i].maso:= L.PhanTu[i+1].maso; L.PhanTu[i].hoten:= L.PhanTu[i+1].hoten; NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 191
LËp tr×nh b»ng Turbo Pascal L.PhanTu[i].namsinh:= L.PhanTu[i+1].namsinh; end end else writeln(' Ma so SV: ',ma,' khong co trong danh sach'); write(' Can huy tiep (Y/N) ?: ');readln(traloi); until upcase(traloi)='N'; if CoHuy then begin {chep tu L vao tep} rewrite(TepHoso); for i:=0 to L.kt do write(TepHoso,L.PhanTu[i]); close(TepHoso); end else close(TepHoso); end; Ch−¬ng tr×nh sau khi ®−îc bæ xung thªm chøc n¨ng huû hå s¬. program QLSV; uses crt, bgchon; Const maxSize=10; Type HoSo= Record maso:integer; hoten:String[20]; namsinh:string[2]; end; DSHoso = record PhanTu: array[0..maxSize] of HoSo; Kt: word; End; Var TepHoso:File of HoSo; L: DSHoso; sv:HoSo; tenfile:String[8]; ma:integer; SoMC: word; TenMC: Mang_String; Chon: integer; procedure MoTep; .... procedure LietKe; .... procedure TimKiem; .... procedure Them; .... procedure Huy; NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 192
LËp tr×nh b»ng Turbo Pascal .... Procedure NhapThamSoBangChon; begin {khoi tri cac tham so bang chon} SoMC:= 6; TenMC[0]:=' Mo tep du lieu '; TenMC[1]:=' Liet ke '; TenMC[2]:=' Tim kiem '; TenMC[3]:=' Them vao '; TenMC[4]:=' Huy ho so '; TenMC[5]:=' Ket thuc'; End; BEGIN Clrscr; NhapThamSoBangChon; repeat chon:= BangChon(60,15,SoMC,TenMC,Blue,Red) + 1; case chon of 1:MoTep; 2:LietKe; 3:TimPhanTu; 4:ThemPhanTu; 5:HuyPhanTu; end; until (chon = SoMC) or (chon = 0); END. 2. Danh s¸ch kiÓu ng¨n xÕp - Stack. NÕu c¸c thao t¸c thªm bít phÇn tö kh«ng x¶y ra "ë gi÷a" danh s¸ch th× hoμn toμn cã thÓ thùc hiÖn b»ng m¶ng nh− ®· ph©n tÝch ë trªn. D−íi ®©y xÐt hai lo¹i danh s¸ch ®Æc biÖt, c¸c phÐp thªm vμo, lÊy ra thùc hiÖn t¹i vÞ trÝ ®Çu hoÆc cuèi. 2.1 §Þnh nghÝa danh s¸ch kiÓu ng¨n xÕp. Khi lμm viÖc víi mét chång hå s¬ trªn bμn, ta chØ thÊy ®−îc c¸i trªn cïng, lÊy ra lÇn l−ît tõ trªn xuèng d−íi. NÕu cã thªm hå s¬ míi th× xÕp chång lªn trªn. M« h×nh trõu t−îng ho¸ cña chång hå s¬ chÝnh lμ mét danh s¸ch víi c¸c thao t¸c thªm vμo, lÊy ra chØ thùc hiÖn t¹i ®Çu danh s¸ch. §ã lμ danh s¸ch kiÓu ng¨n xÕp hay Stack. §inh nghÜa: Danh s¸ch kiÓu ng¨n xÕp (Stack) lμ mét kiÓu danh s¸ch tuyÕn tÝnh ®Æc biÖt mμ phÐp thªm vμo, lÊy ra phÇn tö chØ thùc hiÖn ë mét ®Çu gäi lμ ®Ønh ng¨n xÕp - Top. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 193
LËp tr×nh b»ng Turbo Pascal Khi cã thao t¸c lÊy ra th× phÇn tö ®−îc xÕp cuèi cïng vμo ng¨n xÕp sÏ ®−îc lÊy ra ®Çu tiªn. Do ®ã ng¨n xÕp cßn cã tªn gäi lμ danh s¸ch kiÓu last in, first out hay danh s¸ch LIFO. Stack cã rÊt nhiÒu øng dông. H×nh 13.1: Mét ng¨n xÕp c¸c hå s¬ BiÓu diÔn danh s¸ch kiÓu ng¨n xÕp. 2.2 Nh− ®· ph©n tÝch ë cuèi tiÕt tr−íc, danh s¸ch kiÓu ng¨n xÕp cã thÓ ®−¬c thùc hiÖn dÔ dμng b»ng m¶ng. Mét ng¨n xÕp gåm mét biÕn m¶ng c¸c phÇn tö vμ mét biÕn kiÓu sè nguyªn ®Ó ghi sè phÇn tö hiÖn cã. NÕu ®¸nh sè c¸c phÇn tö m¶ng tõ 1 th× sè phÇn tö hiÖn cã ®ång thêi còng lμ chØ sè cña phÇn tö trªn cïng cña m¶ng. KiÓu ng¨n xÕp cã thÓ ®−îc khai b¸o nh− sau. Type NganXep = Record PhanTu: array [1.. max_kt ] of kiÓu phÇn tö ; Top: word; End; VAR S: NganXep ; ë ®©y max_kt lμ kÝch th−íc (dù phßng) lín nhÊt cã thÓ cña ng¨n xÕp. Top lμ chØ sè cña phÇn tö trªn ®Ønh. Top còng chÝnh lμ sè phÇn tö hiÖn cã trong ng¨n xÕp. 2.3 C¸c phÐp to¸n ®èi víi kiÓu ng¨n xÕp. 1 - Khëi t¹o ng¨n xÕp rçng: Top:= 0; 2 - Thªm vμo mét phÇn tö. Tªn chuÈn lμ Push. C¸c b−íc thùc hiÖn lμ NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 194
LËp tr×nh b»ng Turbo Pascal - KiÓm tra ®Çy ng¨n xÕp ch−a. NÕu ®Çy, b¸o lçi “trμn ng¨n xÕp”. - Tr¸i l¹i: söa l¹i vÞ trÝ ®Ønh vμ chÐp phÇn tö míi vμo. Procedure Push(x: kiÓuphÇntö, VAR S:Ng¨nXÕp); begin if S.Top=maxSize then .... else begin S.Top:= S.Top+1; S.PhanTu[Top]:= x; end end; 3 - LÊy ra mét phÇn tö Tªn chuÈn lμ Pop. C¸c b−íc thùc hiÖn lμ - KiÓm tra ng¨n xÕp cã rçng kh«ng. NÕu rçng, b¸o lçi “ ng¨n xÕp rçng”. - Tr¸i l¹i: lÊy ra néi dung phÇn tö ë ®Ønh vμ söa l¹i vÞ trÝ ®Ønh. Procedure Pop(S: Ng¨nXÕp; VAR x: kiÓuphÇntö) ; begin if Top=0 then ... else begin S.Top:= S.Top-1; x:= S.PhanTu[S.Top+1]; end end; 3. Danh s¸ch kiÓu hµng ®îi - Queue. 3.1 §Þnh nghÜa danh s¸ch kiÓu hµng ®îi . KiÓu danh s¸ch hμnh ®îi lμ m« h×nh hãa mét lo¹i danh s¸ch mμ ho¹t ®éng cña nã gièng nh− hμng ®îi tr−íc cöa mét quÇy b¸n vÐ. PhÇn tö míi chØ ®−îc thªm vμo cuèi cßn phÇn tö ®−îc lÊy ra chØ tõ vÞ trÝ ®Çu tiªn cña danh s¸ch. §Þnh nghÜa: Danh s¸ch kiÓu hμng ®îi (Queue) lμ mét kiÓu danh s¸ch mμ: - PhÐp thªm phÇn tö vμo chØ thùc hiÖn ë mét ®Çu mót, gäi lμ lèi sau (rear) hay ®u«i hμng ®îi; - PhÐp lÊy phÇn tö ra thùc hiÖn ë ®Çu kia, gäi lμ lèi tr−íc (front) hay ®Çu hμng ®îi. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 195
LËp tr×nh b»ng Turbo Pascal ←←←← ← front rear H×nh 13.2: Hμng ®îi tr−íc quÇy b¸n vÐ. Danh s¸ch kiÓu hμng ®îi sÏ ho¹t ®éng theo theo nguyªn t¾c, ®Õn tr−íc phôc vô tr−íc, ®Õn sau phôc vô sau. do ®ã cßn cã tªn gäi lμ danh s¸ch kiÓu first in first out hay danh s¸ch FIFO. 3.2 BiÓu diÔn danh s¸ch kiÓu hµng ®îi b»ng m¶ng. Hμng ®îi Q gåm mét biÕn m¶ng chøa c¸c phÇn tö, hai biÕn kiÓu sè nguyªn ®Ó ghi chØ sè cña phÇn tö ®Çu vμ phÇn tö cuèi vμ mét biÕn nguyªn kh¸c ®Ó ghi sè phÇn tö hiÖn cã. Type HangDoi = Record PhanTu: array [0.. max_kt - 1] of kiÓuphÇntö ; r,f, kt: word; end; Var Q: HangDoi; Trong ®ã, max_kt lμ kÝch th−íc lín nhÊt (dù phßng) cã thÓ cña hμng ®îi. r = chØ sè phÇn tö cuèi hμng ®îi, f = chØ sè phÇn tö ®Çu hμng ®îi, kt = sè phÇn tö hiÖn cã. L−u ý viÖc ®¸nh chØ sè c¸c phÇn tö m¶ng b¾t ®Çu b»ng 0 ®Ó thuËn tiÖn h¬n cho viÖc nèi vßng trßn nh− sau nμy sÏ thÊy. 3.2 C¸c phÐp to¸n. 3.2.1 Ph©n tÝch 1. Khëi t¹o: r:= -1; f:= 0; kt:= 0; 2. Thªm vμ bít phÇn tö. C¸c b−íc thùc hiÖn thao t¸c thªm phÇn tö vμ lÊy ra phÇn tö cña hμng ®îi nh− sau. - Khi thªm mét phÇn tö vμo hμng ®îi cÇn t¨ng chØ sè phÇn tö cuèi r lªn 1 vμ chÐp néi dung vμo Q(r): NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 196
LËp tr×nh b»ng Turbo Pascal Thªm vμo: kt:= kt+ 1; r:=r+1; Q[r]:=x ; - Khi lÊy mét phÇn tö ra khái hμng ®îi cÇn ®äc néi dung Q(f) vμ t¨ng f lªn 1: LÊy ra: x:= Q[f]; f:= f+1; kt:= kt -1; Tuy nhiªn, nÕu theo dâi ho¹t ®éng cña hμng ®îi sau mét lo¹t thao t¸c thªm vμo, lÊy ra ®−îc triÓn khai ®¬n gi¶n nh− trªn sÏ cã hiÖn t−îng hμng ®îi “bß tr−ên”, di chuyÓn dÇn ®i trong bé nhí. f r xxxxx H×nh 13.3: hμng ®îi dÞch dÇn ra ngoμi m¶ng. §Ó kh¾c phôc hiÖn t−îng nμy cÇn h¹n chÕ mét vïng nhí, chØ cho m¶ng c¸c phÇn tö xoay trë trong vïng nμy. Gi¶i ph¸p lμ nèi ®Çu ®u«i thμnh vßng trßn. Do ®ã ph¶i sö dông phÐp chia ®ång d− modulo trong tÝnh to¸n c¸c chØ sè f, r. r f x xxxxxx H×nh 13.4: Hμng ®îi nèi vßng trßn. - Nèi vßng trßn khi thªm vμo. NÕu r = max_kt -1 th× r+1 v−ît ra ngoμi m¶ng. CÇn lén trë l¹i ®Çu m¶ng nh− h×nh vÏ, tøc lμ cÇn cã r+1:= 0. C«ng thøc tÝnh vÞ trÝ cña phÇn tö ®u«i ph¶i thay ®æi l¹i lμ r:= (r+1) Mod max_kt. - Nèi vßng trßn khi lÊy ra. Khi lÊy ra, ®Þa chØ f cña ®Çu hμng ®îi còng céng thªm 1. Do ®ã, vÊn ®Ò hoμn toμn t−¬ng tù nh− trªn. C«ng thøc tÝnh l¹i vÞ trÝ ®Çu hμng ®îi lμ f:= (f+1) Mod max_kt. 3.2.2 Thñ tôc chi tiÕt. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 197
LËp tr×nh b»ng Turbo Pascal Procedure Enqueue(x: kiÓuphÇntö; VAR Q: HangDoi ); begin if Q.kt = max_kt then “bao loi tran” else begin Q.r:=(Q.r + 1) MOD max_kt; Q.kt:= Q.kt + 1; Q.PhanTu[Q.r]:= x; end end; Procedure Dequeue(Q: HangDoi; x:kiÓuphÇntö); begin if Q.kt = 0 then “bao loi rong” else begin x:= Q.PhanTu.[Q.f]; Q.f:= (Q.f + 1) mod max_kt; Q.kt:= Q.kt -1; end end; 4. Danh s¸ch nèi ®¬n. 4.1 M« t¶. Nh−îc ®iÓm cña danh s¸ch m¶ng lμ thªm vμo lÊy ra phiÒn to¸i do ph¶i dån chç. CÊu tróc xÕp liªn tiÕp c¸c phÇn tö thμnh m¶ng chØ thÝch hîp cho kiÓu ng¨n xÕp, hμng ®îi. Muèn thùc hiÖn mét danh s¸ch víi thao t¸c thªm bít phÇn tö mét c¸ch thuËn tiÖn t¹i bÊt cø vÞ trÝ nμo ta cÇn kh¾c phôc nh−îc ®iÓm cña c¸ch tæ chøc xÕp liªn tiÕp c¸c phÇn tö b»ng c¸ch dïng con trá ®Ó mãc nèi, sö dông liªn kÕt ®éng. Khi thªm vμo phÇn tö hoÆc lÊy ra phÇn tö chØ cÇn sña l¹i c¸c liªn kÕt ®éng. CÇn ph¶i g¾n vμo mçi phÇn tö cña danh s¸ch mét con trá ®Ó trá ®Õn phÇn tö ®øng sau nã. B»ng c¸ch thay ®æi gi¸ trÞ cña con trá nμy ta dÔ dμng ®¶o vÞ trÝ, chÌn thªm, gì ra.. c¸c phÇn tö cña danh s¸ch. 4.2 CÊu tróc mãc nèi. 4.2.1 Ph©n tÝch. Mét danh s¸ch mãc nèi cÊu t¹o tõ c¸c nót - node. Mçi nót gåm tèi thiÓu hai tr−êng: NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 198
LËp tr×nh b»ng Turbo Pascal - Data: chøa d÷ liÖu hoÆc con trá ®Õn biÕn ®éng chøa d÷ liÖu; - N ext: con trá trá tíi nót tiÕp theo. Data N ext Nót cuèi cïng cña danh s¸ch cã tr−êng Next = NIL. Nh− vËy, mçi nót lμ mét biÕn kiÓu b¶n ghi - record, cã mét tr−êng kiÓu con trá trá ®Õn mét nót ®Ó lμm mèi nèi. 4.2.2 Khai b¸o kiÓu danh s¸ch mãc nèi Cã mét ®iÓm tÕ nhÞ cÇn l−u ý lμ khi khai b¸o tr−êng kiÓu con trá trá ®Õn mét nót th× chÝnh kiÓu nót cßn ch−a ®−îc ®Þnh nghÜa xong. Theo quy ®Þnh chung th× mäi thø nh− h»ng, kiÓu, biÕn, hμm, thñ tôc... ®Òu ph¶i ®−îc ®Þnh nghÜa tr−íc khi sö dông, nghÜa lμ sau dÊu con trá (^) ph¶i lμ kiÓu d÷ liÖu ®· ®−îc ®Þnh nghÜa. Pascal chÊp nhËn mét biÖt lÖ cho tr−êng hîp nμy. Trong khai b¸o kiÓu míi ta cã thÓ sö dông mét kiÓu ch−a ®−îc ®Þnh nghÜa råi ®Þnh nghÜa nã sau, miÔn lμ cïng n»m trong phÇn khai b¸o kiÓu. Khi x©y dùng danh s¸ch mãc nèi ta ph¶i khai b¸o tr−íc kiÓu mèi nèi nutPtr lμ con trá ®Õn mét nót vμ sau ®ã míi khai b¸o kiÓu nót. Mét danh s¸ch L ®−îc truy cËp b»ng 1 con trá tíi nót ®Çu tiªn. Danh s¸ch rçng th× L = NIL. Type nutPtr = ^nut; Nut = Record Data: kiÓud÷liÖu; Next: nutPtr; End; Type DanhSachMocNoi = nutPtr; H×nh d−íi ®©y minh ho¹ mét danh s¸ch mãc nèi L. L A B C D H×nh 13.5: H×nh ¶nh cña mét danh s¸ch mãc nèi. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 199
LËp tr×nh b»ng Turbo Pascal 4.3 C¸c phÐp to¸n. T¹i mét thêi ®iÓm chØ cã thÓ truy cËp ®Õn mét nót trong danh s¸ch. §ã lμ nót hiÖn hμnh hay View. Trong c¸c thao t¸c ®èi víi danh s¸ch, cÇn cã con trá V trá ®Õn nót hiÖn hμnh. 4.3.1 Khëi t¹o danh s¸ch rçng L:= NIL; 4.3.2 DuyÖt danh s¸ch Gi¶ sö cÇn tiÕn hμnh mét phÐp xö lÝ víi phÇn d÷ liÖu t¹i mäi nót cña danh s¸ch. Thñ tôc cho phÐp lμm ®iÒu nμy víi mçi nót ®óng mét lÇn vμ kh«ng bá sãt nót nμo gäi lμ duyÖt danh s¸ch. Procedure DS_Duyet(VAR L: DanhSachMocNoi); Var V: NutPtr; Begin V:= L; While V NIL do begin "xu li V^.Data" ; V:= V^.next; End; End; 4.3.3 T×m kiÕm. Gi¶ sö d÷ liÖu t¹i mçi nót lμ mét gi¸ trÞ khãa. Cho tr−íc gi¸ trÞ x lμ khãa t×m kiÕm. CÇn t×m xem trong danh s¸ch cã nót nμo chøa khãa b»ng x hay kh«ng. Function DS_TimKiem(x: kiÓud÷liÖu, L: DanhSachMocNoi): boolean; Var V: nutPtr; TimThay: boolean; Begin V:= L; TimThay:= false; While (V NIL) and not Timthay do begin if V^.Data = x then TimThay:= true else V:= V^.next; End; DS_TimKiem:= TimThay; End; NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 200
LËp tr×nh b»ng Turbo Pascal 4.3.4 Thªm nót vμo sau Cho mét d÷ liÖu x. CÇn thªm vμo danh s¸ch mét nót cã tr−êng d÷ liÖu nhËn gi¸ trÞ lμ x. Víi phÐp to¸n thªm nót vμo, cÇn x¸c ®Þnh vÞ trÝ cña nót míi. VÞ trÝ nót ®−îc thªm vμo cã thÓ lμ ngay sau hoÆc ngay tr−íc nót ®ang xÐt trá bëi mét con trá V. ë ®©y ta xÐt phÐp thªm nót míi vμo sau nót hiÖn hμnh V. Ph©n tÝch: - NÕu L rçng th× nót thªm vμo lμ ®Çu danh s¸ch. - Tr¸i l¹i, cÇn ph¶i söa hai mèi nèi nh− h×nh vÏ. L V A B C D N H×nh 13.6: Mãc nèi l¹i ®Ó thªm nót vμo sau View. Procedure DS_ThemNut_SauView(x: kiÓud÷liÖu; VAR L: DanhSachMocNoi; V: nutPtr); {thªm nót vμo sau V} Var N:nutPtr; begin new (N); Nˆ.Data:= x; if L=NIL then begin L:= N; Nˆ.next:= NIL; end else begin Nˆ.next:= Vˆ.next; Vˆ.next:= N; end end; 4.3.5 Thªm nót vμo tr−íc V. Cã 2 c¸ch lμm - Dß tõ ®Çu danh s¸ch ®Õn nót ngay tr−íc V, sau ®ã thªm vμo sau nót nμy. - HoÆc dïng thñ thuËt, chÐp néi dung Data cña V vμo N, chÐp néi dung Data míi vμo V, söa l¹i c¸c mèi nèi gièng nh− trong thñ tôc trªn. (H·y tù thùc hiÖn nh− mét bμi tËp). NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 201
LËp tr×nh b»ng Turbo Pascal 4.3.6 Gì bá nót. CÇn gì bá nót trá bëi V ra khái danh s¸ch. Ph©n tÝch: - NÕu L rçng, b¸o lçi. - NÕu L chØ gåm mét nót, L trë thμnh rçng. - Tr¸i l¹i, cã hai c¸ch lμm. 1 - Dß tõ ®Çu danh s¸ch ®Õn nót ngay tr−íc V, söa mèi nèi cña nót nμy, cho trá ®Õn nót sau V. 2 - Dïng thñ thuËt sau: NÕu V kh«ng ph¶i lμ nót cuèi danh s¸ch th× chÐp néi dung Data cña nót sau V vμo nót V, söa mèi nèi cña V cho trá ®Õn nót sau n÷a. NÕu V lμ nót cuèi danh s¸ch th× phøc t¹p h¬n. Ph¶i dß t×m tõ ®Çu danh s¸ch ®Õn nót ngay tr−íc V vμ söa mèi nèi cña nót nμy thμnh NIL. (H·y tù thùc hiÖn nh− mét bμi tËp). Thñ tôc d−íi ®©y thùc hiÖn theo c¸ch 1. Procedure DS_HuyNut(VAR L:DanhSachMocNoi ; V:nutPtr); Var C: nutPtr; begin if L=NIL then “danh sach rong” ... else if L=V then begin L:= Vˆ.next; dispose(V) ; end else begin C:= L; while Cˆ.next V do C:= Cˆ.next; Cˆ.next:= Vˆ.next; dispose (V); end; end; Th«ng th−êng danh s¸ch ®−îc x©y dùng víi phÐp thªm phÇn tö vμo cuèi danh s¸ch. Do ®ã, ngoμi con trá trá ®Õn ®Çu danh s¸ch nªn l−u gi÷ thªm con trá ®Õn nót cuèi danh s¸ch T = Tail ®Ó tiÖn thao t¸c. Trong tr−êng hîp nμy mét danh s¸ch mãc nèi lμ bé 2 con trá: L trá ®Õn ®Çu danh s¸ch vμ T trá ®Õn nót cuèi cïng. 5. Danh s¸ch nèi kÐp 5.1 CÊu tróc danh s¸ch nèi kÐp. Danh s¸ch nèi ®¬n chØ tiÖn khÞ duyÖt theo mét chiÒu. NÕu cÇn duyÖt theo chiÒu ng−îc l¹i th× chi phÝ lín. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 202
LËp tr×nh b»ng Turbo Pascal C¶i tiÕn, thùc hiÖn thªm mèi nèi theo chiÒu ng−îc l¹i. Mét nót cã hai con trá, trá ®Õn nót sau vμ ®Õn nót tr−íc nã. Left Data Right L R a b c d H×nh 13.7: Danh s¸ch nèi kÐp. DÜ nhiªn c¸c mèi nèi ph¶i cña nót cùc ph¶i, mèi nèi tr¸i cña nót cùc tr¸i lμ b»ng NIL. Danh s¸ch ®−îc qu¶n lÝ b»ng mét con trá L, trá vμo nót cùc tr¸i. §Ó tiÖn duyÖt theo chiÒu ng−îc, ta thªm con trá R trá vμo nót cùc ph¶i. Khi L=R=NIL th× danh s¸ch “rçng”. Khai b¸o cÊu tróc mét nót nut vμ kiÓu danh s¸ch nèi kÐp còng t−¬ng tù nh− tr−êng hîp danh s¸ch nèi ®¬n. Type nutPtr = ^ nut; Nut = Record Data: kiÓu d÷ liÖu; Left, Right: nutPtr; End; Type DSNoiKep = nutPtr; 5.2 C¸c phÐp to¸n víi danh s¸ch nèi kÐp. PhÐp khëi t¹o danh s¸ch rçng lμ khëi t¹o c¸c con trá L, R b»ng NIL. C¸c thao t¸c duyÖt vμ t×m kiÕm cã thÓ triÓn khai dÔ dμng theo hai chiÒu. Ta xÐt c¸c thao t¸c thªm nót vμ gì bá nót. 1 -Thªm nót. CÇn xÐt 3 tr−êng hîp - khi danh s¸ch rçng. - khi bæ sung vμo vi trÝ cùc tr¸i (cùc ph¶i); - khi bæ xung vμo gi÷a danh s¸ch. Tr−êng hîp bæ xung vμo gi÷a danh s¸ch cÇn chia thμnh thªm vμo bªn tr¸i nót hiÖn hμnh V vμ thªm vμo bªn ph¶i nót hiÖn hμnh V. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 203
LËp tr×nh b»ng Turbo Pascal Procedure DS2_ThemNutVaoTraiView(x: kiÓud÷liÖu; VAR L:DSNoiKep V: nutPtr); Var N: nutPtr; begin new(N); Nˆ.Data:= x; if L = NIL then begin Nˆ.Left:= Nˆ.Right:= NIL; L:=R:=N; End else if V = L then { bæ xung vμo cùc tr¸i } begin Nˆ.Left:= NIL; Nˆ.Right:=V; Vˆ.Left:=N; L:=N; End Else begin Nˆ.Left:=Vˆ.Left; Nˆ.Right:=V; Vˆ.Left:=N; (Vˆ.Right)ˆ.Right:= N; end; end; 2 - Gì bá nót: Còng cÇn xÐt c¸c tr−êng hîp - Danh s¸ch rçng; - Danh s¸ch chØ cã mét nót; - khi lo¹i nót cùc tr¸i (cùc ph¶i); - khi lo¹i nót ë gi÷a. Procedure DS2_HuyNut(VAR L: DSNoiKep; V: nutPtr); begin if L= NIL then “danh s¸ch rçng ” ... else if L=R then L:=R:=NIL else if V=L then begin L:=Lˆ.Right; Lˆ.Left:= NIL end else if V=R then begin R:=Rˆ.Left; Rˆ.Right:= NIL end else begin (Vˆ.Left)ˆ.Right:= Vˆ.Right; (Vˆ.Right)ˆ.Left:= Vˆ.Left; end; end; Sö dông h×nh vÏ minh häa b¹n ®äc cã thÓ thÊy râ c¸ch thay ®æi c¸c mèi nèi. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 204
LËp tr×nh b»ng Turbo Pascal 6. VÝ dô øn g dông cña danh s¸ch mãc nèi. 6.1 C¶i tiÕn ch−¬ng tr×nh qu¶n lÝ hå s¬. L¹i xÐt bμi to¸n qu¶n lÝ hå s¬ cña sinh viªn. Ta ®· x©y dùng mét ch−¬ng tr×nh qu¶n gåm cã c¸c chøc n¨ng t¹o lËp, liÖt kª, t×m kiÕm, thªm vμo cuèi vμ huû mét hå s¬ khái danh s¸ch. V× ch−a sö dông con trá vμ biÕn ®éng, thùc hiÖn danh s¸ch b»ng m¶ng nªn thao t¸c thªm b¶n ghi chØ thuËn tiÖn nÕu thùc hiÖn t¹i cuèi danh s¸ch. Thao t¸c huû mét b¶n ghi ®ßi hái ph¶i chÐp dån toμn bé phÇn ®u«i danh s¸ch rÊt vÊt v¶ khi danh s¸ch cã nhiÒu phÇn tö. §Ó cã thÓ tiÕn hμnh c¸c thao t¸c chÌn thªm, gì bá c¸c b¶n ghi mét c¸ch thuËn tiÖn th× c¸ch tèt nhÊt lμ liªn kÕt c¸c b¶n ghi b»ng mét cÊu tróc danh s¸ch ®éng - danh s¸ch mãc nèi. Ta h·y thö x©y dùng mét ch−¬ng tr×nh c¶i tiÕn h¬n, kh«ng dïng danh s¸ch m¶ng mμ sö dông danh s¸ch mãc nèi ®Ó gi¶i quyÕt bμi to¸n trªn. Ch−¬ng tr×nh cã c¸c chøc n¨ng më tÖp, liÖt kª, t×m kiÕm vμ söa ch÷a th«ng tin, thªm mét hå s¬ vμ huû mét hå s¬ cña danh s¸ch. Víi tÝnh linh ho¹t cña danh s¸ch mãc nèi, cã thÓ dÔ dμng thùc hiÖn chøc n¨ng chÌn thªm hå s¬ vμ huû hå s¬ t¹i mét vÞ trÝ bÊt k× trong danh s¸ch. Do ®ã cã thÓ tæ chøc danh s¸ch ®−îc s¾p theo thø tù. 6.2 Ph©n tÝch thiÕt kÕ. 6.2.1 CÊu tróc d÷ liÖu. Sö dông cÊu tróc danh s¸ch mãc nèi ®¬n nh− ®· tr×nh bμy trªn. PhÇn d÷ liÖu trong mçi nót lμ mét b¶n ghi kiÓu HoSo. Type nutPtr = ^nut; nut = Record Data: HoSo; next: nutPtr; end; Type DanhSac hMocNoi = nutPtr; §Ó cho x¸c ®Þnh, ta quy −íc s¾p xÕp danh s¸ch theo m· sè sinh viªn t¨ng dÇn. 6.2.2 Thùc thi c¸c chøc n¨ng. Thñ tôc më tÖp kh«ng cã g× thay ®æi. C¸c ch−¬ng tr×nh con thùc hiÖn c¸c chøc n¨ng kh¸c cña ch−¬ng tr×nh nh− liÖt kª, t×m kiÕm, thªm vμo vμ gì bá hå s¬ sÏ gäi c¸c phÐp to¸n t−¬ng øng trªn danh s¸ch mãc nèi. Do ®ã phÇn ®Çu cña ch−¬ng tr×nh lμ phÇn triÒn khai NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 205
LËp tr×nh b»ng Turbo Pascal 6.2.3 C¸c phÐp to¸n c¬ së trªn danh s¸ch mãc nèi. Ta quy −íc ®Æt tªn thèng nhÊt c¸c ch−¬ng tr×nh con thùc hiÖn c¸c phÐp to¸n c¬ b¶n trªn danh s¸ch mãc nèi b¾t ®Çu b»ng DS_. C¸c phÐp to¸n ®ã lμ: 1- DS_KhoiTao: Thñ tôc khëi t¹o danh s¸ch mãc nèi. Néi dung ®−îc viÕt l¹i nh− trong tiÕt 4. 2- DS_TimKiem_CoThuTu: Thñ tôc t×m kiÕm mét khãa ®· cho trong danh s¸ch mãc nèi c¸c khãa ®· xÕp theo thø tù t¨ng dÇn. - §Çu vμo: Kho¸ cÇn t×m (lμ mét m· sè sinh viªn). - §Çu ra: KÕt qu¶ t×m thÊy hay kh«ng; VÞ trÝ nót chøa khãa trong danh s¸ch (nÕu t×m thÊy). Ph©n tÝch: - Thñ tôc tr¶ l¹i kÕt qu¶ trong biÕn TimThay kiÓu boolean vμ biÕn nut_kq kiÓu nutPtr. -V× danh s¸ch ®−îc s¾p theo thø tù m· sè sinh viªn t¨ng dÇn nªn thao t¸c t×m kiÕm tuÇn tù cã thÓ rót ng¾n h¬n. Qu¸ tr×nh duyÖt vμ so s¸nh sÏ tiÕp tôc nÕu cßn ch−a t×m thÊy vμ nót ®ang xÐt cã kho¸ bÐ h¬n kho¸ cÇn t×m. Qu¸ tr×nh duyÖt vμ so s¸nh sÏ chÊm døt khi ®· t×m thÊy hoÆc nót ®ang xÐt cã kho¸ lín h¬n kho¸ cÇn t×m. - Khi kÕt qu¶ lμ t×m thÊy th× biÕn nut_kq trá ®Õn nót chøa kho¸ cÇn t×m. - Khi kÕt qu¶ lμ kh«ng t×m thÊy th× biÕn nut_kq trá ®Õn nót ®Çu tiªn cã m· sè lín h¬n m· sè cÇn t×m. Do ®ã, phÐp thªm nót míi vμo danh s¸ch theo ®óng thø tù kho¸ t¨ng dÇn sÏ ph¶i chÌn thªm nót vμo danh s¸ch mãc nèi ngay tr−íc nut_kq. Tr−êng hîp t×m ®Õn cuèi danh s¸ch mμ kh«ng thÊy, nghÜa lμ m· sinh viªn cÇn thªm vμo lín h¬n mäi m· sè cã mÆt trong danh s¸ch th× nut_kq = NIL. VÞ trÝ cña nót míi lμ ë sau nót cuèi danh s¸ch. 3- DS_ThemNut_SauView: ChÌn thªm mét nót vμo sau nót hiÖn hμnh. Thñ tôc nμy dùa trªn thuËt gi¶i ®· tr×nh bμy trong tiÕt 4. Nã còng sÏ ®−îc sö dông ®Ó ®äc tõ tÖp trªn ®Üa ra danh s¸ch mãc nèi trong bé nhí. 4- DS_ThemNut_TruocView: ChÌn thªm mét nót vμo tr−íc nót hiÖn hμnh. Thñ tôc nμy ®−îc viÕt dùa trªn thuËt gi¶i ®· tr×nh bμy trong tiÕt 4. Nã sÏ ®−îc sö dông ®Ó chÌn thªm hå s¬ vμo danh s¸ch sao cho ®¶m b¶o ®óng thø tù m· sè t¨ng dÇn. 5- DS_HuyNut: Gì bá mét nót khái danh s¸ch mãc nèi. Thñ tôc nμy dùa theo thuËt gi¶i ®· ®Ò nghÞ trong tiÕt 4. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 206
LËp tr×nh b»ng Turbo Pascal 6.2.4 C¸c thñ tôc kh¸c 1- DocTepVaoDSmocnoi: Thñ tôc thùc hiÖn viÖc ®äc néi dung cña c¸c b¶n ghi tõ tÖp vμ ghi vμo tr−êng d÷ liÖu cña c¸c nót trong danh s¸ch mãc nèi. Nã sÏ ®−îc gäi sau khi më tÖp vμ tr−íc khi b¾t ®Çu c¸c thao t¸c xö lÝ danh s¸ch sinh viªn. 2- VietDSmocnoiRaTep Thñ tôc viÕt d÷ liÖu trong c¸c nót cña danh s¸ch mãc nèi ra tõng b¶n ghi cña tÖp. Nã ®−îc gäi ®Ó hoμn tÊt mét thao t¸c cã thay ®æi néi dung cña danh s¸ch sinh viªn. 6.2.5 C¸c m« ®un cña ch−¬ng tr×nh. Mçi m« ®un thùc hiÖn mét chøc n¨ng xö lÝ theo ®Æc t¶ yªu cÇu. 1- LietKe: thùc hiÖn viÖc hiÓn thi néi dung toμn bé danh s¸ch. Thñ tôc nμy dùa trªn thao t¸c duyÖt danh s¸ch mãc nèi, chØ bæ xung thªm phÇn tr×nh bμy mμn h×nh vμ hiÓn thÞ th«ng tin trong tõng nót. 2- TimVaSua: Thùc hiÖn viÖc t×m vμ hiÓn thÞ mét hå s¬ cã m· sè nhËp tõ bμn phÝm. Sau ®ã cho phÐp söa ch÷a thay ®æi nÕu cÇn. §Çu vμo lμ m· sè sinh viªn cÇn t×m. Thñ tôc nμy gäi thñ tôc DS_TimKiem_CoThuTu ®Ó thùc hiÖn viÖc t×m kiÕm. Sau khi hiÓn thÞ kÕt qu¶ sÏ hái ng−êi sö dông cã muèn söa ch÷a th«ng tin hay kh«ng. Mét biÕn kiÓu boolean CoSua dïng ®Ó ®¸nh dÊu. ChØ khi thùc sù cã söa ch÷a thay ®æi th«ng tin th× míi gäi thñ tôc VietDSmocnoiRaTep ®Ó cËp nhËt kÕt qu¶. 3- ThemPhanTu: Thùc hiÖn viÖc thªm mét hå s¬ vμo ®óng vÞ trÝ, nghÜa lμ ®¶m b¶o thø tù t¨ng dÇn cña m· sè. §Çu tiªn nã gäi thñ tôc DS_TimKiem_CoThuTu ®Ó t×m ra chç cÇn chÌn. Sau ®ã thùc hiÖn viÖc bæ xung thªm b»ng c¸ch gäi thñ tôc DS_ThemNut_TruocView. 4- HuyPhanTu: Thùc hiÖn huû mét hå s¬ cã m· cho tr−íc khái danh s¸ch. Thñ tôc nμy còng gäi DS_TimKiem_CoThuTu ®Ó t×m ra nót cÇn huû. Sau ®ã thùc hiÖn viÖc gì bá nót t×m thÊy khái danh s¸ch b»ng thñ tôc DS_HuyNut. 6.3 TriÓn khai chi tiÕt. Trong c¸c thñ tôc d−íi ®©y L sÏ lμ con trá trá vμo nót ®Çu cña danh s¸ch mãc nèi, T lμ con trá vμo nót cuèi. Sau khi triÓn khai ®Çy ®ñ c¸c ch−¬ng tr×nh con ®· thiÕt kÕ ë trªn vμ l¾p r¸p vμo khung ch−¬ng tr×nh chÝnh víi m«t b¶ng chän nh− ®· biÕt ta nhËn ®−îc ch−¬ng tr×nh hoμn chØnh d−íi ®©y. NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 207
LËp tr×nh b»ng Turbo Pascal program QLSV; {danh sach moc noi} uses crt, BgChon; Const maxSize=10; Type HoSo= Record maso:integer; hoten:String[20]; namsinh:string[2]; end; nutPtr = ^nut; nut = Record Data: HoSo; next: NutPtr; end; DanhSachMocNoi = NutPtr; Var TepHoSo:File of HoSo; L, T: DanhSachMocNoi; sv:HoSo; tenfile:String[8]; ma:integer; SoMC: word; TenMC: Mang_String; Chon: integer; procedure MoTep; ..... procedure DS_KhoiTao; begin L:=NIL; T:=L; end; procedure DS_TimKiem_CoThuTu(sv:HoSo; Var TimThay: boolean; Var nut_kq: NutPtr); Var V: nutPtr; begin TimThay:= false; V:= L; while (V NIL) do begin if V^.Data.maso < sv.maso then V:= V^.next else if V^.Data.maso = sv.maso then begin TimThay:= True; nut_kq:= V; break; end else begin nut_kq:= V; break; end end; end; procedure DS_ThemNut_SauView(sv:HoSo, V:nutPtr); NguyÔn §×nh Ho¸, ViÖn CNTT - §HQG Hμ néi 208