课程设计指导书课程编号j1620102-0（1）课程名称数据结构课程设计周数1英文课程名DataStructureCourseDesign开课院（系）信息学院开课系计算机系修订时间2011年9月3日一、课程设计的意义:通过一个学期的系统学习，学生们掌握了数据结构的基础理论知识，然而由于数据结构原理的抽象性，可能使得学生对数据结构各部分理论的理解不够深入。设置本课程设计，通过网络光纤铺设的最佳方案选择的算法设计与实现，使学生能够学以致用，培养和提高学生的算法设计、运用计算机进行编程、调试等技能，从而培养学生独立工作的能力和创造能力。二、课程设计的主要内容:设计数据结构和算法，实现居民小区之间网络光纤铺设的最佳方案选择，主要内容如下：需要在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。三、课程设计的组织与安排:课程设计可以个人、小组（不多于3人）为单位进行，采取实验室现场辅导、电子邮件等形式相结合的方式。除了常规的实验室上机时间之外，同学们要多安排课外讨论时间和上机时间，以弥补常规时间的不足。四、课程设计的要求:认真参阅课程相关参考资料、数据，了解铺设网络光纤的原理要求，设计一个实现居民小区之间网络光纤铺设的最佳方案选择的算法：在n个居民小区之间铺设n-1条网络光纤，其最佳铺设方案既能连通所有居民小区之间的网络，又能使得光纤铺设的总代价最小。居民小区之间的网络采用图结构表示，其光纤铺设的最佳方案选择即为生成图的最小生成树。在设计的过程中，需考虑以下问题：数据结构设计：采用何种存储结构表示图文件以及最小生成树、如何设计图形的显示结构；功能设计：自动随机生成代价文件、如何读图文件以得到图的存储结构、采用何种算法计算最小生成树、采用图形形式显示最小生成树。课程设计报告要求包括以下内容：1.进行问题描述和分析。2.设计数据的逻辑结构和存储结构。3.根据存储结构设计算法。4.部分关键代码。5.进行时间复杂度和空间复杂度分析。五、课程设计的成绩评定标准:课程设计成绩采用优秀、良好、中等、及格、不及格五个分制给分，以设计过程和最终的论文情况为考核依据。课程设计报告严格按照广东海洋大学课程设计书写格式编写(10分)；课程设计报告报告以论述和说明为主，附源程序代码和运行结果(30分)；严格按照国家软件开发标准规范设计、实现算法功能、完整性好(30分)；算法中的数据存储结构设计合理高效，算法具有较低时间复杂度和空间复杂度(10分)；程序具有良好的结构和性能(10分)；严格按照课程设计进度进行，而且有创新设计(10分)。最终成绩：90-100优秀，80-89良好，70-79中等，60-69及格，0-59不及格