数据结构算法设计

《数据结构算法设计》由会员分享，可在线阅读，更多相关《数据结构算法设计（66页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法分析课程设计内容体系主要内容数据结构课程设计课程，可使学生深化理解书本知识，致力于用学过的 理论知识和上机取得的实践经验，解决具体、复杂的实际问题，培养软件工作者 所需的动手能力、独立解决问题的能力。该课程设计侧重软件设计的综合训练， 包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧、多人 合作，以至一整套软件工作规范的训练和科学作风的培养。一、课程设计要求学生必须仔细阅读数据结构与算法分析课程设计方案，认真主动完成课 程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划， 并在课程设计过程中不断

2、检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要两周时间完成，两周中每天（按每周 5 天）至少 要上3-4 小时的机来调试 C 语言设计的程序，总共至少要上机调试程序 30小时。二、数据结构课程设计的具体内容本次课程设计完成如下模块（共 9个模块，学生可以在其中至少挑选 6 个功 能块完成，但有*号的模块是必须要选择的）1） 运动会分数统计*任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1 m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为： 7、5、3、2、1，前三名的 积分分别为：5、3、2 ；哪些

3、取前五名或前三名由学生自己设定。（mv=20,nv=20 ） 功能要求： 可以输入各个项目的前三名或前五名的成绩；能统计各学校总分； 可以按学校编号、学校总分、男女团体总分排序输出； 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前 三或前五名的学校。规定：输入数据形式和范围： 20以内的整数（如果做得更好可以输入学校 的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相 关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数 据要存储在数据文件中。（数据文件的数据读写方法等相

4、关内容在 c 语言程序设 计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据； 2、整体非法数据； 3、局部非法数 据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中 写明；2）订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具 体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵 达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市， 查询飞机航班情况；订票：可以订票（订票情况可以存在一个数据文件中，结构自己设定），如 果该

5、航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票 数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件 要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序 完成功能；（3）文章编辑*功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储 一页文章，每行最多不超过 80个字符，共 N 行；要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统 计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后 面的字符前移。（4）存储结构使用线性表，分别用几个子函数

6、实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点 符号。输出形式：（1）分行输出用户输入的各行字符；（2）分 4 行输出全部字母 数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文 章；（4 ）约瑟夫环（Joseph ）任务：编号是1 , 2 ,小的n个人按照顺时针方向围坐一圈，每个人只 有一个密码（正整数）一开始任选一个正整数作为报数上限值m,从第一个仍开 始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的 密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下 去，直到所有人全部出列为止。设计一个程序来求出出列

7、顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人 的编号。测试数据： m 的初值为 20， n=7 ,7 个人的密码依次为 3， 1， 7， 2， 4， 7， 4， 首先m=6,则正确的输出是什么？输入数据：建立输入处理输入数据，输入m的初值，n，输入每个人的密 码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列（ 5）猴子选大王*任务：一堆猴子都有编号，编号是1，2,3 .m，这群猴子（m个）按照1-m 的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样 依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入数据：输入 m,n m,

8、n 为整数， nm输出形式：中文提示按照 m 个猴子，数 n 个数的方法，输出为大王的猴子 是几号 ，建立一个函数来实现此功能（6）建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以）*任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列； 分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先 序遍历序列的函数；（7）赫夫曼树的建立任务 ：建立建立最优二叉树函数要求：可以建立函数输入二叉树，并输出其赫夫曼树 在上交资料中请写明：存储结构、 基本算法（可以使用程序流程图） 、输 入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改 进方法；

9、（8）纸牌游戏*任务：编号为 1-52 张牌，正面向上，从第2 张开始，以2 为基数，是 2 的 倍数的牌翻一次，直到最后一张牌；然后，从第 3 张开始，以 3 为基数，是 3 的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4 的倍数的牌翻一次， 直到最后一张牌； .再依次5的倍数的牌翻一次， 6的， 7 的 直到 以 52 为基数的 翻过，输出：这时正面向上的牌有哪些？（9）图的建立及输出任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向 网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存 储结构中，而后输出图的邻接矩阵。要求：给出图的

