栈的操作实验报告

第 3 页 共 14 页
八、程序组成结构示意图 九、顺序栈程序调试图
第 4 页 共 14 页
第 5 页 共 14 页
十、链栈调试图
第 6 页 共 14 页
十一、链栈源代码
//实现链栈的压栈，弹栈，取栈顶操作 //采用字符型数据存储模式，指针型引用做形参 #include<iostream> #include<malloc.h> using namespace std; typedef char ElemType; typedef struct node {
第 7 页 共 14 页
SqList *p;
p=(SqList *)malloc(sizeof(SqList));
p->data=d;
p->next=m->next;
m->next=p;
return true;
}
bool Pop(SqList *&m,ElemType &d)//弹栈
{
SqList *p;
ElemType data[MaxSize]; int Top;
}SqList; void Init(SqList *&m);//初始化 void Destory(SqList *&m);//销毁栈 bool Push(SqList *&m,ElemType &d);//压栈 bool Pop(SqList *&m,ElemType &d);//弹栈 bool GetTop(SqList *&m,ElemType &d);//取栈顶元素 void Init(SqList *&m)//初始化 {
3
报
告 3 实验数据与结果 10
质
量4
总结
4
互评分
组长评分 教师评分
5
排版
2
6
源
7
程
正确性
63
友好性
4
序8
可读性
4
质9
健壮性
4
量
10
创新与多样性
4
合计 总分
评分人签字
目录
一、 实验题目 ---------------------------------------------------------------------------------------------------- 1 二、 实验目的 ---------------------------------------------------------------------------------------------------- 1 三、 实验内容 ---------------------------------------------------------------------------------------------------- 1 四、 实验要点与要求 ------------------------------------------------------------------------------------------- 1 五、 算法思想 ---------------------------------------------------------------------------------------------------- 1 六、 算法描述及流程图 ---------------------------------------------------------------------------------------- 3 七、 实验数据及实验结果 ------------------------------------------------------------------------------------- 3 八、 程序组成结构示意图 ------------------------------------------------------------------------------------- 4 九、 顺序栈程序调试图 ---------------------------------------------------------------------------------------- 4 十、 链栈调试图 ------------------------------------------------------------------------------------------------- 6 十一、 链栈源代码 ---------------------------------------------------------------------------------------------- 7 十二、 顺序栈源代码 ------------------------------------------------------------------------------------------10
cout<<"
*
2 取栈顶
*"<<endl;
cout<<"
*
3 弹栈
*"<<endl;
cout<<"
*
4 退出
*"<<endl;
cout<<"
********************************"<<endl;
cout<<"请选择:";
cin>>choose;
switch(choose)
break;
case 2:
cout<<"当前栈顶元素为:";
if(GetTop(m,d))
cout<<d;
cout<<endl;
break;
case 3:
cout<<"所有站内元素为:";
while(Pop(m,d))
{
Pop(m,d);
cout<<d<<" ";
}
第 9 页 共 14 页
cout<<endl; break; case 4: cout<<"链栈销毁中...."<<endl; cout<<"销毁完毕!"<<endl; cout<<"感谢使用，再见！\n\n"<<endl; exit(0); } } Destory(m);
重庆工商大学
《数据结构》 课程实验报告封面
专业班级： 12 计算机一班
学 号： 2012131152
学生姓名：
古应波
实验室： 10412
实验题目：
顺序栈、链栈的操作
指导教师：
梁新元
成 绩：
日期：2013 年 10 月 日
第 6 周 星期 3 节次 4-5
评分表
序号
项目
总分 自评分
1
算法思想
2
实
验2
Hale Waihona Puke Baidu
算法描述
if(m->next==NULL)
{ cout<<"
栈已弹空！"<<endl;
return false;
}
p=m->next;
d=p->data;
m->next=p->next;
free(p);
return true;
} void Destory(SqList *m)//销毁栈
{
SqList *p=m,*n=m->next;
第 8 页 共 14 页
SqList *m;
ElemType d;
int choose;
Init(m);
for(;;)
{
cout<<"
********************************"<<endl;
cout<<"
*
欢迎使用链栈
*"<<endl;
cout<<"
*
1 压栈
*"<<endl;
测试压栈数据类型进行测试
序号 测试类型
输入数据
合法数据 非法数据
1,2,a,b, -1 1.5 go
期望输出结果
1,2,a,b, -1 1.5 go
实际输出结 果
1,2,a,b
-
1 进队成功 .5 丢失 g 进队成功 o 丢失
测试结论
测试成功，程 序正确执行 不符合程序 预设的数据 处理类型，程 序执行，但是 得不到期望 的结果
顺序栈的弹栈算法
bool Pop(SqList *&m,ElemType &d)//弹栈
{
if(m->Top==-1)
{ cout<<"\n 栈空！"<<endl;
return false;
}
d=m->data[m->Top];
m->Top--;
return true;
} 链栈的弹栈算法
bool Pop(SqList *&m,ElemType &d)//弹栈
2. 必须采用函数调用
五、算法思想
顺序栈压栈的算法 bool Push(SqList *&m,ElemType &d)//压栈 {
if(m->Top==MaxSize-1) {
cout<<"栈满！"<<endl; return false; } m->Top++; m->data[m->Top]=d; return true; }
ElemType data; struct node *next; }SqList; extern void Init(SqList *&m);//初始化栈 extern bool Push(SqList *&m,ElemType &d);//压栈 extern bool Pop(SqList *&m,ElemType &d);//弹栈 extern void Destory(SqList *m);//销毁栈 extern bool GetTop(SqList *&m,ElemType &d);//取栈顶元素 void Init(SqList *&m)//初始化栈 { m=(SqList *)malloc(sizeof(SqList)); m->next=NULL; } bool Push(SqList *&m,ElemType &d)//压栈 {
链栈的弹栈方式是直接读取当前栈顶指针指向的内存空间的数据，然后释放掉 当前空间。
六、算法描述及流程图
顺序栈、链栈的基本结构体系都一样，都实现栈的初始化，压栈，弹栈和取栈顶元 素、销毁栈操作，其中，压榨、弹栈、取栈顶元素用户可选，初始化、销毁系统自动执 行
4
4
3
3
2
2
1
1
0
栈顶
0
a
初始栈顶
-1
-1
七、实验数据及实验结果
第 1 页 共 14 页
链栈压栈的算法 bool Push(SqList *&m,ElemType &d)//压栈 {
SqList *p; p=(SqList *)malloc(sizeof(SqList)); p->data=d; p->next=m->next; m->next=p; return true; } 顺序栈压栈的时候，由于栈顶指针初始化为-1，故而添加元素前需要将栈顶指 针先+1，再向指定的内存空间储存数据。栈满的条件为 Top 指针等于 MaxSize-1； 链栈由于采用分配内存方式，故而不存在栈满的情况，当需要压榨的时候，需 要新建一个节点，为其分配内存空间，然后插入初始化节点之后。修改相应的 next 域值。
while(n!=NULL)
{
free(p);
p=n;
n=n->next;
}
free(p);
} bool GetTop(SqList *&m,ElemType &d)//取栈顶元素 {
if(m->next==NULL){ cout<<"栈为空！"<<endl;
return false;} SqList *p=m->next; d=p->next->data; return true; } void main() {
{
SqList *p;
if(m->next==NULL)
{ cout<<"
栈已弹空！"<<endl;
return false;
}
p=m->next;
d=p->data;
m->next=p->next;
free(p);
return true;
}
第 2 页 共 14 页
对于顺序栈，由于压栈时是先修改栈顶指针，然后进行赋值，故而弹栈时应该 先读取数据，再修改栈顶指针。
实验报告的内容与要求
一、实验题目
顺序栈、链栈的基本操作
二、实验目的
了解顺序栈、链栈的结构特点及有关概念，掌握其基本操作算法。
三、实验内容
实现顺序栈和链栈的初始化、进栈、出栈、销毁操作
四、实验要点与要求
1. 处理的数据类型即 ElemType 的类型 基本版要求：整型、字符型 扩展版要求：字符串型（基础较好的同学）
{
case 1:
do
{
cout<<"请输入数据:";
cin>>d;
Push(m,d);
if(Push(m,d))
cout<<"压栈成功"<<endl;
cout<<"1.继续压栈"<<endl;
cout<<"0.退出"<<endl;
cout<<"请选择:";
cin>>choose;
}while(choose==1);
}
十二、顺序栈源代码
//实现顺序栈的进栈，出栈，取栈顶元素操作 //采用字符型数据储存模式，指针型引用做形参 #include<iostream> #include<malloc.h> using namespace std; #define MaxSize 50 typedef char ElemType; typedef struct Mysq {