数据结构课件1第5章数组和广义表幻灯片.ppt

国际教育学院 5.3 矩阵的压缩存储 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。 2. 什么样的矩阵能够压缩？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。 3. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%） 国际教育学院 三元组表:（(1,2,12), (1,3,9), (3,1,-3),(3,6,14), (4,3,24),(5,2,18), (6,1,15), (6,4,-7) ） 压缩存储原则：每个非零元的行下标、列下标和元素值 稀疏矩阵 国际教育学院 #define MAXSIZE 125000 //设非零元素最大个数125000 typedef struct{ int i; //元素行号 int j; //元素列号 ElemType e; //元素值 }Triple; typedef struct{ Triple data[MAXSIZE+1]; //三元组表 int mu; //矩阵总行数 int nu; //矩阵总列数 int tu; //矩阵中非零元素总个数 }TsMatrix; //一个结点的结构定义 三元组表的顺序存储表示 国际教育学院 typedef struct{ Triple data[MAXSIZE+1]; //非零三元组表 int rpos[MAXRC+1]; //各行第一个非零元素的位置表 int mu,nu,tu; //矩阵的行数，列数和非零元素个数 }RLSMatrix; 行逻辑链接的顺序存储表示 国际教育学院 row col val down right 1 1 3 4 1 8 2 2 5 2 3 4 ^ ^ ^ ^ ^ ^ ^ 链式存储结构（十字链表） 同一列中下一非零元素的指针 同一行中下一非零元素的指针 国际教育学院 十字链表的特点： ①每行非零元素通过right域链接成一个线性链表 ②每列非零元素通过down域链接成一个线性链表 则每个非零元素既是行链表中的一个结点；又是列链表中的一个结点，即呈十字链状。 方法：每个非0元素占用5个域 用途：方便稀疏矩阵的加减运算 链式存储结构（十字链表） row col val down right 国际教育学院 5.4 广义表的定义 广义表（列表）： n ( ? 0 )个表元素组成的有限序列， 记作LS = (a0, a1, a2, …, an-1) LS是表名，ai 是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。 n 为表的长度。n = 0 的广义表为空表。 国际教育学院 线性表的成分都是结构上不可分的单元素 广义表的成分可以是单元素，也可以是有结构的表 线性表是一种特殊的广义表 广义表不一定是线性表，也不一定是线性结构 广义表与线性表的区别？ 国际教育学院 广义表的抽象数据类型定义（教材P107-108 ） （1）求表头GetHead(L)：非空广义表的第一个元素，表头可以是一个单元素，也可以是一个子表 （2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表 国际教育学院 练习 A=( ) 　　　　　　　 GetHead和GetTail均无定义　　　　　　　 A=(a,b) 　　　　　　　 GetHead(A)=a GetTail(A)=(b) 　　　　　　　 A=(a) 　　　　　　　 GetHead(A)=a GetTail(A)=( ) 　　　　　　　 A=((a)) 　　　　　　　 GetHead(A)=(a) GetTail(A)=( ) 　　　　　　　 GetHead(GetTail(GetHead(GetTail(GetTail(A))))) 　　　　　　　 A=(a,b,(c,d),(e,(f,g))) 　　　　　　　 d 国际教育学院 1. GetTail【(b, k, p, h)】＝ ; 2. GetHead【( (a,b), (c,d) )】＝ ; 3. GetTail【( (a,b), (c,d) )】＝ ; 4. GetTail【 Get