实验题目 数组稀疏矩阵及广义表、递归 小组合作 否 姓 名 班级 学 号 一、实验目的 1、掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储 方法。掌握稀疏矩阵的各种存储结构以及基本运算实现算法。 2、掌握广义表的定义、存储结构和运算。 3、掌握递归算法的设计，递归算法到非递归算法的转换 二．实验环境 有 Visual C++6.0 的计算机和相关的硬件设备。 三、实验内容与步骤 1、数组的实验 按行优先顺序和按列优先顺序列出四维数组 A[2][2][2][2]所有元素在内存 中的存储次序。 首 先 新 建 一 工程 “ Myprogect01 ” 然 后在 工 程 的根 目 录下 将 tub.cpp 和 exam5-2.cpp 文件导入进去，然后在 Myprogect01.cpp 的头上输入 exam5-2.cpp， 在 main 函数中输入下列代码： josephus(8,4); 运行程序，截图如下图所示： 

2、稀疏矩阵广义表的实验 对于二维数组 A[m][n],其中 m≤80,n≤80,先读入 m 和 n,然后读该数组的全 部元素,对如三种情况分别编写相应函数: (1) 求数组 A 靠边元素之和; (2) 求从 A[0][0]开始的行、列互不相邻的各元素之和; (3) 当 m=n 时,分别求两条对角线上的元素之和,否则打印出 m≠n 的信息。 首 先 新 建 一 工程 “ Myprogect02 ” 然 后在 工 程 的根 目 录下 将 tub.cpp 和 exam5-3.cpp 文件导入进去，然后在 Myprogect01.cpp 的头上输入 exam5-3.cpp， 在 main 函数中输入下列代码： ElemType a[M][N]={{1,0,3},{0,2,0},{0,0,5}}; ElemType b[M][N]={{-1,0,2},{0,-2,0},{1,0,-5}}; TSMatrix x,y,z; CreatMat(x,a); MatAdd(x,y,z); printf("a 的三元组:\n");DispMat(x); printf("b 的三元组:\n");DispMat(y); printf("相加后的三元组:\n");DispMat(z); 运行程序，截图如下图所示： 

3、递归的实验 采用递归算法求解皇后问题：在 n×n 的方格棋盘上，放置 n 个皇后，要求 每个皇后不同行、不同列、不同左右对角线。 首先新建一工程“Myprogect03”然后在工程的根目录下将 exam6-5.cpp 文 件导入进去，然后在 Myprogect03.cpp 的头上输入 exam6-5.cpp，在 main 函数中 输入下列代码： place(1,4)； 运行程序，截图如下图所示： 

四、实验过程与分析 1、数组稀疏矩阵及广义表稀疏矩阵中非零元素的分布没有任何规律,所以在 存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏 矩阵中的每一个非零元素需由一个三元组(i,j,ai,j)惟一确定,稀疏矩阵中的所 有非零元素构成三元组线性表。 2、在递归的实验中对于尾递归和单向递归的算法,可用循环结构的算法替 代。自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递 归算法替代递归算法。利用栈保存参数,由于栈的后进先出特性吻合递归算法的 执行过程,因而可以用非递归算法替代递归算法 五、实验总结 1、在数组稀疏矩阵及广义表中掌握了数组和一般线性表之间的差异。数组 的顺序存储结构和元素地址计算方法； 掌握各种特殊矩阵如对称矩阵、上、下 三角矩阵和对角矩阵的压缩存储方法； 掌握稀疏矩阵的各种存储结构以及基本 运算实现算法。 2、递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问 题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的 方法是十分有效的；二是递归算法的时间效率通常比较差。因此,对求解某些问 题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递 归算法转换为非递归算法。 六、指导教师评语及成绩 基本完成实验要求，有完整的实验过程和分析，较好的达到了实验目的，在 调试过程中能认真处理调试出现的问题，达到了实验要求。但对实验的总结有些 笼统，没有针对性的分析，还需改进。