天大数据结构_实验作业二_栈(顺序栈)+队列(循环队列).doc

《天大数据结构_实验作业二_栈(顺序栈)+队列(循环队列).doc》由会员分享，可在线阅读，更多相关《天大数据结构_实验作业二_栈(顺序栈)+队列(循环队列).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验作业二：栈（顺序栈）和队列（循环队列）1. 将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top1减1得到新的栈顶位置。当top0+1 = top1时或top0 = top1-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。2. 求fibonacci数列算法，并

2、比较。（递归+非递归）（非递归方法可查阅其他资料）编写实习报告要求：一、需求分析二、概要设计1.抽象数据类型2.算法三、详细设计程序代码（注释）四、调试分析调试过程中所做的工作，时间复杂度等五、测试结果输入数据和输出数据示例六、说明（如果有）编程语言：C语言或C+语言实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar文件，文件名称为学号_班级_姓名_第几次作业。例如：_六班_张三_第二次作业.rar。实习报告作为本课程的平时成绩。抄袭、雷同，双方均为0分。 第一题：一、 需求分析程序要求建立一个共享栈，分配一个存储空间，两个栈分别位于两头。并实现对两个栈的

3、插入，删除，和判断栈满和栈空。栈的位置不同，所以要求对不同栈的插入和删除采用不同的算法。二、概要设计1.抽象数据类型typedef struct int *base;int *top;int stacksize;stack;2.算法1.建立栈。int instack(stack &s,stack &w,int length)s.base=(int *)malloc(length*sizeof(length);w.base=s.base+length;if(!s.base|!w.base) return 0;elses.top=s.base;w.top=w.base;s.stacksize=le

4、ngth;w.stacksize=length;return 1;2.判断栈空。int isempty(stack s,stack w)if(s.top=s.base&w.top=w.base) return 1;if(s.top=s.base) return 2;if(w.top=w.base) return 3;else return 0;3.判断栈满。int isfull(stack s,stack w)if(s.top+1)=w.top) return 1;else return 0;4.插入元素到左边栈。void push1(stack &s,stack &w, int x)if(s

5、.top+1)=w.top) cout栈满，无法进栈!endl;else*s.top=x;s.top+;5.插入元素到右边栈。void push2(stack &s,stack &w, int x)if(s.top+1)=w.top) cout栈满，无法进栈!endl;else*w.top=x;w.top-;6.左栈元素出栈。void pop1(stack &s,int &x)if(s.top=s.base) cout栈空，无法出栈!endl;else-s.top;x=*s.top;7.右栈元素出栈。void pop2(stack &w,int &x)if(w.top=w.base) cout

6、栈空，无法出栈!endl;elsew.top+;x=*w.top;二、 详细设计采用以上算法后，运用下面主程序：int main()int x,l,pase,choice,pr; /定义变量stack s,w; /定义栈cout请输入共享栈的长度：l; /读取共享栈的长度pase=instack(s,w,l); /依据长度创建空间while(pase!=0)coutn*子菜单*;coutn*1-插入数据到表一*;coutn*2-插入数据到表二*;coutn*3-表一的元素出栈*;coutn*4-表二的元素出栈*;coutn*5-判断栈空*;coutn*6-判断栈满*;coutn*0-退出*;c

7、outn 请输入你的选择（0、1、2、3、4、5、6）：choice; /显示程序的操作提醒，并读入用户的选择switch(choice) /依据不同的选择调用算法，进行操作 case 1: /插入数据到表一coutx;push1(s,w,x);break;case 2: /插入数据到表二coutx;push2(s,w,x);break;case 3: /表一的元素出栈pop1(s,x);cout出栈元素为：xendl;break;case 4: /表二的元素出栈pop2(w,x);cout出栈元素为：xendl;break;case 5: /判断栈空pr=isempty(s,w);if(pr

8、=1) cout左、右栈为空！endl;if(pr=2) cout左栈为空！endl;if(pr=3) cout右栈为空！endl;if(pr=0) cout左、右栈不为空！endl;break;case 6: /判断栈满pr=isfull(s,w);if(pr=1) cout栈满！endl;else cout栈未满！ 2 )二、概要设计1.抽象数据类型无2.算法递归算法int fib1(int x) f(x= 1|x=2) return 1; lse return (fib1(x-1)+fib1(x-2);非递归算法int fib2(int x)int a=1,b=1,num=0,n; if

9、(x= 1|x=2) return 1; for (n=0;nx-2;n+) num=a+b; a=b; b=num; return num;四、 详细设计采用以上算法后，运用下面主程序：int main()int sum1,sum2,x; /定义变量cout请输入想要计算的数：x; /输入需要计算到的数值的最后一位sum1=fib1(x); /调用递归算法sum2=fib2(x); /调用非递归算法cout采用递归算法计算得其fibonacci数列值为：sum1endl;cout采用非递归算法计算得其fibonacci数列值为：sum2endl;system(pause);return 0;四、调试分析根据visual C+6.0编译器的提醒，修正代码错误，然后输入数据进行调试。采用分开不同算法的方式，输入大型数值进行运算，分析复杂度。可以明显看出递归算法的运行速度较慢，时间复杂度更高。五、测试结果