Danh sách liên kết

Danh s¸ch liªn kÕt ®¬n.

3.3.1.1. Nguyªn t¾c.

Trong c¸ch cµi ®Æt nµy, danh s¸ch liªn kÕt ®­îc t¹o nªn tõ c¸c phÇn tö nhá mµ ta gäi lµ nót (node). C¸c nót nµy cã thÓ n»m bÊt kú ®©u trong bé nhí m¸y tÝnh. Mçi nót lµ mét b¶n ghi gåm hai tr­êng, tr­êng infor chøa th«ng tin vÒ mét phÇn tö cña danh s¸ch, tr­êng Next lµ mét con trá trá vµo phÇn tö ®øng sau nã trong danh s¸ch. Qui c¸ch cña mçi nót cã thÓ h×nh dung nh­ sau:

 

 

 

Riªng nót cuèi cïng th× kh«ng cã nót ®øng sau nã nªn tr­êng Next cña nót nµy cã gi¸ trÞ NIL ®Ó b¸o kÕt thóc danh s¸ch.

§Ó cã thÓ truy nhËp vµo mäi nót trong danh s¸ch, ta ph¶i truy nhËp tõ nót ®Çu tiªn, nghÜa lµ cÇn cã mét con trá head 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ã h×nh ¶nh cña mét danh s¸ch liªn kÕt ®¬n nh­ sau:

 

 

 

DÊu        chØ gi¸ trÞ tr­êng Next cña phÇn tö nµy b»ng NIL.

D­íi ®©y lµ khai b¸o cÊu tróc d÷ liÖu biÓu diÔn danh s¸ch liªn kÕt ®¬n.

Type

            Pointer = ^Node ;

Node = Record

                        infor : Item ;

                        Next : Pointer;

            End ;

3.3.1.2. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt ®¬n.

B©y giê chóng ta sÏ xem xÐt mét sè phÐp to¸n t¸c ®éng trªn danh s¸ch liªn kÕt ®¬n.

§iÒu kiÖn ®Ó danh s¸ch liªn kÕt ®¬n rçng lµ head = NIL. Do ®ã, ®Ó khëi t¹o danh s¸ch rçng ta chØ cÇn lÖnh g¸n:

head := NIL;

Danh s¸ch liªn kÕt chØ ®Çy khi kh«ng cßn kh«ng gian nhí ®Ó cÊp ph¸t cho c¸c thµnh míi cña danh s¸ch. Chóng ta gi¶ thiÕt ®iÒu nµy kh«ng x¶y ra, nghÜa lµ danh s¸ch liªn kÕt kh«ng bao giê ®Çy. Do ®ã, phÐp to¸n bæ sung mét phÇn tö vµo danh s¸ch lu«n lu«n ®­îc thùc hiÖn.

1. Bæ sung mét nót míi vµo danh s¸ch liªn kÕt ®¬n.

Gi¶ sö Q lµ mét con trá trá mét nót cña danh s¸ch, ta cÇn bæ sung mét nót míi víi infor lµ X vµo sau nót ®­îc trá bëi Q. PhÐp to¸n nµy ®­îc thùc hiÖn bëi thñ tôc sau:

Procedure InsertAfter(Var head : Pointer; Q : Pointer; X : Item);

Var P : Pointer;

Begin

            {1. T¹o mét nót míi}

            NEW(P);

            P^.infor := X;

            {Thùc hiÖn bæ sung, nÕu danh s¸ch rçng th× bæ sung nót míi vµo thµnh nót ®Çu tiªn, ng­îc l¹i bæ sung nót míi vµo sau nót ®­îc trá bëi Q}

            If head = NIL Then

            begin

                        P^.Next := NIL;

head := P;

end

Else begin

            P^.Next := Q^.Next;

            Q^.Next := P;

end;

End;

Cã thÓ m« t¶ thao t¸c bæ sung trªn b»ng h×nh sau.

 

           

 

 

           

           

 

 

 

