Cấu trúc dự liệu động

Caááu truùùc döõ lieõ ääu ñoääng Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 2 Muïïc tieâu⠄ Giôùùi thieääu khaùùi nieääm caááu truùùc döõ lieõ ääu ñoääng. „ Giôùùi thieääu danh saùùch lieân keâ áát: … Caùùc kieååu toåå chöùùc döõ lieõ ääu theo DSLK. … Danh saùùch lieân keâ áát ñôn: toåå chöùùc, caùùc thuaäät toaùùn, öùùng duïïng. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 3 Kieååu döõ lieõ ääu tónh „ Khaùùi nieääm: Moäät soáá ñoáái töôïïng döõ lieõ ääu khoâng thay thay â ñoååi ñöôïïc kích thöôùùc, caááu truùùc, … trong suoáát qua trình soááng. Caùùc ñoáái töôïïng döõ lieõ ääu thuoääc nhöõng kieõ ååu döõ lieõ ääu goïïi laøø kieååu döõ lieõ ääu lieääu tónh. „ Moäät soáá kieååu döõ lieõ ääu tónh: caùùc caááu truùùc döõ lieõ ääu ñöôïïc xaây â döïïng töøø caùùc kieååu cô sôûû nhö: kieååu thöïïc, kieååu nguyeân, kieâ ååu kyùù töïï ... hoaëëc töøø caùùc caááu truùùc ñôn giaûûn nhö maååu tin, taääp hôïïp, maûûng ... Î Caùùc ñoáái töôïïng döõ lieõ ääu ñöôïïc xaùùc ñònh thuoääc nhöõng kieõ ååu döõ lieõ ääu naøøy thöôøøng cöùùng ngaéét, goøø boùùÎ khoùù dieãn taã ûû ñöôïïc thöïïc teáá voáán sinh ñoääng, phong phuùù. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 4 Ví duïï thöïïc teáá „ Moâ taâ ûû, quaûûn lyùù moäät ñoáái töôïïng ‘con ngöôøøi’ caààn theåå hieään caùùc thoâng tin toâ áái thieååu nhö : … Hoïï teânâ … Soáá CMND … Thoâng tin veâ àà cha, meïï Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 5 Ví duïï thöïïc teáá „ Vieääc bieãu dieãn moã ã äät ñoáái töôïïng coùù nhieààu thaøønh phaààn thoâng â tin nhö treân coâ ùù theåå söûû duïïng kieååu baûûn ghi. Tuy nhieân, caâ ààn löu yùù cha, meïï cuûûa moäät ngöôøøi cuõng laõ øø caùùc ñoáái töôïïng kieååu NGUOI, do vaääy veàà nguyeân taâ ééc caààn phaûûi coùù ñònh nghóa nhö sau: typedef struct NGUOI{ char Hoten[30]; int So_CMND ; NGUOI Cha,Me; }; „ Nhöng vôùùi khai baùùo treân, caâ ùùc ngoân ngâ öõ laõ ääp trình gaëëp khoùù khaên trong vieê ääc caøøi ñaëët khoâng vâ öôïït qua ñöôïïc nhö xaùùc ñònh kích thöôùùc cuûûa ñoáái töôïïng kieååu NGUOI ? Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 6 CTDL tónh – Moäät soáá haïïn cheáá „ Moäät soáá ñoáái töôïïng döõ lieõ ääu trong chu kyøø soááng cuûûa noùù coùù theåå thay ñoååi veàà caááu truùùc, ñoää lôùùn, nhö danh saùùch caùùc hoïïc vieân â trong moäät lôùùp hoïïc coùù theåå taêng theâm, giaê â ûûm ñi ... Neááu duøøng nhöõng caõ ááu truùùc döõ lieõ ääu tónh ñaõ bieõ áát nhö maûûng ñeåå bieååu dieãn ã Î Nhöõng thao taõ ùùc phöùùc taïïp, keùùm töïï nhieân â Î chöông trình khoùù ñoïïc, khoùù baûûo trì vaøø nhaáát laøø khoùù coùù theåå söûû duïïng boää nhôùù moäät caùùch coùù hieääu quaûû. „ Döõ lieõ ääu tónh seõ chieõ áám vuøøng nhôùù ñaõ daõ øønh cho chuùùng suoáát quaùù trình hoaïït ñoääng cuûûa chöông trình Î söûû duïïng boää nhôùù keùùm hieääu quaûû. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 7 Höôùùng giaûûi quyeáát „ Caààn xaây dâ öïïng caááu truùùc döõ lieõ ääu ñaùùp öùùng ñöôïïc caùùc yeâu â caààu: … Linh ñoääng hôn. … Coùù theåå thay ñoååi kích thöôùùc, caááu truùùc trong suoáát thôøøi gian soááng. Î Caááu truùùc döõ lieõ ääu ñoääng. Kieååu döõ lieõ ääu Con troûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 9 Bieáán khoâng â ñoääng Bieáán khoâng â ñoääng (bieáán tónh, bieáán nöûûa tónh) laøø nhöõng bieõ áán thoûûa: „ Ñöôïïc khai baùùo töôøøng minh, „ Toààn taïïi khi vaøøo phaïïm vi khai baùùo vaøø chæ maáát khi ra khoûûi phaïïm vi naøøy, „ Ñöôïïc caááp phaùùt vuøøng nhôùù trong vuøøng döõ lieõ ääu (Data segment) hoaëëc laøø Stack (ñoáái vôùùi bieáán nöûûa tónh - caùùc bieáán cuïïc boää). „ Kích thöôùùc khoâng thay â ñoååi trong suoáát quaùù trình soááng. „ Do ñöôïïc khai baùùo töôøøng minh, caùùc bieáán khoâng â ñoääng coùù moäät ñònh danh ñaõ õ ñöôïïc keáát noáái vôùùi ñòa chæ vuøøng nhôùù löu tröõ bieõ áán vaøø ñöôïïc truy xuaáát tröïïc tieááp thoâng qua â ñònh danh ñoùù. „ Ví duïï : int a; // a, b laø caùc bieán khoâng ñoäng char b[10]; Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 10 Kieååu döõ lieõ ääu Con troûû „ Cho tröôùùc kieååu döõ lieõ ääu T = . „ Kieååu con troûû - kyùù hieääu “Tp”- chæ ñeáán caùùc phaààn töûû coùù kieååu “T” ñöôïïc ñònh nghóa: Tp = , trong ñoùù: … Vp = {{caùùc ñiaïï chæ coùù theåå löu tröõ nhõ öõng õ ñoáái töôïïng coùù kieååu T}, NULL} (vôùùi NULL laøø moäät giaùù trò ñaëëc bieäät töôïïng tröng cho moäät giaùù trò khoâng bieâ áát hoaëëc khoâng â quan taâm)â … Op = {caùùc thao taùùc ñònh ñòa chæ cuûûa moäät ñoáái töôïïng thuoääc kieååu T khi bieáát con troûû chæ ñeáán ñoáái töôïïng ñoùù} (thöôøøng goààm caùùc thao taùùc taïïo moäät con troûû chæ ñeáán moäät ñoáái töôïïng thuoääc kieååu T; huûûy moäät ñoáái töôïïng döõ lieõ ääu thuoääc kieååu T khi bieáát con troûû chæ ñeáán ñoáái töôïïng ñoùù). Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 11 Kieååu döõ lieõ ääu Con troûû „ Kieååu con troûû laøø kieååu cô sôûû duøøng löu ñòa chæ cuûûa moäät ñoáái töôïïng döõ lieõ ääu khaùùc. „ Bieáán thuoääc kieååu con troûû Tp laøø bieáán maøø giaùù trò cuûûa noùù laøø ñòa chæ cuaûû moäät vuøøng nhôùù öùùng vôùùi moäät bieáán kieååu T, hoaëëc laøø giaùù trò NULL. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 12 Kieååu döõ lieõ ääu Con troûû „ Kích thöôùùc cuûûa bieáán con troûû tuøøy thuoääc vaøøo quy öôùùc soáá byte ñòa chæ trong töøøng moâ hâ ình boää nhôùù cuûûa töøøng ngoân â ngöõ laõ ääp trình cuïï theåå. „ Ví duïï: … Bieáán con troûû trong Pascal coùù kích thöôùùc 4 bytes (2 bytes ñòa chæ segment + 2 byte ñòa chæ offset) … Bieáán con troûû trong C coùù kích thöôùùc 2 hoaëëc 4 bytes tuøøy vaøøo con troûû near (chæ löu ñòa chæ offset) hay far (löu caûû segment laãn offset)ã Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 13 Con troûû – Khai baùùo „ Cuùù phaùùp ñònh nghóa moäät kieååu con troûû trong ngoân ngâ öõ C :õ typedef * ; „ Ví duïï : typedef int *intpointer; intpointer p; hoaëëc int *p; laøø nhöõng khai baõ ùùo hôïïp leää. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 14 Con troûû – Thao taùùc caên baê ûûn „ Caùùc thao taùùc cô baûûn treân kieâ ååu con troûû:(minh hoïïa baèèng C) … Khi 1 bieáán con troûû p löu ñòa chæ cuûûa ñoáái töôïïng x, ta noùùi ‘p troûû ñeáán x’. … Gaùùn ñòa chæ cuûûa moäät vuøøng nhôùù con troûû p: p = ; p = + ;â … Truy xuaáát noääi dung cuûûa ñoáái töôïïng do p troûû ñeáán (*p) Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 15 Bieáán ñoääng „ Trong nhieààu tröôøøng hôïïp, taïïi thôøøi ñieååm bieân dòch khoâng â â theåå xaùùc ñònh tröôùùc kích thöôùùc chính xaùùc cuûûa moäät soáá ñoáái töôïïng döõ lieõ ääu do söïï toààn taïïi vaøø taêng trê öôûûng cuûûa chuùùng phuïï thuoääc vaøøo ngöõ caõ ûûnh cuûûa vieääc thöïïc hieään chöông trình. „ Caùùc ñoáái töôïïng döõ lieõ ääu coùù ñaëëc ñieååm keåå treân neân â â ñöôïïc khai baùùo nhö bieáán ñoääng. Bieáán ñoääng laøø nhöõng bieõ áán thoûûa: … Bieáán khoâng â ñöôïïc khai baùùo töôøøng minh. … Coùù theåå ñöôïïc caááp phaùùt hoaëëc giaûûi phoùùng boää nhôùù khi ngöôøøi söûû duïïng yeâu caâ ààu. … Caùùc bieáán naøøy khoâng theo qui taâ ééc phaïïm vi (tónh). … Vuøøng nhôùù cuûûa bieáán ñöôïïc caááp phaùùt trong Heap. … Kích thöôùùc coùù theåå thay ñoååi trong quaùù trình soááng. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 16 Bieáán ñoääng „ Do khoângâ ñöôïïc khai baùùo töôøøng minh neânâ caùùc bieáán ñoääng khoângâ coùù moäät ñònh danh ñöôïïc keáát buoääc vôùùi ñòa chæ vuøøng nhôùù caááp phaùùt cho noùù, do ñoùù gaëëp khoùù khaênê khi truy xuaáát ñeáán moäät bieáán ñoääng. „ Ñeåå giaûûi quyeáát vaáán ñeàà, bieáán con troûû (laøø bieáán khoângâ ñoääng) ñöôïïc söûû duïïng ñeåå troûû ñeáán bieáán ñoääng. „ Khi taïïo ra moäät bieáán ñoääng, phaûûi duøøng moäät con troûû ñeåå löu ñòa chæ cuûûa bieáán naøøy vaøø sau ñoùù, truy xuaáát ñeáán bieáán ñoääng thoângâ qua bieáán con troûû ñaõõ bieáát ñònh danh. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 17 Bieáán ñoääng „ Hai thao taùùc cô baûûn treânâ bieáán ñoääng laøø taïïo vaøø huûûy moäät bieáán ñoääng do bieáán con troûû ‘p’ troûû ñeáán: … Taïïo ra moäät bieáán ñoääng vaøø cho con troûû ‘p’ chæ ñeáán noùù … Huûûy moäät bieáán ñoääng do p chæ ñeáán Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 18 Bieáán ñoääng „ Taïïo ra moäät bieáán ñoääng vaøø cho con troûû ‘p’ chæ ñeáán noùù void* malloc(size); // traûû veàà con troûû chæ ñeáán vuøøng nhôùù // size byte vöøøa ñöôïïc caááp phaùùt. void* calloc(n,size);// traûû veàà con troûû chæ ñeáán vuøøng nhôùù // vöøøa ñöôïïc caááp phaùùt goààm n phaààn töûû, // moãiã phaààn töûû coùù kích thöôùùc size byte new // toaùùn töûû caááp phaùùt boää nhôùù trong C++ „ Haøøm free(p) huyûû vuøøng nhôùù caááp phaùùt bôûûi haøøm malloc hoaëëc calloc do p troûû tôùùi „ Toaùùn töûû delete p huyûû vuøøng nhôùù caááp phaùùt bôûûi toaùùn töûû new do p troûû tôùùi Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 19 Bieáán ñoääng – Ví duïï int *p1, *p2; // caáp phaùt vuøng nhôù cho 1 bieán ñoäng kieåu int p1 = (int*)malloc(sizeof(int)); *p1 = 5; // ñaët giaù trò 5 cho bieán ñoäng ñang ñöôïc p1 quaûn lyù // caáp phaùt bieán ñoäng kieåu maûng goàm 10 phaàn töû kieåu int p2 = (int*)calloc(10, sizeof(int)); *(p2+3) = 0; // ñaët giaù trò 0 cho phaàn töû thöù 4 cuûa maûng p2 free(p1); free(p2); Danh saùùch lieânâ keáát (List) Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 21 Danh saùùch lieânâ keáát (List) Ñònh nghóa „ Ñònh nghóa: … Cho T laøø moäät kieååu ñöôïïc ñònh nghiaõõ tröôùùc, kieååu danh saùùch Tx goààm caùùc phaààn töûû thuoääc kieååu T ñöôïïc ñònh nghóa laøø: Tx = trong ñoùù: … Vx = {Taääp hôïïp coùù thöùù töïï caùùc phaààn töûû kieååu T ñöôïïc moùùc noáái vôùùi nhau theo trình töïï tuyeáán tính}; … Ox = {Taïïo danh saùùch; Tìm 1 phaààn töûû trong danh saùùch; Cheøøn 1 phaààn töûû vaøøo danh saùùch; Huyûû 1 phaààn töûû khoûûi danh saùùch ; Lieäät keââ danh saùùch, Saéép xeááp danh saùùch ...} Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 22 Danh saùùch lieânâ keáát (List) Ñònh nghóa „ Ví dụ: Hoàà sô caùùc hoïïc sinh cuûûa moäät tröôøøng ñöôïïc toåå chöùùc thaøønh danh saùùch goààm nhieààu hoàà sô cuûûa töøøng hoïïc sinh; soáá löôïïng hoïïc sinh trong tröôøøng coùù theåå thay ñoååi do vaääy caààn coùù caùùc thao taùùc theâmâ , huûûy moäät hoàà sô; ñeåå phuïïc vuïï coângâ taùùc giaùùo vuïï caààn thöïïc hieään caùùc thao taùùc tìm hoàà sô cuûûa moäät hoïïc sinh, in danh saùùch hoàà sô ... Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 23 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Caùùc hình thöùùc toåå chöùùc danh saùùch: …Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään ngaààm …Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään töôøøng minh Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 24 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään ngaààm: …Moãiã phaààn töûû trong danh saùùch ñöôïïc ñaëëc tröng baèèng chæ soáá. … Caëëp phaààn töûû xi, xi+1 ñöôïïc xaùùc ñònh laøø keáá caään trong danh saùùch nhôøø vaøøo quan heää giöõaõ caëëp chæ soáá i vaøø (i+1). … Caùùc phaààn töûû cuûûa danh saùùch thöôøøng baéét buoääc phaûûi löu tröõõ lieânâ tieááp trong boää nhôùù ñeåå coùù theåå xaâyâ döïïng coângâ thöùùc xaùùc ñònh ñòa chæ phaààn töûû thöùù i address(i) = address(1) + (i-1)*sizeof(T) … Coùù theåå xem maûûng vaøø taääp tin laøø nhöõngõ danh saùùch ñaëëc bieäät ñöôïïc toåå chöùùc theo hình thöùùc lieânâ keáát “ngaààm” giöõaõ caùùc phaààn töûû. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 25 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään ngaààm: … Cho pheùùp truy xuaáát ngaãuã nhieânâ , ñôn giaûûn vaøø nhanh choùùng ñeáán moäät phaààn töûû baáát kyøø trong danh saùùch … Haïïn cheáá veàà maëët söûû duïïng boää nhôùù. … Ñoáái vôùùi maûûng, soáá phaààn töûû ñöôïïc xaùùc ñònh trong thôøøi gian bieânâ dòch vaøø caààn caááp phaùùt vuøøng nhôùù lieânâ tuïïc. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 26 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään ngaààm: … Trong tröôøøng hôïïp toåång kích thöôùùc boää nhôùù troááng coøøn ñuûû ñeåå chöùùa toaøøn boää maûûng nhöng caùùc oââ nhôùù troááng laïïi khoângâ naèèm keáá caään nhau thì cuõngõ khoângâ caááp phaùùt vuøøng nhôùù cho maûûng ñöôïïc. … Ngoaøøi ra do kích thöôùùc maûûng coáá ñònh maøø soáá phaààn töûû cuûûa danh saùùch laïïi khoùù döïï truøø chính xaùùc neânâ coùù theåå gaâyâ ra tình traïïng thieááu huïït hay laõngõ phí boää nhôùù. … Caùùc thao taùùc theâmâ , huûûy moäät phaààn töûû vaøøo danh saùùch ñöôïïc thöïïc hieään khoângâ töïï nhieânâ trong hình thöùùc toåå chöùùc naøøy. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 27 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään töôøøng minh …Moãiã phaààn töûû ngoaøøi caùùc thoângâ tin veàà baûûn thaânâ coøøn chöùùa moäät lieânâ keáát (ñòa chæ) ñeáán phaààn töûû keáá trong danh saùùch neânâ coøøn ñöôïïc goïïi laøø danh saùùch moùùc noáái. … Do lieânâ keáát töôøøng minh, vôùùi hình thöùùc naøøy caùùc phaààn töûû trong danh saùùch khoângâ caààn phaûûi löu tröõõ keáá caään trong boää nhôùù … Khaééc phuïïc ñöôïïc caùùc khuyeáát ñieååm cuûûa hình thöùùc toåå chöùùc maûûng … Vieääc truy xuaáát ñeáán moäät phaààn töûû ñoøøi hoûûi phaûûi thöïïc hieään truy xuaáát qua moäät soáá phaààn töûû khaùùc. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 28 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Moáái lieânâ heää giöõaõ caùùc phaààn töûû ñöôïïc theåå hieään töôøøng minh … Coùù nhieààu kieååu toåå chöùùc lieânâ keáát giöõaõ caùùc phaààn töûû trong danh saùùch nhö : „ Danh saùùch lieânâ keáát ñôn „ Danh saùùch lieânâ keáát keùùp „ Danh saùùch lieânâ keáát voøøng „… Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 29 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Danh saùùch lieânâ keáát ñôn: moãiã phaààn töûû lieânâ keáát vôùùi phaààn töûû ñöùùng sau noùù trong danh saùùch: „ Danh saùùch lieânâ keáát keùùp: moãiã phaààn töûû lieânâ keáát vôùùi caùùc phaààn töûû ñöùùng tröôùùc vaøø sau noùù trong danh saùùch: A B X Z Y A B C D Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 30 Danh saùùch lieânâ keáát (List) Caùùc hình thöùùc toåå chöùùc danh saùùch „ Danh saùùch lieânâ keáát voøøng : phaààn töûû cuoáái danh saùùch lieânâ keáát vôùùi phaààn töûû ñaààu danh saùùch: A B X Z Y A B C D Danh saùùch ñôn - SList (xaâuâ ñôn) Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 32 Moãiã phaààn töûû cuûûa danh saùùch ñôn gồm 2 thaøønh phaààn : … Thaøønh phaààn döõõ lieääu: löu tröõõ caùùc thoângâ tin veàà baûûn thaânâ phaààn töûû . … Thaøønh phaààn moáái lieânâ keáát: löu tröõõ ñòa chæ cuûûa phaààn töûû keáá tieááp trong danh saùùch, hoaëëc löu tröõõ giaùù trò NULL neááu laøø phaààn töûû cuoáái danh saùùch. typedef struct NODE { Data Info; // Data laø kieåu ñaõ ñònh nghóa tröôùc struct NODE * pNext; //con troû chæ ñeán caáu truùc NODE }; SList – Toåå chöùùc 1 phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 33 „ Ví duïï : Ñònh nghóa moäät phaààn töûû trong danh saùùch ñôn löu tröõõ hoàà sô sinh vieânâ : typedef struct SV { char Ten[30]; int MaSV; }; typedef struct SVNode { SV Info; struct SVNode * pNext; }; SList – Toåå chöùùc 1 phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 34 „ Moäät phaààn töûû trong danh saùùch ñôn laøø moäät bieáán ñoääng seõõ ñöôïïc yeâuâ caààu caááp phaùùt khi caààn. Vaøø danh saùùch ñôn chính laøø söïï lieânâ keáát caùùc bieáán ñoääng naøøy vôùùi nhau do vaääy ñaïït ñöôïïc söïï linh ñoääng khi thay ñoååi soáá löôïïng caùùc phaààn töûû SList – Toåå chöùùc, quaûûn lyùù Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 35 SList – Toåå chöùùc, quaûûn lyùù „ Ñeåå quaûûn lyùù moäät xaâuâ ñôn chæ caààn bieáát ñòa chæ phaààn töûû ñaààu xaâuâ . „ Con troûû Head seõõ ñöôïïc duøøng ñeåå löu tröõõ ñòa chæ phaààn töûû ñaààu xaâuâ , ta goïïi Head laøø ñaààu xaâuâ . Ta coùù khai baùùo: NODE* pHead; „ Ñeåå tieään lôïïi, coùù theåå söûû duïïng theâmâ moäät con troûû pTail giöõõ ñòa chæ phaààn töûû cuoáái xaâuâ . Khai baùùo pTail nhö sau : NODE* pTail; A B X Z Y pHead pTail Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 36 Khai baùùo kieååu cuûûa 1 phaààn töûû vaøø kieååu danh saùùch lieânâ keáát ñôn: // kieåu cuûa moät phaàn töû trong danh saùch typedef struct NODE { Data Info; struct NODE * pNext; }; typedef struct SLIST // kieåu danh saùch lieân keát { NODE* pHead; NODE* pTail; }; SList – Toåå chöùùc, quaûûn lyùù Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 37 „ Thuûû tuïïc GetNode ñeåå taïïo ra moäät phaààn töûû cho danh saùùch vôùùi thoângâ tin chöùùa trong x NODE* GetNode(Data x) { NODE *p; // Caáp phaùt vuøng nhôù cho phaàn töû p = new NODE; if (p==NULL) { printf("Khoâng ñuû boä nhôù"); return NULL; } p->Info = x; // Gaùn thoâng tin cho phaàn töû p p->pNext = NULL; return p; } SList – Taïïo moäät phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 38 Ñeåå taïïo moäät phaààn töûû môùùi cho danh saùùch, caààn thöïïc hieään caâuâ leäänh: new_ele = GetNode(x); Æ new_ele seõõ quaûûn lyùù ñòa chæ cuûûa phaààn töûû môùùi ñöôïïc taïïo. SList – Taïïo moäät phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 39 „ Taïïo danh saùùch roãng㠄 Theâmâ moäät phaààn töûû vaøøo danh saùùch „ Tìm kieáám moäät giaùù trò treânâ danh saùùch „ Trích moäät phaààn töûû ra khoûûi danh saùùch „ Duyeäät danh saùùch „ Sắp xeááp danh saùùch „ Huûûy toaøøn boää danh saùùch SList – Caùùc thao taùùc cô sôûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 40 void Init(SLIST &l) { l.pHead = l.pTail = NULL; } SList – Khôûûi taïïo danh saùùch roãngã pHead pTail Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 41 3 vò trí theâmâ phaààn töûû môùùi vaøøo danh saùùch: … Theâmâ vaøøo ñaààu danh saùùch … Noáái vaøøo cuoáái danh saùùch … Cheøøn vaøøo danh saùùch sau moäät phaààn töûû q SList – Theâmâ moäät phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 42 pHead pTail X new_ele SList – Theâmâ moäät phaààn töûû Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 43 A B C D E pHead pTail SList – Theâmâ moäät phaààn töûû vaøøo ñaààu X new_ele Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 44 //input: danh saùùch (head, tail), phaààn töûû môùùi new_ele //output: danh saùùch (head, tail) vôùùi new_ele ôûû ñaààu DS „ Neááu Danh saùùch roãngã Thì … Head = new_ele; … Tail = Head; „ Ngöôïïc laïïi … new_ele ->pNext = Head; … Head = new_ele ; SList – Theâmâ moäät phaààn töûû vaøøo ñaààu Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 45 void AddFirst(SLIST &l, NODE* new_ele) { if (l.pHead == NULL) //Xaâu roãng l.pHead = l.pTail = new_ele; else { new_ele->pNext = l.pHead; l.pHead = new_ele; } } SList – Theâmâ moäät phaààn töûû vaøøo ñaààu Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 46 //input: danh saùùch (head, tail), thaøønh phaààn döõõ lieääu X //output: danh saùùch (head, tail) vôùùi phaààn töûû chöùùa X ôûû ñaààu DS „ Taïïo phaààn töûû môùùi new_ele ñeåå chöùùa döõõ lieääu X „ Neááu taïïo ñöôïïc: Theâmâ new_ele vaøøo ñaààu danh saùùch „ Ngöôïïc laïïi Baùùo loãiã SList Theâmâ moäät thaøønh phaààn döõõ lieääu vaøøo ñaààu Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 47 NODE* InsertHead(SLIST &l, Data x) { NODE* new_ele = GetNode(x); if (new