数据结构第5章数组B

1、1数据结构课程的内容数据结构课程的内容2第第5章章 数组和广义表（数组和广义表（Arrays & Lists）5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构 元素的值并非原子类型，元素的值并非原子类型，可以再分解可以再分解，表中元素也是一个，表中元素也是一个线性表（即广义的线性表）。线性表（即广义的线性表）。 所有数据元素仍属所有数据元素仍属同一数据类型同一数据类型。数组和广义表的特点：数组和广义表的特点：一种特殊的线性表一种特殊的线性表3顺序存储方

2、式：顺序存储方式：按低地址优先（或高地址优先）顺序存入一维按低地址优先（或高地址优先）顺序存入一维数组。数组。（难点是：多维数组与一维数组的地址映射关系难点是：多维数组与一维数组的地址映射关系）例例1：已知二维数组已知二维数组Am,m按按行行存储的元素地址公式是：存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 请问按请问按列列存储的公式相同吗？存储的公式相同吗？ 答：答：尽管是方阵，但公式仍不同，要作修改：尽管是方阵，但公式仍不同，要作修改： Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K例例2：00年计算机系考研题年计算机

3、系考研题设数组设数组a160, 170的基地的基地址为址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存个存储单元，若以列序为主序顺序存储，则元素储，则元素a32,58的存储地址为的存储地址为 。根据列优先公式根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：答：请注意审题！请注意审题！想一想：若数组是想一想：若数组是a059, 069，结果是否仍为结果是否仍为8950？4例例3：【专科考研资格考试专科考研资格考试】假设有假设有三维三维数组数组A798，

4、每个，每个元素用相邻的元素用相邻的6个字节存储，存储器按字节编址。已知个字节存储，存储器按字节编址。已知A的起的起始存储位置（基地址）为始存储位置（基地址）为1000，末尾元素，末尾元素A687的第一个的第一个字节地址为多少？若按字节地址为多少？若按高地址优先高地址优先存储时，元素存储时，元素A476的的第一个字节地址为多少？第一个字节地址为多少？ 答：答： 末尾元素末尾元素A687的第的第1个字节地址个字节地址 1000 +(798)66=4018 按按高地址优先高地址优先存储时，元素存储时，元素A476的第的第1个字节地址个字节地址提示：提示：将第将第3维看作维看作“页码页码”，前面两维就

5、是每页上的二维数组，前面两维就是每页上的二维数组。（高维地址计算通式参见清华殷人昆教材的解释高维地址计算通式参见清华殷人昆教材的解释）35865行指针向量行指针向量a11a12a1nam1am2amn补充：数组的链式存储方式补充：数组的链式存储方式用用带行指针向量的单链表带行指针向量的单链表来表示。来表示。注：注：链式数组的运算请参见链式数组的运算请参见“稀疏矩阵的转置稀疏矩阵的转置”注意：注意： 本章所讨论的数组与高级语言中的数组有所区别：本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也

6、可以是的，也可以是链式结构链式结构，用户可根据需要选择。，用户可根据需要选择。65.3 5.3 矩阵的压缩存储讨论：讨论：1. 什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的存储空间，则只分配一个元素值的存储空间，且零元素不占存储空间。且零元素不占存储空间。2. 所有二维数组（矩阵）都能压缩吗？所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。未必，要看矩阵是否具备以上压缩条件。3. 什么样的矩阵具备以上压缩条件？什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩一些特殊矩阵，如：对称

7、矩阵，对角矩阵，三角矩阵，稀疏矩阵等。阵等。4. 什么叫什么叫稀疏矩阵？稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）重点介绍稀疏矩阵的压缩和相应的操作。重点介绍稀疏矩阵的压缩和相应的操作。7一、一、稀疏矩阵的压缩存储稀疏矩阵的压缩存储问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元素的稀疏矩阵中的非零元素，那这些元素的位置信息位置信息该如何表示？该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存储单元，用来存放其所若干存储单元，用来存放其所在的在的行号行号和和列号列号，便可准确反映该元素所在位置。，便可准确反映该

8、元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表示，）来表示，则每个则每个稀疏矩阵可用一个稀疏矩阵可用一个三元组表三元组表来表示。来表示。二、二、稀疏矩阵的操作稀疏矩阵的操作8例例1 ： 三元素组表中的每个结点对应于稀疏矩阵的三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该一个非零元素，它包含有三个数据项，分别表示该元素的元素的 、 和和 。 行下标行下标列下标列下标元素值元素值例例2 2：写出右图所示稀疏矩阵写出右图所示稀疏矩阵的压缩存储形式。的压缩存储形式。0 12 9 0 0 00 0 0 0

