Tài liệu Giáo trình c c++chuong 8 [compatibility mode]

CHÆÅNG VIII DANH SAÏCH MOÏC NÄÚI Ta thæång sæí duûng maíng cáúu truïc âãø xæí lyï våïi nhoïm dæî liãûu. Âáy laì mäüt caïch tiãúp cáûn âuïng khi ta biãút træåïc chênh xaïc säú caïc cáúu truïc cáön coï. Tuy nhiãn, khi con säú naìy khäng roî raìng, maîng seî tråí nãn khaï täún keïm vç chuïng phaíi âæåüc cáúp phaït âuí bäü nhåï âãø hoaût âäüng. Bäú nhåï naìy âæåüc âàng kyï vaì seî khäng daình cho nhæïng taïc vuû khaïc ngay caí khi ta chè duìng mäüt sä nhoí caïc pháön tæí maíng. Phæång hæåïng giaíi quyãút cho váún âãö naìy laì cho pheïp cáúp phaït bäü nhåï cho mäüt C cho pheïp ta thæûc hiãûn âiãöu naìy thäng qua caïhc cáúp phaït bäü nhåï âäüng bàòng: malloc() vaì calloc() Nhæng caïc cáúu truïc nãúu âæåüc cáúp phaïp xong seî khäng coï âaím baïo naìo ràòng caïc cáúu truïc seî âæåüc âàût liãn tiãúp nhau trong bäü nhåï. Do âoï âiãöu cáön thiãút laì kyî thuáût âãø näúi kãút táút caí caïc cáúu truïc laûi våïi nhau. Phæång caïch thäng duûng âãø kãút näúi caïc pháön tæí âoï laûi laì duìng danh saïch liãn kãút (Linked list) I. 1. Danh saïch liãn kãút âån: Âënh nghéa Cuï phaïp: struct { ; struct * } Vê duû: Âënh nghéa mäüt danh saïch liãn kãút âãø chæïa caïc säú nguyãn. struct Point { int info; struct Point *Next; }; 2. Caïc pheïp toaïn trãn danh saïch liãn kãút a. Cáúp phaït bä nhåï cho biãún con troí måïi Cuï phaïp: Point_New = (struct Point_Name *) malloc (sizeof(struct Point_Name) Vê duû: typedef struct Point POINT; POINT Head, Last, p; CreatNode() { p=(POINT *) malloc (POINT) if (Head==(POINT* ) NULL) Head=Last=p; else { Last=Head; while (Last->Next!= (POINT*) NULL) Last=Last->Next; Last->Next=p; Last=p; } printf(“\nInput information for Node”); scanf(“%d”, p->.info); Last->Next=(POINT *) NULL; return; } b. Xoaï mäüt con troí: Cuï phaïp: free(Point_Variable) Giaíi phoïng vuìng nhåï âæåüc troí båíi Point_Variable c. Caïc pheïp toaïn thæång duìng trong danh saïch liãn kãút Taûo mäüt pháön tæ cuía danh saïch Âiãöu phaíi laìm laì cáúp phaïp bäü nhåï cho cáúu truïc vaì traí vãö con troí troí âãún vuìng nhåï naìy. Vê duû: POINT *CreatNode() { POINT *p; p = (POINT *) malloc (sizeof(POINT)); if (p==NULL) { printf(“Malloc falled.\n”); exit(1); } printf(“Input data for Node info = ”); scanf(“%d”, p->info); p->Next = NULL return p; } Bäø sung pháön tæ vaìo danh saïch Haìm CreatNode() chè cáúp phaït bäü nhåï nhæng noï khäng näúi pháön tæí naìy vaìo danh saïch. Âãø laìm âiãöu naìy, ta cáön thãm mäüt haìm næîa, goüi laì haìm AddNode(). Âæåüc âënh nghéa nhæ sau: static POINT *Head; void AddNode(POINT *e) { POINT *p; if (Head ==NULL) { Head = e; return; } for (p=Head; p->Next!=NULL; p=p->Next); p->Next=e; } Chuï yï: Biãún Head laì con troí troí âãún âáöu danh saïch, nãn cáön âæåüc khai baïo âáöu chæång trçnh.(Sau pháön khai âënh nghéa kiãøu con troí). Cheìn pháön tæ vaìo danh saïch Âãø cheìn pháön tæí vaìo danh saïch liãn kãút, ta phaíi chè roí pháön tæí måïi seî âæåüc cheìn vaìo vë trê naìo.Sau âáy laì haìm seî thæûc hiãûn cäng viãûc trãn. void InsertNode(POINT *p, POINT *q) { if (p=NULL || q=NULL || p==q || q->Next ==p) { printf (“Cannot Insert \n”); return; } p->Next =q->Next; q->Next=p; }; Xoaï pháön tæ vaìo danh saïch Xoaï mäüt pháön tæí khoíi danh saïch liãn kãút âån, ta cáön phaíi tçm pháön tæí træåïc pháön tæí cáön xoaï âãø nhàòm muûc âêch näúi laûi våïi pháön tæí sau pháön tæí cáön xoaï. Ta duìng haìm free() âãø giaíi phäúng bäü nhåï chiãúm båíi pháön tæí bë xoaï. Coï thãø xáy dæng laì: void DeleteNode(POINT *goner) { POINT *p; p=Head; if (goner ==Head) Head = goner->Next; else { while (p!=NULL && p->Next!=goner) p=p->Next; if (p=NULL) { printf(“Cannot find Node \n”); return; } p->Next=p->Next->Next; }; free(goner) }; Tçm pháön tæ vaìo danh saïch Tháût khoï taûo mäüt haìm FindNode() täøng quaït, båíi vç khi tçm kiãúm thç ta phaíi dæûa vaìo mäüt trong nhæîng træåìng dæî liãûu cuía cáúu truïc, âiãöu naìy phuû thuäüc vaìo cáúu truïc dang sæí duûng. Âãø viãút haìm FindNode() täøng quaït ta phaíisæí duûng con troí troí âãún haìm. Våïi cáúu truïc trãn ta xáy dæûng haìm FindNode() nhæ sau: POINT *FindNode(int *n) { POINT *p; for (p=Head; p!=NULL; p=p->Next) if (p->Info=n) return p; return NULL; }; II. Danh saïch âa liãn kãút Âënh nghéa: Cuï phaïp: struct { ; struct *,; } Vê duû: Âënh nghéa mäüt danh saïch liãn kãút âãø chæïa caïc säú nguyãn. struct Point { int info; struct Point *Next,*Previous; }; III. STACK vaì QUEUE 1. STACK Laì danh saïch coï moïc näúi âàûc biãût. Màûc dáöu ta coï thãø thæûc hiãûm nhiãöu pheïp toaïn trãn danh saïch täøng quaït, Stack váùn coï nhæîng tênh cháút riãng biãût: chè cho pheïp thãm vaì xoaï boí caïc pháön tæí åí mäüt vë trê duy nháút, taûi âènh cuía Stack. Våïi âàûc træng nhæ váûy thç Stack coï kiãøu cáúu truïc dæî liãûu laì LIFO (Last In First Out) a. Khåíi taûo Stack Sæí duûng maíng: int stack[100], p; Stackinit() { p=0; } Sæí duûng danh saïch liãn kãút struct Node { int info; struct Node *Next; }; typedef struct Node NODE; NODE *Head, *p, *q; StackInit() { Head = (NODE *) malloc (sizeof *Head); p=(NODE *) malloc (sizeof *p); Head->Next=p; Head->info=0; p->Next=NULL; return 0; }