双端队列测试用例课件.ppt

1、CompanyLOGO实验报告：特殊的线性表班级：计算机软件工程班级：计算机软件工程第一小组第一小组人员名单项目经理 郭圣红 7081130400053 1系统分析 魏 锴 7081130500013 2算法设计 顾振挺 7081130400363 3算法设计 马伽乐 7081130400423 4代码编写 施明亮 7081130300043 5代码编写 沈 平3 6代码编写 何 斌 7081143400023 7测试 江 涛 7081133500013 8测试 徐 超 7081143500033 9文档 朱国锋 7081410400253 10自由人 陈 茹 7081130400413 11

2、双双端队列端队列 定义双端队列的抽象数据类型；设计存储结构存储双端队列；设计双端队列的插入和删除算法；分析算法的时间性能。栈操作实验栈操作实验 建立一个空栈 对已建立的栈进 行插入、删除、取栈顶元素等基本操作。实验内容实验内容特殊的线性表时间进度安排.xlsAdd Your Text特殊的线性表共提交文档任务说明书.DOC双端队列 测试用例.DOC实验需求说明书.DOC双端队列和栈测试报告.DOC双端队列和栈测试操作说明书.DOC双端队列和栈详细设计说明书.DOC试验二：特殊的线性表.doc数据结构上机试验人员 Top组.doc数据结构实验会议纪要源程序和可执行程序数据结构上机试验演示.PPT

3、栈和双端队列的章节安排双端队列双端队列栈栈每实验均六章测试结果需求分析用户使用方法调试分析概要设计详细设计双端队列 需求分析1.双端队列定义双端队列是一个两端都是结尾的队列，是在简单队列数据结构上的改进，其数据结构类似于双向链表，在每头分别设有对头和队尾两个指针；双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表两端进行；双端队列在队列的基础上，对其进行了堆栈化;2.双端队列特点双端队列同时具有队列和栈的性质；双端队列中的元素可以从两端弹出；如果严格禁用右段的操作，双端队列功能就和栈一样；如果严格禁用左段的操作，它的功能就和队列一样；双端队列与

4、栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。双端队列由程序员是控制的双端队列 需求分析3.双端队列功能 设计双端队列的数据结构，实现入队、出队等基本操作;4.双端队列实验的基本运算定义双端队列的抽象数据类型；设计存储结构存储双端队列；分析算法的时间性能；双端队列初始化；双端队列清空双端队列头插入双端队列头取数据双端队列尾插入 双端队列尾取数据5.双端队列实验的接口要求用户能输入数据，和程序能有交互双端队列 需求分析下图是我们对这个双端队列实验的感性认识双端队列TAILPTRHEADPTRNextPrevObjectNextPrevObjectNex

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

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

7、尾指针均指向新建结点，如不为空则将队尾指针指向新建结点，并将新建结点的前驱指针指向原队尾结点，原队尾结点的指针指向新建结点。四、从底部出队列首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结点的后继指针置空。最后返回临时结点或所需要的数据。五、队列清空将队列的队首指针和队尾指针置空即可。双端队列 详细设计双端队列数据类型 typedef struct nodeptr datanode;typedef struct nodeptr void*data;datanode*prev,*next;node;typedef s

8、truct 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 运行主程序显示主选择项运

9、行主程序显示主选择项测试结果：测试结果：按任务书所要求的存数据入首、尾队列，队列首、尾取数据，队列清空，退出等选项显示清晰，达到要求双端队列测试用例双端队列测试用例1双端队列 调试分析Step 2 从队列首添加数据的测试从队列首添加数据的测试测试结果：测试结果：通过监视队列line，可知内部的节点秩序与屏幕输出的秩序一致，因此从队列首添加数据的代码执行正确2双端队列测试用例双端队列测试用例双端队列 调试分析Step 3 从队列尾添加数据的测试从队列尾添加数据的测试测试结果：测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列尾添加数据的代码执行正确3双端队列测试

10、用例双端队列测试用例双端队列 调试分析Step 4 从队列首取四个数据的测试从队列首取四个数据的测试测试结果：测试结果：通过监视队列line，可知，里面的节点秩序与屏幕输出的秩序一致，因此从队列首部取四个数据代码执行正确双端队列测试用例双端队列测试用例4双端队列 调试分析Step 5 从队列尾取四个数据的测试从队列尾取四个数据的测试测试结果：测试结果：内部的节点值与屏幕输出的秩序一致，因此从队列尾部取四个数据代码执行正确5双端队列测试用例双端队列测试用例双端队列 调试分析Step 6 从队列清空数据的测试从队列清空数据的测试测试结果：队列清空代码执行正确测试结果：队列清空代码执行正确6双端队列