Gi¶ sö b©y giê ta cÇn bæ sung nót míi vµo tr­íc nót ®­îc trá bëi Q. PhÐp to¸n nµy phøc t¹p h¬n. Khã kh¨n lµ ë chç, nÕu Q kh«ng ph¶i lµ nót ®Çu tiªn cña danh s¸ch (Q ¹ head) th× ta kh«ng thÓ x¸c ®Þnh ®­îc nót ®øng tr­íc Q ®Ó kÕt nèi nã víi nót míi. Cã thÓ gi¶i quyÕt khã kh¨n b»ng c¸ch, ®Çu tiªn ta vÉn bæ sung nót míi vµo sau Q, sau ®ã trao ®æi gi¸ trÞ chøa trong phÇn infor gi÷a nót míi vµ nót ®­îc trá bëi Q. Thñ tôc thùc hiÖn phÐp to¸n nµy xin dµnh cho b¹n ®äc.

2. Lo¹i bá mét nót ra khái danh s¸ch liªn kÕt ®¬n.

Cho danh s¸ch liªn kÕt ®¬n ®­îc trá bëi head. Q lµ mét con trá trá vµo mét nót trong danh s¸ch. Gi¶ sö ta cÇn lo¹i bá nót ®­îc trá bëi Q. ë ®©y ta còng gÆp khã kh¨n lµ nÕu Q kh«ng ph¶i lµ nót ®Çu tiªn th× kh«ng x¸c ®Þnh ®­îc nót ®øng tr­íc Q. Trong tr­êng hîp nµy ta ph¶i t×m ®Õn nót ®øng tr­íc Q vµ cho con trá R trá vµo nót ®ã, tøc lµ Q = R^.Next. Sau ®ã ta míi thùc hiÖn lo¹i bá nót Q. Ta cã thñ tôc sau:

Procedure Delete(Var head : Pointer; Q : Pointer; Var X : Item);

Var R : Pointer;

Begin

           

            {1. Tr­êng hîp danh s¸ch rçng}

If head = NIL Then

begin

            writeln(‘Danh sach rong’);

            Exit;

end;

X := Q^.infor; {l­u th«ng tin cña nót cÇn lo¹i bá vµo biÕn X}

{2. Tr­êng hîp nót trá bëi Q lµ nót ®Çu tiªn}

If Q = head Then

begin

            head := Q^.Next;

DISPOSE(Q);

Exit;

            end;

            {3. T×m ®Õn nót ®øng tr­íc nót trá bëi Q}

            R := head;

            While R^.next <> Q Do R := R^.Next;

            {4. Lo¹i bá nót trá bëi Q}

            R^.Next := Q^.Next;

            DISPOSE(Q);

End;

PhÐp to¸n lo¹i bá ®­îc m« t¶ bëi h×nh sau:

 

 

 

 

 

 

 

 

3. GhÐp hai danh s¸ch liªn kÕt ®¬n.

Gi¶ sö cã hai danh s¸ch liªn kÕt ®¬n lÇn l­ît ®­îc trá bëi P vµ Q. Thñ tôc sau thùc hiÖn viÖc ghÐp hai danh s¸ch ®ã thµnh mét danh s¸ch míi ®­îc trá bëi P.

Procedure COMBINE(Var P : Pointer; Q : Pointer);

Var R : Pointer;

Begin

            {1. Tr­êng hîp danh s¸ch trá bëi Q rçng}

            If Q = NIL Then Exit;

            {2. Tr­êng hîp danh s¸ch trá bëi P rçng}

            If P = NIL Then

            begin

                        P := Q;

Exit;

            end;

            {3. T×m ®Õn nót cuèi danh s¸ch trá bëi P}

            R := P;

            While R^.Next <> NIL Do

                        R := R^.Next;

            {4. GhÐp}

            R^.Next := Q;

End;

