C語言表、棧和隊列詳解及實例代碼

更新時間：2017年02月09日 10:53:03 投稿：lqh

這篇文章主要介紹了C語言表、棧和隊列詳解及實例代碼的相關(guān)資料,需要的朋友可以參考下

C語言表、棧和隊列詳解

表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ù)組來實現(xiàn)，但在這里使用鏈表的方式來實現(xiàn)。鏈表（linked list）由一系列不必在內(nèi)存中相連的結(jié)構(gòu)組成，每個結(jié)構(gòu)均含有元素和指向包含該元素后繼元的結(jié)構(gòu)的指針。鏈表的結(jié)構(gòu)有很多種，單向鏈表、雙向鏈表、循環(huán)鏈表、有無表頭的鏈表，這里以有表頭結(jié)點的單向鏈表為例，其余幾種的實現(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; 
}

以上是基本的幾個操作，可以看到，操作中沒有對鏈表是否為空進行檢測，在刪除操作中存在隱患。

棧ADT

棧（stack）是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧的頂（top）。對棧的基本操作有Push（進棧）和Pop（出棧），前者相當于插入，后者相當于刪除最后插入的元素。

棧的實現(xiàn)可以是指針，或者使用數(shù)組，數(shù)組的實現(xiàn)在筆者前面的已經(jīng)介紹過了，今次使用單鏈表的方式實現(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; 
}

隊列ADT

像棧一樣，隊列也是一種表，然而，使用隊列時插入在一端進行而刪除則在另一端進行。隊列的基本操作時Enqueue（入隊）和Dequeue（出隊），入隊是指在表的末端rear插入一個元素，而出隊是刪除（或者返回）在表的開頭front的元素。

如同棧的情形一樣，棧的實現(xiàn)可以用指針和數(shù)組的方式，數(shù)組的方式筆者同樣在之前做過介紹，今次使用單鏈表的方式實現(xiàn)。

首先，定義隊列的結(jié)構(gòu)：

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; 
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: