双端队列测试用例课件.ppt
实验报告：特殊的线性表,班级：计算机软件工程,第一小组,第一小组人员名单,双端队列 定义双端队列的抽象数据类型；设计存储结构存储双端队列；设计双端队列的插入和删除算法；分析算法的时间性能。,栈操作实验 建立一个空栈 对已建立的栈进 行插入、删除、取栈顶元素等基本操作。,实验内容,特殊的线性表,特殊的线性表共提交文档,双端队列和栈测试操作说明书.DOC,双端队列和栈详细设计说明书.DOC,试验二：特殊的线性表.doc,数据结构上机试验人员 Top组.doc,数据结构实验会议纪要,源程序和可执行程序,数据结构上机试验演示.PPT,栈和双端队列的章节安排,双端队列,栈,每实验均六章,测试结果,需求分析,用户使用方法,调试分析,概要设计,详细设计,双端队列 需求分析,1.双端队列定义双端队列是一个两端都是结尾的队列，是在简单队列数据结构上的改进，其数据结构类似于双向链表，在每头分别设有对头和队尾两个指针；双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表两端进行；双端队列在队列的基础上，对其进行了堆栈化;2.双端队列特点双端队列同时具有队列和栈的性质；双端队列中的元素可以从两端弹出；如果严格禁用右段的操作，双端队列功能就和栈一样；如果严格禁用左段的操作，它的功能就和队列一样；双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。双端队列由程序员是控制的,双端队列 需求分析,3.双端队列功能 设计双端队列的数据结构，实现入队、出队等基本操作;4.双端队列实验的基本运算定义双端队列的抽象数据类型；设计存储结构存储双端队列；分析算法的时间性能；双端队列初始化；双端队列清空双端队列头插入双端队列头取数据双端队列尾插入 双端队列尾取数据5.双端队列实验的接口要求用户能输入数据，和程序能有交互,双端队列 需求分析,下图是我们对这个双端队列实验的感性认识,双端队列,TAILPTR,HEADPTR,Next,Prev,Object,Next,Prev,Object,Next,Prev,Object,NULL,Application Data,Application Data,Application Data,NULL,双端队列 概要设计,该程序主要实现以下5个功能：1.从队列首输入数据2.从队列尾输入数据3.从队列首取数据4.从队列尾取数据5.队列清空,双端队列 概要设计,针对需要实现的功能做出详细的算法设计采用双向队列来实现，队列中有两个指针，一个指针指向队首结点，一个指向队尾结点。定义一个结构体，其中包含一个数据域和两个指针域，数据域用来存放数据，一个指针域用来存放指向前驱结点的指针，另一个指针域用来存放指向后继结点的指针。1.新建结点就是分配一个新的内存空间。2.每次分配空间都需要判断是否能分配到内存空间，如果未得到内存空间则终止当前操作。3.队列中只有头结点，该队列即为空队列。以上3点后面不再重复说明。,双端队列 概要设计,一、从顶部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队首指针指向新建结点，并将新建结点的后继指针指向原队首结点，原队首结点的指针指向新建结点。二、从顶部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队首结点赋给临时结点。将队首结点的后继指针赋给队列的队首指针，再将队首结点的前驱指针置空。最后返回临时结点或所需要的数据。三、从底部入队列新建一个结点，如果队列为空，则将队列的队首指针和队尾指针均指向新建结点，如不为空则将队尾指针指向新建结点，并将新建结点的前驱指针指向原队尾结点，原队尾结点的指针指向新建结点。四、从底部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结点的后继指针置空。最后返回临时结点或所需要的数据。五、队列清空将队列的队首指针和队尾指针置空即可。,双端队列 详细设计,双端队列数据类型 typedef struct nodeptr datanode;typedef struct nodeptr void*data;datanode*prev,*next;node;typedef struct node*head,*tail,*cursor;int size,item_deleted;queue;,双端队列 详细设计,双端队列实现的功能int Q_Init(queue*q);函数：初始化队列int Q_Empty(queue*q);函数：队列清空int Q_PushHead(queue*q,int*d);函数:数值入队列首int Q_PushTail(queue*q,int*d);函数：数值入队列尾int Q_PopHead(queue*q);函数：首部出队列int Q_PopTail(queue*q);函数：尾部出队列,双端队列 调试分析,Step 1 运行主程序显示主选择项测试结果：按任务书所要求的存数据入首、尾队列，队列首、尾取数据，队列清空，退出等选项显示清晰，达到要求,双端队列测试用例,1,双端队列 调试分析,Step 2 从队列首添加数据的测试测试结果：通过监视队列line，可知内部的节点秩序与屏幕输出的秩序一致，因此从队列首添加数据的代码执行正确,2,双端队列测试用例,双端队列 调试分析,Step 3 从队列尾添加数据的测试测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列尾添加数据的代码执行正确,3,双端队列测试用例,双端队列 调试分析,Step 4 从队列首取四个数据的测试测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列首部取四个数据代码执行正确,双端队列测试用例,4,双端队列 调试分析,Step 5 从队列尾取四个数据的测试测试结果：内部的节点值与屏幕输出的秩序一致，因此从队列尾部取四个数据代码执行正确,5,双端队列测试用例,双端队列 调试分析,Step 6 从队列清空数据的测试测试结果：队列清空代码执行正确,6,双端队列测试用例,双端队列 调试分析,代码测试按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策。测试方法说明采用VC集成开发环境，在代码中嵌入屏幕输出代码，在程序测试运行时，可随时观察程序运行的状态，数据输出是否准确，并记录测试结果。在各函数中设定中断，采用debug调试程序，观察和监视双端队列中各节点的变化过程。对于程序中的故障，亦可设置断点进行参数监视，逐一排查。,双端队列 调试分析,使用上述用例经过5轮测试。共发现7个缺陷，所发现的问题已经全部得到解决，代码现已处在一个稳定运行阶段，达到任务书提出的要求，功能满足了系统设计要求，达到了系统设计的目标,双端队列 用户使用方法,1.s运行双端队列可执行程序DEQUE.exe,程序将会出现先的画面，然后根据程序提示进行相关操作,双端队列 测试结果,1.s从队列首添加数据,双端队列 测试结果,2.s从队列尾添加数据,双端队列 测试结果,3.s从队列首取四个数据,双端队列 测试结果,4.s从队列尾取四个数据,双端队列 实验汇报完毕!,栈 需求分析,1.栈定义栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）,栈 需求分析,2.栈特点栈是机器系统自动分配提供的数据结构，特点是快速高效，缺点是有限制，数据不灵活，但程序员是无法控制的；栈对于进程/线程是唯一的；栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出,栈 概要设计,1.顺序栈实验的要求实现一个空顺序栈；并对已建立的栈进行插入、删除、取栈顶元素等基本操作；栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表2.顺序栈实验的基本运算置栈空；判栈空；判栈满；进栈；退栈；取栈顶元素,栈 概要设计,顺序方式生成一个栈，并实现对栈的操作，具体操作有：入栈、出栈、取栈顶元素，栈内存放数据为整数类型在main方法内实现简单的交互功能，根据输入的命令调用对应函数，可读取一行数据，自左向右依次入栈。操作指令：入栈push/出栈pop/取栈顶gettop/退出exit例如：Push 空格 输入数据/Push 回车 输入数据scanf使用技巧：scanf会读取用户输入的数据，并以空格、制表符为结束标志读取，同时scanf会返回，本次操作读取到数据的数量，读取一行多个数据时，可作为循环条件，判断缓冲区是否读取完毕。,栈 详细设计,栈数据类型 typedef struct int*base;int*top;int stacksize;SqStack;,栈 详细设计,栈实现的功能Status InitStack(Sqstack 函数：判断输入字符函数,栈 调试分析,按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现的bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策,栈代码测试,1,栈 调试分析,采用VC集成开发环境，在代码中嵌入屏幕输出代码，在程序测试运行时，可随时观察程序运行的状态，数据输出是否准确，并记录测试结果。在各函数中设定中断，采用debug调试程序，观察和监视栈中各节点的变化过程。,2,栈测试方法说明,栈 调试分析,步骤1、嵌入栈首尾存数值的测试代码，并通过printf（），显示栈的状态。存入数值的程序采用scanf()，可手工输入数值。设置相关函数断点，监视栈值的变化；步骤2、运行程序，输入、取出任意数值以验证代码功能。设置相关函数断点，监视栈的变化,3,栈功能测试过程,栈 调试分析,经过2轮测试。共发现2个缺陷，所发现的问题已经全部得到解决，代码现已处在一个稳定运行阶段，达到任务书提出的要求，功能满足了系统设计要求，达到了系统设计的目标,栈 用户使用方法,1.s运行栈可执行程序stack.exe,然后根据程序提示进行相关操作,栈实验汇报完毕!,班级：计算机软件工程,My Professor,Thank You!And My Team,EveryOne,Thanks!,第一小组,
