数据结构数组和广义表演示

1、结束第 1 页结束第 2 页第五章第五章数组和广义表数组和广义表第五章第五章数组和广义表数组和广义表 5.1数组5.2矩阵的压缩存储5.3广义表结束第 3 页前前4章介绍的数据结构共同特点：章介绍的数据结构共同特点：（1）都属于线性数据结构；）都属于线性数据结构；（2）每种数据结构中的数据元素，都作为原子数据，不再）每种数据结构中的数据元素，都作为原子数据，不再进行分解；进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；）从逻辑结构上看它们，可看成是线性结构的一种扩展；2）数据元

2、素本身也是一个数据结构；）数据元素本身也是一个数据结构；本章讨论三个方面的内容：数组、本章讨论三个方面的内容：数组、矩阵的压缩存储、广义矩阵的压缩存储、广义表表第五章第五章数组和广义表数组和广义表结束第 4 页5 51 1 数数 组组5.1数 组一 数组的概念二 数组的顺序表示和实现结束第 5 页学习要点学习要点1了解数组的逻辑结构了解数组的逻辑结构2了解数组的两种存储结构；了解数组的两种存储结构；3掌握数组在以行为主序的方式存储时，数组元素掌握数组在以行为主序的方式存储时，数组元素地址的计算方法；地址的计算方法；基本内容基本内容1 数组的概念及基本操作2 数组的顺序存贮结构5 51 1 数数

3、 组组结束第 6 页5 51 1 数数 组组1数组的概念 数组是我们十分熟悉的一种数据类型，几乎所有的程数组是我们十分熟悉的一种数据类型，几乎所有的程序设计语言都包含数组。本书在讨论各种数据结构的顺序序设计语言都包含数组。本书在讨论各种数据结构的顺序存储分配时，也都是借用一维数组来描述它们的存储结构存储分配时，也都是借用一维数组来描述它们的存储结构。这一章将从数据结构的角度，简单讨论数组的逻辑结构。这一章将从数据结构的角度，简单讨论数组的逻辑结构及其存储方式，另外书上还给出了数组的基本操作算法，及其存储方式，另外书上还给出了数组的基本操作算法，如：数组的初始化，读取指定下标的数组元素算法，给指

4、如：数组的初始化，读取指定下标的数组元素算法，给指定下标的数组元素赋值等操作算法；定下标的数组元素赋值等操作算法；注：注：数组的基本操作算法，不是本课程要求掌握的内容数组的基本操作算法，不是本课程要求掌握的内容。结束第 7 页5 51 1 数数 组组 数组是由一组个数固定，类型相同的数据元素组成阵列。数组是由一组个数固定，类型相同的数据元素组成阵列。 数组中的每个元素都受数组中的每个元素都受n n个线性关系的约束，即在每个关系中，每个个线性关系的约束，即在每个关系中，每个元素元素a aijij都有且仅有一个直接前趋，都有且仅有一个直接后继都有且仅有一个直接前趋，都有且仅有一个直接后继。 Amn

5、=a11 a12 a1na21 a22 a2nam1 am2 amn在行关系中在行关系中 a aijij直接前趋是直接前趋是 a aijij-1-1 a aijij直接后继是直接后继是 a aijij+1+1在列关系中在列关系中 a aijij直接前趋是直接前趋是 a ai i-1j-1j a aijij直接后继是直接后继是 a ai i+1j+1j 以二维数组为例：二维数组中的每个元素都受两个线性关系的约束结束第 8 页5 51 1 数数 组组数组的基本操作数组的基本操作1 1 初始化操作初始化操作 InitArrayInitArray(&A,n,bound1,(&A,n,b

6、ound1, ,boundnboundn) )功能：功能：参数合法，构造数组参数合法，构造数组A A，并返回，并返回OKOK；2 2 销毁操作销毁操作 DestroyArrayDestroyArray(&A)(&A)功能：功能：销毁数组销毁数组A A ；3 3 读元素操作读元素操作 Value(A,&e,index1,Value(A,&e,index1, ,indexnindexn) )功能：若指定下标不越界，读指定下标的元素功能：若指定下标不越界，读指定下标的元素，用，用e e返回，并返回返回，并返回OKOK；4 4 写元素操作写元素操作 Assign(A,e

7、,index1,Assign(A,e,index1, ,indexnindexn) )功能：若指定下标不越界，将功能：若指定下标不越界，将e e赋值给赋值给A A指定的指定的下标元素，并返回下标元素，并返回OKOK；结束第 9 页5 51 1 数数 组组2数组的顺序存贮结构数组的顺序存贮结构 一般来说，一般来说，数组一旦定义，其元素的个数和元素之间的相互关数组一旦定义，其元素的个数和元素之间的相互关系不再发生变化，即对数组一般不进行插入和删除操作。因此，数系不再发生变化，即对数组一般不进行插入和删除操作。因此，数组采用顺序存储结构是十分自然的事情。组采用顺序存储结构是十分自然的事情。计算机的内