10、深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果三、上交相关内容要求上交的成果的内容必须由以下四个部分组成，缺一不可1 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该 放到一个文件夹中）；2 .上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说 明；3 课程设计报告：（保存在 word 文档中，文件名要求 按照姓名-学号-课程设计报告起名，如文件名为张三-001-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括:需求分析：在

11、该部分中叙述，每个模块的功能要求 概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该 存储结构的定义。 详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写 程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分 要加上清晰的程序注释。调试分析：测试数据，测试输出的结果，时间复杂度分析，和每个模块 设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的 改进设想。4. 课设总结： （保存在 word 文档中）总结可以包括 : 课程

12、设计 过程的 收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据 结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容数据结构与算法分析课程内容体系主要内容教学单元模块具体教学内容绪论绪论部分是全书的预备知识，主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C+做了简单介绍基本数据结构基本数据结构部分包括线性表、堆栈与队列、数组、字符 串、整数集合类、树（包括AVL树、伸展树等）图（包 括网络流等问题的讨论）散列（Hash ）等典型算法典型算法部分主要介绍了若干典型算法的实现，并给出必 要的复杂性分析和比较过程，具体包括递归、排序、查找和内存管理等复杂数

13、据结构复杂数据结构部分主要包括优先级队列、不相交集合类和文件结构等算法设计技巧典型算法设计技巧的介绍，主要包括贪婪算法、分治算法、 动态规划、回溯算法和随机化算法等应用应用部分是上述数据结构和典型算法的一些应用示例，具 体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问 题的讨论，在课时允许的情况下还会介绍摊还分析、红黑 树等数据结构与算法分析课程实践内容体系主要内容实践教学 单元模块实践教学基本要求实践教学具体内容趣味程序 设计实践1. 熟悉编程环境2. 复习C语言程序 设计的基本内容1.开学第一、二周布置若干趣味程序设计题目，如奇数阶幻 阵算法、万年历算法、迷吕算法等。并元成：2随机产生n

14、个整数，然后用一种排序算法将它们从小到大 排序。3试编一程序，用贪心法求解一般的着色问题。链表应用 实验1. 熟悉链表结构2. 掌握链表结构上 的各种操作3. 学会运用链表结 构求解问题1.试将本早介绍的两种Josephus问题的求解过程在计算机 中实现，实现时要求输出的不是整数，而是实际的人名。2设A与B分别为两个带有头结点的有序循环链表（所谓有 序是指链接点按数据域值大小链接，本题不妨设按数据域 值从小到大排列），listl和list2分别为指向两个链表 的指针。请写出并在计算机上实现将这两个链表合并为一 个带头结点的有序循环链表的算法。栈与队列 应用实验1. 熟悉栈和队列结 构2. 掌握

15、栈和队列结 构上的各种操作3. 学会运用栈和队 列结构求解问题1. 设计实现一个求解n阶Hanoi塔问题的算法提示：将n个圆盘由A依次移到C，B作为辅助塔座。当 n=1时，可以直接完成。否则，将塔座A顶上的n-1个圆 盘移动到塔座B上，用塔座C作为辅助塔座；然后移第n 个圆盘；最后将塔座B上的n-1个圆盘移到塔座C 上,并 用塔座A作为辅助塔座。2. 根据书中介绍的思想，设计并实现一个对简化表达式求 值的系统。3. 在计算机上模拟实现农夫过河问题的解。文本文件 检索实验1. 熟悉字符串的操 作2. 学会运用字符串 的操作进行文本 检索和查询。1.根据课堂介绍设计实现KMP算法2试设计一个简单的文本编辑器，使之具有对字符串的输 入、输出、插入、删除、查找和替换等功能3.设计实现一个通用的判定回文个数问题的算法程序稀疏矩阵 和广义表 实验1. 熟悉稀疏矩阵和 广义表结构2. 掌握稀疏矩阵和 广义表结构上的 各种操作3. 学会运用稀疏矩 阵和广义表结构 求解问题1. 设计实现两个普通矩阵相乘的算法2. 实现用三元组表示法实现稀疏矩阵相加及转置算法3. 设计实现