第4章数据结构-广义线性表.

数据结构（C++版）清华大学出版社第四章广义线性表本章的基本内容是：数组的逻辑结构特征数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构数据结构（C++版）清华大学出版社第四章广义线性表线性表——具有相同类型的数据元素的有限序列。限制插入、删除位置线性表——具有相同类型的数据元素的有限序列。限制元素类型为字符栈——仅在表尾进行插入和删除操作的线性表。队列——在一端进行插入操作，而另一端进行删除操作的线性表。串——零个或多个字符组成的有限序列。特殊线性表数据结构（C++版）清华大学出版社第四章广义线性表线性表——具有相同类型的数据元素的有限序列。将元素的类型进行扩充广义线性表（多维）数组——线性表中的数据元素可以是线性表，但所有元素的类型相同。广义表——线性表中的数据元素可以是线性表，且元素的类型可以不相同。数据结构（C++版）清华大学出版社数组的定义数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。数组的特点元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。广义线性表——多维数组数据结构（C++版）清华大学出版社广义线性表——多维数组a11a12…a1na21a22…a2n…………am1am2…amnA=例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。数组示例数据结构（C++版）清华大学出版社a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)数组——线性表的推广二维数组是数据元素为线性表的线性表。广义线性表——多维数组数据结构（C++版）清华大学出版社数组的基本操作广义线性表——多维数组在数组中插入（或）一个元素有意义吗？a11a12…a1na21a22…a2n…………am1am2…amnA=将元素x插入到数组中第1行第2列。xa11a12…a1na21a22…a2n…………am1am2…amnA=删除数组中第1行第2列元素。数据结构（C++版）清华大学出版社数组的基本操作⑴存取：给定一组下标，读出对应的数组元素；⑵修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作——寻址数组应该采用何种方式存储？数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。广义线性表——多维数组数据结构（C++版）清华大学出版社数组的存储结构与寻址——一维数组设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×c广义线性表——多维数组calai-1ai……ahal+1……Loc(al)Loc(ai)数据结构（C++版）清华大学出版社常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。广义线性表——多维数组数组的存储结构与寻址——二维数组二维数组内存二维结构一维结构数据结构（C++版）清华大学出版社广义线性表——多维数组l2h2l1h1(a)二维数组aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-l1)×(h2-l2＋1)＋(j-l2)本行中aij前面的元素个数每行元素个数整行数aij按行优先存储的寻址数据结构（C++版）清华大学出版社广义线性表——多维数组第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i-l1)×(h2-l2＋1)＋(j-l2)个元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按行优先存储的寻址按列优先存储的寻址方法与此类似。数据结构（C++版）清华大学出版社Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×c广义线性表——多维数组n（n＞2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。数组的存储结构与寻址——多维数组数据结构（C++版）清华大学出版社矩阵的压缩存储特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。特殊矩阵和稀疏矩阵数据结构（C++版）清华大学出版社特殊矩阵的压缩存储——对称矩阵3647862842481697460582957A＝对称矩阵特点：aij=aji如何压缩存储？只存储下三角部分的元素。矩阵的压缩存储数据结构（C++版）清华大学出版社(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的序号=阴影部分的面积=i×(i+1)/2+j+1∵一维数组下标从0开始∴aij在一维数组中的下标k=i×(i+1)/2+j0…in-10…j…n-1aij每行元素个数12…iaij在本行中的序号aij第0行第1行…第i-1行对称矩阵的压缩存储矩阵的压缩存储数据结构（C++版）清华大学出版社对于下三角中的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i。对称矩阵的压缩存储第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1矩阵的压缩存储数据结构（C++版）清华大学出版社特殊矩阵的压缩存储——三角矩阵3cccc62ccc481cc7460c82957(a)下三角矩阵34810c2946cc１57ccc08cccc7(b)上三角矩阵如何压缩存储？只存储上三角（或下三角）部分的元素。矩阵的压缩存储数据结构（C++版）清华大学出版社矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i×(i＋1)/2＋j当i≥jn×(n＋1)/2当i＜jk=下三角矩阵的压缩存储012345kn(n+1)/2第1行第0行a00a10a11a20a21aij…an-1n-1…第2行ca22矩阵的压缩存储存储下三角元素对角线上方的常数——只存一个数据结构（C++版）清华大学出版社矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i×(2n－i＋1)/2＋j－i当i≤jn×(n＋1)/2当i＞jk=上三角矩阵的压缩存储矩阵的压缩存储存储上三角元素对角线上方的常数——只存一个数据结构（C++版）清华大学出版社特殊矩阵的压缩存储——对角矩阵对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。a00a01000a10a11a12000a21a22a23000a32a33a34000a43a44A=矩阵的压缩存储数据结构（C++版）清华大学出版社a00a01000a10a11a12000a21a22a23000a32a33a34000a43a44A=将带状区域立起来0a00a01a10a11a12a21a22a23a32a33a34a43a440B=s＝j-i+1t=i映射到二维数组B中，映射关系对角矩阵的压缩存储矩阵的压缩存储数据结构（C++版）清华大学出版社按行存储元素aij在一维数组中的序号=2+3(i－1)+(j－i+2)=2i+j+1∵一维数组下标从0开始∴元素aij在一维数组中的下标=2i+j(b)寻址的计算方法(c)压缩到一维数组中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112矩阵的压缩存储对角矩阵的压缩存储(a)三对角矩阵000000000000A=a00a01a10a11a12a21a22a23a32a33a34a43a44数据结构（C++版）清华大学出版社稀疏矩阵的压缩存储15000000110000000600000000900000A=如何只存储非零元素？矩阵的压缩存储注意：稀疏矩阵中的非零元素的分布没有规律。数据结构（C++版）清华大学出版社templateclassTstructelement{introw,col;//行号，列号Titem//非零元素值};将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)——三元组矩阵的压缩存储稀疏矩阵的压缩存储定义三元组：数据结构（C++版）清华大学出版社三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。矩阵的压缩存储稀疏矩阵的压缩存储三元组表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))15000000110000000600000000900000A=如何存储三元组表？数据结构（C++版）清华大学出版社稀疏矩阵的压缩存储——三元组顺序表采用顺序存储结构存储三元组表1500220-1501130000006000000009100000A=矩阵的压缩存储三元组顺序表是否需要预留存储空间？稀疏矩阵的修改操作三元组顺序表的插入/删除操作数据结构（C++版）清华大学出版社稀疏矩阵的压缩存储——三元组顺序表采用顺序存储结构存储三元组表0015032205-1511111232364091空空空闲闲闲rowcolitem0123456MaxTerm-1矩阵的压缩存储1500220-1501130000006000000009100000A=7（非零元个数）是否对应惟一的稀疏矩阵？5（矩阵的行数）6（矩阵的列数）数据结构（C++版）清华大学出版社存储结构定义：constintMaxTerm=100;templateclassTstructSparseMatrix{Tdata[MaxTerm];//存储非零元素intmu,nu,tu;//行数，列数，非零元个数};矩阵的压缩存储稀疏矩阵的压缩存储——三元组顺序表数据结构（C++版）清华大学出版社三元组顺序表操作——转置操作例：15000910110000300022060000000-150000B=1500220-1501130000006000000009100000A=矩阵的压缩存储数据结构（C++版）清华大学出版社矩阵的压缩存储0015032205-1511111232364091空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）001504911111213302232650-15空空空闲闲闲rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）数据结构（C++版）清华大学出版社三元组顺序表转置算法——算法Ⅰ基本思想：直接取，顺序存。即在A的三元组顺序表中依次找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。矩阵的压缩存储数据结构（C++版）清华大学出版社矩阵的压缩存储0015032205-1511111232364091空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）设置矩阵B的行数、列数、非零元个数数据结构（C++版）清华大学出版社矩阵的压缩存储0015032205-15