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

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

实验目的：
1. 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。
2. 掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。
实验内容：
1. 栈的顺序表示和实现
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。
（1） 初始化顺序栈
（2） 插入一个元素
（3） 删除栈顶元素
（4） 取栈顶元素
（5） 便利顺序栈
（6） 置空顺序栈
#include
#include
#define MAXNUM 20
#define elemtype int
//定义顺序栈的存储结构
typedef struct
{
elemtype stack[MAXNUM];
int top;
}sqstack;
//初始化顺序栈
void initstack(sqstack *p)
{
if(!p)
printf("error");
p->top=-1;
}
//入栈
void push(sqstack *p,elemtype x)
{

}

//出栈
elemtype pop(sqstack *p)
{

}

//获取栈顶元素
elemtype gettopsqstack *p)
{
elemtype x;
if(p->top!=-1)
{
x=p->stack[p->top];
return x;
}
else
{
printf("Underflow!\n");
return 0;
}
}

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

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

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

typedef struct
{
stacknode *top;
}linkstack;

//初始化链栈
void initstack(linkstack *s)
{
s>top=null;
printf("\n已经初始化链栈!\n");
}
//链栈置空
void setempty(linkstack *s)
{
s->top=null;
printf("\n链栈被置空！\n");
}
//入栈
void pushlstack(linkstack *s,elemtype x)
{

}

//出栈
elemtype poplstack(linkstack *s)
{
}

//取栈顶元素
elemtype stacktop(linkstack *s)
{
if(s->top==0)
{
printf("\n链栈空\n");
exit(-1);
}
return s->top->data;
}

//遍历链栈
void disp(linkstack *s)
{
printf("\n链栈中的数据位：\n");
printf("=======================================\n");
stacknode *p;
p=s->top;
while(p!=null)
{
printf("%d\n",p->data);
p=p->next;
}
printf("=================\n");
}

//主函数
void main()
{
printf("==============链栈操作================\n");
int i,m,n,a;
linkstack *s;
s=(linkstack *)malloc (sizeof(linkstack));
int cord;
do
{
printf("\n第一次使用必须初始化!\n\n");
printf("\n 主菜单 \n");
printf("\n 1 初始化链栈 \n");
printf("\n 2 入栈 \n");
printf("\n 3 出栈 \n");
printf("\n 4 取栈顶元素 \n");
printf("\n 5 置空链栈 \n");
printf("\n 6 结束程序运行 \n");
printf("\n----------------------------------\n");
printf("请输入您的选择（1,2,3,4,5,6）");
scanf("%d",&cord);
printf("\n");
switch(cord)
{
case 1:
{initstack(s);
disp(s);
}break;
case 2:
{printf("输入将要压入链栈的数据的个数:n=");
scanf("%d",&n);
printf("依次将%d个数据压入链栈:\n",n);
for(i=1;i<=n;i++)
{
scanf("%d",&a);
pushlstack(s,a);
}
disp(s);
}break;
case 3:
{
printf("\n出栈操作开始!\n");
printf("输入将要出栈的数据个数:m=");
scanf("%d",&m);
for(i=1;i<=m;i++)
{
printf("\n第%d次出栈的数据是：%d\n",i,poplstack(s));
}break;
}
case 4:
{
printf("\n\n链栈的栈顶元素为:%d\n\n",stacktop(s));
}break;
case 5:
{
setempty(s);
disp(s);
}break;
case 6:exit(0);
}
}while(cord<=6);
}
实验总结：