题目：学院：专业班级：学生姓名：指导教师：2016 年06 月2 9日目录一、课程设计目的 (3)二、课程设计步骤 (3)三、课程设计内容 (4)四、课程设计报告 (6)五、提交材料 (6)六、考核方式与评分标准 (7)七、参考文献 (8)附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9)一、课程设计目的及要求《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。

通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。

使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。

要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。

课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。

要求在教学周的第18周前完成。

二、课程设计步骤随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。

然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。

一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。

虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤：1.问题分析和任务定义通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。

因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。

注意：本步骤强调的是做什么，而不是怎么做。

对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。

例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。

这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。

2.数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。

逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。

在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。

作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说明)，各个主要模块的算法，并画出模块之间的调用关系图。

详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出过程或函数形式的算法框架。

在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。

3.编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。

程序的每行不要超过60个字符。

每个过程(函数)体，即不计首部和规格说明部分，一般不要超过40行。

最长不得超过60 行，否则应该分割成较小的过程(函数)。

要控制语句连续嵌套的深度。

如何编写程序才能较快地完成调试是特别要注意的问题。

对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。

然而，不管你是否写出编码的程序，在上机之前，认真的静态检查却是必不可少的。

多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。

这两种态度是极为有害的。

事实上，非训练有素的程序设计者编写的程序长度超过50 行时，极少不含有除语法错误以外的错误。

上机动态调试决不能代替静态检查，否则调试效率将是极低的。

静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。

如果程序中逻辑概念清楚，后者将比前者有效。

4.上机准备和上机调试上机准备包括以下几个方面：(1) 高级语言文本(体现与编译程序用户手册)的扩充和限制。

例如，有些C 编译程序限制for语句的循环控制变量为局部简单变量等。

(2) 如果用C语言，要特别注意平时惯用的类C语言与标准C语言之间的细微差别。

(3) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。

(4) 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。

“磨刀不误砍柴工”。

计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。

上机调试程序时要带一本高级语言教材或手册。

调试最好分模块进行，自底向上，即先调试低层过程或函数。

必要时可以另写一个调用驱动程序。

这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。

在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。

调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思具想”，而应动手确定疑点，通过修改程序来证实它或绕过它。

调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。

5.总结和整理实习报告注意：在实践中，有时候可能想检验自己的想法，这时可以上机尝试一下，看看自己的思路是否可行。

三、课程设计内容参考题目：1．二叉树的应用－哈夫曼树（电文的编码和译码）2．运动会分数统计3．学生成绩管理系统4．简易客房管理系统5．其他类型管理系统的题目①人事档案管理系统②图书管理系统③进销存货物管理系统④职工工资管理系统6.稀疏矩阵运算器7.长整数的四则运算8.校园导游咨询10．停车场管理11其余题目：（必须事先得到指导老师允许）程序经常需要输入输出，所以可以在考虑采用什么样的数据结构时，考虑如何进行数据的输入和输出，可以把输入和输出分别实现为一个函数。

实现了输入输出功能，也为以后程序的调试和测试带来方便。

四、课程设计报告课程设计报告统一用A4纸打印，并装订成册，封面格式参见所附文档，正文格式要求参见附录1。

课程设计报告内容具体要求如下：1.课程设计实验报告内容总体要求1）给出问题分析过程根据自身对课程的掌握程度，充分分析和理解问题的设计要求，给出较为明确、简洁的设计思路。

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

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

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

特别要注意算法与程序的区别以及上下层模块间的接口处理。

5）给出程序运行结果利用典型的测试用例，将数据输入到程序执行过程中去，记下执行过程中屏幕显示情况与相应结果。

2.具体内容要求：报告包括以下7个内容：1）以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2）概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3）详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。

4）调试分析内容包括：(1) 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；(2) 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)(3) 改进设想；(4) 经验和体会等。

5）用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。

6）测试结果列出你的测试结果，包括输入和输出。

这里的测试数据应该完整和严格，最好多于需求分析中所列。

7）附录带注释的源程序，如果提交程序，可以只列出程序文件名的清单。

五、提交材料课程设计完成后的下一周的周一上午，也就是2012年6月28-29日，提交如下资料并答辩：1．课程设计报告。

课程设计报告总体上主要包括以下几个部分：1）封面2）考核方式与评分标准(见六)3）目录4）课程设计报告正文5）使用说明2.完整的软件系统最终必须向指导老师提交完整的程序源代码(.c和.cpp以及.h为后缀的文件)、数据文件以及使用说明文件等。

源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有8条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。

课程设计项目源代码和相关数据，放到一个目录下，目录名以学号加姓名方式命名。

六、考核方式与评分标准（下页单独打印）综合实践1评分表在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下不及格。

七、参考文献1．严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社, 1997.4 2．严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社, 1999.2附录1齐齐哈尔大学数据结构课程设计说明书（报告）撰写规范（一）正文：汉字应采用《简化汉字总表》规定的简化字，并严格执行汉字的规范。

所有文字字面清晰，不得涂改。

要求文字通顺，语言流畅，无错别字，不得使用铅笔书写。

正文内容层次序号为：1、1.1、1.1.1……。

正文内容一般为：1、选题背景：说明本课题应解决的主要问题及应达到的技术要求；简述本设计的指导思想。