双端队列测试用例课件

实验报告：特殊的线性表班级：计算机软件工程第一小组实验报告：特殊的线性表班级：计算机软件工程第一小组第一小组人员名单项目经理郭圣红70811304000531系统分析魏锴70811305000132算法设计

顾振挺70811304003633算法设计

马伽乐70811304004234代码编写

施明亮70811303000435代码编写

沈平36代码编写

何斌70811434000237测试江涛70811335000138测试

徐超70811435000339文档

朱国锋708141040025310自由人陈茹708113040041311第一小组人员名单项目经理郭圣红70811304双端队列⑴定义双端队列的抽象数据类型；⑵设计存储结构存储双端队列；⑶设计双端队列的插入和删除算法；⑷

分析算法的时间性能。

栈操作实验⑴建立一个空栈⑵

对已建立的栈进行插入、删除、取栈顶元素等基本操作。

实验内容特殊的线性表双端队列栈操作实验实验内容特殊的线性表时间进度安排.xlsAddYourText特殊的线性表共提交文档任务说明书.DOC双端队列测试用例.DOC实验需求说明书.DOC双端队列和栈测试报告.DOC双端队列和栈测试操作说明书.DOC双端队列和栈详细设计说明书.DOC试验二：特殊的线性表.doc数据结构上机试验人员Top组.doc数据结构实验会议纪要源程序和可执行程序数据结构上机试验演示.PPT时间进度安排.xlsAddYourText特殊的线性表共栈和双端队列的章节安排双端队列栈每实验均六章测试结果需求分析用户使用方法调试分析概要设计详细设计栈和双端队列的章节安排双端队列栈每实验均六章测试结果需求分析双端队列需求分析1.双端队列定义双端队列是一个两端都是结尾的队列，是在简单队列数据结构上的改进，其数据结构类似于双向链表，在每头分别设有对头和队尾两个指针；双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表两端进行；双端队列在队列的基础上，对其进行了堆栈化;2.双端队列特点双端队列同时具有队列和栈的性质；双端队列中的元素可以从两端弹出；如果严格禁用右段的操作，双端队列功能就和栈一样；如果严格禁用左段的操作，它的功能就和队列一样；双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。双端队列由程序员是控制的双端队列需求分析1.双端队列定义双端队列需求分析3.双端队列功能

设计双端队列的数据结构，实现入队、出队等基本操作;4.双端队列实验的基本运算定义双端队列的抽象数据类型；设计存储结构存储双端队列；分析算法的时间性能；双端队列初始化；双端队列清空双端队列头插入双端队列头取数据双端队列尾插入

双端队列尾取数据5.双端队列实验的接口要求用户能输入数据，和程序能有交互双端队列需求分析3.双端队列功能双端队列需求分析下图是我们对这个双端队列实验的感性认识双端队列TAILPTRHEADPTRNextPrevObjectNextPrevObjectNextPrevObjectNULLApplicationDataApplicationDataApplicationDataNULL双端队列需求分析下图是我们对这个双端队列实验的感性认识双端双端队列概要设计该程序主要实现以下5个功能：1.从队列首输入数据2.从队列尾输入数据3.从队列首取数据4.从队列尾取数据5.队列清空双端队列概要设计该程序主要实现以下5个功能：双端队列概要设计针对需要实现的功能做出详细的算法设计采用双向队列来实现，队列中有两个指针，一个指针指向队首结点，一个指向队尾结点。定义一个结构体，其中包含一个数据域和两个指针域，数据域用来存放数据，一个指针域用来存放指向前驱结点的指针，另一个指针域用来存放指向后继结点的指针。1.新建结点就是分配一个新的内存空间。2.每次分配空间都需要判断是否能分配到内存空间，如果未得到内存空间则终止当前操作。3.队列中只有头结点，该队列即为空队列。以上3点后面不再重复说明。双端队列概要设计针对需要实现的功能做出详细的算法设计双端队列概要设计一、 从顶部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队首指针指向新建结点，并将新建结点的后继指针指向原队首结点，原队首结点的指针指向新建结点。二、 从顶部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队首结点赋给临时结点。将队首结点的后继指针赋给队列的队首指针，再将队首结点的前驱指针置空。最后返回临时结点或所需要的数据。三、 从底部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队尾指针指向新建结点，并将新建结点的前驱指针指向原队尾结点，原队尾结点的指针指向新建结点。四、 从底部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结点的后继指针置空。最后返回临时结点或所需要的数据。五、 队列清空将队列的队首指针和队尾指针置空即可。双端队列概要设计一、 从顶部入队列双端队列详细设计双端队列数据类型

