《数据结构 第四章 数组串和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构 第四章 数组串和广义表.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4 4章章数组、串和广义表1本章要点本章要点n数组的存储方法、数组元素地址计算；数组的存储方法、数组元素地址计算；n特殊矩阵、稀疏矩阵压缩存储；特殊矩阵、稀疏矩阵压缩存储；n串的概念及相关操作的定义；串的概念及相关操作的定义；n串的顺序结构、堆存储结构和链式存储结构表示串的顺序结构、堆存储结构和链式存储结构表示及有关操作及有关操作n广义表的概念、结构和存储方法。广义表的概念、结构和存储方法。2数数组组是是许许多多编编程程语语言言中中的的一一个个重重要要组组成成部部分分，几几乎乎所所有有语语言言都都提提供供数数组组结结构构，但但不不同同的的语语言言有有不不同同的的实实现现方方式式。数数组组可
2、可以以看看成成线线性性表表的的一一种种特特殊殊情情况况，而而串串可可以以看看成成是是数数组组的的一一个个特特例例，串串中中存存放放的的是是字字符符序序列列，这这里里的的字字符符可可以以是是数数字字、字字母母或或符符号号，在在字字符符串串上上可可以以进进行行不不同同的的操操作作。广广义义表表是是线线性性表表的的另另外外一一种种特特例例，广广义义表表中中的的元元素素可可以以是是原原子子，也也可可以以是是其其他他广广义义表表。在在本本章章中中，对对这这些些概概念念进进行行研研究究，并并分分析析它它们们的的实实现现方式以及效率。方式以及效率。3n数组是许多编程语言中的一个重要组成部分，几乎数组是许多编
3、程语言中的一个重要组成部分，几乎所有语言都提供数组结构，但不同的语言有不同的所有语言都提供数组结构，但不同的语言有不同的实现方式。数组可以看成线性表的一种特殊情况。实现方式。数组可以看成线性表的一种特殊情况。n串可以看成是数组的一个特例，串中存放的是字符串可以看成是数组的一个特例，串中存放的是字符序列，这里的字符可以是数字、字母或符号，在字序列，这里的字符可以是数字、字母或符号，在字符串上可以进行不同的操作。符串上可以进行不同的操作。n广义表是线性表的另外一种特例，广义表中的元素广义表是线性表的另外一种特例，广义表中的元素可以是原子，也可以是其他广义表。可以是原子，也可以是其他广义表。44.1
4、 4.1 数组数组 一.数组的概念及其抽象数据类型n数组(Array)(Array)是是指指由由相相同同类类型型的的若若干干数数据据占占有有连连续续的的存储空间。存储空间。n数数据据结结构构中中的的数数组组与与高高级级语语言言中中的的数数组组既既有有共共同同点点，也有不同点。也有不同点。通通俗俗的的来来说说，数数据据结结构构中中的的二二维维数数组组有有点点类类似似于于高高等等代代数数中中的的二二维维矩矩阵阵，通通过过元元素素的的行行下下标标与与列列下下标标来来使使用用这这个个元元素素，可可以以利利用用下下标标来来找找到到该该元元素素参参与与数数学学计计算算，或或者者是是给给该单元赋值。该单元赋
5、值。严严格格的的来来说说，数数据据结结构构中中的的二二维维数数组组中中的的元元素素可可以以在在行行中中有前驱与后继关系，在列中同样也有前驱与后继的关系。有前驱与后继关系，在列中同样也有前驱与后继的关系。5n数组的抽象数据类型定义数组的抽象数据类型定义可形式地定义为：可形式地定义为：ADT Array ADT Array 数据对象：数据对象：S S是一个集合，它是元素的取值范围，是一个集合，它是元素的取值范围，a a为为数组中的元素，并且数组中的元素，并且a a S S，n n为数组的维数，为数组的维数，b bi i为为数组的第数组的第i i维的长度，维的长度，i=1i=1，2 2，n n 数据
6、关系：数据关系：R=RR=R1 1,R,R2 2,R,Rn n，6 基本操作：基本操作：CreateArray(&A,b1,b2,bn)CreateArray(&A,b1,b2,bn)/创建数组创建数组 初始条件：初始条件：n n表示数组的维数，表示数组的维数，b1,b2,bnb1,b2,bn为每维数为每维数组的长度组的长度 操作结果：返回数组对象操作结果：返回数组对象 DestroyArray(&A)DestroyArray(&A)/销毁数组销毁数组 初始条件：输入数组对象初始条件：输入数组对象A A 操作结果：将数组对象操作结果：将数组对象A A在内存中释放在内存中释放 GetValue(
7、A,index1,index2,indexn)GetValue(A,index1,index2,indexn)/取值取值 初始条件：数组对象初始条件：数组对象A A以及数组对象的下标以及数组对象的下标 操作结果：如果数组下标在许可范围内，返回数组值，返操作结果：如果数组下标在许可范围内，返回数组值，返回错误回错误 AssignValue(&A,value,index1,index2,indexn)AssignValue(&A,value,index1,index2,indexn)/赋值赋值 初始条件：数组对象初始条件：数组对象A A、数值、数值valuevalue以及下标以及下标 操作结果：下
8、标不越界，就对指定的数组单元进行赋值操作结果：下标不越界，就对指定的数组单元进行赋值ADT ArrayADT Array7nn n维数组中含有维数组中含有 个数据元素个数据元素,每个元素都受着每个元素都受着n n个个关系的约束。在每个关系中关系的约束。在每个关系中,元素元素就其单个关系而言就其单个关系而言,这这n n个关系仍是线性关系。个关系仍是线性关系。和线性表一样和线性表一样,所有的数据元素都必须属于同一数据类型所有的数据元素都必须属于同一数据类型。数组中的每个数据元素都对应于一组下标数组中的每个数据元素都对应于一组下标(j(jl l,j,j2 2,j,jn n););每个下标的取值范围是
9、每个下标的取值范围是0=j0=ji i=b=bi i-1,b-1,bi i称为第称为第i i维的长度维的长度(i(il,2,n)l,2,n)。显然显然,当当n=1n=1时时,n,n维数组就退化为定长的线性表。反之维数组就退化为定长的线性表。反之,n,n维数组也可以看成是线性表的推广。维数组也可以看成是线性表的推广。我我们们也也可可以以从从另另一一个个角角度度来来定定义义n n维维数数组组：一一个个n n维维数数组可以看成是以组可以看成是以(n-1)(n-1)维数组为表元素的线性表。维数组为表元素的线性表。都有一个直接后继元素。都有一个直接后继元素。8二.数组的顺序实现n数数组组不不进进行行插插
10、入入与与删删除除运运算算，只只是是对对数数组组的的元元素素进进行行存存取取操操作作。数数组组对对象象一一旦旦创创建建后后，数数组组中中元元素素与与元元素素之之间间的的关关系系就就不不再再发发生生改改变，是变，是静态结构。计计算算机机内内存存是是一一维维结结构构，而而普普通通数数组组一一般般是是多多维维数数组组，二二维维、三三维甚至四维以上维甚至四维以上。一一维维数数组组(向向量量)最最常常用用数数据据类类型型。同同一一数数组组的的不不同同元元素素通通过过不不同同的的下标标识。如：下标标识。如：(a(a1 1,a,a2 2,a,an n)二二维维数数组组Amn可可以以看看成成是是这这样样一一个个
11、定定长长线线性性表表:它它的的每每个个数数据据元元素素也也是是一一个定长线性表：个定长线性表：m个行向量组成的向量，或由个行向量组成的向量，或由n个列向量组成的向量。个列向量组成的向量。n 如如:A=a:A=aijij|0=i=m-1,0=j=n-1,|0=i=m-1,0=j=n-1,可以表示成可以表示成:A=(A=(0 0,1 1,p p)(p=m-1()(p=m-1(列顺序列顺序),),或或p=n-1(p=n-1(行顺序行顺序)其中每个数据元素其中每个数据元素 j j 是一个列向量形式的线性表是一个列向量形式的线性表(p=m-1)(p=m-1)j j=(a=(a0j0j,a,aljlj,a
12、,am-1,jm-1,j)0=j=n-1)0=j=n-1或者或者 i i是一个行向量形式的线性表是一个行向量形式的线性表(p=n-1)(p=n-1)i i=(a=(ai0i0,a,ai1i1,a,ai,n-1i,n-1)0=i=m-1)0=i=m-19n如：如：A=A=其中：其中：或或=，其中：，其中：10元素的存储位置由由于于数数组组是是静静态态结结构构,一一旦旦规规定定了了它它的的维维数数和和各各维维的的长长度度,便便可可为为它它分分配配存存储储空空间间。反反之之,只只要要给给出出一一组组下下标标便便可可求求得得相相应应数数组组元元素素的的存存储储位位置置。以以行行序序为为主主序序的的存存
13、储结构：储结构：假假设设每每个个数数据据元元素素占占m m个个存存储储单单元元,则则二二维维数数组组A A中中任任一元素一元素a aijij的存储位置可由下式确定的存储位置可由下式确定 LOC(i,j)LOC(i,j)LOC(0,0)+(bLOC(0,0)+(b2 2i+j)mi+j)m其其中中，式式中中LOC(i,j)LOC(i,j)是是a aijij的的存存储储位位置置;LOC(0,0)LOC(0,0)是是a a0000的的存存储储位位置置,即即二二维维数数组组A A的的起起始始存存储储位位置置,亦亦称称为为基基地地址或基址。址或基址。11将将此此公公式式推推广广到到一一般般情情况况,可可
14、得得到到n n维维数数组组的的数数据据元元素素存存储储位位置置的计算公式的计算公式:LOC(j1,j2,.,jn)=LOC(0,0,.,0)+(b2bnj1+b3bnj2+bnjn-1+jn)L=LOC(0,0,.,0)+也可缩写成也可缩写成:LOC(jLOC(j1 1,j,j2 2,.,j,.,jn n)=LOC(0,0,.,0)+)=LOC(0,0,.,0)+其中其中c cn n=L,c=L,ci-1i-1=b=bi ic ci i,1i=n,1i=n。称为。称为n n维数组的映象函数。维数组的映象函数。12n在在C C语语言言中中,一一个个二二维维数数组组类类型型可可以以定定义义为为其其
15、分分量量类类型型为为一一维维数组类型的数组类型的维数组类型维数组类型(行顺序行顺序)：typedef E1emType Array2mntypedef E1emType Array2mn；等价于：等价于：typedef ElemType Arraylntypedef ElemType Arrayln；typedef Arrayl Array2mtypedef Arrayl Array2m；n数组的顺序存储表示描述如下：数组的顺序存储表示描述如下：typedef int ElemType;typedef int ElemType;typedeftypedef struct array struc
16、t array ElemType*data;/ElemType*data;/数据存储区域数据存储区域 int dimension;/int dimension;/数组的维数数组的维数 int*boundary;/int*boundary;/每维的长度每维的长度 int*cof;/int*cof;/预存的系数预存的系数 *ArrayPT;*ArrayPT;13基本操作的算法描述(1)创建数组。根据给定的维数以及每维的长度创建数组。根据给定的维数以及每维的长度,创建一个数组对创建一个数组对象象,并数组进行赋初值。注意维并数组进行赋初值。注意维数数dimdim与与boundsbounds的长度要相等
17、。的长度要相等。int CreatArray(ArrayPT&a,int dim,int bounds)int CreatArray(ArrayPT&a,int dim,int bounds)int i,j;int i,j;int total=0;int total=0;if(dim 1)if(dim 1)printf(printf(数组维数不能小于数组维数不能小于1);1);return 1;return 1;for(i=0;i dim;i+)for(i=0;i dim;i+)if(boundsi=0)if(boundsidimension=dim;a-dimension=dim;a-bou
18、ndary=(int*)malloc(dim*sizeof(int);a-boundary=(int*)malloc(dim*sizeof(int);14 if(a-boundary=NULL)if(a-boundary=NULL)printf(printf(空间不够空间不够););return 1;return 1;for(i=0;idim;i+)for(i=0;iboundaryi=boundsi;a-boundaryi=boundsi;a-cof=(int*)(malloc(dim*sizeof(int);a-cof=(int*)(malloc(dim*sizeof(int);/我们假定
19、每维长度都不太大，否则这里需要使用我们假定每维长度都不太大，否则这里需要使用unsigned,unsigned,unsigned longunsigned long if(a-cof=NULL)if(a-cof=NULL)printf(printf(空间不够空间不够);return 1;);return 1;a-cof0=1;a-cof0=1;for(i=1;i dim;i+)for(i=1;i cofi=a-cofi-1*boundsi-1;a-cofi=a-cofi-1*boundsi-1;total=a-cofdim-1*boundsdim-1;total=a-cofdim-1*boun
20、dsdim-1;a-data=(ElementType a-data=(ElementType*)malloc(total*sizeof(ElemType);*)malloc(total*sizeof(ElemType);if(a-data=NULL)if(a-data=NULL)printf(printf(空间不够空间不够);return 1;);return 1;return 0;return 0;15(2)(2)销毁数组。释放数组对象所占的内存空间。销毁数组。释放数组对象所占的内存空间。int DestroyArray(ArrayPT&a)int DestroyArray(ArrayPT
21、&a)if(a-data=NULL)return 1;if(a-data=NULL)return 1;if(a-boundary=NULL)return 1;if(a-boundary=NULL)return 1;if(a-cof=NULL)return 1;if(a-cof=NULL)return 1;free(a-data);free(a-data);free(a-boundary);free(a-boundary);free(a-cof);free(a-cof);a-data=NULL;a-data=NULL;a-boundary=NULL;a-boundary=NULL;a-cof=N
22、ULL;a-cof=NULL;return 0;return 0;16三.矩阵的压缩存储n矩阵：n矩阵的存储：用用高高级级语语言言编编制制程程序序时时,都都是是用用二二维维数数组组来来存存储储矩矩阵阵元元素素。有有的的程程序序设设计计语语言言中中还还提提供供了了各各种种矩矩阵阵运运算算,用用户户使使用用时都很方便。时都很方便。n工工程程计计算算中中经经常常出出现现一一些些阶阶数数很很高高的的矩矩阵阵,或或绝绝大大多多数数是是具具有有相相同同值值的的元元素素，或或值值为为0的的元元素素。有有时时为为了了节节省省存存储储空空间间,可可以以对对这类矩阵进行压缩存储。这类矩阵进行压缩存储。n压缩存储：
23、是是指指为为多多个个值值相相同同的的元元素素只只分分配配一一个个存存储储空空间间;对对零零元素不分配空间。元素不分配空间。n如如果果这这些些值值相相同同的的元元素素或或零零元元素素的的分分布布有有一一定定规规律律,则则我我们们称称此此类矩阵为类矩阵为特殊矩阵；n如如果果这这些些值值相相同同或或值值为为零零的的元元素素非非常常之之多多，而而且且分分布布没没有有规规律律,或或此此类类元元素素很很多多,则则称称之之为为稀疏矩阵。下下面面分分别别讨讨论论它它们们的的压压缩缩存储。存储。17若若n阶矩阵阶矩阵A中的元素满足下述性质：中的元素满足下述性质：aij=aji 0=i,j=n-1则称为则称为n阶
24、阶对称矩阵。对对于于对对称称矩矩阵阵,我我们们可可以以为为每每一一对对对对称称元元素素分分配配一一个个存存储储空空间间。不不失失一一般般性性,我我们们可可以以行行序序为为主主序序存存储储其其下下三三角角(包包括括对对角角线线)中中的的元素元素,则可将则可将n2个元素压缩存储到个元素压缩存储到n(n+1)/2个元素的存储空间中。个元素的存储空间中。假假设设以以一一维维数数组组san(n+1)/2san(n+1)/2作作为为n n阶阶对对称称矩矩阵阵A A的的存存储储结结构构,则则saksak和矩阵元和矩阵元a aijij之间存在着一一对应的关系之间存在着一一对应的关系:若若ijij，k=ik=i
25、(i+1)/2+j 0kn(n+1)/2(i+1)/2+j 0kn(n+1)/2 若若i ij j，k=jk=j(j+1)/2+i 0kn(n+1)/2(j+1)/2+i 0kn(n+1)/2 令令I=max(i,j)I=max(i,j)，J=min(i,j)J=min(i,j)，则，则k k和和i i，j j的对应关系可统一为的对应关系可统一为:k=I k=I(I+1)/2+J 0kn(n+1)/2(I+1)/2+J 0k(k-1)/2|i-j|(k-1)/2，则元素，则元素a aijij=0=0。对对于于上上述述矩矩阵阵，可可以以用用一一个个二二维维数数组组，当当然然也也可可以以用用一一维
26、维数数组组将将非非零零元元素素压压缩缩存存储储起起来来。压压缩缩矩矩阵阵的的关关键键是是找找出出原原矩矩阵阵的的元元素素与经过压缩之后的数组元素之间的关系。与经过压缩之后的数组元素之间的关系。条对角线n行n列一般情形一般情形a00 a01a10 a11 a12 an-2,n-2 an-2,n-1an-1,n-2 an-1,n-100三对角矩阵三对角矩阵203.稀疏矩阵的压缩存储稀疏矩阵：相相同同值值或或值值为为零零的的元元素素个个数数相相对对于于整整个个矩矩阵阵来来说说比比较多时较多时，且分布没有一定规律。，且分布没有一定规律。稀疏因子：=t/(m=t/(mn),n),在在m mn n的的矩矩
27、阵阵中中,有有t t个个元元素素不不为为零零。通通常常认为认为=0.05=0.05时称为稀疏矩阵。时称为稀疏矩阵。矩矩阵阵运运算算的的种种类类很很多多,在在下下列列抽抽象象数数据据类类型型稀稀疏疏矩矩阵阵的的定定义义中中,只列举了几种常见的运算。只列举了几种常见的运算。抽象数据类型稀疏矩阵的定义如下抽象数据类型稀疏矩阵的定义如下:ADT ADT SparseMatrixSparseMatrix 数据对象数据对象:D=a:D=aijij|i=l,2,m;j=1,2,n;|i=l,2,m;j=1,2,n;a aijij 元素集元素集ElemSet,mElemSet,m和和n n分别称为矩阵的行数和
28、列数分别称为矩阵的行数和列数 数据关系数据关系:R=ROWS,COLS:R=ROWS,COLS ROWS=R ROWS=Ri i|i=1,2,.,m,COLS=C|i=1,2,.,m,COLS=Cj j|j=1,2,n,|j=1,2,n,R Ri i=a=|j=1,n-1,i=1,2,m|j=1,n-1,i=1,2,m Cj=a Cj=|i=1,2,m-1,j=1,n|i=1,2,m-1,j=1,n21CreateSparesMatrix()CreateSparesMatrix()/创建稀疏矩阵创建稀疏矩阵 初始条件：无初始条件：无 操作结果：创建一个稀疏矩阵对象操作结果：创建一个稀疏矩阵对象
29、OutputSparesMatrix(M)OutputSparesMatrix(M)/稀疏矩阵输出稀疏矩阵输出 初始条件：输入矩阵对象初始条件：输入矩阵对象 操作结果：将数据矩阵的数据进行输出操作结果：将数据矩阵的数据进行输出MatrixAdd(M1,M2)MatrixAdd(M1,M2)/稀疏矩阵稀疏矩阵相加相加 初始条件：输入两个矩阵初始条件：输入两个矩阵 操作结果：该函数返回一个两个矩阵之和的矩阵对象操作结果：该函数返回一个两个矩阵之和的矩阵对象MatrixSubstract(M1,M2)MatrixSubstract(M1,M2)/稀疏矩阵稀疏矩阵相减相减 初始条件：输入两个矩阵初始条
30、件：输入两个矩阵 操作结果：该函数返回一个两个矩阵之差的矩阵对象操作结果：该函数返回一个两个矩阵之差的矩阵对象MatrixTimes(M1,M2)MatrixTimes(M1,M2)/稀疏矩阵稀疏矩阵相乘相乘 初始条件：输入两个矩阵初始条件：输入两个矩阵 操作结果：该函数返回一个两个矩阵之积的矩阵对象操作结果：该函数返回一个两个矩阵之积的矩阵对象MatrixTranspose(M)MatrixTranspose(M)/稀疏矩阵稀疏矩阵转置转置 初始条件：输入一个矩阵初始条件：输入一个矩阵 操作结果：返回该矩阵的转置矩阵操作结果：返回该矩阵的转置矩阵 ADT SparseMatrix ADT S
31、parseMatrix基本操作基本操作:22按照压缩存储的概念按照压缩存储的概念,只存储稀疏矩阵的非零元。因此只存储稀疏矩阵的非零元。因此,除了存除了存储非零元的值之外储非零元的值之外,还必须同时记下它所在行和列的位置还必须同时记下它所在行和列的位置(r,c)(r,c)。一个一个三元组可以可以唯一确定了矩阵唯一确定了矩阵A A的一个非零元。的一个非零元。因此因此,稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如例如,上图中矩阵上图中矩阵M M可用下列三元组表来表示：可用下列三元组表来表示：(1,6,1),(2,2,1),(3,3,2),(
32、5,1,1),(6,4,9)(1,6,1),(2,2,1),(3,3,2),(5,1,1),(6,4,9)再再加上加上(7,7)(7,7)这一对行、列值这一对行、列值即可。即可。23(1)(1)三元组数组表示三元组数组表示三元组数组表示稀疏矩阵是一种最简单的方法，该结构的空间三元组数组表示稀疏矩阵是一种最简单的方法，该结构的空间利用效率比较高利用效率比较高。下面是我们定义的稀疏矩阵表示：下面是我们定义的稀疏矩阵表示：typedef struct typedef struct int r,c;int r,c;Elemtype value;Elemtype value;Triple;Triple;
33、typedef struct typedef struct Triple*data;Triple*data;int row_num,col_num,triple_num;int row_num,col_num,triple_num;TSMatrix;TSMatrix;typedef TSMatrix*TSMATRIX;typedef TSMatrix*TSMATRIX;假定按行优先来存放三元组，存完一行，再往下存储一行。假定按行优先来存放三元组，存完一行，再往下存储一行。该方法的该方法的优点是是：便于矩阵的加法、减法、乘法运算，但是会便于矩阵的加法、减法、乘法运算，但是会减低矩阵转置的运行效率
34、减低矩阵转置的运行效率。24矩阵加法（减法）运算根据矩阵加法的定义，就是将这两个矩阵中的对应元素相加，根据矩阵加法的定义，就是将这两个矩阵中的对应元素相加，并相加结果存放到新矩阵中，但是这里考虑的矩阵时稀疏矩阵，只并相加结果存放到新矩阵中，但是这里考虑的矩阵时稀疏矩阵，只需需遍历这两个矩阵的非零元遍历这两个矩阵的非零元即可。即可。为了确保开辟的数据空间能够存放矩阵为了确保开辟的数据空间能够存放矩阵McMc的三元组数组的三元组数组,我们可我们可以将这两个矩阵的数组长度加起来以将这两个矩阵的数组长度加起来,作为新的数组长度。矩阵的相作为新的数组长度。矩阵的相加过程与前面讨论过的一元多项式相加类似加
35、过程与前面讨论过的一元多项式相加类似,不同的是一元多项式不同的是一元多项式中只有一个指数项中只有一个指数项,而矩阵的三元组的每个元素有行和列两上变量而矩阵的三元组的每个元素有行和列两上变量,所以在相加过程中所以在相加过程中,在确保行优先顺序存储的情况下在确保行优先顺序存储的情况下,设置三个变量设置三个变量i i、j j、count,count,分别表示分别表示MaMa、MbMb、McMc中三元组的下标中三元组的下标,起始时分别指起始时分别指向三元组的首元素向三元组的首元素,然后分三种情况处理：然后分三种情况处理：如果当前两个三元组的行标不同：如果当前两个三元组的行标不同：如果行标相同，则判断列
36、标是否相同，如果列标不同：如果行标相同，则判断列标是否相同，如果列标不同：如果行标相同，列标也相同：如果行标相同，列标也相同：加法次数为这两个矩阵中非零元个数的最大值。加法次数为这两个矩阵中非零元个数的最大值。25对对于于一一个个m m n n的的矩矩阵阵M,M,它它的的转转置置矩矩阵阵T T是是一一个个n n m m的的矩矩阵阵,且且T(i,j)=M(j,i),1T(i,j)=M(j,i),1 i i n,ln,l j j m m。一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。将将每每个个三三元元组组的的行行与与列列下下标标进进行行互互换换，然然后后按按照照行行
37、优优先的原则来重新先的原则来重新排序即可。排序即可。1)1)将矩阵的行列值相互交换将矩阵的行列值相互交换;2)2)将每个三元组中的将每个三元组中的 i i和和j j相互调换相互调换;3)3)重排三元组之间的次序便可实现矩阵的转置。重排三元组之间的次序便可实现矩阵的转置。前前2 2条条是是容容易易做做到到的的,关关键键是是如如何何实实现现第第3 3条条。即即如如何何使使tb.datatb.data中的三元组是以中的三元组是以T T的行的行(M(M的列的列)为主序依次排列的。为主序依次排列的。转置运算26tata与与tbtb是是TSMatrixTSMatrix型型的的变变量量,那那么么可可以以通通
38、过过比比较较这这两两个个三三元元组组的行下标和列下标的大小来确定的行下标和列下标的大小来确定tata和和tbtb的大小的大小,可按如下规则进行：可按如下规则进行：如如果果满满足足下下列列两两个个条条件件之之一一，那那么么tata大大于于tb tb：tata的的行行下下标标大大于于tbtb的的行行下下标标，或或者者tata和和tbtb的的行行下下标标相相等等但但tata的的列列下下标标大大于于tbtb的列下标的列下标 ；如如果果满满足足下下列列两两个个条条件件之之一一，那那么么tata小小于于tb tb：tata的的行行下下标标小小于于tbtb的的行行下下标标，或或者者tata和和tbtb的的行
39、行下下标标相相等等但但tata的的列列下下标标小小于于tbtb的列下标的列下标 ；如如果果满满足足下下列列条条件件，那那么么tata等等于于tb tb：即即tata的的行行下下标标、列列下下标均等于标均等于tbtb的行下标和列下标的行下标和列下标 。除除此此以以外外，也也可可以以采采取取稳稳定定的的排排序序方方法法，把把交交换换后后的的行行作作为为关关键键字字进进行行排排序序；或或按按照照矩矩阵阵M M的的列列序序方方式式进进行行转转置置；以以及及通通过过设设置置辅辅助助变变量量，将将t ta中中的的元元素素次次序序进进行行转转置置,直直接接置置入入tb中中恰恰当当的的位位置置的的快速转置快速
40、转置方式方式。27稀疏矩阵的乘积n稀疏矩阵稀疏矩阵A A与与B B的乘积实现起来比较复杂的乘积实现起来比较复杂可以利用一种空间效率与空间效率平衡的算法来实现。就是可以利用一种空间效率与空间效率平衡的算法来实现。就是先将矩阵先将矩阵B B进行转置，使得行变成列，列变成行，生成矩阵进行转置，使得行变成列，列变成行，生成矩阵C C，然后进行试计算，即矩阵，然后进行试计算，即矩阵A A的行与矩阵的行与矩阵C C的行对应元素进行的行对应元素进行相乘，并将乘积相加，估计矩阵乘积中有多少个非零元，然相乘，并将乘积相加，估计矩阵乘积中有多少个非零元，然后创建矩阵乘积对象，进行计算，因此这时的工作可以分为后创建
41、矩阵乘积对象，进行计算，因此这时的工作可以分为三个阶段三个阶段:对矩阵对矩阵B B进行转置得到矩阵进行转置得到矩阵C C，所需的计算量为，所需的计算量为 ,其中其中N NB B为矩阵为矩阵B B中的非零元个数中的非零元个数;试计算矩阵乘积中的非零元个数，计算量为试计算矩阵乘积中的非零元个数，计算量为 ，其中其中N NA A，N NB B为矩阵为矩阵A A与矩阵与矩阵B B的非零元的个数的非零元的个数;计算两个矩阵的乘积，计算量为计算两个矩阵的乘积，计算量为 。n根据以上的分析可以发现，所需的计算量为根据以上的分析可以发现，所需的计算量为 ，这，这种方法虽然比较节省空间，但是设计起来比价复杂，对
42、于内存比种方法虽然比较节省空间，但是设计起来比价复杂，对于内存比较少的情况比较使用较少的情况比较使用.28n还可以用以下方法实现稀疏矩阵的乘积。设一个矩还可以用以下方法实现稀疏矩阵的乘积。设一个矩阵为阵为MaMa，另外一个矩阵为，另外一个矩阵为MbMb，目的是求，目的是求MaMa与与MbMb的乘的乘积矩阵积矩阵ptpt。根据根据MaMa的行数以及的行数以及MbMb的列数来确定的列数来确定ptpt的行数和列数，并准的行数和列数，并准备一个空间备一个空间datadata来存储来存储ptpt的所有元素，所有元素的初始值的所有元素，所有元素的初始值设为设为0 0；对两个矩阵的元素进行相乘，但由于两个矩
43、阵相乘的一对对两个矩阵的元素进行相乘，但由于两个矩阵相乘的一对元素若有任何一方为零时，其乘积也为零，所以相乘时只元素若有任何一方为零时，其乘积也为零，所以相乘时只需在需在MaMa和和MbMb找到相应的各对非零元素即可（即当找到相应的各对非零元素即可（即当MaMa中元的中元的列下标等于列下标等于MbMb中元的行下标时）；中元的行下标时）；相乘之后能够得到相乘之后能够得到ptpt的所有元已存在空间的所有元已存在空间datadata中，包含零中，包含零元和非零元，此时需要对元和非零元，此时需要对datadata进行扫描，去掉零元；进行扫描，去掉零元；最后，将得到的非零元复制到新生成的稀疏矩阵最后，将
44、得到的非零元复制到新生成的稀疏矩阵ptpt中中29(2)(2)十字链表十字链表用用三三元元组组来来进进行行表表示示稀稀疏疏矩矩阵阵时时，虽虽然然可可以以节节省省大大量量的的空空间间，但但是是在在矩矩阵阵的的乘乘法法、转转置置运运算算时时，需需要要大大量量的的时时间间来来对对新新矩矩阵阵中中的的数数据据进进行行操操作作，也也就就是是说说花花费费大大量量的的时时间间用用在在非非零零元元的的移移动动上上。为为了了取取得得较较高高运运行行速速度度，可可以以在在时时间间与与空空间间之之间间取取得得一一个个平平衡衡，这这时时我我们们可可以以采采用用十十字字链链表表法法来来存存储储数数据据。即即每每个个结结
45、点点含含五五域域。如图所示。如图所示。其其中中：行行下下标标rowrow、列列下下标标colcol、数数据据valuevalue、指指向向右右边边的的非非零零元元素素的的指指针针rightNode,rightNode,以以及及指指向向下下边边的的非非零零元元素素指指针针downNodedownNode。每每个个非非零零元元既是某个行链表中的一个结点既是某个行链表中的一个结点,又是某个列又是某个列链链表表中中的的一一个个结结点点，整整个个矩矩阵阵构构成成了了一一个个十十字字交交叉叉的的链链表表，故故称称这这样样的的存存储储结结构构为为十字链表,可可用用两两个个分分别别存存储储行行链链表表的的头头
46、指指针针和列链表的头指针的一维数组表示之。和列链表的头指针的一维数组表示之。30此十字链表表示的稀疏矩阵可以如下定义：此十字链表表示的稀疏矩阵可以如下定义：typedef int ElemType;typedef int ElemType;typedeftypedef struct CrossNode struct CrossNode int row,col;/int row,col;/非零元所在的行下标、列下标非零元所在的行下标、列下标 ElemType data;/ElemType data;/该结点存放的非零数据该结点存放的非零数据 CROSSPT rightNode,downNode;
47、CROSSPT rightNode,downNode;/非零元结点的右边非零结点与下边非零结点非零元结点的右边非零结点与下边非零结点CROSSNODECROSSNODE，*CROSSPT;*CROSSPT;typedef struct CrossMatrix typedef struct CrossMatrix CROSSPT*cols,*rows;CROSSPT*cols,*rows;int row_num,col_num;int row_num,col_num;CROSSMATRIXCROSSMATRIX，*CROSSMATRIXPT;*CROSSMATRIXPT;3132在进行矩阵运算时
48、，要牵涉到大量的指针的插入、删除运算。在进行矩阵运算时，要牵涉到大量的指针的插入、删除运算。矩阵转置：矩阵转置：将将源源矩矩阵阵的的每每一一行行的的元元素素来来作作为为目目标标矩矩阵阵的的一一列列,按按照照列列插插入入到新的目标矩阵中到新的目标矩阵中,并对每一列的元素分别来进行链接；并对每一列的元素分别来进行链接；对新生成的矩阵按照目标矩阵的行分别来进行链接对新生成的矩阵按照目标矩阵的行分别来进行链接.通过列链接和行链接通过列链接和行链接,就得到了对源矩阵转置之后的目标矩阵就得到了对源矩阵转置之后的目标矩阵矩阵相加：矩阵相加：与与两两个个一一元元多多项项式式相相加加类类似似,所所不不同同的的是
49、是矩矩阵阵中中每每个个非非零零元元有有两个变元两个变元(行值和列值行值和列值),每个结点既在行表中又在列表中。每个结点既在行表中又在列表中。从从矩矩阵阵的的第第一一行行起起逐逐行行进进行行处处理理。对对每每一一行行都都从从行行表表头头出出发发分分别别找找到到Ma和和Mb在在该该行行中中的的第第一一个个非非零零元元结结点点后后开开始始比比较较,然然后按四种情况后按四种情况(不变、改变值、插入、删除不变、改变值、插入、删除)分别处理。分别处理。矩阵乘法：矩阵乘法：按按照照Ma每每行行与与Mb中中的的每每个个列列相相乘乘，就就会会得得到到目目标标矩矩阵阵的的每每行行非非零零元元，这这些些非非零零元元
50、之之间间在在以以行行链链接接的的方方式式连连接接起起来来，然然后后再再采用同样的方法进行列链接采用同样的方法进行列链接（算法略）（算法略）334.2 串串 串串(又又称称字字符符串串)是是一一种种特特殊殊的的线线性性结结构构，它它的的每每个个结结点点仅仅由由一一个个字字符符组组成成，主主要要是是用用来来解解决决非非数数值值计计算算问问题。题。本本节节主主要要介介绍绍串串的的概概念念、逻逻辑辑结结构构、串串的的三三种种存存储储表表示示及及其其在在三三种种存存储储方方式式上上的的运运算算，能能使使用用程程序序设设计计语言所提供的相关函数解决简单的应用问题。语言所提供的相关函数解决简单的应用问题。3