1、数据结构课程设计课程教学大纲一、课程基本信息二、课程性质和任务数据结构课程设计课程是计算机科学与技术专业必修的一门专业课程。学生在学习本课程之前应当具有高级程序设计、C语言程序设计、数据结构方面的知识。本课程设计安排了二类课程设计项目：第一类课程设计项目为8个基本项目，包括：1、单链表实验，2、算术表达式括号匹配实验，3、二叉树的遍历实验，4、最小生成树实验，5、拓扑排序实验，6、顺序查找实验，7、折半查找实验，8、哈希查找实验。第二类课程设计项目为提高项目，包括：1、文章编辑，2、校园导航问题，3、简单的职工管理系统，4、运动会分数统计。在这两类课程设计项目中，各选择一个项目（课程设计至少需
2、做两个项目，可以只选2个第二类项目，但不可以只选2个第一类项目）。根据所选择的课程设计项目的问题描述和要求，编写出C/C+源程序，实现要求中的功能；并按照数据结构课程设计实验报告格式要求，撰写出课程设计实验报告。三、课程内容及要求第一类课程设计项目：1、单链表实验、问题描述给出初始数据，实现单链表功能、基本要求实现链表结点的创建功能实现单链表的创建功能实现单链表的插入功能实现单链表的删除功能实验单链表某个数据的查找（成功或不成功，成功时位置）界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求2、算术表达式括号匹配实验、问题描述假设一个算术表达式中包括圆括号、方括号和花
3、括号三种形式的括号，判别表达式中括号是否正确配对。、基本要求对于输入的表达式，输出以下四种结果之一：左右括号匹配正确左右括号配对次序不正确；右括号多于左括号左括号多于右括号界面要求：有合理提示3、 二叉树的遍历实验、问题描述给定一颗二叉树的逻辑结构，建立二叉树，并输出先序、中序、后序遍历序列、基本要求输出二叉树的先序遍历序列输出二叉树的中序遍历序列输出二叉树的后序遍历序列4： 最小生成树实验、问题描述给定一个图，求最小生成树。、基本要求以邻接矩阵作为输入，建立图的物理表示采用普里姆、克努斯卡尔或其算法，实现最小生成树输出时，从最小的边开始，以三元组（顶点、顶点、边长）的形式输出最小生成树5、拓
4、扑排序实验、问题描述给定一个有向图，生成一个拓扑排序序列。、基本要求以三元组（弧尾顶点、弧头顶点、弧长）作为输入，建立图的物理表示输出拓扑排序序列6、顺序查找实验、问题描述在一个关键字序列（未排序）中，顺序查找一个关键字、基本要求用顺序表作为数据结构输入一串关键字，生成顺序表在顺序表中查找关键字，返回查找是否成功，如果成功，输出关键字所在的位置。7、折半查找实验、问题描述在一个有序序列中，折半查找一个关键字、基本要求用顺序表作为数据结构输入一串关键字，生成一个有序（可以采用任何排序方法）顺序表在顺序表中采用折半算法查找关键字，返回查找是否成功，如果成功，输出关键字所在的位置。8、哈希查找实验、
5、问题描述采用散列表方式，对关键字进行查找。、基本要求根据输入的关键字序列，建立哈希表；哈希函数由同学们自选，用拉链法解决冲突。查找是否成功（1表示成功，0表示不成功），所在位置，查找次数。第二类课程设计项目1、文章编辑、问题描述输入一页文字，每行最多不超过80个字符，共N行；程序可以统计出文字、数字、空格的个数，并能做插入、删除等操作。、基本要求分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串或一行（提供行号），并将后面的字符/行前移；插入一行，插入的位置应可以在恰当的提示下进行（如提供其行号）；（每次删除或插入操作后）分行显示输入
6、的各行字符；输入的文本必须能存盘；可以从磁盘读出已存文件内容；界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求2、校园导航问题、问题描述设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。、 基本要求设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。界面要求：有合理提示；每个功
7、能可以设立菜单；根据提示，可以完成相关的功能要求3、简单的职工管理系统、问题描述对单位的职工进行管理，包括插入、删除、查找、排序等功能。、基本要求职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。新增一名职工：将新增职工对象按姓名以字典方式职工管理文件（实现时，也可以直接放在内存）中删除一名职工：从职工管理文件中删除一名职工对象。查询：从职工管理文件中查询符合某些条件的职工。修改：检索某个职工对象，对其某些属性进行修改。排序：按需要（出生年月、工作年月）对职工对象文件进行排序。界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求4、运动会分数统计
8、、问题描述参加运动会有n个学校，学校编号为1，2，n比赛分成m个男子项目和w个女子项目；项目编号男子为1，2，m；女子为m+1，m+2，m+w不同项目取前五名或前三名积分；取前五名的积分分别是：7，5，3，2，1；取前三名积分分别为：5，3，2；哪些取前三名或前三名，由同学自己设定；n=20，m+w=20、基本要求可以输入各个项目的前三名或前五名的成绩（可以将数据放在文件（如cin.txt）中（采用freopen(cin.txt, r, stdin);从cin.txt文件中输入），也可以直接放在数组中）能统计各学校总分可以按学校编号、学校总分、男女团体总分排序输出可以按学校编号查询学校某个项目
9、的情况可以按项目编号查询取得前三或前五名的学校界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求四、学时分配建议总 学 时：32讲授学时：0实验学时：32序号教 学 内 容授课实验实践1第一类课程设计项目0122第二类课程设计项目020合计032五、实验内容及安排数据结构课程设计是完全实验性的课程，要求其所有内容，在学生自已的安排下，按课程要求和内容，在规定时间内完成。序号实验名称内容提要学时每组人数类型开出要求1第一类课程设计项目1、单链表实验，2、算术表达式括号匹配实验，3、二叉树的遍历实验，4、最小生成树实验，5、拓扑排序实验，6、顺序查找实验，7、折半查找实验
10、，8、哈希查找实验121验证必做2第二类课程设计项目1、文章编辑，2、校园导航问题，3、简单的职工管理系统，4、运动会分数统计201验证必做合计32六、成绩考核方法本课程的考核分为二个部分，第一类课程设计项目（1、单链表实验，2、算术表达式括号匹配实验，3、二叉树的遍历实验，4、最小生成树实验，5、拓扑排序实验，6、顺序查找实验，7、折半查找实验，8、哈希查找实验），第二类课程设计项目（1、文章编辑，2、校园导航问题，3、简单的职工管理系统，4、运动会分数统计），皆以现场演示、回答问题和提交实验报告方式完成。总成绩按以下公式计算：总成绩 第一类课程设计项目 50%第二类课程设计项目 50%七、教材及主要参考书1.参考书：数据结构课程设计，滕国文编著，清华大学出版社，2010年9月6 / 6
