数据结构课程设计报告超级版.doc

数据结构实验报告班级-姓名-完成日期-学号-完成题目1、二叉树基本操作源文件：binaryTree.cpp2、栈的应用：表达式求值源文件：getValue.cpp3、队列的应用：银行排队系统源文件：bank.cpp 4、查找：航班信息查询与检索系统源文件：flight.cpp5、查找算法比较：顺序查找、折半查找源程序：顺序和折半.cpp6、集合的交/并/差运算：用有序单链表表示集合 源文件：集合交并差.cpp完成情况评价对于程序分析题的7选4比较容易完成。老师以填空的方式让我们完成源程序中一些核心关键的代码 。虽然都是学过的算法且书上都有列出，但是在实现过程中还是要认真仔细知道变通。对于编程题相对有点难度，在实现顺序查找和折半查找的过程中，出现顺序少查找一次，折半多查找一次，最后在老师帮助下得以解决。再则是用有序单链表表示集合交/并/差，刚开始无从下手，自己到网上查找相关算法，虚心请教同学，问老师最终理解并实现。总的来说付出就会有回报，在这次课程设计中我认真积极思考并完成了任务，所以我的收获是丰硕的，受益终身。对课程设计的建议本次课程设计“基础、实用”，希望以后能有更多的机会来实践，从中受益，对日后的工作有所帮助。课程设计题目一：二叉树基本操作1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入的形式：ABC#DE#G#F#变量ch 二叉树结点为char型2）输出的形式输出：树状输出二叉树，前、中、后序输出先、中、后序遍历二叉树char型；叶子节点 char型；几点个数和深度 int型。3）程序所能达到的功能（1）、树状输出二叉树（2）、先序遍历二叉树（3）、中序遍历二叉树（4）、后序遍历二叉树（5）、输出叶子节点（6）、输出叶子节点个数（7）、输出二叉树的深度（8）、退出4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入字符：ABC#DE#G#F#输出结果：先序遍历：ABCDEFG 中序遍历：CBEGDFA 后序遍历：CGEFDBA叶子节点：CGF 叶子节点个数：3 二叉树的深度：52、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型typedef struct BiTNode / 定义二叉树节点结构char data; / 数据域 struct BiTNode *LChild,*RChild; / 左右孩子指针域BiTNode,*BiTree;BiTree T;（2）子程序的功能void CreateBiTree(BiTree *bt) 建立二叉树void TranslevelPrint(BiTree bt) 树型打印二叉树void Visit(char ch) 输出结点void PreOrder(BiTree root) 先序遍历二叉树void InOrder(BiTree root) 中序遍历二叉树void PostOrder(BiTree root) 后序遍历二叉树void PreOrderLeaf(BiTree root) 输出叶子结点int LeafCount(BiTree root) 输出叶子结点的个数int PostTreeDepth(BiTree root) 输出二叉树的深度（3）函数和过程的调用关系图源程序的功能函数调用图二叉树先、中、后序流程图3、详细设计（对主程序和主要算法模块重点介绍）主要程序：(1).建立二叉树void main() 输入二叉树的结点序列(2). 按菜单提示操作void mainwork() 根据输入信息进行操作，调用树型打印二叉树、输出结点、先序遍历二叉树、中序遍历二叉树、后序遍历二叉树、输出叶子结点、输出叶子结点的个数、输出二叉树的深度函数进行操作。(3). 先序遍历二叉树void PreOrder(BiTree root)根据根、左、右遍历二叉树。(4).中序遍历二叉树void InOrder(BiTree root) 根据左、根、右遍历二叉树。(5). 后序遍历二叉树void PostOrder(BiTree root) 根据左、右、根遍历二叉树(6).退出4、测试分析1）调试过程中遇到的问题是如何解决的 空格字符用#表示2）算法的时间复杂度分析无3）经验和体会对二叉树的遍历有了更深入了解和体会4）测试功能展示（测试数据应完整严格，列出测试结果，包括输入和输出）（1）、树状输出二叉树（2）、先序遍历二叉树（3）、中序遍历二叉树（4）、后序遍历二叉树（5）、输出叶子节点（6）、输出叶子节点个数（7）、输出二叉树的深度（8）、退出5、源程序清单（列出程序文件名）源程序：binaryTree.cpp课程设计题目二：栈的应用：表达式求值1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入的形式：加减乘除运算变量top为int型2）输出的形式表达式的计算结果是 :%dn3）程序所能达到的功能表达式求值4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果 输入：2*3+14-8 输出：122、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型t ypedef struct sqstackelemtype stackMAXSIZE; int top;sqstack;（2）子程序的功能void Initstack(sqstack *s) 构造一个空栈bool StackEmpty(sqstack S ) 判空void Push(sqstack *s,elemtype x) 进栈void Pop(sqstack *s,elemtype *x)出栈（3）函数和过程的调用关系图 判断栈是否为空，进栈，出栈流程图3、详细设计（对主程序和主要算法模块重点介绍）(1)、bool StackEmpty(sqstack S ) 若S为空栈，则返回TRUE, 否则返回FALSE(2)、void Push(sqstack *s,elemtype x) 进栈(3)、void Pop(sqstack *s,elemtype *x) 出栈(4)、char Compare(char c1,char c2) 把字符变成数字，并通过原来设定找到优先级(5)、int EvaluateExpression() if(isdigit(c)判断c是否为数字，Push(&OPND,sum);/当前c不为数字，则把之前的把数字串转化成十进制数字再压栈4、测试分析1）调试过程中遇到的问题是如何解决的没有问题2）算法的时间复杂度分析无3）经验和体会对栈的基本操作，构造空栈，进栈，出栈等，有更深入的理解4）测试功能展示（测试数据应完整严格，列出测试结果，包括输入和输出）表达式求值5、源程序清单（列出程序文件名）getValue.cpp课程设计题目三：队列的应用：银行排队系统1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入形式：vip用户和普通用户变量data 为int型变量i窗口号为int型2）输出的形式 业务办理，排队情况，系统查询输出都为%d3）程序所能达到的功能（1）、顾客到达（2）、顾客离开（3）、查看业务办理（4）、查看排队情况（5）、系统查询（6）、退出4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入：Vip 卡号200 密码：2222 普通用户，业务号分别为1,2,3,4输出：结果测试功能展示一致2、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型struct Listint An+1; 顾客用来办理业务的N个窗口 int len; 表示数组中的元素个数L;struct Lnodeint data; 链表结点类型 Lnode *next;struct Linkqueue 链式存储的等候队列的类型定义 Lnode *front; Lnode *rear;Q;（2）子程序的功能void Initshuzu() 初始化线性的算法void Initqueue() 初始化队列的算法void Enqueue(Linkqueue *Q,int elem ) 进队算法int Dlqueue(Linkqueue *Q) 出队算法void printl() 输出数组算法void print2() 输出队列算法void daoda(int x) 解决顾客到达事件算法void likai(int x) 解决顾客离开事件算法int guitai( ) 判断输入的柜台号是否正确int pingfeng( ) 判断输入的分数是否正确void mygrade() 主评分函数void vip(int x) vip用户认证void time() 时间函数（3）函数和过程的调用关系图源程序的功能函数调用图出队的程序流程图3、详细设计（对主程序和主要算法模块重点介绍）(1)、void Enqueue(Linkqueue *Q,int elem ) 进队算法(2)、int Dlqueue(Linkqueue *Q) 出队算法(3)、void printl() 输出数组算法，办理业务的顾客编号分别在几号柜台(4)、void print2() 输出队列算法，s=s-next当顾客人数大于柜台数及存在等候排队，并用计数器i计算(5)、void likai(int x)解决顾客离开事件算法，L.len队伍长度减排队人数减少 (6)、int guitai( ) 判断输入的柜台号是否正确，办理柜台号只能是1-3(7)、int pingfeng( ) 判断输入的分数是否正确，y5评分有误(8)、void main() 主函数，system(color 1f); 屏幕颜色设定，v+; 普通卡顾客计数，4、测试分析1）调试过程中遇到的问题是如何解决的 调试过程中，输入办理业务人数大于3，才有排队情况2）算法的时间复杂度分析 无3）经验和体会 对进出队列的算法的应用有了更实际的理解4）测试功能展示（测试数据应完整严格，列出测试结果，包括输入和输出）（1）、顾客到达（2）、顾客离开（3）、查看业务办理（4）、查看排队情况离开一名顾客以后排队情况（5）、系统查询（6）、退出5、源程序清单（列出程序文件名）bank.cpp课程设计题目四：查找：航班信息查询与检索系统1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入：航班号CQ5200，起点站 盱眙，终点站上海，航班期，起飞时间，到达时间，机型，票价等变量start 起点 为char型变量end 终点 为char型变量Sche 班期 为char型变量time1 起飞时间 为char型变量time2 到达时间 为char型变量model 机型 为char型变量price 票价 为int型变量KeyType 航班号 为char型2）输出的形式航班号%s 起点站%s 终点站%s 航班期%s 起飞时间%s 到达时间%s 机型%s 票价%d3）程序所能达到的功能(1)按航班号查询(2)按起点站查询(3)按终点站查询(4)按起飞时间查询(5)按到达时间查询(6)添加班次(7)退出系统4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入：航班号CQ5200 起点站 盱眙等，具体内容参考4）测试功能展示输出：航班号CQ5200 起点站 盱眙等，具体内容参考4）测试功能展示2、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型 静态链表结点类型 typedef struct KeyType keyskeylen;关键字（航班号）InfoType others;int next;SLNode;静态链表类型 typedef struct SLNode slMaxSpace;静态链表int keynum;关键字字符数int length;表长SLList;typedef int ArrType_nRADIX_n; 数字字符typedef int ArrType_cRADIX_c; 字母字符KeyType keykeylen,kl4;（2）子程序的功能void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)数字字符分配函数void Collect(SLNode *sl, ArrType_n f, ArrType_n e)数字字符收集函数void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e)字母字符分配函数void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e)字母字符收集函数void RadixSort(SLList &L) 链式基数排序函数void Arrange(SLList &L) 按指针链整理线性表int BinSearch(SLList L, KeyType key) 二分查找函数void SeqSearch(SLList L, KeyType key,int i) 顺序查找函数void Display(SLList L, int i) 打印班次信息函数void DisplayStyle(int i, char *s) 调整对齐格式函数void searchcon(SLList L) 交互界面函数void Prompt( ) 显示主菜单bool InputData(SLList &L) 输入航班记录函数bool Check_HangBanHao(char *HangBanHao) 航班号输入效验（3）函数和过程的调用关系图源程序的功能函数调用图二分查找程序流程图3、详细设计（对主程序和主要算法模块重点介绍）(1)、void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)数字字符分配函数，j=slp.keysi%48; /将数字字符映射为十进制数字(2)、void Collect(SLNode *sl, ArrType_n f, ArrType_n e)数字字符收集函数，sl0.next=fj;/将sl0.next指向第一个非空子表的第一个结点，slt.next=fj;t=ej; /链接到主链表(3)、void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e)字母字符分配函数，j=slp.keysi%65;/将字母字符映射为字母集中的相应序号(4)、void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e)字母字符收集函数，for(j=0;!fj; j+);/找第一个非空子表(5)、int BinSearch(SLList L, KeyType key) 二分查找函数(6)、void SeqSearch(SLList L, KeyType key,int i) 顺序查找函数(7)、bool InputData(SLList &L) 输入航班记录函数4、测试分析1）调试过程中遇到的问题是如何解决的在对起飞时间和到达时间进行查询时，输入时间的冒号必须是英文状态下，否则查无记录2）算法的时间复杂度分析其中：顺序查找平均查找长度：ASL=(n+1)/2二分查找平均查找长度：ASL= log(2)n+1 -13）经验和体会二分查找函数,顺序查找函数等等有了更深入了解4）测试功能展示（测试数据应完整严格，列出测试结果，包括输入和输出）(1)按航班号查询(2)按起点站查询(3)按终点站查询(4)按起飞时间查询(5)按到达时间查询(6)添加班次(7)退出系统5、源程序清单（列出程序文件名）源程序：flight.cpp课程设计题目五：查找算法比较：顺序查找、折半查找1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入：有序表：5 13 19 21 37 56 64 75 80 88 92 关键字：21变量keytype关键字为int型变量length长度为int型变量第i个记录为int型变量m 计数器为int型变量low、high、mid为int型2）输出的形式顺序查找结果，顺序程序运算的次数折半查找结果，折半查找程序运算的次数关键字%d、m%d3）程序所能达到的功能(1)顺序查找(2)折半查找(3)顺序查找的次数(4)折半查找的次数(5)退出系统4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入：有序表：5 13 19 21 37 56 64 75 80 88 92 关键字：21输出：顺序查找结果：4，顺序程序运算了8次 折半查找结果：4，折半查找程序运算了3次2、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型typedef int keytype;typedef int infotype;typedef struct keytype key; 关键字 其他数据rectype; 记录类型typedef struct rectype rMAXSIZE+1; r0作为哨兵int length; 顺序表长度SSTable;（2）子程序的功能 void SeqSearch( SSTable S , keytype k )在顺序表中，顺序查找关键字与key相同的元素，并计算运算次数 void BinSearch(SSTable ST,keytype k)在顺序表中，折半查找关键字与key相同的元素并计算运算次数（3）函数和过程的调用关系图顺序查找流程图折半查找流程图3、详细设计（对主程序和主要算法模块重点介绍）（1）、void SeqSearch( SSTable S , keytype k )在顺序表ST中，顺序查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0。设立哨兵，并计算查找次数（2）、void BinSearch(SSTable ST,keytype k)在顺序表ST中，折半查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0，并计算查找次数4、测试分析1）调试过程中遇到的问题是如何解决的在顺序查找的过程中，在查找到相同的元素时要进行一次比较，否则少查1次在折半查找的过程中，在查找数与mid相同时，不需要再比较直接跳出，否则多查一次2）算法的时间复杂度分析(1)、顺序查找性能分析：平均查找长度ASL=(n+1)/2（其中第i个记录概率为1）优点：算法简单且适应面广。它对表的结构无任何要求，无论记录是否按关 键之有序均可应用，且对线性链表也适用。缺点：平均查找长度较大，特别是当n很大时，查找效率较低。(2)折半查找性能分析平均查找长度ASL= log(2)n+1 -1 优点：折半查找效率比顺序查找效率高，分割时只需进行加减运算 缺点：折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法有效地进行折半查找）3）经验和体会对于查找要自己列出数据元素进行查找来验证结果，还要透彻理解查找的含义，不然容易出错4）测试功能展示（测试数据应完整严格，列出测试结果，包括输入和输出）（1）、顺序查找结果及其运算次数（2）、折半查找结果及其运算次数5、源程序清单（列出程序文件名） 源程序：顺序和折半.cpp课程设计题目六：有序单链表表示集合的交/并/差运算1、需求分析（说明程序设计的任务，重点强调程序要做什么，应明确规定以下内容）1）输入的形式和输入值的范围输入形式：输入集合AB个数和数据 变量个数输出为%d2）输出的形式输出：集合A和B交、并、差的结果3）程序所能达到的功能(1)、集合A和B的交运算(2)、集合A和B的并运算(3)、集合A和B的差运算(4)、退出4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入：集合A，集合B的个数，集合A的数据，集合B的数据输出：同4）测试功能展示2、概要设计（说明程序中用到的所有抽象数据类型的定义、各子程序的功能及其调用关系以及各程序模块之间的调用关系。需画出函数和过程的调用关系图）（1）抽象数据类型typedef struct LNode int data;struct LNode *next;LNode,*LinkList;（2）子程序的功能 、void CreateList(LinkList &L,int n) 表尾到表头逆向创造有序单链表、void Insection(LinkList &La,LinkList &Lb,LinkList &Lc) A和B的交运算、void Merge