[IT计算机]数据结构实验设计双端队列

1、 江西农业大学软件学院数据结构实验报告专业班级：软件1104班学生姓名：彭胜学号：20111523指导老师：杨文姬老师联系邮箱：799275381目录一系统简介3二需求分析4三功能分析5四概要设计7五详细设计9六体会心得32实验题目：双端队列双端队列是插入和删除操作可以在两端进行的线性表，表的两端分别称作端点1和端点2.设计双端队列的数据结构，实现入队、出队等基本操作。一系统简介双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2（如下图(a)所示）。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列，如下图(b)所示。在实际使用中，还可以有输出受限的双

2、端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。 一 尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。 双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。二需求分析1.双端队列定义 双端队列是一个两端都是结尾的队列，是在简单队列数据结构上的改进，其数据结构类似于双向链表，在每头分别设有对头和队尾两个指针；双端队列是一种具

3、有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表两端进行；双端队列在队列的基础上，对其进行了堆栈化;2.双端队列特点 双端队列同时具有队列和栈的性质；双端队列中的元素可以从两端弹出；如果严格禁用右段的操作，双端队列功能就和栈一样；如果严格禁用左段的操作，它的功能就和队列一样；双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。双端队列由程序员是控制的3.双端队列功能 设计双端队列的数据结构，实现入队、出队等基本操作;4.双端队列实验的基本运算 定义双端队列的抽象数据类型；设计存储结构存储双端队列；分析算法的时间

4、性能；双端队列初始化；双端队列清空；双端队列头插入双端队列头取数据双端队列尾插入 双端队列尾取数据 5.双端队列实验的接口要求 用户能输入数据，和程序能有交互 三功能分析该程序主要实现以下5个功能：1. 从队列首输入数据2. 从队列尾输入数据3. 从队列首取数据4. 从队列尾取数据5. 队列清空针对需要实现的功能做出详细的算法设计采用双向队列来实现，队列中有两个指针，一个指针指向队首结点，一个指向队尾结点。定义一个结构体，其中包含一个数据域和两个指针域，数据域用来存放数据，一个指针域用来存放指向前驱结点的指针，另一个指针域用来存放指向后继结点的指针。1.新建结点就是分配一个新的内存空间。2.每

5、次分配空间都需要判断是否能分配到内存空间，如果未得到内存空间则终止当前操作。3.队列中只有头结点，该队列即为空队列。以上3点后面不再重复说明。 (一)从顶部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队首指针指向新建结点，并将新建结点的后继指针指向原队首结点，原队首结点的指针指向新建结点。(二)从顶部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队首结点赋给临时结点。将队首结点的后继指针赋给队列的队首指针，再将队首结点的前驱指针置空。最后返回临时结点或所需要的数据。(三)从底部入队列新建一个结点，如果队列为空，则将队列的队首指针和队

6、尾指针均指向新建结点，如不为空则将队尾指针指向新建结点，并将新建结点的前驱指针指向原队尾结点，原队尾结点的指针指向新建结点。(四)从底部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结点的后继指针置空。最后返回临时结点或所需要的数据。(五)队列清空将队列的队首指针和队尾指针置空即可。操作如下是限定插入和删除操作是在表的两端进行的线性表.这两端分别称为端点1和端点2a1 a2 a3.an 插入删除端1端2队列q=(a1,a2,an)插入删除四概要设计（1）系统功能结构设计 该程序主要实现以下5个功能： 1. 从

7、队列首输入数据 2. 从队列尾输入数据 3. 从队列首取数据 4. 从队列尾取数据 5. 队列清空 6.退出（2）数据结构设计针对需要实现的功能做出详细的算法设计采用双向队列来实现，队列中有两个指针，一个指针指向队首结点，一个指向队尾结点。定义一个结构体，其中包含一个数据域和两个指针域，数据域用来存放数据，一个指针域(front)用来存放指向前驱结点的指针，另一个指针域(rear)用来存放指向后继结点的指针。1.新建结点就是分配一个新的内存空间。2.每次分配空间都需要判断是否能分配到内存空间，如果未得到内存空间则终止当前操作。3.队列中只有头结点，该队列即为空队列。以上3点后面不再重复说明。（

8、3）模块接口设计a. 从顶部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队首指针指向新建结点，并将新建结点的后继指针指向原队首结点，原队首结点的指针指向新建结点。b. 从顶部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队首结点赋给临时结点。将队首结点的后继指针赋给队列的队首指针，再将队首结点的前驱指针置空。最后返回临时结点或所需要的数据。c. 从底部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队尾指针指向新建结点，并将新建结点的前驱指针指向原队尾结点，原队尾结点的指针指向新建结点。d.

9、 从底部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结点的后继指针置空。最后返回临时结点或所需要的数据。e. 队列清空将队列的队首指针和队尾指针置空即可。五详细设计函数的类型：queuenotempty(lqueue q)queueappend(lqueue *q ,datatype x)queuedelete(lqueue *q,datatype *d)queueget双端函数：elementtype front (queue q)取队头元素void push (elementtype x)在队头执行入队

