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

《《软件技术基础》实验指导.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、说明每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。1实验一线性表一、实验目的1．熟悉性表的序和式存构2．掌握性表的基本运算3．能利用性表的基本运算完成性表用的运算二、实验内容1．有一个性表E={e1,e2,⋯,en-1,en}，一个算法，将性表逆置，即使元素排列次序倒来，成逆性表E’={en,en-1,⋯,e2,e1}，要求逆性表占用原性表空，并且用序表和表两种方法表示，分用两个程序来完成。（文件：序表逆

2、置、表逆置）2．已知由不具有点的表表示的性表中，含有三字符的数据元素（字母、数字和其他字符），写算法构造三个以循表表示的性表，使每个表中只含有同一的字符，且利用原表中的点空，点可另辟空。（文件：分解表）实验二栈和队列一、实验目的1．熟悉和列的序和式存构2．掌握和列的基本运算3．能利用和列的基本运算完成和列用的运算二、实验内容1．表中存放有n个字符，写算法，判断字符串是否有中心称的关系，例如xyzzyx是中心称的字符串。（提示：将表中的一半字符先依次，然后依次出与表中的另一半字符行比。）（文件：判字符串中心称）2．假以数sequ[m]存放循列的元素，同量rear和quelen分指示循列中尾元

3、素的位置和内含元素的个数。写循列的入和出操作的算法。提示：空的条件：sq->quelen==0；的条件：sq->quelen==m。（文件：循列）实验三串一、实验目的1．熟悉串的序存构2．掌握串的基本运算及用二、实验内容1．串采用序存构，写朴素模式匹配算法，找在串中是否存在定的子串。（文件：模式匹配）2．若S是一个采用序构存的串，利用C的函数strlen和strcpy（或strncpy）写一算法voidSteDelete(char*S,intI,intm)，要求从S中除从第i个字符开始的m个字符。2若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开

4、始直至末尾的字符均删除。（文件夹：删除子串）实验四数组一、实验目的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．熟悉二

5、叉树的链式存储结构2．掌握二叉树的建立、深度优先递归遍历等算法3．能够利用遍历算法实现一些应用二、实验内容1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：交换左右子树）2．采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。（文件夹：统计二叉树结点）实验六图一、实验目的1．熟悉图的邻接矩阵和邻接表的存储结构2．熟悉图的邻接矩阵和邻接表的建立算法3．掌握图的遍历算法二、实验内容1．无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹

6、：无向图邻接矩阵）3ABCDEFGH实验七排序一、实验目的1．熟悉各种内部排序算法2．能够编写程序显示排序过程中各趟排序的结果3．能够编写一些排序的算法二、实验内容1．采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。（文件夹：希尔排序）2．编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。（文件夹：双向起泡排序）实验八查找一、实验目的1．熟悉线性表、二叉排序树和散列表的查找2．能够编写一些查找的算法二、实验内容1．18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、4

7、9、86、53，编写分块查找的算法进行查找。（文件夹：分块查找）2．编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，结点的数据域只存放正整数。（文件夹：判断二叉排序树）附录：原代码实验一：第1题（1）//顺序表逆置的程序代码#include#include//顺序表结构类型定义typedefchardatatype;constintmaxsize=1024