数据结构-ch02-1.pptVIP

同学分别实现，然后比较 同学分别实现，然后比较 同学分别实现，然后比较 2. 对称矩阵 2.4.3 矩阵的压缩存储 3. 对角矩阵 2.4.3 矩阵的压缩存储 二、稀疏矩阵 稀疏矩阵的特点： 非零元素较零元素少，且分布没有规律。 压缩存储方法： 1、三元组表 2、链式存储 3、十字链表 2.4.3 矩阵的压缩存储 结构设计 #define MAX_SIZE 100 /*最大的非零元素个数*/ typedef struct{ int row, col; /*行序号、列序号*/ ElemType value; /*非零元素值*/ }Triple_Item; typedef struct { Triple _Item data[MAXSIZE]; /*存储非零元素的一维数组*/ int mu, nu, tu; /*稀疏矩阵的总行数、列数及非零元素个数*/ } Triple_Table; /*三元组表的存储类型*/ 1. 三元组表 数据类型定义如下： #define Row 100 #define Col 100 typedef struct node{ int col; /*列坐标*/ ElemType value; /*值*/ struct node * next; /*本行下一个非零元指针*/ }SPNode,*SPNodePtr; typedef SPNodePtr LSPMatrix[Row]; 2. 链式存储 三元组线性表的链式存储结构称为十字链表 当矩阵非零元的位置或个数经常变化时,采用链式存储结构更为恰当 1). 链表结点结构 row域存储非零元素的行号， col域存储非零元素的列号， v域存储元素的值， 链域down:链接同一列中下一个非零元； 链域right:链接同一行中下一个非零元； 稀疏矩阵中同一列的非零元通过down链接成一个链表，同一行的非零元通过right链接成一个链表。 3. 十字链表 稀疏矩阵的十字链表 如何求转置矩阵？ M T 2.4.4数组的应用 用常规的二维数组表示时的算法 其时间复杂度为: O(mu×nu) for (col=1; col=nu; ++col) for (row=1; row=mu; ++row) T[col][row] = M[row][col]; 三元组求转置矩阵 M T 由M求其转置矩阵T，需做以下事情： ⑴ 矩阵的行列值互换，即若M为 m×n,则 T为 n×m ⑵ 每个三元组的行列号互换，即mij对应于 tji ⑶ M中三元组以原阵的行序，而T中三元组是以原阵的列序 方法(1) 算法思路： ①M的行、列转化成T的列、行； ②在M.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到T.data中即可。 产生T有以下两种方法： ⑴ 以原阵M的列序依次产生T中各三元组的值； ⑵ 以原阵M的行序产生转置后的三元组，并置入T中的恰当位置。 三元组表示实现转置矩阵 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 2 1 14 5 1 -5 2 2 -7 1 3 36 4 3 28 M T p q 板书和教材例子详细讲解 listsize 数据元素的容量 2.2.4 栈的应用 思考栈有哪些可能应用？ 1.将从键盘输入的字符序列逆置输出 2.检验表达式中的括号是否匹配 3.数制转换 4.表达式求值：计算器 5.栈与递归 …… 2.2.4 栈的应用—迷宫求解 思考栈有哪些可能应用？ 1.将从键盘输入的字符序列逆置输出 2.检验表达式中的括号是否匹配 3.数制转换 4.表达式求值：计算器 5.栈与递归 …… 2.2.4 栈的应用—迷宫求解 增量数组DeltaXY 在某一点（x，y），有8个可以探索的方向： x-1，y-1 x，y-1 x+1，y-1 x-1，y x，y x+1，y x-1，y+1 x，y+1 x+1，y+1 假设：从正东方向开始，沿顺时针方向依次进行探索，则增量数组DeltaXY 为： 用栈保留到达各点的坐标和到达时的探索方向 该栈中元素是由行号x、列号y和到达该点的探索方向d组成的三元组（x，y，d）， 其中x为到达点的横坐标或行号，y为到达点的纵坐标或列号，d为0—7中的一个数字，表示到达坐标为（x，y）的点的方向。 例如从（2，2）点沿东南方向到达（3，3）点时，在栈中要记录一个三元