11、测试用例双端队列测试用例双端队列 调试分析代码测试按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策。测试方法说明采用VC集成开发环境，在代码中嵌入屏幕输出代码，在程序测试运行时，可随时观察程序运行的状态，数据输出是否准确，并记录测试结果。在各函数中设定中断，采用debug调试程序，观察和监视双端队列中各节点的变化过程。对于程序中的故障，亦可设置断点进行参数监视，逐一排查。双端队列 调试分析使用上述用例经过5轮测试。共发现7个缺陷，所发现的问题已经全部得到解决，代码现已处

12、在一个稳定运行阶段，达到任务书提出的要求，功能满足了系统设计要求，达到了系统设计的目标双端队列 用户使用方法1.s运行双端队列可执行程序DEQUE.exe,程序将会出现先的画面，然后根据程序提示进行相关操作双端队列 测试结果1.s从队列首添加数据从队列首添加数据双端队列 测试结果2.s从队列尾添加数据从队列尾添加数据双端队列 测试结果3.s从队列首取四个数据从队列首取四个数据双端队列 测试结果4.s从队列尾取四个数据从队列尾取四个数据双端队列 实验汇报完毕!栈 需求分析1.栈定义栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。栈是一种数据结构，它按照后进先出的原则存储数

13、据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）栈 需求分析2.栈特点栈是机器系统自动分配提供的数据结构，特点是快速高效，缺点是有限制，数据不灵活，但程序员是无法控制的；栈对于进程/线程是唯一的；栈的剩余空间大

14、于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出栈 概要设计1.顺序栈实验的要求实现一个空顺序栈；并对已建立的栈进行插入、删除、取栈顶元素等基本操作；栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表2.顺序栈实验的基本运算置栈空；判栈空；判栈满；进栈；退栈；取栈顶元素栈 概要设计顺序方式生成一个栈，并实现对栈的操作，具体操作有：入栈、出栈、取栈顶元素，栈内存放数据为整数类型在main方法内实现简单的交互功能，根据输入的命令调用对应函数，可读取一行数据，自左向右依次入栈。操作指令：入栈push/出栈pop/取栈顶gettop/退出exit例如：Push 空格 输入数据/Push 回车

15、 输入数据scanf使用技巧：scanf会读取用户输入的数据，并以空格、制表符为结束标志读取，同时scanf会返回，本次操作读取到数据的数量，读取一行多个数据时，可作为循环条件，判断缓冲区是否读取完毕。栈 详细设计栈数据类型 typedef struct int*base;int*top;int stacksize;SqStack;栈 详细设计栈实现的功能Status InitStack(Sqstack&s);函数：初始化栈Status Clearstack(Sqstack&s);函数：栈清空Status GetTop (Sqstack s,SElemType&p);函数:取栈顶元素Statu

16、s Push (Sqstack&s,SElemType&e);函数：进栈函数Status Pop (Sqstack&s,SElemType&c);函数：出栈函数Status Objection(Sqstack&s);函数：判断输入字符函数栈 调试分析按照正常的系统使用条件：测试人员对本系统的逐个功能进行使用，填写入测试报告。测试人员测试结束后，对所呈现的bug，开发人员对系统中问题进行分析，确定故障的原因，并制定相应的对策栈代码测试1栈 调试分析采用VC集成开发环境，在代码中嵌入屏幕输出代码，在程序测试运行时，可随时观察程序运行的状态，数据输出是否准确，并记录测试结果。在各函数中设定中断，采用

17、debug调试程序，观察和监视栈中各节点的变化过程。2栈测试方法说明栈 调试分析步骤步骤1、嵌入栈首尾存数值的测试代、嵌入栈首尾存数值的测试代码，并通过码，并通过printf（），显示栈的状态（），显示栈的状态。存入数值的程序采用。存入数值的程序采用scanf()，可手，可手工输入数值。设置相关函数断点，工输入数值。设置相关函数断点，监视栈值的变化；监视栈值的变化；步骤步骤2、运行程序，输入、取出任意数、运行程序，输入、取出任意数值以验证代码功能。设置相关函数断值以验证代码功能。设置相关函数断点，监视栈的变化点，监视栈的变化3栈功能测试过程栈 调试分析经过2轮测试。共发现2个缺陷，所发现的问题已经全部得到解决，代码现已处在一个稳定运行阶段，达到任务书提出的要求，功能满足了系统设计要求，达到了系统设计的目标栈 用户使用方法1.s运行栈可执行程序stack.exe,然后根据程序提示进行相关操作栈实验汇报完毕!CompanyLOGO班级：计算机软件工程班级：计算机软件工程第一小组