C语言 表、栈和队列详解及实例代码

概述C语言表、栈和队列详解表ADT 形如A1,A2,A3…An的表，这个表的大小为n，而大小为0的表称为空表，非空表中，Ai+1后继Ai，Ai-1前驱Ai，表ADT的相关 *** 有PrintList打印表中的元素；CreateEmpty创建一个空表；Find

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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

总结

以上是内存溢出为你收集整理的C语言 表、栈和队列详解及实例代码全部内容，希望文章能够帮你解决C语言 表、栈和队列详解及实例代码所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。