数据结构课程设计课程设计教学大纲

第一篇：数据结构课程设计课程设计教学大纲

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

Course Design of Data Structure

课程代码：

适用专业：信息计算、信息安全 总学时数：1周编写年月：2004年7月

执 笔：刘科峰、李小英、高学军

课程性质：设计（论文）/必修 开课学期：5 总学分数：1 修订年月：2007年7月

一、课程设计的性质和目的

《数据结构课程设计》是本学院本科专业的集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合应用练习。其目的就是要达到理论与实际相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。

二、课程设计内容及学时分配

写出不少于3000字的课程设计说明书。说明书中除了在封面中应有题目、班级、姓名、学号和课程设计日期以外，其正文一般有如下几个方面的内容：

1.需求分析 2.概要设计 3.详细设计 4.调试分析 5.测试结果 6.附录或参考资料

三、课程设计教学基本要求

四、课程设计选题

根据教材《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，或选择下列与实际应用紧密结合的较综合性的题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。

1． 运动会分数统计系统； 2． 停车场管理系统； 3． 民航售票系统； 4． 有理数四则运算器； 5． 文本格式化器； 6． 哈夫曼编/译码器； 7． 教学计划编制； 8． 计算机辅助考核系统；

9． 学籍管理系统； 10． 图书管理系统。

五、本课程与其它课程的联系与分工

本课程是《数据结构》的配套课程，学完《数据结构》后进行的综合性课程设计。

六、成绩评定

由指导教师根据学生完成任务的情况、课程设计说明书的质量和课程设计过程中的工作态度等综合打分。课程设计结束时，要求学生写出课程设计报告，可运行的软件系统（包括源程序）。课程设计成绩：上机情况（20%）包括出勤情况、调试表现。设计报告占40％，设计作品占40％。

成绩评定实行优、良、中、及格和不及格五个等级。优秀者人数一般不得超过总人数的20%。不及格者不能得到相应的学分，需重新做课程设计，经指导教师考核及格后，方可取得相应学分。有关的考查相关材料（文字材料以及磁盘或光盘）统一妥善保管。

七、建议教材与教学参考书

[1] 《数据结构》，严蔚敏 吴伟民 编著，清华大学出版社

[2] 《数据结构题集》严蔚敏 吴伟民 米宁 编著，清华大学出版社

第二篇：《数据结构》课程设计教学大纲

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

适用专业：计算机科学与技术 课程周数：2周

一、大纲说明

本大纲根据计算机科学与技术专业人才培养方案制订。

（一）课程设计性质

课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。

（二）主要先修课程和后续课程 1.先修课程：《C语言程序设计》 2.后续课程：《计算机组成原理》、《操作系统》、《数据库系统原理》

二、课程设计目的及基本要求

《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。

三、课程设计内容及安排

1、矩阵的转置、加减和相乘

问题描述：采用十字链表存储的稀疏矩阵，完成矩阵转置、加减和相乘功能。要求：

1）采用函数形式完成转置、相加、相减和相乘； 2）有输入数据合法性检查； 3）矩阵的存储采用动态数组；

4）两个矩阵产生后要分别打印出来，完成相应处理后结果要打印出来； 5）每一个函数要有必要的注释，在课程设计论文中有流程图。

2、线索二叉树

问题描述：实现线索二叉树的生成、遍历、查找、插入和删除操作。要求：

1）各功能模块必须是单独的函数； 2）线索二叉树是动态生存的； 3）输入数据进行必要的合法性检查；

4）执行每一个功能后，按二叉树广义表的表达方式打印输出，检查结果是否正确； 5）每一个函数要有必要的注释，在课程设计论文中有流程图。

3、根据哈夫曼树的原理求n个自然数相加减后结果最小（中间结果、最后结果不能负）。

问题描述：实现线索二叉树的生成、遍历、查找、插入和删除操作。要求：

1）可以循环测试，可以选择退出程序；

2）打印这n个自然数进行加减的表达式（注意：中间结果不能为负）； 例如：输入1,2,3，最后打印出3-2-1=0 3）输入数据要进行合法性检查；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

4、普里姆算法求最小生成树

问题描述：用普里姆算法求有向网图或无向网图的最小生成树。要求：

1）先生成一个网图，该网图既能是无向网图，有能是有向网图； 2）要求分别采用邻接矩阵和链接表存储来完成； 3）最后打印输出最小生成树；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

