栈的共享数据结构

1、.实验二共享栈一、设计的目的要求1、 了解栈的特性，以及它在实际问题中的应用。2、 掌握栈的实现方法以及它的基本操作，学习运用栈来解决问题。二、设计的主要容设计两个顺序栈共享空间，试写出两个栈公用的栈操作算法 push（ x，k）和 pop（ k）,其中 k 为 0 或 1，用以指示栈号。编写一个完整的程序实现。三、设计的解题思路线性表（ a1，a2， ， an）试一种逻辑结构，若在计算机中对它采用顺序栈存储结构来存储，则就是栈表。两个栈表公用一个存空间图示如下：0maxsize2431Top0top1在数据结构中用 C 语言来描述， 可以利用数组表示顺序表。 将两个原表 A 和 B 存放在一

2、个数组的存储空间（ a1，a2， ， amaxsize-1 ）中，实现方法是：设置两个栈顶指针变量 top1 和 top0 ，开始时 top0 = -1 和 top1 = maxsize 表示两个栈均为空，然后根据变量 k 是 0 还是 1，分别进行入栈和出栈的操作。具体实现还要编写一个完整的程序，用主函数调用这里的函数来完成出入栈的操作。四、算法思路#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define maxsize 10typedef

3、 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,dataty

4、pex,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-&

5、gt;top0=-1)|(k=1&&s->top1=maxsize)printf("栈空 , 不能退栈！ nn");return 0;x=s->datas->topk;/区栈顶元素给 Xif(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;elsep

6、rintf("请选择输入方向，正向(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=

7、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;i<=s-&

8、gt;topl;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):");

9、scanf("%d",&l);printf("n");x=pop(s,l);if(x=0)printf("选择 '1' 继续 ,'0'结束输出： ");scanf("%d",&l);printf("n");if(l=1)continue;elsebreak;printf("n");else if(l=0)printf("正向第 %d个： %dn",z,x);.z+;printf("n");

10、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(&q

11、uot;=n" );voidmain()/主函数int h,k,l=0;/定义 l 为标志，判断是否已建栈，如未建立l=0 ，否则 l=1char i;sqstack *s;for(;)menu();printf("请选择 0-4 ： " );scanf("%d",&h);if(h<0|h>4)printf("n输人错误 ! n" );printf("Enter 'y' to contunie :");scanf("%s",&i);syste

12、m("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(&

13、quot;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;c

14、ase 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);/对栈元素

15、的检测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（回车）*

16、栈的共享输入*请选择输入方向，正向(0)，方向 (1)，结束 (2): 0（回车）请输入数据： 1 2347810 1（回车）请选择输入方向，正向(0)，方向 (1)，结束 (2): 1（回车）请输入数据： 0 56 1（回车）请选择输入方向，正向(0)，方向 (1)，结束 (2): 2（回车）Enter y tocontinue： y（回车）*栈的检测*请选择输入方向，正向(0)，方向 (1)，结束 (2): 0（回车）正向数据为： 12347810请选择输入方向，正向(0)，方向 (1)，结束 (2): 1（回车）反向数据为： 0 5 6请选择输入方向，正向(0)，方向 (1)，结束 (2

17、): 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（回车）栈空，不能退栈！选

18、择 '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 （回车）*再见*按任意键继续 结果二：还未建

19、立栈就输入数据.栈的共享实验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（回车）请输入数据： 1234567891011 1 （回车）两栈均满，不能进栈！请选择输入方向，正向(0)，方向 (1)，结束 (2): 2（回车）Enter y to continue： y（回车）六、调试小结.函数 init (sqstack *s)中少了一条s=(sqstack *)malloc(siz