8、存空间是一个一维结构，而二维以上的数组是多维计算机的内存空间是一个一维结构，而二维以上的数组是多维结构。因此，用一组连续的存储单元存放数组元素，就有次序约定结构。因此，用一组连续的存储单元存放数组元素，就有次序约定的问题。以二维数组为例，它有两种方式：一种是以行为主序的方的问题。以二维数组为例，它有两种方式：一种是以行为主序的方式，另一种是以列序为主序的方式。行为主序方式是先存储数组的式，另一种是以列序为主序的方式。行为主序方式是先存储数组的第一行元素，再存储第二行元素第一行元素，再存储第二行元素；而列序为主序方式是先存储数；而列序为主序方式是先存储数组的第一列元素，再存储第二列元素组的第一列

9、元素，再存储第二列元素；在众多的程序设计语言中；在众多的程序设计语言中，以行序为主序方式的有，以行序为主序方式的有PASCAL、COBOL、C及扩展及扩展BASIC等，等，以列序为主序方式的有以列序为主序方式的有FORTRAN语言。语言。结束第 10 页5 51 1 数数 组组设设A是是一个具有一个具有m行行n列的元素的二维数组列的元素的二维数组（借助矩阵形式给出比较借助矩阵形式给出比较直观）如下直观）如下：A Am m n= =以行为主序的方式：以行为主序的方式：a a00 00 a a01 01 a a0n-1 0n-1 a a10 10 a a11 11 a a1n-1 1n-1 a a

10、m-10 m-10 a am-11 m-11 a am-1n-1m-1n-10 1 0 1 n-1 n n+1 2n-1 n-1 n n+1 2n-1 mnmn-1-1a a00 00 a a01 01 a a0n-10n-1a a10 10 a a11 11 a a1n-11n-1a am-10 m-10 a am-11 m-11 a am-1n-1m-1n-1结束第 11 页5 51 1 数数 组组以列为主序的方式：a00 a10 am-10 a01 a11 am-11 a0n-1a1n-1 am-1n-10 1 m-1 m m+1 2m-1 nm-1结束第 12 页5 51 1 数数 组

11、组数组元素存储地址的计算数组元素存储地址的计算无论采用哪种存储方式，一旦确定了存储映象的首地址。数组中任无论采用哪种存储方式，一旦确定了存储映象的首地址。数组中任意元素的存储地址都可以确定。意元素的存储地址都可以确定。假设二维数组假设二维数组A每个元素占用每个元素占用k个存储单元，个存储单元，Loc(a aijij)为元素为元素a aijij的存的存储地址，储地址，Loc(a a0000)是是a a0000存储位置存储位置,也是二维数组也是二维数组A的基址的基址。若以行序为主序的方式存储二维数组，则元素若以行序为主序的方式存储二维数组，则元素a aijij的存储位置的存储位置可由下可由下式确定

12、：式确定：Loc(a aijij)=Loc(a a0000)+（n i+j) k若以列序为主序的方式存储二维数组，则元素若以列序为主序的方式存储二维数组，则元素a aijij的存储位置的存储位置可由下可由下式确定：式确定：Loc(a aijij)=Loc(a a0000)+（m j+i) k一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，读者维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，读者可以将二维的情形加以推广便能够得到，这里不再赘述。可以将二维的情形加

