2015年实验指导书(信管专业).doc

数据结构课程设计实验指导书一、课程设计要求课程设计报告要求按照如下几个内容认真完成；其中包括：1、需求分析：在该部分中叙述，每个模块的功能要求。2、概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。3、详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。4、调试分析：测试数据，测试输出的结果和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 5、 课设总结：总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容；二、课程设计内容1、线性表的使用问题描述利用单链表编写一个学生成绩系统，具体包括查询成绩、修改成绩、删除成绩、新增成绩、全班平均成绩等。2、树的遍历问题描述已知以二叉链表做为存储结构，编写按层次顺序遍历二叉树的算法。实现提示采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，如此直到队列空为止。3、二叉排序树的建立和遍历问题描述 已知二叉排序树以二叉树链表作存储结构，编写按从大到小的顺序输出二叉排序树的各个结点的算法。实现提示 先建立一棵二叉排序树，以二叉链表表示。由于按中序遍历二叉排序树即按递增次序遍历，所以要按从大到小的顺序输出二叉排序树的各结点的值，可以对二叉排序树从树根结点中最右下的结点开始进行遍历，先遍历右子树，再访问根结点，最后遍历左子树，这样就可以得到一个按从大到小的顺序输出的序列。4、图的搜索问题描述 很多涉及图上操作的算法都是以图的遍历作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。实现要求 以邻接矩阵为存储结构的图进行dfs和bfs,以邻接表为存储结构的图进行dfs或bfs。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。5、排序问题描述给出n 个学生的考试成绩表，每条信息由姓名与分数组成，试设计一个算法(1)按分数高低次序打印出每个学生在考试中获得的名次，分数相同的为同一名次；(2)按名次列出每个学生的姓名和分数。实现要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。用冒泡排序或快速排序算法实现该问题，最后要对结果做简单分析。6、查找问题描述建立一棵二叉查找树，再在这棵树中查找某一指定结点，最后显示查找结果。实现提示先将欲查找的数值与二叉树的根结点比较，如果比根结点小，再与左子树的根结点比较，否则与右子树的根结点比较，如此，直到找到数据或到达了叶结点为止。7、哈夫曼树的使用问题描述 构造哈夫曼树和哈夫曼编码设一份电文中有不同出现频率的字符，为了提高电文的输入和翻译效率，必须有一套简短而又不会产生歧义的字符代码。试根据哈夫曼算法，对电文中的不同字符，构造出一棵哈夫曼树，对每个字符进行编码。8、病人看病模拟问题描述病人到医院看病排队看医生的情况。（1）在病人排队过程中，主要重复两件事：1）病人到达就诊室，将病历交给护士，排到等待队列中候诊。2）护士从等待队列中取出下一位病人的病历，该病人进入入诊室就诊。 （2）模拟病人等待就诊这一过程：1）排队：输入排队病人的病历号，加入到病人排队队列中。2）就诊：病人排队队列中最前面的病人就诊，并将其从队列中删除。3）查看排队：从队首到队尾列出所有的排队病人的病历号。4）不再排队，余下依次就诊从队首到队尾列出所有的排队病人的病历号，并退出运行。5）医生下班：退出运行。实现提示 考虑到病人排队候诊的过程中具有先排队就诊的特诊，与队列的先进先出的特征相吻合，因此可以考虑采用队列线性表，其中，队列的存储结构有循环顺序队列和单链队列。考虑到循环顺序队列的插入，删除浪费空间和时间，故本题建议采用单链队列。9、十进制四则运算计算器问题描述在以二叉树表示算数表达式的基础上，设计一个十进制的四则运算的计算器。基本要求实现整数的四则运算。实现要求为了更接近实际问题，输入要求与一般常用的真实计算器一样。问题中的一个技术难点是对输入的算术表达式字符串进行分析，自动找出运算符和操作数。实现提示表达式的建立和求值都可以借助栈来完成。10、停车场问题问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。实现要求要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。实现提示汽车的模拟输入格式可以是：（到达/离去，汽车牌照号，到达/离去的时刻）。例如，（A，1，5）表示1号牌照车在5这个时刻到达，而（D，5，20）表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为（E,0,0）时结束。本题可以用栈和队列来实现。11、利用树形结构的搜索算法模拟因特网域名的查询问题描述在计算机网络课程中我们曾讨论Internet的域名系统，以树形结构实现域名的搜索。即输入某站点的域名，在域名系统的树形结构中进行搜索，直至域名全部匹配成功或失败；若成功则给出该站点的IP地址，否则给出找不到该站点的信息。实现要求首先要实现一个反映域名结构的树，例如杭州电子科技大学站点在该树丛根到叶子的各层结点就是root、cn、edu、hdu、www。叶子结点另有一个数据域存放杭电的IP地址82。实现提示1） 可以取常用到的著名站点的域名和IP地址为例构建域名结构的树，一般应该有30个左右的站点域名。当输入时，输出为“82”；而当输入时，