数据结构 第五章-数组和广义表.ppt

第五章 数组和广义表;限制插入、删除位置线性表——具;线性表——具有相同类型的数据元;5.1 数组的定义5.3 ;5.1 数组的定义数组的定义数;a11 a12 … ;a11 a12 … ;数组的基本操作在数组中插入（或;数组的基本操作（存取）⑴ 读取;设一维数组的下标的范围为闭区间;常用的映射方法有两种：按行优先;l2h2 ;第l1行第l1+1行al1l2;例5.2.1：以矩阵形式表示的;行序为主序的存储示图：a00 ;列序为主序的存储示图：a00 ;特殊矩阵：包括对称矩阵、三角矩;3　6　4　7　86　2　8　;(a) 下三角矩阵 ;对于下三角中的元素aij（i≥;3 c　c　 c　 ;矩阵中任一元素aij在数组中的;矩阵中任一元素aij在数组中的;例5.3.1：假设以一维数组作;对角矩阵：所有非零元素都集中在;a00 a01 0　;按行存储 元素aij在一维数组;15 0 0 0;*typedef struc;三元组表：将稀疏矩阵的非零元素;采用顺序存储结构存储三元组表1;采用顺序存储结构存储三元组表 ;三元组顺序表——以顺序存储结构;例： 15 0 ;0 0 ;三元组顺序表操作——转置算法1;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;1. 设置转置后矩阵B的行数、;稀疏矩阵的转置 (算法5.1;三元组顺序表操作——转置算法1;分析：A中第0列的第一个非零元;row col ;引入两个数组作为辅助数据结构：;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;0 0 ;1. 设置转置后矩阵B的行数、;三元组顺序表操作——转置算法2;方法二：稀疏矩阵的压缩存储——;元素结点right——指向同一;稀疏矩阵的十字链表表示的示例5;需要辅助结点作链表的表头，同时;十字链表的类型定义typede;2 0 2∧M=3;一维数组具有线性表的结构，操作;n维数组中，每个数据元素对应n;5.4 广义表的类型定义ADT;广义表是递归定义的线性结构 ;广义表是一个多层次的线性结构例;广义表 LS = ( ?1, ;6) 任何一个非空广义表 L;? 结构的创建和销毁 I;*5.5 广义表的表示方法通常;1) 表头、表尾分析法:构造存;无标题;无标题;练习：L=(a, (x, y);1 1 ;例如:?ls((x)) LS;3 0 0 50 -1 ;2、画出矩阵X的三元???表和十字;3、广义表 F=((((a),;5、假设有二维数组elemty;1 1 ;1 1 ;第五章内容到此结束…;数组的类型定义ADT Arra;二维数组的定义:数据对象: ;基本操作：InitArray(;InitArray(A, n;DestroyArray(A;Value(A, e, in;Assign(A, e, i