C语言 表、栈和队列详解及实例代码
C语言表、栈和队列详解
表ADT
形如A1,A2,A3…An的表，这个表的大小为n，而大小为0的表称为空表，非空表中，Ai+1后继Ai，Ai-1前驱Ai，表ADT的相关操有PrintList打印表中的元素；CreateEmpty创建一个空表；Find返回关键字首次出现的位置；Insert和Delete从表的某个位置插入和删除某个关键字。
对表的所有操作都可以通过使用数组来实现，但在这里使用链表的方式来实现。链表（linkedlist）由一系列不必在内存中相连的结构组成，每个结构均含有元素和指向包含该元素后继元的结构的指针。链表的结构有很多种，单向链表、双向链表、循环链表、有无表头的链表，这里以有表头结点的单向链表为例，其余几种的实现思路相同。
首先定义链表的结构：
structNode
{
ElementTypeElement;
Node*Next;
};
表ADT的主要操作：
Node*CreateEmpty()
{
Node*header=newNode;
Header->Element=0;
Header->Next=NULL;
returnheader;
}
voidPrintList(Node*List)
{
Node*p=List->Next;
While(p)
{
std::cout<<p->Element<<““;
}
}
Node*Find(Node*List,ElementTypeX)
{
Node*p=List->Next;
while(p&&p->Element!=X)
{
p=p->Next;
}
returnp;
}
voidInsert(Node*List,ElementTypeX)
{
Node*p=List;
while(p->Next)
{
p=p->Next;
}
p->Next=newNode;
p=p->Next;
p->Next=NULL;
p->Element=X;
}
voidDelete(Node*List,ElementTypeX)
{
Node*p=List->Next;
Node*d=p->Next;
while(d->Element!=X)
{
p=p->Next;
d=p->Next;
}
p->Next=d->Next;
deleted;
}
以上是基本的几个操作，可以看到，操作中没有对链表是否为空进行检测，在删除操作中存在隐患。
栈ADT
栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（top）。对栈的基本操作有Push（进栈）和Pop（出栈），前者相当于插入，后者相当于删除最后插入的元素。
栈的实现可以是指针，或者使用数组，数组的实现在笔者前面的已经介绍过了，今次使用单链表的方式实现。
首先，栈的结构定义：
structStack
{
ElementTypeElement;
Stack*Next;
};
栈ADT的主要操作：
Stack*CreateStack()
{
Stack*S=newStack;
S->Next=NULL;
returnS;
}
voidPush(Stack*S,ElementTypeX)
{
Stack*p=newStack;
p->Next=S;
S->Element=X;
S=p;
}
ElementTypePop(Stack*S)
{
Stack*p=S;
if(S->Next)
{
S=S->Next;
deletep;
}
returnS->Element;
}
队列ADT
像栈一样，队列也是一种表，然而，使用队列时插入在一端进行而删除则在另一端进行。队列的基本操作时Enqueue（入队）和Dequeue（出队），入队是指在表的末端rear插入一个元素，而出队是删除（或者返回）在表的开头front的元素。
如同栈的情形一样，栈的实现可以用指针和数组的方式，数组的方式笔者同样在之前做过介绍，今次使用单链表的方式实现。
首先，定义队列的结构：
structQueue
{
ElementTypeElement;
Queue*Next;
};
队列ADT的主要操作：
Queue*CreateQueue()
{
Queue*p=newQueue;
p->Next=NULL;
returnp;
}
voidEnqueue(Queue*rear,ElementTypeX)
{
Queue*p=newQueue;
p->Element=X;
rear->Next=p;
rear=p;
}
ElementTypeDequeue(Queue*front)
{
Queue*p=front;
ElementTypee=front->Element;
front=front->Next;
deletep;
returne;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！