CH¯ NG 5

DANH SÁCH LIÊN K¾T

KDLTT danh sách ã °ãc xác Ënh trong ch°¡ng 4 vÛi các phép toán xen vào, lo¡i bÏ và tìm ki¿m mÙt Ñi t°ãng khi cho bi¿t vË trí cça nó trong danh sách và mÙt lo¡t các phép toán khác c§n thi¿t cho các xí lý a d¡ng khác trên danh sách. Trong ch°¡ng 4 chúng ta ã cài ·t danh sách bßi m£ng. H¡n ch¿ c¡ b£n cça cách cài ·t này là m£ng có cá cÑ Ënh, mà danh sách thì luôn phát triÃn khi ta thñc hiÇn phép toán xen vào, và do ó trong quá trình xí lý danh sách, nó có thà có Ù dài v°ãt quá cá cça m£ng. MÙt cách lña chÍn khác là cài ·t danh sách bßi c¥u trúc dï liÇu danh sách liên k¿t (DSLK). Các thành ph§n dï liÇu trong CTDL này °ãc liên k¿t vÛi nhau bßi các con trÏ; m×i thành ph§n chéa con trÏ trÏ tÛi thành ph§n ti¿p theo. DSLK có thà nÑi dài ra khi c§n thi¿t, trong khi m£ng chÉ l°u °ãc mÙt sÑ cÑ Ënh Ñi t°ãng dï liÇu.

NÙi dung chính cça ch°¡ng này là nh° sau: Måc 5.1 trình bày nhïng ki¿n théc c§n thi¿t vÁ con trÏ và c¥p phát Ùng bÙ nhÛ trong C + + °ãc sí dång th°Ýng xuyên sau này. Måc 5.2 s½ nói vÁ DSLK ¡n và các d¡ng DSLK khác: DSLK vòng tròn, DSLK kép. Trong måc 5.3, chúng ta s½ cài ·t KDLTT danh sách bßi DSLK. Sau ó, trong måc 5.4, chúng ta s½ phân tích so sánh hai ph°¡ng pháp cài ·t KDLTT danh sách: cài ·t bßi m£ng và cài ·t bßi DSLK. CuÑi cùng, trong måc 5.5, chúng ta s½ th£o lu­n vÁ sñ cài ·t KDLTT t­p Ùng bßi DSLK.

5.1 CON TRÎ VÀ C¤P PHÁT ØNG BØ NHÚ

Cing nh° nhiÁu ngôn ngï l­p trình khác, C + + có các con trÏ, nó cho phép ta xây dñng nên các DSLK và các CTDL phéc t¡p khác. Bi¿n con trÏ (pointer variable), hay gÍi t¯t là con trÏ (pointer), là bi¿n chéa Ëa chÉ cça mÙt t¿ bào nhÛ trong bÙ nhÛ cça máy tính. NhÝ có con trÏ, ta Ënh vË °ãc t¿ bào nhÛ và do ó có thà truy c­p °ãc nÙi dung cça nó.

à khai báo mÙt bi¿n con trÏ P l°u giï Ëa chÉ cça t¿ bào nhÛ chéa dï liÇu kiÃu Item, chúng ta vi¿t

Item * P;

Ch³ng h¡n, khai báo

int * P ;

nói r±ng P là bi¿n con trÏ nguyên, téc là P chÉ trÏ tÛi các t¿ bào nhÛ chéa sÑ nguyên.

MuÑn khai báo P và Q là hai con trÏ nguyên, ta c§n vi¿t

int * P;

int * Q;

ho·c

int * P , * Q;

C§n nhÛ r±ng, n¿u vi¿t

int * P, Q;

thì chÉ có P là bi¿n con trÏ nguyên, còn Q là bi¿n nguyên.

N¿u chúng ta khai báo:

int * P;

int x;

thì các bi¿n này °ãc c¥p phát bÙ nhÛ trong thÝi gian dËch, sñ c¥p phát bÙ nhÛ nh° th¿ °ãc gÍi là c¥p phát t)nh, nó x£y ra tr°Ûc khi ch°¡ng trình °ãc thñc hiÇn. NÙi dung cça các t¿ bào nhÛ ã c¥p phát cho P và x ch°a °ãc xác Ënh, xem minh ho¡ trong hình 5.1a.

B¡n có thà ·t Ëa chÉ cça x vào P b±ng cách sí dång toán tí l¥y Ëa chÉ & nh° sau:

P = &x;

Khi ó chúng ta có hoàn c£nh °ãc minh ho¡ trong hình 5.16, ký hiÇu *P biÃu diÅn t¿ bào nhÛ mà con trÏ P trÏ tÛi

¿n ây, n¿u b¡n vi¿t ti¿p:

*P = 5;

thì bi¿n x s½ có giá trË 5, téc là hiÇu qu£ cça lÇnh gán *P = 5 t°¡ng °¡ng vÛi lÇnh gán x = 5, nh° °ãc minh ho¡ trong hình 5.1c.

Sñ c¥p phát bÙ nhÛ còn có thà x£y ra trong thÝi gian thñc hiÇn ch°¡ng trình, và °ãc gÍi là c¥p phát Ùng (dynamic allocation). Toán tí new trong C + + cho phép ta thñc hiÇn sñ c¥p phát Ùng bÙ nhÛ.

Bây giÝ, n¿u b¡n vi¿t

P = new int;

thì mÙt t¿ bào nhÛ l°u giï sÑ nguyên °ãc c¥p phát cho bi¿n Ùng *P và con trÏ P trÏ tÛi t¿ bào nhÛ ó, nh° °ãc minh ho¡ trong hình 5.1d. C§n l°u ý r±ng bi¿n Ùng *P chÉ tÓn t¡i khi nó ã °ãc c¥p phát bÙ nhÛ, và khi ó, nó °ãc sí dång nh° các bi¿n khác.

Ti¿p theo, b¡n có thà vi¿t

*P = 8;

khi ó sÑ nguyên 8 °ãc ·t trong t¿ bào nhÛ mà con trÏ P trÏ tÛi, ta có hoàn c£nh nh° trong hình 5.1e.

Gi£ sí, b¡n vi¿t ti¿p:

int * Q;

Q = P;

Khi ó, con trÏ Q s½ trÏ tÛi t¿ bào nhÛ mà con trÏ P ã trÏ tÛi, nh° °ãc minh ho¡ trong hình 5.1f.

N¿u bây giÝ b¡n không muÑn con trÏ trÏ tÛi b¥t kó t¿ bào nhÛ nào trong bÙ nhÛ, b¡n có thà sí dång h±ng con trÏ NULL. Trong các minh ho¡, chúng ta s½ biÃu diÅn h±ng NULL bßi d¥u ch¥m. Dòng lÇnh:

Q = NULL

s½ cho hiÇu qu£ nh° trong hình 5.1g.

MÙt khi bi¿n Ùng *P không c§n thi¿t nïa trong ch°¡ng trình, chúng ta có thà thu hÓi t¿ bào nhÛ ã c¥p phát cho nó và tr£ vÁ cho hÇ thÑng. Toán tí delete thñc hiÇn công viÇc này.

Dòng lÇnh

delete P;

s½ thu hÓi t¿ bào nhÛ ã c¥p phát cho bi¿n Ùng *P bßi toán tí new, và chúng ta s½ có hoàn c£nh °ãc minh ho¡ bßi hình 5.1h

int * P;

int x; P x

P = &x ;

P x ho·c *P

*P = 5;

(ho·c x = 5;) P x ho·c *P

P = new int ;

P *P x

*P = 8 ;

P *P x

int * Q ;

Q = P ;

P *P ho·c *Q x

Q

Q = NULL;

P *P x

Q

delete P ;

P x

Q

Hình 5.1. Các thao tác vÛi con trÏ.

C¥p phát m£ng Ùng

Khi chúng ta khai báo mÙt m£ng, ch³ng h¡n

int A[30];

thì ch°¡ng trình dËch s½ c¥p phát 30 t¿ bào nhÛ liên ti¿p à l°u các sÑ nguyên, tr°Ûc khi ch°¡ng trình °ãc thñc hiÇn. M£ng A là m£ng t)nh, vì bÙ nhÛ °ãc c¥p phát cho nó là cÑ Ënh và tÓn t¡i trong suÑt thÝi gian ch°¡ng trình thñc hiÇn, Óng thÝi A là con trÏ trÏ tÛi thành ph§n §u tiên A[0] cça m£ng.

Chúng ta có thà sí dång toán tí new à c¥p phát c£ mÙt m£ng. Sñ c¥p phát này x£y ra trong thÝi gian thñc hiÇn ch°¡ng trình, và °ãc gÍi là sñ c¥p phát m£ng Ùng.

Gi£ sí có các khai báo sau:

int size;

double * B;

Sau ó, chúng ta °a vào lÇnh:

size = 5;

B = new double[size]l

Khi ó, toán tí new s½ c¥p phát mÙt m£ng Ùng B gÓm 5 t¿ bào nhÛ double, và con trÏ B trÏ tÛi thành ph§n §u tiên cça m£ng này, nh° trong hình 5.2b.

Chúng ta có thà truy c­p tÛi thành ph§n thé i trong m£ng Ùng B bßi ký hiÇu truyÁn thÑng B[i], ho·c *(B + i). Ch³ng h¡n, n¿u b¡n vi¿t ti¿p

B[3] = 3.14;

ho·c *(B + 3) = 3.14;

thì thành ph§n thé 3 trong m£ng B s½ l°u 3.14, nh° °ãc minh ho¡ trong hình 5.3c. Tóm l¡i, các thao tác Ñi vÛi m£ng Ùng là giÑng nh° Ñi vÛi m£ng t)nh.

