课程名称：空间数据结构实验
英文名：Data Structure
对应理论课程编号：162220
课程总学时：38学时
实验总学时：38学时
实验周学时：2学时
开设实验项目数：1
课程总学分：2学分
课程性质：选修
面对院系、专业、年级：地理与海洋科学学院、地理信息科学系、二年级
课程主持人（主讲教师）：谢顺平
本大纲主撰人：谢顺平
一、实验教学目标与基本要求：
数据结构实验教学以深化理解和灵活掌握课堂教学内容、提高分析与解决实际问题的水平、培养熟练掌握和运用流行软件平台Visual C++实现各种数据结构算法的能力为主要目标。本实验课以数据结构课堂教学内容为主线，与各章内容相对应安排14个基本实习单元，每个实习单元根据难度安排相应的实习时间，学生必须在规定时间内认真完成每项实习。实习题全部采用统一格式，有问题描述、基本要求、测试数据、实验提示四部分组成。学生在上机完成每项实习后，应提交实习报告，实习报告由问题分析；详细设计；编程调试，结果分析等五部分组成。
二、课程（实验）内容与学时分配：
|
序号
|
实验项目名称
|
内 容 提 要
|
学时
|
专业
年级
|
类 型
|
|
综
合
|
设
计
|
验证
|
|
一
|
必修实验：
|
|
|
|
|
|
|
|
1
|
线性表及其应用
|
用尾插法建立带表头结点的单向线性链表，
输出该链表的数据，仅对单向线性链表进行处理，在不建立新链表的前提下，使原链表中的数据结点逆序，输出处理后的链表数据。
|
2
|
二
|
|
√
|
|
|
2
|
基于链表的一元稀疏多项式计算器的设计
|
设计一元稀疏多项式计算器程序，基本功能包括：输入并建立多项式；输出多项式；多项式A和多项式B相加；多项式A和多项式B相减。
|
4
|
二
|
|
√
|
|
|
3
|
栈及其应用
|
利用堆栈技术实现将中缀算术表达式转为后缀表达式，并利用栈和后缀表达式计算表达式的值。
|
2
|
二
|
|
√
|
|
|
4
|
链队及其应用
|
用链式队列操作实现将一幅图像按四叉剖分原则分割成单调子块集合，生成四元组(子块左下角坐标,尺寸、单调值)单调子块记录队列，并将其恢复成图像。
|
2
|
二
|
|
√
|
|
|
5
|
稀疏矩阵的三元组实现及其运算操作
|
用三元组存放输入的两个稀疏矩阵A34和B34，将稀疏矩阵A转置后与稀疏矩阵B相乘，结果存放三元组C，并输出结果。
|
2
|
二
|
|
√
|
|
|
6
|
稀疏矩阵的十字链表实现及其运算操作
|
输入并建立两个稀疏矩阵A和B的十字链表，完成两稀疏矩阵的加法运算A=A+B, 要求相加结果为0的元素从结果稀疏矩阵的十字链表中删除, 输出A稀疏矩阵。
|
2
|
二
|
|
√
|
|
|
7
|
由先根遍历序列和中根遍历序列还原构造二叉树
|
设计一个算法，根据一棵二叉树结点的先根遍历序列和中根遍历序列构造该二叉树，并输出该二叉树的先序、中序和后序遍历结果。（树采用链接结构，任意两个结点data域的值均不相同）
|
2
|
二
|
|
√
|
|
|
8
|
二叉树中序线索化及其插入结点处理
|
按先序序列输入并建立二叉树，输出中序遍历结果，中序线索化二叉树，在指定结点的父结点后插入一个结点，用非递归算法输出插入结点后该线索二叉树中序遍历结果。
|
2
|
二
|
|
√
|
|
|
9
|
构建报文字符的哈夫曼树和哈夫曼编码并进行报文压缩
|
根据一组字符在报文中的出现频率，生成对应的哈夫曼树(孩子结点权值按左小右大原则构造)，用构造的的哈夫曼编码压缩报文后还原，并求出平均编码长度和压缩比。
|
4
|
二
|
|
√
|
|
|
10
|
图的广度优先搜索和深度优先搜索
|
按顺序输入无向图的顶点对集合，试编算法按头插法建立相应的邻接表，并基于该邻接表，输出从顶点v1开始搜索得到的DFS和BFS序列。
|
2
|
二
|
|
√
|
|
|
11
|
构建连通图的最小生成树
|
对城际交通带权无向图，建立相应的邻接矩阵，分别用Prime算法和Kruskal算法生成从城市C1出发的最小生成树, 并按生成树的顺序输出其中各边的顶点对。
|
3
|
二
|
|
√
|
|
|
12
|
计算最短路径长度
|
对城市交通带权有向图，建立相应的邻接矩阵，用Dijkstra算法求从源点vi到其余各点的最短路径长度，用Floyd算法求每对顶点间的最短路径长度，并输出这些最短路径。
|
3
|
二
|
|
√
|
|
|
13
|
排序算法效率比较
|
分别用直接插入排序、希尔排序、快速排序、堆排序、归并排序、基数排序对随机产生的5组(每组50万个)实数进行增序排序，并验证排序结果，统计各算法运算时间，比较效率。
|
3
|
二
|
|
√
|
|
|
14
|
哈希表的构建与查找
|
针对某个集体(如本班级)中的人名设计一个哈希表，使得对其平均查找长度不超过R，表中每个记录存放一人的学号、人名、性别等，完成相应的建表和查表程序。
|
3
|
二
|
|
√
|
|
|
二
|
选修实验：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
三、实验教学方式与考核要求：
数据结构实验题目在课堂上布置和讲解，所有实习均在微机实验室上机进行，授课教师负责上机实验指导和答疑。实习要求全部采用Visual C++软件环境编程，需要图形界面的可以使用其MFC开发环境及文档/视图结构。参加实习的学生必须按照实习要求认真准备、分析、设计、编程和调试，并完成相应的文档。学生在上机考核前应准备好实习报告，待实习考核通过后提交。根据学生完成实习的总体情况，给出考核成绩，考核成绩分优、良、合格和不合格4档，学期期末考试结束后实习成绩按一定比例计入课程总成绩。
四、主要使用仪器设备：
|
序号
|
实验项目名称
|
使用仪器设备名称
|
性能要求
|
台套数
|
|
|
空间数据结构实验
|
台式计算机
|
P586/3.1GHz/4GB/300GB
|
30台
|
五、实验教材、参考资料：
（一）实验教材：数据结构题集，严蔚敏、吴伟民、米宁编著，清华大学出版社
（二）参考资料：
数据结构(C语言描述)，严蔚敏、吴伟民编著，清华大学出版社
数据结构(用面向对象方法与C++语言描述)，殷人昆编著，清华大学出版社
C++语言程序设计(第3版)，郑莉、董渊、张瑞丰编著，清华大学出版社