栈的共享数据结构

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

2、, ,amaxsize-1 )中，实现方法是：设置两个栈顶指针变量top1和top0，开始时top0 = -1 和top1 = maxsize表示两个栈均为空，然后根据变量k是0还是1,分别进行入栈和出栈的操作。具体实现还要编写一个完整的程序，用主函数调用这里的函数来完成出入栈的操作。四、算法思路#i nclude <stdio.h>#in clude <stri ng.h> #in clude <stdlib.h> #in clude <coni o.h> #defi ne maxsize 10 typedef int datatype;typ

3、edef structdatatype datamaxsize;int top2;定义一个结构体类型的sqstack定义一个结构体类型变量a和指针变量sssqstack;/sqstack a,*s;/初始化两个栈均为空，s是指向栈类申请空间sqstack *init(sqstack *s)/型的指针s=(sqstack *)malloc(sizeof(sqstack); /s->top0=-1;个栈的栈顶指针s->top1=maxsize;return s;/top1、top0 分别是第 0和第 1int push(sqstack *s,datatypex,int k) /入栈操作

4、，s是栈顶指针，x是要插入的数，k是栈号if(s->top0+1=s->top1)printf("n");printf("两个栈均满，不能进栈！ n"); / 判断是否栈满return 0;if(k=0)s->topk+;/elses->topk-;s->datas->topk=x; /return 1;改栈顶指针加 1或减 1，来选择不满的栈将X插入当前栈顶int pop(sqstack *s,int k) /int x;出栈操作，栈顶元素由参数 x返回if(k=0&&s->top0=-1)|(

5、k=1&&s->top1=maxsize)printf("栈空 , 不能退栈！return 0;x=s->datas->topk; / if(k=0)s->topk-;/elsenn");区栈顶元素给 X改栈顶指针加 1或减 1，来选择不满的栈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选择要输入的栈p

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,

7、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

8、;i<=s->topl;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(" 请选择输出方

9、向，正向 (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(”正向第 个：%dn",z,x)

10、;z+; printf("n");elseprintf(”反向第 %(个: %dn",f,x);f+;printf("n");void menu()/菜单函数printf(" 1.栈的建立 n" )Jprintf(" 2.栈的共享输入n" );printf(" 3.栈单个的输出n" );printf(" 4.栈的检测 n" )Jprintf(" 0.退出实验 n" )Jprintf("=n" );void main()int

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

12、ontunie :"); scanf("%s",&i);system("cls");continue;elseswitch(h) case 1:system("cls");printf( "*n"); printf("* 栈的建立 *n");printf( "*n"); printf("n");栈的建立s=init(s); / printf("Enter 'y' to contunie :"); sca

13、nf("%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("

14、;%s",&i); printf("n"); system("cls");break;case 3:system("cls");printf(printf("* 栈单个的输出 * n");printf(H*n" );print(s); / 栈的单个输出printf("n"); system("cls"); break;case 4:system("cls");printf(H*printf("* 栈的检测 * n&qu

15、ot;);printf(H*n" );check(s); /对栈内元素的检测printf("n");system("cls");break;case 0:system（"cls"）;printf（"*再见！ *n"）;prin tf（"n ”）;return 0;五、运算结果结果一：0号栈输入元素（1, 2, 3, 4, 7, 8, 10） , 1号栈输入元素（0, 5, 6） 栈的共享实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0.退出实验请选择0-4: 1 （回车）*

16、栈的建立*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（回车）Enter y' to continue:y（回车）*栈的检测*请选择输入方向，正向（0），方向(1):，结束(2): 0（回车）正向数据为：1 2 3 4 78 10请选择输入方向，正向（0），方向(1):，结束(2): 1（回车

17、）反向数据为：0 5 6请选择输入方向，正向（0），方向(1):，结束(2): 2（回车）*栈的单个输出请选择0-4: 0 (回车) 1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0.退出实验请选择0-4: 1 （回车）*栈的建立*Entery' to continue: y（回车）请选择输出方向，正向(0):，力向:0(回车)正向第1个：10请选择输出方向，正向(0):，方向:0(回车)正向第2个：8请选择输出方向，正向(0):，方向:0(回车)正向第3个：17请选择输出方向，正向(0)，方向(1)：0(回车)正向第4个：4请选择输出方向，正向(0)，方向(1)：0

18、(回车)正向第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'

19、;结束输出：0 (回车) 栈的共享实验5. 栈的建立6. 栈的共享输入7. 栈单个的输出8. 栈的检测1. 退出实验1. 栈的建立2. 栈的共享输入3. 栈单个的输出4. 栈的检测0.退出实验请选择0-4: 2 （回车）*栈的共享输入栈的共享输入 *请选择输入方向，正向（0），方向（1），结束（2）: 0（回车）请输入数据：1 2 3 4 5 6 7 8 9 10 11-（回车）两栈均满，不能进栈！请选择输入方向，正向（0），方向（1），结束（2）: 2（回车）Entery' to continue: y （回车）六、调试小结栈还未建立！Entery' to continue: y（回车）结果三：输入的数据过多时栈的共享实验函数 init (sqstack *s) 中少了一条 s=(sqstack *)malloc(sizeof(sqstack)语句，这就导致了栈的内存空间无法分配，所以执行出错。在程序中多加了 get (sqstack