【精品】《软件技术基础》实验指导(含答案).doc

【精品】《软件技术基础》实验指导(含答案).doc说明每个实验题冃含有一个main函数和一些函数,与实验题冃相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出,供上机实验参考使用。对于每个题目,只需耍根据题目要求设计算法,补充函数定义,然后对程序进行编译、调试。实验一线性表一、实验目的熟悉线性农的顺序和链式存储结构掌握线性表的基本运算能够利用线性衣的基本运算完成线性农应用的运算二、实验内容设有一个线性表E={e1,e2,...,,en},设计一个算法,将线性表逆置,即使元素排列次序颠倒过来,成为逆线性表E'={Cn,en」,…,6,5},要求逆线性表占用原线性表空间,并且用顺序表和单链农两种方法农示,分别用两个程序來完成。(文件夹:顺序表逆置、单链农逆置)已知山不具有头结点的单链表衣示的线性衣中,含有三类字符的数据元素(字埒、数字和其他字符),试编写算法构造三个以循环链农表示的线性农,使每个表中只含有同一类的字符,U利用原表中的结点空I、可,头结点可另辟空间。(文件夹:分解单链农)实验二栈和队列一、 实验目的熟悉栈和队列的顺序和链式存储结构掌握栈和队列的基本运算能够利用栈和队列的基本运算完成栈和队列应用的运算二、 实验内容设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。(提示:将单链表中的一半字符先依次进栈,然后依次岀栈与单链表中的另一半字符进行比较。)(文件夹:判宁符串中心对称)假设以数组sequg]存放循环队列的元素,同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元索的个数。编写实现该循环队列的入队和出队操作的算法。提示:队空的条件:sq->quelen==O;队满的条件:sq->quelen==m0(文件夹:循坏队列)实验三串一、 实验目的熟悉串的顺序存储结构掌握串的基本运算及应用二、 实验内容串采用顺序存储结构,编写朴素模式匹配算法,杳找在串中是否存在给定的子串。(文件夹:模式匹配)若S是一*个采用顺序结构存储的串,利用C的库函数strlen和strcpy(或strncpy)编写-算法voidSteDelete(char*S,intI,intm),要求从S中删除从第i个字符开始的连续m个字符。若i^strlen(S),则没有字符被删除;若i+m^strlen(S),则将S中从位置i开始直至末尾的字符均删除。(文件夹:删除子串)实验四数组一、 实验目的熟悉数组的结构掌握矩阵的压缩存储能够対数组和矩阵的压缩存储进行运算二、 实验内容若在矩阵Amxn中存在一个元素A[i][j],其满足A是第i行元索中最小值,且又是第j列元素中最大值,则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵An】x„,设计算法求出矩阵中所有马鞍点。(文件夹:找弓輸点)A和B是两个nXn阶的对称矩阵,以行为主序输入対称矩阵的下三角元素,压缩存储存入一维数纽A和B,编写一个算法计算対称矩阵A和B的乘积,结果存入二维数组Co(文件夹:对称矩阵相乘)实验五树一、 实验目的熟悉二叉树的链式存储结构掌握二叉树的建立、深度优先递归遍丿力等算法能够利用遍历算法实现一些应用二、 实验内容已知二叉树采用二叉链表存储结构,如果左、右子树非空,口左子树根结点大于右子树根结点,则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。(文件夹:交换左右子树)采用二叉链表结构存储一棵二叉树,编写一个算法统计该二叉树中结点总数及叶子结点总数。(文件夹:统计一一叉树结点)实验六图一、 实验目的熟悉图的邻接矩阵和邻接表的存储结构熟悉图的邻接矩阵和邻接农的建立算法掌握图的遍历算法二、 实验内容无向图采用邻接矩阵存储,编写深度优先搜索遍历算法,从不同的顶点出发对无向图进行遍历。(文件夹:无向图邻接矩阵)A实验七排序一、实验目的熟悉各种内部排序算法能够编写程序显示排序过程屮乞趟排序的结果能够编写一些排序的算法二、实验内容采用希尔排序方法対顺序表中的证型数据进行排序,设计希尔排序算法并显示每趟排序的结果。(文件夹:希尔排序)编写一个双向起泡的排序算法,即在排序过程中交替改变扫描方向,同时显示各趟排序的结果。(文件夹:双向起泡排序)实验八查找一、实验目的熟悉线性表、二叉排序树和散列表的杳找能够编写一些查找的算法二、实验内容18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53,编写分块查找的算法进行查找°(文件夹:分块杳找)编写一个判别给定的二叉树是否为二叉排序树的算法,设二叉树以二叉链衣存储衣示,结点的数据域只存放止整数。(文件夹:判断一-叉排序树)附录:原代码实验一:第I题(1)〃顺序表逆置的程序代码#include<>#includ