栈的共享数据结构

实验二共享栈一、设计的目的要求1、 了解栈的特性，以及它在实际问题中的应用。2、 掌握栈的实现方法以及它的基本操作，学习运用栈来解决问题。二、设计的主要内容设计两个顺序栈共享空间，试写出两个栈公用的栈操作算法push （ x，k）和 pop （ k）,其中 k 为 0 或 1，用以指示栈号。编写一个完整的程序实现。三、设计的解题思路线性表（ a1， a2 ， an ）试一种逻辑结构，若在计算机中对它采用顺序栈存储结构来存储，则就是栈表。两个栈表公用一个内存空间图示如下：024maxsize31top0top1在数据结构中用c 语言来描述，可以利用数组表示顺序表。将两个原表a 和 b 存放在一个数组的存储空间（a1 ， a2 ， amaxsize-1 ）中，实现方法是：设置两个栈顶指针变量 top1 和 top0 ，开始时top0 = -1和 top1 = maxsize表示两个栈均为空，然后根据 变量 k 是 0 还是 1，分别进行入栈和出栈的操作。具体实现还要编写一个完整的程序，用主函数调用这里的函数来完成出入栈的操作。四、算法思路精品资料#include #include #include #include #define maxsize 10typedef int datatype; typedef structdatatype datamaxsize; int top2;sqstack;/定义一个结构体类型的sqstacksqstack a,*s;/ 定义一个结构体类型变量a和指针变量 sssqstack *init(sqstack *s)/ 初始化两个栈均为空，s是指向栈类型的指针s=(sqstack *)malloc(sizeof(sqstack);/ 申请空间s-top0=-1;/top1 、top0 分别是第 0 和第 1个栈的栈顶指针s-top1=maxsize; return s;int push(sqstack *s,datatype x,int k)/ 入栈操作， s是栈顶指针， x是要插入的数， k是栈号if(s-top0+1=s-top1)printf(n);printf( 两个栈均满，不能进栈！n); / 判断是否栈满return 0;if(k=0)s-topk+;/ 改栈顶指针加1或减 1 ，来选择不满的栈elses-topk-;s-datas-topk=x;/将x 插入当前栈顶return 1;int pop(sqstack *s,int k)/ 出栈操作，栈顶元素由参数x返回int x;if(k=0&s-top0=-1)|(k=1&s-top1=maxsize)printf( 栈空 ,不能退栈！ nn); return 0;x=s-datas-topk;/区栈顶元素给x if(k=0)s-topk-;/ 改栈顶指针加1 或减 1 ，来选择不满的栈elses-topk+; return x;void get(sqstack *s,int l)/元素输入函数，l来判断是否已经建栈int k=0,x;while(k=1|k=0)if(l=0)printf( 栈还未建立！n); break;elseprintf( 请选择输入方向，正向(0) ，方向 (1) ，结束 (2):);/ 选择要输入的栈号，并输入元素scanf(%d,&k);printf(n); if(k=0|k=1)x=0;printf( 请输入数据：); while(x!=-1)scanf(%d,&x); if(x=-1)break;push(s,x,k);printf(n);elsebreak;void check(sqstack *s)/ 检测栈内的元素但并不输出int i,l=0; while(l=0|l=1)printf( 请选择输出方向，正向(0) ，方向 (1) ，结束 (2):); scanf(%d,&l);printf(n); if(l=2) break;else if(l=0&s-top0=-1)|(l=1&s-top1=maxsize)printf( 栈空 ,不能退栈！ nn); continue;else if(l=0)printf( 正向数据为：); for(i=0;itopl;i+)printf(%4d,s-datai); printf(nn);elseprintf( 反向数据为：); for(i=maxsize-1;i=s-topl;i-)printf(%4d,s-datai); printf(nn);void print(sqstack *s)/元素输出函数int x,z=1,f=1,l=0; while(l=0|l=1)printf( 请选择输出方向，正向(0) ，方向 (1):); scanf(%d,&l);printf(n);x=pop(s,l); if(x=0)printf( 选择 1继续 ,0 结束输出： ); scanf(%d,&l);printf(n); if(l=1) continue; else break; printf(n);else if(l=0)printf( 正向第 %d 个： %dn,z,x); z+;printf(printf(n);elseprintf( 反向第 %d 个： %dn,f,x); f+;printf(n);void menu()/ 菜单函数printf(栈的共享实验n ); printf(=n);printf( 1. 栈 的 建 立 n ); printf( 2. 栈的共享输入 n ); printf( 3. 栈单个的输出 n ); printf( 4. 栈的检测 n );printf( 0. 退 出 实 验 n ); printf(=n );精品资料voidmain()/ 主函数int h,k,l=0;/定义 l为标志，判断是否已建栈，如未建立l=0 ，否则l=1char i; sqstack *s; for(;)menu();printf(请选择0-4 ： );scanf(%d,&h); if(h4)printf(n 输 人 错 误 ! n ); printf(enter y to contunie :); scanf(%s,&i);system(cls); continue;else switch(h)case 1:system(cls); printf(*n); printf(*栈的建立 *n);printf(*n);printf(n);s=init(s);/栈的建立printf(enter y to contunie :); scanf(%s,&i);printf(n); l=1;system(cls); break;case2:system(cls); printf(*n); printf(*栈的共享输入*n); printf(*n );get(s,l);/ 栈的输入printf(n);printf(enter y to contunie :);scanf(%s,&i);printf(n);system(cls); break;case3:system(cls); printf(*n ); printf(*栈单个的输出* n); printf(*n );print(s);/ 栈的单个输出printf(n);system(cls); break;case4:system(cls); printf(*n ); printf(*栈的检测 * n);printf(*n );check(s);/对栈内元素的检测printf(n);system(cls); break;case0: system(cls);printf(*再 见！ *n); printf(n);return 0;五、运算结果1.栈的建立2.栈的共享输入3.栈单个的输出4.栈的检测0.退 出 实 验请 选 择0-4 ： 1 （回车）* 栈 的 建 立 *结果一： 0 号栈输入元素（1 ，2， 3， 4 ， 7， 8， 10）， 1 号栈输入元素（0，5 ， 6 ）栈的共享实验entery tocontinue： y（回车）* 栈 的 共 享 输 入 *请选择输入方向，正向(0) ，方向请输入数据： 1 2 3 4 7 8 101(1) ，结束 (2): 0（回车）（回车）请选择输入方向，正向(0) ，方向(1) ，结束 (2): 1（回车）请输入数据： 0 5 6 1（回车）请选择输入方向，正向(0) ，方向(1) ，结束 (2): 2（回车）entery tocontinue： y（回车）* 栈 的 检 测 *请选择输入方向，正向(0) ，方向(1) ，结束 (2): 0（回车）正向数据为： 1 2 3 4 7 8 10请选择输入方向，正向(0) ，方向(1) ，结束 (2): 1（回车）反向数据为： 0 5 6请选择输入方向，正向(0) ，方向(1) ，结束 (2): 2（回车）* 栈 的 单 个 输 出 *请选择输出方向，正向(0) ，方向 (1): 0（回车）正向第 1 个： 10请选择输出方向，正向(0) ，方向 (1): 0正向第 2 个： 8（回车）请选择输出方向，正向(0) ，方向 (1): 0（回车）正向第 3 个： 17请选择输出方向，正向(0) ，方向 (1): 0（回车）正向第 4 个： 4请选择输出方向，正向(0) ，方向 (1): 0（回车）正向第 5 个： 3请选择输出方向，正向(0) ，方向 (1): 0（回车）正向第 6 个： 2请选择输出方向，正向(0) ，方向 (1): 0正向第 7 个： 1（回车）请选择输出方向，正向(0) ，方向 (1): 0（回车）栈空，不能退栈！选择 1 继续,0 结束输出： 1（回车）请选择输出方向，正向(0) ，方向 (1): 1反向第 1 个： 6（回车）请选择输出方向，正向(0) ，方向 (1): 1（回车）反向第 2 个： 5请选择输出方向，正向(0) ，方向 (1): 1（回车）反向第 3 个： 0请选择输出方向，正向(0) ，方向 (1): 1（回车）栈空，不能退栈！选择 1 继续,0 结束输出： 0（回车）栈的共享实验5.栈的建立6.栈的共享输入7.栈单个的输出8.栈的检测1.退 出 实 验请 选 择0-4 ： 0 （回车）* 再 见 *按任意键继续结果二：还未建立栈就输入数据栈的共享实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0.退出实 验请选择0-4 ： 2 （回车）* 栈 的 共 享 输 入 *栈还未建立！entery tocontinue： y（回车）结果三：输入的数据过多时栈的共享实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0.退 出 实 验请 选 择0-4 ： 1 （回车）* 栈 的 建 立 *entery tocontinue： y（回车）* 栈 的 共 享 输 入 *请选择输入方向，正向(0) ，方向 (1) ，结束 (2): 0（回车）请输入数据： 1 2 3 4 5 6 7 8 9 10 111（回车） 两栈均满，不能进栈！请选择输入方向，正向(0) ，方向 (1) ，结束 (2): 2（回车）entery tocontinue： y（回车）六、调试小结函数 init (sqstack *s)中少了一条s=(sqstack *)malloc(sizeof(sqstack)语句， 这就导致了栈的内存空间无法分配，所以执行出错。在程序中多加了get (sqstack *s,int l)、check (sqstack *s)、print (sqstack *s)三个函数以便与栈的输入输出以及对栈的检测（不出栈）。为了在栈的输入之前判断是否已经建栈，在主函数中定义了一个l 并定义为 0，当 l = 0时表示还未建栈，l = 1时表示已经建栈。所以只要将l 的值传入get (sqstack *s,int l)函数中就可以判断在此之前是否已经建栈。七、疑问对标志 l 的赋值只能放在建栈