用顺序结构表示栈并实现栈的各种基本操作

《用顺序结构表示栈并实现栈的各种基本操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

栈的顺序表示和实现2.2基础实验2.2.1实验目的（1）掌握栈的顺序表示和实现（2）掌握栈的链式表示和实现（3）掌握队列的顺序表示和实现（4）掌握队列的链式表示和实现2.2.2实验内容实验一：栈的顺序表示和实现【实验内容与要求】编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈【知识要点】栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top==MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置【实现提示】/*定义顺序栈的存储结构*/typedefstruct{ElemTypestack[MAXNUM]; inttop;}SqStack;/*初始化顺序栈函数*/voidInitStack(SqStack*p){q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/)/*入栈函数*/voidPush(SqStack*p,ElemTypex){if(p->toptop=p->top+1;/*栈顶+1*/p->stack[p->top]=x;}/*数据入栈*/}/*出栈函数*/ElemTypePop(SqStack*p){x=p->stack[p->top];/*将栈顶元素赋给x*/p->top=p->top-1;}/*栈顶-1*//*获取栈顶元素函数*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍历顺序栈函数*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d ",i,p->stack[i]);}/*置空顺序栈函数*/voidsetEmpty(SqStack*p){p->top=-1;}【参考程序】#include#include#defineMAXNUM20#defineElemTypeint/*定义顺序栈的存储结构*/typedefstruct{ElemTypestack[MAXNUM];inttop;}SqStack;/*初始化顺序栈*/voidInitStack(SqStack*p){if(!p)printf("Eorror");p->top=-1;}/*入栈*/ voidPush(SqStack*p,ElemTypex){if(p->toptop=p->top+1;p->stack[p->top]=x;}elseprintf("Overflow! ");}/*出栈*/ElemTypePop(SqStack*p){ElemTypex;if(p->top!=0){x=p->stack[p->top];printf("以前的栈顶数据元素%d已经被删除！ ",p->stack[p->top]);p->top=p->top-1;return(x);}else{printf("Underflow! ");return(0);}}/*获取栈顶元素*/ElemTypeGetTop(SqStack*p){ElemTypex;if(p->top!=0){x=p->stack[p->top];return(x);}else{printf("Underflow! ");return(0);}}/*遍历顺序栈*/voidOutStack(SqStack*p){inti;printf(" ");if(p->top<0)printf("这是一个空栈！");printf(" ");for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d ",i,p->stack[i]);} /*置空顺序栈*/voidsetEmpty(SqStack*p){p->top=-1;}/*主函数*/main(){SqStack*q;inty,cord;ElemTypea;do{printf(" ");printf("第一次使用必须初始化！ ");printf(" ");printf(" 主菜单 ");printf(" 1初始化顺序栈 ");printf(" 2插入一个元素 ");printf(" 3删除栈顶元素 ");printf(" 4取栈顶元素 ");printf(" 5置空顺序栈 ");printf(" 6结束程序运行 ");printf(" -------------------------------- ");printf("请输入您的选择(1,2,3,4,5,6)");scanf("%d",&cord);printf(" ");switch(cord){case1:{q=(SqStack*)malloc(sizeof(SqStack));InitStack(q);OutStack(q);}break;case2:{printf("请输入要插入的数据元素：a=");scanf("%d",&a);Push(q,a);OutStack(q);}break;case3:{Pop(q);OutStack(q);}break;case4:{y=GetTop(q);printf(" 栈顶元素为：%d ",y);OutStack(q); }break;case5:{setEmpty(q);printf(" 顺序栈被置空！ ");OutStack(q);}break;case6:exit(0);}}while(cord<=6);}【思考与提高】（1）读栈顶元素的算法与退栈顶元素的算法有何区别？（2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？实验二：栈的链式表示和实现【实验内容与要求】编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈【知识要点】链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。【实现提示】typedefintElemtype;typedefstructstacknode{Elemtypedata; stacknode*next;}StackNode;/*定义链栈*/typedefstruct{stacknode*top;//栈顶指针}LinkStack;/*初始化链栈函数*/voidInitStack(LinkStack*s){s=(LinkStack*)malloc(sizeof(LinkStack));/*初始化申请空间*/s->top=NULL;}/*链栈置空函数*/voidsetEmpty(LinkStack*s){s->top=NULL;}/*入栈函数*/voidpushLstack(LinkStack*s,Elemtypex){p=(StackNode*)malloc(sizeof(StackNode));//建立一个节点。p->data=x;p->next=s->top;//指向栈顶。s->top=p;//插入}/*出栈函数*/ElemtypepopLstack(LinkStack*s){x=p->data;s->top=p->next;//当前的栈顶指向原栈的nextfree(p);//释放}/*取栈顶元素函数*/ElemtypeStackTop(LinkStack*s){returns->top->data;}/*遍历链栈函数*/voidDisp(LinkStack*s){while(p!=NULL){printf("%d ",p->data);p=p->next;}}【参考程序】#include"stdio.h"#include"malloc.h"#include"stdlib.h"typedefintElemtype;typedefstructstacknode{ Elemtypedata;stacknode*next;}StackNode;typedefstruct{stacknode*top;//栈顶指针}LinkStack;/*初始化链栈*/voidInitStack(LinkStack*s){s->top=NULL;printf(" 已经初始化链栈！ ");}/*链栈置空*/voidsetEmpty(LinkStack*s){s->top=NULL;printf(" 链栈被置空！ ");}/*入栈*/voidpushLstack(LinkStack*s,Elemtypex){StackNode*p;p=(StackNode*)malloc(sizeof(StackNode));//建立一个节点。p->data=x;p->next=s->top;//由于是在栈顶pushLstack，所以要指向栈顶。s->top=p;//插入}/*出栈*/ElemtypepopLstack(LinkStack*s){Elemtypex;StackNode*p;p=s->top;//指向栈顶if(s->top==0){printf(" 栈空，不能出栈！ ");exit(-1);}x=p->data;s->top=p->next;//当前的栈顶指向原栈的nextfree(p);//释放returnx;}/*取栈顶元素*/ElemtypeStackTop(LinkStack*s){if(s->top==0){printf(" 链栈空 ");exit(-1);} returns->top->data;}/*遍历链栈*/voidDisp(LinkStack*s){printf(" 链栈中的数据为： ");printf("======================================= ");StackNode*p;p=s->top;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("======================================= ");}voidmain(){printf("=================链栈操作================= ");inti,m,n,a;LinkStack*s;s=(LinkStack*)malloc(sizeof(LinkStack));intcord;do{printf(" ");printf("第一次使用必须初始化！ ");printf(" ");printf(" 主菜单 ");printf(" 1初始化链栈 ");printf(" 2入栈 ");printf(" 3出栈 ");printf(" 4取栈顶元素 ");printf(" 5置空链栈 ");printf(" 6结束程序运行 ");printf(" -------------------------------- ");printf("请输入您的选择(1,2,3,4,5,6)");scanf("%d",&cord);printf(" ");switch(cord){case1:{InitStack(s);Disp(s);}break;case2:{printf("输入将要压入链栈的数据的个数：n=");scanf("%d",&n);printf("依次将%d个数据压入链栈： ",n);for(i=1;i<=n;i++) {scanf("%d",&a);pushLstack(s,a);}Disp(s);}break;case3:{printf(" 出栈操作开始! ");printf("输入将要出栈的数据个数：m=");scanf("%d",&m);for(i=1;i<=m;i++){printf(" 第%d次出栈的数据是：%d",i,popLstack(s));}Disp(s);}break;case4:{printf(" 链栈的栈顶元素为：%d ",StackTop(s));printf(" ");}break;case5:{setEmpty(s);Disp(s);}break;case6:exit(0);}}while(cord<=6);}【思考与提高】（1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？（2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？实验三：队列的顺序表示和实现【实验内容与要求】编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空 （6）取队头元素（7）遍历队列【知识要点】队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1）"下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2）"真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。（3）"假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。【实现提示】/*定义队列*/typedefstruct{Elemtypequeue[MAXNUM];intfront;intrear;}sqqueue;/*队列初始化函数*/intinitQueue(sqqueue*q){q=(sqqueue*)malloc(sizeof(sqqueue));/*初始化申请空间*/q->front=-1;q->rear=-1;}/*入队函数*/intappend(sqqueue*q,Elemtypex){q->rear++;q->queue[q->rear]=x;}/*出队函数*/ElemtypeDelete(sqqueue*q){x=q->queue[++q->front];}/*判断队列是否为空函数*/intEmpty(sqqueue*q){if(q->front==q->rear)returnTRUE;} /*取队头元素函数*/intgethead(sqqueue*q){return(q->queue[q->front+1]);}/*遍历队列函数*/voiddisplay(sqqueue*q){while(srear){s=s+1;printf("%d<-",q->queue[s]);}}/*建立顺序队列函数*/voidSetsqqueue(sqqueue*q){for(i=0;i#include#defineMAXNUM100#defineElemtypeint#defineTRUE1#defineFALSE0typedefstruct{Elemtypequeue[MAXNUM];intfront;intrear;}sqqueue;/*队列初始化*/intinitQueue(sqqueue*q){if(!q)returnFALSE;q->front=-1;q->rear=-1;returnTRUE;}/*入队*/intappend(sqqueue*q,Elemtypex){if(q->rear>=MAXNUM-1)returnFALSE;q->rear++;q->queue[q->rear]=x;returnTRUE;}/*出队*/ElemtypeDelete(sqqueue*q) {Elemtypex;if(q->front==q->rear)return0;x=q->queue[++q->front];returnx;}/*判断队列是否为空*/intEmpty(sqqueue*q){if(q->front==q->rear)returnTRUE;returnFALSE;}/*取队头元素*/intgethead(sqqueue*q){if(q->front==q->rear)return0;return(q->queue[q->front+1]);}/*遍历队列*/voiddisplay(sqqueue*q){ints;s=q->front;if(q->front==q->rear)printf("队列空! ");else{printf(" 顺序队列依次为：");while(srear){s=s+1;printf("%d<-",q->queue[s]);}printf(" ");printf("顺序队列的队尾元素所在位置:rear=%d ",q->rear);printf("顺序队列的队头元素所在位置:front=%d ",q->front);}}/*建立顺序队列*/voidSetsqqueue(sqqueue*q){intn,i,m;printf(" 请输入将要入顺序队列的长度:");scanf("%d",&n);printf(" 请依次输入入顺序队列的元素值: ");for(i=0;i