《软件技术基础》实验指导.docx

说明
每个实验题目含有一个 main 函数和一些函数，与实验题目相关
的基本运算的函数定义和 main 函数定义的代码在附录以及对应的文
件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目
要求设计算法，补充函数定义，然后对程序进行编译、调试。
实验一线性表
实验目的
.熟悉线性表的顺序和链式存储结构
.掌握线性表的基本运算
.能够利用线性表的基本运算完成线性表应用的运算
实验内容
.设有一个线性表 E={ei, e2,…，en-i, en},设计一个算法，将线性表逆置，即使元素排列次 序颠倒过来，成为逆线性表 E'={ en , en-i,…，e2 , ei },要求逆线性表占用原线性表空间， 并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 （文件夹：顺序表逆置、
单链表逆置）
.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字 和其他字符），试编写算法构造三个以循环链表表示的线性表， 使每个表中只含有同一类
的字符，且利用原表中的结点空间，头结点可另辟空间。 （文件夹:分解单链表）
实验二栈和队列
一、实验目的
.熟悉栈和队列的顺序和链式存储结构
.掌握栈和队列的基本运算
.能够利用栈和队列的基本运算完成栈和队列应用的运算
二、实验内容
.设单链表中存放有 n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如 xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出 栈与单链表中的另一半字符进行比较。 ）（文件夹：判字符串中心对称）
.假设以数组sequ[m]存放循环队列的元素，同时设变量 rear和quelen分别指示循环队列
中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。
提示：队空的条件：sq->quelen==0;队满的条件：sq->quelen==m。（文件夹：循环队列）
实验三串
一、 实验目的
.熟悉串的顺序存储结构
.掌握串的基本运算及应用
二、实验内容
.串采用顺序存储结构， 编写朴素模式匹配算法， 查找在串中是否存在给定的子串。 （文件
夹:模式匹配）
.若S是一个采用顺序结构存储的串，利用 C的库函数strlen和strcpy （或strncpy）编写 一算法void SteDelete（char*S,int I,int m），要求从S中删除从第i个字符开始的连续 m个字符。
若i>strlen（S）,则没有字符被删除；若 i+m >strlen（S）,则将S中从位置i开始直至末尾的
字符均删除。（文件夹：删除子串）
实验四数组
一、实验目的
.熟悉数组的结构
.掌握矩阵的压缩存储
.能够对数组和矩阵的压缩存储进行运算
二、实验内容
.若在矩阵Am"中存在一个元素 A[i][j],其满足A[i][j] 是第i行元素中最小值，且又 是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵 Am
xn ,设计算法求出矩阵中所有马鞍点。 （文件夹：找马鞍点）
. A和B是两个nxn阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储 存入一维数组 A和B,编写一个算法计算对称矩阵 A和B的乘积，结果存入二维数组
Co （文件夹：对称矩阵相乘）
实验五树
一、实验目的
.熟悉二叉树的链式存储结构
.掌握二叉树的建立、深度优先递归遍历等算法
.能够利用遍历算法实现一些应用
二、实验内容
.已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置， 即结点的左子树变为结点的右子树，右子树变为左子树。 （文件夹：交换左右子树）
.采用二叉链表结构存储一棵二叉树， 编写一个算法统计该二叉树中结点总数及叶子结点 总数。（文件夹：统计二叉树结点）
实验六图
一、实验目的
.熟悉图的邻接矩阵和邻接表的存储结构
.熟悉图的邻接矩阵和邻接表的建立算法
.掌握图的遍历算法
二、实验内容
.无向图采用邻接矩阵存储， 编写深度优先搜索遍历算法， 从不同的顶点出发对无向图进 行遍历。（文件夹：无向图邻接矩阵）
实验七排序
一、实验目的
.熟悉各种内部排序算法
.能够编写程序显示排序过程中各趟排序的结果
.能够编写一些排序的算法
二、实验内容
.采用希尔排序方法对顺序表中的证型数据进行排序， 设计希尔排序算法并显示每趟排序
的结果。（文件夹：希尔排序）
.编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序 的结果。（文件夹：双向起泡排序）
实验八查找
一、实验目的
.熟悉线性表、二叉排序树和散列表的查找