typedefstructnodeptrdatanode;typedefstructnodeptr{void*data;datanode*prev,*next;}node;typedefstruct{node*head,*tail,*cursor;intsize,item_deleted;}queue;双端队列详细设计双端队列数据类型双端队列详细设计双端队列实现的功能intQ_Init(queue*q);函数：初始化队列intQ_Empty(queue*q);函数：队列清空intQ_PushHead(queue*q,int*d);函数:数值入队列首intQ_PushTail(queue*q,int*d);函数：数值入队列尾intQ_PopHead(queue*q);函数：首部出队列intQ_PopTail(queue*q);函数：尾部出队列双端队列详细设计双端队列实现的功能双端队列调试分析Step1运行主程序显示主选择项测试结果：按任务书所要求的存数据入首、尾队列，队列首、尾取数据，队列清空，退出等选项显示清晰，达到要求双端队列测试用例1双端队列调试分析Step1运行主程序显示主选择项双端队双端队列调试分析Step2从队列首添加数据的测试测试结果：通过监视队列line，可知内部的节点秩序与屏幕输出的秩序一致，因此从队列首添加数据的代码执行正确2双端队列测试用例双端队列调试分析Step2从队列首添加数据的测试2双双端队列调试分析Step3从队列尾添加数据的测试测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列尾添加数据的代码执行正确3双端队列测试用例双端队列调试分析Step3从队列尾添加数据的测试3双端队列调试分析Step4从队列首取四个数据的测试测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列首部取四个数据代码执行正确双端队列测试用例4双端队列调试分析Step4从队列首取四个数据的测试双端队列调试分析Step5从队列尾取四个数据的测试测试结果：内部的节点值与屏幕输出的秩序一致，因此从队列尾部取四个数据代码执行正确5双端队列测试用例双端队列调试分析Step5从队列尾取四个数据的测试双端队列调试分析Step6从队列清空数据的测试测试结果：队列清空代码执行正确6双端队列测试用例双端队列调试分析Step6从队列清空数据的测试6双端双端队列调试分析代码测试按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策。测试方法说明采用VC集成开发环境，①在代码中嵌入屏幕输出代码，在程序测试运行时，可随时观察程序运行的状态，数据输出是否准确，并记录测试结果。②在各函数中设定中断，采用debug调试程序，观察和监视双端队列中各节点的变化过程。对于程序中的故障，亦可设置断点进行参数监视，逐一排查。双端队列调试分析代码测试双端队列调试分析使用上述用例经过5轮测试。共发现7个缺陷，所发现的问题已经全部得到解决，代码现已处在一个稳定运行阶段，达到任务书提出的要求，功能满足了系统设计要求，达到了系统设计的目标双端队列调试分析使用上述用例经过5轮测试。共发现7个缺陷，双端队列用户使用方法1.s运行双端队列可执行程序DEQUE.exe,程序将会出现先的画面，然后根据程序提示进行相关操作双端队列用户使用方法1.s运行双端队列可执行程序DEQUE双端队列测试结果1.s从队列首添加数据双端队列测试结果1.s从队列首添加数据双端队列测试结果2.s从队列尾添加数据双端队列测试结果2.s从队列尾添加数据双端队列测试结果3.s从队列首取四个数据双端队列测试结果3.s从队列首取四个数据双端队列测试结果4.s从队列尾取四个数据双端队列测试结果4.s从队列尾取四个数据双端队列

实验汇报完毕!!!!双端队列

实验汇报完毕!!!!栈需求分析1.栈定义栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）栈需求分析1.栈定义栈需求分析2.栈特点栈是机器系统自动分配提供的数据结构，特点是快速高效，缺点是有限制，数据不灵活，但程序员是无法控制的；栈对于进程/线程是唯一的；栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出栈需求分析2.栈特点栈

概要设计1.顺序栈实验的要求实现一个空顺序栈；并对已建立的栈进行插入、删除、取栈顶元素等基本操作；栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表2.顺序栈实验的基本运算置栈空；判栈空；判栈满；进栈；退栈；取栈顶元素栈概要设计1.顺序栈实验的要求栈

概要设计顺序方式生成一个栈，并实现对栈的操作，具体操作有：入栈、出栈、取栈顶元素，栈内存放数据为整数类型在main方法内实现简单的交互功能，根据输入的命令调用对应函数，可读取一行数据，自左向右依次入栈。操作指令：入栈push/出栈pop/取栈顶gettop/退出exit例如：Push空格输入数据/Push回车输入数据scanf使用技巧：scanf会读取用户输入的数据，并以空格、制表符为结束标志读取，同时scanf会返回，本次操作读取到数据的数量，读取一行多个数据时，可作为循环条件，判断缓冲区是否读取完毕。栈概要设计顺序方式生成一个栈，并实现对栈的操作，具体操作有栈

详细设计栈数据类型

typedefstruct{ int*base; int*top; intstacksize;}SqStack;栈详细设计栈数据类型栈

详细设计栈实现的功能StatusInitStack(Sqstack&s);函数：初始化栈StatusClearstack(Sqstack&s);函数：栈清空StatusGetTop(Sqstacks,SElemType&p);函数:取栈顶元素StatusPush(Sqstack&s,SElemType&e);函数：进栈函数StatusPop(Sqstack&s,SElemType&c);函数：出栈函数StatusObjection(Sqstack&s);函数：判断输入字符函数栈详细设计栈实现的功能栈

调试分析按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现的bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对