5、克鲁斯卡尔算法求最小生成树

问题描述：用克鲁斯卡尔算法求有向网图或无向网图的最小生成树。要求：

1）先生成一个网图，该网图既能是无向网图，有能是有向网图； 2）要求分别采用邻接矩阵和链接表存储来完成； 3）最后打印输出最小生成树；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

6、狄杰斯特算法求最短路径

问题描述：采用狄杰斯特算法求一个顶点到其它顶点的最短路径。要求：

1）先生成一个带权的有向图，并打印输出； 2）用函数形式完成狄杰斯特算法；

3）打印输出最后的该顶点到其它顶点的路径，并打印最短路径。4）每一个函数要有必要的注释，在课程设计论文中有流程图。

7、佛洛依德算法求最短路径

问题描述：采用佛洛依德算法求每对顶点到其它顶点的最短路径。要求：

1）先生成一个带权的有向图，并打印输出； 2）用函数形式完成佛洛依德算法； 3）打印输出每对顶点的最短路径。

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

8、分块查找

问题描述：采用分块查找的方法查找指定的关键码。要求：

1）可以循环查找，可以选择退出；

2）分别采用顺序存储和链式存储完成分块查找，其中在顺序存储结果下，索引表的查找采用二分查找；

3）分别用函数完成索引表查找和块中查找；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

9、关键路径

问题描述：建立AOE图，确定其拓扑有序后求关键路径。要求：

1）建立一个AOE图，并输出结果确保创建成功；

2）判断AOE图是一个拓扑有序序列，如果不是拓扑有序则报错； 3）编写函数求AOE图的关键路径； 4）打印输出关键路径；

5）每一个函数要有必要的注释，在课程设计论文中有流程图。

10、二叉排序树

问题描述：完成二叉排序树的创建、查找、插入和删除操作。要求：

1）创建一颗二叉排序树，并打印输出；

2）分别编写函数完成二叉排序树的查找、插入和删除； 3）测试二叉排序树的查找、插入和删除，分别打印测试结果； 4）每一个函数要有必要的注释，在课程设计论文中有流程图。

11、B-树

问题描述：完成B-树的创建、查找、插入和删除。要求：

1）创建一颗B-树，并打印输出；

2）分别编写函数完成B-的查找、插入和删除；

3）测试B-树的查找、插入和删除，分别打印测试结果； 4）每一个函数要有必要的注释，在课程设计论文中有流程图。

12、哈希表查找

问题描述：定义一个哈希表和对哈希表进行插入、查找和删除、打印。要求：

1）定义一个哈希表，并打印输出结果； 2）分别编写函数完成查找、插入和删除； 3）测试查找、插入和删除，分别打印测试结果；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

四、指导方式

集体辅导与个别辅导相结合。

五、课程设计考核方法及成绩评定

1、程序清单：代码应具有详细注释，用来说明程序的功能、结构；

2、设计报告：报告中应包含上机时遇到的问题及解决办法，观察到的现象及其分析，对程序设计技巧的总结及分析等；程序的输出结果及对结果的分析；实验的心得体会，以及其它信息；

3、提交时，须向指导教师说明：程序的使用方法，调用方法、操作步骤等；要求输入信息的类型及格式；出错信息的含义及程序的适用范围等。

成绩评定：课程设计成绩分两部分，设计报告占40％，设计作品占60％。

六、课程设计教材及主要参考资料 教学参考书

[1]李素若.《数据结构》.北京：化学工业出版社，2009.参考资料：

[1] 朱蓉，《数据结构实验指导书》

[2]严蔚敏 吴伟民，.数据结构(C语言版)，1999，清华大学出版社； [3]严蔚敏 吴伟民，.数据结构题集(C语言版)，1999，清华大学出版社； [4]徐孝凯，数据结构课程实验，2002，清华大学出版社；

[5]孟佳娜 胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社；

