数据结构与非数值算法基础
实验内容与上机指导
实验内容与上机指导
实验内容与上机指导
?实验 1 线性表及其运算
?实验 2 链表及其运算
?实验 3 二叉树的存储与遍历
?实验 4 图的存储与遍历
?实验 5 排序
?实验 6 查找
实验内容与上机指导
实验一 线性表及其运算
?一、实验目的
1,掌握线性表的逻辑特征
2,掌握线性表顺序存储结构的特点
3,熟练掌握线性表的基本运算
4,掌握栈和队列的特点及其运算
?二、实验内容
? 1,有一个已按递增次序排好序的线性表，今
输入一个数，要求按原来的排序规律将它插
入到线性表中。
实验内容与上机指导
[实验说明 ]
设已建立了一个上界为 11，元素个数为 10递增
排序的线性表,12,14,16,22,25,27,29，
32,43,70。若将待插入数据插入到合适位置，
首先将线性表的末尾元素与之比较。如果该元
素小于待插入元素，则直接将插入元素放到线
性表末端即可；否则从线性表头开始，找到其
插入的第 i个位置，将第 i个元素之后的所有元素
依次后移，最后将其插入第 i个位置，即完成了
所要求的操作。
实验内容与上机指导
? 2,利用一个堆栈，将一个线性表中的元素按
逆序重新存放。例如原来的顺序为 12,8,6，
4,2，要求改为 2,4,6,8,12。
[实验说明 ]
设原始数据已存入数组 a中，堆栈为 stack，已清
空，栈指针为 top，初始 top=0。首先从线性表第
1个元素开始，依次将其元素压入栈中，然后将
栈中元素依次弹出，重新放入数组 a中。
? 3,设数组 QU[0,mo-1]中存放循环队列的元
素。编写能向该循环队列插入一个结点数据
和删除一个结点数据的程序。
实验内容与上机指导
[实验说明 ]
(1) 队列的特点是在队尾入队，在队首出队。在
循环队列中，最初队列为空时队首指针 front和队
尾指针 rear都指向同一位置，当有元素入队时，
由于是循环的，所以 rear位置前移，即：
QU.rear = (QU.rear + 1) % mo
将插入元素放到 rear的新位置上。
(2)当有元素出队时，先将 front前移一个位置，
即：
QU.front = (QU.front + 1) % mo
将 front新位置的元素取出即可。
实验内容与上机指导
?三、实验要求
按要求编写实验程序，将实验程序上机调试运
行，给出输出的结果，并提交实验报告，写出
调试运行程序的分析和体会。
返回
实验内容与上机指导
实验 二 链表及其运算
?一、实验目的
1,掌握链表存储结构的特点
2,熟练掌握单链表的基本运算
3,掌握循环链表和双链表的特点和基本运算
?二、实验内容
? 1,建立一个单链表，显示链表中每个结点的
数据，并做删除和插入处理。
[实验说明 ]
(1) 建立链表是从无到有地建立起一个链表，即
一个一个地输入各结点数据，并建立起前后相
互链接的关系。
实验内容与上机指导
(2) 显示链表是将链表中各结点的数据依次显示。设
一个指针变量 p，先指向第 1个结点，显示 p所指的结
点，然后 p后一个结点再显示之，直到链表尾结点。
(3) 删除链表中的结点是从 p指向第 1个结点开始，检
查该结点的数据是否等于要删除的数据，如果相等就
将该结点删除，如不相等，则将 p后移一个结点，如
此进行下去，直到表尾为止。
(4) 插入结点是将一个结点插入到已知的链表中，且
保持结点的数据按原来的递增次序排列。
? 2,建立一个双链表，从链首开始，顺序显示链
表中的所有结点的数据，然后从链尾开始，反序
显示链表中所有结点的数据，最后将一个新的结
点插入到链表中。
实验内容与上机指导
[实验说明 ]
(1) 设双向链表的类型定义如下,
struct chn
{
struct chn *prior;
struct chn *next;
char data[100];
}
prior是指向直接前趋结点的指针,next是指向直接后
继结点的指针。结点的数据域为字符串。
实验内容与上机指导
(2) 建立双链表时，用到复制字符串库函数：
strcpy(char *destin,char *source);
该函数的功能是将字符串 source的内容复制到字符
型数组 destin中。在本程序中应用此函数是将输入
到字符数组 buf中的字符串复制到双链表一个结点
的数据域中。
(3) 通过向后指针 next，可以从链首向后顺序显示
链表中各结点的数据；通过向前指针 prior可以从链
尾反序显示链表中各结点的数据。
(4) 修改向前、向后指针可以实现从双链表中删除
和插入结点。设该双链表没有空表头结点，即其链
首结点的 prior域为 NULL，其链尾结点的 next域为
NULL。
实验内容与上机指导
? 3,建立如图所示的循环链表，编写一个程序
将所有箭头方向取反。
a 1 a 2 a n
head
实验内容与上机指导
[实验说明 ]
(1) 因为此链表为循环链表, 所以建此链表时最
后一个结点的指针域不能是 p->next=NULL,而
是指向第一个结点, 即 p->next=head;p=head;
(2) 为了将链表的所有箭头取反, 需从头开始扫
描单链表, 将第一个结点的 next域指向最后一个
结点, 将第二个结点的 next域指向第一个结点,
将第三个结点的 next域指向第二个结点, … 直到
最后一个结点用 head指向它 。
(3) 判定最后一个结点不能用 p->next=NULL,因
为是循环链表, 需用 q指向第 1个结点, 以 p!=q作
为条件 。 返回
实验内容与上机指导
实验三 二叉树的存储与遍历
?一、实验目的
1,掌握二叉树的非线性和递归性特点
2,掌握二叉树的存储结构
3,掌握二叉树的遍历（递归和非递归方式）操
作的实现方法
?二、实验内容
? 1,建立链式存储二叉树并遍历该二叉树。
[实验说明 ]
(1) 采用链式存储结构建立二叉树，并按先序输
入二叉树的结点序列。例如建立如图所示的二
叉树：
实验内容与上机指导
a
b
c
d
e
f
g
实验内容与上机指导
建立时按先序输入的结点序列为：
abc000de0f00g00
(2) 二叉树的建立, 先序遍历, 中序遍历, 后序
遍历均采用递归方式实现 。
(3) 主函数中设计一个选项菜单, 可选择执行建
立二叉树, 先序, 中序, 后序遍历二叉树 。
? 2,用栈实现二叉树先序遍历的非递归程序 。
实验内容与上机指导
[实验说明 ]
(1) 非递归遍历二叉树的程序中, 要用栈来保存
遍历经过的路径, 才能访问到二叉树的每一个
结点 。 先序遍历二叉树的顺序是, 根, 左,
右,, 所以, 在对二叉树进行先序遍历时, 从
二叉树的根结点开始, 在沿左子树向前走的过
程中, 将所遇结点进栈, 并退栈访问之, 并将
其左, 右子树进栈, 当前进到最左端无法再走
下去时, 则退回, 按退回的顺序进入其右子树
进行遍历, 如此重复直到树中的所有结点都访
问完毕为止 。
(2)上题所示的二叉树，先序非递归方式遍历该
二叉树时栈的变化如下：
实验内容与上机指导
初始栈
a 入栈
a t op =1
实验内容与上机指导
a 退栈并访问 a,其左、右子树 d, b 入栈
b
d
t o p =2
c
d
t o p =2
b 退栈并访问 b,其左子树 c 入栈
实验内容与上机指导
d t op =1
c 退栈并访问之
d 退栈并访问 d,其左、右子树 g, e 入栈
e
g
t o p =2
实验内容与上机指导
e 退栈并访问 e,其右子树 f 入栈
f
g
t o p =2
g t o p =1
f 退栈并访问 f
实验内容与上机指导
t o p = 0
g 退栈并访问 g, t o p = 0,结束
返回
实验内容与上机指导
实验 四 图的存储与遍历
?一、实验目的
1,掌握图的非线性结构的特点
2,掌握图的邻接矩阵和邻接表的存储结构
3,掌握基于图的两种常用存储结构下的深度优先
搜索（ DFS）和广度优先搜索操作的实现。
?二、实验内容
? 1,完成无向图用邻接矩阵存储的深度优先搜
索程序。
实验内容与上机指导
[实验说明 ]
(1)用邻接矩阵表示图，除了要用一个二维数组存
储用于表示顶点间相邻关系的邻接矩阵外，还需
用一个一维数组来存储顶点信息，另外还有图的
顶点数和边数。为了反映上面图的全面信息，可
以采用以下结构：
#define MAX 10
typedef struct
{
char vexs[MAX];
int edges[MAX][MAX];
int n,e;
}MGraph;
实验内容与上机指导
(2) 图的深度优先搜索可以通过递归调用来实现，
其调用过程可描述如下：
DFS (Vi)
访问 Vi结点；
visited[i]=true;
对所有与 Vi相邻接的顶点 j
if visited[j]=False then DFS(Vj);
visited[]是一个布尔型标志数组，用以标志一个结
点是否被访问过。
实验内容与上机指导
? 2,完成无向图用邻接表的广度优先搜索程序。
[实验说明 ]
(1) 广度优先搜索是一种分层的搜索过程，当访
问图中某指定起始点后，由 V0出发访问与它相
邻的所有顶点 w1,w2…,然后再访问 w1,w2…
等各顶点的相邻顶点，如此做下去，直到所有的
顶点均被访问过为止。当然访问过程中已被访问
过的顶点则不重复访问。为此程序中设置了一个
访问标志数组 visited[MAX]。
(2) 广度优先搜索不是递归过程，过程中需借一
个队列 Q[MAX]，其队头指针为 front，队首指针
为 rear。
返回
实验内容与上机指导
实验五 排序
?一、实验目的
1,掌握常用排序方法的基本思想及其实现技术
2,了解各种排序方法的优缺点和适用范围
?二、实验内容
?实现冒泡、直接插入、选择排序和快速排序，
并比较各种排序算法的运行速度。
[实验说明 ]
(1) 采用顺序表存放待排序的记录，设关键字类
型为整型。
(2) 设计一个菜单，以菜单方式选择上述排序方
法。
(3) 程序执行时，能按趟输出排序的结果。 返回
实验内容与上机指导
实验六 查找
?一、实验目的
1,掌握常用查找方法的基本思想及其实现技术
2,了解各种查找方法的优缺点和适用范围
?二、实验内容
? 1,在有 n个元素的顺序表上进行顺序查找。
[实验说明 ]
(1) 建立有 n个元素的顺序表，数据元素为整型。
(2) 在该顺序表上查找某个数据，若查找成功输
出其位置，若查找失败输出失败信息。
实验内容与上机指导
? 2,在有 n个元素的有序顺序表上进行二分查找。
[实验说明 ]
(1) 建立有 n个元素的有序顺序表，数据元素为整
型。
(2) 在该顺序表上用二分法查找某个数据，若查
找成功输出其位置及查找次数，若查找失败输出
失败信息、比较次数和应插入的位置。
实验内容与上机指导
? 3,建立有 n个元素的二叉排序树，并在其上进
行查找。
[实验说明 ]
(1) 建立 n个元素的二叉树，以链式结构存储，数
据元素为整型。
(2) 在该二叉树上查找某种数据，若查找成功则
输出成功信息，若查找失败，则插入该数据，并
以中序遍历该树，输出结果。
返回
实验内容与上机指导
实验内容与上机指导
实验内容与上机指导
?实验 1 线性表及其运算
?实验 2 链表及其运算
?实验 3 二叉树的存储与遍历
?实验 4 图的存储与遍历
?实验 5 排序
?实验 6 查找
实验内容与上机指导
实验一 线性表及其运算
?一、实验目的
1,掌握线性表的逻辑特征
2,掌握线性表顺序存储结构的特点
3,熟练掌握线性表的基本运算
4,掌握栈和队列的特点及其运算
?二、实验内容
? 1,有一个已按递增次序排好序的线性表，今
输入一个数，要求按原来的排序规律将它插
入到线性表中。
实验内容与上机指导
[实验说明 ]
设已建立了一个上界为 11，元素个数为 10递增
排序的线性表,12,14,16,22,25,27,29，
32,43,70。若将待插入数据插入到合适位置，
首先将线性表的末尾元素与之比较。如果该元
素小于待插入元素，则直接将插入元素放到线
性表末端即可；否则从线性表头开始，找到其
插入的第 i个位置，将第 i个元素之后的所有元素
依次后移，最后将其插入第 i个位置，即完成了
所要求的操作。
实验内容与上机指导
? 2,利用一个堆栈，将一个线性表中的元素按
逆序重新存放。例如原来的顺序为 12,8,6，
4,2，要求改为 2,4,6,8,12。
[实验说明 ]
设原始数据已存入数组 a中，堆栈为 stack，已清
空，栈指针为 top，初始 top=0。首先从线性表第
1个元素开始，依次将其元素压入栈中，然后将
栈中元素依次弹出，重新放入数组 a中。
? 3,设数组 QU[0,mo-1]中存放循环队列的元
素。编写能向该循环队列插入一个结点数据
和删除一个结点数据的程序。
实验内容与上机指导
[实验说明 ]
(1) 队列的特点是在队尾入队，在队首出队。在
循环队列中，最初队列为空时队首指针 front和队
尾指针 rear都指向同一位置，当有元素入队时，
由于是循环的，所以 rear位置前移，即：
QU.rear = (QU.rear + 1) % mo
将插入元素放到 rear的新位置上。
(2)当有元素出队时，先将 front前移一个位置，
即：
QU.front = (QU.front + 1) % mo
将 front新位置的元素取出即可。
实验内容与上机指导
?三、实验要求
按要求编写实验程序，将实验程序上机调试运
行，给出输出的结果，并提交实验报告，写出
调试运行程序的分析和体会。
返回
实验内容与上机指导
实验 二 链表及其运算
?一、实验目的
1,掌握链表存储结构的特点
2,熟练掌握单链表的基本运算
3,掌握循环链表和双链表的特点和基本运算
?二、实验内容
? 1,建立一个单链表，显示链表中每个结点的
数据，并做删除和插入处理。
[实验说明 ]
(1) 建立链表是从无到有地建立起一个链表，即
一个一个地输入各结点数据，并建立起前后相
互链接的关系。
实验内容与上机指导
(2) 显示链表是将链表中各结点的数据依次显示。设
一个指针变量 p，先指向第 1个结点，显示 p所指的结
点，然后 p后一个结点再显示之，直到链表尾结点。
(3) 删除链表中的结点是从 p指向第 1个结点开始，检
查该结点的数据是否等于要删除的数据，如果相等就
将该结点删除，如不相等，则将 p后移一个结点，如
此进行下去，直到表尾为止。
(4) 插入结点是将一个结点插入到已知的链表中，且
保持结点的数据按原来的递增次序排列。
? 2,建立一个双链表，从链首开始，顺序显示链
表中的所有结点的数据，然后从链尾开始，反序
显示链表中所有结点的数据，最后将一个新的结
点插入到链表中。
实验内容与上机指导
[实验说明 ]
(1) 设双向链表的类型定义如下,
struct chn
{
struct chn *prior;
struct chn *next;
char data[100];
}
prior是指向直接前趋结点的指针,next是指向直接后
继结点的指针。结点的数据域为字符串。
实验内容与上机指导
(2) 建立双链表时，用到复制字符串库函数：
strcpy(char *destin,char *source);
该函数的功能是将字符串 source的内容复制到字符
型数组 destin中。在本程序中应用此函数是将输入
到字符数组 buf中的字符串复制到双链表一个结点
的数据域中。
(3) 通过向后指针 next，可以从链首向后顺序显示
链表中各结点的数据；通过向前指针 prior可以从链
尾反序显示链表中各结点的数据。
(4) 修改向前、向后指针可以实现从双链表中删除
和插入结点。设该双链表没有空表头结点，即其链
首结点的 prior域为 NULL，其链尾结点的 next域为
NULL。
实验内容与上机指导
? 3,建立如图所示的循环链表，编写一个程序
将所有箭头方向取反。
a 1 a 2 a n
head
实验内容与上机指导
[实验说明 ]
(1) 因为此链表为循环链表, 所以建此链表时最
后一个结点的指针域不能是 p->next=NULL,而
是指向第一个结点, 即 p->next=head;p=head;
(2) 为了将链表的所有箭头取反, 需从头开始扫
描单链表, 将第一个结点的 next域指向最后一个
结点, 将第二个结点的 next域指向第一个结点,
将第三个结点的 next域指向第二个结点, … 直到
最后一个结点用 head指向它 。
(3) 判定最后一个结点不能用 p->next=NULL,因
为是循环链表, 需用 q指向第 1个结点, 以 p!=q作
为条件 。 返回
实验内容与上机指导
实验三 二叉树的存储与遍历
?一、实验目的
1,掌握二叉树的非线性和递归性特点
2,掌握二叉树的存储结构
3,掌握二叉树的遍历（递归和非递归方式）操
作的实现方法
?二、实验内容
? 1,建立链式存储二叉树并遍历该二叉树。
[实验说明 ]
(1) 采用链式存储结构建立二叉树，并按先序输
入二叉树的结点序列。例如建立如图所示的二
叉树：
实验内容与上机指导
a
b
c
d
e
f
g
实验内容与上机指导
建立时按先序输入的结点序列为：
abc000de0f00g00
(2) 二叉树的建立, 先序遍历, 中序遍历, 后序
遍历均采用递归方式实现 。
(3) 主函数中设计一个选项菜单, 可选择执行建
立二叉树, 先序, 中序, 后序遍历二叉树 。
? 2,用栈实现二叉树先序遍历的非递归程序 。
实验内容与上机指导
[实验说明 ]
(1) 非递归遍历二叉树的程序中, 要用栈来保存
遍历经过的路径, 才能访问到二叉树的每一个
结点 。 先序遍历二叉树的顺序是, 根, 左,
右,, 所以, 在对二叉树进行先序遍历时, 从
二叉树的根结点开始, 在沿左子树向前走的过
程中, 将所遇结点进栈, 并退栈访问之, 并将
其左, 右子树进栈, 当前进到最左端无法再走
下去时, 则退回, 按退回的顺序进入其右子树
进行遍历, 如此重复直到树中的所有结点都访
问完毕为止 。
(2)上题所示的二叉树，先序非递归方式遍历该
二叉树时栈的变化如下：
实验内容与上机指导
初始栈
a 入栈
a t op =1
实验内容与上机指导
a 退栈并访问 a,其左、右子树 d, b 入栈
b
d
t o p =2
c
d
t o p =2
b 退栈并访问 b,其左子树 c 入栈
实验内容与上机指导
d t op =1
c 退栈并访问之
d 退栈并访问 d,其左、右子树 g, e 入栈
e
g
t o p =2
实验内容与上机指导
e 退栈并访问 e,其右子树 f 入栈
f
g
t o p =2
g t o p =1
f 退栈并访问 f
实验内容与上机指导
t o p = 0
g 退栈并访问 g, t o p = 0,结束
返回
实验内容与上机指导
实验 四 图的存储与遍历
?一、实验目的
1,掌握图的非线性结构的特点
2,掌握图的邻接矩阵和邻接表的存储结构
3,掌握基于图的两种常用存储结构下的深度优先
搜索（ DFS）和广度优先搜索操作的实现。
?二、实验内容
? 1,完成无向图用邻接矩阵存储的深度优先搜
索程序。
实验内容与上机指导
[实验说明 ]
(1)用邻接矩阵表示图，除了要用一个二维数组存
储用于表示顶点间相邻关系的邻接矩阵外，还需
用一个一维数组来存储顶点信息，另外还有图的
顶点数和边数。为了反映上面图的全面信息，可
以采用以下结构：
#define MAX 10
typedef struct
{
char vexs[MAX];
int edges[MAX][MAX];
int n,e;
}MGraph;
实验内容与上机指导
(2) 图的深度优先搜索可以通过递归调用来实现，
其调用过程可描述如下：
DFS (Vi)
访问 Vi结点；
visited[i]=true;
对所有与 Vi相邻接的顶点 j
if visited[j]=False then DFS(Vj);
visited[]是一个布尔型标志数组，用以标志一个结
点是否被访问过。
实验内容与上机指导
? 2,完成无向图用邻接表的广度优先搜索程序。
[实验说明 ]
(1) 广度优先搜索是一种分层的搜索过程，当访
问图中某指定起始点后，由 V0出发访问与它相
邻的所有顶点 w1,w2…,然后再访问 w1,w2…
等各顶点的相邻顶点，如此做下去，直到所有的
顶点均被访问过为止。当然访问过程中已被访问
过的顶点则不重复访问。为此程序中设置了一个
访问标志数组 visited[MAX]。
(2) 广度优先搜索不是递归过程，过程中需借一
个队列 Q[MAX]，其队头指针为 front，队首指针
为 rear。
返回
实验内容与上机指导
实验五 排序
?一、实验目的
1,掌握常用排序方法的基本思想及其实现技术
2,了解各种排序方法的优缺点和适用范围
?二、实验内容
?实现冒泡、直接插入、选择排序和快速排序，
并比较各种排序算法的运行速度。
[实验说明 ]
(1) 采用顺序表存放待排序的记录，设关键字类
型为整型。
(2) 设计一个菜单，以菜单方式选择上述排序方
法。
(3) 程序执行时，能按趟输出排序的结果。 返回
实验内容与上机指导
实验六 查找
?一、实验目的
1,掌握常用查找方法的基本思想及其实现技术
2,了解各种查找方法的优缺点和适用范围
?二、实验内容
? 1,在有 n个元素的顺序表上进行顺序查找。
[实验说明 ]
(1) 建立有 n个元素的顺序表，数据元素为整型。
(2) 在该顺序表上查找某个数据，若查找成功输
出其位置，若查找失败输出失败信息。
实验内容与上机指导
? 2,在有 n个元素的有序顺序表上进行二分查找。
[实验说明 ]
(1) 建立有 n个元素的有序顺序表，数据元素为整
型。
(2) 在该顺序表上用二分法查找某个数据，若查
找成功输出其位置及查找次数，若查找失败输出
失败信息、比较次数和应插入的位置。
实验内容与上机指导
? 3,建立有 n个元素的二叉排序树，并在其上进
行查找。
[实验说明 ]
(1) 建立 n个元素的二叉树，以链式结构存储，数
据元素为整型。
(2) 在该二叉树上查找某种数据，若查找成功则
输出成功信息，若查找失败，则插入该数据，并
以中序遍历该树，输出结果。
返回
