赞
踩
栈和队列本质上是限制线性表某些操作的“衍生产品”。
数组和矩阵本质上是线性表的推广。
栈(Stack)是只允许在一端进行插入和删除的线性表。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
理论上线性表的操作特性它都具备,可由于它的特殊性,一些操作特别是插入和删除操作有变化,我们将其改名为PUSH和POP。
ADT 栈(stack)
DATA
同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
Operation
InitStack(&S):初始化一个空栈。
StackEmpty(S):判断一个栈是否为空。
Push(&S,x):进栈(若栈未满)。
Pop(&S,&x):出栈(若栈非空)。
GetTop(S,&x):读栈顶元素,用x返回元素(若栈非空)。
ClearStack(&S):将队列清空。
DestroyStack(&S):销毁栈,并释放空间。
endADT
#define MaxSize 50 //定义栈中元素最大个数
typedef struct{
Elemtype data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack;
栈顶指针—>S.top,初始设置S.top= -1;
栈顶元素—>S.data[S.top]
####· 进栈操作(Push)
bool Push(SqStack *S,SElemType e){
if(S->top==MAXSIZE -1)
return false; //栈满
S->top++; //栈顶指针加一
S->data[S->top]=e; //插入新元素
return true;
}
bool Pop(SqStack *S,SElemType *e){
if(S->top==-1)
return false; //栈空
*e=S->data[S->top]; //要删除的元素赋给e
S->top--; //栈顶指针减一
return true;
}
顺序栈有一个很大的缺陷,就是必须事先确定数组存储空间的大小。
对于两个相同类型的栈,我们可以做到最大限度地利用事先开辟的存储空间。
共享栈这种数据结构通常适用于两个栈空间有相反的需求关系。
typedef struct{
SElemType data[MAXSIZE];
int top1; //栈1栈顶指针
int top2; //栈2栈顶指针
}SqDoubleStack;
当top1+1=top2时栈满(两栈顶指针见面)
bool Push(SqDoubleStack *S,SElemType e,int stackNumber){
if(S->top1+1==S->top2)
return false; //栈满
if(stackNumber==1){ //栈1进栈
S->top1++; //栈1栈顶指针加一
S->data[S->top1]=e;
}
else if(stackNumber==2){ //栈2进栈
S->top2--; //栈2栈顶指针减一
S->data[S->top2]=e;
}
return true;
}
bool Pop(SqDoubleStack *S,SElemType *e,int stackNumber){
if(stackNumber==1){
if(S->top1==-1)
return false; //栈空
*e=S->data[S->top1]; //要删除的元素赋给e
S->top1--; //栈顶指针减一
}
else if(stackNumber==2){
if(S->top2==MAXSIZE)
return false; //栈空
*e=S->data[S->top2]; //要删除的元素赋给e
S->top2++; //栈顶指针加一
}
return true;
}
typedef struct StackNode{
SELemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;//结点
typedef struct{
LinkStackPtr top;
int count;
}LinkStack;//链栈
栈顶指针是链表的头指针;
链栈没有头结点;
bool Push(LinkStack *S,SElemType e){
LinkStackPtr p=(LinkStackPtr)malloc(sizeof(StackNode));
p->data=e;
p->next=S->top; //栈顶成为s的后继
S->top=p; //栈顶指针变为s
S->count++; //链表长度+1
return true;
}
bool Pop(LinkStack *S,SElemType &e){
LinkStackPtr p;
if(StackEmpty(*S)) //判断栈空
return false;
e=S->top->data; //栈顶元素值赋给e
p=S->top;
S->top=S->top->next; //栈顶指针变更
free(p); //释放原栈顶空间
S->count--; //链表长度-1
return true;
}
我们日常使用的计算表达式——中缀表达式,不仅依赖于运算符的优先级,还要处理括号,计算机处理起来很麻烦。
后缀表达式(逆波兰式)是一种不需要括号的后缀表达法。它的特点是:所有的运算符都出现在要运算的数字后面。
计算机用后缀表达式计算的过程:
若在一个函数、过程或数据结构的定义中,又应用它自身,则称为递归。
eg——斐波那契数列:
int Fib(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
递归模型必须满足下面两个条件:
递归调用的过程中,编译器使用到了递归工作栈。递归次数过多容易造成栈溢出。
队列(Queue)是只允许在表的一端进行插入,而在表的另一端进行删除的线性表。队列又称为先进先出(First In First Out)的线性表,简称FIFO结构。
插入和删除操作有变化,我们将其改名为EnQueue和DeQueue。
ADT 队列(queue)
DATA
同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
Operation
InitQueue(&Q):初始化一个空队列。
QueueEmpty(Q):判断一个队列是否为空。
EnQueue(&Q,e):插入新元素e到队尾(队列存在)。
DeQueue(&Q,&e):删除队列中的队头元素并用e返回(若队列非空)。
GetHead(Q,&e):读队头元素,用e返回元素(若队列非空)。
DestroyQueue(&Q):销毁队列,并释放空间。
ClearQueue(&Q):将队列清空。
QueueLength(Q):返回队列中元素个数。
endADT
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:
#define MaxSize 50 //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放队列元素
int front,rear; //队头指针和队尾指针
}SqQueue;
初始状态(队空条件):Q.front=Q.rear=0 ;
进队操作:队不满时,先送值到队尾,再将队尾指针+1.
出队操作:队不空时,先取队头元素值,再将队头指针+1.
判断队列满并不能用Q.rear==MaxSize判断,溢出可能是“假溢出”。
未解决以上空间浪费的缺陷,将顺序队列臆造为一个环状的空间,称为循环队列。
此时判断队列满的两种方法:
通用的计算队列长度的公式:(rear-front+QueueSize)%QueueSize.
#define MaxSize 50 //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放队列元素
int front,rear; //队头指针和队尾指针
}SqQueue;
初始化循环队列:Q->front=0; Q->rear=0;
bool EnQueue(SqQueue *Q,QElemType e){
if((Q->rear+1)%MaxSize == Q->front)
return false; //队列判满
Q->data[Q->rear]=e; //e赋给队尾
Q->rear=(Q->rear+1)%MaxSize; //队尾指针变更
return true;
}
bool Dequeue(SqQueue *Q,QElemType *e){
if(Q->front == Q->rear)
return false; //队列判空
*e=Q->data[Q->front]; //队头元素赋值给e
Q->front=(Q->front+1)%MaxSize; //对头指针变更
return true;
}
即使是循环队列也面临着溢出的问题。
队列的链式存储结构,其实就是线性表的单链表,只是它只能尾进头出。
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;//结点
typedef struct{
QueuePtr front,rear;//或QNode *front,*rear;
}LinkQueue;//链队列
队头指针指向链队列的头结点,队尾指针指向链队列的终端结点。
空队列的front和rear都指向头结点。
bool EnQueue(LinkQueue *Q,SElemType e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p; //p变为Q的新队尾结点
Q->rear=p; //队尾指针指向p
return true;
}
bool DeQueue(LinkQueue *Q,SElemType &e){
QueuePtr p;
if(Q->front==Q->rear) //判断队列空
return false;
p=Q->front->next; //将欲删除的队头结点暂存给p
e=p->data; //将欲删除的队头结点的值暂存给e
Q->front->next=p->next; //原头结点的后继从p变成p的后继
if(Q->rear==p)
Q->rear=Q->front; //若要删除的p是队列中唯一的元素,则直接初始化
free(p);
return true;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。