数据结构课设报告-绝对原版大家珍惜啊.doc

数据结构课程设计报告姓名：班级：学号：指导教师成绩：一 各个课设概述1 算术表达式求值 (必做)A 算法思想及数据结构及时间复杂度(括号内容)：算式（栈）：计算部分(n)：建立运算符优先规则，存在一个二维数组中。运用数字栈和运算符栈，逐个字符读入算式，若字符为数字则放入数字栈；若字符为运算符则让它和元素符栈的栈顶元素比较优先级，若优先级低则进运算符栈，若优先级高，则取数字栈中元素进行运算。直至读到#。纠错部分(n)：首先对每个读入的字符进行判断，如果非法则终止程序。对于运算符匹配，则在计算完后查看字符栈和数字栈，进而判断。B 程序测试 正确表达式测试：#7+8+(9+6*5)+4#结果：OPTR: OPND: OPTR: #OPND: OPTR: #OPND: 7OPTR: + #OPND: 7OPTR: + #OPND: 8 7OPTR: #OPND: ?OPTR: + #OPND: ?OPTR: ( + #OPND: ?OPTR: ( + #OPND: 9 ?OPTR: + ( + #OPND: 9 ?OPTR: + ( + #OPND: 6 9 ?OPTR: * + ( + #OPND: 6 9 ?OPTR: * + ( + #OPND: 5 6 9 ?OPTR: + ( + #OPND: N 9 ?OPTR: ( + #OPND: W ?OPTR: + #OPND: W ?OPTR: #OPND: fOPTR: + #OPND: fOPTR: + #OPND: 4 fOPTR: #OPND: jresult: 58错误表达式测试#(7*5)(3+4)#输出结果：OPTR: OPND: OPTR: #OPND: OPTR: ( #OPND: OPTR: ( #OPND: 7OPTR: * ( #OPND: 7OPTR: * ( #OPND: 5 7OPTR: ( #OPND: SOPTR: #OPND: SOPTR: ( #OPND: SOPTR: ( #OPND: 3 SOPTR: + ( #OPND: 3 SOPTR: + ( #OPND: 4 3 SOPTR: ( #OPND: 7 SOPTR: #OPND: 7 S算式操作符搭配有问题，请重新输入。2 二叉树的应用 (必做)A 算法思想及数据结构及时间复杂度：二叉树（二叉树）：建树：采用课本上先序建树方法。层序遍历：增加一个数字栈，从树的祖先开始访问，访问后就把该节点的左右子树放进栈里，然后访问栈顶元素，依次递归下去，直至栈为空。深度：在树节点的结构体内增加一个level变量用来记录该节点的层数。采用层序遍历，令头结点的level为1，访问到时在把其左右子树放进栈的同时，付其level为2，依次递归下去。繁茂度：在求深度程序的基础上，加开一个一维数组，记录各个节点的level，访问完后再扫描一下数组，分别记录各个层的节点数，找出最大值再乘以深度。叶子节点个数：加开count变量。任意遍历方法，若访问节点左右子树均为空则count+；遍历完后，count即为叶子节点个数。判断完全二叉树：采用层序遍历的方法，并把访问多的节点记录在数组里，如果在数组中间出现了NULL，则树不是完全二叉树。B 测试主界面当输入相应的代号就能输出相应的结果。3 Huffman编码与解码 (必做)A 算法思想及数据结构及时间复杂度：哈弗曼（哈弗曼树）：编码：先读一遍文章，统计各个字符出现的个数，赋给各个字符以weight；然后建立哈弗曼树(n2)，生成哈弗曼编码。然后再读一遍文章，把其转换为哈弗曼编码。解码(ne)：让编码在输出哈弗曼编码的同时，并把各个节点的父节点以及左右孩子节点输出，利用这些数据重新还原哈弗曼数，然后读入哈弗曼编码，如果是1则从树头往右走，如果读入0则往左走。B 使用说明编码：直接运行编码的程序，就能把默认final.in里的文章转换成哈弗曼编码，并记录在final.out中，如果显示每个字符的编码，只需把主函数中的“输出各个字母所对应的哈弗曼编码”部分取消注释即可。在执行解码时，请先运行编码，并把“输出各个字母所对应的哈弗曼编码”注释掉，解码部分将从final.out读入数据，把解码结果存放在finalout.out中。4 校园局域网布线和游历问题 (必做) A 算法思想及数据结构及时间复杂度：校园游历（图论，）：遍历图：利用深搜(n+e)和宽搜(n+e)建立校园网(n2)：利用prim算法求最小生成树。从宿舍到其他各点的路径(n2)：利用迪杰斯特拉算法求某点到其他各点的最短路径。查询任意两点间的路径长度(n2)：利用弗洛伊的算法求两点间的最短距离。B 测试主界面当输入相应的代号，就能执行相应的操作，当键入c后则显示：5 Hash表应用 （必做）A 算法思想及数据结构及时间复杂度：哈希（哈希算法）：手机号码哈希(n)：经分析，对于一个手机号码可取代表性的几位第三、六以及后四位，根据其出现的频率不同并附其不同的权值，鉴于此程序对象是500个数据，可用公式 第三位*3+第六位*9+后四位之和*27，并采用二次探测再散列。另外开一个大的指向人员信息的指针数组，首先置其所有变量为空。当读到一个手机号码，利用上述公式计算出一个整数，然后就让该整数对应的指针指向这个人，如果这个指针已经指向别人，就用二次探测再散列解决冲突，当超出指针数组大小时，就用recalloc增大数组容量并使增添的指针置空。姓名哈希(n)：方法同手机号码哈希。利用手机号码查找，利用姓名查找：首先根据号码或姓名算出一个数n，如果指针n指向人的号码或手机与要查找人的相同，则输出这个人的信息，否则利用二次探测再散列继续查找。利用手机号删除：首先根据号码或姓名算出一个数n，如果指针n指向人的号码与要删除人的相同，则令该指针置空，如果不相同，则利用二次探测再散列继续查找直至相同，并置其为空，令mark=0（在现实所有人信息时，如果mark=1则显示，如果为0则不显示）。6、排序算法比较 （必做）A 算法思想及数据结构及时间复杂度：排序：简单排序(n2)；快排（nlogn）；堆排（nlogn）；归并（nlogn）；基数（d(n+rd)）。B 功能测试当运行程序后，就会依次排序500、1500、2000、2500、30000个数，并显示所需时间。7 家谱管理系统 （4）A 算法思想及数据结构及时间复杂度：家谱管理 （二叉树）：建树采用左母亲右孩子的方式，数据存储时采用先序遍历的方式把家谱成员写入，用二叉树中的先序方法建立原始家谱，原始家谱成员的信息中要有他的代数，以后添加时就不用在写了。显示第n代人的信息(n)：利用先序遍历，当访问节点的level与n相等时则输出他的信息图形显示(n)：自定义递归方法，使其俺家谱辈分输出，利用成员的代数，在其前打空格。按出生年月查询：利用先序遍历的方式，如果访问到的成员的出生日期与要查询人的一致则输出此人的信息。按姓名查询(n)：利用先序遍历，若访问节点有做孩子，则查看其左孩子的有孩子们有没有要查找的人，如果有则输出访问节点信息及其左孩子的信息（即是要查询人父母的信息），如果访问绩点没有左孩子或有左孩子而左孩子没有右孩子则让其指向其右孩子；若其左孩子有右孩子则指向其右孩子，依次递归。添加、删除节点(n)：利用先序遍历，当找到节点时若要删除这个节点及孩子，则令其左右孩子为NULL，并释放其所有孩子的空间。如果要添加孩子，则先判断该节点是否符合添加孩子要求，如何就执行添加操作，并对孩子的level赋值。确定两个人的关系(2n)：利用先序遍历分别找到两个人的信息，比较他们对应的level即可。按出生时间排序家谱成员(n)：另外加开一个链表，其成员为指向家谱成员的指针，利用线序排序，不断开链表并插入到链表中，是链表中的指针按顺序的指向家谱中的成员。B 功能测试主界面键入不同的号码将会执行相应的操作，如键入11，将有以下界面8 公交线路提示 （4）A 算法思想及数据结构及时间复杂度：公交线路（图论）：最少停靠点(n2)：令一条线路中相邻站点之间的权值为1，再用弗洛伊的算法求最短路径即可。最少换乘(n2)：令一条线路中任意两个站点之间的权值为1，再利用弗洛伊的算法求最短路径即可，而且易知，经过的站点就为换乘站点。B 测试主界面当键入1后则有一下界面9 关键路径问题 （3）A 算法思想及数据结构及时间复杂度：关键路径（图论）(n+e)：先用拓扑排序，把访问过的节点一次放到一个栈中，与此同时，计算出各个点的最早开始时间，并记录下来；遍历完后，再把栈中元素一次取出，计算出个点的最迟结束时间，并记录下来。若最早开始时间和相等，则这个点就是关键路径上的点。B 使用说明当执行完程序后，将把9.in中存的图的工序的关键路径和图的临界表存放在9.out中。10 电梯模拟 （5）A 算法思想及数据结构及时间复杂度：电梯模拟（栈和队列）(1)：在电梯内部设置两个栈：上升栈和下降栈，再往电梯里放元素的时候是可以插队的，对于要上升的人，就把他插入到上升栈中，并且，从栈顶到栈尾元素依次增大，为的是方便下电梯时的处理。对于要下楼的人，就把他插入到下降栈中，并且，从栈顶到栈尾元素是依次减小的，也是为了下电梯时处理的方便。在电梯外，每层设置了两个对列，如果随机产生的人要上楼，就把它放到上升队列中，反之，放在下降队列中。当电梯到达相应楼层是，只需把相应队列中的元素全部放进去就行了。另外，电梯内添加了一个callHeight数组，用来存放电梯要在哪层停，电梯外有一个upordownHeight2的二维数组，用来存放电梯外的需求，当随机产生了人后，就对其对应的upordownmn赋值，若其要上升则令upordownm1=1;反之令upordownm0=1；表示该层有上升或下降的需求。当人进入电梯后，就在对电梯内callm赋值1表示要在m层停。利用for循环执行电梯，每一次循环处理一次电梯处于上升、下降或静止的情况。B 测试主界面当输入任意时间后，则运行电梯，其表现形式如下图图中为五层楼即横线中间的部分。掐腰的人表示电梯里面，招手的人表示外面，数组时人的代号。掐腰人后面的数字表示电梯内现在的人，招手的人后面的数字表示电梯外现在的人。二 结束语终于写到结束语这最后一个环节了，数据结构课设也算是告一段落了。回想起来，在写课设的这段日子里真实很充实啊，尤其是停课之后的这段时间，每天爬起来的第一件事就是打开电脑，洗漱之后就是写程序，一直到吃午饭。然后，那道自习室去写，知道关门。有时忘记吃饭；有时望着窗外，天已经有黑转白。但最终，这一切还是挺过去了。看着这是个活灵活现的程序，心中不禁沾沾自喜。但细想起来，心中也难免有些遗憾，一方面是程序确实还存在这一些小问题，另一方面程序还有很多可以完善的地方，还有就是所有的程序都没有用到可视化界面。在问题上我总结了一下，主要有以下几点。（1）算式表达式求值：由于只用了一个字符栈，所以只能计算输入为单个位的数字，计算结果及中间数不能超过阿斯科马范围。由于时间原因，也没有进一步改进。（2）排序算法比较中的基数排序，调试了很久也通过不了，考虑到后面还有很多课设要做，就没继续调试下去。在完善这方面，主要有：（1）算术表达式求值，我完全可以在加一个数字栈，改几个变量就行了。（2）公交管理系统中，我只实现了显示最小换乘的中间站点以及最少停靠站点时经过的站点，而没有显示所乘坐车的路线名。对于最小换乘，我可以用一个数组记录各个站点，然后查看经过的相邻两个站点同时在哪些公交路线中出现即使其乘坐车的路线。同样的思路也可以应用到最少停靠站点上（3）在哈希中，程序比较散乱，没有与用户写交互界面，只是一些功能的直接展示。我计划这些需要完善的程序将是我练手MFC的首个堡垒。而在可视化方面，只是后悔当初没有学习MFC啊