9、0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0解：解：至少有至少有4 4种存储形式。种存储形式。法法1 1：用线性表表示：用线性表表示：0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 09法法2 2：用三元组矩阵表示：用三元组矩阵表示：0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0121213931-335144324521861156

10、4-7注意：注意：为更可靠描述，为更可靠描述，通常再加一行通常再加一行“总体总体”信息：即信息：即总行数、总总行数、总列数、非零元素总个列数、非零元素总个数数668ijvalue稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点缺点：将失去随机将失去随机存取功能存取功能 ！10法三：法三：用用带辅助向量带辅助向量的三元组表示。的三元组表示。 方法：方法： 增加增加2个辅助向量：个辅助向量： 记录每行非记录每行非0元素个数，用元素个数，用NUM（i）表示；表示； 记录稀疏矩阵中每行第一个非记录稀疏矩阵中每行第一个非0元素在元素在三三元组中的元组中的行号行号，用，用POS（i）表示。表示。765312112

11、02NUM( i)6543POS( i )21i0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0-7461516182524341453-3139311221866vji0123456783用途：用途：便于便于高效访问高效访问稀疏矩阵中稀疏矩阵中任一非任一非零元素零元素。POS(POS(i i) )如何计算？如何计算？POS(1)1POS(i)POS(i-1)+NUM(i-1)11法四：法四：用用十字链表十字链表表示表示用途：用途：方便稀疏矩阵的方便稀疏矩阵的加减加减运算运算方法：方法：每个非每

12、个非0元素占用元素占用5个域个域right downvji同一同一列列中下一非中下一非零元素的指针零元素的指针同一同一行行中下一非中下一非零元素的指针零元素的指针十字链表的特点：十字链表的特点：每行非零元素链接每行非零元素链接成带表头结点的循环链表；成带表头结点的循环链表；每列非零元素也链接每列非零元素也链接成带表头结点的循环链表。成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即链表中的一个结点，即呈十字链状。呈十字链状。122100H1931182512typedef structtypede

13、f struct TripleTriple datadataMAXSIZE+1; MAXSIZE+1; /三元组表，以行为主序存入一三元组表，以行为主序存入一维向量维向量 data data 中中 int int mumu; ; /矩阵总行数矩阵总行数 int int nunu; ; /矩阵总列数矩阵总列数 int tu; int tu; /矩阵中非零元素总个数矩阵中非零元素总个数 TsMatrixTsMatrix; ; 三元组表的顺序存储表示三元组表的顺序存储表示（见教材（见教材P98P98）对三元组表对三元组表的整体定义的整体定义 #define MAXSIZE 125000 #defin

14、e MAXSIZE 125000 /设非零元素最大个数设非零元素最大个数125000125000 typedef struct typedef struct int i; int i; /元素行号元素行号 int j; int j; /元素列号元素列号 ElemType e; ElemType e; /元素值元素值 TripleTriple; ; 对表中每对表中每个结点的结构定义个结点的结构定义13二、二、稀疏矩阵的操作稀疏矩阵的操作 0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 00 0 3 0

15、 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三三元元组组表表a.data三三元元组组表表b.data转置后转置后MT（以转置运算为例）（以转置运算为例）目的：目的：14答：答：肯定不正确！肯定不

16、正确！除了：除了： （1 1）每个元素的行下标和列下标互换（即三元组）每个元素的行下标和列下标互换（即三元组中的中的i i和和j j互换互换）；）；还需要：还需要：（2 2） T T的总行数的总行数mumu和总列数和总列数nunu也要也要互换；互换； （3 3）重排重排三元组内各元素顺序三元组内各元素顺序，使转置后的三元，使转置后的三元组也按行（或列）为主序有规律的排列。组也按行（或列）为主序有规律的排列。上述（上述（1 1）和（）和（2 2）容易实现，难点在）容易实现，难点在（3 3）。 若采用三元组压缩技术存储稀疏矩阵，只要把每个若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的元素的行下

17、标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 有两种实现有两种实现转置的方法转置的方法压缩转置压缩转置快速快速( (压缩压缩) )转置转置提问：提问：15方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描a a表表（记为（记为a.dataa.data）中的中的列序列序，从从j=1j=1n n依次进行转置。依次进行转置。三三元元组组表表a.data三三元元组组表表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6

