发布时间 : 星期二 文章数据结构实验二题目一栈和队列实验报告更新完毕开始阅读
.
数据结构实验报告
实验名称: 实验2——栈和队列 学生姓名: 班 级: 班内序号: 学 号: 日 期: 一、 实验要求
1、实验目的: 进一步掌握指针、模板类、异常处理的使用
掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力
2、实验内容:
根据栈和队列的抽象数据类型的定义,按要求实现一个栈或一个队列。 要求: 实现一个共享栈 实现一个链栈 实现一个循环队列 实现一个链队列
编写测试main()函数测试线性表的正确性 二、程序分析 2.1 存储结构
顺序栈、链栈和顺序队列
.
.
顺序栈 链栈 顺序队列 2.2 关键算法分析 A、实现一个共享栈: a、伪代码实现
入栈操作:如果栈满,则抛出上溢异常;
判断是插在栈1还是栈2,如果在栈1插入,则栈顶指针top1加1,在top1处
填入x,如果在栈2插入,则栈顶指针top2加1,在top2处填入x。
出栈操作:如果栈空,则抛出下溢异常;
判断是栈1出栈还是栈2,如果是栈1,则输出栈1栈顶元素,并且top1减1,
如果是栈2,则输出栈2栈顶元素,并且top2加1。
得到栈顶元素操作:如果栈空,则抛出下溢异常;
判断是栈1出栈还是栈2,如果是栈1,则输出栈1栈顶元素,如果是栈2,则
输出栈2栈顶元素。
b、算法实现:
void shareseqstack::push(int x,int pushnumber)//进栈操作 {if(top1+1==top2)//异常处理 throw \上溢\
if(pushnumber==1)//判断栈1还是栈2 data[++top1]=x; if(pushnumber==2) data[--top2]=x; }
void shareseqstack::pop(int popnumber)//出栈操作 {if(popnumber==1) //异常处理 { if(top1==-1) throw \下溢\
.
.
else cout< if(popnumber==2) //异常处理 {if(top2==seqstack) throw \下溢\else cout< void shareseqstack::gettop(int getnumber)//得到栈顶元素 {if(getnumber==1) //判断栈1还是栈2 {if(top1==-1) throw \下溢\异常处理 cout< {if(top2==seqstack) throw \下溢\cout< B、实现一个链栈 插入 删除 a伪代码实现 入栈:生成新结点,对新结点赋值,新结点的指向原栈顶指针,修改栈顶指针为新结点。 出栈:判断若为空栈抛出下溢异常,保存栈顶元素,建立新结点,保存栈顶指针,修改栈顶指针为原栈顶指针的下一个结点,删除栈顶指针并输出栈顶元素。 b、算法实现: void linkstack::push(int x)//进栈操作 {Node*p=new Node;//定义新结点 . . p->data=x; p->next=top; top=p; } void linkstack::pop()//出栈操作 {if(empty()) throw \下溢\异常处理 int x=top->data; Node*p=new Node; //定义新结点 p=top; top=top->next; delete p; cout< void linkstack::gettop()//得到栈顶元素 {if(empty()) throw \下溢\异常处理 cout< linkstack::~linkstack()//析构 {while(top) {Node*p=top; top=top->next; delete p; } } C、实现一个循环队列 a、 伪代码实现: .