《数据结构课程设计》课程设计方案

算法与数据结构课程设计方案Course Design of Data Structure适用专业：计算机科学与技术专业 本科课程代码：B08233004一、课程设计的性质和目的软件设计能力培养对学生是很重要。通过数据结构的学习，使学生对软件编程能力有一定的提高。数据结构学习是锻炼学生在进一步掌握模块化、结构化程序设计的方法的同时，培养学生运用已学知识分析问题、解决问题及编写实用程序的能力，通过对线性化、层次化、网络化数据结构的了解进一步掌握自然数据的结构方式及组织方式，让学生深入体会存储在计算机中的数据及程序，如何运用数据实现编程。课程设计是数据结构课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。主要目的如下：1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3、培养学生初步的软件设计及软件测试的能力。二、课程设计的基本要求学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况。1、设计和调试过程要规范化。(1)需求分析将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。(2)源程序（可以是一组源程序，即详细设计部分）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。2、实施方式可设1-3人一题，安排在数据结构课程开课学期布置题目，然后在期末一周时间内完成。三、课程设计进度安排课程设计大体分五个阶段:1、选题与搜集资料：每人选择相应题目,进行课程设计课题的资料搜集.2、分析与概要设计：根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计.3、程序设计用掌握C语言编写程：运序,实现所程序的各个模块功能.4、调试与测试程序,成：自行调试员交叉测试程序,并记录测试情况.5、实习报告：编写实习报告6、验收与评分：指导教师对每个小组的开发的系统,及每个成员开发的模块进行综合答辩验收.结合设计报告,根据课程设计成绩的评定方法,评出成绩.四、课程设计报告的书写设计结束后要写出课程设计报告,字数不少于6000，以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写（具体格式要求详见附录1和附录2）,打印并装订,排版及图,表要清楚,工整。装订顺序如下：封面、任务书、目录、正文。报告中除了在封面中应有题目、班级、姓名、学号和课程设计日期以外，其正文一般有如下几个方面的内容：正文包括以下7个内容:1、问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2、逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3、详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6、结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7、附录或参考资料：附录源程序及参考文献。五、课程设计的内容及安排根据教材数据结构课程设计（滕国文编著）选择课程设计题目，或选择下列与实际应用紧密结合的较综合性的题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。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).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。*存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、一元多项式计算*问题描述：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；3、订票系统*问题描述：通过此系统可以实现如下功能：1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）修改航班信息：当航班信息改变可以修改航班数据文件*要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；4、迷宫求解*问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；*要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；5、文章编辑*问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。*要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。*存储结构使用线性表，分别用几个子函数实现相应的功能；*输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。*输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；6、joseph环 *问题描述：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。*要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。*测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？*输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。*输出形式：建立一个输出函数，将正确的输出序列7、猴子选大王*问题描述：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。*输入数据：输入m,n m,n 为整数，nm*输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 8、建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以）*问题描述：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 9、赫夫曼树的建立*问题描述：建立建立最优二叉树函数*要求：可以建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存储结构、 基本算法（可以使用程序流程图） 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；10、纸牌游戏*问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过。输出：这时正面向上的牌有哪些？ 11、图的建立及输出*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 12、拓扑排序*问题描述：编写函数实现图的拓扑排序。13、各种排序*问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。*输入的数据形式为任何一个正整数，大小不限。*输出的形式：数字大小逐个递增的数列?14、图的遍历*问题描述：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。15、线性表的操作*问题描述：利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。16、长整数四则运算*问题描述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 *测试数据：（1）0；0；应输出“0”。（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；应输出“999（4）1,0001,0001；-1,0001,0001；应输出“0”。（5）1,0001,0001；-1,0001,0000；应输出“1”。（6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。*实现提示：（1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。17、马踏棋盘*问题描述：将马随机放在国际象棋的8* 8棋盘Bord88的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入个8* 8的方阵，输出之。*测试数据：由读者指定,可自行指定一个马的初始位置。*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。18、校园导游咨询*问题描述： （1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 （3）为来访客人提供图中任意景点相关信息的查询。*测试数据：由读者根据实际情况指定。*实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。19、编制一个求解迷宫通路的图形界面演示程序*问题描述：1） 输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上。2） 根据用户界面提示，用键盘输入。Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，Esc键退出。3）橙色的实心小圆圈表示起点，绿色实心圆圈表示终点，空心圆圈表示足迹，红色方块表示墙。4）本程序只求出一条成功的通路，但若对求解函数MazePath稍加更改即可求得全部路径。此外，因受图形界面限制，不能保存或载入测试文件（此功能可在Maze_text中实现）。5）当未输入起点时，消息显示“Error： You must set Startplace.”；未输入终点时，显示“Error： You must set Endplace.” 找到路径时，屏幕显示足迹，并在消息框出现Path found，否则消去足迹，显示Path not found.20一元稀疏多项式计算器*问题描述：一元多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。*实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点。21算术表达式求值演示*问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。*基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。*实现提示：（1）设置运算栈和运算数栈辅助分析算符优先关系。（2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。*选作内容：（1）扩充运算符集，如增加乘方、单目减、赋值等运算；（2）运算量可以是变量；（3）运算量可以是实数类型；（4）计数器的功能和仿镇界面。22稀疏矩阵运算器*问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本原酸的运算器。*基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。*实现提示：（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。23图书管理系统*问题描述：图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。*基本要求：（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等五4。（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述四项基本业务活动都是通过书号（即关键字）进行的，所以要用B树对书号尽力索引，以获得高效率。（3）系统应实现的操作及功能定义如下：采编入库：新购入一种书，经分类和确定书号后登记到图书帐目中去。如果这种书在帐目中已有，则只将总库存量增加。清除库存：某种书已无保留价值，将它从图书帐目中注销。某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。归还：注销对借阅者的登记，改变该书的现存量。显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。下列B树的打印格式如下所示：六、本课程与其它课程的联系与分工本课程是数据结构的配套课程，学完数据结构后进行的综合性课程设计。七、课程设计考核方法及成绩评定由指导教师根据学生完成任务的情况、课程设计说明书的质量和课程设计过程中的工作态度等综合打分。课程设计结束时，要求学生写出课程设计报告，可运行的软件系统（包括源程序）。课程设计成绩：上机情况（20%）包括出勤情况、调试表现。设计报告占40，设计作品占40。成绩评定实行优、良、中、及格和不及格五个等级。1、评定为优的是：出勤率良好、设计报告优秀、软件演示优秀、答辩三个问题全部正确。2、评定为良的是：出勤率良好、设计报告良好、软件演示良好、答辩三个问题全部良好。3、评定为中的是：出勤率合格、设计报告中等、软件演示中等、答辩三个问题基本正确。4、评定为及格的是：出勤率合格、设计报告及格、软件演示及格、答辩三个问题基本及格。5、评定为合格的是：出勤率不合格、或设计报告不及格、或软件演示不及格、或答辩三个问题不及格。优秀者人数一般不得超过总人数的30%。不及格者不能得到相应的学分，需重新做课程设计，经指导教师考核及格后，方可取得相应学分。有关的考查相关材料统一交系部资料室妥善保管。八、建议教材与教学参考书1数据结构课程设计滕国文 编著，清华大学出版社2数据结构严蔚敏 吴伟民 编著，清华大学出版社3数据结构题集严蔚敏 吴伟民 米宁 编著，清华大学出版社4c语言程序设计谭浩强 编著，清华大学出版社5数据结构（C语言篇）习题与解析李春葆 编著，清华大学出版社 10附录1：郑州科技学院算法与数据结构课程设计任务书专业 班级 学号 姓名 一、设计题目：二、基本要求三、设计任务四、设计时间 2010 年 月 日 至 2011 年 月 日指导教师： 教研室主任： 附录2：宋体二号加黑华文新魏小初号，简体郑州科技学院算法与数据结构课程设计 3号黑体，论文题目不得超过25个汉字题 目 _ _所填内容为黑体3号学生姓名 专业班级 学 号 所 在 系 指导教师 固定内容为宋体3号完成时间 年 月 日 目录目录3号黑体4号黑体1 1 1.11 1.1.12小4号宋体，目录只到三级编号，正文可以到四级编号4号宋体结束语60致谢61参考文献62（附录）63注：表示一个空格（两个字符位置） 括号内的内容表示视论文而定的内I课程设计论文题目（将自己的课程设计论文题目作为页眉）小5号宋体居中格3号黑体左顶格1一级节标题为1.1，1.2，1.3，小3号黑体1.1二级节标题为1.1.1，1.1.2，1.1.3，4号黑体1.1.1三级节标题为1.1.1.1，1.1.1.2，1.1.1.3，小4号黑体1.1.1.1注：如果下面还有编号，可依次用(1)，(2)，(3) 和，。正文中具体对某个问题进行说明，但并不属于全文的整体编号时，使用第一，第二，第三进行分点说明。文中参考文献的标注，企业集团的转移定价决策问题不仅为企业管理层所高度重视，同时也是学术界讨论的热门话题。Hirshleifer(1956) 1最先提出在确定性环境下当中间产品转移价格等于边际成本时，公司利润达到最大。Baldenius（1999）2在考虑特定关系投资的前提下，提出了两部转移定价法。正文部分：文字小4号，中文宋体；英文和数字Times New Roman图中英文文字为5号正体Times New Roman卖出看跌卖出看涨Long putl optionLong calll option 图2-5期权的基本交付模式图中中文文字为5号楷体图号按大标题加编，如图2-5表示第2章中的第5个图。图题在图下，小4号宋体正文开始标注页码，位置居中zhong 1公式：公式另起一行居中打印同行靠右注明公式序号，编号方法与图相同 (2-7)（如果有的话）表题在表上，小4号宋体，与图的编号方法相同表内文字5号，分别用宋体和Times New Roman表6-1中外基金的规模比较（1997年值，单位：亿美元）品种数基金总资产基金资产占流通市值的比率中国7516.910.38美国160004000049.5香港13008505 数据来源：1996年中国经济年鉴，1997年中国统计年鉴数据必须注明来源。表注小5号宋体和Times New Roman（正文部分字数不少于6000字）25致谢致谢3号黑体空1行。小4号宋体参考文献参考文献小3号黑体空1行1 Hirshleifer J. On the Economics of Transfer PricingJ. Journal of Business, 1956, 29(3): 172 - 184.2 Baldenius T, Reichelstein S, Sahay S A. Negotiated Versus Cost-Based Transfer PricingJ.Review of Accounting Studies,1999,4: 67-915号宋体和Times New Roman3 夏普WF, 亚历山大GJ，贝利JV. 赵锡军，龙永红，季冬生，等译. 投资学.北京：中国人民大学出版社，1996，124 约瑟夫 AA. 王微等译. 期权市场运作. 北京：清华大学出版社，1998，45 陈共，周生业，吴晓求. 证券投资分析. 北京：中国人民大学出版社，1998，86 林文俏. 股市风险透视与防范. 广州：广东经济出版社，1997，8网址标注到引用文章处7 门明. 论期权与风险投资管理. 对外经济贸易大学学报，1999，2：10158 秦海波. “太阳”为何与微软打“世界官司”. 经济日报，1999年5月27日9 唐晓强. 中国通信产业研究 注：（1）按论文中参考文献出现的先后顺序用阿拉伯数字连续编号，并与文中的编号顺序相对应。 小3号黑体（2）参考文献中每条项目应齐全。文献中的作者不超过三位时全部列出；超过三位时只列出前三位，后而加“等”字；作者姓名之间用逗号分开；中外人名一体采用姓在前，名在后的著录法。附录附录注：论文的附录依次为附录1，附录2，编号。附录中的图表公式另编排序号，与正文分开。