链栈顺序栈实验报告.docx
《链栈顺序栈实验报告.docx》由会员分享，可在线阅读，更多相关《链栈顺序栈实验报告.docx（11页珍藏版）》请在冰点文库上搜索。
链栈顺序栈实验报告
第五次实验报告——
顺序栈、链栈的插入和删除
一需求分析
1、在演示程序中，出现的元素以数字出现定义为int型，
2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上
3、顺序栈的程序执行的命令包括如下：
（1）定义结构体
（2）顺序栈的初始化及创建
（3）元素的插入
（4）元素的删除
（5）顺序栈的打印结果
3、链栈的程序执行的命令包括如下：
（1）定义结构体
（2）链栈的初始化及创建
（3）元素的插入
（4）元素的删除
（5）链栈的打印结果
二概要设计
1、顺序栈可能需要用到有序表的抽象数据类型定义：
ADTList{
数据对象:
D={ai|ai∈ElemL,i=1,2,...,n,n≥0}
数据关系:
R1={|ai-1,ai∈D,i=2,...,n}
基本操作：
InitStack（SqStack&S）
操作结果：
构造一个空栈
Push（L,e）
操作结果：
插入元素e为新的栈顶元素
StatusPop（SqStack&S）
操作结果：
删除栈顶元素
}ADTList；
2、链栈可能需要用到有序表的抽象数据类型定义：
ADTList{
数据对象:
D={ai|ai∈ElemL,i=1,2,...,n,n≥0}
数据关系:
R1={|ai-1,ai∈D,i=2,...,n}
基本操作：
LinkStack（SqStack&S）
操作结果：
构造一个空栈
StatusPush（L,e）
操作结果：
插入元素e为新的栈顶元素
StatusPop（SqStack&S）
操作结果：
删除栈顶元素
}ADTList；
3、顺序栈程序包含的主要模块：
（1）已给定的函数库：
（2）顺序栈结构体：
（3）顺序栈初始化及创建:
（4）元素插入
（5）元素删除
（6）主程序：
4、链栈程序包含的主要模块：
（1）已给定的函数库：
（2）链栈结构体：
（3）链栈初始化及创建:
（4）元素插入
（5）元素删除
（6）主程序：
三详细设计
线性栈：
结构体
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
typedefstruct
{
int*base;//在构造栈之前和销毁之后，base的值为NULL
int*top;//栈顶指针
intstacksize;//当前已分配的存储空间，以元素为单位
}SqStack#include"Base.h"
主函数
#include"construction.h"
#include"stack_operation.c"
intmain（）
{
SqStackS;
intchoice,e;
S=InitStack（）;
S=Input_Sq（S）;
printf（"请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
{
printf（"请输入插入元素的值e="）;
scanf（"%d",&e）;
S=Push（S,e）;
printf（"执行入栈操作后的线性栈为"）;
Print_Stack（S）;
};break;
case2:
{S=Pop（S）;
printf（"执行出栈操作后的线性栈为"）;
Print_Stack（S）;
};break;
default:
printf（"您输入的值不合法"）;
}
}
线性栈的创建
SqStackInitStack（）//线性栈的创建
{
SqStackS;
S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;//分配存储空间
if（!
S.base）
exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnS;
}
输入函数
SqStackInput_Sq（SqStackS）//输入函数
{
intn,i;
printf（"请输入元素个数n="）;
scanf（"%d",&n）;
printf（"请输入%d个元素",n）;
for（i=0;i{
scanf（"%d",S.top）;
S.top++;
}
returnS;
}
进栈函数
SqStackPush（SqStackS,inte）//进栈函数
{
if（S.top-S.base>=S.stacksize）//判断栈是否为满，追加存储空间
{
S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（int））;
if（!
S.base）
exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;//插入元素
returnS;
}
出栈函数
SqStackPop（SqStackS）//删除函数
{
inte;
if（S.top==S.base）
printf（"线性栈为空"）;
e=*--S.top;
returnS;
}
输出函数
voidPrint_Stack（SqStackS）//打印函数
{
inti;
while（S.base!
=S.top）
{
for（i=0;i{
S.top--;
printf（"%5d",*S.top）;
}
printf（"\n"）;
}
库函数
*Base.h（程序名）*/
#include
#include
#include/*malloc（）等*/
#include/*INT_MAX等*/
#include/*EOF（=^Z或F6）,NULL*/
#include/*atoi（）*/
#include/*eof（）*/
#include/*floor（）,ceil（）,abs（）*/
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSEl
链栈程序：
结构体
typedefstructSNode//建立链表结构体
{
intdata;
structSNode*next;
}SNode,*LinkStack;
主函数
#include"Base.h"
#include"construction.h"
#include"LinkStack_operation.c"
intmain（）
{
LinkStackS;
intchoice,e;
S=Creatlist_Stack（）;
printf（"请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
{
printf（"请输入插入元素的值e="）;
scanf（"%d",&e）;
S=Push（S,e）;
printf（"执行操作入栈后的线性栈为"）;
Print_Stack（S）;
};break;
case2:
{
S=Pop（S）;
printf（"执行出栈操作后的线性栈为"）;
Print_Stack（S）;
};break;
default:
printf（"您输入的值不合法\n"）;
}
}
创建链栈函数
LinkStackCreatlist_Stack（）//创建一个链栈
{
LinkStackS;
LinkStackP;
inti,n;
S=（LinkStack）malloc（sizeof（SNode））;
S->next=NULL;/*先建立一个链栈*/
printf（"请输入元素个数n="）;
scanf（"%d",&n）;
printf（"请输入%d个数据\n",n）;
i=0;
scanf（"%d",&S->data）;
for（i=1;i{
P=（LinkStack）malloc（sizeof（SNode））;/*生成新结点*/
P->next=S;
S=P;
scanf（"%d",&S->data）;/*输入元素值*/
}
returnS;
}
入栈函数
LinkStackPush（LinkStackS,inte）
{
LinkStackP;
if（S==NULL）
returnERROR;
P=（LinkStack）malloc（sizeof（SNode））;
P->data=e;
P->next=S;
S=P;
returnS;
}
出栈函数
LinkStackPop（LinkStackS）
{
LinkStackP,Q;
P=S;
S=S->next;
free（P）;
returnS;
}
输出函数
voidPrint_Stack（LinkStackS）
{
while（S）
{
printf（"%5d",S->data）;
S=S->next;
}
printf（"\n"）;
}
库函数
*Base.h（程序名）*/
#include
#include
#include/*malloc（）等*/
#include/*INT_MAX等*/
#include/*EOF（=^Z或F6）,NULL*/
#include/*atoi（）*/
#include/*eof（）*/
#include/*floor（）,ceil（）,abs（）*/
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSEl
四调试分析:
输出函数用了语句S->next!
=NULL
改正：
语句S！
=NULL
五用户手册:
看提示内容
六测试结果
线性栈：
1）请输入元素的个数：
4，请输入4个数据1234，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为64321
2）请输入元素的个数：
4，请输入4个数据1234，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为321
链栈：
1）请输入元素的个数：
4，请输入4个数据1234，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为64321
2）请输入元素的个数：
4，请输入4个数据1234，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为321
升级会员 