13、以推广便能够得到，这里不再赘述。结束第 13 页 小 结1数组中的每个元素都受n个线性关系的约束，在每个关系中，每个元素 aij都有且仅有一个直接前趋，都有且仅有一个直接后继。2二维数组有两种方式：一种是以行为主序的方式，另一种是以列序为主序的方式。 5 51 1 数数 组组结束第 14 页5 52 2 矩阵的压缩存储矩阵的压缩存储5.2矩阵的压缩存储 一 特殊矩阵的压缩存储二 稀疏矩阵的压缩存储 结束第 15 页5 52 2 矩阵的压缩存储矩阵的压缩存储基本内容 1 特殊矩阵的压缩存储 ； 2 稀疏矩阵的压缩存储； 3 稀疏矩阵在三元组顺序表存储方式下，矩阵的运算的实现；学习要点1 了解矩阵

14、的两种压缩存储方法及适用范围；2 了解在三元组顺序表存储方式下，实现矩阵运算的方法；结束第 16 页5 52 2 矩阵的压缩存储矩阵的压缩存储矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。一一个个m行行n列的矩阵是一平面阵列，有列的矩阵是一平面阵列，有m n个元素。可以对矩阵作加、减、个元素。可以对矩阵作加、减、乘等运算。这里我们感兴趣的不是矩阵本身，而是矩阵在计算机内的有乘等运算。这里我们感兴趣的不是矩阵本身，而是矩阵在计算机内的有效存储方法和对应的各种矩阵运算的算法。效存储方法和对应的各种矩阵运算的算法。只有只有少数程序设计

15、语言提供了矩阵运算。通常程序员是用二维数组存少数程序设计语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。为容易地实现矩阵的各种运算。A Am m n= =a a00 00 a a01 01 a a0n-10n-1a a10 10 a a11 11 a a1n-11n-1a am-10 m-10 a am-11 m-11 a am-1n-1m-1n-1结束第 17 页然而应用中常遇到一些阶数很高的矩阵，并且矩阵中有许然而应用中常遇到一些阶数很高的矩阵

16、，并且矩阵中有许多值相同的元素或零元素，用二维数组存储矩阵会浪费很多的多值相同的元素或零元素，用二维数组存储矩阵会浪费很多的存储单元存放实际上可以不必存放的元素。为了节省存储空间，存储单元存放实际上可以不必存放的元素。为了节省存储空间，对这类矩阵可以压缩存储。所谓压缩存储是指为多个值相同的对这类矩阵可以压缩存储。所谓压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间。元素分配一个存储空间，对零元素不分配存储空间。例如，设一个例如，设一个1000 1000的矩阵中有的矩阵中有800个非零元素，若用二个非零元素，若用二维数组存储需要维数组存储需要106个存储单元，而压缩存储只需

17、个存储单元，而压缩存储只需800个存储单个存储单元。元。本章将讨论两类矩阵的压缩存储：本章将讨论两类矩阵的压缩存储：1特殊矩阵的压缩存储特殊矩阵的压缩存储2稀疏矩阵的压缩存储稀疏矩阵的压缩存储5 52 2 矩阵的压缩存储矩阵的压缩存储结束第 18 页5 52 2 矩阵的压缩存储矩阵的压缩存储一一特殊矩阵特殊矩阵1什么是特殊矩阵什么是特殊矩阵值相同元素或者零元素分布有一定规律的矩阵称为值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵特殊矩阵例例对称矩阵、对称矩阵、上（下）三角矩阵都是特殊矩阵上（下）三角矩阵都是特殊矩阵2特殊矩阵压缩存储特殊矩阵压缩存储下面以对称矩阵为例，讨论特殊矩阵的压缩存

18、储下面以对称矩阵为例，讨论特殊矩阵的压缩存储对称矩阵是满足下面条件的对称矩阵是满足下面条件的n阶矩阵阶矩阵 a aijij= = a aji ji 1 1 i,ji,j n n 结束第 19 页5 52 2 矩阵的压缩存储矩阵的压缩存储 n阶对称矩阵中，显然只需存储对称矩阵的上（或下）三阶对称矩阵中，显然只需存储对称矩阵的上（或下）三角元素。这样，角元素。这样，n阶对称矩阵的阶对称矩阵的n2个元素就压缩到个元素就压缩到n(n+1)/2个存个存储单元中。储单元中。设用一维数组设用一维数组Sn(n+1)/2存储存储n阶对称对称矩阵阶对称对称矩阵A的下三角的下三角（包括主对角线元素）的元素。不失一般