NhËn xÐt: Râ rµng víi c¸c danh s¸ch tuyÕn tÝnh mµ kÝch th­íc lu«n biÕn ®éng trong qu¸ tr×nh xö lý hay th­êng xuyªn cã c¸c phÐp bæ sung vµ lo¹i bá t¸c ®éng, th× viÖc cµi ®Æt b»ng danh s¸ch liªn kÕt nh­ trªn tá ra thÝch hîp. Tuy nhiªn c¸ch cµi ®Æt nµy còng cã nh÷ng nh­îc ®iÓm nhÊt ®Þnh:

ChØ cã phÇn tö ®Çu tiªn trong danh s¸ch ®­îc truy nhËp trùc tiÕp, c¸c phÇn tö kh¸c chØ ®­îc truy nhËp sau khi ®· qua c¸c phÇn tö ®øng tr­íc nã.

ë mçi nót trong danh s¸ch ph¶i cã thªm tr­êng Next ®Ó l­u tr÷ ®Þa chØ cña nót tiÕp theo, do ®ã víi cïng mét danh s¸ch th× viÖc cµi ®Æt bëi danh s¸ch liªn kÕt sÏ tèn bé nhí h¬n.

3.3.1. Danh s¸ch liªn kÕt vßng.

Mét c¶i tiÕn cña danh s¸ch liªn kÕt ®¬n lµ kiÓu danh s¸ch liªn kÕt vßng. Nã kh¸c víi danh s¸ch liªn kÕt ®¬n ë chç: tr­êng Next cña nót cuèi cïng trong danh s¸ch kh«ng ph¶i b»ng NIL, mµ nã trá ®Õn nót ®Çu tiªn trong danh s¸ch, t¹o thµnh mét vßng trßn. H×nh ¶nh cña nã nh­ sau:

 

 

 

 

 

C¶i tiÕn nµy lµm cho viÖc truy nhËp vµo c¸c nót trong danh s¸ch ®­îc linh ho¹t h¬n. Ta cã thÓ truy nhËp vµo mäi nót trong danh s¸ch b¾t ®Çu tõ nót nµo còng ®­îc, kh«ng nhÊt thiÕt ph¶i tõ nót ®Çu tiªn. §iÒu ®ã cã nghÜa lµ nót nµo còng cã thÓ coi lµ nót ®Çu tiªn vµ con trá L trá tíi nót nµo còng ®­îc. Nh­ vËy, ®èi víi danh s¸ch liªn kÕt vßng chØ cÇn cho biÕt con trá trá tíi nót muèn lo¹i bá ta vÉn thùc hiÖn ®­îc v× vÉn t×m ®­îc ®Õn nót ®øng tr­íc ®ã. Víi phÐp ghÐp, phÐp t¸ch còng cã nh÷ng thuËn lîi nhÊt ®Þnh.

Tuy nhiªn, danh s¸ch nèi vßng cã mét nh­îc ®iÓm rÊt râ lµ trong khi xö lý, nÕu kh«ng cÈn thËn sÏ dÉn tíi mét chu tr×nh kh«ng kÕt thóc, bëi v× kh«ng biÕt ®­îc vÞ trÝ kÕt thóc danh s¸ch.

§Ó kh¾c phôc nh­îc ®iÓm nµy, ng­êi ta ®­a thªm vµo danh s¸ch mét nót ®Æc biÖt gäi lµ “nót ®Çu danh s¸ch”. Tr­êng infor cña nót nµy kh«ng chøa d÷ liÖu cña phÇn tö nµo vµ con trá head b©y giê trá tíi nót ®Çu danh s¸ch nµy. ViÖc dïng thªm nót ®Çu danh s¸ch ®· khiÕn cho danh s¸ch vÒ mÆt h×nh thøc kh«ng bao giê rçng. H×nh ¶nh cña nã nh­ sau:

 

 

 

 

 

Sau ®©y lµ ®o¹n gi¶i thuËt bæ sung mét nót vµo thµnh nót ®Çu tiªn trong danh s¸ch cã “nót ®Çu danh s¸ch” trá bëi head.

New(P);

P^.infor := X;

P^.Next := head^.Next;

head^.Next := P;

3.3.1. Danh s¸ch liªn kÕt ®«i.