七、其他 i=[1] t=[12] i=[2] t=[4] i=[3] t=[10] i=[4] t=[12] i=[5] t=[1] i=[6] t=[2] i=[7] t=[2] i=[8] t=[11] i=[9] t=[5] i=[10] t=[10] i=[11] t=[11] i=[12] t=[8] i=[13] t=[2] i=[14] t=[3] i=[15] t=[9] i=[16] t=[7] i=[17] t=[5] i=[18] t=[6] i=[19] t=[12] i=[20] t=[7] i=[21] t=[3] i=[22] t=[7] i=[23] t=[8] i=[24] t=[6] i=[25] t=[7] i=[26] t=[8] i=[27] t=[3] i=[28] t=[2] i=[29] t=[7] i=[30] t=[4] i=[31] t=[3] i=[32] t=[8] i=[33] t=[9] i=[34] t=[1] i=[35] t=[1] i=[36] t=[3] i=[37] t=[8] i=[38] t=[1] i=[39] t=[10] i=[40] t=[12] i=[41] t=[10] i=[42] t=[9] i=[43] t=[12] i=[44] t=[2] i=[45] t=[1] i=[46] t=[6] i=[47] t=[4] i=[48] t=[7] i=[49] t=[1]

第三篇：数据结构课程设计教学大纲

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

Data Structure Course Design

一、课程的性质、教学目的和要求

《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

二、设计要点

1．设计和调试过程要规范化。① 需求分析

将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。

对有些题目提出算法改进方案，比较不同算法的优缺点。

如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。

2．课程设计实习报告的书写格式

① 设计题目（任选其一）②运行环境（软、硬件环境）③算法设计的思想 ④算法的流程图 ⑤算法设计分析 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式

可设3-4人一题，安排在《数据结构》课程开课学期布置题目，然后在期末两周时间内完成。

三．设计要求

学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要两周时间完成，两周中每天至少要上3-4小时的机来调试C语言设计的成成，总共至少要上机调试程序30小时。为保证质量，需要每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。

四．设计题目

1、运动会分数统计

*问题描述：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+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 为整数，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、长整数四则运算

*问题描述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(2^151)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。*测试数据：

（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 5 进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。

（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结

点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。

17、马踏棋盘

*问题描述：将马随机放在国际象棋的8 8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部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树的打印格式如下所示：

50，52 70，72

8

第四篇：数据结构课程设计教学大纲

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

Data Structure Course Design

一、课程的性质、教学目的和要求

《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

二、设计要点

1．设计和调试过程要规范化。① 需求分析

将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。

对有些题目提出算法改进方案，比较不同算法的优缺点。

如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。

2．课程设计实习报告的书写格式

① 设计题目（任选其一）②运行环境（软、硬件环境）③算法设计的思想 ④算法的流程图 ⑤算法设计分析 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式

可设2-3人一题，安排在《数据结构》课程开课学期布置题目，然后在期末前两周完成。

三．设计要求

学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要1周时间完成，1周中每天至少要上6-8小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。为保证质量，需要每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。

四．设计题目

1、校园导游程序

[问题描述]

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

[基本要求]（1）查询各景点的相关信息；

（2）查询图中任意两个景点间的最短路径。

（3）查询图中任意两个景点间的所有路径。

（4）增加、删除、更新有关景点和道路的信息。

[选作内容]

（1）求多个景点的最佳（最短）游览路径。

（2）区分机动车道和人行道。

（3）实现导游图的仿真界面。

2、算术表达式求值

[问题描述]

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

[基本要求]

（1）从键盘读入一个合法的算术表达式，输出正确的结果。

（2）显示输入序列和栈的变化过程。

[选作内容]

扩充运算符集合。

引入变量操作数。

操作数类型扩充到实数。

3、文学研究助手

[问题描述]

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。[基本要求]

英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。[测试数据]

以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。[实现提示]

设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。

如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。[选作内容]

（1）模式匹配要基于KMP算法。

（2）整个统计过程中只对小说文字扫描一遍以提高效率。

（3）假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。

（4）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）

4.迷宫求解

[问题描述]

可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

[基本要求]

含有两个以上的迷宫图，由用户选择哪一张迷宫图； 实现深度优先、广度优先两种回溯法。

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、算法的时间复杂度、另外可以提出算法的改进方法；

[实现提示]

可以用一个二维数组存储迷宫图，值为1或者0分别表示通路和不通； 搜索路径可以参考树的深度优先和广度优先算法。

5.括号匹配的检验

