数据结构实验二题目一栈和队列实验报告Word格式.docx
《数据结构实验二题目一栈和队列实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验二题目一栈和队列实验报告Word格式.docx（16页珍藏版）》请在冰点文库上搜索。
2.2关键算法分析
A、实现一个共享栈：
a、伪代码实现
入栈操作：
如果栈满，则抛出上溢异常；
判断是插在栈1还是栈2,如果在栈1插入，则栈顶指针topi加1,在topi处填入X，如果在栈2插入，则栈顶指针top2加1,在top2处填入X。
出栈操作：
如果栈空，则抛出下溢异常；
判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，并且top1减1，
如果是栈2，则输出栈2栈顶元素，并且top2加1。
得到栈顶元素操作：
判断是栈1出栈还是栈2，如果是栈1,则输出栈1栈顶元素，如果是栈2,则
输出栈2栈顶元素。
b、算法实现：
voidshareseqstack:
:
push（intx,intpushnumber）//进栈操作
{if（top1+1==top2）〃异常处理
throw"
上溢”;
if（pushnumber==1）〃判断栈1还是栈2
data[++top1]=x;
if（pushnumber==2）
data[__top2]=x;
}
pop（intpopnumber）//出栈操作
{if（popnumber==1）//异常处理
{if（top1==-1）throw"
下溢"
;
elsecout<
<
data[top1--]<
endl;
if（popnumber==2）//异常处理
{if（top2==seqstack）throw"
data[top2++]<
gettop（intgetnumber）//得至U栈顶元素
{if（getnumber==1）//判断栈1还是栈2
{if（top1==-1）throw"
//异常处理cout<
data[top1]<
if（getnumber==2）
cout<
data[top2]<
B、实现一个链栈
插入删除
a伪代码实现
入栈：
生成新结点，对新结点赋值，新结点的指向原栈顶指针，修改栈顶指针为新结点。
出栈：
判断若为空栈抛出下溢异常，保存栈顶元素，建立新结点，保存栈顶指针，修改栈顶指针为原栈顶指针的下一个结点，删除栈顶指针并输出栈顶元素。
b、算法实现:
voidlinkstack:
push（intx）//进栈操作
{Node*p=newNode;
//定义新结点
p_>
data=x;
next=top;
top=p;
voidlinkstack:
pop（）〃出栈操作{if（empty（））throw"
下溢"
//异常处理intx=top->
data;
Node*p=newNode;
//定义新结点
p=top;
top=top->
next;
deletep;
x<
gettop（）〃得到栈顶元素{if（empty（））throw"
top->
data<
linkstack:
~linkstack（）〃析构
{while（top）
{Node*p=top;
C、实现一个循环队列
入队：
判断若为队满，抛出异常，尾指针后移，指向入队元素。
出队：
判断若为队空，抛出异常，头指针后移，输出队头元素。
b、算法实现
voidcirclequeue:
enqueue（intx）〃进队操作
{if（（rear+1）%queuesize==front）throw"
上溢”;
〃异常处理rear=（rear+1）%queuesize;
data[rear]=x;
dequeue（）〃出队操作
{if（rear==front）throw"
//异常处理
front=（front+1）%queuesize;
data[front]<
getfront（）得到队头元素
data[（front+1）%queuesize]<
getlength（）〃得到队列长度
{cout<
（（rear-front+queuesize）%queuesize）<
D、实现一个链队列
voidlinkqueue:
enqueue（intx）//进队操作
{rear->
next=newNode;
rear=rear->
rear->
next=NULL;
dequeue（）〃出队操作{Node*p=front->
front->
next=p->
intx=p->
if（!
（front->
next））rear=front;
getfront（）〃得到头结点元素{if（!
（front->
next））throw"
〃异常处理cout<
（front->
next->
data）<
linkqueue:
~linkqueue（）〃析构
{while（front）
{rear=front->
deletefront;
front=rear;
2.3其他
源代码
#include<
iostream>
usingnamespacestd;
structNode//定义结点
{
intdata;
structNode*next;
};
constintseqstack=100;
classshareseqstack//定义共享栈
{public:
shareseqstack（）;
voidpush（intx,intpushnumber）;
voidpop（intpopnumber）;
voidgettop（intgetnumber）;
private:
intdata[seqstack];
inttop1;
inttop2;
shareseqstack:
shareseqstack（）〃构造{top仁-1;
top2=seqstack;
{if（top1+^=top2）〃异常处理
{if（popnumber==1）//异常处理
elsecout<
{if（top仁=-1）throw"
//异常处理
cout<
classlinkqueue//定义链队列
linkqueue（）{front=rear=newNode;
front->
~linkqueue（）;
voidenqueue（intx）;
voiddequeue（）;
voidgetfront（）;
boolempty（）{returnfront==rear?
true:
false;
Node*front;
Node*rear;
rear=rear->
{Node*p=front->
classlinkstack//定义链栈
linkstack（）{top=NULL;
~linkstack（）;
voidpush（intx）;
voidpop（）;
voidgettop（）;
boolempty（）{return（NULL==top）?
}private:
structNode*top;
voidlinkstack:
push（intx）//进栈操作{Node*p=newNode;
//定义新结点p->
pop（）//出栈操作
{if（empty（））throw"
intx=top->
//定义新结点p=top;
gettop（）〃得到栈顶元素
constintqueuesize=1000;
〃定义循环队列
classcirclequeue
circlequeue（）{front=rear=O;
voidgetlength（）;
boolempty（）{returnfront=rear?
intdata[queuesize];
intfront;
intrear;
上溢"
//异常处理rear=（rear+1）%queuesize;
front=（front+1）%queuesize;
voidmain（）〃主函数
{linkstackD;
D.push
（1）;
〃进栈
D.push
（2）;
D.push（3）;
链栈的实现：
endl<
出栈顺序为：
D.pop（）;
//出栈
栈顶元素为：
D.gettop（）;
D.~linkstack（）;
〃析构
shareseqstackA;
A.push（1,1）;
A.push（2,1）;
A.push（3,1）;
A.push（10,2）;
A.push（9,2）;
A.push（8,2）;
共享栈的实现：
标号为1的栈出栈元素为:
A.pop
（1）;
标号为2的栈出栈元素为：
A.pop
（2）;
标号为1的栈栈顶元素为：
A.gettop
（1）;
标号为2的栈栈顶元素为：
A.gettop
（2）;
linkqueueC;
链队列的实现：
endl;
C.enqueue
（2）;
C.enqueue（4）;
C.enqueue（6）;
出队元素为：
C.dequeue（）;
队头元素为：
C.getfront（）;
C.~linkqueue（）;
circlequeueB;
B.enqueue（11）;
B.enqueue（22）;
B.enqueue（33）;
B.enqueue（44）;
B.enqueue（55）;
循环队列的实现：
出队的元素为：
B.dequeue（）;
B.getfront（）;
队列长度为：
B.getlength（）;
3.程序运行结果
1、流程图
2、测试结果
出楼.切弓;
^521
視顶元素为；
工
帝r如曲吃匕拦1.点勺3極号为左的曲岀損兀■青：
・标号为1的桂甩顶元奮为：
i标号为工的呼甩唄元素冷；
9
%EKM的吳观：
出限元玉再：
a
I：
.1*
縞不臥列的实规：
出狀的元Jf>
5：
II
l；
L*F盂当iZ
飢列左庭为:
*
PT+JSK岬tcecntlrHJ*,
4.总结
心得体会
实践才能得出真知，在通过上机操作后，才发现了许多在平时上理论课没有想到的方方面面。
编写程序时发现很多语法错误，很多英语单词记不熟，有的会记错，程序函数错用等等，以后需多多实践多多上机操作才能解决已有的问题
下一步的改进：
入栈可以手动输入，这样修改入栈元素就可以不必修改原程序了。
升级会员 