Khi lµm viÖc víi danh s¸ch, cã nh÷ng xö lý trªn mçi nót cña danh s¸ch l¹i liªn quan ®Õn c¶ nót ®øng tr­íc vµ nót ®øng sau. Trong nh÷ng tr­êng hîp nh­ thÕ, ®Ó thuËn tiÖn, ng­êi ta ®­a vµo mçi nót cña danh s¸ch hai con trá: Nextleft trá ®Õn nót døng tr­íc vµ Nextright trá ®Õn nót ®øng sau nã. §Ó truy nhËp vµo danh s¸ch ta dïng hai con trá: con trá Left trá vµo nót ®Çu tiªn vµ con trá Right trá vµo nót cuèi cïng cña danh s¸ch. H×nh ¶nh cña danh s¸ch liªn kÕt ®«i nh­ sau:

 

 

 

 

 

Ta cã thÓ khai b¸o cÊu tróc d÷ liÖu danh s¸ch liªn kÕt ®«i nh­ sau:

Type

            TRO = ^Nut;

            Nut = Record

                        Infor : Item;

                        Next_left, Next_right : TRO;

            End;

Var Left, Right : TRO;

ViÖc cµi ®Æt danh s¸ch liªn kÕt ®«i sÏ tiªu tèn nhiÒu bé nhí h¬n so víi danh s¸ch liªn kÕt ®¬n. Song bï l¹i, danh s¸ch liªn kÕt ®«i cã nh÷ng ­u ®iÓm mµ danh s¸ch liªn kÕt ®¬n kh«ng thÓ cã ®­îc, ch¼ng h¹n: khi xem xÐt danh s¸ch liªn kÕt ®«i ta cã thÓ lïi l¹i sau, hoÆc tiÕn lªn tr­íc.

C¸c phÐp to¸n trªn danh s¸ch liªn kÕt ®«i ®­îc thùc hiÖn dÔ dµng h¬n. Ch¼ng h¹n, khi thùc hiÖn phÐp to¸n lo¹i bá, víi danh s¸ch liªn kÕt ®¬n, ta kh«ng thÓ thùc hiÖn ®­îc nÕu kh«ng biÕt nót ®øng tr­íc nót cÇn lo¹i bá. Trong khi ®ã, ta cã thÓ tiÕn hµnh dÔ dµng trªn danh s¸ch liªn kÕt ®«i.

B©y giê ta xÐt mét sè gi¶i thuËt t¸c ®éng lªn danh s¸ch liªn kÕt ®«i nãi trªn.

1. PhÐp bæ sung mét nót míi.

Cho hai con trá Left vµ Right lÇn l­ît trá tíi nót ®Çu vµ nót cuèi cña mét danh s¸ch liªn kÕt ®«i, M lµ con trá trá tíi mét nót trong danh s¸ch nµy. Gi¶i thuËt nµy thùc hiÖn bæ sung mét nót míi, mµ d÷ liÖu chøa ë X, vµo tr­íc nót trá bëi M.

Procedure Bo_sung(Var Left, Right : TRO; M : TRO; X : Item);

Var P : TRO;

Begin

{1. T¹o nót míi}

            New(P); P^.infor := X;

{Tr­êng hîp danh s¸ch rçng}

            if (Right = NIL) then

            begin

                        P^.Nextleft := NIL; P^.Nextright := NIL;

                        Left := P; Right := P;

            End

            Else

{Tr­êng hîp M trá tíi nót ®Çu tiªn}

                        if (M = Left) then

                        begin

                                    P^.Nextleft := NIL;

                                    P^.Nextright := M

                                    M^.Nextleft := P;

                                    Left := P;

                        end

                        else {Bæ sung vµo gi÷a}

                        begin

                                    P^.Nextleft := M^.Nextleft;

                                    P^.Nextright := M;

                                    M^.Nextleft := P;

                                    P^.Nextleft^.Nextright := P;

                        end;

End;

2. Lo¹i bá mét nót trªn danh s¸ch.

