《数据结构》实验教案 .pdf

《《数据结构》实验教案 .pdf》由会员分享，可在线阅读，更多相关《《数据结构》实验教案 .pdf（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、重庆邮电大学教学实施方案（20122013 学年 秋季 学期）课程名 称：数据结构实验授课对 象：2011 级全校各专业课程性 质：必修课课程学 时：10 学时授课教 师：刘伯红（硕士/副教授）所属部 门：计算机学院计算机专业实验中心2012 年 10 月 12 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红2 目 录重庆邮电大学教师实验授课计划.4 数据结构 C语言程序书写规范.7 一、程序书写规范要求 .7 二、C语言程序示例 .7 三、实验步骤.10 实验一教案线性表的实现及操作.12 一、实验目的.12

2、 二、实验要求.12 三、实验重点与难点 .13 四、实验内容.13 五、参考资料.14 六、实验小结.14 七、课后作业.14 实验二教案栈与队列的应用.16 一、实验目的.16 二、实验要求.16 三、实验重点与难点 .17 四、实验内容.17 五、参考资料.20 六、实验小结.20 七、课后作业.20 实验三教案二叉树的实现及遍历.21 一、实验目的.21 二、实验要求.21 三、实验重点与难点 .21 四、实验内容.22 五、参考资料.24 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红3 六、实验小结.

3、24 七、课后作业.24 实验四教案图的实现与遍历.25 一、实验目的.25 二、实验要求.25 三、实验重点与难点 .25 四、实验内容.26 五、参考资料.27 六、实验小结.27 七、课后作业.27 实验五教案查找算法的实现及比较 .28 一、实验目的.28 二、实验要求.28 三、实验重点与难点 .28 四、实验内容.29 五、参考资料.29 六、实验小结.29 七、课后作业.29 实验六教案综合实验 .30 一、实验目的.30 二、实验要求.30 三、实验重点与难点 .31 四、实验内容.31 1简易图书管理模拟系统.31 2.航空客运订票系统.33 3.校园导游咨询.35 五、参考

4、资料.36 六、实验小结.37 七、课后作业.37 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红4 重庆邮电大学教师实验授课计划填表人：刘伯红填表时间：2012 年 9 月 10 日学年学期：20121课程编号：040301 课程名称：数据结构实验年级：2011专业：全校各专业学时/学分：理论学时：实验学时：10 学时教材名称及出版社：数据结构 实验指导书（内部讲义）开课专业及班级：全校各专业：1191102、0410906、0360902班等序号周次授课内容摘要（包括授课内容、参考书、自学提纲、学习方法等）课

5、内时数重点、难点及其基本要求相关耗材1 6-7 线性表的实现及操作2 1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2.掌握线性表的顺序存储结构的定义及其C 语言的实现。3.掌握线性表的链式存储结构单链表的定义及其C语言的实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作算法及其 C 语言的实现。5.掌握线性表在链式存储结构单链表中的各种基本操作算法及其 C 语言的实现。2 8-9 栈与队列的应用2 1.了解栈和队列的特性。2.掌握栈的 顺序 表示和实现。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 37 页 -数据结构 实验教案计算机学院计算机专

6、业实验中心：刘伯红5 3.掌握栈的 链式 表示和实现。4.掌握队列的顺序（循环队列）表示和实现。5.掌握队列的链式表示和实现。掌握栈和队列在实际问题中的应用。3 10-11 二叉树的实现及遍历2 1.掌握二叉树的逻辑结构和存储结构特性2.掌握以二叉链表存储二叉树的各种基本操作的实现。3.理解树的孩子兄弟链表与二叉树二叉链表存储结构及操作。4 11-12 图的实现与遍历2 1.掌握图的基本存储方法。2.掌握有关图的操作算法并用高级语言实现。3.熟练掌握图的两种搜索路径的遍历方法。4.掌握图的有关应用。5 13-14 查找算法的实现及比较2 1.掌握几种典型的查找方法（顺序查找、折半查找、二叉排序

7、树的查找、哈希查找）。2.对各种算法的特点、使用名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红6 范围和效率有进一步的了解，并能使用高级语言实现查找算法。6 课下综合实验1 学期1.了解并掌握数据结构的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。主讲教师：刘伯红辅导教师：刘伯红授课人

