第4章广义线性表-1

《第4章广义线性表-1》由会员分享，可在线阅读，更多相关《第4章广义线性表-1（66页珍藏版）》请在文档大全上搜索。

1、1第第4章章 广义广义线性表线性表多维数组和广义表多维数组和广义表本章的基本内容是：本章的基本内容是：数组的逻辑结构特征数组的逻辑结构特征数组的存储方式及寻址方法数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构广义表的基本概念和存储结构2线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除位置线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操

2、作的线性表。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特殊线性表特殊线性表3线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广义线性表广义线性表（多维）数组（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。广义表广义表线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且元素的类型可以不相同。且元素的类型可以不相同

3、。44.1 多维数组多维数组多维数组的知识点组织结构图多维数组的知识点组织结构图多维数组的逻辑结构多维数组的逻辑结构数组的定义数组的定义数组的数组的ADT定义定义数组的存储结构数组的存储结构顺序存储顺序存储行优先行优先列优先列优先压缩存储压缩存储特殊矩阵特殊矩阵稀疏矩阵稀疏矩阵5数组的定义数组的定义数组是由一组数组是由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集合，每个数据元素称为一个数组元素（简称为元合，每个数据元素称为一个数组元素（简称为元素），每个元素受素），每个元素受n n( (n n1)1)个个线性关系线性关系的约束，每的约束，每个元素在个元素在n n个线性关系中

4、的序号个线性关系中的序号i i1 1、i i2 2、i in n称称为该元素的下标，并称该数组为为该元素的下标，并称该数组为 n n 维数组。维数组。 数组的特点数组的特点元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。6 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a a2222受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有一个行前驱一个行前驱a a2121和一个行后继和一个行后继a a2323，在列上有一个列

5、，在列上有一个列前驱前驱a a1212和和一个列后继和和一个列后继a a3232。数组示例数组示例7 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)数组数组线性表的推广线性表的推广二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。8数组的基本操作数组的基本操作在数组中插入（或）一个元素有意义吗？在数组中插入（或）一个元素有意义吗？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=将元素将元素 x x 插入插入到数组中第到数组中第1 1

6、行第行第2 2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=删除数组中删除数组中第第1 1行第行第2 2列元素。列元素。9数组的基本操作数组的基本操作 存取（读）：给定一组下标，读出对应的数组存取（读）：给定一组下标，读出对应的数组元素；元素； 修改（写）：给定一组下标，存储或修改与其修改（写）：给定一组下标，存储或修改与其相对应的数组元素。相对应的数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？适合采用顺序存储。适合采用顺序存储。数组的数组的ADTADT定义（教材

7、定义（教材P116)P116)10数组的存储结构与寻址数组的存储结构与寻址一维数组一维数组设一维数组的设一维数组的下标的范围下标的范围为闭区间为闭区间l l，h h，每个，每个数组元素占用数组元素占用 c c 个存储单元，则其个存储单元，则其任一元任一元素素 a ai i 的的存储地址可由下式确定：存储地址可由下式确定： Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)11常用的映射方法有两种：常用的映射方法有两种：按按行行优先：优先：先行后列先行后列，先存储行号较小的元素，先存储行号较小的元素，行号相同者先存储列号较小的元素。行号

8、相同者先存储列号较小的元素。 按按列列优先：优先：先列后行先列后行，先存储列号较小的元素，先存储列号较小的元素，列号相同者先存储行号较小的元素。列号相同者先存储行号较小的元素。 二维数组二维数组内内 存存二维结构二维结构一维结构一维结构数组的存储结构与寻址数组的存储结构与寻址二维数组二维数组12l2h2 l1h1(a) (a) 二维数组二维数组aij前面的元素个数前面的元素个数= =整行数整行数每行元素个数每行元素个数+ +本行中本行中aij前面的元素个数前面的元素个数=( (i - -l1) )( (h2 - -l21) )( (j - -l2) )本行中本行中a aijij前面的元素个数前

9、面的元素个数每行元素个数每行元素个数整整行行数数aij按行优先存储的寻址按行优先存储的寻址13按行优先存储的寻址按行优先存储的寻址第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )个元素个元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。a(0,0)a(0,1)a(0,3)a(1,0)a(1,1)a(1,3)a(3

10、,2)a(6,0)a(6,3) 012 3例例1 1：如何求出：如何求出的存储地址？的存储地址？要事先确定：要事先确定：是行优先方式还是列优先方式？是行优先方式还是列优先方式？数组的首地址是多少？数组的首地址是多少？每个元素的长度？每个元素的长度？否则无法否则无法求出结果求出结果15111101121202111101101000mnananamaaamaaamaaaa设数组开始存放位置设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用每个元素占用 l 个存储单元个存储单元 则则aij的存储地址：的存储地址： LOC ( i, j ) = a + ( j *n +i ) * l

11、按列优先存储的寻址按列优先存储的寻址例例2：例例3 3：一个二维数组：一个二维数组A A，行下标的范围是，行下标的范围是1 1到到6 6，列下标的，列下标的范围是范围是0 0到到7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，存个字节存储，存储器按字节编址。那么，这个数组的体积是储器按字节编址。那么，这个数组的体积是 个字节。个字节。 288288答：答： Volume=mVolume=m* *n n* *L=(6-1L=(6-1+1+1) )* *(7- 0 (7- 0 +1+1) )* *6=486=48* *6=2886=288例例4 4：已知二维数组：已知二维数组A