Cho hai con trá Left vµ Right lÇn l­ît trá tíi nót ®Çu vµ nót cuèi cña mét danh s¸ch liªn kÕt ®«i, M lµ con trá trá tíi mét nót trong danh s¸ch nµy. Gi¶i thuËt nµy thùc hiÖn lo¹i bá nót trá bëi M ra khái danh s¸ch.

Procedure Loai_bo(Var Left, Right : TRO; M : TRO);

Begin

            if R = NIL then

                        write('Danh sach rong')

            else

                        if Left = Right then

                        begin

                                    Left := NIL; Right := NIL;

                        end

                        else

                                    if M = Left then

                                    begin

                                                Left := Left^.Nextright;

                                                Left^.Nextleft := NIL;

                                    end

                                    else if M = Right then

                                    begin

                                                Right := Right^.Nextleft;

                                                Right^.Nextright := NIL;

                                    end

                                    else begin

                                                M^.Nextleft^.Nextright := M^.Nextright;

                                                M^.Nextright^.Nextleft := M^.Nextleft;

                                    end;

End;

Chó ý: Trong c¸c øng dông, ng­êi ta còng th­êng sö dông c¸c danh s¸ch liªn kÕt ®«i vßng trßn, cã nót ®Çu danh s¸ch. Víi lo¹i danh s¸ch nµy, ta cã tÊt c¶ c¸c ­u ®iÓm cña danh s¸ch liªn kÕt ®«i vµ danh s¸ch vßng trßn.

3.3.4. øng dông danh s¸ch liªn kÕt: c¸c phÐp tÝnh sè häc trªn ®a thøc.

Trong môc nµy ta sÏ xÐt c¸c phÐp tÝnh sè häc (céng, trõ, nh©n, chia) ®a thøc mét Èn d¹ng:

A(x) = a_nxⁿ + a_n-1x^n-1 + ...+ a₁x + a₀ (1)

Mçi h¹ng thøc cña ®a thøc ®­îc ®Æc tr­ng bëi hÖ sè vµ sè mò cña x. Gi¶ sö c¸c h¹ng thøc trong ®a thøc ®­îc s¾p xÕp theo thø tù gi¶m dÇn cña sè mò, nh­ trong ®a thøc (1). Ta thÊy ®a thøc nh­ mét danh s¸ch tuyÕn tÝnh víi c¸c phÇn tö cña danh s¸ch lµ c¸c h¹ng thøc cña ®a thøc. Khi ta thùc hiÖn c¸c phÐp to¸n trªn ®a thøc ta sÏ nhËn ®­îc ®a thøc cã bËc kh«ng thÓ ®o¸n tr­íc ®­îc. Ngay c¶ nh÷ng ®a thøc cã bËc x¸c ®Þnh th× sè c¸c h¹ng thøc cña nã còng biÕn ®æi rÊt nhiÒu tõ mét ®a thøc nµy ®Õn mét ®a thøc kh¸c. Do ®ã, ph­¬ng ph¸p tèt nhÊt lµ biÓu diÔn ®a thøc d­íi d¹ng mét danh s¸ch liªn kÕt. Mçi nót cña danh s¸ch lµ mét b¶n ghi gåm ba tr­êng: coef chØ hÖ sè, exp chØ sè mò cña x vµ con trá Next ®Ó trá tíi nót tiÕp theo. CÊu tróc d÷ liÖu m« t¶ mét h¹ng thøc (mét nót) nh­ sau:

type     tro = ^Nut;

            Nut = Record

                        coef : real;

                        exp : integer;

                        next : tro;

            end;

V× nh÷ng ­u ®iÓm cña danh s¸ch vßng trßn cã nót ®Çu danh s¸ch (kh«ng cÇn kiÓm tra danh s¸ch rçng, mäi thµnh phÇn ®Òu cã thµnh phÇn ®i sau), ta chän danh s¸ch liªn kÕt vßng trßn ®Ó biÓu diÔn ®a thøc. Víi c¸ch chän nµy viÖc thùc hiÖn c¸c phÐp to¸n ®a thøc sÏ rÊt gän. Nót ®Çu danh s¸ch lµ nót ®Æc biÖt, cã exp = -1.

