栈的共享数据结构

实验二 共享栈一、 设计的目的要求1、 了解栈的特性，以及它在实际问题中的应用。2、 掌握栈的实现方法以及它的基本操作，学习运用栈来解决问题。二、 设计的主要内容设计两个顺序栈共享空间，试写出两个栈公用的栈操作算法push（x，k）和pop（k）,其中k为0或1，用以指示栈号。编写一个完整的程序实现。三、 设计的解题思路线性表（a1，a2，an）试一种逻辑结构，若在计算机中对它采用顺序栈存储结构来存储，则就是栈表。两个栈表公用一个内存空间图示如下：2 4 3 1 0 maxsizeTop0 top1在数据结构中用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 struct datatype 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，来选择不满的栈 else s-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，来选择不满的栈 else s-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; else printf(请选择输入方向，正向(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); else break; 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); else printf(反向数据为：); 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(n); else printf(反向第%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 );void main() /主函数 int h,k,l=0; /定义l为标志，判断是否已建栈，如未建立l=0，否则l=1 char 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; case 2: 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; case 3: system(cls); printf(*n ); printf(* 栈单个的输出* n); printf(*n ); print(s); /栈的单个输出 printf(n); system(cls); break; case 4: system(cls); printf(*n ); printf(* 栈的检测* n); printf(*n ); check(s); /对栈内元素的检测 printf(n); system(cls); break; case 0: system(cls); printf(* 再 见！*n); printf(n); return 0; 五、 运算结果结果一：0号栈输入元素（1，2，3，4，7，8，10），1号栈输入元素（0，5，6）栈的共享实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0. 退 出 实 验请 选 择 0-4：1 （回车）* 栈 的 建 立 *Enter y to continue ：y （回车）*栈 的 共 享 输 入*请选择输入方向，正向(0)，方向(1)，结束(2): 0 （回车）请输入数据：1 2 3 4 7 8 10 1 （回车）请选择输入方向，正向(0)，方向(1)，结束(2): 1 （回车）请输入数据：0 5 6 1 （回车）请选择输入方向，正向(0)，方向(1)，结束(2): 2 （回车）Enter y to continue ：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 （回车）*栈 的 共 享 输 入*栈还未建立！Enter y to continue ：y （回车）结果三：输入的数据过多时栈的共享实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0. 退 出 实 验请 选 择 0-4：1 （回车）* 栈 的 建 立 *Enter y to continue ：y （回车）*栈 的 共 享 输 入*请选择输入方向，正向(0)，方向(1)，结束(2): 0 （回车）请输入数据：1 2 3 4 5 6 7 8 9 10 11 1 （回车）两栈均满，不能进栈！请选择输入方向，正向(0)，方向(1)，结束(2): 2 （回车）Enter y to continue ：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的赋值只能放在建栈函数s=init(s)之后，而不能放在它的前面。如下： printf(n); s=init(s); printf(Enter y to contunie :); scanf(%s,&i); 正确 printf(n); l=1; system(cls);printf(n);l=1; s=init(s); printf(Enter y to contunie :); scanf(%s,&i); 错误！l的值任然为0，不赋值为1 printf(n); system(cls);