10、操作void pop(queue q)队头执行出队操作elementtype frontappend(queue q)出队并取队头元素elementtype rear(queue)取队尾元素void inject (elementtype x,queue q)在队尾执行入队操作void eject(queue q)在队尾执行出队操作element type rearandeject（queue q）双端队列数据类型typedef struct qnodedatatype data;struct qnode *next;lqnode;typedef struct lqnode *front;lq

11、node *rear;lqueue; 链式队列的操作实现： void queueinitiate(lqueue *q) /*初始化*/q-rear=null;q-rear=null;int queuenotempty(lqueue q) /*非空否*/if (q.front=null) return 0;else return 1; int queueappend (lqueue *q, datatype x) /*入队列*/lqnode *p;if(p=(lqnode *)malloc(sizeof(lqnode)=null)printf (空间不足!);return 0;p-data=x;

12、p-next=null;if (q-rear!=null)q-rear-next=p; q-rear=p;if (q-front=null)q-front=p;return 1;int queuedelete(lqueue *q, datatype *d) /*出队列*/lqnode *p;if (q-front=null)printf (队列已经空了，没有数据元素出队列!n);return 0;else *d=q-front-data;p=q-front;q-front=q-front-next;if (q-front=null)q-rear=null;free (p);return 1;i

13、nt queueget(lqueue q,datatype *d) /*取对头数据元素*/if (q.front=null)printf (队列已经空了，没有数据元素出队列!n);return 0;else *d=q.front-data;return 1;void destroy (lqueue q) /*撤消动态申请空间 destroy(slnode *head)*/lqnode *p,*p1;p=q.front ;while(p!=null)p1=p;p=p-next;free(p1); 双端队列实现的功能如下： 1. 从队列首输入数据 2. 从队列尾输入数据 3. 从队列首取数据 4.

14、 从队列尾取数据 5. 队列清空/ 取队头元素elementtype front(queue q) if(!isempty(q)return q-arrayq-front;error(empty queue);return 0;queueappend(lqueue *q,datatype x) /插入函数在队头执行入队操作void push(elementtype x, queue q) if(isfull(q)error(full queue);elseq-size+;q-front = prev(q-front, q);q-arrayq-front = x;queuedelete(lque

15、ue *q,datatype x)/删除函数/ 在队头执行出队操作void pop(queue q) if(isempty(q)error( empty queue );elseq-size-;q-front = succ(q-front, q);/ 出队并取队头元素elementtype frontandpop(queue q) elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-front;q-front = succ(q-front, q);return x;/取队尾元素elementtyp

16、e rear(queue q) if(!isempty(q)return q-arrayq-rear;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函数/在队尾执行入队操作void inject(elementtype x, queue q) if(isfull(q)error(full queue);elseq-size+;q-rear = succ(q-rear, q);q-arrayq-rear = x;queuedelete(lqueue *q,datatype x) /删除函数/在队尾执行出队操作voi

17、d eject(queue q) if(isempty(q)error( empty queue );elseq-size-;q-rear = prev(q-rear, q);/ 出队并取队尾元素elementtype rearandeject(queue q) elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-rear;q-rear = prev(q-rear, q);return x;*/函数的界面设计：int main() char s10; int c; printf(n); print

18、f(1. 从队列首插入数据=按键1:n); printf(2. 从队列尾插入数据=按键2:n); printf(3. 从队列首删除数据=按键3:n); printf(4. 从队列尾删除数据=按键4:n); printf(5. 队列清空=按键5:n); printf(6. 退出=按键6:n); printf(n输入选项1-6: n);/输入1-6选项 do gets(s); c=atoi(s);if( c 6) printf(请输入正确的代码。n); while( c 6); return c;函数的大体设计，功能设计差不多就是这样的，具体的创建工程，头文件和源文件在前面的代码里。整体来讲，这些

19、代码还是比较繁琐，不够简洁。但这是我目前尽所能写代码了，很多地方自己也觉得很不满意，很多算法还是写不出来。慢慢改进。源代码：#include #include #include #include typedef int datatype;#include queue.hint main() char s10; int c; printf(n); printf(1. 从队列首输入入数据=按键1:n); printf(2. 从队列尾输入数据=按键2:n); printf(3. 从队列首取四个数据=按键3:n); printf(4. 从队列尾取四个数据=按键4:n); printf(5. 队列清空=

20、按键5:n); printf(6. 退出=按键6:n); printf(n输入选项1-6: n);/输入1-6选项 do gets(s); c=atoi(s);if( c 6) printf(请输入正确的代码。n); while( c 6); return c;/*queueinitiate(&myqueue); elementtype front(queue q) / 取队头元素 if(!isempty(q)return q-arrayq-front;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函数void

21、push(elementtype x, queue q) /在队头执行入队操作 if(isfull(q)error(full queue);elseq-size+;q-front = prev(q-front, q);q-arrayq-front = x;queuedelete(lqueue *q,datatype x)/删除函数void pop(queue q) / 在队头执行出队操作 if(isempty(q)error( empty queue );elseq-size-;q-front = succ(q-front, q);elementtype frontandpop(queue q

22、) / 出队并取队头元素 elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-front;q-front = succ(q-front, q);return x;elementtype rear(queue q) /取队尾元素 if(!isempty(q)return q-arrayq-rear;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函数void inject(elementtype x, queue q)

23、/在队尾执行入队操作 if(isfull(q)error(full queue);elseq-size+;q-rear = succ(q-rear, q);q-arrayq-rear = x;queuedelete(lqueue *q,datatype x) /删除函数void eject(queue q) /在队尾执行出队操作 if(isempty(q)error( empty queue );elseq-size-;q-rear = prev(q-rear, q);elementtype rearandeject(queue q) / 出队并取队尾元素 elementtype x = 0;

24、if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-rear;q-rear = prev(q-rear, q);return x;*/typedef struct qnodedatatype data;struct qnode *next;lqnode;typedef struct lqnode *front;lqnode *rear;lqueue; void queueinitiate(lqueue *q) /*初始化*/q-rear=null;q-rear=null;int queuenotempty(lqueue q) /*非

25、空否*/if (q.front=null) return 0;else return 1; int queueappend (lqueue *q, datatype x) /*入队列*/lqnode *p;if(p=(lqnode *)malloc(sizeof(lqnode)=null)printf (空间不足!);return 0;p-data=x;p-next=null;if (q-rear!=null)q-rear-next=p; q-rear=p;if (q-front=null)q-front=p;return 1;int queuedelete(lqueue *q, dataty

26、pe *d) /*出队列*/lqnode *p;if (q-front=null)printf (队列已经空了，没有数据元素出队列!n);return 0;else *d=q-front-data;p=q-front;q-front=q-front-next;if (q-front=null)q-rear=null;free (p);return 1;int queueget(lqueue q,datatype *d) /*取对头数据元素*/if (q.front=null)printf (队列已经空了，没有数据元素出队列!n);return 0;else *d=q.front-data;re

27、turn 1;void destroy (lqueue q) /*撤消动态申请空间 destroy(slnode *head)*/lqnode *p,*p1;p=q.front ;while(p!=null)p1=p;p=p-next;free(p1); 六。调试分析系统最后还是没能玩成所有的功能，在调试过程中，所出现的问题大致如下：sddldl.cpp(37) : error c2065: myqueue : undeclared identifier为什么开始会出现呢。开始以为定义了，仔细看看才发现定义的不是myqueue,而是lqueue,g:sddldl.cpp(37) : error

28、 c2501: queueinitiate : missing storage-class or type specifiersqueueinitiate初始化整个双端队列,缺少missing storage-class or type specifiers 这现在都没有理解,g:sddldl.cpp(37) : error c2373: queueinitiate : redefinition; different type modifiers g:sddlqueue.h(16) : see declaration of queueinitiate出现很多关于queueinitiate初始化

29、的问题，初始化时根据课本上的要求来弄得，出现这么多问题，始料未及。这可能和后面的定义有关g:sddldl.cpp(37) : error c2440: initializing : cannot convert from int * to int this conversion requires a reinterpret_cast, a c-style cast or function-style castg:sddldl.cpp(40) : warning c4518: int : storage-class or type specifier(s) unexpected here; ig

30、noredg:sddldl.cpp(40) : error c2146: syntax error : missing ; before identifier q缺少分号？但是在代码中明明是有分号的，可能这个函数的写法存在错误，但是反复调试，修改。还是存在问题g:sddldl.cpp(40) : error c2556: void _cdecl main(void) : overloaded function differs only by return type from int _cdecl main(void)这个不懂，问题出在哪里调试不出来g:sddldl.cpp(8) : see d

31、eclaration of maing:sddldl.cpp(40) : error c2371: main : redefinition; different basic types g:sddldl.cpp(8) : see declaration of maing:sddldl.cpp(40) : fatal error c1004: unexpected end of file found执行 cl.exe 时出错.sddl.exe - 1 error(s), 0 warning(s) 这是在最后的调试中出现的结果，在前面的调试中更加有一百多个错误，虽然反复调试，错误虽有减少，但是仍然

32、存在错误。最后调试的自己无法解决，问题的症结还是没能找出来。很多问题不单单是细节，正的的构造好像还是欠缺了，虽然一步一步的写下来，但是连接性还是不够，整个系统来讲，如果有一个错误，那么整个系统就不能运算出来，对于这次试验，我认识到了自己很大的不足，今后不单单要在程序算法上下工夫。更多的要会用好的方法来调试程序。因为有些错误仍然没该过来，很多功能还是不能运行，因此，只能将后面的代码注释掉。前面的运行结果截图如下： 后面本来预计是从队头输入四值然后进行队头的排列，然后从队尾输入四个值进行排列。但是调试这关没过，回天无力。 代码测试的基本要求：代码测试按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策。测试方法说明采用