湘潭大学计算机专业数据结构课程实验内容与要求.pdf

数据结构课程实验内容与要求 序号 实验项目 项目任务 实验要求 实 验 学 时 实验题目 1 顺序表的操作 1．掌握顺序表类的声明和 实现的方法，能设计一些简 单的测例 2．学习在数据结构中自动 调 整 存 储 空 间 的 函 数 （ReSize）设计方法 3． 熟悉 C++的编程规范， 养 成良好的编程风格 写出实验报告(包括 项目、简单数据存储 结构描述及实现、数 据的插入与删除操 作) 2 1、P96，2.1 停 车场管理； 2 、 P104 ， 2.9 迷宫问题； 3、字符匹配查 找 （给定一个模 式串， 在主串中 查找与模式串 匹配的所有结 果， 输出匹配的 位置） 4 、 P136 ， 4.1 稀疏矩阵运算 器； 5、 P79， 1.1 运 动会分数统计； 6 、 P149 ， 5.2 哈夫曼编/译码 器； 7 、 P152 ， 5.7 表达式类型的 实现； 8 、 P166 ， 6.2 哈希表设计； 9、P6.4，平衡 二叉树操作的 演示； 10、P121，3.5 程序分析 2 单向链表的实现 1. 理解以复合类方式定 义单链表类（带头节点，类 名为 LinkList）的方法。

2. 掌握单链表类的声明 和主要操作：构造、插入， 删除、查找； 3. 熟悉 C++的编程规范， 养成良好的编程风格 写出实验报告(包括 项目、节点定义、链 表的插入删除) 2 3 栈的实现和应用 1． 理解栈的 LIFO 操作特点 2．掌握采用顺序存储结构 的栈类的声明和实现之方 法 3．了解栈类在括号检查方 面的应用 写出实验报告(包括 项目、栈的建立与实 现， 调用及参数保存、 返回和能力提高的体 会) 2 4 循环队列的实现和应 用 1． 理解掌握队列的 FIFO 的操作特点 2． 掌握采用顺序存储结 构的队列的声明和实 现方法 3． 掌握循环队列的存储 特征和应用 写出实验报告(包括 项目、队列的存储及 数据插入、删除和循 环应用和能力提高的 体会) 2 5 串操作 1． 串的存储实现 2． 串的匹配与查找 写出实验报告(包括 项目、串的存储、串 的匹配与查找实现和 能力提高的体会) 2 6 二叉树的实现 1.理解二叉链表构造二叉树 类的方法 2.理解二叉链表存储结构 下，前序、中序、后序、层 序遍历二叉树的算法 写出实验报告(包括 项目、二叉树与二叉 链表的存储与操作、 二叉树的遍历和能力 提高的体会) 2 3.掌握采用递归解决二叉树 相关算法的方法。

7 图的实现 熟悉图的两种常用的存储 结构，以及在这两种存储结 构上的两种遍历图的方法， 即深度优先遍历和广度优 先遍历进一步掌握递归算 法的设计方法 写出实验报告(包括 项目、图的存储、图 的搜索和能力提高的 体会) 2 8 查找和排序 1． 最基本的查找方法的 实现 2． 常见排序的实现 写出实验报告(包括 项目、查找匹配的实 现、关键字的数据排 序和能力提高的体 会) 2 时间：时间：9-16 周周四四 56 节节 地点：工科楼北楼六楼计算机大机房地点：工科楼北楼六楼计算机大机房 选做四个实习题（同一章只能选一题选做四个实习题（同一章只能选一题，难度系数高的题有加分，难度系数高的题有加分）） 《数据结构》课程设计题目及要求《数据结构》课程设计题目及要求 一、数据结构课程设计要求 1.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求有问题及 时主动通过各种方式与教师联系沟通 2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程 中不断检测自己的计划完成情况，及时向教师汇报 3.课程设计按照教学要求需要两周时间完成， 两周中每天至少要上 2 小时的上机来调试 C 或 C++语言设计的程序。