[问题描述]

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即CC或[（[ ] [ ]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：

[([ ] [ ])]

8

当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，„„，依次类推。可见这个处理过程正好和栈的特点相吻合。

[基本要求]

设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中，若是右括号，则或者是和当前栈顶的括号相匹配，或者是不合法的情况，输出“此串括号匹配不合法”。在初始和结束时，栈应该是空的。

[测试数据]

输入 #（[ ]（））#，结果“匹配”

输入 #[（）]#，结果“此串括号匹配不合法”

#为起始和结束标志。

6.停车场管理

[问题描述]

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。[测试数据]

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。[基本要求]

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。[选作内容]

（1）两个栈共享空间，思考应开辟数组的空间是多少？

（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

7.简单行编辑程序

[问题描述]

文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。[基本要求]

实现以下4条基本编辑命令：

（1）行插入。格式：i<行号><回车><文本><回车>

将<文本>插入活区中第<行号>行之后

（2）行删除。格式：d<行号1>[□<行号2>]<回车>

删除活区中第<行号1>行（到第<行号2>行）。两种格式的例子是：“d10↙”和“d10□14↙”

（3）活区切换。格式：n<回车>

将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。

（4）活区显示。格式：p<回车>

逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1。

各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。[实现提示]

（1）设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态 8 链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。

（2）初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。

（3）在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。

（4）若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。

（5）可令前三条命令执行后自动调用活区显示。[选作内容]

（1）对于命令格式非法等一切错误作严格检查和适当处理。

（2）加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

8.图遍历的演示

[问题描述]

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。[基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。[实现提示]

设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,„,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

[选作内容]

（1）借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。

（2）以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树

（3）实现有向图的遍历操作。

9、赫夫曼树的建立

*问题描述：建立建立最优二叉树函数

*要求：可以建立函数输入二叉树，并输出其赫夫曼树

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

10、图的建立及输出

*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

11、各种排序

*问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。

*输入的数据形式为任何一个正整数，大小不限。*输出的形式：数字大小逐个递增的数列?

12、图的遍历

*问题描述：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。

13、线性表的操作

*问题描述：利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。

14、编制一个求解迷宫通路的图形界面演示程序。*问题描述：

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.15．一元稀疏多项式计算器

*问题描述：一元多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,„,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。*实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点。

16．算术表达式求值演示

*问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。

*基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

*实现提示：（1）设置运算栈和运算数栈辅助分析算符优先关系。（2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。

*选作内容：（1）扩充运算符集，如增加乘方、单目减、赋值等运算；（2）运算量可以是变量；（3）运算量可以是实数类型；（4）计数器的功能和仿镇界面。

17．稀疏矩阵运算器

*问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本原酸的运算器。

*基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。

*实现提示：（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。（3）在用三元组表示稀 疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。18．图书管理

*问题描述：图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。

*基本要求：（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等五4。（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述四项基本业务活动都是通过书号（即关键字）进行的，所以要用B树对书号尽力索引，以获得高效率。（3）系统应实现的操作及功能定义如下：①采编入库：新购入一种书，经分类和确定书号后登记到图书帐目中去。如果这种书在帐目中已有，则只将总库存量增加。②清除库存：某种书已无保留价值，将它从图书帐目中注销。③某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。④归还：注销对借阅者的登记，改变该书的现存量。⑤显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。下列B树的打印格式如下所示：

19、文章编辑

*问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。

*要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

*存储结构使用线性表，分别用几个子函数实现相应的功能；

*输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

*输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”（3）输出删除某一字符串后的文章；

50，52 70，72

20、回文判断

[问题描述]

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。[实现提示]

首先，序列1进栈，然后序列1出栈并与序列2比较。

21、建立二叉树，层序、先序遍历（用递归或非递归的方法都可以）*问题描述：

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；

五、参考书目

《数据结构 C语言》 严蔚敏 清华大学出版社 《c语言程序设计》 谭浩强 清华大学出版社 《数据结构》 高教出版社

《数据结构习题》 李春保 清华大学出版社 《数据结构习题》 严蔚敏 清华大学出版社 《c语言与数据结构》 王立柱 清华大学出版社

《数据结构（C语言篇）习题与解析》李春葆 清华大学出版社

计算机软件教研室 2004年1月7日

第五篇：《数据结构课程设计》教学大纲

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

课程名称： 课程编号： 适用专业： 总 学 分： 总 学 时： 其中实验学时 主 撰 人： 撰写日期：

一、目的与任务

《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

二、教学基本要求

1．设计和调试过程要规范化

需求分析：将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。

对有些题目提出算法改进方案，比较不同算法的优缺点。

如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。2．课程设计实习报告的书写格式

① 设计题目

数据结构 408104 计算机科学与技术 72 30 2012．6

436104 软件工程

审 核 人：

②运行环境（软、硬件环境）③算法设计的思想 ④算法的流程图 ⑤算法设计分析 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式

可设3-4人一题，安排在《数据结构》课程开课学期布置题目，然后在期末两周时间内完成。

4．答辩：课题的论述、测试及问题回答

三、课程设计内容

1、背包问题的求解：

假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。

提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。

由于回溯求解的规则规则是“后进先出”因此自然要用到栈。

2、订票系统（1）问题描述

通过此系统可以实现如下功能： 1）录入：

可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；

可以输入起飞抵达城市，查询飞机航班情况；

3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；

4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

5）修改航班信息：当航班信息改变可以修改航班数据文件（2）要求

根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；

3、迷宫求解（1）问题描述

可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；（2）要求

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

4、dijkstra算法求最短路径

问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）

1)首先输入图的结点数->num 2)依次输入图的各条边

