第一篇：数据结构实验教案
第一次实验 线性表
（一）实验目的和要求：
1.熟悉VC集成环境
2.会定义线性表的顺序结构和链式结构
3.熟悉对线性表的基本操作，如插入、删除等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现线性表的建立、插入、删除等功能。
写出线性表、顺序表、链表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的顺序表算法有： 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有： 1.建立链表
2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第二次实验 栈和队列
（一）实验目的和要求：
1.熟练掌握栈和队列的结构，以及这种数据结构的特点 2.会定义顺序栈、循环队列，能实现栈、队列的基本操作 3.会利用栈解决典型问题，如数制转换等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现栈（或者队列）的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等
写出栈的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.初始化栈 2.入栈 3.出栈
4.判断栈是否为空 5.十进制转换为八进制
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第三次实验 二叉树
（一）实验目的和要求：
1.熟练掌握二叉树的结构，以及这种数据结构的特点 2.会定义二叉树的链式存储结构
3.能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现二叉树的各种基本操作，如二叉树的建立（头插法或者尾插法），遍历等 写出二叉树的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第四次实验
查找
（一）实验目的和要求：
1.熟练掌握查找算法的基本思想，以及算法的适用条件
2.会定义静态查找表的顺序结构，能实现顺序查找、二分查找
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现顺序查找、二分查找。
写出静态查找表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.建立静态查找表 2.顺序查找
3.建立有序的静态查找表 4.二分查找
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第二篇：数据结构实验教案
实验一 预备实验
一、实验项目的目的和要求：
1． 复习C语言指针的用法
2． 复习C语言结构体的用法 3． 理解时间复杂度分析的基本方法
二、实验内容：
1．用指针方式编写程序：从键盘输入N个整型数据，并存入数组，要求将N个数中最大的数与第一个数交换；将其中最小的数最后一个数交换。
基本思想：设两个指针分别指向最大数组元素和最小数组元素。再设一个移动指针从数组的第一个元素开始，依次与最大数组元素指针、最小数组元素指针的内容进行比较，作出相应的变化，一直到移动指针移到最后一个元素。
2．有N 个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求从键盘依次输入N 个学生的学号、姓名、三门课的成绩，自动计算三门课的平均分数，并将N 个学生的数据输出。
基本思想：对每一名学生循环，再对三门课程循环求平均成绩
三、实验中存在的问题：
实验二 线性表的基本操作
一、实验项目的和要求：
1． 掌握线性表的特点
2． 掌握线性表的顺序存储结构和链式存储结构的基本运算。3． 尽可能考虑算法的健壮性
4． 实验报告中要写出测试数据、错误分析以及收获。
二、实验内容一：线性表两种存储结构的基本运算
1.用结构体类型描述线性表的两种存储结构 2.完成课堂上所讲的两种存储结构的基本运算 3.要求用二级菜单实现
***************************** * 1-------顺序表 * * 2-------链 表 * * 0-------退 出 * *****************************
请输入的选择：(0-2)：
线性表的链式存储
## # 1----前插建立链表
# # 2----后插建立链表 # # 3----访问第i个元素 # # 4----插入 # # 5----删除 # # 6----求线性表的表长 # # 0----退出 #
## 请输入选择(0-6)：
分析：1．使用循环建立菜单
２．使用switch语句进行选择，执行相应的子函数（每一个运算编写一个子函数）
实验内容二：超市密码存储箱系统的设计与实现
1.顾客使用箱子的流程为“投一元硬币”--------“找到一个空箱子，同时产生密码”（系统完成）--------“打印密码，打开箱子”（系统完成）--------“取密码纸存包，并关闭箱子，入超市购物”--------“购物结束”--------“输入密码”--------“找到对应箱子并打开”（系统完成）--------“取包”。2.现要求设计程序模拟以上系统完成的功能
①界面：在我们的模拟系统中，箱子在屏幕上被画出来，并编号，空箱为蓝色，被使用时变成红色，再变为空后则恢复蓝色； ②通过按“1”键模拟顾客投币；
③当空箱子被顾客申请得到的同时，系统自动生成6位数密码，此密码不能与正在被使用的任何一个箱子的密码相同。3.设计分析
在设计时，可利用链表来组织所有的箱子，所有的箱子以结点的形式表示，结点中存放箱号、密码（满箱有，空箱无）以及指向下一个结点的指针。空箱结点放在一个链表1中，满箱结点放在另一个链表2中。
若有顾客投币（这里按下“1”键模拟），查看链表1是否为空，若为空，则显示“箱满，请稍侯！”，若非空，则取出一个结点，随机产生一个六位数密码，并将些密码和链表2中所有结点的密码相比较，若有重复，则再随机产生一个新密码，直到无重复；将密码信息写入此结点，并将其插入链表2；将此箱的颜色改为红色。4.密码箱的存储结构类型定义 typedef struct node { int num;/*箱子的号码*/ int password;/*箱子的密码（满箱有，空箱无）*/ struct node *next;/*指向下个结点的指针*/ }Node,*LinkList；
分析：１．初始化，建立一个代表空箱子链表，建立一个只有头结点的实箱子链表．
２．如果想要存包时，就在空箱子链表中进行查找，如果为空，代表箱子已满，否则从空箱子链表中删除一个结点，并给它赋值，将该结点插入到实箱子链表中．
３．如果想要取包时，就输入密码，在实箱子链表中进行匹配，如果成功，就从实箱子链表中删除相应的结点，插入到空箱子链表中．
４．另外还需要的函数有：随意产生密码函数，匹配密码函数 实验内容三：员工通讯录管理系统
1.为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的办公室电话号码、手机号码及电子邮箱。
2.现要求设计程序模拟以上系统完成的功能
其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的输出。3.设计分析
在本设计中，整个通讯录可以采用顺序表或链表方式存储。采用前者，可以提高查询速度；采用后者，可以提高插入与删除记录的效率。
4.员工通讯信息的结构类型定义和通讯录链表的结点类型
typedef struct { char num[5];/*员工编号*/ char name[8];/*员工姓名*/ char phone[9];/*办公室电话号码*/ char call[12];/*手机号码*/ }DataType；/*员工通讯信息的结构类型*/ typedef struct node { DataType data;/*结点的数据域*/ struct node *next;/*结点的指针域*/ }ListNode,*LinkList；/*通讯录链表的结构类型*/ 分析：１．建立一个可循环的菜单
２．使用switch语句，调用子函数实现以下功能
针对每一位员工作为一个结点建立链表．
在该链表上进行查找、插入、删除、修改及输入／出。实验内容四：运动会记分子系统或学生成绩管理子系统
1.参加运动会的N个学校编号为1~N。比赛分成M个男子项目和W个女子项目，每个项目取前3名，得分分别为5，3，2。写一个程序产生各种成绩单和得分报表。2.完成功能包括如下：
①产生一总成绩表，包括：学校编号名、男子团体总分、女子团体总分、团体总分 存储结构要求用线性表的顺序存储。
②实验报告中要写出测试数据、错误分析以及收获。
③若选择学生成绩管理子系统，可仿照运动会记分子系统完成相关的插入、删除、查找及各种统计工作。
分析：１．分析顺序表中每个元素的结构（数组元素是一个结构体）
２．建立顺序表
３．在顺序表进行插入、删除、查找
４．进行统计 实验中存在的问题：
实验三 栈和队列的应用
一、实验目的和要求：
1． 掌握栈和队列的概念和特点
2． 掌握栈和队列在顺序和链式存储结构下的插入、删除算法 3． 认真分析项目实例中的内容，将相关程序在计算机上运行实现
二、实验内容一：表达式求值问题
1．求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”、“—”、“*”、“/”）的算术表达式，计算其结果。2．设计分析
首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）3．结点结构类型描述如下
typedef struct { char *base,*top;int stacksize;}sqstack;分析：１．判断输入的字符是否为数值
2.比较判断运算符的优先级 3.何时结束循环，不再运算
实验内容二：迷宫求解问题
1.迷宫是一个m行n列的矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m,n），即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则 沿原路退回，换一个方向再继续探索，直到出口为止。2.迷宫的功能
要求随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圏障碍，设置东南西北四个方向，采用链栈进行操作。最后迷宫如不是通路给出“此迷宫元解”，如是通路要求输出所走过的路径。3．结点结构类型描述如下
typedef struct node { int row;int col;
struct node *next;};分析：１．建立迷宫，使用二维数组，第一行／列，最后一行／列均初始化为０代表墙不通，这样使其内部的元素均有四个方向进行统一判断，其余元素进行随机产生０代表不通，１代表通．
２．确定入口，出口的坐标．
３．判断该元素是否可通（元素值等于１，一方面代表通，另一方面未走过）． ４．标记每一个走过的元素，将其元素值加１．
５．元素的四个方向用０－３表示，下一个方向的坐标可以从当前坐标及方向就可以确定．
三、实验中存在的问题：
实验四
二叉树两种存储结构的应用
一、实验目的和要求：
1． 掌握二叉树的遍历思想及二叉树的存储实现。2． 掌握二叉树的基本操作：建立二叉树、二叉树的遍历 3． 选择一种形式完成二叉树的显示 4． 掌握二叉树的常见算法的程序实现
5． 实验报告中要写出测试数据、错误分析以及收获
二、实验内容一：二叉树的建立及相关算法的实现
1．完成的功能包括如下几点：
①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。
分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在结点则输入@
②显示二叉树
③求二叉树的高度及二叉树的叶子个数等等
④在主函数中设计一个简单的菜单，分别调试上述算法
实验内容二：哈夫曼编码/译码系统
1．要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。2．设计分析
在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信息的翻译。要求设置发送者和接收者两个功能。
发送者的功能包括：
①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出现的次数（频率）；③根据字符的种类数和各字符出现的次数建立哈夫曼树；④利用以上哈夫曼树求出各字符的哈夫曼编码；⑤将字符信息转换成对应的编码信息进行传送。接收者的功能包括：
①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信息还原成发送前的字符信息。3．结点的类型定义
①哈夫曼树的存储结构类型定义为：
typedef struct { char data;/*编码对应的字符*/ int weight;/*结点的权值*/ int lchild,rchild,parent;/*左右孩子及双亲的下标*/ }HTNode;②哈夫曼编码的存储结构类型定义为： typedef struct { char bits[N];/*存放哈夫曼编码的字符数组*/ int start;/*记录编码的起始位置，因为每种字符的编码长度不同*/ }HCode;
三、实验中存在的问题：
实验五
图子系统一、实验目的和要求：
１．掌握图的存储思想及其存储实现
２．掌握图的深度、广度优先遍历算法思想及其程序实现 ３．掌握图的常见应用算法的思想及其程序实现
二、实验内容一：图的遍历问题
1．键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。建立一个有向图或无向图（自定）的邻接表并输出该邻接表 2．在图的邻接表的基础上计算各顶点的度，并输出 3．以有向图的邻接表为基础实现输出它的拓扑排序序列 4．采用邻接表存储实现无向图的深度优先遍历 5．采用邻接表存储实现无向图的广度优先遍历
6．采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法
7．在主函数中设计一个简单的菜单，分别调试上述算法 实验内容二：所有顶点对的最短路径
1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这
4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2．设计分析
用有向加权图表示的交通图中，有向边
typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct { vextype vex[maxsize];edgetype arc[maxsize][maxsize];int vexnum,arcnum;}Mgraph;
三、实验中存在的问题：
实验六 数据结构综合性实验
一、实验目的和要求：
掌握小型系统开发方法，提高学生综合开发能力。根据实际问题，设计方案，综合运用课程知识，完成《学生成绩管理系统》或《数据结构算法演示系统》的设计、编程与调试工作。
二、实验内容一：
分析、调研数据结构课程所学的算法（功能模块）或学生成绩管理的相关功能模块，采用结构化设计思想、模块分解的规则构成一个易使用的小型管理系统。具体要求见《数据结构实验》课程设计
实验内容二：手机短信中电话号码和手机号码的识别与提取
1.在使用手机收发短信时，收到的短信内容中常会包含对方发来的电话号码或手机号码，为了方便用户能直接提取其中的号码并存入到其手机的通讯录中，现要求开发手机系统软件中的一个子功能，实现从手机短信内容中识别和提取电话号码（7位或8位）和手机号码(11位)，并将其存入通讯录中。2.设计分析
要从手机短信的内容中识别电话号码或手机号码，必须从短信的第一个字符开始查找，找到第一个数值型字符（‘0’～‘9’），然后依次判断其后的字符，若其后有连续的6个或7个数值型字符，则将其识别成电话号码并提取，若其后有连续的10个数值型字符，则将其识别成手机号码并提取。继续向后搜索直到整个短信查找完毕。3.存储结构类型定义 ①短信的存储结构类型定义
typedef struct { char word[200];/*短信内容*/ int length;/*短信长度*/ }Message;②通讯录中记录的存储结构类型的定义
typedef struct { char name[8];/*姓名*/ char phone[11];/*电话号码或手机号码*/
}Note;实验内容三：药店的药品销售统计系统
1.设计一系统，实现医药公司定期对各药品的销售记录进行统计，并按药品编号、单价、销售量或销售额做出排序。2.设计分析
在设计中，首先从数据文件读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药品名称、单价、销售量、销售额。其中药品编号共4位，采用字母和数字混合编号，如：B125，前一位为大写字母，后三位为数字。3.存储结构类型定义
①药品信息的存储结构类型定义
typedef struct node { char num[4];/*药品编号*/ char name[10];/*药品名称*/ float price;/*单价*/ int count;/*销售量*/ float sale;/*销售额*/ }DataType;②存储药品信息的顺序表的定义
typedef struct { DataType r[maxsize];int length;}sequenList;实验内容四：电视大赛观众投票及排名系统
1.在很多电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排列，从而自动产生冠军、亚军和季军。现要求编写一程序模拟实现上述系统的功能。2.设计分析
在本系统中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依次存入顺序表单元中，观众通过按键进行投票，按“1”表示为1号选手投票，按“2”表示为2号选手投票，依次类推。以按“0”作为投票结束标志。投票结束后进行排序。3.存储结构类型定义
①选手信息的存储结构类型定义
typedef struct node { char name[8];/*选手姓名*/ int num;/*选手编号*/ int score;/*选手得分*/ int tax;/*选手名次*/ }Node;②开辟空间用于构造存放选手信息的顺序表R：R=(Node *)malloc(n*sizeof(Node));其中n 为参赛选手的人数，在此采用动态空间分配，而不是在开始时直接开辟静态数组，这样是为了避免空间的不足造成浪费。
在投票时，按“1”为1号选手投票的实现：
Scanf(“%c”,&k);/*观众按键*/ R［K-48］.score= R［K-48］.score+1;若观众输入的是“1”，则“1”-48即为ASCII-48=1，因此可以实现对1号选手的票数加1，即R［1］=R［1］+1。其他选手类似。
第三篇：数据结构实验课教案
授课教案
（2016—2017学第一学期）
课程名称： 课程编码： 总学时： 课程类别：
任课教师： 开课单位： 职称： 授课专业： 授课班级：
数据结构 B13040009A 总学分： 专业课 李素若 计算机工程学院
教授 计算机科学与技术
2015级计算机科学与技术专业1、2班 授课进度第3周，第6次课（2学时）授课题目
(教学章、节实验一线性表的顺序存储结构 或主题)
授课日期
016年9月14日（9 2
月13日）
.掌握线性表顺序存储结构的特点：逻辑上相邻的数据元素其物理位置上也相邻。1 2.掌握线性表顺序存储结构的插入、删除操作特点移动操作。
教学
目标
1.线性表的顺序存储特点
教学 2.线性表的顺序存储的基本算法 重点
1.线性表的顺序存储的基本算法
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．输入一组整型元素序列，建立顺序表。1 2 ．遍历该顺序表。3 ．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。4 ．判断该顺序表中元素是否对称,对称返回1,否则返回0。5 ．输入整型元素序列利用有序表插入算法建立一个有序表。6 ．利用实验6建立两个递增有序表并把它们合并成一个递增有序表。7
二、实验指导
1．参考程序为：
voidCreateSqList(SqList*L){ intn,i; do{ printf(“请输入数据元素的个数:”);
scanf(“%d”,&n);
if(n<=0)printf(“输入错误n”); } while(n<=0); for(i=0;i
} 2 ．参考程序为：
voidPrintList(SqListL){ inti;
for(i=0;i intFindelems(SqListL,ElemTypee){ inti; for(i=0;i return0; } 4．分析：从顺序表表头开始扫描，当数据元素为偶数时就从该数开始往后查找，一旦 — 1— 教学过程及内容 找到奇数，则将该偶数与此奇数交换。顺序表中所有数据全部扫描结束后，所有奇数就排列 在表的前端。参考程序为： voidChangeVal(SqList*L){ inti,j,temp; for(i=0;i if(L>elem[j]%2!=0){ temp=L>elem[i]; L>elem[i]=L>elem[j]; L>elem[j]=temp; break; } } if(j==L>length)break; } } } 5．参考程序为： intYesNo_Symmetry(SqListL){ inti,j; j=L.length1; for(i=0;i return0; } return1; } 6 ．参考程序为： voidInsert_OrderList(SqList*L,intx){ inti,j; for(i=0;i — 2— 教学过程及内容 L>elem[j+1]=L>elem[j]; L>elem[i]=x; L>length++; } voidCreate_OrderList(SqList*L){ intn,i,input; do{ printf(“请输入数据元素的个数:”); scanf(“%d”,&n); if(n<=0)printf(“输入错误n”); while(n<=0); } for(i=0;i Insert_OrderList(L,input); } } 7 ．参考程序为： SqList*Merge_OrderList(SqListA,SqListB)//将有序顺序表A和B合并到有序顺序表C中返回 { inti=0,j=0,k=0; SqList*C=(SqList*)malloc(sizeof(SqList)); C>length=0; while(j C>elem[i++]=A.elem[j++]; else C>elem[i++]=B.elem[k++]; } if(j==A.length) while(k } — 3— 授课进度第4周，第8次课（2学时）授课题目 (教学章、节实验二单向链表 或主题) 授课日期 016年9月21日（9 2 月20日） ．掌握线性链表的操作特点，即指针是逻辑关系的映像。1 ．掌握动态产生单链表的方法。2 3 ．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。 教学 目标 1．掌握动态产生单链表的方法。 教学 2．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。重点 1．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 ．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。1 ．遍历单向链表。2 3 ．把单向链表中元素逆置（不允许申请新的结点空间）。．在单向链表中删除所有的偶数元素结点。4 5 ．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建 立一个非递减有序单向链表。 ．利用实验5建立两个递增有序单向链表，然后合并成一个递增链表。6 7 ．利用实验1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个 全部为偶数（尽量利用已知的存储空间）。 二、实验指导 1．参考程序为： LinkListCreateListH(void)//头插法产生带头结点单链表 { intch; LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists; head>next=NULL; while(scanf(“%d”,&ch)==1)//输入数据类型错误时结束单链表的生成 { s=(LinkList)malloc(sizeof(LNode)); s>data=ch; s>next=head>next; head>next=s; } returnhead; } LinkListCreateListRand(void)//利用随机函数产生带头结点单链表（头插法）{ intch,i; LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists; head>next=NULL; srand((unsigned)time(NULL)); printf(“PleaseinputCreateNnmbers:”); scanf(“%d”,&ch); for(i=0;i s>data=rand()%50;//随机产生0~49之间的数 — 1— 教学过程及内容 s>next=head>next; head>next=s; } returnhead; } 2 ．参考程序为： voidPrintLinkList(LNodeL){ LinkListp; p=L.next; while(p){ printf(“%d”,p>data); p=p>next; } printf(“n”); } 3．参考程序为： voidInverse_set(LinkListhead){ LNode*r,*m=NULL,*p; p=head>next; while(p!=NULL){ r=m;m=p; p=p>next; m>next=r; } head>next=m; } 4．参考程序为： voidDelEvenLinkList(LinkListhead){ LinkListq,p; p=head>next; q=head; while(p){ if(p>data%2==0){ q>next=p>next; free(p); — 2— 教学过程及内容 p=q>next; } else { q=p; p=p>next; } } } 5 ．参考程序为： voidInsertIncr(LinkListhead,ElemTypex)//将结点插入递增的单链表 { LinkListq,p,s; s=(LinkList)malloc(sizeof(LNode)); s>data=x; q=head; p=head>next; while(p&&p>data p=p>next; } s>next=q>next; q>next=s; } LinkListCreateListIncr(void)//通过调用插入有序链表函数生成递增单链表 { intch; LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists; head>next=NULL; while(scanf(“%d”,&ch)==1)//输入数据类型错误时结束单链表的生成 InsertIncr(head,ch); returnhead; } 6 ．参考程序为： LinkListLinkListCat(LinkListhead1,LinkListhead2){ LinkListh1,h2,h; LinkListhead=(LinkList)malloc(sizeof(LNode)); head>next=NULL; — 3— 教学过程及内容 h1=head1>next; h2=head2>next; h=head; while(h1&&h2){ if(h1>data h1=h1>next; } else { h>next=h2; h=h>next; h2=h2>next; } } if(h1)h>next=h1; if(h2)h>next=h2; returnhead; } 7 ．参考程序为： # include voidPrintLinkList(LNodeL){ LinkListp; p=L.next; while(p){ printf(“%d”,p>data); p=p>next; — 4— 教学过程及内容 } printf(“n”); } voidDecoLinkList(LNodehead,LinkListhead1,LinkListhead2)//将单链表head拆分奇数链head1和偶数链head2 { LinkListh,h1,h2; h=head.next; h1=head1; h2=head2; while(h){ if(h>data%2==0){ h2>next=h; h=h>next; h2=h2>next; } else { h1>next=h; h=h>next; h1=h1>next; } } h1>next=NULL; h2>next=NULL; } main(){ LinkListhead; LinkListhead1=(LinkList)malloc(sizeof(LNode)); LinkListhead2=(LinkList)malloc(sizeof(LNode)); head=CreateListIncr(); PrintLinkList(*head); DecoLinkList(*head,head1,head2); PrintLinkList(*head1); PrintLinkList(*head2); } — 5— 授课进度第5周，第10次课（2学时）授课题目 (教学章、节实验三栈的存储及基本运算 或主题) 授课日期 016年9月28日（9 2 月27日） .掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。1 2.了解和掌握递归程序设计的基本原理和方法。 教学 目标 .掌握栈的两种存储结构 1.栈的基本运算 教学 2.了解栈在递归函数中的作用 重点 3.掌握栈的两种存储结构 1 教学 2.栈的基本运算 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 ．采用顺序存储实现栈的初始化、入栈、出栈操作。1 2 ．采用链式存储实现栈的初始化、入栈、出栈操作。3 ．写一个程序，将输入的十进制数据M转换为八进制数据M8，将其调试通过。在此 基础上修改程序，实现十进制数据M向N进制（2或8或16）的转换。（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。 二、实验指导 ．参考程序为： 1 # include //用来存放栈中元素的一维数组 //用来存放栈顶元素的下标 } SqStack; intInitStack(SqStack**s)//初始化顺序栈 {(*s)=(SqStack*)malloc(sizeof(SqStack)); if((*s)==NULL)returnERROR;(*s)>top=1; returnOK; } intEmptyStack(SqStacks)//判断栈空 { if(s.top==1) { printf(“stackisempty!n”); returnOK; } returnERROR; } intGetTop(SqStacks,int*e)//取栈顶元算 { if(EmptyStack(s))returnERROR; *e=s.elem[s.top]; — 1— 教学过程及内容 returnOK; } intPush(SqStack*s,inte)//入栈 { if(s>top==Stack_Size1) { printf(“stackisfull!n”); returnERROR; } s>top++; s>elem[s>top]=e; returnOK; } voidPrintStack(SqStacks)//打印栈中数据 { inti; for(i=0;i<=s.top;i++)printf(“%d”,s.elem[i]); printf(“n”); } intPop_Stack(SqStack*s,int*e)//出栈 { if(EmptyStack(*s)) returnERROR; *e=s>elem[s>top]; s>top; returnOK; } voidmain(){ intcord,e,x,y; SqStack*s; do { printf(“nMainMenun”); printf(“1CreatStackn”); printf(“2GetTopElementn”); printf(“3Pushn”); printf(“4Popn”); printf(“5Printn”); printf(“6quitn”); scanf(“%d”,&cord); — 2— 教学过程及内容 switch(cord){ case1: InitStack(&s); break; case2: if(GetTop(*s,&y)) printf(“StackTop=[%d]n”,y); break; case3: printf(“Pleaseinputpushelement:”); scanf(“%d”,&e); Push(s,e); break; case4: if(Pop_Stack(s,&x)) printf(“Popstack=[%d]n”,x); break; case5: PrintStack(*s); break; case6: return; } } while(cord<=6); } 2 ．参考程序为： include structstacknode*next; } StackNode; typedefstruct { StackNode*top;/*栈顶指针*/ LinkStack; } — 3— 教学过程及内容 voidInitStack(LinkStack*s)//初始化栈 { s>top=NULL; } intEmptyStack(LinkStacks)//判断栈空 { if(s.top==NULL)returnOK; elsereturnERROR; } intGetTop(LinkStacks,int*e)//取栈顶元素 { if(EmptyStack(s))returnERROR; *e=s.top>data; } voidPush(LinkStack*s,inte)//入栈 { StackNode*p=(StackNode*)malloc(sizeof(StackNode)); p>data=e; p>next=s>top; s>top=p; } intPop_Stack(LinkStack*s,int*e)//出栈 { StackNode*p; if(EmptyStack(*s))returnERROR; p=s>top; *e=p>data; s>top=p>next; free(p); returnOK; } voidPrintStack(LinkStacks)//打印栈中元素 { StackNode*p=s.top; while(p){ printf(“%d”,p>data); p=p>next; } } voidmain() — 4— 教学过程及内容 { intcord,e,x,y; LinkStacks; do { printf(“nMainMenun”); printf(“1CreatStackn”); printf(“2GetTopElementn”); printf(“3Pushn”); printf(“4Popn”); printf(“5Printn”); printf(“6quitn”); scanf(“%d”,&cord); switch(cord){ case1: InitStack(&s); break; case2: if(GetTop(s,&y)) printf(“StackTop=[%d]n”,y); break; case3: printf(“Pleaseinputpushelement:”); scanf(“%d”,&e); Push(&s,e); case4: break; if(Pop_Stack(&s,&x)) printf(“Popstack=[%d]n”,x); break; case5: PrintStack(s); break; case6: return; } } while(cord<=6); } 3 ．参考程序为： 1）（— 5— 教学过程及内容 voidConversion(SqStack*S){ intN,n1,t; printf(“输入一个十进制数字:n”); scanf(“%d”,&N);//输入一个十进制数字 printf(“输入要转换的n进制数字(2、8、16):n”); scanf(“%d”,&n1);//输入要转换的进制 while(N){ Push(S,N%n1); N=N/n1; } printf(“该数转化为%d进制数为:t”,n1); if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t); if(t==10){printf(“A”);continue;} if(t==11){printf(“B”);continue;} if(t==12){printf(“C”);continue;} if(t==13){printf(“D”);continue;} if(t==14){printf(“E”);continue;} if(t==15){printf(“F”);continue;} printf(“%d”,t); } } else PrintStack(*S); } voidmain(){ SqStack*S; InitStack(&S); Conversion(S); }（2） voidConversion(LinkStack*S){ intN,n1,t; printf(“输入一个十进制数字:n”); scanf(“%d”,&N);//输入一个十进制数字 — 6— 教学过程及内容 printf(“输入要转换的n进制数字(2、8、16):n”); scanf(“%d”,&n1);//输入要转换的进制 while(N){ Push(S,N%n1); N=N/n1; } printf(“该数转化为%d进制数为:t”,n1); if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t); if(t==10){printf(“A”);continue;} if(t==11){printf(“B”);continue;} if(t==12){printf(“C”);continue;} if(t==13){printf(“D”);continue;} if(t==14){printf(“E”);continue;} if(t==15){printf(“F”);continue;} printf(“%d”,t); } } else PrintStack(*S); } voidmain(){ LinkStackS; InitStack(&S); Conversion(&S); } — 7— 授课进度第8周，第14次课（2学时）授课题目 (教学章、节实验四队列 或主题) 授课日期 016年10月19日（10 2 月18日） .掌握队列这种数据结构的逻辑特性及其主要存储结构。1 2.在简单情况下会使用顺序结构的实现队列，熟练掌握循环队列的使用。.在复杂情况下会使用链表结构的队列，并能在现实生活中灵活运用。3 教学 目标 1.熟练掌握循环队列的使用。 教学 2.在复杂情况下会使用链表结构的队列。重点 1.链队列的使用。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 ．采用顺序存储实现循环队列的初始化、入队、出队操作。1 2 ．采用链式存储实现队列的初始化、入队、出队操作。3 ．编写一个程序，使用两个链队q1和q2，用来分别存储由计算机随机产生的20个 100以内的奇数和偶数，然后每行输出q1和q2的一个值，即奇数和偶数配对输出，直到任 一队列为空为止。 二、实验说明 ．循环队列类型采用如下结构： 1 defineMAXSIZE100//最大队列长度 # typedefintElemType; typedefstruct{ ElemTypedata[MAXSIZE]; intfront,rear;//队头、队尾指针 SqQueue; } ．链队类型采用如下结构： 2 typedefstructQNode { ElemTypedata; structQNode*next; QNode,*QueuePtr; } typedefstruct { QueuePtrfront; QueuePtrrear; LinkQueue; } 三、实验指导 1．参考程序为： intInitQueue(SqQueue**Q)//初始化循环队列 { * Q=(SqQueue*)malloc(sizeof(SqQueue)); if(!(*Q)) return0; *Q)>front=(*Q)>rear=0;(return1; } intQueueEmpty(SqQueueQ)//判断队空 { returnQ.front==Q.rear; } — 1— 教学过程及内容 intQueueFull(SqQueueQ)//判断队满 { return(Q.rear+1)%MAXSIZE==Q.front; } intEnQueue(SqQueue*Q,ElemTypee)//入队操作 { if(QueueFull(*Q)) /队列满 return0; /Q>data[Q>rear]=e; Q>rear=(Q>rear+1)%MAXSIZE; return1; } intDeQueue(SqQueue*Q,ElemType*e)//出队操作 { if(QueueEmpty(*Q))return0; else { *e=Q>data[Q>front]; Q>front=(Q>front+1)%MAXSIZE; return1; } } 2 ．参考程序为： intInitQueue(LinkQueue*Q)//将Q初始化为一个空的链队列 { Q>front=Q>rear=(QueuePtr)malloc(sizeof(QNode)); if(Q>front==NULL) return0; Q>front>next=NULL; return1; } intQueueEmpty(LinkQueueQ)//判断队空 { returnQ.front==Q.rear; } intEnQueue(LinkQueue*Q,ElemTypee)//入队操作 { QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) return0; — 2— 教学过程及内容 p>data=e; p>next=NULL; Q>rear>next=p; Q>rear=p; return1; } intDeQueue(LinkQueue*Q,ElemType*e)//出队操作 { QueuePtrp; if(QueueEmpty(*Q))return0;//若队列Q为空队列 p=Q>front>next; *e=p>data; Q>front>next=p>next; if(Q>rear==p) Q>rear=Q>front;//若Q只有一个结点 free(p); return1; } 3 ．参考程序为： intmain(){ LinkQueueq1,q2; inti=0,j=0,num; InitQueue(&q1); InitQueue(&q2); srand((unsigned)time(NULL)); while(i<20||j<20){ num=rand()%100; if(num%2==0&&i<20){ EnQueue(&q1,num); i++; } if(num%2!=0&&j<20){ EnQueue(&q2,num); j++; } } while(!QueueEmpty(q1)&&!QueueEmpty(q2)) — 3— 教学过程及内容 { DeQueue(&q1,&i);DeQueue(&q2,&j); printf(“%3d%3dn”,i,j); } free(q1.front); free(q2.front); return0; } — 4— 授课进度 授课题目 第9周，第16次课（2学时）授课日期 016年10月26日（10 2 月25日） (教学章、节实验五二叉树（Ⅰ）或主题)．掌握二叉树的存储实现。1 ．掌握二叉树的遍历思想。2 教学 目标 ．掌握二叉树的存储实现。1 ．掌握二叉树的遍历思想。教学 2 重点 1.掌握二叉树的遍历思想。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 1．数据域为字符的一棵二叉树用广义表形式输入，创建一个采用二叉链表存储的二叉 树，并按广义表的形式输出这棵二叉树。 ．在实验1的基础上完成这棵二叉树的中序遍历的递归算法。2 ．在实验1的基础上完成这棵二叉树的中序遍历的非递归算法。3 二、实验指导 ．参考代码为： 1 # defineMaxSize100 voidCreateBTNode(BTree*b,char*str)//广义表形式输入二叉树，按二叉链表存储二叉树 { BTNode*St[MaxSize],*p=NULL; inttop=1,k,j=0; charch; *b=NULL; ch=str[j]; while(ch!=' '){ switch(ch){ case'(':top++;St[top]=p;k=1;break; case')':top;break; case',':k=2;break; default:p=(BTNode*)malloc(sizeof(BTNode)); p>data=ch;p>lchild=p>rchild=NULL; if(*b==NULL)*b=p; else { switch(k){ case1:St[top]>lchild=p;break; case2:St[top]>rchild=p;break; } } } j++; ch=str[j]; } } voidDispBTNode(BTNode*b)//广义表输出二叉树 — 1— 教学过程及内容 { if(b!=NULL){ printf(“%c”,b>data); if(b>lchild!=NULL||b>rchild!=NULL){ printf(“(”); DispBTNode(b>lchild); if(b>rchild!=NULL)printf(“,”); DispBTNode(b>rchild); printf(“)”); } } } 2 ．参考代码为： voidInOrder(BTreeT)//中序递归遍历 { if(T){ InOrder(T>lchild);/*中遍历左子树*/ printf(“%3c”,T>data);/*访问根结束*/ InOrder(T>rchild); } } 3 ．参考代码为： voidInOrder1(BTreeT)//非递归中序遍历 { SqStack*S;BTreeP=T; InitStack(&S); do{ /*从树或子树根出发往左到叶子*/ while(P){ Push(S,P); P=P>lchild; } if(S>top!=1){/*P为NULL要么是叶子，要么是没有左子树*/ Pop(S,&P); printf(“%3c”,P>data); P=P>rchild; } } while((S>top!=1)||P); } /*中根遍历右子树*/ — 2— 授课进度第11周，第20次课（2学时）授课题目 (教学章、节实验五二叉树（Ⅱ）或主题)．二叉树的常用算法。1 2 ．二叉树线索化及遍历。 授课日期 016年11月9日（11 2 月8日） 教学 目标 1．二叉树的常用算法。 教学 重点 1.二叉树的常用算法。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 ．求二叉树的宽度。1 2 ．求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。．输出二叉树中从每个叶子结点到根结点的路径。3 4 ．建立前序线索二叉树，并实现前序遍历。 二、实验指导 1．参考代码为： intBTWidth(BTNode*b)//求二叉树宽度 { struct { /结点的层次编号 intlno; /BTNode*p; //结点指针 Qu[MaxSize];//定义顺序非循环队列 } intfront,rear; //定义队首和队尾指针 intlnum,max,i,n; front=rear=0;//置队列为空 if(b!=NULL){ rear++; //根结点指针入队 Qu[rear].p=b; Qu[rear].lno=1; //根结点的层次编号为1 //队列不为空 while(rear!=front) { front++; b=Qu[front].p; //队头出队 //左孩子入队 lnum=Qu[front].lno; if(b>lchild!=NULL){ rear++; Qu[rear].p=b>lchild; Qu[rear].lno=lnum+1; } if(b>rchild!=NULL){ rear++; Qu[rear].p=b>rchild; Qu[rear].lno=lnum+1; } } — 1— //右孩子入队 教学过程及内容 max=0;lnum=1;i=1; while(i<=rear){ n=0; while(i<=rear&&Qu[i].lno==lnum){ /求每层的结点数 n++;i++; /} lnum=Qu[i].lno; if(n>max)max=n; } returnmax; } else return0; } 2 ．参考代码为： intBTNodeDepth(BTNode*b)//求二叉树b的深度 { intlchilddep,rchilddep; if(b==NULL)return(0); else { lchilddep=BTNodeDepth(b>lchild);//左子数的高度 rchilddep=BTNodeDepth(b>rchild);//右子树的高度 return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); } } voidLong(BTreeT){ if(T!=NULL)//在T不为空的情况下 { printf(“%3c”,T>data);//访问节点 if(BTNodeDepth(T>lchild)>BTNodeDepth(T>rchild))//判断往左走还是往右走 Long(T>lchild); else Long(T>rchild); } } 3．参考代码为： — 2— 教学过程及内容 voidPrintStack(SqStack*S)//使用线性栈辅助操作 { inti; for(i=0;i<=S>top;i++)printf(“%3c”,S>elem[i]); printf(“n”); } voidAllPath(BTreeT,SqStack*S)//输出二叉树上从根到所有叶子结点的路径 { charch; if(T){ Push(S,T>data); if(!T>lchild&&!T>rchild)//如果左指针和右指针同时为空，才说明该节点为叶子节 点 PrintStack(S); else { AllPath(T>lchild,S); AllPath(T>rchild,S); } Pop(S,&ch); } } 4．参考代码为： BiThrTreepre; voidPreThreading(BiThrTreep)//先序线索化 { if(p){ if(!p>lchild) { p>LTag=Thread; p>lchild=pre; //前驱线索 } if(!pre>rchild) { pre>RTag=Thread; pre>rchild=p; //后继线索 } pre=p; if(p>LTag==Link) PreThreading(p>lchild);//左子树线索化 if(p>RTag==Link) — 3— 教学过程及内容 PreThreading(p>rchild);//右子树线索化 } } BiThrTreePreOrderThreading(BiThrTreeT)//先序线索二叉树 { BiThrTreethrt; if(!(thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) returnNULL; thrt>LTag=Link; thrt>RTag=Thread;//建头结点 thrt>rchild=thrt;//右指针回指 if(!T)thrt>lchild=thrt;//空二叉树 else { thrt>lchild=T; pre=thrt; PreThreading(T);//先序遍历进行先序线索化 pre>rchild=thrt;pre>RTag=Thread;//最后一个结点线索化 thrt>rchild=pre; } returnthrt; } voidPreOrderTraverse_Thr(BiThrTreethrt)//先序遍历二叉树 { BiThrTreep; printf(“先序遍历结果为：”); p=thrt>lchild; while(p!=thrt){ printf(“%3c”,p>data); while(p>LTag==Link){ p=p>lchild; printf(“%3c”,p>data); } p=p>rchild; } printf(“n”); } — 4— 授课进度第13周，第24次课（2学时）授课题目 (教学章、节实验六哈夫曼树 或主题) 授课日期 016年11月23日（11 2 月22日） .理解哈夫曼树的特征及其应用。1.在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编 2 码和译码。 教学 目标 3.通过该实验，使学生对数据结构的应用有更深层次的理解。 1.哈夫曼树构造。 教学 2.哈夫曼编码和译码。重点 1.哈夫曼树构造。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 1．哈夫曼树问题。 利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据 进行解码（复原）对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码 系统。试为这样的信息收发站写一个哈夫曼的编译码系统。 基本要求；（1）从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权 值（即字符出现的频度），建立哈夫曼树，进行编码，最后输出并存于文件hfmtree中。 2）利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正（文，再输出该文的二进制码。 3）测试数据。（用表2.1中给出的字符集(n=27)和频度的实际统计数据建立哈夫曼树。 表2.1用于测试的字符集合频度 并实现以下报文的译码和输出：“THISPROGRAMISMYFAVORITE”。 2．思考题：利用哈夫曼树及哈夫曼编码的原理编写一个算法，n个自然数之间经过加 减运算后结果最小的值是多少。注意：只能进行加减运算，且最后结果和运算的中间结果不 能为负。 二、实验指导 # include weight; parent,lchild,rchild; } HTNode,*HuffmanTree; typedefchar **HuffmanCode; typedefstruct{ unsignedint s1; unsignedint s2; } MinCode; MinCodeSelect(HuffmanTreeHT,unsignedintn); HuffmanCodeHuffmanCoding(HuffmanTree*H1,unsignedint*w,char*ch,unsignedintn)//求哈夫曼树及哈夫曼编码，将哈夫曼编码写入文本文件 { — 1— 教学过程及内容 unsignedinti,s1=0,s2=0; HuffmanTreep,HT; HuffmanCodeHC; char *cd; unsignedintf,c,start,m; MinCodemin; FILE*fp; if((fp=fopen(“Huffman.txt”,“wt”))==NULL){ printf(“CannotopenfileHuffman.txtanykeyexit!”); exit(1); } if(n<=1){ printf(“Codetoosmall!n”);exit(1);} m=2*n1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i<=n;i++,p++,w++){ p>weight=*w;p>parent=0; p>lchild=0;p>rchild=0; } for(;i<=m;i++,p++){ p>weight=0;p>parent=0; p>lchild=0;p>rchild=0; } for(i=n+1;i<=m;i++){ min=Select(HT,i1); s1=min.s1;s2=min.s2; HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char*)); cd[n1]=' '; for(i=1;i<=n;i++){ start=n1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[start]='0'; — 2— 教学过程及内容 elsecd[start]='1'; HC[i]=(char*)malloc((nstart)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); for(i=1;i<=n;i++)fprintf(fp,“%c%sn”,ch[i],HC[i]); fclose(fp); H1=HT; * returnHC; } MinCodeSelect(HuffmanTreeHT,unsignedintn)//求权值的最小值和次最小值 { unsignedintmin,secmin; unsignedinttemp; unsignedinti,s1,s2; MinCodecode; s1=1;s2=1; for(i=1;i<=n;i++)if(HT[i].parent==0){ min=HT[i].weight; s1=i; break; } for(;i<=n;i++)if(HT[i].weight s2=i; break; } for(i=1;i<=n;i++)if(HT[i].weight — 3— 教学过程及内容 s2=i; } code.s1=s1; code.s2=s2; returncode; } voidTranscodeing(intn,char*Char_Code,char*Huffman_Code)//从文本文件中读取哈夫曼编码，并字符编码转为哈夫曼编码 { FILE*fp; charstr[215],ch[50]={' '}; HuffmanCodeHC=NULL; inti=0,len,j,k; HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); if((fp=fopen(“Huffman.txt”,“rt”))==NULL){ printf(“CannotopenfileHuffman.txtanykeyexit!”); exit(1); } while(!feof(fp)){ memset(str,0,sizeof(str)); fgets(str,215,fp); if(str[0]==0)break; len=strlen(str); ch[i]=str[0]; HC[i]=(char*)malloc((len1)*sizeof(char*)); memcpy(HC[i],&str[1],len2); HC[i][len2]=0; i++; } fclose(fp); i=0;k=0; while(Char_Code[i]!=' '){ for(j=0;j — 4— 教学过程及内容 free(HC); } intmain(){ HuffmanTreeHT=NULL; HuffmanCodeHC=NULL; unsignedint*w=NULL,i,n; charch[50]={' '},Huffman_Code[1024]={' '}; charChar_Code[]=“THISPROGRAMISMYFAVORITE”; printf(“Inputn:n”); scanf(“%d”,&n); w=(unsignedint*)malloc((n+1)*sizeof(unsignedint)); w[0]=0; printf(“Enterweight,character:n”); for(i=1;i<=n;i++){ printf(“w[%d],ch[%d]=”,i,i); scanf(“%d,%c”,&w[i],&ch[i]); } HC=HuffmanCoding(&HT,w,ch,n); Transcodeing(n,Char_Code,Huffman_Code); printf(“%sn”,Huffman_Code); free(w); return0; } — 5— 授课进度第14周，第26次课（2学时）授课题目 (教学章、节实验七图的遍历（Ⅰ）或主题) 授课日期 016年11月30日（11 2 月29日） .掌握图常用的邻接矩阵存储存储结构。1.掌握图的邻接矩阵存储结构上的两种遍历图的方法，即深度优先遍历和广度优 2 先遍历。 教学 目标 1.图的邻接存储结构。 教学 2.图的邻接矩阵存储结构下的两种遍历。重点 1.图的邻接矩阵存储结构下的两种遍历。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 图的邻接矩阵存储结构如下： #defineMaxVerNum100//设置邻接矩阵的最大顶点数 typedefcharVertexType;//设置图的顶点信息为字符 //设置边上权值为整型 typedefintEdgeType; typedefstruct{ VertexTypevexs[MaxVerNum];//图的顶点信息表 EdgeTypeedges[MaxVerNum][MaxVerNum];//图的邻接矩阵 //图的顶点数和边数 intn,e; MGraph;//图的邻接矩阵表示结构定义 } 1．键盘输入数据，建立一个图的邻接矩阵，并进行图的深度优先遍历和广度优先遍历。 二、实验指导 ．参考代码为： 1 # include //设置边上权值为整型 typedefintEdgeType; typedefstruct{ VertexTypevexs[MaxVerNum];//图的顶点信息表 EdgeTypeedges[MaxVerNum][MaxVerNum];//图的邻接矩阵 //图的顶点数和边数 intn,e; MGraph;//图的邻接矩阵表示结构定义 } typedefenum{FALSE,TRUE}boolean; booleanvisited[MaxVerNum];//顶点访问标记向量 structlinkqueuenode { intdata; structlinkqueuenode*next; } ; typedefstruct { structlinkqueuenode*front; structlinkqueuenode*rear; linkque; } voidInitQueue(linkque*q){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>next=NULL; — 1— 教学过程及内容 q>front=p;q>rear=p; } intQueueEmpty(linkqueq){ inti; if(q.front==q.rear)i=1; elsei=0; return(i); } voidEnQueue(linkque*q,intx){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>data=x;p>next=NULL; if(QueueEmpty(*q)){ q>front>next=p; q>rear=p; } else { q>rear>next=p; q>rear=p; } } intDeQueue(linkque*q,int*x){ structlinkqueuenode*p; if(QueueEmpty(*q)){printf(“queueisempty!n”);return(0);} else { p=q>front>next; *x=p>data; q>front>next=p>next; if(p>next==NULL) q>rear=q>front; free(p); return(1); } } linkqueQ; voidCreateMGraph(MGraph*g)//建立图g的邻接矩阵表示 — 2— 教学过程及内容 { inti,j,k,w; intflag; printf(“创建:有限图选0，无向图选1n”); scanf(“%d”,&flag); printf(“请输入顶点数和边数(格式为:顶点数,边数)n”); scanf(“%d,%d”,&g>n,&g>e); printf(“输入顶点的信息,每个顶点以回车作为结束:n”); for(i=0;i scanf(“%c”,&(g>vexs[i])); } /将邻接矩阵数组初始化 for(i=0;i //构造无向图 if(flag) g>edges[j][i]=w; } } voidDFSM(MGraph*g,inti)//对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索 { intj; printf(“%c”,g>vexs[i]);//访问序号为i的顶点 visited[i]=TRUE;//将序号为i的顶点设置访问过标记 for(j=0;j if((g>edges[i][j]!=0)&&(!visited[j]))//寻找序号为i的顶点的未访问过的邻接点 设序号为j)（{ printf(“>”); DFSM(g,j);//以序号为j的顶点为出发点进行深度优先搜索 } } voidDFSMTraverse(MGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start出发进行深度优先搜索 { inti; for(i=0;i — 3— 教学过程及内容 visited[i]=FALSE; DFSM(g,start);//对图进行深度优先搜索 printf(“n”); } voidBFSM(MGraph*g,intk)//对以邻接矩阵表示的图，以序号为k的顶点为出发点进行广度优先搜索 { inti,j; InitQueue(&Q); printf(“%c”,g>vexs[k]);//访问序号为k的顶点 visited[k]=TRUE;//将序号为k是结点设置为已访问过 EnQueue(&Q,k);//将序号为k的顶点入队 while(!QueueEmpty(Q)){ DeQueue(&Q,&i); for(j=0;j if((g>edges[i][j]!=0)&&(!visited[j])) //若序号为i的顶点有未访问过邻接点 { printf(“>%c”,g>vexs[j]);//访问序号为j的顶点 visited[j]=TRUE;//设置序号为j的顶点访问过标记 EnQueue(&Q,j);//将序号为j的顶点入队 } } } voidBFSMTraverse(MGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start开始进行广度优先搜索 { inti; for(i=0;i } voidmain(){ MGraph*g=(MGraph*)malloc(sizeof(MGraph));//申请图g的邻接矩阵表示空间 CreateMGraph(g);//建立图 DFSMTraverse(g,0);//从顶点0出发进行图的深度搜索遍历 BFSMTraverse(g,0);//从顶点0出发进行图的广度搜索遍历 } — 4— 授课进度 授课题目 第15周，第28次课（2学时）授课日期 016年12月7日（12 2 月6日） (教学章、节实验七图的遍历（Ⅱ）或主题).掌握图常用的邻接表存储存储结构。1.掌握图的邻接表存储结构上的两种遍历图的方法，即深度优先遍历和广度优先 2 遍历。 教学 目标 1.图的邻接表存储结构。 教学 2.图的邻接表存储结构下的两种遍历。重点 1.图的邻接表存储结构下的两种遍历。 教学 难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 教学过程及内容 一、实验内容 图的邻接表存储结构如下： #defineMaxVerNum100//定义最大顶点数为100 typedefcharVertexType;//设置图的顶点信息为字符 //边表表结点结构 typedefstructNode{ intadjvex; structNode*next; } EdgeNode; typedefstructVNode{//顶点结点结构 VertexTypevertex; EdgeNode*firstedge; } VNode,AdjList[MaxVerNum]; typedefstruct{ AdjListadjlist; //顶点数和边数 intn,e; intkind; //有向图为0，无向图为1 } ALGraph; 1．键盘输入数据，建立一个图的邻接邻接表，并进行图的深度优先遍历和广度优先遍 历。 二、实验指导 1．参考代码为： # include //边表表结点结构 typedefstructNode{ intadjvex; structNode*next; } EdgeNode; typedefstructVNode{//顶点结点结构 VertexTypevertex; EdgeNode*firstedge; } VNode,AdjList[MaxVerNum]; typedefstruct{ AdjListadjlist; //顶点数和边数 intn,e; intkind; //有向图为0，无向图为1 } ALGraph; typedefenum{FALSE,TRUE}boolean; booleanvisited[MaxVerNum];//顶点访问标记向量 — 1— 教学过程及内容 structlinkqueuenode { intdata; structlinkqueuenode*next; } ; typedefstruct { structlinkqueuenode*front; structlinkqueuenode*rear; linkque; } voidInitQueue(linkque*q){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>next=NULL; q>front=p;q>rear=p; } intQueueEmpty(linkqueq){ inti; if(q.front==q.rear)i=1; elsei=0; return(i); } voidEnQueue(linkque*q,intx){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>data=x;p>next=NULL; if(QueueEmpty(*q)){ q>front>next=p; q>rear=p; } else { q>rear>next=p; q>rear=p; } } intDeQueue(linkque*q,int*x){ — 2— 教学过程及内容 structlinkqueuenode*p; if(QueueEmpty(*q)){printf(“queueisempty!n”);return(0);} else { p=q>front>next; *x=p>data; q>front>next=p>next; if(p>next==NULL) q>rear=q>front; free(p); return(1); } } linkqueQ; voidCreateALGraph(ALGraph*g)//建立图的邻接矩阵表示 { inti,j,k; intflag; EdgeNode*s1,*s2; printf(“创建:有向图选0，无向图选1n”); scanf(“%d”,&flag); printf(“请输入顶点数和边数(格式为:顶点数,边数)n”); g>kind=flag; scanf(“%d,%d”,&g>n,&g>e);//输入图的顶点数和边数 printf(“输入顶点的信息,每个顶点以回车作为结束:n”); for(i=0;i s1=(EdgeNode*)malloc(sizeof(EdgeNode)); s1>adjvex=j; s1>next=g>adjlist[i].firstedge; g>adjlist[i].firstedge=s1; } } — 3— 教学过程及内容 else { //无向图 for(k=1;k<=g>e;k++){ scanf(“%d,%d”,&i,&j); s1=(EdgeNode*)malloc(sizeof(EdgeNode)); s1>adjvex=j; s2=(EdgeNode*)malloc(sizeof(EdgeNode)); s2>adjvex=i; s1>next=g>adjlist[i].firstedge; g>adjlist[i].firstedge=s1; s2>next=g>adjlist[j].firstedge; g>adjlist[j].firstedge=s2; } } } voidDFSAL(ALGraph*g,inti)//对以邻接表表示的图，以序号为i的顶点为出发点进行深度优先搜索 { EdgeNode*p; printf(“%c”,g>adjlist[i].vertex);//访问序号为i的顶点 visited[i]=TRUE;//将序号为i的顶点设置访问过标记 p=g>adjlist[i].firstedge; while(p){ if(!visited[p>adjvex]){ printf(“>”);DFSAL(g,p>adjvex); } p=p>next; } } voidDFSALTraverse(ALGraph*g,intstart)//对以邻接表表示的图，从最初顶点start出发进行深度优先搜索 { inti; for(i=0;i visited[i]=FALSE; DFSAL(g,start);//对图进行深度优先搜索 printf(“n”); } voidBFSAL(ALGraph*g,intk)//对以邻接表表示的图，以序号为i的顶点为出发点进行广度优先搜索 { inti; — 4— 教学过程及内容 EdgeNode*p; InitQueue(&Q); printf(“%c”,g>adjlist[k].vertex);//访问序号为k的顶点 visited[k]=TRUE;//将序号为k是结点设置为已访问过 EnQueue(&Q,k);//将序号为k的顶点入队 while(!QueueEmpty(Q)){ DeQueue(&Q,&i); p=g>adjlist[i].firstedge; while(p){ if(!visited[p>adjvex]){ printf(“>%c”,g>adjlist[p>adjvex].vertex);//访问p>adjvex的顶点 visited[p>adjvex]=TRUE; EnQueue(&Q,p>adjvex); } p=p>next; } } } voidBFSALTraverse(ALGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start出发进行广度优先搜索 { inti; for(i=0;i DFSALTraverse(g,0);//从顶点0出发进行深度优先搜索 BFSALTraverse(g,0);//从顶点0出发进行广度优先搜索 } — 5— 授课进度第16周，第30次课（2学时）授课题目 (教学章、节实验八查找 或主题) 授课日期 016年12月14日（12 2 月13日） ．掌握顺序查找、折半查找算法的思想及程序实现。1 2 ．掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散 3 教学 目标 列表的查找、建立。 ．掌握顺序查找、折半查找算法的思想及程序实现。1 ．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散 教学 2 重点 列表的查找、建立。 1.掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散 教学 列表的查找、建立。难点 请选择你授课时所采用的教学方法（在括号中画“√”）： 讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学 谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习 方法 法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学 实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本 手段 ﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业 [ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）： 参考 电出版社，2014.文献 数据结构教案 实验一：线性表的顺序表示与实现 实验学时：2学时 一．实验目的： 1．掌握线性表的顺序存储结构； 2．掌握在顺序表上进行的插入、删除、查找、修改等操作。 二．实验内容： 1．分别建立顺序表，并输入初始数据； 2．对顺序表分别编写插入、删除、查找、修改等函数。 三．实验重点： 顺序表的建立及操作。 四．实验要求： 1．用C语言编写程序源代码； 2．要分别完成建立、插入、删除、查找、修改五种功能。3．源程序必须编译调试成功，独立完成。 五． 实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤： 顺序表 ： 1．定义头文件和顺序表的存储结构类型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include return overflow;l->length=0;l->listsize=list_init_size;return ok;} 3．编写对顺序表进行插入操作的函数： status listinsert(sqlist *l,int i,elemtype e){ elemtype *newbase,*q,*p;if(i<1||i>listlength(*l)+1) return error;if(l->length==l->listsize) { newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype)); if(!newbase) return overflow; l->listsize+=listincrement; } q=&(l->elem[i-1]);for(p=&(l->elem[l->length])-1;p>=q;--p) *(p+1)=*p;*q=e;++l->length;return ok;} 4．编写对顺序表进行删除操作的函数： status listdelete(sqlist *l,int i,elemtype *e){ elemtype *p,*q;if(i<1||i>l->length) return error;p=&(l->elem[i-1]);*e=*p;q=l->elem+l->length-1;for(++p;p<=q;++p) *(p-1)=*p;--l->length;return ok;} 5．编写对顺序表进行查找操作的函数： status getelem(sqlist l,int i,elemtype *e){ if(i<1||i>listlength(l))return error;*e=l.elem[i-1];return ok;} 6．编写对顺序表进行修改操作的函数： status locateelem(sqlist l,elemtype e){ int i;for(i=0;i if(l.elem[i]==e) return i+1;return 0;} 7．编写实现两个线性表的归并操作的函数 void mergelist(sqlist la,sqlist lb,sqlist *lc){ int i,j,k;int la_len,lb_len;elemtype ai,bj;i=j=1;k=0;listinit(lc);la_len=listlength(la);lb_len=listlength(lb);while(i<=la_len&&j<=lb_len){ getelem(la,i,&ai);getelem(lb,j,&bj);if(ai<=bj) { listinsert(lc,++k,ai); ++i; } else { listinsert(lc,++k,bj); ++j; } } while(i<=la_len){ getelem(la,i++,&ai);listinsert(lc,++k,ai);} while(j<=lb_len) { getelem(lb,j++,&bj);listinsert(lc,++k,bj); } } 8．销毁线性表、清空线性表、判空、求表长等 status destroylist(sqlist *l){ if(l->elem)free(l->elem),l->elem=null;return ok;} status clearlist(sqlist *l){ l->length=0;return ok;} status listempty(sqlist l){ return(l.length==0);} status listlength(sqlist l){ return l.length;} 9．打印线性表 void print(sqlist l){ int i;printf(“nlist: ”);for(i=0;i 10． 编写主函数 void main(){ int i;int n;elemtype a;sqlist l,la,lb,lc;clrscr();listinit(&l);listinit(&la);listinit(&lb); printf(“please input list number”);scanf(“%d”,&n);printf(“n”);for(i=0;i scanf(“%d”,&a); listinsert(&l,i+1,a);} print(l);printf(“nlist length:%d”,listlength(l)); getelem(l,4,&a);printf(“ngetelem(l,4,&a),%d”,a); listdelete(&l,3,&a);printf(“nlistdelete(&l,3,&a),%d”,a);print(l); printf(“ninput list la”); for(i=0;i<5;i++){ scanf(“%d”,&a); listinsert(&la,i+1,a);} printf(“ninput list lb”);for(i=0;i<7;i++){ scanf(“%d”,&a); listinsert(&lb,i+1,a);} mergelist(la,lb,&lc);print(la);print(lb);print(lc);} 实验二：链表 实验学时：2学时 一．实验目的： 11． 掌握单、双向链表的存储结构； 12． 掌握在单、双向链表上进行的插入、删除、查找、修改等操作。 二．实验内容： 4．分别建立单、双向链表，并输入初始数据； 5．对两种单、双向链表分别编写插入、删除、查找、修改等函数。 三．实验重点： 单向链表的建立及操作。 四．实验要求： 1．用C语言编写程序源代码； 2．要分别完成建立、插入、删除、查找、修改五种功能。6．源程序必须编译调试成功，独立完成。 五． 实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤： 单链表 ： 1．定义头文件和单链表的结构体类型 #include int data; struct LNode *next;}LNode, *LinkList; 2．编写构造单链表的函数 void InitList_L(LinkList L){ LinkList p,q;int i,b,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);do { scanf(“%d”,&b);q=(LinkList)malloc(sizeof(LNode));q->data=b;p->next=q;p=p->next;j+=1;} while(b!=-1);p->next=NULL;p=L;for(i=1;i 13． 编写对单链表进行插入操作的函数： void ListInsert_L(LinkList L,int r,int e){ LinkList p,s; int q=1,i,j=0; p=L; while(q>=1&&q<=r-1) { p=p->next; ++q; } s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; p=L;while(p->next!=NULL) { p=p->next; j+=1; } p=L; printf(“插入一个新结点后的链表为：n”); for(i=1;i { p=p->next; printf(“%dn”,p->data); } printf(“插入一个新结点后链表结点的个数为:%dn”,j-1); printf(“***************************************n”);} 14． 编写对单链表进行删除操作的函数： void ListDelete_L(LinkList L,int r){ LinkList p,s;int q=1,i,e;p=L;if(r<1||r>k){ printf(“删除的位置不正确n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;++q;} s=p->next;p->next=s->next;e=s->data;k=k-1;printf(“删除的结点的值为：%dn”,e);printf(“删除一个结点后的链表为：n”);p=L;for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“删除一个结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} } 15． 编写对单链表进行查找操作的函数： void GetElem_L(LinkList L,int r){ LinkList p;int q=1,e;p=L;if(r<1||r>k){ printf(“第%d个元素不存在n”,r);printf(“***************************************n”);} else { while(q>=1&&q<=r){ p=p->next;q++;} e=p->data;printf(“第%d个元素的值为:n%dn”,r,e);printf(“***************************************n”);} } 16． 编写对单链表进行修改操作的函数： void UpdateElem_L(LinkList L,int r){ LinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“请输入修改后该结点的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d个元素的值后链表为：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 17． 编写主函数 void main(){ int m,n=0;LinkList l;l=(LinkList)malloc(sizeof(LNode));InitList_L(l);while(n!=-1){ printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”);printf(“***************************************n”);scanf(“%d”,&n);printf(“***************************************n”);switch(n){ case 1: printf(“请输入在第几个结点之前插入新结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListInsert_L(l,m);break;case 2: printf(“请输入删除第几个结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListDelete_L(l,m);break;case 3: printf(“请输入查找第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);GetElem_L(l,m);break;case 4: printf(“请输入修改第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);UpdateElem_L(l,m);break;} } printf(“操作结束!n”);} 双向链表 1．定义头文件和双向链表的结构体类型 #include 2．编写构造双向链表的函数 void InitList_DuL(DuLinkList L){ DuLinkList p,q;int i,b=0,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);while(b!=-1){ scanf(“%d”,&b);q=(DuLinkList)malloc(sizeof(DuLNode));q->data=b;p->next=q;q->prior=p;p=p->next;j+=1;} k=j-1;p->next=NULL;p=L;printf(“***************************************n”);printf(“创建的双向链表为：n”);for(i=1;i 3．对双向链表进行插入操作的函数 void ListInsert_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,n;p=L;if(r<1||r>k){ printf(“插入的位置不正确!n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;q++;} s=(DuLinkList)malloc(sizeof(DuLNode));printf(“请输入插入的结点的值：n”);scanf(“%d”,&n);printf(“***************************************n”);s->data=n;s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;k=k+1;p=L;printf(“插入一个新结点后的链表为：n”);for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“插入一个新结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} } 7． 写对双向链表进行删除操作的函数 void ListDelete_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,e;p=L;if(r<1||r>k) { printf(“删除的位置不正确n”); printf(“***************************************n”);} else { while(q>=1&&q<=r-1) { p=p->next; ++q; } s=p->next; p->next=s->next; s->next->prior=p; e=s->data; k=k-1; printf(“删除的结点的值为：%dn”,e); printf(“删除一个结点后的链表为：n”); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“删除一个结点后链表结点的个数为:%dn”,k); printf(“***************************************n”);} } 8． 编写对双向链表进行查找操作的函数 void GetElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,e;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } e=p->data; printf(“第%d个元素的值为:n%dn”,r,e); printf(“***************************************n”);} } 9． 编写对双向链表进行修改操作的函数 void UpdateElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“请输入修改后该结点的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d个元素的值后链表为：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 10． 编写主函数 void main(){ int m,n=0;DuLinkList l;l=(DuLinkList)malloc(sizeof(DuLNode));InitList_DuL(l);while(n!=-1){ printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”); printf(“***************************************n”); scanf(“%d”,&n); printf(“***************************************n”); switch(n) { case 1: printf(“请输入在第几个结点之前插入新结点：n”); scanf(“%d”,&m); printf(“***************************************n”); ListInsert_DuL(l,m); break; case 2: printf(“请输入删除第几个结点：n”); scanf(“%d”,&m); printf(“***************************************n”); ListDelete_DuL(l,m); break; case 3: printf(“请输入查找第几个结点的值：n”); scanf(“%d”,&m); printf(“***************************************n”); GetElem_DuL(l,m); break; case 4: printf(“请输入修改第几个结点的值：n”); scanf(“%d”,&m); printf(“***************************************n”); UpdateElem_DuL(l,m); break; } } printf(“操作结束!n”);} 实验三：栈、队列 实验学时：2学时 一．实验目的： 1．掌握栈、队列的存储结构； 2．掌握在栈、队列上进行的各种操作。 二．实验内容： 1．编写模拟Hanoi塔函数计算的程序，掌握栈在递归中的作用； 2．编写循环队列的进队、出队、初始化等函数。（2选1） 三．实验重点： 对栈、队列的存储结构的理解。 四．实验难点： 循环队列操作函数的编写。 五．实验要求： 1．用C语言编写程序源代码； 2．源程序必须编译调试成功，独立完成。 六．实验器材： 一个装有C语言编译环境的计算机。 七．实验步骤： Hanoi塔程序的编写 1．定义头文件： #include 2．编写move函数： void move(char x,char y){ printf(“%c-->%cn”,x,y);} 3．编写Hanoi塔函数： void hanoi(int n,char a,char b,char c){ if(n==1) move(a,c); else { hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); } } 4．编写主函数： void main(){ int m;printf(“请输入需要移动的盘子数：n”);scanf(“%d”,&m);printf(“%d个盘子通过B从A移动到C的过程如下：n”,m);hanoi(m,'A','B','C');} 循环队列操作函数的编写 1．定义头文件和结构体类型等： #include int front;//顺序存储，即地址，所以用下标表示元素，front是第一个元 //的下标 int rear;//rear是最后一个元素的下标 }SqQueue; 2．编写初始化函数： int InitQueue(SqQueue &Q){ Q.base=(int*)malloc(MAXQSIZE*sizeof(int));if(!Q.base) return 0; else { Q.front=0; Q.rear=0; return 1; } } 3．编写进队函数： void EnQueue(SqQueue &Q,char e){ if((Q.rear+1)%MAXQSIZE==Q.front) printf(“队列满”);else { Q.base[Q.rear]=e;//Q.base表示数组的地址也即数组名；Q.rear表示引用结//构体类型变量Q中的一个成员rear ,也即是数组中下标为rear的元素 Q.rear=(Q.rear+1)%MAXQSIZE; } } 4．编写出队函数： void DeQueue(SqQueue &Q){ char e;if(Q.front==Q.rear) printf(“队列空n”);else { e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } } 5．编写显示功能函数： void Display(SqQueue Q){ int i; if(Q.front==Q.rear) printf(“队列空n”);else { i=Q.front; printf(“队列中的元素如下:”); do { printf(“%c”,Q.base[i]); i=(i+1)%MAXQSIZE; } while(i!=Q.rear); } } 6．编写主函数： void main(){ SqQueue Q; char r; int i=0; InitQueue(Q); while(i!=-1) { printf(“请选择对队列进行何种操作:n 输入1表示进行入队操作n 输入2表示进行出队操作n 输入-1表示不进行任何操作n”); printf(“********************************************n”); scanf(“%d”,&i); printf(“********************************************n”); switch(i) { case 1: printf(“请输入要入队的元素的值,输入#表示结束:n”); printf(“****************************************n”); scanf(“%c”,&r); while(r!='#') { EnQueue(Q,r); scanf(“%c”,&r); } printf(“****************************************n”); Display(Q); printf(“****************************************n”); break; case 2: DeQueue(Q); Display(Q); break; } } } 实验四：树 实验学时：2学时 一．实验目的： 1．掌握二叉树的存储结构； 2．掌握在二叉树上进行的各种操作。 二．实验内容与基本要求： 1．编写二叉树的各种操作函数，包括建立、初始化、添加、删除、查找等； 2．编写对二叉树进行三种遍历的函数； 3．编写8皇后的模拟计算程序。 (3选2) 三．实验重点： 二叉树的各种操作及遍历的函数。 四．实验难点： 二叉树的三种遍历函数的编写。 五．实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤： 1．建立、初始化二叉树； struct tree //声明树的结构 { struct tree *left; int data; struct tree *right;};typedef struct tree treenode;typedef treenode *b_tree; //声明二叉树链表 //插入二叉树的节点 b_tree insert_node(b_tree root,int node){ b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_tree)malloc(sizeof(treenode)); //建立新节点的内存空间 newnode->data=node; newnode->right=NULL; newnode->left=NULL;if(root=NULL) return newnode; else { currentnode=root; while(currentnode!=NULL) { parentnode=currentnode; if(currentnode->data>node) currentnode=currentnode->left; else currentnode=currentnode->right; } if(parentnode->data>node) parentnode->left=newnode; else parentnode->right=newnode; return root;} } // 建立二叉树 b_tree create_btree(int *data,int len){ b_tree root=NULL; int i; for(i=0;i root=insert_node(root,data[i]);//调用insert_node函数，参数为空指针 //root和数组中元素data[i]，//insert_node函数的返回值赋给 //create_btree函数中定义root，并作为 //create_btree函数的返回值返回 return root;//返回值为root } 2．编写对二叉树进行的各种操作的函数，包括、添加、删除、查找等； 3．编写对二叉树进行三种遍历的函数； //二叉树先序遍历 void preorder(b_tree point){ if(point!=NULL) { preorder(point->left);//递归 printf(“%d”,point->data); preorder(point->right);//递归 } } //二叉树中序遍历 void inorder(b_tree point){ if(point!=NULL) { inorder(point->left);//递归 printf(“%d”,point->data); inorder(point->right);//递归 } } //二叉树后序遍历 void postorder(b_tree point){ if(point!=NULL) { postorder(point->left);//递归 printf(“%d”,point->data); postorder(point->right);//递归 } } //主程序 void main(){ b_tree root=NULL; int index; int value; int nodelist[20]; printf(“n please input the elements of binary tree(exit for 0):n”); index=0; //读取数值存到数组中 scanf(“%d”,&value); while(value!=0) { nodelist[index]=value; index=index+1; scanf(“%d”,&value); } //建立二叉树 root=create_btree(nodelist,index);//主函数调用创建函数，参数为数组名和 //长度，创建函数的返回值(返回的本身 //是root)赋给主函数中定义root，并作//为参数传给inorder函数 //先序遍历二叉树 printf(“nThe preorder traversal result is :”); preorder(root);//主函数调用inorder函数 printf(“n”);//中序遍历二叉树 printf(“nThe inorder traversal result is :”); inorder(root);//主函数调用inorder函数 printf(“n”);//后序遍历二叉树 printf(“nThe postorder traversal result is :”); postorder(root);//主函数调用inorder函数 printf(“n”);} 4．编写8皇后的模拟计算程序。实验五：图 实验学时：2学时 一．实验目的： 1．掌握图的存储结构； 2．掌握在图上进行的各种操作。 二．实验内容与基本要求： 1．编写图的各种操作函数，包括建立、初始化、添加、删除、查找等； 2．编写建立最小生成树的程序； 3．编写计算两点间最短路径的程序。（3选2） 三．实验重点： 掌握图的存储结构 四．实验难点： 编写计算两点间最短路径的程序 五．实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤 计算两点间最短路径： 1．义头文件等 #include #define max 10000//设定一个极大值 2．编写主函数 void main(){ int D[vex][vex][vex];//定义一个三维数组，用来一次一次的迭代，按 //FLOYD算法求出结点之间的最短路径 int arcs[vex][vex]={0,4,11,6,0,2,3,max,0};//邻接矩阵 int i,j,k; for(i=0;i //空间进行初始化 for(k=0;k for(i=0;i for(j=0;j if(D[k-1][i][j] D[k][i][j]=D[k-1][i][j];else D[k][i][j]=D[k-1][i][k]+D[k-1][k][j];//求出每次迭代最小 //值，最后一次即为两个顶点之间的最短路径 printf(“图的邻接矩阵为:n”);for(i=0;i for(j=0;j { printf(“%d ”,arcs[i][j]); } printf(“nn”); }//打印邻接矩阵 printf(“n”); printf(“表示各点间最短路径的矩阵为:n”); for(i=0;i { for(j=0;j { printf(“%d ”,D[vex-1][i][j]); } printf(“nn”); } } 实验六：排序 实验学时：2学时 一．实验目的： 1．掌握二叉查找树的性质及其相关的应用； 2．掌握插入排序、快速排序、选择排序、归并排序、基数排序的算法实现。 二．实验内容与基本要求： 1．编写二叉查找树的生成及应用程序； 2．编写插入排序、快速排序、选择排序、归并排序、基数排序的程序。 三．实验重点： 掌握各种排序算法的思想 四．实验器材： 一个装有C语言编译环境的计算机。 五．实验步骤 插入排序： #include printf(“Please input %d numbers:n”,N);for(i=0;i for(j=i-2;t printf(“%d ”,a[i]);printf(“n”);} 快速排序： #include while(a[i]<=A && i quickSort(a,0,i-1);if(i+1<9) quickSort(&a[i+1],i+1,9);} void main(){ int i,j,a[N]; printf(“Please input %d numbers:n”,N);for(i=0;i printf(“%d ”,a[i]);printf(“n”);} 冒泡排序： #include int a[10];int i,j,t; printf(“input 10 numbers :n”);for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(j=0;j<10;j++)for(i=0;i<10-j;i++)if(a[i]>a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<10;i++)printf(“%d ”,a[i]);printf(“n”);} 选择排序： #include int i,j,k,t,a[N]; printf(“Please input %d numbers:n”,N); for(i=0;i scanf(“%d”,&a[i]); for(i=0;i for(j=i;j if(a[j] { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } k=a[i]; a[i]=a[j]; a[j]=k;} printf(“the sorted numbers:n”); for(i=0;i printf(“%d ”,a[i]); printf(“n”);} 30 《数据结构》实验(训)指导书 电气与信息工程学院实验中心 前 言 《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。 一、实验目的、要求和任务 计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。 1.熟练掌握C语言的编辑、编译、调试程序。2.会书写类C语言的算法，并将算法转变为程序实现。 3.正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。4.有较强的逻辑分析能力。 5.针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。 6.学会分析研究计算机加工的数据结构的特性，以便为应用设计的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。 7.本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。 8.通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。 二、实验基本内容及学时分配 为了达到实验目的，本课程安排了4个实验单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及到几部分教学内容。总学时：8学时。 1、线性表（2学时） （1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点； （3）通过本次实验帮助学生提高C语言的编程能力（特别是函数参数、指针类型、链表的使用）。 2、数组和广义表（2学时）（1）掌握稀疏矩阵的压缩存储 （2）掌握稀疏矩阵的转置算法 3、树与二叉树（2学时） 常见的二叉树遍历算法有先序遍历，中序遍历和后序遍历算法。实现简单的先序遍历，中序遍历和后序遍历算法。 4、排序（2学时） 常见的内部排序算法，插入类排序算法，如直接插入排序和希尔排序；交换类排序算法，如冒泡排序和快速排序；选择类排序算法，如简单选择排序、树形选择类排序和堆排序。实冒泡排序或者直接插入排序算法。 三、说明 该课程采用理论与实践相结合的教学方法，集知识性与趣味性于一体，达到良好的教学效果。硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供电脑等设备。学生每次上机实验都必须遵守实验室的有关规定。 四、实验报告规范 实验报告的内容包括： 1、实验目的：说明实验所验证的知识点。 2、需求分析：以无歧义的陈述说明程序设计的任务、约束条件、输入输出要求、对功能的规定及模型。 3、逻辑设计：说明本程序中用到的所有抽象的数据类型的定义、主程序的流程以及各程序模块之间的层次调用关系。 4、详细设计：逻辑设计中定义的所有数据类型的实现，核心算法的设计描述、人机界面设计、函数之间调用关系的描述，主要功能的算法框架，测试数据设计。 5、测试分析：测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。 6、心得：软件设计与实现过程中的经验与体会，进一步改进的设想。 7、程序清单：源程序中应有足够的注释。如果提交源程序软盘，列出程序文件名。 五、如何提高上机效率 为了提高上机的效率，真正达到实验目的，要求同学做好实验前的准备工作，写好实验预习报告，即实验报告规范中的1）、2）、3）、4）部分，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对C语言程序不熟悉的同学，上机时最好带上C语言程序设计的教材，以备查阅。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。 实验室要求： 不能旷课，不迟到，不穿拖鞋进实验室 实验需预习报告（不能单纯抄写，预习程序代码）实验报告（总结，注释，实验结果） 目 录 实验一 线性表实验（设计性实验）..........................................4 实验二 数组和广义表实验（设计性实验）....................................6 实验三 树与二叉树（设计性实验）..........................................8 实验四 排序（设计性实验）................................................9 实验一 线性表实验（设计性实验） 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 五、实验提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node { elemtype data;//数据域 struct node *next;//指针域 }linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址： p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 六、实验总结与思考 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？ 实验二 数组和广义表实验（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.实现上三角阵的压缩存储。 2.用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.创建一个数组。2.输入数据 3.给定矩阵任一元素的下标，4.打印给定下标所对应的数据。5.创建三元组顺序表。a22 7.A输出对应的矩阵。 21五、实验提示 aaa6.输入矩阵中的数据。11a11a313233a21221.对于如下对称矩阵： Aaaa424341a31a32a331个位置，a21存入到第二个位置，将它们存入到一个线性数组中B，不存非零元素，a11存入到第a41a42aija44aij的位则aij能存到第几个位置，我们要以用梯形公式算面积。置是它上面的元素之和再加上左边的元素之和。 它上面的元素之和为((1+(i-1))×(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。 因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为 k=j(j-1)/2+i-1.所以存在关系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.结点结构 struct triple{ int i,j;//非零元的行下标和列下标 elemtype e;//非零元数据} 三元组顺序表存储类型 struct tsmatrix{ triple data[12500];aaa44 int mu,nu,tu;} 三元顺序表的转置 方法：(1)将矩阵行列互换，(2)重排矩阵 六、实验总结与思考 1.如何存储三对角阵？ 2.如何用行逻辑链接顺序表及十字链表存储稀疏矩阵？ 实验三 树与二叉树（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.练习二叉树的建立与存储 2.练习二叉树的遍历 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。 五、实验提示 建立二叉树的代码如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一个新结点q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新结点地址存入s指针数组中*/ if(i!= 1)/*i = 1，对应的结点是根结点*/ {j = i / 2;/*求双亲结点的编号j*/ if(i % 2 == 0)s[j]->lchild = q;/*q结点编号为偶数则挂在双亲结点j的左边*/ else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根结点地址*/ } 六、实验总结与思考 1.如何用孩子兄弟表示法存储树？ 2.熟悉及难赫夫曼树。 实验四 排序（设计性实验） 一、实验目的 1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3.了解各种方法的排序过程及其时间复杂度的分析方法。 二、实验内容 统计成绩 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2）按名次列出每个学生的姓名与分数。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.定义结构体。2.定义结构体数组。 3.定出主程序，对数据进行排序。 五、实验提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n请输入学生成绩: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、实验总结与思考 1.快速排序算法解决本问题。2.较各种排序算法的优缺点及。 3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。第四篇：数据结构实验课教案
第五篇：《数据结构》实验指导书
点击咨询 