《链队列实验报告》由会员分享，可在线阅读，更多相关《链队列实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、 数据结构与算法实验院 别：计算机科学与信息工程学院年级专业：2014级空间信息与数字技术姓 名：杨哲庆学 号：1420012138评语和成绩: 2015 年 10月 实验3 链队列实验3.1链队列3.1.1实验的主要内容和目的 掌握队列的链式存储结构； 验证链队列的存储结构和基本操作的实现； 验证链队列的操作特性； 掌握链队列的一些基本应用。3.1.2代码LinkQueue.h#if !defined(AFX_LINKQUEUE_H_FC16C47E_48CA_420B_8C0D_216DBF48A867_INCLUDED_)#define AFX_LINKQUEUE_H_FC16C47E_
2、48CA_420B_8C0D_216DBF48A867_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000/*-一定义链队列的结点-*/templatestruct NodeNode* next;T data;/*-一声明链队列类LinkQueue-*/templateclass LinkQueue public: LinkQueue(); /默认构造函数LinkQueue(T a,int n); /将数组存入队列中 virtual LinkQueue(); /析构函数void EnQueue(T x); /将元素x入队T
3、DeQueue(); /将队头元素出队T GetQueueFront(); /取链队列的头元素bool IsEmpty(); /判断是否为空void ShowQueue(); /输出队列中的所有元素private:Node* front,*rear; /创建队头和队尾指针;#endif LinkQueue.cpp#include LinkQueue.h /引用LinkQueue的声明#include /引入输入输出流templateLinkQueue:LinkQueue()Node* s=NULL;s=new Node;s-next=NULL;front=rear=s;templateLink
4、Queue:LinkQueue(T a,int n)Node* p;p=new Node;p-next=NULL;front=rear=p;for(int i=0;in;i+)p=new Node;p-data=ai;p-next=NULL;rear-next=p;rear=p;templateLinkQueue:LinkQueue()Node* p=NULL;while(front!=NULL)p=front-next;delete front;front=p;templatevoid LinkQueue:EnQueue(T x)Node* p;p=new Node;p-data=x;p-n
5、ext=NULL;rear-next=p;rear=p;templateT LinkQueue:DeQueue()T x;if( IsEmpty() )cout队空，不能进行出队操作！endl;exit(0);Node* p;p=front-next;x=p-data; /暂存队头元素front-next=p-next; /将队头元素所在结点摘链if(p-next=NULL) /判断出队前队列长度是否为1rear=front;delete p;return x;templateT LinkQueue:GetQueueFront()if( IsEmpty() )cout队空，停止运行！endl;
6、exit(0);Node* p;p=front-next;return p-data;templatebool LinkQueue:IsEmpty()return (rear=front);templatevoid LinkQueue:ShowQueue()Node* p;p=front-next;while(p)coutdatanext;coutendl;Test.cpp#includeLinkQueue.cpp#includeusing namespace std;int main()int a6=2,3,4,5,6,7; /创建数组a6LinkQueue q(a,4); /将数组存入队列
7、中q.ShowQueue(); /输出队列中所有元素if( q.IsEmpty() ) /判断是否为空cout队列为空endl; elsecout队列非空endl;cout将元素6,7,8,9,10执行入队操作：endl;q.EnQueue(6); q.EnQueue(7);q.EnQueue(8);q.EnQueue(9);q.EnQueue(10);q.ShowQueue();cout查看队头元素：endl;coutq.GetQueueFront()endl; /取队头元素cout执行出队操作：endl;q.DeQueue(); /出队操作cout查看队列的所有元素：endl;q.Show
8、Queue(); /输出队列中所有元素return 0; 3.1.3总结（1）实验过程中碰到了3个比较有意义的错误，分别是错误a、错误b和错误c：a. 错误：NULL未定义。如图1-1。图1-1修正：在LinkQueue.cpp文件首部加入代码”#inlcude”。如图1-2。图1-2b.错误：函数声明是无返回值，可在函数体内却有return 返回一个x。错误代码如图2-1。图2-1改正：将void改成与x同样的数据类型即可。如图2-2。图2-2c.错误：数组a定义的长度小于实际长度。如图3-1。图3-1改正：将原长度3改为大于数组中的实际个数的数即可。如图3-2。图3-2（2）实验过程使用的主要知识点a.建立一个空队列。b.对已建立的队列进行入队、出队、取队头元素等基本操作。c.利用头指针和尾指针对队列进行操作。（3）实验中遇到的不理解或体会比较深的问题a.队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。队列中的元素具有先进先出的特性。b.链队列通常设置附设头结点，并设置队头指针指向头结点，队尾指针指向终端节点。c.链队列基本操作的实现本质上也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度为O(1)。