18、, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)11col q1234讨论：每个元素的列分量怎样书写？讨论：每个元素的列分量怎样书写？a.datap.j p123416Status TransPoseSMatrix(TSMatrix M, TSMatrix &T)T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for(col=1; col=M.nu; col+) for(p=1; p=M.tu;

19、p+) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.value=M.datap.value; q+; return OK; /TranposeSMatrix;压缩转置算法描述压缩转置算法描述：（见教材（见教材P99）/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求，求M M的转置矩阵的转置矩阵T T/q q是转置矩阵是转置矩阵T T的结点编号的结点编号/colcol是扫描是扫描M M三元表列序的变量三元表列序的变量/p是是M M三元表中结点编号三元表中结点编号17三三元元组组表表a.data三

20、三元元组组表表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)11col q1234 p12341 1、主要时间消耗在主要时间消耗在查找查找M.datap.j=colM.datap.j=col的元素的元素，由两重循，由两重循环完成环完成: : for(col=1; col=M.nu; col+) 循环次数列长

21、度循环次数列长度nu for(p=1; p=M.tu; p+) 循环次数非零元素个数循环次数非零元素个数tu压缩转置算法的效率分析压缩转置算法的效率分析：所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(nunu* *tutu) ) - -即即M M的列数与的列数与M M中非零元素的个数之中非零元素的个数之积积最恶劣情况：最恶劣情况：M M中全是非零元素，此时非零元素总数中全是非零元素，此时非零元素总数tu=mutu=mu* *nunu， 时间复杂度为时间复杂度为 O(O(nunu2 2* *mumu ) )注：注：若若M M中基本上是非零元素时，即使用传统转置算法的时间复中基本上是非零