19、性，我们以行序为主（包括主对角线元素）的元素。不失一般性，我们以行序为主序方式存储对称矩阵下三角元素。序方式存储对称矩阵下三角元素。a11 a21 a22 a31 a32 a33 am1 am2 amn 0 1 2 3 4 5 n(n+1)/2-1结束第 20 页5 52 2 矩阵的压缩存储矩阵的压缩存储对任意一组下标值（对任意一组下标值（i,j），），均可以在均可以在S找到矩阵找到矩阵a aijij，反，反之，对所有之，对所有k=0,2n(n+1)/2-1,都能确定都能确定Sk在矩阵中的位置（在矩阵中的位置（i,j）因此，称因此，称S为为n阶对称矩阵阶对称矩阵A的压缩存储。的压缩存储。k =

20、k =i(i-1)/2+j-1 i(i-1)/2+j-1 当当 i i j jj(j-1)/2+i-1 j(j-1)/2+i-1 当当 i i j jA中任意一元素中任意一元素a aijij与它的存储位置之间存在着如下对应与它的存储位置之间存在着如下对应关系：关系：结束第 21 页5 52 2 矩阵的压缩存储矩阵的压缩存储2稀疏矩阵 1 什么是稀疏矩阵 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。例M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0

21、15 0 0 -7 0 0 0M有42（67）个元素有8个非零元素结束第 22 页5 52 2 矩阵的压缩存储矩阵的压缩存储2 稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）；如何进行稀疏矩阵的压缩存储？稀疏矩阵的压缩存储有多种方法，本课程主要介绍三元组顺序表这种存储方式。1）三元组表 按照压缩存储的概念，只须存储稀疏矩阵的非零元素。但稀疏矩阵按照压缩存储的概念，只须存储稀疏矩阵的非零元素。但稀疏矩阵零元素分布没有一定规律，因此，除了存储非零元素的值之外，还必须零元素分布没有一定规律，因此，除了存储非零元素的值之外，还必须同时记下它所在行和列号；反之，一个三元组（同时记下它所在行和列号

22、；反之，一个三元组（i,j,e)，能唯一确定矩阵能唯一确定矩阵的一个非零元。由此，稀疏矩阵可由非零元的三元组表及其行数、列数的一个非零元。由此，稀疏矩阵可由非零元的三元组表及其行数、列数唯一确定。唯一确定。 例如，下列三元组表A=(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)加上行、列数6，7便可作为矩阵M的另一种表示方式。 上述三元组表的不同存储方法可引出稀疏矩阵不同的压缩存储方法 结束第 23 页5 52 2 矩阵的压缩存储矩阵的压缩存储2）三元组顺序表）三元组顺序表假设以顺序存储结构来表示三元组

23、表，则可得稀疏矩阵的一种压缩假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式存储方式我们称之为三元组顺序表。我们称之为三元组顺序表。稀疏矩阵的三元组顺序表的类型定义稀疏矩阵的三元组顺序表的类型定义#defineMAXSIZE12500/假设非零元个数的最大值为假设非零元个数的最大值为12500Typrdefstructinti,j;/非零元的行下标和列下标非零元的行下标和列下标ElemTypee;/非零元非零元Triple;TypedefunionTripledataMAXSIZE+1;/用于存储非零元三元组表用于存储非零元三元组表,data0未未用用intmu,nu,tu;

24、/矩阵的行数、列数和非零矩阵的行数、列数和非零元个数元个数TSMatrix;结束第 24 页5 52 2 矩阵的压缩存储矩阵的压缩存储Triple：是包含三个域的结构类型，其变量用于存储矩阵的非是包含三个域的结构类型，其变量用于存储矩阵的非零元三元组零元三元组i,j：两个整数域，用于存储两个整数域，用于存储非零元的行下标和列下标非零元的行下标和列下标e：用于存储用于存储非零元的值非零元的值TSMatrix：是包含四个域的结构类型，是包含四个域的结构类型，data：一维数组，用于存储矩阵的非零元三元组表一维数组，用于存储矩阵的非零元三元组表mu,nu,tu：三个整数域，分别存储三个整数域，分别存

25、储矩阵的行数、列数和非零矩阵的行数、列数和非零元个数元个数设设M M是是 TSMatrix类型的结构变量，则类型的结构变量，则M有四个域，其中有四个域，其中M.data用于存储矩阵用于存储矩阵M的三元组表，在此我们约定，的三元组表，在此我们约定，M.data域域中非零元三元组是以行序为主序顺序存储的。中非零元三元组是以行序为主序顺序存储的。结束第 25 页5 52 2 矩阵的压缩存储矩阵的压缩存储M的三元组顺序表的三元组顺序表图示图示 M M= = 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0-