MÙt khi m£ng Ùng không còn °ãc sí dång nïa, chúng ta có thà thu hÓi bÙ nhÛ ã c¥p phát cho nó và tr£ vÁ cho hÇ thÑng à có thà sí dång l¡i cho các công viÇc khác.

N¿u b¡n vi¿t

delete [ ] B;

thì m£ng Ùng B °ãc thu hÓi tr£ l¡i cho hÇ thÑng và chúng ta có hoàn c£nh nh° trong hình 5.2d

a) int size; size B

double * B;

b) size = 5; size B

B = new double[size];

0 1 2 3 4

c) B[3] = 3.14; size B

(ho·c *(B + 3) = 3.14;)

0 1 2 3 4

d) delete [ ] B; size B

Hình 5.2. C¥p phát và thu hÓi m£ng Ùng.

5.2 C¤U TRÚC Dî LIÆU DANH SÁCH LIÊN K¾T

Trong måc này, chúng ta s½ trình bày c¥u trúc dï liÇu DSLK và các phép toán c¡ b£n trên DSLK.

Danh sách liên k¿t ¡n

Danh sách liên k¿t ¡n, gÍi t¯t là danh sách liên k¿t (DSLK) °ãc t¡o nên të các thành ph§n °ãc liên k¿t vÛi nhau bßi các con trÏ. M×i thành ph§n trong DSLK chéa mÙt dï liÇu và mÙt con trÏ trÏ tÛi thành ph§n ti¿p theo. Chúng ta s½ mô t£ m×i thành ph§n cça DSLK nh° mÙt hÙp gÓm hai ngn: mÙt ngn chéa dï liÇu data và mÙt ngn chéa con trÏ next, nh° trong hình 5.3a. Hình 5.3b biÃu diÅn mÙt DSLK chéa dï liÇu là các sÑ nguyên.

(a) Node

& ..

Head

(c) & ..

Head Tail

(d) & &

Hình 5.3. a) MÙt thành ph§n cça DSLK.

b) DSLK chéa các sÑ nguyên.

c) DSLK vÛi mÙt con trÏ ngoài Head

d) DSLK vÛi hai con trÏ ngoài Head và Tail.

Chúng ta s½ biÃu diÅn m×i thành ph§n cça DSLK bßi mÙt c¥u trúc trong C + +, c¥u trúc này gÓm hai bi¿n thành ph§n: bi¿n data có kiÃu Item nào ó, và bi¿n next là con trÏ trÏ tÛi c¥u trúc này.

struct Node

{

Item data ;

Node* next ;

} ;

C§n l°u ý r±ng, trong thành ph§n cuÑi cùng cça DSLK, giá trË cça next là h±ng con trÏ NULL, có ngh)a là nó không trÏ tÛi âu c£ và °ãc biÃu diÅn bßi d¥u ch¥m.

à ti¿n hành các xí lý trên DSLK, chúng ta c§n ph£i có kh£ nng truy c­p tÛi tëng thành ph§n cça DSLK. N¿u bi¿t °ãc thành ph§n §u tiên, i theo con trÏ next, ta truy c­p tÛi thành ph§n thé hai, rÓi të thành ph§n thé hai ta có thà truy c­p tÛi thành ph§n thé ba, & Do ó, khi l°u trï mÙt DSLK, chúng ta c§n ph£i xác Ënh mÙt con trÏ trÏ tÛi thành ph§n §u tiên trong DSLK, con trÏ này s½ °ãc gÍi là con trÏ §u Head. Nh° v­y, khi l­p trình xí lý DSLK vÛi con trÏ §u Head, chúng ta c§n °a vào khai báo

Node* Head ;

Khi mà DSLK không chéa thành ph§n nào c£ (ta nói DSLK r×ng), chúng ta l¥y h±ng con trÏ NULL làm giá trË cça bi¿n Head. Do ó, khi sí dång DSLK vÛi con trÏ §u Head, Ã khßi t¡o mÙt DSLK r×ng, chúng ta chÉ c§n ·t:

Head = NULL ;

Hình 5.3c biÃu diÅn DSLK vÛi con trÏ §u Head. C§n phân biÇt r±ng, con trÏ Head là con trÏ ngoài, trong khi các con trÏ next trong các thành ph§n là các con trÏ trong cça DSLK, chúng làm nhiÇm vå liên k¿t các dï liÇu.

Trong nhiÁu tr°Ýng hãp, Ã các thao tác trên DSLK °ãc thu­n lãi, ngoài con trÏ §u Head ng°Ýi ta sí dång thêm mÙt con trÏ ngoài khác trÏ tÛi thành ph§n cuÑi cùng cça DSLK : con trÏ uôi Tail. Hình 5.3d biÃu diÅn mÙt DSLK vÛi hai con trÏ ngoài Head và Tail. Trong tr°Ýng hãp DSLK r×ng, c£ hai con trÏ Head và Tail Áu có giá trË là NULL.

Sau ây chúng ta s½ xét các phép toán c¡ b£n trên DSLK. Các phép toán này là c¡ sß cho nhiÁu thu­t toán trên DSLK. Chúng ta s½ nghiên céu các phép toán sau:

Xen mÙt thành ph§n mÛi vào DSLK.

Lo¡i mÙt thành ph§n khÏi DSLK.

i qua DSLK (duyÇt DSLK).

Xen mÙt thành ph§n mÛi vào DSLK

Gi£ sí chúng ta ã có mÙt DSLK vÛi mÙt con trÏ ngoài Head (hình 5.3c), chúng ta c§n xen mÙt thành ph§n mÛi chéa dï liÇu là value vào sau (tr°Ûc) mÙt thành ph§n °ãc trÏ tÛi bßi con trÏ P (ta s½ gÍi thành ph§n này là thành ph§n P).

ViÇc §u tiên c§n ph£i làm là t¡o ra thành ph§n mÛi °ãc trÏ tÛi bßi con trÏ Q, và ·t dï liÇu value vào thành ph§n này:

Node* Q;

Q = new Node ;

