数据结构课程设计

安徽农业大学·信息与计算机学院·《数据结构课程设计》

《数据结构课程设计》

课程中文名称：数据结构课程设计

课程英文名称：Data Structure Course Design 适用专业：计算机科学与技术相关专业

一 课程设计的性质、任务和目的

课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。

二 课程设计的基本理论

《数据结构》课程设计中牵涉到本课程中的六个主要章节的基本理论，包括基本数据结构（线性结构（线性表、栈、队列）、图、树）的特点、存储方式、运算原理和方法、典型应用和两种重要操作查找、排序的基本原理与方法。

三 课程设计的方式、设计要点和基本要求

1 方式：整个课程设计要求分为四个阶段来完成。

第一阶段为分组及准备阶段，此阶段要求将学生分成若干小组，每小组选择好设计模块，然后由学生自主进行问题分析和相关资料查询，并对课程设计内容作初步设计；

第二阶段为编程及程序调试阶段，此阶段会安排一定数量的集中上机时间，有指定的指导老师负责指导学生解决凝难问题；

第三阶段为程序测试及检查阶段，此阶段由指导老师对每位学生的设计结果作测试和检查，并根据测试及检查结果评定学生成绩，此成绩占课程设计总成绩的70%；

第四阶段为学生编写课程设计实验报告阶段，每位学生按照课程设计实验报告的内容和要求编写详细的课程设计实验报告并打印上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占课程设计总成绩的30%。

2 设计要点：设计和调试过程要规范化。

1 需求分析 ○

第 1 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。

对有些题目提出算法改进方案，比较不同算法的优缺点。

如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。 ② 源程序（可以是一组源程序，即详细设计部分）

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。 3 基本要求： 《数据结构》课程设计为实现一个综合算法设计系统，内含6个组成模块，分别对应于课程中主要章节的内容。

各模块又分为若干个子模块，各自完成一个应用操作过程，子模块根据难易程度分为两个等级，其中★级为巩固题，重在使学生熟练地掌握所学知识；★★级为能力题，具有灵活性大、难度较高的特点，学生可以通过查阅资料或在原有算法的基础上改进加以实现，重在使学生加深对所学知识的理解并发挥自己的创造能力。

《数据结构》课程设计要求学生在规定的时间内完成1或2个组成模块，并根据所选问题分析设计思路、选择数据结构描述、确立算法过程、用一种计算机语言（如C）编写出详细的实现程序，然后通过上机反复调试与修改，直到获得满意的结果为止。对于要解决的同一问题，由于所采用的数据结构可能不同、所选择的算法可能不同、编写的程序也不仅相同，但只要结果正确且有效（具有较好的时间复杂度和空间复杂度）即可，即不要求编写的算法和程序完全一致，但力求编写的算法和程序更优秀、综合指标更好。

学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。

课程设计按照教学要求需要两周时间完成，两周中每天至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。为保证质量，需要每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。

四 课程设计的内容

具体内容：（见附录A） 各模块实现的具体要求如下： 1.1顺序表的有关操作★

第 2 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

要求实现对顺序表的建立、查找、插入和删除操作。 1.2顺序表的应用举例

要求可以自选题目，并实现相关操作（如：学生成绩管理程序等）。 1.3单链表的有关操作★

要求实现对单链表的建立、查找、插入和删除操作。 1.4双向链表的有关操作

要求实现对双向链表的建立、查找、插入和删除操作。 1.5链表的应用举例★★

要求可以自选题目，并实现相关操作（如：多项式相加问题等）。 2.1栈的有关操作★

要求实现栈的入栈和出栈操作，可以任选顺序栈或链栈。 2.2栈的应用举例

要求可以自选题目，并实现相关操作（如：递归的应用等）。 2.3队列的有关操作★

要求实现队列的入队列和出队列操作，可以任选循环队列或链队列。 2.4队列的应用举例★★

要求可以自选题目，并实现相关操作（如：离散事件模拟等）。 3.1二叉树的有关操作★

要求实现二叉树的建立、各种遍历操作。 3.2线索二叉树的有关操作★

要求实现二叉树的建立、并进行线索化操作。 3.3二叉排序树的有关操作★

要求实现二叉排序树的建立、查找、插入、删除操作。 3.4二叉树的应用举例★★

要求可以自选题目，并实现相关操作（如：表达式树构造等）。 4.1图的建立★

要求实现图的建立与输出操作，可以任选存储结构。 4.2图的遍历★

要求实现图的遍历操作。 4.3图的最短路径的实现★

要求实现从一个顶点到其余顶点的最短路径操作。 4.4图的应用举例★★

要求可以自选题目，并实现相关操作（如：图的关键路径计算等）。

第 3 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

5.1插入排序有关算法★

要求实现一种性能较好的插入排序操作。 5.2交换排序有关算法★

要求实现一种性能较好的交换排序操作。 5.3选择排序有关算法★

要求实现一种性能较好的选择排序操作。 5.4其它排序算法★★

要求可以自选题目。 6.1顺序表的查找操作★

要求实现顺序查找的有关操作，任选存储结构。 6.2有序表的查找操作★

要求实现二分法查找的有关操作，注意限制的条件。 6.3哈希表的查找操作★

要求实现哈希法查找的有关操作。 6.4其它查找算法★★

—— 要求可以自选题目 ——

五 课程设计选题（见附录B）

六 课程设计实验报告内容与要求

《数据结构》课程设计实验报告要求完成的内容包括：

1、 给出问题分析过程 根据自身对课程的掌握程度，从综合算法设计系统中选做1或2个模块，并充分分析和理解问题的设计要求，给出较为明确、简洁的设计思路。

2、 给出数据结构描述

根据要解决的问题，考虑各种可能的数据结构类型，从中选择一种较为有效的方法，并写出采用的数据结构描述及其功用。

3、 给出相应算法设计

根据问题分析的结果，并确立好所选的数据结构描述，然后写出合理的算法设计过程，特别要注意所使用函数间的调用与被调用关系。

4、 给出详细程序清单

根据算法的内容，用计算机语言（如C）编写完整的程序，并将程序在机器上反复调试，直到结果正确为止，最后将程序清单打印出来，要求附上详细注解。特别要注意算法与

第 4 页 共 30 页