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

《北邮数据结构实验报告实验二含源码》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验二——栈和队列学生姓名：申宇飞班级：2012211103班内序号：03学号：2012210064日期：2013年11月18日1．实验要求1.1实验目的：通过选择下面五个题目之一进行实现，掌握如下内容：Ø进一步掌握指针、模板类、异常处理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4

2、、实现一个链队列编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。第7页北京邮电大学信息与通信工程学院datanexta(n)top栈顶a(n-1)a2^a1栈底关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1）Node*s=newNode;2）p->data=x;3）p->next=to

3、p;4）top=p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1）if(Empty())throw"下溢";2）Tx=top->data;3）Node*p=top;4）top=top->next;5）eletep;三、链栈的取栈顶元素第7页北京邮电大学信息与通信工程学院算法步骤：自然语言描述:1、 判断栈是否为空2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(Empty())throw"下溢";2)Node

4、*p=top;3)cout<data;四、遍历链栈元素算法步骤：自然语言描述：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）structNode*p=top;3）top=top->ne

5、xt;4）deletep;时间复杂的：O(1)。3.程序运行结果程序截图第7页北京邮电大学信息与通信工程学院链栈：1、测试主函数流程：流程图如图1所示开始1,2,3按照先后入栈遍历从栈顶开始遍历出栈操作遍历获取栈顶元素结束图1流程图示意图2、测试条件：问题规模n=3，数组元素1,2,3.3、测试结论：从栈顶开始遍历123入栈：321从栈顶开始遍历出栈操作：21栈顶元素：2第7页北京邮电大学信息与通信工程学院4.总结1、调试时出现的问题及解决的方法连接头文件时，头文件若改名，需将main.cpp中的include也改名，同时重新编译project，否则

6、会出错。2、心得体会这次选择的题目非常基本，是链栈的基本实现，相对也比较容易，但却是很基础的，有些细节部分是值得高度重视的，也是容易出错的地方。对这些基本的特殊线性表的测试与实现是编写较复杂程序的基础，应该牢固掌握它们。 这个实验也让我学会了异常处理的方法3、下一步的改进由于近期处于快到考试阶段，所以没能选择更有难度的题目做，但实际上这道题虽然看似简单但在很多地方也是容易出错的。下一步应该改进的更加具有交互性。代码#includeusingnamespacestd;templatestructNode{Tdata;

7、structNode*next;};templateclassLinkStack//定义链栈模板类{public:LinkStack(){top=NULL;}//构造函数，初始化空栈~LinkStack();//析构函数voidPrintStack();//按次序遍历voidPush(Tx);//入栈操作TPop();//出栈操作TGetTop();//查找栈顶元素boolEmpty(){return(NULL==top)?true:false;}//判别栈是否为空private:structNode*top;//栈顶指针

8、};template第7页北京邮电大学信息与通信工程学院voidLinkStack::