项目四串数组矩阵广义表.ppt

项目四 串、数组、矩阵、广义表,项目导读 串是字符串的简称，它的每个数据元素由一个字符组成。串是一种特殊的线性表。随着非数值处理的广泛应用，字符串已成为某些程序系统的处理对象。本章主要介绍串的存储结构及基本运算。数组可视为线性表的推广，其特点是数据元素仍然是一个表。本章主要讨论数组的逻辑结构、存储结构、稀疏矩阵及其压缩存储等内容。广义表是线性表的一种推广。本章我们主要介绍广义表的定义及其存储结构。教学目标通过本章学习，要求掌握以下内容：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 chMAX;/*MAX是事先定义好的常量，用以确定*/int len;/*字符串数组可能的最大长度*/STRING;,当计算机按字节（byte）单位编址时，一个机器字，即一个存储单元刚好存放一个字符，串中相邻的字符顺序地存放在地址相邻的字节中。若给定串s=data structure，则顺序串的存储如图4-1所示。,图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 chMAX;/*用字符型数组ch存放串值，MAX是已经定义过的常量*/下面讨论顺序串的运算方法，主要包括求串长、串连接、两串相等判断、取子串、插入子串、删除子串、子串定位和子串置换。根据C语言数组下标从0开始的特点，串中的第1个元素存放在ch0中，其中字符的位置顺序为第0，1，MAX-1。,1求串长求串长就是求字符串的长度，将求得的长度值返回。#define MAX 50int 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中*/si=s1i;for（i=0;ilength(s2);i+）/*将s2存放到s中*/slength(s1)+i=s2i;slength(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;im;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(n1length(s)/*如果位置不对则返回0值*/return(0);for(k=0;(kn2),main（）/*主程序*/char a1MAX=Beijing China，sMAX;/*定义字符数组并给该数组赋初值*/if(substring（a1,4,4,s）)/*如果取子串成功，则函数返回值为1，输出该子串*/printf(“%s”,s);else/*函数返回值为0时，输出不成功信息*/printf(“unsuccess”);输出的结果为:jing,5插入子串 插入子串就是在给定串s的第p个字符之前插入一个串t。插入成功函数返回值为1，否则函数返回值为0。其算法描述如下：#define MAX 50int insert（char*s,int p,char*t）int i,j,k;i=length(s);j=length(t);/*求S串和t串的长度分别赋给变量i,j*/if(pi)|(i+j)=MAX)return(0);/*如果位置不合适或者两个字符串合在一起的长度比MAX大时函数返回0值。*/for(k=i-1;kp-2;k-)sk+j=sk;/*将s 串中从第p个字符开始一直到串尾分别向后挪动j个位置以便将t串插入*/,for(k=0;kj;k+)sp-1+k=tk;si+j=0;return(1);main（）/*主程序*/char sMAX=Beijing China，tMAX=Shanghai;/*定义两个字符数组并分别给它们赋初值*/int i=8;if(insert(s,i,t)printf(“%s”,s);else printf(“insert is unsuccessful”);输出结果为：Beijing Shanghai China,6删除子串 在串中删除从某一位置开始连续的字符。如在s串中，从第p个字符开始连续删除j个字符。可能出现三种情况：（1）如果p值不在s串范围内，不能删除。（2）从第p个字符开始到最后的字符数不足j个，删除时，不用移动元素。（3）p和j都可以满足要求。删除后，要把后面其余的元素向前移动j位。删除成功后函数返回值为1，否则函数返回值为0。删除子串的C语言算法描述如下：,#define MAX 50/*定义一常量MAX为50*/int delete（char*s，int p，int j）int i,k;i=length(s);/*求串s的长度*/if(pi)return(0);/*如果位置不合适函数返回0值*/if(p+j-1)i)sp-1=0;/*从第p个字符开始到最后的字符数不足j个，删除时，不用移动元素，只需给sp-1时赋值为0即可*/elsefor(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 China13 在该例中，串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=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 50struct 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 50typedef 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”,for(i=1;i=t;i+)scanf(“%d,%d,%d”,若设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所示。,图4-7 矩阵M的num和pot数组的值,快速转置的C语言算法描述如下：#define MAX 50typedef 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的行数m、列数n、非零元素的个数t*/,ma0.row=m;ma0.col=n;ma0.val=t;for(i=1;i=t;i+)scanf(“%d,%d,%d”,上述算法有四个并列的循环，第一个循环对数组num置零进行初始化操作；第二个循环对转置前矩阵非零元素的三元组数组ma进行扫描，且将统计出的ma中的每列非零元素的个数放入数组num中；第三个循环按公式生成数组pot；第四个循环是矩阵的转置操作。上述算法的时间主要花费在这四个并列的循环上，其时间复杂度为O（n+t）。当矩阵M无非零元素（即t=mn）时，其时间复杂度就变成O（mn），此时和用二维数组表示矩阵转置的时间复杂度相同。,4.4.3 稀疏矩阵的链式存储及其基本操作实现用三元数组的结构来表示稀疏矩阵，在某些情况下，它可以节省存储空间并加快运算速度，但在运算过程中，若稀疏矩阵的非零元素位置发生变化，必将会引起数组中元素的频繁移动。这时，采用链式存储结构会更好些。十字链表是稀疏矩阵的另一种存储结构。十字链表适用于在矩阵中非零元素的个数的运算及元素位置变动频繁的稀疏矩阵。在十字链表中，每一个非零元素可用一个结点表示。每个结点由五个域组成，其中行域（row）、列域（val）分别表示非零元素的行号、列号和值。向下域（down）用以链接含同一列中下一个非零元素的结点，向右域（right）用以链接含同一行中下一个非零元素的结点。结点结构如图4-8（b）所示。,稀疏矩阵中同一行非零元素通过向右链接成一个行链表，同一列的非零元素也通过向下域链接成一个列链表。因此，对于表示每个非零元素的结点来说，它既是第i行行链表中的一个结点，又是第j列列链表中的一个结点。整个稀疏矩阵是用一个十字交叉的链表结构表示的。所以称作十字链表。另外还设行指针数组rh和列指针数组ch。设稀疏矩阵有m 行、n列。行指针数组有m个元素，分别指向各行的含第一个非零元素的结点；列指针数组有n个元素，分别指向各列的含第一个非零元素的结点。这样对矩阵元素的查找可顺着所在行的行链表进行，也可以顺着所在列的列链表进行。稀疏矩阵M及十字链表表示如图4-8所示。,图4-8 稀疏矩阵的十字链表表示示例,采用十字链表表示的稀疏矩阵时，由于需要额外的存储链域空间，且还要有行、列指针数组，所以在十字链表中，只有当非零元素不超过总元素个数的20%时才可能比一般的数组表示方法节省存储空间。,4.5 广义表,广义表是线性表的一种推广，广义表双称列表。4.5.1 广义表的定义和特性广义表是n个元素的有限序列，记为L=(d1,d2,dn)其中，L是广义表的名称，n是广义表的长度，di（1in）是广义表的数据元素，这这些数据元素也可为数据对象或广义表。若di是数据元素，则称di是广义表L的原子；若di是广义表，则称di为广义表的子表。显然，广义表的定义是一个递归的定义，广义表中可以包含广义表。按照惯例，用英文大写字母表示广义表的名称，小写字母表示数据元素。当广义表L非空（n0）时，第一个数据元素（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)，其结果为（）AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#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.405.对稀疏矩阵进行压缩存储目的是（）。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.d7.设广义表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.特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么