Nh­ vËy víi ®a thøc: A(x) = 4x⁵ - 2x³ + 5x² + 6 sÏ ®­îc biÓu diÔn nh­ sau

 

 

 

 

 

 

Sau ®©y chóng ta sÏ xÐt phÐp céng hai ®a thøc A(x) vµ B(x). Con trá A trá tíi ®Çu danh s¸ch biÓu diÔn ®a thøc A(x), con trá B trá tíi ®Çu danh s¸ch biÓu diÔn ®a thøc B(x). Sau khi thùc hiÖn phÐp céng hai ®a thøc trªn ta ®­îc ®a thøc C(x) vµ con trá C trá tíi ®Çu danh s¸ch biÓu diÔn C(x).

Gi¶i thuËt

Tr­íc hÕt cÇn ph¶i thÊy r»ng ®Ó thùc hiÖn phÐp céng A(x) víi B(x) ta ph¶i t×m ®Õn tõng h¹ng thøc cña ®a thøc ®ã, nghÜa lµ ph¶i dïng hai biÕn con trá P vµ Q ®Ó duyÖt qua hai danh s¸ch t­¬ng øng víi hai ®a thøc A(x) vµ B(x) trong qu¸ tr×nh t×m nµy.

Ta thÊy cã nh÷ng tr­êng hîp sau:

a) EXP(P) = EXP(Q), ta sÏ ph¶i thùc hiÖn céng gi¸ trÞ coef ë hai nót ®ã, nÕu gi¸ trÞ tæng kh¸c kh«ng th× ph¶i t¹o ra nót míi thÓ hiÖn h¹ng thøc tæng ®ã vµ g¾n vµo danh s¸ch øng víi C(x).

b) EXP(P) > EXP(Q) (hoÆc ng­îc l¹i còng t­¬ng tù): ph¶i sao chÐp nót P vµ g¾n vµo danh s¸ch cña C(x).

c) NÕu mét danh s¸ch kÕt thóc tr­íc: phÇn cßn l¹i cña danh s¸ch kia sÏ ®­îc sao chÐp vµ g¾n vµo danh s¸ch cña C(x).

Mçi lÇn mét nót míi ®­îc t¹o a ®Òu ph¶i g¾n vµo cuèi danh s¸ch C(x). Do ®ã, cÇn mét con trá R trá vµo nót cuèi cña danh s¸ch C(x).

C«ng viÖc nµy ®­îc thùc hiÖn nhiÒu lÇn, v× vËy cÇn ®­îc thÓ hiÖn b»ng mét thñ tôc gäi lµ Attack(h, m, R). Nã thùc hiÖn: lÊy mét nót míi, ®­a vµo tr­êng coef cña nót nµy gi¸ trÞ h, ®­a vµo tr­êng exp gi¸ trÞ m vµ g¾n nót míi ®ã vµo sau nót trá bëi con trá R.

Procedure Attack(h : real; m : integer; R : tro);

Var N : tro;

Begin

            New(N);

N^.coef := h;

N^.exp := m;

R^.next := N;

R := N;

End;

Sau ®©y lµ thñ tôc céng hai ®a thøc.

Procedure Add(A, B : tro; Var C : tro);

Var      P, Q, R : tro;

            x : real;

Begin

            P := A; Q := B;

New(C); C^.exp := -1; R := C;

            While (P^.exp <> -1) and (Q^.exp <> -1) Do

                        if P^.exp = Q^.exp then

                        begin

                                    x := P^.coef + Q^.coef;

                                    if x <> 0 then

                                                Attack(x, P^.exp, R);

                                    P := P^.next; Q := Q^.next;

 

                        end

                        else

                                    if P^.exp < Q^.exp then

                                    begin

                                                Attack(Q^.coef, Q^.exp, R);

                                                Q := Q^.next;

                                    end

                                    else begin

                                                Attack(P^.coef, P^.exp, R);

                                    end;

            While (P^.exp <> -1) Do {Danh s¸ch øng víi B(x) ®· hÕt}

            Begin                                     

                        Attack(P^.coef, P^.exp, R);

                        P := P^.next;

            End;

            While (Q^.exp <> -1) Do {Danh s¸ch øng víi A(x) ®· hÕt}

            Begin                                     

                        Attack(Q^.coef, Q^.exp, R);

                        Q := Q^.next;

            End;

            R^.next := C;