学院安排上机时间学生不得缺席 4.实习报告：按习题教材要求执行 二、上交相关内容要求 上交的成果的内容必须由以下四个部分组成，缺一不可 1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文 件夹中） ； 2． 上交程序的说明文件：（保存在.txt 中） 在说明文档中应该写明上交程序所在的目录， 上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； 3．课程设计报告： （保存在 word 文档中，文件名要求按照“姓名-学号-课程设计报告题 目“起名，如文件名为“张三-001-二叉树动态演示“.doc）按照课程设计的具体要求建立的功 能模块，每个模块要求按照如下几个内容认真完成； 其中包括: a)需求分析： 在该部分中叙述，每个模块的功能要求 b)概要设计 在此说明每个部分的算法设计说明（可以是描述每一个算法的流程图） ，每个程序中使 用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义 c）详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能 模块采用不同的函数实现） 源程序要按照写程序的规则来编写要结构清晰，重点函数的重点变量，重点功能部分 要加上清晰的程序注释。

d)调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思 考（问题是哪些？问题如何解决？） ，算法的改进设想 e)总结： 总结可以包括:课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试 能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等 内容 三、数据结构课程设计题目：上面表格中的 10 题或下面的题目，要求各选 2 题 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)可以按学校编号查询学校某个项目的情况； 可以按项目编号查询取得前三或前五名的学校 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要 求。

存储结构： 学生自己根据系统功能要求自己设计， 但是要求运动会的相关数据要存储在 数据文件中数据文件的数据读写方法等相关内容在 c 语言程序设计的书上， 请自学解决） 请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用 1、全部合法数据；2、整体非法数据；3、局部非法数据进行程序测 试，以保证程序的稳定测试数据及测试结果请在上交的资料中写明； 2.飞机订票系统 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询： 可以查询某个航线的情况 （如， 输入航班号， 查询起降时间， 起飞抵达城市， 航班票价，票价折扣，确定航班是否满仓） ； 可以输入起飞抵达城市，查询飞机航班情况； 订票： （订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 3.文章编辑 功能：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过 80 个字符，共 N 行；要求（1）分别统计出其中 英文字母数和空格数及整篇文章总字数； （2）统计某一字符串在文章中出现的次数，并输出 该次数； （3）删除某一子串，并将后面的字符前移 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号 输出形式： （1）分行输出用户输入的各行字符； （2）分 4 行输出“全部字母数“、“数字 个数“、“空格个数“、“文章总字数“（3）输出删除某一字符串后的文章； 4.纸牌游戏 任务：编号为 1-52 张牌，正面向上，从第 2 张开始，以 2 为基数，是 2 的倍数的牌翻 一次，直到最后一张牌；然后，从第 3 张开始，以 3 为基数，是 3 的倍数的牌翻一次，直到 最后一张牌； 然后…从第 4 张开始， 以 4 为基数， 是 4 的倍数的牌翻一次， 直到最后一张牌； . 再依次 5 的倍数的牌翻一次，6 的，7 的直到以 52 为基数的翻过，输出：这时正面向上的牌 有哪些？ 5.宿舍管理查询软件 1)任务：为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求： A.采用交互工作方式 B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排 序等任选一种) 2)查询菜单:(用二分查找实现以下操作) A.按姓名查询 B.按学号查询 C.按房号查询 3)打印任一查询结果（可以连续操作） 6.地图着色问题 设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的 颜色总数最少。

7.校园导航问题 设计要求：设计你的学校的平面图，至少包括 10 个以上的场所，每两个场所间可以有不同 的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径） 1、基本要求： 1）设计校园平面图，在校园景点选 10 个左右景点以图中顶点表示校园内各景点，存放景 点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息 2）为来访客人提供图中任意景点相关信息的查询 3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径 2、实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网 顶点和边均含有相关信息 8.学校超市选址问题（带权有向图的中心点） 设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度 也不同请为超市选址，要求实现总体最优 9.教学计划编制问题 [问题描述] 大学的每个专业都要制定教学计划假设任何专业都有固定的学习年限，每学年含两学 期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在 开设时间的安排必须满足先修关系每门课程有哪些先修课程是确定的，可以有任意多门， 也可以没有。

每门课恰好占一个学期试在这样的前提下设计一个教学计划编制程序 [基本要求] （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占 3 位的字母数 字串)、学分和直接先修课的课程号 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀； 二是使课程尽可能地集中在前几个学期中 （3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的 文件中计划的表格格式自行设计 [测试数据] 学期总数：6；学分上限：10；该专业共开设 12 门课，课程号从 C01 到 C12，学分顺序为 2,3,4,3,2,3,4,4,7,5,2,3先修关系如下： 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1，C2 C4 汇编语言 C1 C5 语言的设计和分析 C3，C4 C6 计算机原理 C11 C7 编译原理 C5，C3 C8 操作系统 C3，C6 C9 。