栈和队列---一站式入门,数据结构真的不难
栈的抽象数据类型的类型定义:
ADT Stack {
数据对象:
D={ ai | ai cElemSet, i=1,2...n,n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2...n }
约定an端为栈顶,a1端为栈底。
基本操作:初始化、进栈、出栈、取栈顶元素等
}ADT Stack
InitStack(&S)初始化操作
操作结果:构造一个空栈S。
DestroyStack(&S)销毁栈操作
初始条件:栈S已存在。
操作结果:栈S被销毁。
StackEmpty(S)判定S是否为空栈
初始条件:栈S已存在。
操作结果:若栈S为空栈,则返回TRUE,
否则FALSE。
StackLength()求栈的长度
初始条件:栈S已存在。
操作结果:返回S的元素个数,即栈的长度。
GetTop(S,&e) 取栈顶元素
初始条件:栈S已存在且非空。
操作结果:用e返回S的栈顶元素。
ClearStack(&S) 栈置空操作
初始条件:栈S已存在。
操作结果:将S清为空栈。
Push(&S, e) 入栈操作
初始条件:栈S已存在。
操作结果:插入元素e为新的栈顶元素。
Pop(&S,&e) 出栈操作
初始条件:栈S已存在且非空。
操作结果:删除S的栈顶元素an,并用e返回
其值。
使用数组作为顺序栈存储方式的特点:简单方便容易溢出(上溢下溢)
存储方式:同一般线性表的顺序存储结构完全相同,
利用—组地址连续的存储单元依次存放自栈底
到栈页的数据元素。栈底一般在低地址端。
·附设top指针,指示栈顶元素在顺序栈中的位置。
·另设base指针,指示栈底元素在顺序栈中的位置。
base==top栈空
Top-bace==stzcksie栈满
stacksize表示栈可用的最大容量
顺序栈的表示
#define MAXSIZE 100
typedef struct{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈可用最大容量
}SqStack;
Status InitStack(SqStack &S){//构造一个空栈
S.base = new SElemType[MAXSIZE];
//或S.base=(SElemType)malloc(MAXSIZE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top= S.base;//栈顶指针等于栈底指针
S.stacksize =MAXSIZE;
return OK;
}
判断顺序栈是否为空
Status StackEmpty(SqStackS)
//若栈为空,返回TRUE;否则返回FALSE
if (S.top == S.base)
return TRUE;
else
return FALSE;
}
求顺序栈长度
int stacklengh(SqStack S)
{
Return S.top-S.base;
}
清空顺序栈:
Status ClearStack( SqStack &S){
if( S.base ) S.top = S.base;
return OK;
}
销毁顺序栈:
Status DestroyStack( SqStack &S ) {
if( S.base ) {
delete S.base ;
S.stacksize = O;
S.base = S.top = NULL;
}
return OK;
}
顺序栈的入栈:
出栈
链栈
链栈是运算受限的单链表,;只能从链表一端进行操作
链栈初始化:
Void InitStack(LinkStack &S){
//构造一个空栈,栈顶指针置为空
S=NULL;
return 0;
}
判断链栈是否为空
Status StackEmpty(LinkStack S)
{
if (S==NULL) return TRUE;
else return FALSE;
}
链栈压栈(入栈)
Status Push(LinkStack &s,SElemType e){
p=new StackNode;//p=(StackNode)malloc(sizeof(StackNode))
//生成新结点p
p->data=e;//将新结点数据域置为e
p- >next=s;//将新结点插入栈顶
s=p;//修改栈顶指针
return OK;
}
链栈弹栈(出栈)
Status Pop (LinkStack &S,SElemType &e){
if (S==NULL) return ERROR;
e = S-> data;
p= S;
S = S->next;
delete p;//free(p)
return OK;
取栈顶元素:
SElemType GetTop(LinkStack S){
if (S!=NULL)
return S->data;
}
栈和递归:
若一个对象包含自己一部分,或者自己给自己定义,则称这个对象是递归的
若一个过程直接或间接地调用自己,则称这个过程是递归的过程
以下三种情况常常用到递归方法:
递归定义的数学函数
具有递归特性的数据结构
可递归求解的问题
分治法:对于一个较为复杂的问题,能够分解成几个相对简单的且解法相同或类似的子问题来求解
必备的三个条件
1、能将一个问题转变成一个新问题,而新问题与原问题的解法相同或类同,不同的仅是处理的对象,且这些处理对象是变化有规律的
2、可以通过上述转化而使问题简化
3、必须有一个明确的递归出口,或称递归的边界
队列的抽象数据类型定义:
解决假上溢的方法:
将队空间设想成一个循环的表,即分配给队列的m个存储单元可以循环使用,当rear为maxqsize时,若向量的开始端空着,又可从头使用空着的空间。当front为maxqsize时,也是一样。
#include <stdio.h>
#define max 5//表示顺序表申请的空间大小
int enQueue(int *a,int front,int rear,int data){
//添加判断语句,如果rear超过max,则直接将其从a[0]重新开始存储,如果rear+1和front重合,则表示数组已满
if ((rear+1)%max==front) {
printf("空间已满");
return rear;
}
a[rear%max]=data;
rear++;
return rear;
}
int deQueue(int *a,int front,int rear){
//如果front==rear,表示队列为空
if(front==rear%max) {
printf("队列为空");
return front;
}
printf("%d ",a[front]);
//front不再直接 +1,而是+1后同max进行比较,如果=max,则直接跳转到 a[0]
front=(front+1)%max;
return front;
}
int main() {
int a[max];
int front,rear;
//设置队头指针和队尾指针,当队列中没有元素时,队头和队尾指向同一块地址
front=rear=0;
//入队
rear=enQueue(a,front,rear, 1);
rear=enQueue(a,front,rear, 2);
rear=enQueue(a,front,rear, 3);
rear=enQueue(a,front,rear, 4);
//出队
front=deQueue(a, front, rear);
//再入队
rear=enQueue(a,front,rear, 5);
//再出队
front=deQueue(a, front, rear);
//再入队
rear=enQueue(a,front,rear, 6);
//再出队
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
return 0;
}
使用此方法需要注意的是,顺序队列在判断数组是否已满时,出现下面情况:
当队列为空时,队列的头指针等于队列的尾指针;
当数组满员时,队列的头指针等于队列的尾指针;
顺序队列的存储状态不同,但是判断条件相同。为了对其进行区分,最简单的解决办法是:牺牲掉数组中的一个存储空间,判断数组满员的条件是:尾指针的下一个位置和头指针相遇,就说明数组满了,
队列的初始化:
队列的长度:
int QueueLength (SqQueue Q){
return (Qrear-Q.front+MAXQSIZE)%MAXQSIZE;
}
循环队列入队
Status EnQueue(SqQueue &Q,QElemType e){
if((Qrear+1)%MAXQSIZE==Qfront) return ERROR;//队满
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
出队:
Status DeQueue (SqQueue &QQElemType &e){
if(Q.front==Q.rear) return ERROR;//队空
e=Qbase[Q.front];//保存队头元素
Q.front=(Q.front+1)%MAXQSIZE;//队头指针+1
return OK;
}
取队头元素
SElemType GetHead(SqQuere Q){
if(Q.front!=Q.rear)//队列不为空
return Qbase[Q.front];//返回队头指针元素的值,队头指针不变
}
链队列的初始化
Status InitQueue (LinkQueue &Q){
Qfront=Qrear=(QueuePtr)malloc(sizeof(QNode));
if(!Qfront)exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
销毁链队列:
Status DestroyQueue (LinkQueue &Q){
while(Qfront){
p=Q.front->next;free(Q.front);Q.front=p;
}
return OK;
}
将元素e入队
Status EnQueue(LinkQueue &Q,QElemType e){
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
链队列出队
Status DeQueue (LinkQueue &QQElemType &e){
if(Q.front==Q.rear)return_ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
delete p;
return OK;
链队列队头元素
Status GetHead (LinkQueue Q,QElemType &e){
if(Q.front==Qrear)return ERROR;
e=Q.front->next->data;
return OK;
}