《结构课程设计指导09(2010》由会员分享，可在线阅读，更多相关《结构课程设计指导09(2010（10页珍藏版）》请在金锄头文库上搜索。
1、信息科学与技术学院信息科学与技术学院算法与数据结构算法与数据结构 （分册）（分册）盐城师范学院信息科学与技术学院编盐城师范学院信息科学与技术学院编2010.122010.12算法与数据结构算法与数据结构课程设计课程设计一、概 述（一）课程设计的性质、目的与作用算法与数据结构是计算机及其相关专业一门重要的核心课程，是学习计算机软件设计的重要基础课程。从实际工作需要来看，仅靠教学计划安排的课内实践时间是难以满足要求的，为了帮助同学扎实的掌握数据结构内容，提高运用数据结构的方法解决实际问题的能力，有计划、有目的、有系统地进行必要的实践训练，编写了算法与数据结构课程设计这部分内容。课内的实验是侧重于对
2、某一方面知识的学习，在解决实际问题时，可能涉及并运用多个方面的知识，具有较强的综合性，这就需要进行一些综合性的设计练习，来提高分析和解决实际应用问题的能力。数据结构课程设计的目的是利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不算太复杂却具有综合性的问题。通过课程设计，在建立问题模型、构造求解算法、设计数据结构、编写程序代码及上机调试等方面得到全面的锻炼，从而能更深刻地理解算法与数据结构的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。包括，1熟练掌握数据结构的一些常用算法和经典算法；2熟练的运用常用的算法和经典算法解决具有一定规模和复杂程度的实际问题；3熟练掌握分析
3、问题和解决问题的方法，合理选择数据结构，学会分析算法的优劣，分析算法的复杂度。（二）课程设计的要求在课程设计时，对要解决的问题，要注意以下几个方面：1正确性：设计的算法要严谨、正确，能正确解决实际问题，符合指定的要求；2高效：有效的建立数学模型，合理的选择数据结构，编写高效的程序代码；3清晰：算法和程序的结构要清晰，算法要用流程图来表示，程序代码要加注解；4设计报告：每一个问题解决后，要按统一的纸张及格式，完整、整洁地写出设计报告，打印程序清单，拷贝所做设计的电子版文档和程序。（三）设计报告格式设计报告格式在将综合设计作为教学的一个环节时，设计报告一般包括以下几个方面的内容：1 设计任务、要求
4、和所用的软件环境和技术；2 设计思想及其简要说明；3 设计的算法，以及算法可能由几个模块组成，算法用流程图表示出来；4 使用说明，包括使用前提，所用软件环境，文件清单；5 验收时间，验收情况说明等；6 通过课程设计的收获以及对所用方法的分析和综合；7 打印的程序清单以及结果，结果以贴图的方式附在报告后。二、预备知识（一） Turbo C 2.01、编辑环境2、上机步骤开开始始编编辑辑编编译译有有错错连连接接执执行行结结果果正正确确结结束束正正确确有有无无不不正正确确运行程序:Ctrl+F9显示程序运行结果：Alt+F5（二） 数据结构基础1、线性表的顺序和链式表示和实现2、栈和队列的表示和实现
5、以及应用3、递归和非递归的转化4、串的表示和实现5、数组的应用6、树及其二叉树的表示、实现、遍历和应用7、图的表示方法及其遍历和应用8、各种查找方法的实现和分析及应用9、各种排序方法的实现和分析和应用三、三、 算法与数据结构算法与数据结构课程设计课题课程设计课题可供选择的课程设计题：【课题 1】用贪婪法求解“货郎担问题” 。所谓“货郎担问题”是指，给定一个无向图，并已知各边的权，在这样的图中，找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小。【课题 2】背包问题。从 N 件不同价值、不同重量的物品中选取一部分物品，在不超过规定重量的情况下，使这部分物品的总价值最大。【课题
6、3】用十字链表表示稀疏矩阵，并实现稀疏矩阵加法。【课题 4】马的遍历问题。设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个“马” 均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。程序输出 88 方阵，用 164 表示走过每个位置的次序，起始点标为 1。【课题 5】编写程序，初始从键盘输入二叉树的结点数据创建二叉树，并将该二叉树的数据以某种方式存储到文件 btree.dat 中，以便程序此后运行时从文件中读取数据构建该二叉树；要求能根据指定结点求出其在二叉树中所在的层数。【课题 6】若某算术表达式采用后置法表示（即逆波兰表达式） ，请编程计算该表达式的
7、值。如：表达式(a+b*c)/d-e 用后置法表示为 abc*+d/e-。【课题 7】最短路径问题。用有向图表示道路网，有向边上的权表示两地间的距离，要对如下图求出从 c1 到各点的最短路径（程序应通用） 。C C1 1C C2 2C C3 3C C4 4C C5 5C C6 6 C C8 8C C7 73 32 2 5 59 9 7 7 5 5 3 35 54 41 15 58 87 74 41 1【课题 8】若已知一棵二叉树的先序序列和中序序列（如从键盘输入） ，设计算法及程序实现构造其对应的二叉树。【课题 9】利用二叉排序树可以实现集合的插入、删除和查找操作。编写程序统计一份英文文献中单
8、词使用的频度。【课题 10】设计程序完成如下功能：对给定的图结构和起点，产生其所有的深度优先搜索遍历序列（深度优先搜索序列不唯一） 。【课题 11】设计程序完成如下功能：对给定的有向图，用 Kruskal 算法的基本思想求解出所有的最小生成树。【课题 12】设计程序完成如下功能：对给定的 AOV 网，求出该 AOV 网所有的拓扑序列。【课题 13】设计程序以实现构造哈夫曼树的哈夫曼算法，并计算出所构造的哈夫曼树的带权路径长度。【课题 14】设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及 SQR 和 ABS 函数的任意整型表达式进行求解。【课题 15】选择合适的存储结构表示图
9、，在此基础上实现求解最短路径的 Dijkstra算法。【课题 16】若二叉树采用二叉链表存储，利用栈实现中序线索化二叉树的非递归算法。【课题 17】 设计一个简单的文本编辑器，使其具有通常编辑器（如 Notepad）具备的功能。【课题 18】苏州园林导游程序设计。用无向网表示苏州园林的平面图，图中顶点表示著名园林，存放园林的编号、名称、特色简介等信息，图中的边表示园林间的通路，存放路径长度等信息。要求实现以下功能：（1）根据园林名称或编号查询各园林的相关信息；（2）查询图中任意两个园林间的最短路径；（3）查询图中任意两个园林间的所有路径。【课题 19】散列法的实验研究。散列法中，散列函数构造方
10、法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。给出程序及实验数据对比、分析研究。【课题 20】 “吃金子”游戏在地下某处藏有金子（g） ，有一个精灵（）寻找并获取金子。游戏者通过输入四个方向键指挥精灵沿该方向移动去吃金子（每输入一次方向键只移动一步） ；金子是随机地、每隔一段时间出现在不同的位置，游戏者需在金子消失前到达才能获取它。游戏者的成绩是看其在一定时间内获取的金子数量计算。如下图示。所需知识：数组、随机数、键盘输入码的识别-g-g-g-g-（提示：需要使用一些库
11、函数，如： 原型 int bioskey(int cmd)所属头文件 bios.h功能 返回键盘读取一个按键的 ASCII 值，两字节。Cmd 参数说明：参数 cmd 确定实际的操作，cmd 取值为0返回下一个键盘输入的字符，如果低 8 位非 0，则为 ASCII 码；如果低 8 位为 0，则高 8 位为扩展键盘代码查 PC ASCII 表。1测试是否有可读的输入键，如果返回 0，则表示没有；否则返回下一个输入键。键还保存，供下次参数 cmd 为 0 的 bioskey 调用返回。2请求当前移位(Shift)状态 原型 void gotoxy(int x,y)所属头文件 conio.h功能 将
12、光标移动到(x,y)坐标处。屏幕的坐标系左上角为(0,0)。 ）【课题 21】五子棋游戏游戏者 A、B 对奕五子棋（规则略） ，百子用 W、黑子用 B 表示，在一个 n*n 的棋盘上对奕，棋盘屏幕布局如下图示例。所需知识：二维数组。123456789ABCDEFGHIJKLMNO2 WBW3 BWWB4WBBPlayer A:X- Y- Player B:X- Y-【课题 22】有若干生产者和消费者，生产者负责生产商品、每生产处一个商品就放入一个环形缓冲区中的空闲缓冲区中供消费者取商品消费，并检查是否有消费者等待取商品，若有就唤醒他；如果没有空闲的缓冲区则排入等待队列等待消费者取走商品后空出缓
13、冲区。同样，消费者到环形缓冲区中找一个存有商品的缓冲区取商品，如果所有缓冲区均空（无商品可供消费）则排入消费者队列等待，如果有商品可取、取出商品后查看生产者队列是否有等待的生产者并唤醒他。环形缓冲区如下图所示。所需知识：环形队列、链队列。【课题 23】在网吧管理中，需要在每个客户用时（下机）到达前 5 分钟提醒客户。由于当前上机的用户数目不确定、每个用户的下机时间不同，所以需要采用链表结构的间隔时钟进行管理。链表钟头节点中记录的时间值是相对于当前时间还需经过的时间、而后继节点中记录的时间值是相对于其前趋节点的终止时间还需经过的时间。系统设置一个时钟中断，时钟中断处理程序总是从头节点开始检查需要
14、发布提醒信息的用户（节点）并提醒之，并修改剩余节点中的间隔时间值（减去头节点中的值） 。所需知识：链表。【课题 24】老鼠走迷宫。有一个 n*n 格的迷宫，有些格子是墙不能通过、而另一些是通道可以通行。整个迷宫有一个入口和一个出口，四周也是墙。老鼠从入口进入顺可以通行的通道前进，当遇到无法通行的墙时就需要尝试另一方向前进、直到所有方向（除了进入得方向）尝试完还不能前行，就得后退再寻找出路。所需知识：数组、回溯程序设计。提示：用数组 Mazenn表示迷宫，标志数组 mark用来记录已走过的位置，还要能对下一步前进方向计算出下已位置等。见下图示。入口-0 0 0 1 1 1 1 1 1 1 1 1
15、 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 1 1 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 1 0 0 0 0 1 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 0 0 1 1 1 1 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 1 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 0 0 1 0 11 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1【课题 25】设有一算术表达式，参与运算的数据均为 1 位数字、并且只使用加、减、乘、除四则运算和圆括号，编程实现该表达式求值计算。所用知识：栈和字符串。提示：教材上有该题的算法，需具体实现。也可以参考其他方法。【课题 26】将 n 个名字（每个名字步超过 10 个字符-可英文单词表示）建立成一个单链表，节点中包含名字、原（输入时的）序号、指向下一个节点的
