V 2.0
数据结构与算法
实验指导书
编写：陆绍飞
校核：______
湖南大学软件学院 2011年9月
湖南大学软件学院 数据结构与算法实验指导书 目录
目 录
实验教学大纲................................................. 1
一、课程所占的学时、学分及实验课所占学时、学分 ............................. 1 二、实验适用专业： ......................................................... 1 三、实验的任务、性质和目的 ................................................. 1 四、实验的基本理论 ......................................................... 1 五、实验方式与基本要求 ..................................................... 2 六、实验项目的设置与内容提要 ............................................... 2 七、考核方式与评分办法 ..................................................... 3
实验项目1——三元组ADT ....................................... 4 实验项目2——复数四则运算 .................................... 6 实验项目3——基本线性表运算 ................................... 8 实验项目4——基本线性表就地逆置 ...............................13 实验项目5——数制转换 ........................................15 实验项目6——回文判断 ........................................17 实验项目7——算术表达式求值演示 ...............................19 实验项目8——迷宫问题 ........................................22 实验项目9——树与二叉树 ......................................27 实验项目10——图遍历演示 .....................................30 实验项目11——二叉排序树 .....................................33 实验项目12——内部排序算法比较 ................................35 实验项目13——哈希表设计 .....................................36 实验项目14——约瑟夫环 .......................................37 实验项目15——停车场管理 .....................................38 实验项目16——旅游导游系统....................................39
第 i 页
湖南大学软件学院 数据结构与算法实验指导书 教学大纲
实验教学大纲
课程名称：数据结构与算法 课程编号：26547
本大纲主笔人：李睿 陆绍飞修改
一、课程所占的学时、学分及实验课所占学时、学分
总学时：80 总学分：4 实验课时：48 实验学分：1
二、实验适用专业：
软件工程、计算机专业、通信、信息类本科学生
三、实验的任务、性质和目的
数据结构与算法是一门技术性与实践性很强的课程，实验的设置十分重要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，通过要求完成对一些典型问题的分析及其实现的各环节，使学生掌握所用到的一些技术，扩充知识面。通过实验内容的训练，突出构造性思维训练的特征，提高学生组织数据与进行编写大型程序能力。
同时，上机实习是对学生的一种全面综合的训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。实习题中的问题比平时的习题复杂得多，也更接近实际。实习着眼于原理与应用的结合点，使学生学会把书上学到的知识解决实际问题，培养软件工程所需要的动手能力；另一方面，能使书本知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作,以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。
四、实验的基本理论
“数据结构与算法”是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并对进行性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础，数据结构与算法课程是计算机专业的一门核心的关键性课程。
为了使学生熟练掌握并运用所学知识，本实验安排了16个主实习单元，除实习1、2作为预备练习之外，其它各单元的训练重点在于基本的数据结构，而不强调面面俱到。各实
第 1 页 共 40页
湖南大学软件学院 数据结构与算法实验指导书 教学大纲
习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及几部分教学内容。
每个实习题采取统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等5个部分组成。
问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；
基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试数据部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
实现提示对实现中的难点及其解法思路等问题作了简要提示； 选做内容向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。
五、实验方式与基本要求
为了培养一个软件工作者所应具备的科学工作的方法和作风，实验过程要求按以下5个步骤进行：
1． 问题分析和任务定义； 2． 数据类型和系统设计； 3． 编码实现和静态检查； 4． 上机准备和上机调试；
5． 总结和整理实习报告。
六、实验项目的设置与内容提要
实验 每组 实验 实验 学时 人数 类型 要求 4 1 综合 必修 序号 1 实验项目 内 容 提 要 抽象数据类型（三元组ADT、复数四则运算） 实现创建一个三元组，实现其基本操作。设计实现抽象数据类型“复数”。 2 线性表（基本线性表运算、线性表的逆置） 4 1 实现基本线性表的创建、求基本线性表的长度、在基本线性表中查找某个数据元素、在某个位置插入一个新数据元素、在某个线性表中删除综合 必修 某个数据元素等操作。 3 栈、队列与递归算法设计（数制转换问题，回文判断） 4 1 分别以不同存储结构实现线性表的就地逆置 将十进制数N转换为其它d进制数； 判断依次读入的一个以@为结束符的字母序列，是否为形如?序列1 & 序列2?模设计 必修 式的字符序列。其中序列1和序列2 中都不含字符?&?，且序列2 是序列1的逆序列 设计 选修 设计 选修 4 5 算术表达式求值演示 迷宫问题 4 8 1 2 演示用算符优先法对算术表达式求值过程。 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程第 2 页 共 40页
湖南大学软件学院 数据结构与算法实验指导书 教学大纲
序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 二叉树的建立与遍历、图遍历的6 演示 二叉排序树查找 8 2 综合 必修 7 4 2 综合 选修 内部排序算法比较、哈希表设计 8 8 3 综合 必修 9 10 约瑟夫环 停车场管理 旅游导游问题 4 8 1 1 设计 选修 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历 从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受； 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 设计一个程序求出按约瑟夫规则的出列顺序。 设计 选修 为停车场编制按要求进行管理的模拟程序 11 8 2 假设一个旅游景区由n个不同景点组成（有向网），并用带权邻接矩阵表示，权值表示设计 选修 两个景点之间的步行时间，编写程序求任意两个景点之间的最短步行时间。。 七、考核方式与评分办法
以实验报告及程序完成情况计算成绩，实验成绩占总成绩的20%。
第 3 页 共 40页