3）程序所能达到的功能：输出用dijkstra算法求出的一条最短路径。

5、joseph环（1）问题描述

编号是1，2，„„,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。（2）要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。（3）测试数据：

m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

（4）输入数据：建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。

（5）输出形式：建立一个输出函数，将正确的输出序列

6、建立二叉树，层序、先序遍历（用递归或非递归的方法都可以）（1）问题描述：建立二叉树，并实行层序、先序遍历等算法

（2）要求：能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；

7、赫夫曼树的建立

（1）问题描述：建立建立最优二叉树函数

（2）要求：可以建立函数输入二叉树，并输出其赫夫曼树

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

8、图的建立及输出

（1）问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型）

（2）要求：能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

9、拓扑排序

（1）问题描述：编写函数实现图的拓扑排序。（2）要求：能够以一定的方式输入数据结点

10、各种排序

（1）问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。（2）要求：输入的数据形式为任何一个正整数，大小不限。

输出的形式：数字大小逐个递增的数列

11、图的遍历 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。

12、线性表的操作

利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。

13、长整数四则运算

*问题描述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(2^151)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。*测试数据：

（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）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结

点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。

14、克鲁斯尔算法求最小生成树

问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）

1)首先输入图的结点数->num 2)依次输入图的各条边

3)程序所能达到的功能：能够输出这个图的一棵最小生成树

15、算术表达式求值演示

（1）问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。（2）基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

16．稀疏矩阵运算器

*问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本原酸的运算器。

*基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。

*实现提示：（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。

四、时间安排

《数据结构课程设计》安排在第三学期进行，时间2周（17-18周）。

五、组织管理

1．由院、系指派经验丰富的专业教师担任指导教师。

2．课程设计实行指导教师负责制，由指导教师全面负责课程设计的指导与管理工作。

六、成绩考核与评定

学生课程设计结束后写出总结报告，对设计的内容和效果进行总结，按照学生在设计期间的表现，指导老师对每位学生写出评语和鉴定，系课程设计领导小组组织答辩，最后确定每位学生课程设计成绩，课程设计成绩分为优、良、中、及格和不及格五个等级。

课程设计成绩为平时表现30%、设计报告50%、答辩20%。评分标准：

① 优秀：目的明确，态度端正，模范遵守学校的各项纪律。工作认真，积极 主动，吃苦耐劳，能出色的完成设计任务。撰写了高质量的总结报告。答辩准确流利。

② 良好：目的明确，态度端正，能遵守学校的各项纪律，工作比较积极主动。能较好地完成设计任务，成绩较突出，表现良好；撰写了质量比较高的实习报告。答辩较准确流利。

③ 及格：目的明确，态度基本端正，能遵守学校纪律，在督促下能开展工作 并完成一定的设计任务，无大的违纪违规现象；撰写了实习报告。通过了答辩。

④ 不及格：实习态度端正，不能遵守实习单位的纪律，不服从领导，自由散漫，工作消极被动，不能完成实习任务，实习期间有失职、旷工、打架、酗酒等大的过失。或无实习报告，没有通过答辩。

2．成绩评定

依据上述考核内容，最后采用优（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五级记分制评定学生课程设计成绩。

七、主要参考资料

《数据结构 C语言》 严蔚敏 清华大学出版社 2006.2 《c语言程序设计》 谭浩强 清华大学出版社 2010.8 《数据结构习题》 李春保 清华大学出版社 2006.4 《数据结构习题》 严蔚敏 清华大学出版社 2006.2 《c语言与数据结构》 王立柱 清华大学出版社 2010.6 《数据结构（C语言篇）习题与解析》李春葆 清华大学出版社2006.4