北邮数据结构实验报告实验二含源码.docx

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验二栈和队列学生姓名： 申宇飞班 级： 2012211103班内序号： 03学 号： 2012210064日 期： 2013年11月18日1实验要求1.1实验目的：通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。 要求：1、 实现一个共享栈2、 实现一个链栈3、 实现一个循环队列4、 实现一个链队列编写测试main()函数测试线性表的正确性。2. 程序分析 2.1 存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。 data next a(n) top 栈顶a(n-1) a2a1 栈底 关键算法分析链栈：一、 入栈操作算法步骤： 自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1）Node * s = new Node;2）p-data = x;3）p-next = top;4）top = p;二、出栈操作算法步骤：自然语言描述：1、 判断栈是否为空2、 保存栈顶结点的数据域3、 定义指针p指向栈顶结点4、 栈顶指针指向下一个结点5、释放p结点伪代码描述：1）if(Empty()throw下溢;2）T x = top-data;3）Node * p = top;4）top = top-next;5）elete p; 三、 链栈的取栈顶元素 算法步骤： 自然语言描述:1、判断栈是否为空 2、定义指针p指向栈顶结点 3、返回栈顶元素的值，不删除 伪代码描述1)if(Empty()throw下溢;2)Node*p=top;3)coutdata;四、遍历链栈元素算法步骤： 自然语言描述：1、 定义指针p指向栈顶结点2、 判断栈是否为空3、 返回栈元素的值4、 把下一个指针的值赋给p伪代码描述：1）Node*p = top;2）while(p != NULL)3）cout data ;4）p = p-next; 五、析构函数 算法步骤： 自然语言描述：1、 判断栈顶指针是否为空2、 定义指针p指向栈顶结点3、 把下一个指针的值赋给栈顶指针4、 释放要释放的指针 伪代码描述：1）while(top) 2）struct Node * p = top; 3）top = top-next; 4）delete p;时间复杂的：O(1)。3. 程序运行结果程序截图链栈：1、 测试主函数流程：流程图如图1所示开始1,2,3按照先后入栈遍历从栈顶开始遍历出栈操作遍历获取栈顶元素结束图1 流程图示意图2、 测试条件：问题规模n=3，数组元素1,2,3 .3、 测试结论：从栈顶开始遍历123入栈： 3 2 1 从栈顶开始遍历出栈操作： 2 1 栈顶元素：24. 总结1、 调试时出现的问题及解决的方法连接头文件时，头文件若改名，需将main.cpp中的include也改名，同时重新编译project，否则会出错。2、 心得体会这次选择的题目非常基本，是链栈的基本实现，相对也比较容易，但却是很基础的，有些细节部分是值得高度重视的，也是容易出错的地方。对这些基本的特殊线性表的测试与实现是编写较复杂程序的基础，应该牢固掌握它们。这个实验也让我学会了异常处理的方法3、 下一步的改进由于近期处于快到考试阶段，所以没能选择更有难度的题目做，但实际上这道题虽然看似简单但在很多地方也是容易出错的。下一步应该改进的更加具有交互性。代码#include using namespace std;template struct Node T data; struct Node * next;template class LinkStack /定义链栈模板类public: LinkStack()top = NULL;/构造函数，初始化空栈 LinkStack();/析构函数 void PrintStack();/按次序遍历 void Push(T x);/入栈操作 T Pop();/出栈操作 T GetTop();/查找栈顶元素 bool Empty()return(NULL = top)?true:false;/判别栈是否为空private: struct Node * top;/栈顶指针;template void LinkStack:Push(T x)/入栈操作 struct Node * p = new Node ; p-data = x; p-next = top; top = p;template T LinkStack:Pop()/出栈操作 if(Empty()throw下溢; T x = top-data; struct Node *p = top; top = top-next; delete p;/释放原栈顶结点 return x;template LinkStack:LinkStack()/析构函数 while(top) struct Node * p = top; top = top-next; delete p; template void LinkStack:PrintStack()/按次序遍历栈 Node*p = top; while(p != NULL) cout data next; template /获取栈顶元素T LinkStack:GetTop() Node*p = top; cout data;int main() LinkStack Stack; Stack.Push(1); Stack.Push(2); Stack.Push(3); Stack.Push(4); Stack.Push(5); cout 从栈顶