C語言 表、棧和隊(duì)列詳解
表ADT
形如A1,A2,A3…An的表，這個表的大小為n，而大小為0的表稱為空表，非空表中，Ai+1后繼Ai，Ai-1前驅(qū)Ai，表ADT的相關(guān)操有PrintList打印表中的元素；CreateEmpty創(chuàng)建一個空表；Find返回關(guān)鍵字首次出現(xiàn)的位置；Insert和Delete從表的某個位置插入和刪除某個關(guān)鍵字。
對表的所有操作都可以通過使用數(shù)組來實(shí)現(xiàn)，但在這里使用鏈表的方式來實(shí)現(xiàn)。鏈表（linked list）由一系列不必在內(nèi)存中相連的結(jié)構(gòu)組成，每個結(jié)構(gòu)均含有元素和指向包含該元素后繼元的結(jié)構(gòu)的指針。鏈表的結(jié)構(gòu)有很多種，單向鏈表、雙向鏈表、循環(huán)鏈表、有無表頭的鏈表，這里以有表頭結(jié)點(diǎn)的單向鏈表為例，其余幾種的實(shí)現(xiàn)思路相同。
首先定義鏈表的結(jié)構(gòu)：
struct Node { ElementType Element; Node *Next; }; 表ADT的主要操作：
Node *CreateEmpty() { Node *header = new Node; Header->Element = 0; Header->Next = NULL; return header; } void PrintList(Node *List) { Node *p = List->Next; While (p) { std::cout << p->Element << “ “; } } Node *Find(Node *List, ElementType X) { Node *p = List->Next; while(p && p->Element != X) { p = p->Next; } return p; } void Insert(Node *List, ElementType X) { Node *p = List; while(p->Next) { p = p->Next; } p->Next = new Node; p = p->Next; p->Next = NULL; p->Element = X; } void Delete(Node *List, ElementType X) { Node *p = List->Next; Node *d = p->Next; while(d->Element != X) { p = p->Next; d = p->Next; } p->Next = d->Next; delete d; } 以上是基本的幾個操作，可以看到，操作中沒有對鏈表是否為空進(jìn)行檢測，在刪除操作中存在隱患。
棧ADT
棧（stack）是限制插入和刪除只能在一個位置上進(jìn)行的表，該位置是表的末端，叫做棧的頂（top）。對棧的基本操作有Push（進(jìn)棧）和Pop（出棧），前者相當(dāng)于插入，后者相當(dāng)于刪除最后插入的元素。
棧的實(shí)現(xiàn)可以是指針，或者使用數(shù)組，數(shù)組的實(shí)現(xiàn)在筆者前面的已經(jīng)介紹過了，今次使用單鏈表的方式實(shí)現(xiàn)。
首先，棧的結(jié)構(gòu)定義：
struct Stack { ElementType Element; Stack *Next; }; 棧ADT的主要操作：
Stack *CreateStack() { Stack *S = new Stack; S->Next = NULL; return S; } void Push(Stack *S, ElementType X) { Stack *p = new Stack; p->Next = S; S->Element = X; S = p; } ElementType Pop(Stack *S) { Stack *p = S; if(S->Next) { S = S->Next; delete p; } return S->Element; } 隊(duì)列ADT
像棧一樣，隊(duì)列也是一種表，然而，使用隊(duì)列時插入在一端進(jìn)行而刪除則在另一端進(jìn)行。隊(duì)列的基本操作時Enqueue（入隊(duì)）和Dequeue（出隊(duì)），入隊(duì)是指在表的末端rear插入一個元素，而出隊(duì)是刪除（或者返回）在表的開頭front的元素。
如同棧的情形一樣，棧的實(shí)現(xiàn)可以用指針和數(shù)組的方式，數(shù)組的方式筆者同樣在之前做過介紹，今次使用單鏈表的方式實(shí)現(xiàn)。
首先，定義隊(duì)列的結(jié)構(gòu)：
struct Queue { ElementType Element; Queue *Next; }; 隊(duì)列ADT的主要操作：
Queue *CreateQueue() { Queue *p = new Queue; p->Next = NULL; return p; } void Enqueue(Queue *rear, ElementType X) { Queue *p = new Queue; p->Element = X; rear->Next = p; rear = p; } ElementType Dequeue(Queue *front) { Queue *p = front; ElementType e = front->Element; front = front->Next; delete p; return e; } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點(diǎn)
疑難解答
圖片精選
