《《数据结构课程设计》 指 导 书 山东建筑大学 计算机科学与技术学院 二》由会员分享，可在线阅读，更多相关《《数据结构课程设计》 指 导 书 山东建筑大学 计算机科学与技术学院 二（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计 指 导 书山东建筑大学计算机科学与技术学院二六年十二月1课程设计基本情况：课程名称：数据结构课程设计 相关课程：C 语言程序设计、Visual C+程序设计、数据结构 适合专业：计算机科学与技术、网络工程、软件工程 设计周数：2 周 学 分： 2 学分 开课学期：第 4 学期 开课单位：计算机科学与技术学院一、课程设计的教学目的和任务1、 使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作 实现算法，以及它们在程序中的使用方法。 2、 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。3、 使学生掌握使用各种计算机资料和有关参
2、考资料，提高学生进行程序设计的基本能力。4、 使学生能用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备 的科学的工作方法和作风。二、课程设计的主要内容1 问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求 做什么？限制条件是什么？ 2 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为 中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每 个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要 模块的算法，并画出模块之间的调用关系图。 3 物理设计。定义相应的存储结构并写出各函数的伪代
3、码算法。在这个过程中，要综合 考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽 可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据 结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的 算法框架。 4 程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和 断言，使程序中逻辑概念清楚。 5 程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调 试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试 正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和
4、结果。 6 结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结 果。算法的时间、空间复杂性分析。 7 编写课程设计报告。2三、课程设计的基本教学要求1、 巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。 2、 培养学生自学参考书籍，查阅手册、图表和文献资料的能力。 3、 通过实际课程设计，初步掌握简单软件的分析方法和设计方法。 4、 了解与课程有关的工程技术规范，能正确解释和分析实验结果。 5、 详细情况参考数据结构课程设计教学大纲。四、课程设计报告的规范课程设计报告要求规范书写。应当包括如下八个部分： 1、 问题描述：描述要求编程解决的问题。 2、 基
5、本要求：给出程序要达到的具体的要求。 3、 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计 程序的功能。 4、 算法思想：描述解决相应问题算法的设计思想。 5、 模块划分：描述所设计程序的各个模块（即函数）功能。 6、 数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定 义的抽象数据类型。 7、 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参 数的含义和函数返回值的含义。 8、 测试情况：给出程序的测试情况，并分析运行结果。五、注意事项1、 学生必须仔细阅读课程设计任务书，认真主动完成课程设计的要求。有问题及时主
6、动 通过各种方式与教师联系沟通。 2、 学生要发挥自主学习的能力，充分利用时间，安排好课程设计的进度，并在课程设计 过程中不断检查自己的计划完成情况，及时向教师汇报。 3、 课程设计按照教学要求需要两周时间完成，两周中每天（按每周 5 天）至少要上机 4 小时来调试程序，总共至少要上机调试程序 40 小时。 4、 程设计需要学生完成两项工作，一个是把基本数据结构改写成 C+，这是每个学生都 要做的。第二是所给的任务书中选择一个。工作量不饱满者，不能及格。如果要获得 优秀成绩必须完成 2 题以上。(建议 3-4 个学生一组，每个学生主持完成任务的一个环 节，最好，一组布置 3-4 个题目，这样，
7、所有的同学可以参与所有环节的主持工作， 得到较充分的锻炼。)六、课程设计需要提交的报告1. 课程设计报告（1 份，A4 纸打印，同时包括一份电子版） 报告要求版面清晰，格式规范，否则重新编写。报告内容要求参见附录二。 2. 完整的程序系统（电子方式提交）3能够对输入产生相应的输出，同时尽量的完成可视化演示。该部分包括源代码和可执 行文件两个部分。 3. 答辩报告（编写 Power Point 答辩报告，电子方式提交） 要求突出重点，思路清晰。同时就此报告准备答辩。所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用 Winrar 或 Winzip 均可），压缩后的文件按规定格式进行命
8、名，命名格式为：学号+姓名.rar（如 2004111 李盛恩.rar）。六、成绩评定标准出勤 20%，课程设计说明书 50%，成果展示 30%。七、参考资料1. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社, 2005.11 2. 谭浩强. C 语言程序设计. 清华大学出版社, 2005.11 3. 范辉. Visual C+程序设计. 高等教育出版社八、设计报告的内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。 设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及 要求如下： 封面：题目、班级、姓名、学号、指导教师和完成日期。 正文
9、包括以下 7 个内容： 1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的 层次(调用)关系。 3详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和 其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计 算机键盘直接输入高级程序设计语言程序)；可采用流程图 N S 图或
10、 PAD 图进行描述， 画出函数和过程的调用关系图。 4调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 4改进设想；c经验和体会等。 5用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。 6测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需 求分析中所列。 7参考文献列出参考的相关资料和书籍。九、大纲执笔人和审定人编 写 人：张志军审 核 人：牛小飞批 准 人：李盛恩 编写日期：2006 年 12 月5附录 课程设计报告范例一、问题描述
11、：设编号为 1,2,n(n0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开 始时任意给出一个报数上限值 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时 停止报数，抱 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起 重新自 1 起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过 程，并给出出列人的编号序列。二、基本要求：（1）初始报数上限值 m 和测试数据在程序中确定； （2）用带头结点的单循环链表作数据元素的存储结构； （3）把带头结点的单循环链表作为抽象数据类型设计。三、测试数据：n = 7，七个人的密码依次为 3,1,7,
12、2,4,8,4 初始报数上限值 m = 20 四、算法思想：JesephRing()函数是实现问题要求的主要函数，其算法思想是：从 1 至 m 对带头结点 的单循环链表循环计数，到 m 时，输出该结点的编号值，将该结点的密码作为新的 m 值， 再从该结点的下一个结点起重新自 1 起循环计数；如此下去，直到单循环链表空时循环过 程结束。五、模块划分：（1）带头结点的单循环链表抽象数据类型 SCLinList，其中包括基本操作的函数有：初始 化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数 和判表是否非空操作函数。该抽象数据类型文件名为 SCLinList.h。 （2
13、）void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针 p 所指结点的下一个结点。这是对带头结点的单循环链表抽象数据类型 SCLinList，补充本 问题需要的一个操作函数。 （3）void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表 head,以 m 为初始报数上限值实现问题要求。 （4）void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单 循环链表，调用 JesephRing()函数实现问题要求。六、数据结构：（1）数据类型 DataType 定义如
14、下：typedef struct int number; int cipher; DataType; 6（2）带头结点单循环链表抽象数据类型 SCLinList。 （3）带头结点单循环链表抽象数据类型的结点结构定义如下： typedef struct node DataType data; struct node *next; SCLNode; 七、源程序：源程序存放在两个文件中，文件 SCLinList.h 是带头结点单循环链表抽象数据类型， 文件 Exam3-9.c 是主程序。1. 文件 SCLinList.h：typedef struct node DataType data; stru
15、ct node *next; SCLNode; /*结点结构定义*/ void SCLLInitiate(SCLNode *head) /*初始化*/ if(*head = (SCLNode *)malloc(sizeof(SCLNode) = NULL) exit(1); (*head)-next = *head; int SCLLInsert(SCLNode *head, int i, DataType x) /*插入一个结点*/ SCLNode *p, *q; int j; p = head-next; j = 1; while(p != head j+; if(j != i - 1 r
16、eturn 0; if(q = (SCLNode *)malloc(sizeof(SCLNode) = NULL) exit(1); q-data = x; q-next = p-next; p-next = q; return 1; int SCLLDelete(SCLNode *head, int i, DataType *x) /*删除一个结点*/ SCLNode *p, *q; int j; p = head; j = 0;7while(p-next != head j+; if(j != i - 1) printf(“删除位置参数错！“);return 0; q = p-next; p-next = p-next-next; *x = q-data; free(q); return 1; int SCLLGet(SCLNode *head, int i, DataType *x) /*取一个结点数
