栈的顺序和链式存储的表示和实现.docx

实验三栈的顺序和链式存储的表示和实现

实验目的：
熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。
掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。
实验内容：
栈的顺序表示和实现
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。
初始化顺序栈
插入一个元素
删除栈顶元素
取栈顶元素
便利顺序栈
置空顺序栈
#include<stdio.h>
#include<stdlib.h>
#defineMAXNUM20
#defineelemtypeint
//定义顺序栈的存储结构
typedefstruct
{
elemtypestack[MAXNUM];
inttop;
}sqstack;
//初始化顺序栈
voidinitstack(sqstack*p)
{
if(!p)
printf("error");
p->top=-1;
}
//入栈
voidpush(sqstack*p,elemtypex)
{

}

//出栈
elemtypepop(sqstack*p)
{

}

//获取栈顶元素
elemtypegettop(sqstack*p)
{
elemtypex;
if(p->top!=-1)
{
x=p->stack[p->top];
returnx;
}
else
{
printf("Underflow!\n");
return0;
}
}

//遍历顺序栈
voidoutstack(sqstack*p)
{
inti;
printf("\n");
if(p->top<0)
printf("这是一个空栈！\n");
for(i=p->top;i>=0;i--)
printf("第%d个数据元素是：%6d\n",i,p->stack[i]);
}

//置空顺序栈
voidsetempty(sqstack*p)
{
}

//主函数
main()
{
sqstack*q;
inty,cord;
elemtypea;
do
{
printf("\n第一次使用必须初始化！\n\n");
printf("\n主菜单\n");
printf("\n1初始化顺序栈\n");
printf("\n2插入一个元素\n");
printf("\n3删除栈顶元素\n");
printf("\n4取栈顶元素\n");
printf("\n5置空顺序栈\n");
printf("\n6结束程序运行\n");
printf("\n----------------------------------\n");
printf("请输入您的选择（1,2,3,4,5,6）");
scanf("%d",&cord);
printf("\n");
switch(cord)
{
case1:
{
q=(sqstack*)malloc(sizeof(sqstack));
initstack(q);
outstack(q);
}break;
case2:
{
printf("请输入要插入的数据元素：a=");
scanf("%d",&a);
push(q,a);
outstack(q);
}break;
case3:
{
pop(q);
outstack(q);
}break;
case4:
{
y=gettop(q);
printf("\n栈顶元素为：%d\n",y);
outstack(q);
}break;
case5:
{
setempty(q);
printf("\n顺序栈被置空!\n");
outstack(q);
}break;
case6:
exit(0);
}
}
while(cord<=6);
}
栈的链式表示和实现
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。
初始化链栈
入栈
出栈
取栈顶元素
置空链栈
遍历链栈
参考代码：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#definenull0
typedefintelemtype;
typedefstructstacknode
{
elemtypedata;
stacknode*next;
}stacknode;

typedefstruct
{
stacknode*top;
}linkstack;

//初始化链栈
voidinitstack(linkstack*s)
{
s->top=null;
printf("\