22、元素时，即使用传统转置算法的时间复杂度也不过是杂度也不过是O(O(nunu* *mumu) ) （程序见教材（程序见教材P99P99）结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提：前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tutumumu* *nunu）的情况。）的情况。18方法方法2 2 快速转置快速转置三三元元组组表表a.data三三元元组组表表b.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)(1, 2, 12)(1, 3, 9 )(

23、3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路：思路：依次依次把把a.dataa.data中的元素直接送入中的元素直接送入b.datab.data的恰当位的恰当位置上（置上（即即M M三元组的三元组的p p指针不回溯指针不回溯）。）。关键：关键：怎样寻找怎样寻找b.datab.data的的“恰当恰当”位置？位置？ p1234 q 3 519如果能如果能预知预知M矩阵矩阵每一列每一列( (即即T的每一行的每一行) )的的非零元素个数非零元素个数，又能预知又能预知第一个非零元素第一个非零元素在在b.datab.data中的

24、中的位置位置, ,则扫描则扫描a.data时便可以将每个元素准确定位（时便可以将每个元素准确定位（因为已知若干参考点因为已知若干参考点）。）。技巧：先生成技巧：先生成三元组表的三元组表的两个辅助向量两个辅助向量，让它携带每行（或，让它携带每行（或列）的非零元素个数列）的非零元素个数 NUM(i)以及每行（或列）的第一以及每行（或列）的第一个非零元素在三元组表中的位置个非零元素在三元组表中的位置POS(i) 等信息。等信息。设计思路：设计思路：i123456NUM(i)202112POS( i )133567注：为实现转置运算，应当注：为实现转置运算，应当按列按列生成生成 M 矩阵的辅助向量矩阵

25、的辅助向量计算式计算式：POS(1)1POS(i)POS(i-1)+NUM(i-1)辅助向量的样式：辅助向量的样式：请注意请注意a.dataa.data特征：每列首个非零元素必定先被扫描到。特征：每列首个非零元素必定先被扫描到。20令：令：M矩阵中的矩阵中的列列变量用变量用col表示；表示； num col ：存放存放M中第中第col 列中非列中非0 0元素个数元素个数 cpot col ：存放存放M中第中第col列的第一个非列的第一个非0 0元素的位置元素的位置 （即（即b.datab.data中待计算的中待计算的“恰当恰当”位置所需参考点）位置所需参考点）讨论：讨论：求出求出按列优先按列优

26、先的的辅助向量辅助向量后，后，如何如何实现快速转置？实现快速转置？col123456numcol222110cpotcol1计算式：计算式： cpot(1)1cpotcol cpotcol-1 + numcol-1 3 5 7 8 90 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0Mcol 1 2 3 4 5 6由由a a.data.data中每个元素的列信息，可以直接中每个元素的列信息，可以直接从辅助向量从辅助向量cpotcol中查出在中查出在b b.data.data中的中的“基准基准”位置，

27、进而得到当前元素之位置。位置，进而得到当前元素之位置。三三元元组组表表a.data(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)col p1234想一想：是从原始矩阵想一想：是从原始矩阵M M中统计中统计numcol方便些，方便些，还是从对应的三元组表还是从对应的三元组表a.dataa.data中统计更方便？中统计更方便？21Status FastTransposeSMatrix（TSMatirx M, TSMatirx &T） T.mu = M.nu ;T .nu = M

28、.mu ; T.tu = M.tu ; if ( T.tu ) for(col = 1; col =M.nu; col+) numcol =0; for( i = 1; i =M.tu; i +) col =M.datai .j ; +num col ; cpos 1 =1; for(col = 2; col =M.nu; col+) cposcol =cposcol-1+num col-1 ; for( p =1; p =M.tu ; p + ) col =M.data p . j ; =cpos col ; T.dataq.i = M.datap. j; T.dataq.j = M.dat

29、ap. i; T.dataq. value = M.datap. value; /for /ifreturn OK; /FastTranposeSMatrix;快速转置算法描述快速转置算法描述：/M/M是顺序存储的三元组表，求是顺序存储的三元组表，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量再生成每列首元位置辅助向量/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量得查辅助向量得 ，即，即T T中位置中位置前前3 3个个forfor循环循环用来产生两个用来产生两个辅助

30、向量辅助向量重要！修改向量内容（列坐标加重要！修改向量内容（列坐标加1 1），），预备给预备给同列同列的下一非零元素定位之用的下一非零元素定位之用元素转置元素转置221.1. 与常规算法相比，附加了与常规算法相比，附加了生成辅助向量表生成辅助向量表的工作。增开了的工作。增开了2 2个长度为列长的数组个长度为列长的数组( (num 和和cpos ）。传统转置：传统转置：O(O(mumu* *nunu) ) 压缩转置：压缩转置：O(O(mumu* *tutu) ) 压缩快速转置：压缩快速转置：O(O(nu+nu+tutu) )快速转置算法的效率分析快速转置算法的效率分析：2.2. 从时间上，此算法

31、用了从时间上，此算法用了4 4个并列的单循环，而且其中前个并列的单循环，而且其中前3 3个个单循环都是用来产生辅助向量表的。单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col+) ; 循环次数循环次数nu;nu; for( i = 1; i =M.tu; i +) ; 循环次数循环次数tu;tu; for(col = 2; col =M.nu; col+) ; 循环次数循环次数nu;nu; for( p =1; p =M.tu ; p + ) ; 循环次数循环次数tu;tu; 该算法的时间复杂度该算法的时间复杂度nu+tu+nu+tu=O(nu+tu+nu

32、+tu=O(nu+tunu+tu）讨论：讨论：最恶劣情况是矩阵中全为非零元素，此时最恶劣情况是矩阵中全为非零元素，此时tu=nutu=nu* *mumu而此时的时间复杂度也只是而此时的时间复杂度也只是O(O(mumu* *nunu) )，并未超过传统转置算，并未超过传统转置算法的时间复杂度。法的时间复杂度。小结：小结：稀疏矩阵相乘的算法略，稀疏矩阵相乘的算法略，见教材见教材P101-103P101-103增设辅助向量，牺牲空间增设辅助向量，牺牲空间效率换取时间效率。效率换取时间效率。235.4 5.4 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（广义表是线性表的推广，也称为列表（

33、lists）记为：记为： LS = ( a1 , a2 , ， an ) 广义表名广义表名 表头表头(Head） 表尾表尾 (Tail)1、定义：、定义： 第一个第一个元素是表头元素是表头，而其余元素组成的，而其余元素组成的表称为表尾表称为表尾； 用小写字母表示原子类型，用用小写字母表示原子类型，用大写字母大写字母表示列表。表示列表。n n是表长是表长在广义表中约定：在广义表中约定：讨论：讨论：广义表与线性表的区别和联系？广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表；广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。当每个元素都

34、为原子且类型相同时，就是线性表。242、特点：、特点： 有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元素个数表中括号的重数表中括号的重数自己可以作为自己的子表自己可以作为自己的子表可以为其他广义表所共享可以为其他广义表所共享特别提示：特别提示：任何一个非空表，表头可能是原子，也可能任何一个非空表，表头可能是原子，也可能是列表；但是列表；但表尾一定是列表表尾一定是列表。25E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为为递归表递归表1）A =( )2）B = ( e ) 3）C =(

35、 a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)例例1：求下列广义表的长度。求下列广义表的长度。n=0，因为因为A A是空表是空表n=1，表中元素表中元素e e是原子是原子n=2，a a 为原子，为原子，(b,c,d)(b,c,d)为子表为子表n=3，3 3个元素都是子表个元素都是子表n=2，a a 为原子，为原子，E E为子表为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表26ABDCeabcd A=( a , (b, A) )例例2 2：试用图形表示下列广义表试用图形表示下列广义表. .（设（设 代表子表，代表子表， 代表元素）代表元素） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为深度括号的重数深度括