26、3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 015 0 0 -7 0 0 0设设M M是是TSMatrix类型的结构变量，则类型的结构变量，则M有有四个域，其中四个域，其中M.data用于存储矩阵用于存储矩阵M的三的三元组表，如右图所示元组表，如右图所示i j ei j e1 12 23 34 45 56 67 78 83 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4

27、 -76 4 -73 6 143 6 14M.dataM.data6 67 78 8M.M.mumuM.M.nunuM.M.tutu结束第 26 页5 52 2 矩阵的压缩存储矩阵的压缩存储 3 转置运算算法 下面以矩阵的转置运算为例，讨论在三元组顺序表存储方式下，如何实现矩阵的运算。本课件介绍两种转置运算算法。 转置运算是一种最简单的矩阵运算。对于一个m行 n列的矩阵M，它的转置矩阵T是一个n行m列的矩阵。例如，下图中的矩阵M和T互为转置矩阵。 M = 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14

28、 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 015 0 0 -7 0 0 0 T = 0 0 -3 0 0 150 0 -3 0 0 1512 0 0 0 18 0 12 0 0 0 18 0 9 0 0 24 0 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 结束第 27 页

29、5 52 2 矩阵的压缩存储矩阵的压缩存储 M第一列第一列 第二列第二列第三列第三列 第四列第四列第五列第五列 第六列第六列 T T第一行第一行 第二行第二行第三行第三行 第四行第四行第五行第五行 第六行第六行结束第 28 页5 52 2 矩阵的压缩存储矩阵的压缩存储i j v123456783 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14M.data678M.muM.nuM.tui j v123456782 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 18T.data768T.muT.nuT.tu矩阵M的

30、三元组顺序表M的转置矩阵T的三元组顺序表结束第 29 页5 52 2 矩阵的压缩存储矩阵的压缩存储1)转置运算算法转置运算算法TransposeSMatrix(TSMatrixM,TSMatrix&T)基本思想基本思想 对对M.dataM.data从头至尾扫描：从头至尾扫描： 第一次扫描时，将第一次扫描时，将M.dataM.data中列号为中列号为1 1的三元组赋值到的三元组赋值到T.dataT.data中，中， 第二次扫描时，将第二次扫描时，将M.dataM.data中列号为中列号为2 2的三元组赋值到的三元组赋值到T.dataT.data中，中， 依此类推，直至将依此类推，直至将M

31、.dataM.data所有三元组赋值到所有三元组赋值到T.dataT.data中中结束第 30 页5 52 2 矩阵的压缩存储矩阵的压缩存储转置运算算法Status TransposeSMatrix(TSMatrix M, TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; / q为当前三元组在T.data 存储位置(下标) for (col=1; col=M.nu; +col) for (p=1; p=M.tu; +p) /p为扫描M.data 的“指示器” /p“

32、指向”三元组称为当前三元组 if (M.datap.j= =col) T.dataq.i =M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK;/ TransposeSMtrix 算法5.1结束第 31 页i j vi j v1 2 121 2 121 3 91 3 93 1 -33 1 -33 6 143 6 144 3 244 3 245 2 185 2 186 1 156 1 156 4 -76 4 -7i j vi j v3 1 -33 1 -32 5 182 5 181 3 -31 3 -36 1 15

33、6 1 151 6 151 6 151 2 121 2 122 1 122 1 125 2 185 2 181 3 91 3 93 1 93 1 94 3 244 3 243 4 243 4 246 4 -76 4 -74 6 -74 6 -73 6 143 6 146 3 146 3 14M.dataM.dataT.dataT.data对对M M六次扫描完成转置运算六次扫描完成转置运算第一次扫描查找第一次扫描查找第第1 1列元素列元素第一次扫第一次扫描结束描结束第二次扫第二次扫描结束描结束第二次扫描查找第二次扫描查找第第2 2列元素列元素5 52 2 矩阵的压缩存储矩阵的压缩存储第三次扫描查

34、找第三次扫描查找第第3 3列元素列元素第四次扫描查找第四次扫描查找第第4 4列元素列元素第五次扫描查找第五次扫描查找第第5 5列元素列元素第六次扫描查找第六次扫描查找第第6 6列元素列元素转置运算算法图示转置运算算法图示结束第 32 页5 52 2 矩阵的压缩存储矩阵的压缩存储时间复杂度分析时间复杂度分析算法的基本操作为将算法的基本操作为将M.data中的中的三元组赋值到三元组赋值到T.dataT.data，是是在两个循环中完成的，故算法的时间复杂度为在两个循环中完成的，故算法的时间复杂度为O(nu u tu u) )我们知道，若用二维数组存储矩阵，转置算法的时间复我们知道，若用二维数组存储矩

35、阵，转置算法的时间复杂度为杂度为O（mumu nunu）。当非零元的个数。当非零元的个数tu u和矩阵元素个数和矩阵元素个数mumu nunu同数量级时，转置运算算法同数量级时，转置运算算法1的时间复杂度为的时间复杂度为O（mumu nunu nu u）。）。由此可见：在这种情况下，用由此可见：在这种情况下，用三元组顺序表存储矩阵，三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于适于tumumu nunu的情况的情况。 该算法效率不高的原因是：对为实现该算法效率不高的原因是：对为实现M M到到T T的转置，该

36、的转置，该算法算法对对M.data进行了多次扫描。能否在对进行了多次扫描。能否在对M.data一次扫描的过程中，一次扫描的过程中，完成完成M到到T的转置？的转置？结束第 33 页5 52 2 矩阵的压缩存储矩阵的压缩存储快速转置算法快速转置算法下面介绍转置运算算法称为快速转置算法下面介绍转置运算算法称为快速转置算法,分析分析:在在M.data中，中，M的各列非零元对应的三元组是以行为主的各列非零元对应的三元组是以行为主序存储的，故序存储的，故M的各列非零元对应的三元组存储位置不是的各列非零元对应的三元组存储位置不是“连连续续”的。然而，的。然而，M的各列非零元三元组的存储顺序却与各列非的各列非

37、零元三元组的存储顺序却与各列非零元在零元在M中的顺序一致。中的顺序一致。如：如：M的第一列非零元素是的第一列非零元素是-3、15，它们对应的三元组在，它们对应的三元组在M.data中的存储顺序也是（中的存储顺序也是（3，1，-3）在前（）在前（6，1，15）后。）后。如果能先求得如果能先求得M各列第一个非零元三元组在各列第一个非零元三元组在T.data中的位置中的位置，就能在对，就能在对M.data一次扫描的过程中，完成一次扫描的过程中，完成M到到T的转置：的转置：对对M.data一次扫描时，一次扫描时，首先遇到各列的第一个非零元三元首先遇到各列的第一个非零元三元组，可按先前求出的位置，将其放

38、至组，可按先前求出的位置，将其放至T.data中，当再次遇到各中，当再次遇到各列的非零元三元组时，只须顺序放到对应列元素的后面。列的非零元三元组时，只须顺序放到对应列元素的后面。结束第 34 页5 52 2 矩阵的压缩存储矩阵的压缩存储 M M= = 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 015 0 0 -7 0

39、0 0i j vi j v1 12 23 34 45 56 67 78 83 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 14M.dataM.data6 67 78 8M.M.mumuM.M.nunuM.M.tutuM的各列非零元三元组的各列非零元三元组的的存储顺序存储顺序与各列与各列非零元在非零元在M中的顺序一致中的顺序一致结束第 35 页5 52 2 矩阵的压缩存储矩阵的压缩存储i j v1 12 23 34 45 56 67 783 1 -36 1 15

40、1 2 125 2 181 3 94 3 246 4 -73 6 14M.data678M.muM.nuM.tui j v123456782 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 18T.data768T.muT.nuT.tu各列第一个非零元三元组按先前求出的位置，放至T.data中各列后续的非零元三元组，顺序放到对应列元素的后面结束第 36 页5 52 2 矩阵的压缩存储矩阵的压缩存储辅助向量辅助向量num、cpos为先求得为先求得M各列第一个非零元三元组在各列第一个非零元三元组在T.data中的位置。引入两个辅中的位置。引入两个辅助向量助向量