Q ( data = value;

Các thao tác c§n ti¿n hành à xen mÙt thành ph§n mÛi phå thuÙc vào vË trí cça thành ph§n P, nó ß §u hay giïa DSLK, và chúng ta c§n xen vào sau hay tr°Ûc P.

Xen vào §u DSLK. Trong tr°Ýng hãp này, thành ph§n mÛi °ãc xen vào trß thành §u cça DSLK, và do ó giá trË cça con trÏ Head c§n ph£i °ãc thay Õi. Tr°Ûc h¿t ta c§n móc nÑi thành ph§n mÛi vào §u DSLK, sau ó cho con trÏ Head trÏ tÛi thành ph§n mÛi, nh° °ãc chÉ ra trong hình 5.4a. Các thao tác này °ãc thñc hiÇn bßi các lÇnh sau:

Q ( next = Head;

Head = Q;

Chúng ta có nh­n xét r±ng, thç tåc trên cing úng cho tr°Ýng hãp DSLK r×ng, bßi vì khi DSLK r×ng thì giá trË cça Head là NULL và do ó giá trË cça con trÏ next trong thành ph§n §u mÛi °ãc xen vào cing là NULL.

Xen vào sau thành ph§n P. Gi£ sí DSLK không r×ng và con trÏ P trÏ tÛi mÙt thành ph§n b¥t kó cça DSLK. Ã xen thành ph§n mÛi Q vào sau thành ph§n P, chúng ta c§n móc nÑi thành ph§n Q vào trong dây chuyÁn ã có sµn, nh° °ãc chÉ ra trong hình 5.4b. Tr°Ûc h¿t ta cho con trÏ next cça thành ph§n mÛi Q trÏ tÛi thành ph§n i sau P, sau ó cho con trÏ next cça thành ph§n P trÏ tÛi Q:

Q ( next = P ( next;

P ( next = Q;

Cing c§n l°u ý r±ng, thç tåc trên v«n làm viÇc tÑt cho tr°Ýng hãp P là thành ph§n cuÑi cùng trong DSLK.

Xen vào tr°Ûc thành ph§n P. Gi£ sí DSLK không r×ng, và con trÏ P trÏ tÛi thành ph§n không ph£i là §u cça DSLK. Trong tr°Ýng hãp này, à xen thành ph§n mÛi vào tr°Ûc thành ph§n P, chúng ta c§n bi¿t thành ph§n i tr°Ûc P à có thà móc nÑi thành ph§n mÛi vào tr°Ûc P. Gi£ sí thành ph§n này °ãc trÏ tÛi bßi con trÏ Pre. Khi ó viÇc xen thành ph§n mÛi vào tr°Ûc thành ph§n P t°¡ng °¡ng vÛi viÇc xen nó vào sau thành ph§n Pre, xem hình 5.4c. Téc là c§n thñc hiÇn các lÇnh sau:

Q ( next = P; (ho·c Q ( next = Pre ( next)

Pre ( next = Q;

Head

.......

(a)

Q

P

(b)

... .....

Q

Pre P

(c) ...... ....

Q

Hình 5.4. a) Xen vào §u DSLK.

b) Xen vào sau thành ph§n P.

c) Xen vào tr°Ûc thành ph§n P.

Lo¡i mÙt thành ph§n khÏi DSLK

Chúng ta c§n lo¡i khÏi DSLK mÙt thành ph§n °ãc trÏ tÛi bßi con trÏ P. Cing nh° phép toán xen vào, khi lo¡i mÙt thành ph§n khÏi DSLK, c§n quan tâm tÛi nó n±m ß âu trong DSLK. N¿u thành ph§n c§n lo¡i ß giïa DSLK thì giá trË cça con trÏ ngoài Head không thay Õi, nh°ng n¿u ta lo¡i §u DSLK thì thành ph§n ti¿p theo trß thành §u cça DSLK, và do ó giá trË cça con trÏ Head c§n thay Õi thích éng.

Lo¡i §u DSLK. ó là tr°Ýng hãp P trÏ tÛi §u DSLK. à lo¡i §u DSLK, ta chÉ c§n cho con trÏ Head trÏ tÛi thành ph§n ti¿p theo (xem hình 5.5a). VÛi thao tác ó thành ph§n §u thñc sñ ã bË lo¡i khÏi DSLK, song nó v«n còn tÓn t¡i trong bÙ nhÛ. S½ là lãng phí bÙ nhÛ, n¿u à nguyên nh° th¿, vì v­y chúng ta c§n thu hÓi bÙ nhÛ cça thành ph§n bË lo¡i tr£ vÁ cho hÇ thÑng. Nh° v­y viÇc lo¡i thành ph§n §u DSLK °ãc thñc hiÇn bßi các lÇnh sau:

Head = Head ( next;

delete P;

Lo¡i thành ph§n không ph£i §u DSLK. Trong tr°Ýng hãp này à tháo gá thành ph§n P khÏi dây chuyÁn , chúng ta c§n móc nÑi thành ph§n i tr°Ûc P vÛi thành ph§n i sau P (xem hình 5.5b). Gi£ sí thành ph§n i tr°Ûc thành ph§n P °ãc trÏ tÛi bßi con trÏ Pre. Chúng ta c§n cho con trÏ next cça thành ph§n i tr°Ûc P trÏ tÛi thành ph§n i sau P, sau ó thu hÓi bÙ nhÛ cça thành ph§n bË lo¡i. Do ó thç tåc lo¡i thành ph§n P là nh° sau:

Pre ( next = P ( next;

delete P;

Thç tåc lo¡i trên cing úng cho tr°Ýng hãp P là thành ph§n cuÑi cùng trong DSLK.

Head

& ..

P

(a)

Pre P

& . & ..

(b)

Hình 5.5. (a) Lo¡i §u DSLK.

(b) Lo¡i thành ph§n P

i qua DSLK (DuyÇt DSLK)

Gi£ sí r±ng, b¡n ã có mÙt DSLK, i qua DSLK có ngh)a là truy c­p tÛi tëng thành ph§n cça DSLK b¯t §u të thành ph§n §u tiên ¿n thành ph§n cuÑi cùng và ti¿n hành các xí lý c§n thi¿t vÛi m×i thành ph§n cça DSLK. Chúng ta th°Ýng xuyên c§n ¿n duyÇt DSLK, ch³ng h¡n b¡n muÑn bi¿t mÙt dï liÇu có chéa trong DSLK không, ho·c b¡n muÑn in ra t¥t c£ các dï liÇu có trong DSLK.

Gi£i pháp cho v¥n Á ·t ra là, chúng ta sí dång mÙt con trÏ cur trÏ tÛi thành ph§n hiÇn thÝi (thành ph§n ang xem xét) cça DSLK. Ban §u con trÏ cur trÏ tÛi thành ph§n §u tiên cça DSLK, cur = Head, sau ó ta cho nó l§n l°ãt trÏ tÛi các thành ph§n cça DSLK, b±ng cách gán cur = cur ( next, cho tÛi khi cur ch¡y qua toàn bÙ DSLK, téc là cur = = NULL.

L°ãc Ó duyÇt DSLK °ãc mô t£ bßi vòng l·p sau:

Node* cur ;

for (cur = Head; cur ! = NULL; cur = cur ( next)

{ các xí lý vÛi dï liÇu trong thành ph§n °ãc trÏ bßi cur}

Ví då. à in ra t¥t c£ các dï liÇu trong DSLK, b¡n có thà vi¿t

for (cur = Head; cur ! = NULL; cur = cur ( next)

cout << cur ( data << endl;

Có nhïng xí lý trên DSLK mà Ã các thao tác °ãc thñc hiÇn dÅ dàng, khi duyÇt DSLK ng°Ýi ta sí dång hai con trÏ ch¡y trên DSLK cách nhau mÙt b°Ûc, con trÏ cur trÏ tÛi thành ph§n hiÇn thÝi, con trÏ pre trÏ tÛi thành ph§n éng tr°Ûc thành ph§n hiÇn thÝi, téc là cur = = pre ( next. Ban §u cur trÏ tÛi §u DSLK, cur = Head còn pre = NULL. Sau ó m×i l§n chúng ta cho hai con trÏ ti¿n lên mÙt b°Ûc, téc là ·t pre = cur và cur = cur ( next.

DuyÇt DSLK vÛi hai con trÏ cur và pre là r¥t thu­n tiÇn cho nhïng tr°Ýng hãp mà các xí lý vÛi thành ph§n hiÇn thÝi liên quan tÛi thành ph§n éng tr°Ûc nó, ch³ng h¡n khi b¡n muÑn xen mÙt thành ph§n mÛi vào tr°Ûc thành ph§n hiÇn thÝi, ho·c b¡n muÑn lo¡i bÏ thành ph§n hiÇn thÝi.

Chúng ta có thà biÃu diÅn l°ãc Ó duyÇt DSLK sí dång hai con trÏ bßi vòng l·p sau:

Node* cur = Head ;

Node* pre = NULL;

while (cur! = NULL)

{

Các xí lý vÛi thành ph§n °ãc trÏ bßi cur;

pre = cur;

cur = cur ( next;

}

Ví då. Gi£ sí b¡n muÑn lo¡i khÏi DSLK t¥t c£ các thành ph§n chéa dï liÇu là value. Ã thñc hiÇn °ãc iÁu ó, chúng ta i qua DSLK vÛi hai con trÏ. Khi thành ph§n hiÇn thÝi chéa dï liÇu value, chúng ta lo¡i nó khÏi DSLK, nh°ng trong tr°Ýng hãp này chÉ cho con trÏ cur ti¿n lên mÙt b°Ûc, còn con trÏ Pre éng nguyên, và thu hÓi bÙ nhÛ cça thành ph§n bË lo¡i. Chúng ta cing c§n chú ý ¿n thành ph§n c§n lo¡i là §u hay ß giïa DSLK Ã có các hành Ùng thích hãp. Khi thành ph§n hiÇn thÝi không chéa dï liÇu value, chúng ta cho c£ hai con trÏ cur và Pre ti¿n lên mÙt b°Ûc. Thu­t toán lo¡i khÏi DSLK t¥t c£ các thành ph§n chéa dï liÇu value là nh° sau:

Node* P;

Node* cur = Head;

Node* pre = NULL;

while (cur ! = NULL)

{

if (cur ( data = = value)

if (cur = = Head)

{

Head = Head ( next;

P = cur;

cur = cur ( next;

delete P;

}

else {

pre ( next = cur ( next;

P = cur;

cur = cur ( next;

delete P;

}

else {

pre = cur;

cur = cur ( next;

}

} // h¿t while

5.3 CÁC D NG DSLK KHÁC.

DSLK mà chúng ta ã xét trong måc 5.2 là DSLK ¡n, m×i thành ph§n cça nó chéa mÙt con trÏ trÏ tÛi thành ph§n i sau, thành ph§n cuÑi cùng chéa con trÏ NULL. Trong måc này chúng ta s½ trình bày mÙt sÑ d¡ng DSLK khác: DSLK vòng tròn, DSLK có §u gi£, DSLK kép. Và nh° v­y, trong mÙt éng dång khi c§n sí dång DSLK, b¡n s½ có nhiÁu cách lña chÍn, b¡n c§n chÍn d¡ng DSLK nào phù hãp vÛi éng dång cça mình.

5.3.1 DSLK vòng tròn

Gi£ sí trong ch°¡ng trình b¡n sí dång mÙt DSLK ¡n (hình 5.3c) Ã l°u các dï liÇu. Trong ch°¡ng trình ngoài các thao tác xen vào dï liÇu mÛi và lo¡i bÏ các dï liÇu không c§n thi¿t, gi£ sí b¡n th°Ýng xuyên ph£i xí lý các dï liÇu theo tr­t tñ ã l°u trong DSLK të dï liÇu ß thành ph§n §u tiên trong DSLK ¿n dï liÇu ß thành ph§n sau cùng, rÓi quay l¡i thành ph§n §u tiên và ti¿p tåc. Të mÙt thành ph§n, i theo con trÏ next, chúng ta truy c­p tÛi dï liÇu ß thành ph§n ti¿p theo, song tÛi thành ph§n cuÑi cùng chúng ta ph£i c§n ¿n con trÏ Head mÛi truy c­p tÛi dï liÇu ß thành ph§n §u. Trong hoàn c£nh này, s½ thu­n tiÇn h¡n cho l­p trình, n¿u trong thành ph§n cuÑi cùng, ta cho con trÏ next trÏ tÛi thành ph§n §u tiên trong DSLK Ã t¡o thành mÙt DSLK vòng tròn, nh° °ãc minh ho¡ trong hình 5.6a.

Head

......

(a)

Tail

......

(b)

Hình 5.6. DSLK vòng tròn.

Trong DSLK vòng tròn, mÍi thành ph§n Áu bình ³ng, të mÙt thành ph§n b¥t kó chúng ta có thà i qua toàn bÙ danh sách. Con trÏ ngoài (có nó ta mÛi truy c­p °ãc DSLK) có thà trÏ tÛi mÙt thành ph§n b¥t kó trong DSLK vòng tròn. Tuy nhiên à thu­n tiÇn cho các xí lý, chúng ta v«n tách biÇt ra mÙt thành ph§n §u tiên và thành ph§n cuÑi cùng nh° trong DSLK ¡n. N¿u chúng ta sí dång con trÏ ngoài trÏ tÛi thành ph§n §u tiên nh° trong hình 5.6a, thì à truy c­p tÛi thành ph§n cuÑi cùng chúng ta không có cách nào khác là ph£i i qua danh sách. Song n¿u chúng ta sí dång mÙt con trÏ ngoài Tail trÏ tÛi thành ph§n cuÑi cùng nh° hình 5.6b, thì chúng ta có thà truy c­p tÛi c£ thành ph§n cuÑi và thành ph§n §u tiên, bßi vì con trÏ Tail ( next trÏ tÛi thành ph§n §u tiên. Do ó, sau này khi nói tÛi DSLK vòng tròn ta c§n hiÃu là DSLK vòng tròn vÛi con trÏ ngoài Tail trÏ tÛi thành ph§n cuÑi cùng, nh° trong hình 5.6b. Khi DSLK vòng tròn r×ng, giá trË cça con trÏ Tail là NULL.

VÛi DSLK vòng tròn, khi thñc hiÇn các thao tác xen, lo¡i trong các hoàn c£nh ·c biÇt, b¡n c§n l°u ý Ã khÏi m¯c sai sót. Ch³ng h¡n, të DSLK vòng tròn r×ng, khi xen vào mÙt thành ph§n mÛi °ãc trÏ tÛi bßi con trÏ Q, b¡n c§n vi¿t:

Tail = Q ;

Tail ( next = Tail;

Thêm vào dòng lÇnh Tail ( next = Tail à t¡o thành vòng tròn.

B¡n cing c§n chú ý ¿n phép toán duyÇt DSLK. VÛi DSLK ¡n, ta cho con trÏ cur ch¡y trên DSLK b¯t §u të cur = Head, rÓi thì giá trË cça con trÏ cur thay Õi bßi cur = cur ( next cho tÛi khi cur có giá trË NULL. Nh°ng vÛi DSLK vòng tròn, giá trË cça con trÏ next trong các thành ph§n không bao giÝ là NULL, do ó iÁu kiÇn k¿t thúc vòng l·p c§n ph£i thay Õi, ch³ng h¡n nh° sau:

if (Tail ! = NULL)

{

Node* first = Tail ( next;

Node* cur = first;

do {

các xí lý vÛi dï liÇu trong thành ph§n °ãc trÏ bßi cur;

cur = cur ( next;

}

while (cur ! = first) ;

}

5.3.2 DSLK có §u gi£

Trong DSLK ¡n, khi thñc hiÇn phép toán xen, lo¡i b¡n c§n ph£i xét riêng tr°Ýng hãp xen thành ph§n mÛi vào §u DSLK và lo¡i thành ph§n ß §u DSLK. Ã tránh ph£i phân biÇt các tr°Ýng hãp ·c biÇt này, ng°Ýi ta °a vào DSLK mÙt thành ph§n °ãc gÍi là §u gi£. Ch³ng h¡n, DSLK ¡n trong hình 5.3c, n¿u °a vào §u gi£ chúng ta có DSLK nh° trong hình 5.7a. C§n chú ý r±ng, trong DSLK có §u gi£, các thành ph§n thñc sñ cça danh sách b¯t §u të thành ph§n thé hai, téc là °ãc trÏ bßi Head ( next. DSLK có §u gi£ không bao giÝ r×ng, vì ít nh¥t nó cing chéa §u gi£.

Khi i qua DSLK có §u gi£ sí dång hai con trÏ: con trÏ tr°Ûc Pre và con trÏ hiÇn thÝi cur, thì ban §u Pre = Head và cur = Head ( next. Ã lo¡i thành ph§n °ãc trÏ bßi cur ta không c§n l°u ý thành ph§n ó có là §u DSLK không, trong mÍi hoàn c£nh, ta chÉ c§n ·t:

Pre ( next = cur ( next;

Head

& &

§u gi£

(a)

Head

§u gi£

(b)

Hình 5.7. (a) DSLK có §u gi£

(b) DSLK vÛi §u gi£ l°u thông tin

ôi khi, ng°Ýi ta sí dång §u gi£ à l°u mÙt sÑ thông tin vÁ danh sách, ch³ng h¡n nh° Ù dài, giá trË lÛn nh¥t, giá trË nhÏ nh¥t trong danh sách, nh° trong hình 5.7b. Nh°ng khi ó, §u gi£ có thà có kiÃu khác vÛi các thành ph§n thñc sñ cça DSLK. Và do ó các phép toán xen, lo¡i v«n c§n các thao tác riêng cho các tr°Ýng hãp xen mÙt thành ph§n mÛi vào §u DSLK và lo¡i thành ph§n §u cça DSLK.

5.3.3 DSLK kép

Trong DSLK ¡n, gi£ sí b¡n c§n lo¡i mÙt thành ph§n °ãc Ënh vË bßi con trÏ P, b¡n c§n ph£i bi¿t thành ph§n éng tr°Ûc, n¿u không bi¿t b¡n không có cách nào khác là ph£i i të §u DSLK. MÙt hoàn c£nh khác, các xí lý vÛi dï liÇu trong mÙt thành ph§n l¡i liên quan tÛi các dï liÇu trong thành ph§n i sau và c£ thành ph§n i tr°Ûc. Trong các hoàn c£nh nh° th¿, Ã thu­n lãi ng°Ýi ta thêm vào m×i thành ph§n cça DSLK mÙt con trÏ mÛi: con trÏ tr°Ûc precede, nó trÏ tÛi thành ph§n éng tr°Ûc. Và khi ó ta có mÙt DSL>®

Ò

Ú.* B Š ˜ Ê Ø ¶Jd8 R - !Ö)â)|+~+€+„+8,>,----Î-Ô-Ö-Ø-\.'.Í.Ñ.Û.Ý.(101H1J1†2‰2D3E3 44@4®4N7T7Š8Ô96:';v< >X?P@R@ú@üóíóíóíóíóíóÝÐÝÐÝÐÝóíó½ó½ó½ó½ó½ó½ó½ó½ó½ó½ó½ó½ó½ó½óíóíü¶üíüíüíüí¦íjhKtsCJ UmHnHu

hKts5\$jhKts5CJ U\mHnHuh©I&hKtsCJmH

sH

h©I&hKts5CJ\mH

sH

hKtsCJhKts5CJ\hKtsA :<>À ØÚ,.ê²Èð¶&<R\zª Š¸ýýûûûòòíííòòçíçíòççíûòòíò„Ê'„Ê$a$$„Ê'„Êa$°Þ°þ'ýýý¸‚->N2jz€- !:!š!œ#Ò#"$ò$ %v%Æ%Ž&(f(°(***„*|+ööñèèñèèñèèèñèèñèèèñèèñèèèñ$„Ê'„Êa$$a$$„Ê'„Êa$|+€+†+˜+6,8,P,R, ---.-Ì-Î-Ö-ô-[.\.i.j.Ì.Í.Û./00úúòééòúúúúáééúáØØáéØØáééé$„h^„ha$$

&

Fa$$„Ð^„Ða$$

&

Fa$$a$0 0&1(1F1H122B2...2†2"2ë2ì2û2D3F344@4B4-4ööñéàöööööéààààñ×ÎÁÁÁ

$

ÆÚ„Ê'„Êa$$

ÆÚa$$

ÆÚa$$„h^„ha$$

&

Fa$$a$$„Ð^„Ða$-4®4 7R8Š89v9¶9Ô96:';v<<Ú< >X?r?Ž?L@N@P@T@òëééßßÖÍËÖéòòÖé¾òÖÖÖÖ

$

ÆÚ„Ê'„Êa$$

ÆÚa$$

ÆÚa$

ÆÚ„Ê'„Ê

Æ

Ú

$

ÆÚ„Ê'„Êa$T@V@ú@AAA¼AîAðAüAþAäBæB‚CÀCÄCÆCÈClDnDEEEEòòåòòòåÜÜÜÜÜòåÚÚÚÔÔÊÔÔÔ

Æo „h^„h

Æo $

ÆÚa$

$

ÆÚ„Ð^„Ða$

$

ÆÚ„h^„ha$ú@þ@¼AÂAðAúA‚CCÀCÂCE EEEEÊEÌEˆFŠFÌFÎF$J&J(J*J,J0JÆJÊJÜJTKVKbKdKžKªK¬K²K6L8L<L>LBLðLMŒMŽM"MdOfOêPöPšRV¬VXXŒXDZ¢^Ø^_è'&bòbôbðêðêðêðêðêðêðêáêÝêáêÝÙÝðêðêÓðêðêðêðêðêÓðêðêðêðêáêÝáêÝêÝêÝêƶ«Æê¢ jàðhKtsCJ h©I&hKtsmH

sH

h©I&hKts5CJ\mH

sH

h©I&hKtsCJmH

sH

hÓCJhÓhKtshKts5CJ\

hKtsCJjhKtsCJ UmHnHu@EnEpEÊEÌEˆFŠFÌFÎF$J&J(J,JÄJÆJÈJÊJæJTKbKžK¬K6L8LöíííæíííæææííäääÛÕäÏÏÈÈ

ÆÍæ

ÆÍ

Æ|

&

F

Æ|

Æ Úo $

Æo a$$

Æo a$8L>LðLMŒMM'MàMLNÐNfOhOèPêPQ

Q,QPQXQZQšRVøøøòòðêàêêÛÛÛÎÎÎÎÎÎÎÇ

Æ Ú

$

Æ

„Ê'„Êa$$a$

Æ

„h^„h

Æ

Ææ

ÆÍæV¬VXXŒXDZè\"^d^¢^Ö^Ø^__è'Úa8b¢bcLdòðçàÓÓÇÇǺ®¡àÓÓÓÓÓ

$

Æ

„h^„ha$

$

&

F

Æ

a$

$

Æ

„Ê^„Êa$

$

&

F

Æ

a$

$

Æ

„Ê'„Êa$

Æ Ú

$

Æ

a$

$

Æ

„Ê'„Êa$ôbLdldòfôfÌhühÐkÒkækèkúkükâlmžp pÆpÈpàpâpøpúpqqqq¾qÊq;r<rÆrÉrs s

s;sBsFs€s„s‡s¨s­sÂsttttttltptÉtÏtÒtÚtÜtßtAuBuDuFu„u...u‡u w&wdw€zšz~úñúèúñúèúèúèúáÝÖÝÖÝÖÝÖÝÆÝÆúÆúÆúÆúÆÀúºÆúÆÀúÆ'úÆúÆúÆúÆúÆúÆúÀúÆúÆúÆúñúáÝñú

hélšCJ

hÓCJ

h©I&CJjhKtsCJ UmHnHu

jàðhKtshKts

hKts5\ jàðhKtsCJhKts5CJ\

hKtsCJGLdîfg$gÌhÌköklâlšpðpq qq¾q:r;rÆrs

s ss9sòòòòòòòéâââ××òéÕÕÏÕÕÕÉ

Æü„Ð'„Ð

Æ Ú

„'„

Æ Ú

$

Æ

a$

$

Æ

„Ê'„Êa$9s:s;s<s=s>s?s@sAsBsGss€s¨sttttttitjtktltÉtöíííííííííëëëåëëëëëëëàÛÛ$a$$a$„Ð'„Ð$

Æüa$$

Æüa$ÉtÑtÒtAuCuDuGuHuIu‚uƒu„u†u všv$w&wbwdw~z€zù÷÷÷÷÷÷÷ññèãÝÝÝÝÓÈÁÁ

Æ Úú

Æ

ú„h^„h

&

F

Æ

ú

Æú$a$$„Ð'„Ða$„Ð'„Ð

ÆM

€zî}~.~0~¾Òt‚x‚~‚Ø‚Ú‚'ƒbƒdƒ†ƒŽƒƒ-ƒ„„ „òòòòòòòòéããáãááÛÒÒÉÉáá$

ÆVa$$

ÆVa$

ÆV

Ʊ$

Æúa$

$

Æú„Ê'„Êa$~~0~v~˜š®°t‚v‚x‚z‚~‚'‚Ú‚Þ‚ƒ"ƒ-ƒ¦ƒ „0„......

...

............¼...À...ô...‹‹ø‹bŒdŒèŒòŒ¸ºðò68r't'‚'h•j•~•ˆ•>›@›Î›Ð›œœ^œ_œkœlœ¤œ¥œ žNž÷ñèñ÷ñ÷ñØñØñØñØñØñØñØñØñØñØñèñȽ¶½²¶²«²¶²¶²¶²¶²ñ÷ñ«²¶²¶²¶²¶²¶²¶²¶²«

hKts5\hKts

jàðhKts h©I&hKtsmH

sH

h©I&hKts5CJ\mH

sH

jhKtsCJ UmHnHuhKts5CJ\

hKtsCJ jàðhKtsCJC „...

... ............X...¾...À...ò...ô...Úˆ˜‹ø‹ŒrŒèŒfÈŽ‚'ùùððçåßÕÕÌÕÅÅÅÅÅÅÅÅÅÅ

Æ ÚÎ

&

F

ÆÎ

Æ΄h^„h

ÆÎ$

Æta$$

Æta$

Æt‚'¬"T"V"€"¨"Ð"Ô"0•L•x•|•~•Žšš¦šÎšöš ›$›b›Ž› ›Þ›œ œòòòòòòèèèèèèÞÞÞÞÞÞÞÞÞÞÞÞÞ $

Æ

Îa$

Æ΄Ê'„Ê

$

Æ΄Ê'„Êa$ œ6œ@œKœsœ‹œ¬œÅœÓœÞœøœ(ž žNžPžr¡t¡¦¡¨¡è§ì§ô§ ¨=¨õõõõõõõõõõõõççççõõççõççÝÝ

Æ΄Ê'„Ê

$

Æ

΄'„a$ $

Æ

Îa$Nžt¡¨¡è§ê§ô§ø§ ¨ ¨=¨@¨I¨J¨K¨Y¨ ©!©#©ª¶¯¸¯d³„³†³Ò³Ô³tµvµ ··v·x·º·È·†¸ˆ¸¼¸È¸ø¸,¹ø¼ú¼-¾˜¾®¿°¿È¿Ê¿Ø¿Ú¿à¿â¿ä¿ ÀúÀÁ Á@ÁBÁDÁFÁzÁšÁ¬ÁÊÁÌÁÐÁÀÂÄÂÚÅÆÊüDþFþJþPþüõüåüåßåßåßåßåßåßÖüÏüÄÏÄÏÄÏÄõüÏüõüÏüõüõüÏüÏüÏüÏüåüåüåüßüßåßåßåüßåßÖßüõüÂüåüåU h©I&hKtsmH

sH

jàðhKtshKts5CJ\

hKtsCJjhKtsCJ UmHnHu

hKts5\hKtsL=¨A¨B¨C¨H¨I¨K¨«¨¬¨â¨©©© ©"©#©[©k©˜±d³z³¢³'· ·ù÷÷ññññ÷÷÷÷÷ëë÷ååÝÝÝÝÑÝÝ

$

Æ

„'„a$$

Æ

a$

Ææ

ÆÈ

Æ_

ÆÎ ·:·B·†·º·Ð·Z¸-¸²¸ì¸ö¸ø¸,¹.¹'½¦¿Ø¿à¿ä¿<À>À@ÀÁ Á6Á>Á@Á÷÷÷÷÷÷÷÷÷÷ëëë÷÷÷ë÷ëéééééää$a$

$

Æ

„'„a$$

Æ

a$@ÁDÁzÁœÁžÁ Á¢ÁÂÁÊÁÎÁÐÁ4ÂÂÂÄÂØÅÚÅÆÆ@þBþDþHþJþTþ„þúúøøøøøóúøííúåÙÙååååÙøÓø

Æ"

$

Æ

„'„a$$

Æ

a$„Ð'„Ð$a$$a$K kép, nh° trong hình 5.8a. M×i thành ph§n cça DSLK kép chéa mÙt dï liÇu và hai con trÏ: con trÏ next trÏ tÛi thành ph§n i sau, con trÏ precede trÏ tÛi thành ph§n i tr°Ûc. Giá trË cça con trÏ precede ß thành ph§n §u tiên và giá trË cça con trÏ next ß thành ph§n sau cùng là h±ng NULL.

Head

(a)

Head

(b)

Head

(c)

(c)

Hình 5.8. (a) DSLK kép.

(b) DSLK kép vòng tròn có §u gi£.

(c) DSLK kép r×ng vòng tròn vÛi §u gi£.

à thu­n tiÇn cho viÇc thñc hiÇn các phép toán xen, lo¡i trên DSLK kép, ng°Ýi ta th°Ýng sí dång DSLK kép vòng tròn có §u gi£ nh° °ãc minh ho¡ trong hình 5.8b. C§n l°u ý r±ng mÙt DSLK kép r×ng vòng tròn vÛi §u gi£ s½ có d¡ng nh° trong hình 5.8c. B¡n có thà khßi t¡o ra nó bßi các dòng lÇnh:

Head = new Node;

Head ( next = Head;

Head ( precede = Head;

VÛi DSLK kép vòng tròn có §u gi£, b¡n có thà thñc hiÇn các phép toán xen, lo¡i mà không c§n quan tâm tÛi vË trí ·c biÇt. Xen, lo¡i ß vË trí §u tiên hay cuÑi cùng cing giÑng nh° ß vË trí b¥t kó khác.

Gi£ sí b¡n c§n lo¡i thành ph§n °ãc trÏ bßi con trÏ P, b¡n chÉ c§n ti¿n hành các thao tác °ãc chÉ ra trong hình 5.9a, téc là:

Cho con trÏ next cça thành ph§n i tr°Ûc P trÏ tÛi thành ph§n i sau P.

Cho con trÏ precede cça thành ph§n i sau P trÏ tÛi thành ph§n i tr°Ûc P.

Các thao tác trên °ãc thñc hiÇn bßi các dòng lÇnh sau:

P ( precede ( next = P ( next;

P ( next ( precede = P ( precede;

P

(a)

P

Q

(b)

Hình 5.9. (a) Lo¡i khÏi DSLK kép thành ph§n P.

(b) Xen thành ph§n Q vào tr°Ûc thành ph§n P.

Chúng ta có thà xen vào DSLK kép mÙt thành ph§n mÛi °ãc trÏ bßi con trÏ Q vào tr°Ûc thành ph§n °ãc trÏ bßi con trÏ P b±ng các thao tác °ãc chÉ ra trong hình 5.9b

·t con trÏ next cça thành ph§n mÛi trÏ tÛi thành ph§n P.

·t con trÏ precede cça thành ph§n mÛi trÏ tÛi thành ph§n i tr°Ûc P.

·t con trÏ next cça thành ph§n i tr°Ûc P trÏ tÛi thành ph§n mÛi.

·t con trÏ precede cça thành ph§n P trÏ tÛi thành ph§n mÛi.

Các dòng lÇnh sau thñc hiÇn các hành Ùng trên:

Q ( next = P;

Q ( precede = P ( precede;

P ( precede ( next = Q;

P ( precede = Q;

ViÇc xen mÙt thành ph§n mÛi vào sau mÙt thành ph§n ã Ënh vË trong DSLK kép cing °ãc thñc hiÇn t°¡ng tñ.

5.4 CÀI ¶T DANH SÁCH BÞI DSLK

Trong ch°¡ng 4, chúng ta ã nghiên céu ph°¡ng pháp cài ·t KDLTT danh sách bßi m£ng, téc là mÙt danh sách (a1, a2, & , an) s½ °ãc l°u ß o¡n §u cça m£ng. Måc này s½ trình bày mÙt cách cài ·t khác: cài ·t bßi DSLK, các ph§n tí cça danh sách s½ °ãc l§n l°ãt °ãc l°u trong các thành ph§n cça DSLK. à cho phép toán Append (thêm mÙt ph§n tí mÛi vào uôi danh sách) °ãc thñc hiÇn dÅ dàng, chúng ta có thà sí dång DSLK vÛi hai con trÏ ngoài Head và Tail (hình 5.10a) ho·c DSLK vòng tròn vÛi mÙt con trÏ ngoài Tail (hình 5.10b). N¿u lña chÍn cách thé hai, téc là cài ·t danh sách bßi DSLK vòng tròn, thì chÉ c§n mÙt con trÏ ngoài Tail, ta có thà truy c­p tÛi c£ uôi và §u (bßi Tail ( next) và thu­n tiÇn cho các xí lý mang tính l§n l°ãt tëng thành ph§n và quay vòng trên danh sách. Sau ây chúng ta s½ cài ·t danh sách bßi DSLK vÛi hai con trÏ ngoài Head và Tail nh° trong hình 5.10a. ViÇc cài ·t danh sách bßi DSLK vòng tròn vÛi mÙt con trÏ ngoài Tail (hình 5.10b) à l¡i cho Ùc gi£ xem nh° bài t­p.

Head Tail

& &

(a)

Tail

& &

(b)

Hình 5.10. Cài ·t danh sách (a1, a2, & , an) bßi DSLK

C§n l°u ý r±ng, n¿u cài ·t DSLK chÉ vÛi mÙt con trÏ ngoài Head, thì khi c§n xen vào uôi danh sách chúng ta ph£i i të §u l§n l°ãt qua các thành ph§n mÛi ¡t tÛi thành ph§n cuÑi cùng.

Chúng ta s½ cài ·t KDLTT danh sách bßi lÛp khuôn phå thuÙc tham bi¿n kiÃu Item, vÛi Item là kiÃu cça các ph§n tí trong danh sách (nh° chúng ta ã làm trong các måc 4.2, 4.3). Danh sách s½ °ãc cài ·t bßi ba lÛp: lÛp các thành ph§n cça DSLK (°ãc ·t tên là lÛp LNode), lÛp danh sách liên k¿t (lÛp LList) và lÛp công cå l·p (lÛp LListIterator). Sau ây chúng ta s½ l§n l°ãt mô t£ ba lÛp này.

LÛp LNode s½ chéa hai thành ph§n dï liÇu: bi¿n data à l°u dï liÇu có kiÃu Item và con trÏ next trÏ tÛi thành ph§n i sau. LÛp này chÉ chéa mÙt hàm ki¿n t¡o à t¡o ra mÙt thành ph§n cça DSLK chéa dï liÇu value, và giá trË cça con trÏ next là NULL. MÍi thành ph§n cça lÛp này Áu là private. Tuy nhiên, các lÛp LList và LListIterator c§n có kh£ nng truy c­p trñc tíêp ¿n các thành ph§n cça lÛp LNode. Do ó, chúng ta khai bào các lÛp LList và LListIterator là b¡n cça lÛp này. Ënh ngh)a lÛp LNode °ãc cho trong hình 5.11.

template <class Item>

class LList ; // khai báo tr°Ûc lÛp LList.

template <class Item>

class LListIterator ; // khai báo tr°Ûc.

template <class Item>

class LNode

{

LNode (const Item & value)

{ data = value ; next = NULL ; }

Item data ;

LNode * next ;

friend class LList<Item> ;

friend class LListIterator<Item> ;

} ;

Hình 5.11. LÛp LNode.

LÛp LList. LÛp này chéa ba thành ph§n dï liÇu: con trÏ Head trÏ tÛi §u DSLK, con trÏ Tail trÏ tÛi uôi cça DSLK, bi¿n length l°u Ù dài cça danh sách. LÛp LList chéa các hàm thành ph§n cing giÑng nh° trong lÛp Dlist (xem hình 4.3) vÛi mÙt vài thay Õi nhÏ. Chúng ta cing khai báo lÛp LListIterator là b¡n cça LList, à nó có thà truy c­p trñc ti¿p tÛi các thành ph§n dï liÇu cça lÛp LList. Ënh ngh)a là LList °ãc cho trong hình 5.12.

template <class Item>

class LListIterator ;

template <class Item>

class LList

{

friend class LListIterator <Item> ;

public :

LList( ) // khßi t¡o danh sách r×ng

{ Head = NULL; Tail = NULL ; length = 0 ; }

LList (const LList & L) ; // Hàm ki¿n t¡o copy

~ LList( ) ; // Hàm hu÷

LList & operator = (const LList & L); // Toán tí gán.

bool Empty( ) const

{ return length = = 0; }

int Length( ) const

{ return length ; }

void Insert(const Item & x, int i);

// xen ph§n tí x vào vË trí thé i trong danh sách.

void Append(const Item & x);

// xen ph§n tí x vào uôi danh sách.

void Delete(int i);

// lo¡i ph§n tí ß vË trí thé i trong danh sách.

Item & Element(int i);

// tr£ vÁ ph§n tí ß vË trí thé i trong danh sách.

private :

LNode <Item> * Head ;

LNode <Item> * Tail ;

int length ;

} ;

Hình 5.12. Ënh ngh)a lÛp LList.

Bây giÝ chúng ta xét sñ cài ·t các hàm thành ph§n cça lÛp LList. LÛp LList chéa các thành ph§n dï liÇu °ãc c¥p phát Ùng, vì v­y trong lÛp này, ngoài hàm ki¿n t¡o m·c Ënh khßi t¡o ra danh sách r×ng, °ãc cài ·t inline, chúng ta c§n ph£i °a vào hàm ki¿n t¡o copy, hàm hu÷ và toán tí gán. Sau ây chúng ta xét l§n l°ãt các hàm này.

Hàm ki¿n t¡o copy. Hàm này thñc hiÇn nhiÇm vå t¡o ra mÙt DSLK mÛi vÛi các con trÏ ngoài Head và Tail chéa các dï liÇu nh° trong DSLK ã cho vÛi con trÏ ngoài L.Head và L.Tail. N¿u DSLK ã cho không r×ng, §u tiên ta t¡o ra DSLK mÛi gÓm mÙt thành ph§n chéa dï liÇu nh° trong thành ph§n §u tiên cça DSLK ã cho, rÓi sau ó l§n l°ãt xen vào DSLK mÛi các thành ph§n chéa dï liÇu nh° trong các thành ph§n ti¿p theo cça DSLK ã cho. Có thà cài ·t hàm ki¿n t¡o copy nh° sau:

LList <Item> :: LList(const LList<Item> & L)

{

if (L.Empty( ))

{ Head = Tail = NULL ; length = 0 ; }

else {

Head = new LNode <Item> (L.Head ( data);

Tail = Head ;

LNode <Item> * P ;

for (P = L.Head ( next; P! = NULL ; P = P ( next)

Append (P ( data) ;

length = L.length ;

}

}

Hàm hu÷. Hàm này c§n thu hÓi t¥t c£ bÙ nhÛ ã c¥p phát cho các thành ph§n cça DSLK tr£ vÁ cho hÇ thÑng và ·t con trÏ Head và Tail là NULL. MuÑn v­y, chúng ta thu hÓi tëng thành ph§n kà të thành ph§n §u tiên cça DSLK. Hàm hu÷ °ãc cài ·t nh° sau:

LList <Item> :: ~ LList( )

{

if (Head ! = NULL)

{

LNode <Item> * P ;

while (Head ! = NULL)

{

P = Head ;

Head = Head ( next ;

delete P;

}

Tail = NULL ;

length = 0 ;

}

}

Toán tí gán. NhiÇm vå cça toán tí gán nh° sau: ta có mÙt Ñi t°ãng (°ãc trÏ bßi con trÏ this) chéa DSLK vÛi các con trÏ ngoài Head và Tail và mÙt Ñi t°ãng khác L chéa DSLK vÛi các con trÏ ngoài L.Head và L.Tail, phép gán c§n ph£i làm cho Ñi t°ãng *this chéa DSLK là b£n sao cça DSLK trong Ñi t°ãng L. à thñc hiÇn °ãc iÁu ó, §u tiên chúng ta c§n làm cho DSLK trong Ñi t°ãng *this trß thành r×ng (vÛi các hành Ùng nh° trong hàm hu÷), sau ó copy DSLK trong Ñi t°ãng L (giÑng nh° hàm ki¿n t¡o copy). Hàm operator = tr£ vÁ Ñi t°ãng *this. Cài ·t cå thà hàm toán tí gán à l¡i cho Ùc gi£, xem nh° bài t­p.

Sau ây chúng ta cài ·t các hàm thñc hiÇn các phép toán trên danh sách.

Hàm Append (xen mÙt ph§n tí mÛi x vào uôi danh sách). Hàm này r¥t ¡n gi£n, chÉ c§n sí dång thao tác xen mÙt thành ph§n mÛi chéa dï liÇu x vào uôi DSLK

void LList <Item> :: Append (const Item & x)

{

LNode <Item> * Q = new LNode <Item> (x) ;

if (Empty( ))

{ Head = Tail = Q ; }

else {

Tail ( next = Q ;

Tail = Q ;

}

length + + ;

}

Các hàm xen ph§n tí x vào vË trí thé i trong danh sách, lo¡i ph§n tí ß vË trí thé i khÏi danh sách và tìm ph§n tí ß vË trí thé i cça danh sách Áu có mÙt iÃm chung là c§n ph£i Ënh vË °ãc thành ph§n cça DSLK chéa ph§n tí thé i cça danh sách. Chúng ta s½ sí dång con trÏ P ch¡y trên DSLK b¯t §u të §u, i theo con trÏ next trong các thành ph§n cça DSLK, ¿n vË trí mong muÑn thì dëng l¡i. MÙt khi con trÏ P trÏ tÛi thành ph§n cça DSLK chéa ph§n tí thé i 1 cça danh sách, thì viÇc xen vào vË trí thé i cça danh sách ph§n tí mÛi x t°¡ng °¡ng vÛi viÇc xen vào DSLK mÙt thành ph§n mÛi chéa dï liÇu x sau thành ph§n °ãc trÏ bßi con trÏ P. ViÇc lo¡i khÏi danh sách ph§n tí ß vË trí thé i có ngh)a là lo¡i khÏi DSLK thành ph§n i sau thành ph§n °ãc trÏ bßi P. Các hàm xen và lo¡i °ãc cài ·t nh° sau:

Hàm Insert

template <class Item>

void LList<Item> :: Insert(const Item & x, int i)

{

assert ( i > = 1 && i < = length) ;

LNode <Item> * Q = new LNode<Item> (x) ;

if (i = = 1) // xen vào §u DSLK.

{

Q ( next = Head ;

Head = Q ;

}

else {

LNode <Item> * P = Head ;

for (int k = 1 ; k < i 1 ; k + + )

P = P ( next ;

Q ( next = P ( next ;

P ( next = Q ;

}

length + + ;

}

Hàm Delete

template <class Item>

void LList <Item> :: Delete (int i)

{

assert ( i > = 1 && i <= length) ;

LNode<Item> * P ;

If ( k = = 1) // Lo¡i §u DSLK

{

P = Head ;

Head = Head ( next ;

Delete P ;

if (Head = = NULL) Tail = NULL ;

}

else {

P = Head ;

for (int k = q ; k < i 1; k + +)

P = P ( next ;

LNode <Item> * Q ;

Q = P ( next ;

P (next = Q ( next ;

delete Q;

if ( P ( next = = NULL) Tail = P ;

}

length - - ;

}

Hàm tìm ph§n tí ß vË trí thé i

template <class Item>

Item & LList <Item> :: Element(int i)

{

assert ( i > = 1 && i < = length) ;

LNode <Item> * P = Head;

for (int k = 1 ; k < i ; k + +)

P = P ( next ;

return P ( data ;

}

Bây giÝ chúng ta cài ·t lÛp công cå l·p LListIterator. LÛp này chéa các hàm thành ph§n giÑng nh° các hàm thành ph§n trong lÛp DlistIterator (xem hình 4.4). LÛp LListIterator chéa mÙt con trÏ h±ng LlistPtr trÏ tÛi Ñi t°ãng cça lÛp LList, ngoài ra à cho các phép toán liên quan tÛi duyÇt DSLK °ãc thñc hiÇn thu­n tiÇn, chúng ta °a vào lÛp LListIterator hai bi¿n con trÏ: con trÏ current trÏ tÛi thành ph§n hiÇn thÝi, con trÏ pre trÏ tÛi thành ph§n éng tr°Ûc thành ph§n hiÇn thÝi trong DSLK thuÙc Ñi t°ãng mà con trÏ LListPtr trÏ tÛi. Ënh ngh)a lÛp LListIterator °ãc cho trong hình 5.12.

template <class Item>

class LListIterator

{

public :

LListIterator (const LList<Item> & L) // Hàm ki¿n t¡o.

{ LListPtr = & L; current = NULL ; pre = NULL; }

void Start( )

{ current = LListPtr (Head; pre = NULL: }

void Advance( )

{ assert (current ! = NULL); pre = current; current =

current ( next; }

bool Valid( )

{return current ! = NULL; }

Item & Current( )

{ assert (current! = NULL); return current ( data; }

void Add(const Item & x);

void Remove( );

private :

const LList<Item> * LlistPtr;

LNode<Item> * current;

LNode<Item> * pre ;

}

Hình 5.12. LÛp công cå l·p LListIterator.

Các hàm thành ph§n cça lÛp LListIterator Áu r¥t ¡n gi£n và °ãc cài ·t inline, trë ra hai hàm Add và Remove. Cài ·t hai hàm này cing ch³ng có gì khó khn c£, chúng ta chÉ c§n sí dång các phép toán xen, lo¡i trên DSLK ã trình bày trong måc 5.2.1. Các hàm này °ãc cài ·t nh° sau:

Hàm Add

template <class Item>

void LListIterator<Item> :: Add (const Item & x)

{

assert (current ! = NULL);

LNode <Item> * Q = new LNode<Item> (x);

if (current = = LListPtr ( Head)

{

Q ( next = LListPtr ( Head;

LListPtr (Head = Q;

pre = Q;

}

else {

Q (next = current;

pre ( next = Q;

pre = Q ;

}

LListPtr ( length + + ;

}

Hàm Remove

template <class Item>

void LListIterator<Item> :: Remove( )

{

assert (current ! = NULL);

if (current = = LListPtr ( Head)

{

LListPtr ( Head = current (next;

delete current ;

current = LListPtr (Head ;

if (LListPtr (Head = = NULL)

LListPtr ( Tail = NULL;

}

else {

pre ( next = current ( next;

delete current;

current = pre ( next;

if (current = = NULL)

LListPtr (Tail = pre;

}

LListPtr (length - - ;

}

5.5 SO SÁNH HAI PH¯ NG PHÁP CÀI ¶T DANH SÁCH

MÙt KDLTT có thà cài ·t bßi các ph°¡ng pháp khác nhau. Trong ch°¡ng 4, chúng ta ã nghiên céu cách cài ·t KDLTT danh sách bßi m£ng (m£ng t)nh ho·c m£ng Ùng). Måc 5.4 ã trình bày cách cài ·t danh sách bßi DSLK. Trong måc này chúng ta s½ phân tích ánh giá °u khuy¿t iÃm cça m×i ph°¡ng pháp. Dña vào sñ phân tích này, b¡n có thà °a ra quy¿t Ënh lña chÍn cách cài ·t nào cho phù hãp vÛi éng dång cça mình.

Cài ·t danh sách bßi m£ng là cách lña chÍn tñ nhiên hãp lý: các ph§n tí cça danh sách l§n l°ãt °ãc l°u trong các thành ph§n liên ti¿p cça m£ng, kà të §u m£ng. Gi£ sí b¡n cài ·t danh sách bßi m£ng t)nh có cá là MAX. N¿u MAX là sÑ r¥t lÛn, khi danh sách còn ít ph§n tí, thì c£ mÙt không gian nhÛ rÙng lÛn trong m£ng không sí dång ¿n, và do ó s½ lãng phí bÙ nhÛ. Khi danh sách phát triÃn, tÛi mÙt lúc nào ó nó có thà có sÑ ph§n tí v°ãt quá cá cça m£ng. ó là h¡n ch¿ c¡ b£n cça cách cài ·t danh sách bßi m£ng t)nh. Bây giÝ gi£ sí b¡n l°u danh sách trong m£ng Ùng. M×i khi m£ng §y, b¡n có thà c¥p phát mÙt m£ng Ùng mÛi có cá g¥p ôi m£ng Ùng ci. Nh°ng khi ó b¡n l¡i ph£i m¥t thÝi gian à sao chép dï liÇu të m£ng ci sang m£ng mÛi. Sñ lãng phí bÙ nhÛ v«n x£y ra khi mà danh sách thì ng¯n mà cá m£ng thì lÛn.

Trong cách cài ·t danh sách bßi DSLK, các ph§n tí cça danh sách °ãc l°u trong các thành ph§n cça DSLK, các thành ph§n này °ãc c¥p phát Ùng. DSLK có thà móc nÑi thêm các thành ph§n mÛi ho·c lo¡i bÏ các thành ph§n tr£ vÁ cho hÇ thÑng m×i khi c§n thi¿t. Do ó cài ·t danh sách bßi DSLK s½ ti¿t kiÇm °ãc bÙ nhÛ.

MÙt °u iÃm cça cài ·t danh sách bßi m£ng là ta có thà truy c­p trñc ti¿p tÛi m×i ph§n tí cça danh sách. N¿u ta cài ·t danh sách bßi m£ng A, thì ph§n tí thé i trong danh sách °ãc l°u trong thành ph§n A[i - 1] cça m£ng, do ó thÝi gian truy c­p tÛi ph§n tí b¥t kó cça danh sách là O(1). Vì v­y thÝi gian cça phép toán tìm ph§n tí thé i trong danh sách Element(i) là O(1), vÛi i b¥t kó.

Song n¿u chúng ta sí dång DSLK à cài ·t danh sách, thì chúng ta không có cách nào truy c­p trñc ti¿p tÛi thành ph§n cça DSLK chéa ph§n tí thé i cça danh sách. Chúng ta ph£i sí dång con trÏ P ch¡y trên DSLK b¯t §u të §u, l§n l°ãt qua các thành ph§n k¿ ti¿p à ¡t tÛi thành ph§n chéa ph§n tí thé i cça danh sách. Do v­y, thÝi gian à thñc hiÇn phép toán tìm ph§n tí thé i cça danh sách khi danh sách °ãc cài ·t bßi DSLK là phå thuÙc vào i và là O(i).

N¿u danh sách °ãc cài ·t bßi m£ng A, thì à xen mÙt ph§n tí mÛi vào vË trí thé i trong danh sách (ho·c lo¡i khÏi danh sách ph§n tí ß vË trí thé i), chúng ta ph£i ©y các ph§n tí cça danh sách chéa trong các thành ph§n cça m£ng kà të A[i] ra phía sau mÙt vË trí (ho·c ©y lên tr°Ûc mÙt vË trí các ph§n tí chéa trong các thành ph§n kà të A[i + 1]). Do ó, các phép toán Insert(x,i) và Delete(i) òi hÏi thÝi gian O(n i), trong ó n là Ù dài cça danh sách.

M·t khác, n¿u cài ·t danh sách bßi DSLK thì à thñc hiÇn phép toán xen, lo¡i ß vË trí thé i cça danh sách, chúng ta l¡i ph£i m¥t thÝi gian à Ënh vË thành ph§n cça DSLK chéa ph§n tí thé i cça danh sách (b±ng cách cho con trÏ P ch¡y të §u DSLK). Do ó, thÝi gian thñc hiÇn các phép toán xen, lo¡i là O(i).

ThÝi gian thñc hiÇn các phép toán danh sách trong hai cách cài ·t bßi m£ng và bßi DSLK °ãc cho trong b£ng sau, trong b£ng này n là Ù dài cça danh sách.

Phép toán Danh sách cài ·t bßi m£ng Danh sách cài t bßi DSLK Insert (x, i)

Delete (i)

Append (x)

Element (i)

Add (x)

Remove ( )

Current ( ) O(n i)

O(n i)

O(1)

O(1)

O(n)

O(n)

O(1)

O(i)

O(i)

O(1)

O(i)

O(1)

O(1)

O(1)

5.6 CÀI ¶T T¬P ØNG BÞI DSLK

Trong måc 4.4, chúng ta ã nghiên céu ph°¡ng pháp cài ·t t­p Ùng bßi m£ng. Þ ó lÛp t­p Ùng DSet ã °ãc cài ·t b±ng cách sí dång lÛp danh sách Ùng Dlist nh° lÛp c¡ sÏ private. °¡ng nhiên chúng ta cing có thà sí dång lÛp danh sách liên k¿t LList nh° lÛp c¡ sß private à cài ·t lÛp DSet. Song cài ·t nh° th¿ thì phép toán tìm ki¿m trên t­p Ùng s½ òi hÏi thÝi gian không ph£i là O(n) nh° khi sí dång lÛp DList. Hàm tìm ki¿m tu§n tñ trong lÛp DSet sí dång lÛp c¡ sß DList (xem måc 4.4) chéa dòng lÇnh:

for (int i = 1; i < = length( ); i + +)

if (Element (i). key = = k) return true;

Trong lÛp DList, thÝi gian cça phép toán Element(i) là O(1) vÛi mÍi i, do ó thÝi gian cça phép toán tìm ki¿m là O(n), vÛi n là Ù dài cça danh sách. Tuy nhiên trong lÛp LList, thÝi gian cça Element(i) là O(i), do ó thÝi gian cça phép toán tìm ki¿m trên t­p Ùng n¿u chúng ta cài ·t lÛp DSet b±ng cách sí dång lÛp LList làm lÛp c¡ sß private s½ là O(n2).

MÙt cách ti¿p c­n khác à cài ·t t­p Ùng bßi DSLK là chúng ta biÃu diÅn t­p Ùng bßi mÙt List vÛi List là mÙt Ñi t°ãng cça lÛp LList. LÛp DSet s½ chéa mÙt thành ph§n dï liÇu là List.

Cing nh° trong måc 4.4, chúng ta gi£ thi¿t r±ng t­p Ùng chéa các dï liÇu có kiÃu Item, và Item là mÙt c¥u trúc chéa mÙt thành ph§n là khoá (key) vÛi kiÃu là keyType. LÛp DSet °ãc Ënh ngh)a nh° sau:

template <class Item>

class DSet

{

public:

void DsetInsert (const Item & x);

void DsetDelete (keyType k) ;

bool Search (keyType k) const ;

Item & Max( ) const ;

Item & Min( ) const ;

private :

LList <Item> List;

};

Chú ý r±ng, lÛp DSet có các hàm sau ây °ãc tñ Ùng thëa h°ßng të lÛp LList:

Hàm ki¿n t¡o m·c Ënh tñ Ùng (hàm ki¿n t¡o copy tñ Ùng), nó kích ho¡t hàm ki¿n t¡o m·c Ënh (hàm copy, t°¡ng éng) cça lÛp LList à khßi t¡o Ñi t°ãng List.

Toán tí gán tñ Ùng, nó kích ho¡t toán tí gán cça lÛp LList.

Hàm hu÷ tñ Ùng, nó kích ho¡t hàm hu÷ cça lÛp LList.

Các phép toán t­p Ùng s½ °ãc cài ·t b±ng cách sí dång các phép toán bÙ công cå l·p à duyÇt DSLK List. Ch³ng h¡n, hàm tìm ki¿m °ãc cài ·t nh° sau:

template <class Item>

bool DSet<Item> :: Search(keyType k)

{

LListIterator<Item> It<List> ; // Khßi t¡o It là Ñi t°ãng cça lÛp

// công cå l·p, It g¯n vÛi List.

for (It.Start( ) ; It.Valid( ); It.Advance( ))

if (It.Current( ).key = = k)

return true;

return false;

}

Hàm lo¡i khÏi t­p Ùng dï liÇu vÛi khoá k °ãc cài ·t t°¡ng tñ: duyÇt DSLK List, khi g·p dï liÇu c§n lo¡i thì sí dång hàm Remove( ) trong bÙ công cå l·p.

template <class Item>

void DSet<Item> :: DsetDelete (keyType k)

{

LListIterator<Item> It(List);

for (It.Start( ); It.Valid( ); It.Advance( ))

if (It.Current( ).key = = k)

{ It.Remove( ) ; break); }

}

Hàm xen mÙt dï liÇu mÛi x vào t­p Ùng °ãc thñc hiÇn b±ng cách gÍi hàm Append trong lÛp LList à xen x vào uôi DSLK.

template <class Item>

void DSet<Item> :: DsetInsert(const Item & x)

{

if (! Search (x.key))

List.Append(x);

}

Các phép toán tìm ph§n tí có khoá lÛn nh¥t (hàm Max), tìm ph§n tí có khoá nhÏ nh¥t (hàm Min) Ã l¡i cho Ùc gi£ , xem nh° bài t­p.

Các phép toán trong bÙ công cå l·p chÉ c§n thÝi gian O(1), do ó vÛi cách cài ·t lÛp DSet nh° trên, t¥t c£ các phép toán trong t­p Ùng chÉ òi hÏi thÝi gian O(n), vÛi n là sÑ dï liÇu trong t­p Ùng.

Chú ý. Khi cài ·t t­p Ùng bßi DSLK chúng ta chÉ có thà tìm ki¿m tu§n tñ. Cho dù các dï liÇu cça t­p Ùng °ãc l°u trong DSLK l§n l°ãt theo giá trË khoá tng d§n, chúng ta cing không thà áp dång kù thu­t tìm ki¿m nhË phân, lý do ¡n gi£n là trong DSLK chúng ta không thà truy c­p trñc ti¿p tÛi thành ph§n ß giïa DSLK.

BÀI T¬P.

Cho DSLK ¡n vÛi con trÏ ngoài head trÏ tÛi §u DSLK, và P là con trÏ trÏ tÛi mÙt thành ph§n cça DSLK ó. Hãy vi¿t ra các m«u hàm và cài ·t các hàm thñc hiÇn các nhiÇm vå sau:

Xen thành ph§n mÛi chéa dï liÇu d vào tr°Ûc P.

Lo¡i thành ph§n P.

In ra t¥t c£ các dï liÇu trong DSLK.

Lo¡i khÏi DSLK t¥t c£ các thành ph§n chéa dï liÇu d.

Cho hai DSLK, hãy vi¿t hàm k¿t nÑi hai DSLK ó thành mÙt DSLK vòng tròn, ch³ng h¡n vÛi hai DSLK:

head 1 head 2

ta nh­n °ãc DSLK vòng tròn sau:

tail

Chú ý r±ng, mÙt trong ho·c c£ hai DSLK ã cho có thà r×ng.

Cho DSLK vòng tròn vÛi con trÏ ngoài tail trÏ tÛi uôi DSLK. Hãy cài ·t các hàm sau:

Xen thành ph§n mÛi chéa dï liÇu d vào uôi DSLK.

Xen thành ph§n mÛi chéa dï liÇu d vào §u DSLK.

Lo¡i thành ph§n ß §u DSLK.

Hãy cài ·t các hàm ki¿n t¡o copy, hàm hu÷, toán tí gán trong lÛp Dlist bßi các hàm Ç quy.

Hãy cài ·t lÛp Llist, trong ó danh sách °ãc cài ·t bßi DSLK vòng tròn vÛi mÙt con trÏ ngoài tail.

PAGE

PAGE 167

5

5

5

8

8

5

8

5

·

5

·

5

5

3.14

5

data next

5

8

3 · ·· · ·

5

8

3 ·

5

8

3 ·

value

value

value

5

8

3 ·

7

12

9

3 ·

4 12 3

· 5

3

8

·

5

3

8

4

a1

a2

an ·

a1

a2

an

3

7

5 (

3

9

5

9

3

7

3