实验三栈的顺序和链式存储的表示和实现
实验目的:
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 gettop(sqstack *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
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 结束程序运行
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"); \n");
outstack(q);
}break;
case 6:
exit(0);
}
}
while(cord
}
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
{
scanf("%d",&a);
pushlstack(s,a);
}
disp(s);
}break;
case 3:
{
printf("\n出栈操作开始!\n");
printf("输入将要出栈的数据个数:m=");
scanf("%d",&m);
for(i=1;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
}
实验总结:
实验三栈的顺序和链式存储的表示和实现
实验目的:
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 gettop(sqstack *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
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 结束程序运行
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"); \n");
outstack(q);
}break;
case 6:
exit(0);
}
}
while(cord
}
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
{
scanf("%d",&a);
pushlstack(s,a);
}
disp(s);
}break;
case 3:
{
printf("\n出栈操作开始!\n");
printf("输入将要出栈的数据个数:m=");
scanf("%d",&m);
for(i=1;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
}
实验总结: