C語言 表、棧和隊列詳解及實例代碼。本站提示廣大學習愛好者：（C語言 表、棧和隊列詳解及實例代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是C語言 表、棧和隊列詳解及實例代碼正文
C語言 表、棧和隊列詳解
表ADT
形如A1,A2,A3…An的表，這個表的大小為n，而大小為0的表稱為空表，非空表中，Ai+1後繼Ai，Ai-1前驅Ai，表ADT的相關操有PrintList打印表中的元素；CreateEmpty創建一個空表；Find返回關鍵字首次出現的位置；Insert和Delete從表的某個位置插入和刪除某個關鍵字。
對表的所有操作都可以通過使用數組來實現，但在這裡使用鏈表的方式來實現。鏈表（linked list）由一系列不必在內存中相連的結構組成，每個結構均含有元素和指向包含該元素後繼元的結構的指針。鏈表的結構有很多種，單向鏈表、雙向鏈表、循環鏈表、有無表頭的鏈表，這裡以有表頭結點的單向鏈表為例，其余幾種的實現思路相同。
首先定義鏈表的結構：
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;
}
以上是基本的幾個操作，可以看到，操作中沒有對鏈表是否為空進行檢測，在刪除操作中存在隱患。
棧ADT
棧（stack）是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧的頂（top）。對棧的基本操作有Push（進棧）和Pop（出棧），前者相當於插入，後者相當於刪除最後插入的元素。
棧的實現可以是指針，或者使用數組，數組的實現在筆者前面的已經介紹過了，今次使用單鏈表的方式實現。
首先，棧的結構定義：
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;
}
隊列ADT
像棧一樣，隊列也是一種表，然而，使用隊列時插入在一端進行而刪除則在另一端進行。隊列的基本操作時Enqueue（入隊）和Dequeue（出隊），入隊是指在表的末端rear插入一個元素，而出隊是刪除（或者返回）在表的開頭front的元素。
如同棧的情形一樣，棧的實現可以用指針和數組的方式，數組的方式筆者同樣在之前做過介紹，今次使用單鏈表的方式實現。
首先，定義隊列的結構：
struct Queue
{
ElementType Element;
Queue *Next;
};
隊列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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
