Bài giảng Công nghệ thông tin - Chương VIII: Danh sách móc nối

Nội dung text: Bài giảng Công nghệ thông tin - Chương VIII: Danh sách móc nối

1. 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áúu truïc måïi khi cáön thiãút.
2. 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)
3. I. Danh saïch liãn kãút âån: 1. Âë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.
4. 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)
5. 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;
6. 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; }
7. 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 FTaû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û:
8. 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; }
9. FBäø 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; }
10. 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í). FCheì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.
11. 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; };
12. FXoaï 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;
13. 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) };
14. FTç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:
15. POINT *FindNode(int *n) { POINT *p; for (p=Head; p!=NULL; p=p->Next) if (p->Info=n) return p; return NULL; };
16. II. Danh saïch âa liãn kãút Âënh nghéa: Cuï phaïp: struct { ; struct * , ; }
17. 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; };
18. 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)
19. 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; };
20. 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; }
21. b. Âáøy dæî liãûu vaìo Stack Sæí duûng maíng: Push (int x) { stack[p++]=x; } Sæí duûng danh saïch liãn kãút:
22. Push(int a) { q=(NODE *) malloc (sizeof *q); q->info=a; q->Next=Head->Next; Head->Next=q; return 0; } c. Láúy giaï trë ra khoíi Stack Sæí duûng maíng: Pop (int x) { return stack[p ]; }
23. Sæí duûng danh saïch liãn kãút: Pop() { int x; q=Head->Next; Head->Next=q->Next; x=q->info; free(q); return x; }
24. d. Kiãøm tra Stack räùng Sæí duûng maíng: int stackempty() { return !p; } Sæí duûng danh saïch liãn kãút: int StackEmpty() { return Head->Next==p; }
25. Vê duû: Xáy dæûng stack bàòng danh saïch liãn kãt: #include "stdio.h" #include "alloc.h" #define ESC 27 struct Node { int info; struct Node *Next; }; typedef struct Node NODE; NODE *Head, *p, *q;
26. StackInit() { Head = (NODE *) malloc (sizeof *Head); p=(NODE *) malloc (sizeof *p); Head->Next=p; Head->info=0; p->Next=NULL; return 0; }
27. Push(int a) { q=(NODE *) malloc (sizeof *q); q->info=a; q->Next=Head->Next; Head->Next=q; return 0; }
28. Pop() { int x; q=Head->Next; Head->Next=q->Next; x=q->info; free(q); return x; } int StackEmpty() { return Head->Next==p; }
29. void main() { int b; char c; StackInit(); do { clrscr(); printf("\nNhap gia tri vao Stack "); scanf("%d",&b); Push(b);
30. printf("\nAn Enter de tiep tuc/ESC de thoi nhap"); c=getchar(); c=getch(); } while(c!=ESC); printf("\nCac gia tri trong Stack\n"); while (!StackEmpty()) printf("%d ",Pop()); printf("\nAn ESC de ket thuc"); getch(); }
31. 2. Queue Queue hay coìn goüi laì haìng âåüi, âáy laì mäüt kiãøu danh saïch âàûc biãût. Caïc pháön tæí âæåüc thãm vaìo tæì mäüt âáöu, âæåüc goüi laì âáöu sau, vaì láúy ra mäüt âáöu khaïc, âæåüc goüilaì âáöu træåïc. Cáúu truïc naìy âæåüc sæí duûng trong caïc tçnh huäúng láûp trçnh cáön xæí lyï mäüt daîy caïc pháön tæí theo mäüt tráût tæû cäú âënh. Viãûc xæí lyï naìy goüi laì FIFO (First Int First Out).