数据结构B课程设计指导书(按要求)讲述.doc

数据结构B课程设计 指导书 目录 1 课程简介 3 2 教学目的与意义 3 3设计内容、任务描述 3 4 课程设计主要步骤与时间分配 3 4.1 课程设计的主要步骤 3 4.2 课程设计进度安排 4 5 课程设计过程中的各环节内容 4 5.1建立模型 4 5.2选择合适的存储结构 4 5.3 构造求解算法 5 5.4编写程序 5 5.5测试 6 5.6 撰写课程设计报告 6 6 课程设计成绩的评定 7 附录1：参考选题 8  1 课程简介 数据结构信息管理与信息系统专业的重要基础课程是一门实践课程数据结构在教师的指导下，利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不太复杂但却是综合性的问题。从规模来说，课程设计是在平时作业的基础上进一步扩大的大作业。在设计中，要求学生要全面考虑相互联系的各个方面及问题。? 教学目的与意义 数据结构信息管理与信息系统专业的重要基础课程通过课程设计，使学生对整个数据结构课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习、毕业设计环节以及将来的实际工作打好坚实的基础。3设计内容、任务描述在认真研读教材，理解讲课内容的基础上，参考选题中选1-2个设计课题可自拟课程相关题目，问题，运用《数据结构》、程序设计以及迄今为止所学课程中的各种基本技术和理论在规定的时间内完成数据模型的选择、数据结构的定义、求解算法设计及程序编制及调试。 4 课程设计与时间4.1 课程设计周模型建立储选择解编写测试、4.2 课程设计集中讲授：2学时模型建立储选择：1解编写测试：时间（第二天5 课程设计过程中的各环节 5.1建立模型 建立模型通常包括所描述问题中的数据对象及其关系的描述、问题求解的要求及方法等方面。将一个具体的问题转换为所熟悉的模型，要描述群体中个体之间的关系时，可以采用《离散数学》中所介绍的图结构。要一个工程时，可以采用图结构 AOV 网或 AOE 网等。数值计算问题中常用的数学模型为线性方程组(用于求解电路的电流强度或结构中的应力)或微分方程(用于预报人口增长情况或化学反应速度等)。《离散数学》及许多数学课程中就介绍了许多模型。《数据结构》课程中所介绍的各种结构模型。数学模型的建立是求解实际问题的基础。一般情况下，实际应用问题可能会各式各样，但问题都是同一类数学模型，例如我们所熟悉的工资表的处理问题学生成绩管理问题电话号码查询问题图书管理系统等都属于‘线性表’这种模型。只要掌握‘线性表’的存储结构、操作算法我们就能解决如工资表的处理、学生成绩管理等一系列问题，学习《数据结构》这门课程的根本目的就在于此。再如：n个选手P1，P2，P3，…，Pn参加的单循环赛中，每对选手之间非胜即负。现要求求出一个选手序列P1′，P2′，P3′，…，Pn′，使其满足Pi′胜Pi+1′(i=1,…,N-1)。这个问题看似复杂，由于仅涉及到n个选手，并且这些选手之间的关系仅是胜负关系，因此可用图这种数学模型i′胜Pj′，有从i到j的一条弧，在这种表示下，本题问题变成了在有向图中求解出一条包含所有顶点的简单路径的问题。由此可见，正确选择数学模型5.2选择合适的存储结构 在构造出求解算法之后，就需要考虑如何在计算机上实现。从算法到程序还是有一定距离的。为此，需要做两方面的工作，其一是选择合适的存储结构，其二是用指定的计算机语言来描述算法。下面先讨论第一个方面，即选择存储结构的问题。 选择合适的存储结构首先是为了将问题所涉及到的数据(包括数据中的基本对象及对象之间的关系)存储到计算机中。此外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。《数据结构》课程中已经对此作了许多讨论。在实际应用时，需根据问题的要求进行合理的选择及综合。不同的存储形式对问题的求解实现有较大的影响，所占用的存储空间也可能有较大的差异。例如，顺序存储结构一般来说便于直接存取，从而节省存取时间，但是在插入和删除元素时需要移动元素，从而浪费时间，而链式存储结构在插入和删除元素时无需移动元素，但需花费时间来有哪些信誉好的足球投注网站元素。线性表较多采用顺序存储结构，而非线性结构则不宜采用这种形式。 5.3 构造求解算法 在建立好模型之后，一个具体的问题就变成了一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识(例如数据结构中有关图结构的基本知识)，我们可以相对容易地描述出原问题的求解方法即算法。从某种意义上说，该算法不仅能实现原问题的求解，而且还能实现许多类似的具体问题的求解，尽管这些具体问题的背景及其描述形式可能存在较大的差异。 算法设计的核心是给出问题求解的基本算法。所给出的算法并非一定要用某种计算