数据结构实验——栈和队列.doc

《数据结构实验——栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2008级数据结构实验报告实验名称：实验二——栈和队列学生姓名：班级：班内序号：学号：日期：2009年11月7日1．实验要求根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构2.1.1共享栈2.1.2链栈2.2关键算法分析2.2.1共享栈开辟一个空间，两个栈共享。top1和top2分别为栈1和栈2的栈顶指针。Stack_Size为整个数组空间的大小；栈1的底固定在下标为0的一端；栈

2、2的底固定在下标为StackSize-1的一端。如果是压栈，则栈1的top1加1，栈2的top2减1；如果是出栈，则栈1的top1减1，栈2的top2加1。压栈：1、如果栈满，则抛出上溢异常；2、判断是插在栈1还是栈2；2.1若是在栈1插入，则栈顶指针top1加1，在top1处填入x；2.1若是在栈2插入，则栈顶指针top2减1，在top2处填入x；时间复杂度为O（1）出栈：1、判断是在栈1删除还是在栈2删除。2、若是在栈1删除，则2.1若栈1为空栈，抛出下溢异常；2.2删除并返回栈1的栈顶元素；3、若是在栈2删除，则3.1若栈2为空栈，

3、抛出下溢异常；3.2删除并返回栈2的栈顶元素；时间复杂度为O（1）2.2.2链栈链栈在压栈的时候先创造一个新的结点，将要加入的元素作为它的元素。将top->next指向这个新的结点。top指向这个新的结点。在出栈的时候，先构造一个工作节点，把当前的栈顶结点赋给它。将栈顶结点摘链，并释放工作结点。压栈：1、工作指针p初始化；2、生成一个元素值为x的新结点；3、将新结点s插入到结点p之后；时间复杂度为O（1）aia1∧topxs①②top出栈：1、判断链栈是否为空；2、工作指针初始化；3、x暂存被删元素值；4、top下移；5、释放工作指针；时

4、间复杂度为O（1）ai-1aia1∧toptopp3.程序运行结果3.1共享栈开始A、B初始化输入num1,data1溢出输出A、B输入num2输出A、B输出异常结束链栈：开始初始化压栈出栈输出链栈输出链栈结束4.总结1、通过实验知道了，如果时两个数据类型相同的栈，可以公用一个数组来节约内存空间。如果他们时此消彼长的变化，则这段内存空间得到了很好的应用。2、利用链表的简化形式可以将栈存储为链栈。链栈比起顺序栈和共享站的好处是，他没有上溢的问题，当栈使用的过程中元素个数变化较大的时候，用链栈时比较适宜的。3、在编写和调试程序过程中遇到的问题

5、以及解决方法：（1）在做链栈的时候，由于没有定义Node，导致程序总时出现很多错误，检查后添加结构体Node的定义，解决了问题。（2）在写链栈的print（）函数的时候，设置了工作指针p，但是输出的时候总是只输出一个数，检查后发现，时因为输出语句写成了“cout<data;p++”，这就导致了虽然工作指针p的位置改变了，但是控制输出的top并没有改变，所以输出不会改变。（3）每次Push的时候，总是两个元素被同时删去，检查了各个函数，均没有发现问题。最后，终于发现，是主函数中Push函数的两次调用导致了这个问题的发生。4、有待

6、提高：异常的处理。