结构课程设计指导09(2010

《结构课程设计指导09(2010》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息科学与技术学院算法与数据结构（分册）盐城师范学院信息科学与技术学院编2010.12《算法与数据结构》课程设计一、概述（一）课程设计的性质、目的与作用算法与数据结构是计算机及其相关专业一门重要的核心课程，是学习计算机软件设计的重要基础课程。从实际工作需要来看，仅靠教学计划安排的课内实践时间是难以满足要求的，为了帮助同学扎实的掌握数据结构内容，提高运用数据结构的方法解决实际问题的能力，有计划、有目的、有系统地进行必要的实践训练，编写了《算法与数据结构》课程设计这部分内容。课内的实验是侧重于对某一

2、方面知识的学习，在解决实际问题时，可能涉及并运用多个方面的知识，具有较强的综合性，这就需要进行一些综合性的设计练习，来提高分析和解决实际应用问题的能力。数据结构课程设计的目的是利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不算太复杂却具有综合性的问题。通过课程设计，在建立问题模型、构造求解算法、设计数据结构、编写程序代码及上机调试等方面得到全面的锻炼，从而能更深刻地理解《算法与数据结构》的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。包括，1．熟练掌握数据结构的一些常

3、用算法和经典算法；2．熟练的运用常用的算法和经典算法解决具有一定规模和复杂程度的实际问题；3．熟练掌握分析问题和解决问题的方法，合理选择数据结构，学会分析算法的优劣，分析算法的复杂度。（二）课程设计的要求在课程设计时，对要解决的问题，要注意以下几个方面：1．正确性：设计的算法要严谨、正确，能正确解决实际问题，符合指定的要求；2．高效：有效的建立数学模型，合理的选择数据结构，编写高效的程序代码；3．清晰：算法和程序的结构要清晰，算法要用流程图来表示，程序代码要加注解；4．设计报告：每一个问题解决后

4、，要按统一的纸张及格式，完整、整洁地写出设计报告，打印程序清单，拷贝所做设计的电子版文档和程序。（三）设计报告格式在将综合设计作为教学的一个环节时，设计报告一般包括以下几个方面的内容：1．设计任务、要求和所用的软件环境和技术；1．设计思想及其简要说明；2．设计的算法，以及算法可能由几个模块组成，算法用流程图表示出来；3．使用说明，包括使用前提，所用软件环境，文件清单；4．验收时间，验收情况说明等；5．通过课程设计的收获以及对所用方法的分析和综合；6．打印的程序清单以及结果，结果以贴图的方式附在报

5、告后。二、预备知识（一）TurboC2.01、编辑环境2、上机步骤运行程序:Ctrl+F9显示程序运行结果：Alt+F5（二）数据结构基础1、线性表的顺序和链式表示和实现2、栈和队列的表示和实现以及应用3、递归和非递归的转化4、串的表示和实现5、数组的应用6、树及其二叉树的表示、实现、遍历和应用7、图的表示方法及其遍历和应用8、各种查找方法的实现和分析及应用9、各种排序方法的实现和分析和应用三、《算法与数据结构》课程设计课题可供选择的课程设计题：【课题1】用贪婪法求解“货郎担问题”。所谓“货郎担

6、问题”是指，给定一个无向图，并已知各边的权，在这样的图中，找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小。【课题2】背包问题。从N件不同价值、不同重量的物品中选取一部分物品，在不超过规定重量的情况下，使这部分物品的总价值最大。【课题3】用十字链表表示稀疏矩阵，并实现稀疏矩阵加法。【课题4】马的遍历问题。设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个“马”．均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。程序输出8×8方阵，用1－

7、64表示走过每个位置的次序，起始点标为1。【课题5】编写程序，初始从键盘输入二叉树的结点数据创建二叉树，并将该二叉树的数据以某种方式存储到文件btree.dat中，以便程序此后运行时从文件中读取数据构建该二叉树；要求能根据指定结点求出其在二叉树中所在的层数。【课题6】若某算术表达式采用后置法表示（即逆波兰表达式），请编程计算该表达式的值。如：表达式(a+b*c)/d-e用后置法表示为abc*+d/e-。【课题7】最短路径问题。用有向图表示道路网，有向边上的权表示两地间的距离，要对如下图求出从c1

8、到各点的最短路径（程序应通用）。【课题8】若已知一棵二叉树的先序序列和中序序列（如从键盘输入），设计算法及程序实现构造其对应的二叉树。【课题9】利用二叉排序树可以实现集合的插入、删除和查找操作。编写程序统计一份英文文献中单词使用的频度。【课题10】设计程序完成如下功能：对给定的图结构和起点，产生其所有的深度优先搜索遍历序列（深度优先搜索序列不唯一）。【课题11】设计程序完成如下功能：对给定的有向图，用Kruskal算法的基本思想求解出所有的最小生成树。【课题12】设计程序完成如下功能：对给定的A