8、数 132人教学部主任签名：方义秋二级学院院长签名：夏英名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红7 数据结构 C语言程序书写规范一、程序书写规范要求头文件包含命令符号常量的定义数据逻辑结构类型的定义各个子函数的定义（子函数完成各个功能）主函数的定义（完成数据的输入、调用子函数实现功能、输出结果）二、C语言程序示例实现顺序表操作的C 语言程序如下：/头文件包含命令#include stdio.h/符号常量的定义#define maxsize 1024/数据逻辑结构类型的定义typedef char datat

9、ype;typedef struct datatype datamaxsize;/存放数据元素的数组int last;/最后一个元素的下标（从0 开始）sequenlist;/各个子函数的定义（子函数完成各个功能）/在第 i（位置）个元素前插入元素x int insert(sequenlist*L,datatype x,int i)int j;if(L-last=maxsize-1)/如果线性表已满 printf(overflow);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红8 else i

10、f(iL-last+2)/插入位置不合理 printf(error,please input the right i);return 0;else for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;L-datai-1=x;L-last=L-last+1;return(1);/删除第 i（位置）个元素int dellist(sequenlist*L,int i)int k;if(iL-last+1)/检查删除位置是否合法 printf(error,please input the right i);return 0;else for(k=i;klast;k+)L-d