41、num、cpos：numcol：存储第存储第col列非零元个数列非零元个数cposcol：存储第存储第col列第一个非零元三元组在列第一个非零元三元组在T.data中的位置中的位置cposcol的计算方法：的计算方法：cpos1=1cposcol=cposcol-1+numcol-12coln例例 矩阵矩阵M Mcolnumcolcpotcol1234567 22811001352784539结束第 37 页5 52 2 矩阵的压缩存储矩阵的压缩存储快速转置算法主要步骤：1 求M中各列非零元个数num ;2 求M中各列第一个非零元在T.data中的下标cpos ;3 对M.data进行一次扫描

42、， 遇到col列的第一个非零元三元组时，按cposcol 的位置，将其放至T.data中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面;结束第 38 页5 52 2 矩阵的压缩存储矩阵的压缩存储快速转置算法Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) /采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol=0; for (t=1; t=M.tu; +t

43、) +numM.datat.j; /求M中每一列非零元个数 /求第 col列中第一个非零元在T.data中的序号 cpot1=1; for(col=2; col=M.tu; +col) cpotcol=cpotcol-1+numcol-1;for(p=1;pM.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;/for/ifreturnOK;/FastTransposeSMatrix结束第 39 页colnumcolcpotcol1 2 3 4 5

44、 6 7228110013527891 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vi j vM.dataT.data1 2 122 1 12第2列第一个非零元在b中的位置1 3 9第3列第一个非零元在b中的位置3 1 93 1 -31 3 -33 6 146 3 144 3 243 4 245 2 182 5 186 1 151 6 156 4 -74 6 -74第2列第二个非零元在b中的位置65快速转置算法图示第3列第二个非零元在b中的位置第1列第一个非零元在b中的位置2793第4 列第一个非零元在b中的位置求各列第1个非零元在b中位

45、置求各列非零元个数扫描M.data实现M到T 的转置5 52 2 矩阵的压缩存储矩阵的压缩存储结束第 40 页用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为:O(munu)for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;结束第 41 页5 52 2 矩阵的压缩存储矩阵的压缩存储时间复杂度分析时间复杂度分析 该算法利用该算法利用两个辅助向量两个辅助向量num、cpos，实现了实现了对对M.data一次扫描完成一次扫描完成M到到T的转置。的转置。从时间上看，算法中有四个并列的单循环，循环次从时间上

46、看，算法中有四个并列的单循环，循环次数分别为数分别为mu、tu，因而总的时间复杂度为，因而总的时间复杂度为O（nu+tu)，在在M的非零元个数的非零元个数tu和和mumu nunu同等数量级时，其时间复同等数量级时，其时间复杂度为杂度为O(mumu nunu) )，和经典转置算法的时间复杂度相同。，和经典转置算法的时间复杂度相同。由此可见，只有当由此可见，只有当tumumu nunu时，使用时，使用快速转置算法快速转置算法才有意义。才有意义。结束第 42 页 三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩便于进行依行顺序处理的

47、矩阵运算阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表结束第 43 页#define MAXMN 500 typedefstruct Triple dataMAXSIZE + 1; intrposMAXMN+1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos, 其值在稀疏矩阵的初始化函数中确定。rposi第i行 第一个非零值的位置结束第 44 页例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M, int

48、r, int c) p = M.rposr;/rposi第i行第一个非零值的位置 while (M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; elsereturn 0; / value结束第 45 页矩阵乘法的精典算法矩阵乘法的精典算法:for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为其时间复杂度为:O(m1n2n1)结束第 46

49、 页 Q初始化; if Q是非零矩阵 / 逐行求积for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data；/ for arow/ if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N）的过程可大致描述如下：的过程可大致描述如下：结束第 47 页Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) returnERROR; Q.mu

50、 = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow/ if returnOK; / MultSMatrix结束第 48 页 ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元 brow=M.datap.j; if (brow M.nu ) t = N.rposbrow+1; else

51、t = N.tu+1 /t存放上界 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) returnERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M结束第 49 页分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非

