《数据结构实验二题目一栈和队列实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构实验二题目一栈和队列实验报告.doc（12页珍藏版）》请在三一文库上搜索。
1、数据结构实验报告实验名称： 实验2栈和队列学生姓名： 班 级： 班内序号： 学 号：日 期： 一、 实验要求1、实验目的： 进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力 2、实验内容：根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：实现一个共享栈实现一个链栈实现一个循环队列实现一个链队列编写测试main()函数测试线性表的正确性二、程序分析2.1 存储结构顺序栈、链栈和顺序队列 顺序栈 链栈 顺序队列2.2 关键算法分析A、实现一个共享栈： a、伪代码实现入栈操作：如果栈满，则
2、抛出上溢异常； 判断是插在栈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)
3、/异常处理throw 上溢;if(pushnumber=1)/判断栈1还是栈2data+top1=x;if(pushnumber=2)data-top2=x;void shareseqstack:pop(int popnumber)/出栈操作if(popnumber=1) /异常处理 if(top1=-1) throw 下溢;else coutdatatop1-endl; if(popnumber=2) /异常处理if(top2=seqstack) throw 下溢;else coutdatatop2+endl;void shareseqstack:gettop(int getnumber)/
4、得到栈顶元素if(getnumber=1) /判断栈1还是栈2if(top1=-1) throw 下溢; /异常处理coutdatatop1endl;if(getnumber=2)if(top2=seqstack) throw 下溢;coutdatatop2data=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;coutx ;void linkstack:gettop()/
5、得到栈顶元素if(empty() throw 下溢;/异常处理coutdatanext;delete p;C、实现一个循环队列a、 伪代码实现:入队：判断若为队满，抛出异常，尾指针后移，指向入队元素。出队：判断若为队空，抛出异常，头指针后移，输出队头元素。b、 算法实现void circlequeue:enqueue(int x)/进队操作if(rear+1)%queuesize=front) throw 上溢;/异常处理rear=(rear+1)%queuesize;datarear=x;void circlequeue:dequeue()/出队操作if(rear=front) throw
6、下溢;/异常处理front=(front+1)%queuesize;coutdatafrontendl;void circlequeue:getfront()得到队头元素if(rear=front) throw 下溢;/异常处理coutdata(front+1)%queuesizeendl;void circlequeue:getlength()/得到队列长度cout(rear-front+queuesize)%queuesize)next=new Node;rear=rear-next;rear-data=x;rear-next=NULL;void linkqueue:dequeue()/出
7、队操作Node*p=front-next;front-next=p-next;int x=p-data;delete p;if(!(front-next)rear=front;coutxnext) throw 上溢;/异常处理coutnext-data)next;delete front;front=rear;2.3 其他源代码#includeusing namespace std;struct Node /定义结点int data;struct Node*next;const int seqstack=100;class shareseqstack /定义共享栈 public:sharese
8、qstack();void push(int x,int pushnumber);void pop(int popnumber);void gettop(int getnumber);private:int dataseqstack;int top1;int top2;shareseqstack:shareseqstack()/构造top1=-1;top2=seqstack;void shareseqstack:push(int x,int pushnumber)/进栈操作if(top1+1=top2)/异常处理throw 上溢;if(pushnumber=1)/判断栈1还是栈2data+to
9、p1=x;if(pushnumber=2)data-top2=x;void shareseqstack:pop(int popnumber)/出栈操作if(popnumber=1) /异常处理 if(top1=-1) throw 下溢;else coutdatatop1-endl; if(popnumber=2) /异常处理if(top2=seqstack) throw 下溢;else coutdatatop2+endl;void shareseqstack:gettop(int getnumber)/得到栈顶元素if(getnumber=1) /判断栈1还是栈2if(top1=-1) thr
10、ow 下溢; /异常处理coutdatatop1endl;if(getnumber=2)if(top2=seqstack) throw 下溢;coutdatatop2next=NULL;linkqueue();void enqueue(int x);void dequeue();void getfront();bool empty()return front=rear? true:false;private:Node*front;Node*rear;void linkqueue:enqueue(int x)/进队操作rear-next=new Node;rear=rear-next;rear-
11、data=x;rear-next=NULL;void linkqueue:dequeue()/出队操作Node*p=front-next;front-next=p-next;int x=p-data;delete p;if(!(front-next)rear=front;coutxnext) throw 上溢;/异常处理coutnext-data)next;delete front;front=rear;class linkstack/定义链栈public:linkstack()top=NULL;linkstack();void push(int x);void pop();void gett
12、op();bool empty()return(NULL=top)? true:false;private:struct Node*top;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;coutx ;void linkstack:gettop()/得到栈顶
13、元素if(empty() throw 下溢;/异常处理coutdatanext;delete p;const int queuesize=1000;/定义循环队列class circlequeuepublic:circlequeue()front=rear=0;void enqueue(int x);void dequeue();void getfront();void getlength();bool empty()return front=rear? true:false;private:int dataqueuesize;int front;int rear;void circleque
14、ue:enqueue(int x)/进队操作if(rear+1)%queuesize=front) throw 上溢;/异常处理rear=(rear+1)%queuesize;datarear=x;void circlequeue:dequeue()/出队操作if(rear=front) throw 下溢;/异常处理front=(front+1)%queuesize;coutdatafrontendl;void circlequeue:getfront()得到队头元素if(rear=front) throw 下溢;/异常处理coutdata(front+1)%queuesizeendl;voi
15、d circlequeue:getlength()/得到队列长度cout(rear-front+queuesize)%queuesize)endl;void main()/主函数 linkstack D;D.push(1);/进栈D.push(2);D.push(3);cout链栈的实现：endl出栈顺序为：;D.pop();/出栈D.pop();D.pop();D.push(1);D.push(2);D.push(3);coutendl;cout栈顶元素为：;D.gettop();D.linkstack();/析构coutendl;shareseqstack A;A.push(1,1);A.
16、push(2,1);A.push(3,1);A.push(10,2);A.push(9,2);A.push(8,2);cout共享栈的实现：endl标号为1的栈出栈元素为：;A.pop(1);cout标号为2的栈出栈元素为：;A.pop(2);cout标号为1的栈栈顶元素为：;A.gettop(1);cout标号为2的栈栈顶元素为：;A.gettop(2);coutendl;linkqueue C;cout链队列的实现：endl;C.enqueue(2);C.enqueue(4);C.enqueue(6);cout出队元素为：;C.dequeue();cout队头元素为：;C.getfront
17、();C.linkqueue();coutendl;circlequeue B;B.enqueue(11);B.enqueue(22);B.enqueue(33);B.enqueue(44);B.enqueue(55);cout循环队列的实现：endl;cout出队的元素为：;B.dequeue();cout队头元素为：;B.getfront();cout队列长度为：;B.getlength();3. 程序运行结果 1、流程图2、测试结果4. 总结心得体会实践才能得出真知，在通过上机操作后，才发现了许多在平时上理论课没有想到的方方面面。编写程序时发现很多语法错误，很多英语单词记不熟，有的会记错，程序函数错用等等，以后需多多实践多多上机操作才能解决已有的问题下一步的改进：入栈可以手动输入，这样修改入栈元素就可以不必修改原程序了。