《数据结构课程设计》教学大纲.doc

《《数据结构课程设计》教学大纲.doc》由会员分享，可在线阅读，更多相关《《数据结构课程设计》教学大纲.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计教学大纲课程编号：32.课程名称：数据结构课程设计英文名称：Data Structure Course Design设计周数： 2 学分：2开设学期： 第3学期适用专业： 计算机科学与技术先修课程： 算法与数据结构一、目的和意义数据结构是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好数据结构，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。二、选题要求从给定题目中任选一个题目按要求完成，每个题目最多5到6个人选择

2、，也可以自己设计题目经指导教师审核同过即可，必须每人完成1个题目。三、任务及要求1、 运动会分数统计*问题描述：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）*功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名

3、的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。*存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、 一元多项式计算*问题描述：能够按

4、照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；3、 订票系统*问题描述：通过此系统可以实现如下功能：1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航

5、班已经无票，可以提供相关可选择航班；4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）修改航班信息：当航班信息改变可以修改航班数据文件*要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；4、 迷宫求解*问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；*要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；5、 文章编辑*问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态

6、存储一页文章，每行最多不超过80个字符，共N行。*要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。*存储结构使用线性表，分别用几个子函数实现相应的功能；*输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。*输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；6、 joseph环 *问题描述：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正

7、整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。*要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。*测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？*输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。*输出形式：建立一个输出函数，将正确的输出序列7、 猴子选大王*问题描述：一堆猴子都有编号，编

8、号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。*输入数据：输入m,n m,n 为整数，nm*输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 8、 建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以）*问题描述：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 9、 赫夫曼树的建立 *问题描述：建立建立最优二叉树

9、函数*要求：可以建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存储结构、 基本算法（可以使用程序流程图） 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；10、 纸牌游戏*问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过。输出：这时正面向上的牌有哪些？ 11、图的建立及输出*问题描述：建立图的

10、存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 12、拓扑排序*问题描述：编写函数实现图的拓扑排序。13、 各种排序*问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。*输入的数据形式为任何一个正整数，大小不限。*输出的形式：数字大小逐个递增的数列?14、图的遍历*问题描述：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、

11、取队头元素、判队空）实现图的广度优先搜索周游。15、线性表的操作*问题描述：利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果四、进程安排序号内 容时间1题目说明、任务布置、资料准备，完成实习报告“功能说明”部分资料准备，进行程序概要设计，确定程序总体结构，完成实习报告“程序框架设计”部分资料准备，进行程序概要设计，确定程序总体结构，完成实习报告“程序框架设计”部分第1次课2资料准备，进行程序概要设计，确定程序总体结构，完成实习报告“程序框架设计”部分第2次课3进行程

12、序详细设计，确定程序模块、程序流程完成实习报告“程序模块”定义部分第3次课4编写代码，实现题目要求功能第4次课5编写代码，实现题目要求功能，完成实习报告“程序模块实现”部分第5次课6程序测试，完成实习报告的全部内容第6次课7检查程序、上交实习报告第7次课五、考核方法及成绩评定考核方法：考查成绩评定：采用100分制计分，可以折算为优、良、中、及格和不及格，优：90100；良：8089；中：7079；及格：6069；不及格：059。成绩组成: 平时出勤与课堂考核占30，系统设计与功能实现占40%，最终课程设计报告占30。考核标准：1. 程序由本人独立编写，实现题目规定的全部基本功能。2. 实习报告

13、由本人独立完成，内容充实、合理，格式符合附录规定。3. 代码风格严谨规范。4. 完成题目中规定的提高部分。六、课程设计报告内容与要求设计题目（任选其一）1. 运行环境（软、硬件环境）2. 算法设计的思想3. 算法的流程图4. 算法设计分析5. 源代码6. 运行结果分析7. 收获及体会七、教材及主要参考资料1. 数据结构 C语言 严蔚敏 清华大学出版社2. c语言程序设计 谭浩强 清华大学出版社3. 数据结构 高教出版社 4. 数据结构习题 李春保 清华大学出版社5. 数据结构习题 严蔚敏 清华大学出版社6. c语言与数据结构 王立柱 清华大学出版社7. 数据结构（C语言篇）习题与解析李春葆 清华大学出版社八、其它说明无大纲制订人：郭祥峰 大纲审定人： 制订日期： 2009 年 12 月 25 日