内容发布更新时间 : 2024/5/5 6:24:48星期一 下面是文章的全部内容请认真阅读。

说明

每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。

1

实验一 线性表

一、 实验目的

1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算

3．能够利用线性表的基本运算完成线性表应用的运算

二、 实验内容

1．设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）

2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）

实验二 栈和队列

一、 实验目的

1．熟悉栈和队列的顺序和链式存储结构 2．掌握栈和队列的基本运算

3．能够利用栈和队列的基本运算完成栈和队列应用的运算

二、 实验内容

1．设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）

2．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。（文件夹：循环队列）

实验三 串

一、 实验目的

1． 熟悉串的顺序存储结构 2． 掌握串的基本运算及应用

二、 实验内容

1．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹：模式匹配）

2．编写一个算法void strDelete(seqstring*S,int pos,int len)，从串S中删除第pos个字符开始长度为len的子串。要求：1≤pos≤S->length-len+1（文件夹：删除子串）

2

实验四 数组

一、 实验目的

1．熟悉数组的结构 2．掌握矩阵的压缩存储

3．能够对数组和矩阵的压缩存储进行运算

二、 实验内容

1. 若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又

是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am

（文件夹：找马鞍点） ×n ，设计算法求出矩阵中所有马鞍点。

2. A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储

存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）

实验五 树

一、 实验目的

1．熟悉二叉树的链式存储结构

2．掌握二叉树的建立、深度优先递归遍历等算法 3．能够利用遍历算法实现一些应用

二、 实验内容

1．已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树

根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。（文件夹：交换左右子树）

2．采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。（文件夹：统计二叉树结点）

实验六 图

一、 实验目的

1．熟悉图的邻接矩阵和邻接表的存储结构 2．熟悉图的邻接矩阵和邻接表的建立算法 3．掌握图的遍历算法

二、 实验内容

1． 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）

3