栈的共享 数据结构.docx
《栈的共享 数据结构.docx》由会员分享，可在线阅读，更多相关《栈的共享 数据结构.docx（16页珍藏版）》请在冰点文库上搜索。
栈的共享数据结构
实验二共享栈
一、设计的目的要求
1、了解栈的特性，以及它在实际问题中的应用。
2、掌握栈的实现方法以及它的基本操作，学习运用栈来解决问题。
二、设计的主要内容
设计两个顺序栈共享空间，试写出两个栈公用的栈操作算法push（x，k）和pop（k）,其中k为0或1，用以指示栈号。
编写一个完整的程序实现。
三、设计的解题思路
线性表（a1，a2，……，an）试一种逻辑结构，若在计算机中对它采用顺序栈存储结构来存储，则就是栈表。
两个栈表公用一个内存空间图示如下：
0maxsize
Top[0]top[1]
在数据结构中用C语言来描述，可以利用数组表示顺序表。
将两个原表A和B存放在一个数组的存储空间（a1，a2，……，amaxsize-1）中，实现方法是：
设置两个栈顶指针变量top[1]和top[0]，开始时top[0]=-1和top[1]=maxsize表示两个栈均为空，然后根据变量k是0还是1，分别进行入栈和出栈的操作。
具体实现还要编写一个完整的程序，用主函数调用这里的函数来完成出入栈的操作。
四、算法思路
#include
#include
#include
#include
#definemaxsize10
typedefintdatatype;
typedefstruct
{
datatypedata[maxsize];
inttop[2];
}sqstack;//定义一个结构体类型的sqstack
sqstacka,*s;//定义一个结构体类型变量a和指针变量ss
sqstack*init（sqstack*s）//初始化两个栈均为空，s是指向栈类型的指针
{
s=（sqstack*）malloc（sizeof（sqstack））;//申请空间
s->top[0]=-1;//top[1]、top[0]分别是第0和第1个栈的栈顶指针
s->top[1]=maxsize;
returns;
}
intpush（sqstack*s,datatypex,intk）//入栈操作，s是栈顶指针，x是要插入的数，k是栈号
{
if（s->top[0]+1==s->top[1]）
{
printf（"\n"）;
printf（"两个栈均满，不能进栈！
\n"）;//判断是否栈满
return0;
}
if（k==0）
s->top[k]++;//改栈顶指针加1或减1，来选择不满的栈
else
s->top[k]--;
s->data[s->top[k]]=x;//将X插入当前栈顶
return1;
}
intpop（sqstack*s,intk）//出栈操作，栈顶元素由参数x返回
{
intx;
if（（k==0&&s->top[0]==-1）||（k==1&&s->top[1]==maxsize））
{
printf（"栈空,不能退栈！
\n\n"）;
return0;
}
x=s->data[s->top[k]];//区栈顶元素给X
if（k==0）
s->top[k]--;//改栈顶指针加1或减1，来选择不满的栈
else
s->top[k]++;
returnx;
}
voidget（sqstack*s,intl）//元素输入函数，l来判断是否已经建栈
{
intk=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;
}
}
}
voidcheck（sqstack*s）//检测栈内的元素但并不输出
{
inti,l=0;
while（l==0||l==1）
{
printf（"请选择输出方向，正向（0），方向
（1），结束
（2）:
"）;
scanf（"%d",&l）;
printf（"\n"）;
if（l==2）
break;
elseif（（l==0&&s->top[0]==-1）||（l==1&&s->top[1]==maxsize））
{
printf（"栈空,不能退栈！
\n\n"）;
continue;
}
elseif（l==0）
{
printf（"正向数据为：
"）;
for（i=0;i<=s->top[l];i++）
printf（"%4d",s->data[i]）;
printf（"\n\n"）;
}
else
{
printf（"反向数据为：
"）;
for（i=maxsize-1;i>=s->top[l];i--）
printf（"%4d",s->data[i]）;
printf（"\n\n"）;
}
}
}
voidprint（sqstack*s）//元素输出函数
{
intx,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"）;
}
elseif（l==0）
{
printf（"正向第%d个：
%d\n",z,x）;
z++;
printf（"\n"）;
}
else
{
printf（"反向第%d个：
%d\n",f,x）;
f++;
printf（"\n"）;
}
}
}
voidmenu（）//菜单函数
{
printf（"栈的共享实验\n"）;
printf（"==================================\n"）;
printf（"1.栈的建立\n"）;
printf（"2.栈的共享输入\n"）;
printf（"3.栈单个的输出\n"）;
printf（"4.栈的检测\n"）;
printf（"0.退出实验\n"）;
printf（"==================================\n"）;
}
voidmain（）//主函数
{
inth,k,l=0;//定义’l’为标志，判断是否已建栈，如未建立l=0，否则l=1
chari;
sqstack*s;
for（;;）
{
menu（）;
printf（"请选择0--4：
"）;
scanf（"%d",&h）;
if（h<0||h>4）
{
printf（"\n输人错误!
\n"）;
printf（"Enter'y'tocontunie:
"）;
scanf（"%s",&i）;
system（"cls"）;
continue;
}
else
switch（h）
{
case1:
system（"cls"）;
printf（"**********************************************\n"）;
printf（"*栈的建立*\n"）;
printf（"**********************************************\n"）;
printf（"\n"）;
s=init（s）;//栈的建立
printf（"Enter'y'tocontunie:
"）;
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'tocontunie:
"）;
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"）;
return0;
}
}
}
五、运算结果
结果一：
0号栈输入元素（1，2，3，4，7，8，10），1号栈输入元素（0，5，6）
栈的共享实验
1.栈的建立
2.栈的共享输入
3.栈单个的输出
4.栈的检测
1.退出实验
请选择0--4：
1（回车）
*栈的建立*
Enter‘y’tocontinue：
y（回车）
*栈的共享输入*
请选择输入方向，正向（0），方向
（1），结束
（2）:
0（回车）
请输入数据：
12347810–1（回车）
请选择输入方向，正向（0），方向
（1），结束
（2）:
1（回车）
请输入数据：
056–1（回车）
请选择输入方向，正向（0），方向
（1），结束
（2）:
2（回车）
Enter‘y’tocontinue：
y（回车）
*栈的检测*
请选择输入方向，正向（0），方向
（1），结束
（2）:
0（回车）
正向数据为：
12347810
请选择输入方向，正向（0），方向
（1），结束
（2）:
1（回车）
反向数据为：
056
请选择输入方向，正向（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.栈的检测
2.退出实验
请选择0--4：
0（回车）
*再见*
按任意键继续……
结果二：
还未建立栈就输入数据
栈的共享实验
1.栈的建立
2.栈的共享输入
3.栈单个的输出
4.栈的检测
1.退出实验
请选择0--4：
2（回车）
*栈的共享输入*
栈还未建立！
Enter‘y’tocontinue：
y（回车）
结果三：
输入的数据过多时
栈的共享实验
1.栈的建立
2.栈的共享输入
3.栈单个的输出
4.栈的检测
1.退出实验
请选择0--4：
1（回车）
*栈的建立*
Enter‘y’tocontinue：
y（回车）
*栈的共享输入*
请选择输入方向，正向（0），方向
（1），结束
（2）:
0（回车）
请输入数据：
1234567891011–1（回车）
两栈均满，不能进栈！
请选择输入方向，正向（0），方向
（1），结束
（2）:
2（回车）
Enter‘y’tocontinue：
y（回车）
六、调试小结
函数init（sqstack*s）中少了一条s=（sqstack*）malloc（sizeof（sqstack））语句，这就导致了栈的内存空间无法分配，所以执行出错。
在程序中多加了get（sqstack*s,intl）、check（sqstack*s）、print（sqstack*s）三个函数以便与栈的输入输出以及对栈的检测（不出栈）。
为了在栈的输入之前判断是否已经建栈，在主函数中定义了一个l并定义为0，当l=0时表示还未建栈，l=1时表示已经建栈。
所以只要将l的值传入get（sqstack*s,intl）函数中就可以判断在此之前是否已经建栈。
七、疑问
对标志l的赋值只能放在建栈函数s=init（s）之后，而不能放在它的前面。
如下：
printf（"\n"）;
s=init（s）;
printf（"Enter'y'tocontunie:
"）;
scanf（"%s",&i）;正确
printf（"\n"）;
l=1;
system（"cls"）;
printf（"\n"）;
l=1;
s=init（s）;
printf（"Enter'y'tocontunie:
"）;
scanf（"%s",&i）;错误！
l的值任然为0，不赋值为1
printf（"\n"）;
system（"cls"）;
Welcome!
!
!
欢迎您的下载，
资料仅供参考！
升级会员 