52、零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是 (M.mu N.nu+M.tu N.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu = Mmn， N中非零元的个数 N.tu = Nnp，(带入上式)相乘算法的时间复杂度就是 (mp(1+nMN) ，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于 (mp)。结束第 50 页三、三、十字链表十字链表M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4

53、 52 2-13 1 2 结束第 51 页 小 结 1 矩阵压缩存储是指为多个值相同的元素分配一个 存储空间，对零元素不分配存储空间； 2 特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系； 3 稀疏矩阵的压缩存储除了要保存零元素的值外，还要保存零元素在矩阵中的位置； 5 52 2 矩阵的压缩存储矩阵的压缩存储结束第 52 页习题八1 P32 5.7 2 p35 5.25 习题取自数据结构题集 C语言版 严尉敏等编 清华大学出版社第五章第五章 习习 题题结束第 53 页53广义表广义表5.3广义表5.3.1广义表的概念5.3.2广义表的存储结构*5.3.

54、3m 元多项式的表示*5.3.4广义表的递归算法结束第 54 页基本内容基本内容1 广义表的概念； 2 广义表的基本操作； 3 广义表的存储结构；学习要点学习要点 了解广义表的结构特征及存储方法；53广义表广义表结束第 55 页5.3.1广义表的概念广义表的概念1什么是广义表什么是广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (1, 2。n)。其中i其可以是单个元素，也可以是广义表。53广义表广义表说明 1）广义表的定义是一个递归定义，因为在描述）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；广义表时又用到了广义表；2）在线性表中数据元素是

55、单个元素，而在广义）在线性表中数据元素是单个元素，而在广义表中，表中，元素可是以单个元素称为原子，也可以是元素可是以单个元素称为原子，也可以是广义表，称为广义表的子表；广义表，称为广义表的子表；3）n是广义表长度；是广义表长度；结束第 56 页53广义表广义表4）下面是一些广义表的例子；）下面是一些广义表的例子；A=()空表，表长为空表，表长为0；B=(e)B中只有一个元素中只有一个元素e，表长为表长为1；C=(a,(b,c,d)C的表长为的表长为2，两个元素分别为，两个元素分别为a和子表（和子表（b,c,d)；D=(A,B,C)D的表长为的表长为3，它的三个元素，它的三个元素A，B，C广义表

56、；广义表；5）对非空广义表：称第一个元素为对非空广义表：称第一个元素为L的表头，其余元素组成的表称为的表头，其余元素组成的表称为LS的表尾；的表尾；B=(e)表头：表头：e表尾表尾()C=(a,(b,c,d)表头：表头：a表尾表尾(b,c,d)D=(A,B,C)表头：表头：A表尾表尾(B,C)若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表确定广义表结束第 57 页2广义表的基本操作广义表的基本操作 1）创建空的广义表创建空的广义表L；2）销毁广义表销毁广义表L；3）已有广义表已有广义表L，由由L复制得到广义表复

57、制得到广义表T；4）求广义表求广义表L的长度；的长度；5）求广义表求广义表L的深度；的深度；6）判广义表判广义表L是否为空；是否为空；7）取广义表取广义表L的表头；的表头；8）取广义表取广义表L的表尾；的表尾；9）在在L中插入元素作为中插入元素作为L的第一个元素；的第一个元素；10）删除广义表）删除广义表L的第一个元素，并的第一个元素，并e用返回其值；用返回其值；11）遍历广义表）遍历广义表L，用函数用函数visit()处理每个元素；处理每个元素；53广义表广义表结束第 58 页5.4广义表的类型定义广义表的类型定义ADTGlist 数据对象数据对象：Dei | i=1,2,.,n; n0;

58、eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2inADT Glist基本操作基本操作:结束第 59 页广义表是递归递归定义的线性结构线性结构， LS = ( 1, 2, , n )其中：i 或为原子 或为广义表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )结束第 60 页广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中: E=(a, (b, c) F=(d, (

59、e)DEFa( )d( )bce结束第 61 页广义表广义表LS=( 1, 2, n)的结构特点的结构特点:1) 广义表中的数据元素有相对次序次序;2) 广义表的长度长度定义为最外层包含元素个数;3) 广义表的深度深度定义为所含括弧的重数; 注意:“原子”的深度为 0; “空表”的深度为 1。4) 广义表可以共享共享;5) 广义表可以是一个递归递归的表; 递归表的深度是无穷值，长度是有限值。结束第 62 页6) 任何一个非空广义表非空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分例如例如

60、: D = ( E, F ) = (a, (b, c)，F )Head( D) = E Tail( D ) = ( F )Head(E) = a Tail(E ) = ( ( b, c) )Head(b,c) ) = ( b, c) Tail( (b,c) ) = ( )Head(b,c) = b Tail( (b,c) ) = ( c )Head( (c) ) = c Tail( (c) ) = ( )结束第 63 页 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作基本操作 状态函数状态函数 GListLength(L); GListDepth(L); GLis