项目四串数组矩阵广义表

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,项目四 串、数组、矩阵、广义表,项目导读,串是字符串的简称，它的每个数据元素由一个字符组成。串是一种特殊的线性表。随着非数值处理的广泛应用，字符串已成为某些程序系统的处理对象。本章主要介绍串的存储结构及基本运算。,数组可视为线性表的推广，其特点是数据元素仍然是一个表。本章主要讨论数组的逻辑结构、存储结构、稀疏矩阵及其压缩存储等内容。,广义表是线性表的一种推广。本章我们主要介绍广义表的定义及其存储结构。,教学目标,通过本章学习，要求掌握以下内容：,1,串的存储结构及其基本运算。,2,数组的存储结构及稀疏矩阵的压缩存储。,3,广义表的定义及其存储结构。,4.1,串,串是一种特殊的线性表，它的数据对象是字符集合，它的每个元素都是一个字符，一系列相连的字符就组成了一个字符串，字符串简称串。,计算机中的非数值处理的对象基本上是字符串数据。在程序设计语言中，字符串通常是作为输入和输出的常量出现的。随着计算机程序设计语言的发展，产生了字符串处理，字符串也作为一种变量类型出现在程序设计语言中。在汇编语言的编译程序中，源程序和目标程序都是字符串数据。,在日常事务处理程序中，也有许多字符串应用的例子，如客户的名称和地址信息、产品的名称和规格等信息都是作为字符串来处理的。在文字处理软件中，在计算机翻译系统中，都使用了字符串处理的方法。,1.1,串的定义和特性,串是由,n,个字符组成的有限序列，一般记为：,s=a1 a2an ,（,n0,）,其中，,s,是串的名字，用双引号括起来的字符序列是串的值。双引号本身不属于串，它是定界符，用来标志字符串的起始和终止。,ai,（,1in,）可以是字母、数字或其他字符。,n,为串中字符的个数称为串的长度。,空串：不含任何字符的串称为空串，它的长度,n=0,，记为,s=,。,空格串：仅由空格组成的串称为空格串，它的长度为空格符的个数。为了清楚起见，在书写时把空格写成, ,，如,s=,，则,s,串长度为,n=1,。,由于空格也是一个字符，因此它可以出现在其他串之间。计算串的长度时，这些空格符也要计算在内。如串,s=I am a student.,，该串的长度是,15,，而不是,12,。,子串：串中任意个连续字符构成的序列称为该串的子串，而包含该子串的串称为母串。例如，串,s1=,abcdefghijk,，,s2=def,，则称,s2,是,s1,的子串，,s1,是,s2,的母串。,两串相等：只有当两个串的长度相等，并且各对应位置上的字符都相同时，两个串才相等。,4.1.2,串的顺序存储及其基本操作实现,串的顺序存储结构，简称为顺序串。顺序串中的字符被顺序地存放在内存中一片连续的存储单元中。在计算机中，一个字符只占一个字节，所以串中的字符是顺序存放在相邻字节中的。,在,C,语言中，串的顺序存储可用一个字符型数组和一个整型变量来表示，其中字符型数组存放串值，整型变量存放串的长度。用,C,语言描述如下：,typedef,struct,string,char,ch,MAX,; /*MAX,是事先定义好的常量，用以确定*,/,int,len,; /*,字符串数组可能的最大长度*,/,STRING;,当计算机按字节（,byte,）单位编址时，一个机器字，即一个存储单元刚好存放一个字符，串中相邻的字符顺序地存放在地址相邻的字节中。若给定串,s=data structure,，则顺序串的存储如图,4-1,所示。,d,a,t,a,s,t,r,u,c,t,u,r,e,图,4-1,顺序串存储示意图,当计算机按字（,word,）单位编址时，一个存储单元由若干个字节组成。这时串的顺序存储结构有非紧缩存储和紧缩存储两种方式。,1,串的非紧缩存储,假设计算机的字长为,32,位，即,4,个字节（,bytes,），则一个存储单元仅存放一个字符时，就要浪费,3,个字节。若给定串,s=data structure,，则非紧缩存储方式如图,4-2,所示。这种存储方式的优点是对串中的字符处理效率高，但对存储空间的利用率低。,图,4-2,非紧缩格式存储,图,4-3,紧缩格式存储,2,串的紧缩存储,根据计算机中的字的长度，尽可能将多个字符存放在一个字中。若给定串,s=data structure,，则紧缩存储方式如图,4-3,所示。,与非紧缩存储的优缺点相反，紧缩存储方式对存储空间的利用率高，但对串的单个字符操作很不方便，需要花较多的处理时间。,在,C,语言中，若采用非紧缩的顺序存储方式存放长度不超过,MAX,的串，可使用字符数组来实现，顺序串的类型定义如下：,#define MAX 100,char,ch,MAX,; /*,用字符型数组,ch,存放串值，,MAX,是已经定义过的常量*,/,下面讨论顺序串的运算方法，主要包括求串长、串连接、两串相等判断、取子串、插入子串、删除子串、子串定位和子串置换。,根据,C,语言数组下标从,0,开始的特点，串中的第,1,个元素存放在,ch,0,中，其中字符的位置顺序为第,0,，,1,，,，,MAX-1,。,1,求串长,求串长就是求字符串的长度，将求得的长度值返回。,#define MAX 50,int,length(char,*s),/*,求串,s,中所含字符个数*,/,int,i;,for(i,=0;si!=0;i+);,return(i,);,main(), char,chMAX,= china”;,int,len,;,len,=,length(ch,);,printf(“%d”,len,);,2,串连接,串连接就是把两个串连接在一起，其中一个串接在另一个串的末尾，生成一个新串。如给出两个串,s1,和,s2,，把,s2,连接到,s1,之后，生成一个新串,s,。其算法描述如下：,#define MAX 50 /*,定义一常量,MAX,为,50*/,char * connect,（,char * s1,，,char * s2,）,char,sMAX,;,int,i;,if,（,length(s1)+length(s2)=MAX,）,/*,当,s1,和,s2,的长度之和小于或等于,MAX,时*,/,for,（,i=0;ilength(s1);i+,）,/*,将,s1,存放到,s,中*,/,s,i,=s1,i,;,for,（,i=0;ilength(s2);i+,）,/*,将,s2,存放到,s,中*,/,s,length(s1)+i,=s2,i,;,s,length(s1)+i,=0; /*,设置串结尾标志*,/,else /*,当,s1,和,s2,的长度之和大于,MAX,时*,/,s0=0; /*,不能连接，置,s,空串*,/,return,（,s,）,; /*,连接成功，返回,s,，不成功时返回空串*,/,main,（）,/*,主程序*,/,char a1MAX=Beijing,，,a2MAX=China,*s; /*,字符数组,a1,和,a2,并给这两个数组赋初值*,/,s=connect,（,a1,，,a2,）,; /*,调用,connect,函数*,/,printf,（,n%sn,，,s,）,; /*,输出结果*,/,输出结果为：,Beijing China,在该例中，有两个串分别为,a1=Beijing,，,a2=China,，调用函数,connect,（,a1,，,a2,）后，函数的串值为,s=Beijing China,。,3,两串相等判断,只有当两个串的长度相等，并且各对应位置上的字符都相等时，两个串才相等。如给定两个串,s1,和,s2,，判断这两个串是否相等。当,s1,与,s2,相等时，返回函数值,1,，否则返回函数值,0,。算法如下：,#define MAX 50 /*,定义一常量,MAX,为,50*/,int,equal,（,char *s1,，,char *s2,）,int,i,m,n,;,m=length(s1); /*,求,s1,字符串的长度*,/,n=length(s2); /*,求,s2,字符串的长度*,/,if,（,m!=n,）,/*,如果,s1,与,s2,长度不等*,/,return,（,0,）,; /*,返回函数值,0*/,else /*,如果,s1,与,s2,长度相等*,/,for,（,i=0;i,m;i,+,）,/*,判断,s1,和,s2,中各对应位置上字符是否相等*,/,if,（,s1i!=s2i,）,/*,如果某一对应位置上字符不相等*,/,return,（,0,）,; /*,返回函数值,0*/,/*,两个串完全相等时*,/,return,（,1,）,; /*,返回函数值,1*/,main,（）,/*,主程序*,/,char a1MAX=Beijing,a2MAX=China; /*,定义两个字符数组并给它们赋初值*,/,int,r;,r=equal,（,a1,a2,）,; /*,调用,equal,函数*,/,if(r,),printf(“equaln,”); /*,输出结果*,/,else,printf,(“ not equaln”);,输出结果为,:,not equal,在该例中，有两个串分别为,a1=Beijing,，,a2=China,，调用函数,equal,（,a1,a2,）后，函数的返回值为,0,，所以才输出,not equal,。,4,取子串,取子串就是在给定串中，从某一位置开始连续取出若干字符，作为子串的值。例如，给定串,s,，从,s,中的第,n1,个字符开始，连续取出,n2,个字符，放在,t,串中。其算法描述如下：,#define MAX 50 /*,定义一常量,MAX,为,50*/,int,substring,（,char *s,int,n1,int n2, char *t,）,int,i,k,;,if(n1,length(s,) /*,如果位置不对则返回,0,值*,/,return(0);,for(k,=0;(k=MAX) return(0); /*,如果位置不合适或者两个字符串合在一起的长度比,MAX,大时函数返回,0,值。*,/,for(k=i-1;kp-2;k-) sk+j=sk; /*,将,s,串中从第,p,个字符开始一直到串尾分别向后挪动,j,个位置以便将,t,串插入*,/,for(k=0;ki) sp-1=0; /*,从第,p,个字符开始到最后的字符数不足,j,个，删除时，不用移动元素，只需给,sp-1,时赋值为,0,即可*,/,else,for(k=0;k=(i-p-j+1);k+) /*,删除,j,个字符后要把后面的其余的元素向前移动,j,位。*,/,sp-1+k=sp-1+j+k;,si-j=0;,return(1);,main,（）,/*,主程序*,/,char,sMAX,= ,Beiing,Shanghai China;,int,i=8,，,j=9;,if(delete(s,i,j,),printf(“%s”,s,);,else,printf(“delete,is unsuccessful”);,输出结果为,:,Beijing China,13,在该例中，串,s=Beijing Shanghai China,，在调用了,delete,（,s,，,i,，,j,）后，得到的结果为,s=Beijing China,。,7,子串定位,子串定位运算也称串的模式匹配。这是一种很常用的串运算，在文本编辑中经常用到这种运算。,所谓模式匹配，就是判断某个串是否是另一个已知串的子串。如果是其子串，则给出该子串在这个串中的起始位置，即子串第一个字符的位置。如果不是，则给出不是的信息。,下面介绍一个简单的模式匹配算法。,设有一母串,s,和一子串,s1,，判断母串,s,中是否包含子串,s1,。其判断的基本方法是：从母串,s,中的第一个字符开始，按,s1,子串的长度与,s1,子串中的字符依次对应比较。,若不匹配，则再从,s,串中的第二个字符开始，仍按,s1,子串的长度与,s1,子串中的字符依次对应比较。,如此反复进行比较。直到匹配成功或者母串,s,中剩余的字符少于,s1,的长度为止。若匹配成功，则返回,s1,串在,s,串中的位置。若匹配不成功，则返回函数值,0,。,子串定位的算法如下：,#define MAX 50 /*,定义一常量,MAX,为,50*/,int,match,（,char *s,，,char *s1,）,int,i,，,j,m,n,;,i=j=0;,m=,length(s,); /*,将,s,串的长度赋给,m,变量*,/,n=length(s1);/*,将,s1,串的长度赋给,n,变量*,/,while(i,m)&(j,=n) return(i-n+1); /*,如果,j=n,那么,s1,就是,s,的子串并返回其在,s,串中的位置*,/,else return(0);,main,（）,/*,主程序*,/,char,aMAX,=Beijing Shanghai China,，,a1MAX=Shanghai; /*,定义两个字符数组，给字符数组赋初值*,/,int,r;,r=match,（,a,，,a1,）,; /*,调用,match,函数*,/,printf,（,n%d,，,r,）,; /*,输出结果*,/,输出结果为：,9,8,串置换,串置换就是把母串中的某个子串用另一个子串来替换。字符串替换算法可以用删除子串的算法和插入子串的算法来实现。在这里不在详述，大家可以依照上面的程序稍加改动即可。,4.1.3,串的链式存储及其基本操作实现,串的链式存储结构与单链表类似。由于串结构的特殊性,-,结构中的每个数据元素是一个字符，用链表存储串值时，就存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符，如图,4-3,所示的链表，其结点大小分别为,4,和,1,。,图,4-3,串的链式存储结构,对于结点大小超过,1,的结点，在存储串值时，最后一个结点的,data,域不一定正好填满，这时就要以一个非串值字符（例如,）补足。,在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样重要，直接影响对串的处理的效率。,总的来说，由于串的特殊性，使得采用采用链式存储结构存储串不太实用，所以并不常用链式存储结构方式存储串。,4.1.4,串的应用举例,文本编辑是串应用的一个典型例子。有很多种文本编辑的软件，用于不同的应用领域，如一般的办公室文书编辑、专业用的报刊和书籍编辑。不同的软件公司也开发出了不同的文本编辑软件。这些文本编辑软件的大小、功能都不一样，但其基本操作原理都是一致的，通常都是串的插入、删除、查找替换以及字符格式的设置等。,这些编辑软件进行文本处理时，对整个文本进行了不同的拆分方法，如页、段、行、句、词和字等。在编辑过程中，可以把整个文本看成是一个字符串，也可以把它叫做文本串，那么页就是文本串的子串，行又是页的子串，等等。这样，在编辑过程中，就能够以不同的单位对文本进行各种不同功能的操作。,计算机在执行文本编辑程序时，要对文本建立起各种功能所需要的存储信息表，如页表、行表。在编辑过程中，要设立页指针、行指针和字符指针。在进行插入、删除等操作时都是按照这些指针进行相应的修改工作。如插入字符后，后面的文本要相应向后移动，删除字符后，后面的文本要相应向前移动等。,4.2,数组,4.2.1,数组的定义和运算,数组是最常用的一种数据结构，在大多数程序设计语言中都把数组作为固有的数据类型。,数组类似于线性表，是由同种类型的数据元素构造而成，数组的每个元素由一个值和一组下标所决定，数组中各元素之间的关系是由各元素的下标体现出来。也就是，在有下标指定数组的相关元素中都存在一个与它相对应的值。,一维数组记为,An,或,A=(a0,a1, ,an-1),，每个数组元素由一个值和一个下标来确定，数组元素的下标的顺序可作为一个线性表中的序号。,二维数组，又称矩阵，图,4-1,为矩阵的表示形式。,图,4-1,矩阵的表示,图,4-1,矩阵的表示,二维数组中的每一个元素由矩阵元素,aij,值及一组下标（,i,j,）,(i=0,1,2, ,m-1;j=0,1,2, ,n-1),来确定。每组下标（,i,j,）都唯一地对应一个值,aij,。二维数组中的每一个元素都要受到两个关系即行关系第,i,行的行表,ai0,ai1,ai2, ,ain-1,，同行元素,aij,是,aij-1,的直接后继；另一个是表达列关系第,j,列的列表,a0j,a1j,a2j, am-1j,，同列元素,aij,是,ai-1j,的直接后继。,可以把二维数组看成是这样一个线性表，它的每个元素是一个线性表。例如，图,4-1,所示是一个二维数组，以,m,行,n,列的矩阵形式表示：,A=(a00,a01, ,a0n-1),(a10,a11, ,a1n-1), ,(am-10,am-11, ,am-1n-1),它的每个数组元素是一个以行序为主的线性表。而,A=(a00,a10, ,am-10),(a01,a11, ,am-11), ,(a0n-1,a1n-1, ,am-1n-1),它的每个数组元素是一个以列序为主的线性表。,对于数组，通常只有两种运算。,1,给定一个下标，存取相应的数据元素。,2,给定一个下标，修改相应的数据元素的某个数据项的值。,4.2.2,数组的顺序存储结构,由于数组一般不作删除或插入运算，所以一旦数据被定义后，数组中的元素个数和元素间的关系就无需变动。一般采用顺序存储结构，而随机存取是顺序存储结构的主要特性。在这里我们只讨论二维数组的顺序存储结构，大部分高级语言对二维数组的顺序存储均采用以行序为主的存储方式，如图,4-2,（,b,）所示，如,C,语言。但在有的语言（如,Fortran,）中采用的是以列序为主的存储方式，如图,4-2,（,c,）所示。,图,4-2,二维数组的两种存储结构,在,C,语言中，数组中任一元素,aij,的地址计算公式为：,LOC(Aij,)=LOC(A00)+(in+j)s 0im-1,，,0jn-1,其中，,LOC(A00),为数组的起始位置，,s,为每个数据元素所占存储单元个数。由于在定义数组时，,LOC(A00),、,s,和,n,是已知的，因此根据公式可以计算出任一元素的存储地址，实现随机存取。,4.3,矩阵的压缩存储,在许多的科学技术和工程计算中，矩阵是数值分析问题研究的数学对象。对于矩阵数据结构主要研究其中计算机中的存储，从而使矩阵得到更为有效地存储和使用。,一般情况下，高级语言对矩阵采用二维数组进行存储，然而，实际应用中会遇到一些特殊矩阵，所谓特殊矩阵是指矩阵中值相同的元素或者零元素的分布有一定的规律。例如，对称矩阵、三角矩阵、带状矩阵等都是特殊矩阵。对于这种特殊矩阵，在运算时为了节省存储空间，需要对这类矩阵进行压缩存储。下面我们讨论如何对这些特殊矩阵实现压缩存储。,4.3.1,对称矩阵的压缩存储,对称矩阵是个,n,阶方阵。若一个,n,阶矩阵,A,的元素满足于,aij,=,aji,（,0 ,i,j, n-1,）的性质，则称为,n,阶对称矩阵。即在对称矩阵中，以对角线,a00,，,a11,，,，,an-1n-1,为轴线的对称位置上的矩阵元素值相等。由此，可以对每一对对称的矩阵元素分配一个存储空间，那么,n,阶矩阵中的,n n,个元素就可以被压缩到,n(n+1)/2,个元素的存储空间中去。,若以行序为主序存储的对称矩阵为例，包括对角线元素的下三角矩阵。假设以一维数组,Sn(n+1)/2,作为,n,阶对称矩阵,A,的存储结构，一维数组,Sk,与矩阵元素,aij,之间存在一一对应的关系的公式如下：,对于任意一组下标（,i,j,），均可在,S,中找到矩阵元素,aij,反之，对所有的,k=0,1,2,，,n(n+1)/2-1,，都能确定在,Sk,中的元素在对称矩阵中的下标位置（,i,j,）。其存储结构如图,4-3,所示。,图,4-3,对称矩阵的压缩存储,4.3.2,三角矩阵的压缩存储,三角矩阵也是量个,n,阶方阵，有上三角和下三角矩阵，下（上）三角矩阵是主对角线以上（下）元素为零的,n,阶矩阵。图,4-4,是一个下三角矩阵。,如果不存储主对角线另一方的零元素，三角矩阵的压缩存储方式可与对称矩阵相同。,图,4-4,下三角矩阵,4.4,稀疏矩阵,4.4.1,稀疏矩阵的定义,在一个,mn,矩阵中，如果零元素比非零元素个数多得多，且非零元素在矩阵中的分布无规律，则称此矩阵为稀疏矩阵。如图,4-5,所示的矩阵,M,和矩阵,N,都是稀疏矩阵。,图,4-5,稀疏矩阵,M,和,N,对于稀疏矩阵的压缩存储，仍然以存储矩阵的非零元素为原则。但是稀疏矩阵中的非零元素是无规律地出现的，所以不能简单的进行存储，对于稀疏矩阵的存储也有顺序存储和链式存储两种方式。,4.4.2,稀疏矩阵的顺序存储及其基本操作实现,稀疏矩阵的顺序存储方式可以用三元组表示法来表示。这个方法用一个线性表来表示稀疏矩阵，线性表的每个结点对应稀疏矩阵的一个非零元素。其中包括三个域，分别为矩阵非零元素行号、列号和值。记做（,row,，,col,，,val,），结点仍按矩阵行优先顺序排列（跳过零元素），称该线性表为三元组表。图,4-6,所示的三元组表分别对应图,4-5,的两个稀疏矩阵。,图,4-6,稀疏矩阵的三元组表示图例,若用一维数组,ma,存储矩阵,M,，用一维数组,mb,存储矩阵,N,。则用,C,语言描述算法的具体结构定义如下：,#define MAX 50,struct,node,int,row;,int,col,;,int,val,;,NODE;,NODE ma ,MAX,mbMAX,;,当稀疏矩阵用三元组表示后，可对它进行某些运算，以矩阵转置为例说明三元组表示的稀疏矩阵是如何进行运算的。,矩阵的转置运算是矩阵中一种最简单的基本运算。对于,m n,的矩阵,M,，它的转置矩阵,N,是一个,n m,的矩阵，且,Nij,=,Mij,，其中，,1in,，,1 ,jm,。例如，图,4-5,中,M,是,N,的转置矩阵，反之，,N,也是,M,的转置矩阵。相互转换的结果应满足下列两个条件：,（,row,，,col,，,val,） （,col,，,row,，,val,）,使转置的三元组数组仍是按行排列的。进行矩阵的转置操作，首先要将矩阵的行列值相互交换。使转置的三元组数组仍然按行号的递增次序存储。具体实现转置运算时有以下两种算法。,1,矩阵的列序转置,矩阵,M,是按行序为主序存储的，若按列序为主序进行转置可以得到按行序为主序存储的转置矩阵,N,。假设，矩阵,M,的三元组存入一维数组,ma,，而转置矩阵,N,的三元组将存入另一个一维数组,mb,中。由此，只要在数组,ma,中按三元组的列域,col,的值开始扫描，从第,1,列至第,n-1,列，依序将三元组列域与行域之值对换，并顺次存入数组,mb,中。转换成功后函数返回值为,1,，否则，函数返回值为,0,。其具体算法描述如下,：,#define MAX 50,typedef,struct,node,int,row;,int,col,;,int,val,;,NODE;,NODE ma ,MAX,mbMAX,;,int,trans(NODE,ma,NODE,mb,),int,i,j,k,=1,m,n,t;,if(ma0.val=0) return (0); /*,矩阵中无非零元素 *,/,m=ma0.row; /*m,为矩阵,M,的行数*,/,n=ma0.col; /*n,为矩阵,M,的列数*,/,t=ma0.val; /* t,为矩阵,M,的非零元素的个数 *,/,mb0.row=n; /*,转置矩阵,N,的行数 *,/,mb0.col=m; /*,转置矩阵,N,的列数 *,/,mb0.val=t; /*,转置矩阵,N,中的非零元素个数*,/,for(j,=1;j=,n;j,+),for(i,=1;i=,t;i,+),if(mai.col,=j),mbk.row,=,mai.col,;,mbk.col,=,mai.row,;,mbk.val,=,mai.val,;,k+;,return(1);,main(),int,i,j,val,m,n,t,;,scanf(“%d,%d,%d”,&m,&n,&t,);/*,输入矩阵,M,的行数,m,、列数,n,、非零元素的个数,t */,ma0.row=m;,ma0.col=n;,ma0.val=t;,for (i=1;i=,t;i,+),scanf(“%d,%d,%d”,&m,&n,&val,);,mai.row,=m;,mai.col,=n;,mai.val,=,val,;,j=,trans(ma,mb,);,if(j,),t=mb0.val;,for(i,=1;i=,t;i,+),printf(“%5d%5d%5dn”,mbi.row,mbi.col,mbi.val);,若设,n,为转置矩阵的列数，,t,矩阵中非零元素个数，则上述算法的时间主要花费在两个循环上，所以时间复杂度为,O,（,nt,）。也就是说，时间的花费和矩阵,M,的列数和非零元素个数的乘积成正比。若换一种方法用,mn,二维数组表示矩阵，则相应的矩阵转置算法的循环为：,for(i,=1;i=,n;i,+),for(j,=1;j=,m;j,+),bij,=,aji,；。此时，时间复杂度为,O,（,mn,）。比较两种算法，若矩阵中无非零元素，即,t=,mn,时，则上述算法的时间复杂度将达到,O,（,mn2,）。由此可见，上述算法仅适用存在大量的非零元素的稀疏矩阵。若要节省时间可以用快速转置方法进行转置。,2,矩阵的快速转置,矩阵的快速转置算法是在对按转置前矩阵,M,的列序进行转置时，将转置后的三元组按矩阵,N,的行序直接置入,mb,中适当的位置上。首先，要确定,M,中每列非零元素的个数，这就确定了,N,中每一行非零元素的个数，也就确定了数组,ma,中每一列第一个非零元素在,mb,中的存放位置。这样就能够容易地把,ma,中的元素依次移到它们在,mb,中正确的位置上。为此，需要设两个一维数组,numMAX,和,potMAX,。,numj,( 1jn),表示数组,ma,中第,j,列非零元素个数；而,ma,中第一列第一个非零元素转置后必须放在,mb1,中，这样就可以推算出数组,ma,中每一列第一个非零元素在数组,mb,中的位置。设数组,pot,用以记录此位置。,potj,为数组,ma,中第,j,列第一个非零元素在转置后数组,mb,中的位置。显然有：,例如，矩阵,M,的,num,和,pot,的数组值，如图,4-7,所示。,j,1,2,3,4,5,numj,1,2,1,1,1,potj,1,2,4,5,6,图,4-7,矩阵,M,的,num,和,pot,数组的值,快速转置的,C,语言算法描述如下：,#define MAX 50,typedef,struct,node,int,rowi,;,int,col,;,int,val,;,NODE;,NODE ma ,MAX,mbMAX,;,int,tranquick,( NODE,ma,NODE,mb,),int,i,j,m,n,t,numMAX,potMAX,;,if( ma0.val=0) return(0); /*,矩阵无非零元素 *,/,m=ma0.row; /*m,为矩阵,M,的行数*,/,n=ma0.col; /*n,为矩阵,M,的列数*,/,t=ma0.val; /* t,为矩阵,M,的非零元素的个数 *,/,mb0.row=n; /*,转置矩阵,N,的行数 *,/,mb0.col=m; /*,转置矩阵,N,的列数 *,/,mb0.val=t; /*,转置矩阵,N,中的非零元素个数*,/,for(i,=1;i=,n;i,+),numi,=0; /*,对数组,num,初始化*,/,for(j,=1;j=,t;j,+) /*,统计第,j,列中非零元素的个数*,/, m=,maj.col;numm,+;,pot1=1;,for(i,=2;i=,n;i,+),poti,=poti-1+numi-1;/*pot,数组记录每列非零元素在,mb,数组中的位置*,/,for(i,=1;i=,t;i,+),j=,mai.col,;,mbpotj.row,=,mai.col,;,mbpotj.col,=,mai.row,;,mbpotj.val,=,mai.val,;,potj,+;,return(1);,main(),int,i,j,val,m,n,t,;,scanf(“%d,%d,%d”,&m,&n,&t,);/*,输入矩阵,M,的行数,m,、列数,n,、非零元素的个数,t */,ma0.row=m;,ma0.col=n;,ma0.val=t;,for (i=1;i=,t;i,+),scanf(“%d,%d,%d”,&m,&n,&t,);,mai.row,=m;,mai.col,=n;,mai.val,=t;,j=,tranquick(ma,mb,);,if(j,),t=mb0.val;,for(i,=1;i0,）时，第一个数据元素（,d1,）称为广义表的表头（,head,），其余数据元素组成的表,(d2,d3, ,dn,),为广义表,L,的表尾（,tail,），分别记为,head(L,)= d1,，,tail(L,)= (d2,d3, ,dn,),。下面是几个广义表的例子。,A=,（,a,），广义表,A,的长度为,1,，唯一的数据元素是原子,a,。,B=,（,a,，,(x,，,y),），广义表,B,由数据元素,a,和子表,(x,，,y),组成，其长度为,2,。,C=,（,A,，,B,，（），广义表,C,的长度为,3,，第一个数据元素为广义表,A,，第二个数据元素为广义表,B,，最后一个数据元素是空表，可以写成,C=,（,a,），（,a,，,(x,，,y),），,(),）。,D=,（,a,D,），广义表长度为,2,，其中第二项仍为,D,，所以,D,是一个递归表，相当于一个无限表，可写成,D=,（,a,(a,(a,),）,E=,（），,E,为长度为零的空表。,F=,（,E,），,F,为长度为,1,的空表，可写成,F=,（）。,从上述定义和例子可推出如下结论。,一个广义表可以与其子表共享数据。在上述广义表,C,中，子表,A,，,B,与,C,共享数据。,广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。上述广义表,D,就是一个递归的表。,另外，广义表的数据元素之间除了存在次序关系外，还存在层次关系，这种关系可以图形表示。例如，图,4-9,所示的广义表,C,，图中的圆形图符表示广义表，方形图符表示数据元素。,图,4-9,广义表,C,的图形表示,广义表中数据元素的最大层次为表的深度。数据元素的层次就是包括该元素的括号对的数目。例如广义表,G,（,a,b,(c,(d,),）中，数据元素,a,b,在第一层，数据元素,c,在第二层，数据元素,d,在第三层，广义表,G,的深度为,3,。,4.5.2,广义表的存储结构及其基本操作实现,通常广义表采用链表存储结构。每个数据元素可用一个结点表示，这些元素可能是原子或子表。由此采用两种结构结点，一种是表结点，另一种为原子结点，如图,4-10,所示。广义表的表结点由,tag,hp,tp,三个域组成。,tag,为标识域（,tag=1,标识表结点）；,hp,为表头域存放指向该子表的指针值。,tp,域为链域，用以存放指向广义表中下一个元素的指针值。图,4-10,（,a,）为表结点的结构；广义表的原子结点有三个域，,tag,为标识域（,tag=0,标识原子结点），,value,为值域，,link,为下一个数据元素的指针域，图,4-10(b),为数据元素结点的结构。,在链表中，广义表各元素之间的次序关系被表示得更为清晰。一般用横向箭头表示元素之间的次序，用竖向的箭头表示元素之间的层次关系。图,4-11,给出了广义表,AF,的链表存储结构。,图,4-10,广义表的链表结点,图,4-11,广义表的链表存储结构,与链表类似，可对广义表进行的操作有查找、插入和删除等。由于广义表在结构上较线性表复杂的多，广义表操作的实现要比线性表困难得多。下面介绍广义表的两种基本操作，取广义表的表头,head(L,),和取表尾,tail(L,),。对前述例子有以下操作。,head(A,)=a,，,tail(A,)=();,head(B,)=a,，,tail(B,)=(,x,y,);,head(C,)=A,，,tail(C,)=(B,();,head(D,)=a,，,tail(D,)=(D);,head(F,)=E,，,tail(F,)=();,4.6,项目小结,1,串是一种受限制的线性表，串的存储方式有两种：静态存储结构和动态存储结构。静态存储结构分为紧缩格式存储和非紧缩格式存储。两种存储方式各有其优缺点，非紧缩格式存储，不能节省内存单元，但操作起来比较方便。相反，紧缩格式存储可以节省内存单元，但操作起来不方便。,2,数组是一种最常见的存储结构，数组一般采用顺序存储结构进行存储，在内存中是以行序为主序进行存储的。二维数组的特例就是矩阵，对于一些特殊矩阵一般会采用压缩的存储方式，如，对称矩阵、三解矩阵等等，除此之外，对于稀疏矩阵我们也采用压缩存贮方式：线性存储采用三元组表示法；链式存储采用十字链表表示法。,3,广义表也是一种线性表，对于广义表的操作主要有取表头和表尾的操作。,习 题,4,一、选择题,1,下面关于串的的叙述中，哪一个是不正确的？（ ）,A,串是字符的有限序列,B,空串是由空格构成的串,C,模式匹配是串的一种重要运算,D,串既可以采用顺序存储，也可以采用链式存储,2, 若串,S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行,concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2),，其结果为（ ）,A,ABC#G0123 B,ABCD#2345 C,ABC#G2345 D,ABC#2345,E,ABC#G1234 F,ABCD#1234 G,ABC#01234,3,设有两个串,p,和,q,，其中,q,是,p,的子串，求,q,在,p,中首次出现的位置的算法称为（ ）,A,求子串,B,联接,C,匹配,D,求串长,4.,设有一个,10,阶的对称矩阵,A,，采用压缩存储方式，以行序为主存储，,a11,为第一元素，其存储地址为,1,，每个元素占一个地址空间，则,a85,的地址为（ ）。,A. 13 B. 33 C. 18 D. 40,5.,对稀疏矩阵进行压缩存储目的是（ ）。,A,便于进行矩阵运算,B,便于输入和输出,C,节省存储空间,D,降低运算的时间复杂度,6.,广义表,A=(,a,b,(c,d),(e,(f,g,),则下面式子的值为（ ）。,Head(Tail(Head(Tail(Tail(A,),A. (g) B. (d) C. c D. d,7.,设广义表,L=,（,a,b,c,），则,L,的长度和深度分别为（ ）。,A. 1,和,1 B. 1,和,3 C. 1,和,2 D. 2,和,3,二、判断题,1,串是一种数据对象和操作都特殊的线性表。（ ）,2.,稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）,3.,数组是同类型值的集合。（ ）,4.,数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）,5.,一个稀疏矩阵,Am*n,采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把,m,和,n,的值互换，则就完成了,Am*n,的转置运算。（ ）,6.,二维以上的数组其实是一种特殊的广义表。（ ）,7.,广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）,三、填空题,1,空格串是指,_(1)_,，其长度等于,_(2)_,。,2,组成串的数据元素只能是,_,。,3,一个字符串中,_,称为该串的子串 。,4.,数组的存储结构采用,_,存储方式。,5.,所谓稀疏矩阵指的是,_,。,6.,广义表,A=,（,a,，,b,），（,c,，,d,，,e,），取出,A,中的原子,e,的操作是,: _,。,四、应用题,1,名词解释：串,2,描述以下概念的区别：空格串与空串。,3.,特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？,4.,试叙述一维数组与有序表的异同。,5.,一个,nn,的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？,五、算法设计题,1,设,s,、,t,为两个字符串，分别放在两个一维数组中，,m,、,n,分别为其长度，判断,t,是否为,s,的子串。如果是，输出子串所在位置（第一个字符），否则输出,0,。（注：用程序实现）,2,编写算法打印出由指针,Hm,指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：,它们已用,val,域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由,right,（,down,）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。,项目实训,3,实训目的要求：,1,进一步理解稀疏矩阵的三元组存贮方法,2,学会转置矩阵的算法