END;

3.3.5. Danh s¸ch liªn kÕt kiÓu ng¨n xÕp vµ hµng ®îi.

Nh­ ta ®· biÕt, ®èi víi ng¨n xÕp viÖc truy nhËp chØ ®­îc thùc hiÖn ë mét ®Çu (®Ønh). V× vËy, viÖc cµi ®Æt ng¨n xÕp b»ng danh s¸ch liªn kÕt lµ kh¸ tù nhiªn. Ch¼ng h¹n, víi danh s¸ch liªn kÕt ®¬n trá bëi head th× cã thÓ coi head nh­ con trá trá tíi ®Ønh cña ng¨n xÕp. Bæ sung mét nót vµo ng¨n xÕp chÝnh lµ viÖc bæ sung mét nót vµo thµnh nót ®Çu tiªn cña danh s¸ch, cßn lo¹i bá mét nót ra khái ng¨n xÕp chÝnh lµ lo¹i bá nót ®Çu tiªn cña danh s¸ch ®ang trá bëi head. Trong viÖc bæ sung víi ng¨n xÕp d¹ng nµy kh«ng cÇn kiÓm tra hiÖn t­îng trµn nh­ víi ng¨n xÕp l­u tr÷ kÕ tiÕp.

§èi víi hµng ®îi th× lo¹i bá ë mét ®Çu, cßn bæ sung th× ë ®Çu kia. NÕu coi danh s¸ch liªn kÕt ®¬n nh­ mét hµng ®îi th× viÖc lo¹i bá mét nót còng gièng nh­ víi ng¨n xÕp, nh­ng bæ sung mét nót th× ph¶i thùc g¾n nót míi vµo cuèi danh s¸ch, nghÜa lµ ph¶i t×m ®Õn nót cuèi cïng. Trong tr­êng hîp nµy, ®Ó l­u tr÷ danh s¸ch ng­êi ta dïng hai con trá, mét con trá trá vµo nót ®Çu danh s¸ch vµ mét con trá trá vµo nót cuèi danh s¸ch.

3.3.5.1. Cµi ®Æt ng¨n xÕp bëi danh s¸ch liªn kÕt.

§Ó cµi ®Æt ng¨n xÕp bëi danh s¸ch liªn kÕt, ta sö dông con trá S trá vµo ®Ønh cña ng¨n xÕp (h×nh 3.2).

 

 

 

 

 

 

 

H×nh 3.2: Danh s¸ch liªn kÕt biÓu diÔn ng¨n xÕp.

CÊu tróc d÷ liÖu cña ng¨n xÕp ®­îc khai b¸o nh­ sau:

Type   Tro = ^Node;

            Node = Record

                        Info : Item;

                        Next : Tro;

            End;

Var S : Tro;

Trong c¸ch cµi ®Æt nµy, ng¨n xÕp rçng khi S = NIL. Ta gi¶ sö viÖc cÊp ph¸t bé nhí ®éng cho c¸c phÇn tö míi lu«n thùc hiÖn. Do ®ã, ng¨n xÕp kh«ng bao giê ®Çy vµ phÐp to¸n PUSH lu«n thùc hiÖn thµnh c«ng.

Sau ®©y lµ c¸c hµm vµ thñ tôc thùc hiÖn c¸c phÐp to¸n trªn ng¨n xÕp:

+ Khëi t¹o ng¨n xÕp rçng:

Procedure Create(Var S:Tro);

Begin

            S := NIL;

End;

+ KiÓm tra ng¨n xÕp rçng:

Function Empty(S : Tro) : Boolean;