11、atak-1=L-datak;L-last=L-last-1;return(1);/建立顺序表，其元素为单个字符void creatlist(sequenlist*L)int n,i;char tmp;printf(请输入数据的个数:n);scanf(%d,&n);for(i=0;idatai=tmp;L-last=n-1;printf(n);/输出顺序表void printout(sequenlist*L)int i;for(i=0;ilast;i+)printf(data%d,i);printf(%cn,L-datai);/主函数的定义（完成数据的输入、调用子函数实现功能、输出结果及其他辅

12、助功能）main()sequenlist*L;char cmd,x;int i;L=(sequenlist*)malloc(sizeof(sequenlist);/指针初始化creatlist(L);printout(L);do printf(i,I.插入 n);printf(d,D.删除 n);printf(q,Q.退出 n);do fflush(stdin);/清除键盘缓冲区scanf(%c,&cmd);while(cmd!=d)&(cmd!=D)&(cmd!=D)&(cmd!=q)&(cmd!=Q)&(cmd!=i)&(cmd!=I);switch(cmd)case i:case I:名

13、师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红10 printf(请输入你要插入的数据:);fflush(stdin);scanf(%c,&x);printf(请输入你要插入的位置：);scanf(%d,&i);insert(L,x,i);printout(L);break;case d:case D:printf(请输入你要删除元素的位置：);fflush(stdin);scanf(%d,&i);dellist(L,i);printout(L);break;while(cmd!=q)&(cmd!=Q);三、实验步

14、骤1.问题分析和任务定义明确问题要求做什么，限制做什么。2.数据类型和系统设计分为逻辑设计和详细设计。逻辑设计指的是，为操作数据对象定义相应的数据类型，以数据结构为中心的原则划分模块，定义主模块和各个抽象数据类型。详细设计则为定义相应的存储结构并写出各函数的伪代码算法。3.编码实现即程序设计，是对详细设计结果的进一步求精，用某种高级语言表达出来。4.上机调试名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红11 调试最好分模块进行，自底向上，即先调试底层函数模块，必要时可以另写一个调用函数。5.书写实验报告。名师资

15、料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红12 实验一教案线性表的实现及操作第 1 次课教学周第 6-7 周机时安排2 学时实验名称实验一 线性表的实现及操作实验类型1.验证性 2.综合性 3.设计性 4.其它 实验一线性表的实现及操作一、实验目的1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2.掌握线性表的顺序存储结构的定义及其C 语言的实现。3.掌握线性表的链式存储结构 单链表的定义及其C 语言的实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作算法及其 C 语言的实现。5.掌握

16、线性表在链式存储结构 单链表中的各种基本操作算法及其 C 语言的实现。二、实验要求1.认真编写和掌握本实验的算法和程序。2.上机调试本程序。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红13 3.保存和上交程序，并结合程序分析其输出结构。4.认真书写实验报告。三、实验重点与难点实验重点：1数据结构C 语言程序编写规范。2线性表的逻辑结构和存储结构。3线性表的各种基本操作。实验难点：线性表的链式存储结构及其基本操作实现。四、实验内容1顺序表的操作实现请编写C 程序，利用顺序存储方式实现下列功能：根据键盘输入数据建

17、立一个顺序表，并输出该线性表；然后根据选择不同的操作，可以进行数据的插入、删除、查找和退出程序，并在插入和删除线性表后，再输出该线性表。2单链表的操作实现请编写C 程序，利用链式存储方式实现下列功能：根据键盘输入数据建立一个单链表，并输出该单链表；然后根据选择不同的操作，可以进行数据的插入、删除、查找和退出程序，并在插入和删除线性表后，再输出该线性表。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红14 3应用题：约瑟夫环（1）问题描述：约瑟夫问题的一种描述为，编号为1,2,3,n的 n 个人按顺时针方向围坐一圈

18、，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 的值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序求出出列顺序。（）基本操作：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。（）测试数据：m 的初值为20；n=7,7 个人的密码依次为：3,1,7,2,4,8,4,首先 m 值为 6（正确的出列顺序应为6,1,4,7,2,3,5）。（4）实现提示：程序运行后，首先要求用户指定初始报数上限值，然后读取各人

19、的密码。可设n30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。五、参考资料严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华大学出版社,2007.5。六、实验小结部分学生不熟悉教材程序伪码和实际程序的区别与转换，部分学生动手编程能力有待提高。七、课后作业名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红15 完成课堂上未完成的作业与程序编码，撰写实验报告，预习下节课的内容。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验

20、中心：刘伯红16 实验二教案栈与队列的应用第 2 次课教学周第 8-9 周机时安排2 学时实验名称实验二 栈与队列的应用实验类型1.验证性 2.综合性 3.设计性 4.其它 实验二 栈与队列的应用一、实验目的1.了解栈和队列的特性。2.掌握栈的顺序表示和实现。3.掌握栈的链式表示和实现。4.掌握队列的顺序（循环队列）表示和实现。5.掌握队列的链式表示和实现。6.掌握栈和队列在实际问题中的应用。二、实验要求1认真编写和掌握本实验的算法和程序。2上机调试本程序。3保存和上交程序，并结合程序分析其输出结构。4认真书写实验报告。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 37 页

21、-数据结构 实验教案计算机学院计算机专业实验中心：刘伯红17 三、实验重点与难点实验重点：1栈和队列的逻辑结构和存储结构。3栈和队列的各种基本操作及实现。实验难点：队列的链式表示和实现。栈和队列的应用。四、实验内容1.栈的顺序表示和实现请编写C 程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈。（2）插入元素。（3）删除栈顶元素。（4）取栈顶元素。（5）遍历顺序栈。（6）置空顺序栈。2.栈的链式表示和实现请编写C 程序，实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 3

22、7 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红18（1）初始化链栈。（2）入栈。（3）出栈。（4）取栈顶元素。（5）遍历链栈。（6）置空链栈。3.循环队列的表示和实现请编写C 程序，实现循环队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化循环队列。（2）入队。（3）出队。（4）取队头元素。（5）遍历队列。（6）置空队列。4.链队的表示和实现请编写C 程序，实现链队的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链队。（2）入队。（3）出队。（4）取队头元素。名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 37 页

23、 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红19（5）遍历队列。（6）置空队列。5应用题：迷宫问题（1）问题描述：以一个 m n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。（2）基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如：对 于 下 列 数 据 的 迷 宫，输 出 的 一 条 通 路 为：(1,1,1),(1,2,2),(2,2,2)

24、,(3,2,3),(3,1,2)。（3）测试数据：迷宫的测试数据如下：左下角(1,1)为入口，右下角(8,9)为出口。0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0（4）实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的

25、通路都探索到而未能到达出口，则所设定的迷宫名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红20 没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1,1)，出口点的下标为(n,n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。五、参考资料严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华大学出版社,2007.5。六、实验小结同学们基本能完成栈和队列的基本操作及实现。由于内容较多，课堂上时间不够，没完成的内容靠学生课下完成。七、课后作业完成课堂上

26、未完成的作业与程序编码，撰写实验报告，预习下节课的内容。名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红21 实验三教案二叉树的实现及遍历第 3 次课教学周第 10-11周机时安排2 学时实验名称实验三 二叉树的实现及遍历实验类型1.验证性 2.综合性 3.设计性 4.其它 实验三 二叉树的实现及遍历一、实验目的1.掌握二叉树的逻辑结构和存储结构特性2.掌握以二叉链表存储二叉树的各种基本操作的实现。3.理解树的孩子兄弟链表与二叉树二叉链表存储结构及操作。二、实验要求1认真编写和掌握本实验的算法和程序。2上机调试本

27、程序。3保存和上交程序，并结合程序分析其输出结构。4认真书写实验报告。三、实验重点与难点实验重点：1二叉树的逻辑结构和存储结构。名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红22 3二叉树的各种基本操作及实现。实验难点：二叉树的遍历操作。四、实验内容1请编制 C 程序，实现如下操作：（1）输入字符序列，建立二叉链表结构的二叉树。（2）按先序、中序和后序遍历二叉树（递归算法）。（3）按树状打印整棵二叉树。（4）求二叉树的高度。（5）求二叉树的所有结点、叶子结点个数。（6）交换二叉树的左右子树。（7）队列实现二叉树

28、的层次遍历。（8）索化二叉树，并实现在中序线索二叉树中查找前驱和后继结点元素。（9）数中设计一个简单的类似菜单的函数调用，分别实现上述算法功能。2应用题：哈夫曼编码（1）问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红23 一个完整的编译码系统。试为这样的信息收发站写一个哈夫曼码的编

29、译码系统。（2）基本要求：一个完整的系统应具有以下功能：a.：初始化（Initialization）。从终端读入字符集大小n,以及 n个字符和 n 个权值，建立哈夫曼树，并将它存于文件hfmTree 中。b.：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件CodeFile 中。c.：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile 中。d.：印代码文件（Print）。将文件CodeFile 以紧凑格式显示在终端上，每行

30、50 个代码。同时将此字符形式的编码文件写入文件CodePrin 中。e.：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中。()测试数据：见上机指导书测试数据。()实现提示：a.文件 CodeFile 的基类型可以设为子界型bit=01。b.用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中

31、心：刘伯红24 完毕后再显示此菜单，直至某次用户选择了“”为止。c.在程序的一次执行过程中，第一次执行I,D 或命令之后，哈夫曼树已经在内存了，不必读入。每次执行中不一定执行命令，因为文件 hfmTree 可能早已建好。五、参考资料严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华大学出版社,2007.5。六、实验小结同学们基本能完成二叉树基本操作及实现。由于内容较多，课堂上时间不够，应用题（选作）靠学生课下时间完成。七、课后作业完成课堂上未完成的作业与程序编码，撰写实验报告，预习下节课的内容。名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 37 页 -数据结构 实验教案计

32、算机学院计算机专业实验中心：刘伯红25 实验四教案图的实现与遍历第 4 次课教学周第 11-12周机时安排2 学时实验名称实验四 图的实现与遍历实验类型1.验证性 2.综合性 3.设计性 4.其它 实验四 图的实现与遍历一、实验目的1.掌握图的基本存储方法。2.掌握有关图的操作算法并用高级语言实现。3.熟练掌握图的两种搜索路径的遍历方法。4.掌握图的有关应用。二、实验要求1认真编写和掌握本实验的算法和程序。2上机调试本程序。3保存和上交程序，并结合程序分析其输出结构。4认真书写实验报告。三、实验重点与难点实验重点：名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 37 页 -数据

33、结构 实验教案计算机学院计算机专业实验中心：刘伯红26 1图的逻辑结构和存储结构。2图的基本操作及实现。实验难点：图的两种搜索路径的遍历方法。四、实验内容1.请编制C 程序，以邻接矩阵表示法建立图，并实现深度优先遍历和广度优先遍历。2.请编制C 程序，以邻接表表示法建立图，并实现深度优先遍历和广度优先遍历。3.应用题：无向图遍历（1）问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。（2）基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集

34、。（3）测试数据：教科书图7.33。暂时忽略里程，起点为北京。（4）实现提示：设图的结点不超过30 个，每个结点用一个编号表示（如果一个图有n 个结点，则它们的编号分别为1,2,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红27 五、参考资料严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华大学出版社,2007.5。六、实验小结同学们基本能完成图的基本操作及实现。内容较多，课堂上

35、时间不够，应用题（选作内容）靠学生课下时间完成。七、课后作业完成课堂上未完成的作业与程序编码，撰写实验报告，预习下节课的内容。名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红28 实验五教案查找算法的实现及比较第 5 次课教学周第 13-14周机时安排2 学时实验名称实验五 查找算法的实现及比较实验类型1.验证性 2.综合性 3.设计性 4.其它 实验五 查找算法的实现及比较一、实验目的1.掌握几种典型的查找方法（顺序查找、折半查找、二叉排序树的查找、哈希查找）。2.对各种算法的特点、使用范围和效率有进一步的了解

36、，并能使用高级语言实现查找算法。二、实验要求1认真编写和掌握本实验的算法和程序。2上机调试本程序。3保存和上交程序，并结合程序分析其输出结构。4认真书写实验报告。三、实验重点与难点实验重点：名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红29 1各种查找算法基本操作及实现算法。2查找算法的比较。实验难点：查找算法的比较。四、实验内容请编制 C 程序，实现如下操作：设计程序，实现顺序查找、折半查找、二叉排序树的查找。尽量操作界面以菜单的形式进行选择。五、参考资料严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华

37、大学出版社,2007.5。六、实验小结同学们基本能完成查找算法的基本操作及实现。课堂上时间不够，查找算法比较与实现靠学生课下时间完成。七、课后作业完成课堂上未完成的作业与程序编码，撰写实验报告，预习下节课的内容。名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红30 实验六教案综合实验第 6 次课教学周课下完成（选做或实践课）机时安排1 学期实验名称实验六 综合实验实验类型1.验证性 2.综合性 3.设计性 4.其它 实验六 综合实验一、实验目的1了解并掌握数据结构的设计方法，具备初步的独立分析和设计能力。2初步掌

38、握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。3提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、实验要求1认真编写和掌握本实验的算法和程序。2上机调试本程序。3保存和上交程序，并结合程序分析其输出结构。名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红31 4认真书写实验报告。三、实验重点与难点实验重点：数据结构综合知识的运用。解决实际问题。实验难点：运用所学的数据结构理论知识和方法独

39、立分析和解决实际问题。四、实验内容（三选一）1简易图书管理模拟系统插入、查找和删除等数据操作在实际应用中非常普遍，通过设计和实现一个简易的图书管理系统，进一步提高学生对插入、查找和删除等操作的理解和应用能力。帮助学生理解和掌握线性表和平衡二叉树等数据结构的基本操作和实现方法，加强学生综合应用数据结构知识解决实际问题的水平和能力。（1）问题描述：一个简易图书管理的基本业务活动包括：对新购入一种书的采编入库、图书的借阅和归还等。（2）基本要求：a.每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。b.作为演示系统，不必使用文件存储书籍数据和借阅登记信息。名师资料总结-精品资料欢迎下

40、载-名师精心整理-第 31 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红32 我们要求各种书的数据用二叉排序树来存储，借阅登记信息采用顺序表链表来存储。顺序表存储借阅者信息，链表存储借阅者所借的各种书籍信息。借阅登记信息的存储结构如下示意：需要实现的三种主要功能定义如下：采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去。如果这种书在帐中已有，则只将该书的总库存量增加。借阅：如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。归还：注销对借阅者的登记，改变该书的现存量（如果借阅者归还所有的书，则注销该借阅者的信息）。(3)测试数据：入

41、库书号：ISBN 7-302-02368-9，ISBN 978-7-115-16985-3/TP，ISBN 978-7-302-03314-1，ISBN7-115-10563-4/TP 3043，ISBN 978-7-121-07479-0，ISBN 978-7-115-18809-0/TP，ISBN 978-7-04-024246-1，ISBN 7-111-12886-9，ISBN 978-7-115-19601-9/TP，ISBN 7-900183-01-9。借书证号为081716 的借阅者，先借阅10 种图书各一本，后归还借阅者 1 所借书 1 所借书 2 所借书 x 借阅者 2 所借书

42、 1 所借书 2 所借书 y 所借书 1 所借书 2 所借书 z 借阅者 n 所借书 1 所借书 2 所借书 m 名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红33 图书 ISBN 7-302-02368-9和 ISBN 978-7-121-07479-0。借 书 证 号 为081710的 借 阅 者，先 借 阅 图 书ISBN 978-7-121-07479-0和 ISBN 978-7-302-03314-110各一本，后归还图书 ISBN 978-7-121-07479-0。其余数据可自行设计。（4）实现提

43、示：各种图书按登记的先后顺序入库（利用平衡二叉树实现动态查找表的插入），书号为图书的关键字。初始时，平衡二叉树为空树。借阅者借阅图书时，先检查借阅者有无超期未归还图书，如有，则不能借阅，如无，利用平衡二叉树实现动态查找表的查找，登记借阅信息。注意，按规定，同一种书不能重复借阅。清除库存（选作）时，将该图书从平衡二叉树中删除。（5）选作内容：实现图书管理的清除库存操作：某种书已无保留价值，将它从图书帐目中注销。即，要实现平衡二叉树的删除操作。实现图书管理的显示操作：每次插入或删除平衡二叉树的一个结点之后，更新平衡二叉树的显示。平衡二叉树的显示可采用数据结构题集 6.69题要求的凹入表形式，也可以

44、采用图形界面画出树形。图书管理模拟系统的其它功能实现。2.航空客运订票系统名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红34 帮助学生熟练掌握线性表的基本操作在顺序和链式两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。(1)问题描述：航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。(2)基本要求：a.每条航线所涉及的信息有：终点站名、航班号、机型、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、手机号、订票

45、量、舱位等级1，2 或 3）以及等候替补的客户名单（包括姓名、手机号、所需票量）；b.作为示意系统，全部数据可只放在内存中；c.系统实现功能：查询航班：根据客户提供的终点站名输出下列信息：航班号、机型、飞行周日（星期几）、最后一天航班的日期和余票量。承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出订单号；若已满员或余票额少于订票额，则需重新询问；若需要，可登记排队候补。承办退票业务：根据客户提供的订单号或客户情况（姓名、日期和航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求

46、，则为他办理订票手续，否则依次询问其他排队候补的客户。名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红35(3)测试数据：由老师另外提供。(4)实现提示：已定票客户名单可采用链式存储的线性表作存储结构；等候替补的客户名单可采用链式存储的队列作为存储结构。整个系统需汇总个条航线的情况登记在一张顺序存储的线性表中，按航班号有序或目的地有序。每条航线作为该线性表的一条记录，应包括上述 8 个域，其中，乘员名单域为指向乘员名单链表的头指针，等候替补的客户为分别指向队头和队尾的指针。(5)选作内容：当客户订票要求不能满足时

47、，系统可向客户提供到达同一目的地的其他航线情况。3.校园导游咨询通过设计一个简单的校园导游咨询系统，加强学生对图数据结构的创建，查询以及其他的基本操作的理解，进一步提升学生对使用图结构解决具体问题的能力。帮助学生理解和掌握图数据结构在处理日常事务中的应用方法，加强学生综合应用数据结构知识解决实际问题的水平和能力。1、问题描述：设计一个校园导游程序，为来访客人提供各种信息查询服务。2、基本要求：（1）设计你所在学校的校园平面图，所含景点不少于10 个。以图中的顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径的长度等相关信息。名师资料总结-精品资料欢迎下载-名师精心整理

48、-第 35 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红36（2）为来访客人提供图中任意景点相关信息查询。（3）为来访客人提供图中任意景点的纹路查询，即查询任意两个景点之间的一条最短的简单路径。3、测试数据：根据学校的实际情况制定。4、实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。5、选作内容：（1）求校园图的相关节点。（2）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。（3）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。（4）校园导游图的景点和道路的修改扩充功能。（5）

49、扩充道路信息，如道路类别（车道，人行道等）、沿途景色等级、以及可按客人所需分别查询人行路径或车行路径或景观路径等。（6）扩充每个景点的邻接景点的方向等信息，使得路径的查询结果能提供详尽的导向信息。（7）实现校园导游图的仿真界面。五、参考资料名师资料总结-精品资料欢迎下载-名师精心整理-第 36 页，共 37 页 -数据结构 实验教案计算机学院计算机专业实验中心：刘伯红37 严蔚敏,吴伟民,米宁著.数据结构题集(语言版)M,清华大学出版社,2007.5。六、实验小结本次实验是大型作业，可作为学生集中上机实践使用，也可作为学生课外学习兴趣作业，主要靠学生课下时间完成。七、课后作业课下完成大型作业与程序编码，撰写实作报告。名师资料总结-精品资料欢迎下载-名师精心整理-第 37 页，共 37 页 -