Begin

            Empty := (S = NIL);

End;

+ Bæ sung mét phÇn tö vµo ®Ønh ng¨n xÕp:

Procedure PUSH(Var S : Tro; X : Item);

Var P : Tro;

Begin

            New(P);

            P^.Info := X;

            P^.Next := NIL;

            If S = NIL Then

                        S := P

            Else

                        begin

                                    P^.Next := S;

                                    S := P;

                        end;

End;

 

 

 

 

 

 

 

                                    H×nh **: Minh ho¹ thao t¸c PUSH.

 

+ LÊy ra mét phÇn tö ë ®Ønh ng¨n xÕp:

Procedure POP(Var S : Tro; Var X : Item; Var OK : Boolean);

Var P : Tro;

Begin

            If Empty(S) Then OK := False

            Else begin

                        P := S;

                        X := S^.Info;

                        S := S^.Next;

                        OK := True;

                        Dispose(P);

            end;

End;

 

 

 

 

 

 

 

 

                                    Hinh **: Minh ho¹ thao t¸c POP.              

 

3.3.5.2. Cµi ®Æt hµng ®îi bëi danh s¸ch liªn kÕt.

Còng nh­ ng¨n xÕp, hµng ®îi còng cã cÊu tróc lµ mét danh s¸ch, trªn ®ã ta chØ thùc hiÖn ®­îc mét sè phÐp to¸n ®Æc biÖt. Ta còng cã thÓ sö dông danh s¸ch liªn kÕt ®Ó biÓu diÔn hµng ®îi, trong tr­êng hîp nµy ta sö dông hai con trá, mét con trá trá ®Õn nót ®Çu hµng ®îi, mét con trá trá ®Õn nót cuèi hµng ®îi.

CÊu tróc d÷ liÖu biÓu diÔn hµng ®îi nh­ sau

Type   Tro = ^Node;

            Node = Record

                        Info : Item;

                        Next : Tro;

            End;

            Queue = Record

                        front : Tro;

                        rear : Tro;

            End;

Var  Q : Queue;

Trong c¸ch biÓu diÔn trªn, front lµ con trá trá ®Õn nót ®Çu hµng ®îi, rear lµ con trá trá ®Õn nót cuèi hµng ®îi.

 

 

 

 

 

 

 

H×nh **: Danh s¸ch liªn kÕt biÓu diÔn hµng ®îi.

Víi c¸ch cµi ®Æt nµy, hµng ®îi ®­îc xem lµ kh«ng khi nµo ®Çy. Hµng ®îi rçng khi Q.front = NIL.

Sau ®©y lµ c¸c hµm vµ thñ tôc thùc hiÖn c¸c phÐp to¸n trªn hµng ®îi:

+ Khëi t¹o hµng ®îi rçng:

Procedure Create(Var Q : Queue);

Begin

            Q.front := NIL;

            Q.rear := NIL;

End;

+ KiÓm tra hµng ®îi rçng:

Function Empty(Q : Queue) : Boolean;

Begin

            Empty := (Q.front = NIL);

End;

+ Bæ sung mét phÇn tö vµo cuèi hµng ®îi:

Procedure ADD(Var Q : Queue; X : Item);

Var P : Tro;

Begin

            New(P);

            P^.Info := X;

            P^.Next := NIL;

            If Empty(Q) Then

            begin

                        Q.front := P;

                        Q.rear := P;

            end

            Else

                        begin

                                    Q.rear^.Next := P;

                                    Q.rear := P;

                        end;

End;

 

 

 

 

 

 

 

                                    H×nh **: Minh ho¹ thao t¸c bæng sung.

 

+ LÊy ra mét phÇn tö ë ®Çu hµng ®îi:

Procedure Del(Var Q : Queue; Var X : Item; Var OK : Boolean);

Var P : Tro;

Begin

            If Empty(Q) Then OK := False

            Else begin

                        P := Q.front;

                        X := Q.front^.Info;

                        Q.front := Q.front^.Next;

                        OK := True;

                        Dispose(P);

            end;

End;