《数据结构教程》-第五章

第5章串和数组5.3串的基本运算5.4数组

5.4.1数组的基本概念

5.4.2数组的存储结构

5.4.3特殊矩阵的压缩存储5.5稀疏矩阵

5.5.1稀疏矩阵的三元组表示

5.5.2稀疏矩阵的十字链表表示

返回上一页5.1串的定义和基本运算5.1.1串的定义1.串的定义串(String)是由零个或多个任意字符组成的有限序列。一般记作:其中s是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。ai(1<=i<=n>是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号;n为串的长度，表示串中所包含的字符个数。2.几个术语(1)长度——串中字符的个数，称为串的长度。(2)空串——长度为零的字符串称为空串。下一页返回5.1串的定义和基本运算(3)空格串—由一个或多个连续空格组成的串称为空格串。(4)串相等—两个串是相等的，是指两个串的长度相等且对应字符都相等。(5)子串—串中任意连续的字符组成的子序列称为该串的子串。(6)主串—包含子串的串称为该子串的主串。(7)模式匹配—子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。下一页返回上一页5.1串的定义和基本运算[例5-1]字符串的长度及子串的位置。S1是S3,S4的子串，S1在S3,S4中的位置都为1。S2也是S3,S4的子串，S2在S3中的位置为6;S2在S4中的位置为7。下一页返回上一页5.1串的定义和基本运算3.串的应用在汇编语言和高级语言的编译程序中，源程序和目标程序都是以字符串表示的。在事务处理程序中，如客户的姓名、地址、邮政编码、货物名称等，一般也是作为字符串数据处理的。另外，信息检索系统、文字编辑系统、语言翻译系统等，也都是以字符串数据作为处理对象的。5.1.2串的输入与输出1.字符串的输入在C语言中，字符串的输人有以下两种方法。(1)使用、canf()函数使用、eanf()函数时，输人格式中要设置”%、”，再加上字符数组名称。下一页返回上一页5.1串的定义和基本运算[例5-2]使用seanf()方式输入时，字符串中不能含有空格。在G++中还可以用输人流对象Cin。(2)使用gets()函数格式为:gets(字符数组名);[例5-3]下一页返回上一页5.1串的定义和基本运算使用gets()方式输入时，字符串中允许含有空格。2.字符串的输出字符串的输出也有两种方法。(1)使用printf()函数使用printf()函数时，输出格式中要设置”%、”，再加上字符数组名。[例5-4]在G++中还可以用输出流对象Cout。(2)使用puts()函数格式为:puts(字符数组名);下一页返回上一页5.1串的定义和基本运算[例5-5]5.1.3串的基本运算(1)求串长LenStr(s)。操作条件:串s存在。操作结果:求出串s的长度。(2)串连接:GoncatStr(s1,s2)操作条件:串s1，s2存在。操作结果:新串、1是串、1和串s2连接以后的新串，原串s2值不变，串、1的值则改变二下一页返回上一页5.1串的定义和基本运算[例5-6]设s1=”MicrosoftΠ”，s2="Office"，求两个串连接的结果。操作结果:s1=”MicrosoftΠOffice";s2=”Office"。(3)求子串SubStr(s，i,len)。操作条件:串s存在。操作结果:返回从串、的第i个字符开始的长度为len的子串。len=0得到的是空串。[例5-7]SubStr(”abodefghi”，3，4)=”cdef"下一页返回上一页5.1串的定义和基本运算(4)串比较:EqualStr(s1,s2)。操作条件:串s1，s2存在。操作结果:若s1==s2，返回值为0;若s1<s2，返回值<0;若s1>s2，返回值>0。(5)子串查找IndexStr(s，t):找子串t在主串s中首次出现的位置(也称模式匹配)。操作条件:串s，t存在。操作结果:若t是s的子串，则返回t在s中首次出现的位置，否则返回值为0。[例5-8]子串定位。下一页返回上一页5.1串的定义和基本运算(6)串插入InsStr(s，t,i)。操作条件:串s，t存在操作结果:将串t插入到串、的第i个字符前，s的串值发生改变。(7)串删除DelStr(s，i,len)o操作条件:串s存在操作结果删除串s中第i个字符起长度为len的子串，s的串值改变。返回上一页5.2串的表示和实现5.2.1定长顺序存储在C++语言中，字符串顺序存储可以用一个字符型数组和一个整型变量表示，其中字符数组存储串值，整型变量表示串的长度。下一页返回5.2串的表示和实现5.2.2链接存储对于长度不确定的字符串的输入，若采用定长字符串存储就会产生这样的问题:存储空间定符大，而实际输入字符串长度小，则造成内存空间的浪费;反之，存储空间定符小，而实际输入字符串长度大，则不够存储。此时可采用链接存储的方法。1.链接存储的描述用链表存储字符串，每个结点有两个域:一个数据域(data)和一个指针域(next)。下一页返回上一页5.2串的表示和实现其中:数据域(data)-存放串中的字符;指针域(next)-存放后继结点的地址。仍然以存储S="StringStructure”为例，链接存储结构如图5-1所示。(1)链接存储的优点—插入、删除运算方便;(2)链接存储的缺点-存储、检索效率较低。2.串的存储密度在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几百万个字符，情报资料的几千万个条目，这要求在处理时必须考虑字符串的存储密度。存储密度=串值所占的存储位/实际分配的存储位。下一页返回上一页5.2串的表示和实现串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串的连接等操作的实现比较方便。3.大结点结构为了提高存储空间的利用率，有人提出了大结点的结构(即串的链块表示)。所谓大结点，就是一个结点的值域存放多个字符，以减少链表中的结点数量，从而提高空间的利用率。例如每个结点存放四个字符，如图5-2所示。这样一来，存储空间利用率明显提高，但插入、删除极不方便，所以链接存储的优点也消失了。由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较少。下一页返回上一页5.2串的表示和实现5.2.3串的堆分配存储结构在实际应用中，往往要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储(也称为索引存储)，这是一种动态存储结构。1.堆分配存储的方法(1)开辟一块地址连续的存储空间，用于存储各串的值，该存储空间称为“堆”(也称为自由存储区)。(2)另外建立一个索引表，用来存储串的名字(name)、长度(length)和该串在"堆"中存储的起始地址(Stradr)。(3)程序执行过程中，每产生一个串，系统就从“堆”中分配一块大小与串的长度相同的连续空间，用于存储该串的值，并且在索引表中增加一个索引项，用于登记该串的名字、长度和该串的起始地址。下一页返回上一页5.2串的表示和实现2.索引存储的例子设字符串:A="Red"B=”Yellow"G=”Blue"D=”White”用指针free指向堆中末使用空间的首地址。索引表如图5-3所示。考虑到对字符串的插入和删除操作，可能引起串的长度变化，在“堆”中为串值分配空间时，可预留适当的空间。这时，索引表的索引项应增加一个域，用于存储该串在“堆”中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。下一页返回上一页5.2串的表示和实现3.带长度的索引表的G语言描述索引项的结点类型为:4.“堆”的管理G语言中用动态分配函数malloc()和free()来管理“堆”。利用函数malloc()为每个新串分配一块实际串长所需要的存储空间，分配成功则返回一个指向起始地址的指针作为串的基址，同时，约定的串长也作为存储结构的一部分。函数free()则用来吸收用malloc()分配的存储空间。下一页返回上一页5.2串的表示和实现在G++语言中malloc()可用new替换，而free()也可用delete代替。这里仅简单地介绍了堆分配存储的基本思想，具体的算法及细节尚未涉及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠性也更高。本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除等运算。为了讨论方便再次描述定长顺序串的结构如下:下一页返回上一页5.2串的表示和实现在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如G语言中处理定长串的方法就是这样的，用‘\0‘来表示串的结束，如图5-4所示。返回上一页5.3串的基本运算1.求串的长度用判断当前字符是否是‘、0’来确定串是否结束，若非‘、0'，则表示字符串长度的i加1;若是‘\0'，则表示字符串结束，跳出循环，i即字符串的长度。下一页返回5.3串的基本运算2.串连接两个串r1和r2首尾连接成一个新串r1即:r1=r1+r2。下一页返回上一页5.3串的基本运算3.求子串在给定字符串r中从指定位置i开始连续取出j个字符构成子串r1。下一页返回上一页5.3串的基本运算下一页返回上一页5.3串的基本运算4.串相等比较两个串的长度相等且各对应位置上的字符都相等时，两个串才相等。5.插入子串在字符串r中的指定位置i插入子串r1。下一页返回上一页5.3串的基本运算下一页返回上一页5.3串的基本运算6.删除子串在给定字符串r中删除从指定位置i开始的连续j个字符。下一页返回上一页5.3串的基本运算7.模式匹配模式匹配即子串定位运算。设‘和t是给定的两个串，在主串‘中找到等于子串t的过程称为模式匹配。其中被匹配的主串‘称为目标串，匹配的子串t称为模式。这里只介绍一种最简单的模式匹配算法。(1)基本思想首先将s1与t1进行比较，若不同，就将s2与t1进行比较，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符ti不同时，则s返回到本趟开始字符的下一个字符，即si-j+2,t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是i-j+1,否则,匹配失败。下一页返回上一页5.3串的基本运算(2)模式匹配的例子主串s=”ABABCABCACBAB"，模式t="ABCAC“。匹配位置:i-j+1=11-6+1=6(3)算法描述返回在字符串r中子串r1出现的位置。下一页返回上一页5.3串的基本运算(4)时间复杂度分析设串s长度为n，串t长度为m。匹配成功的情况下，考虑下面两种极端情况。在最好情况下，每趟不成功的匹配都发生在第一对字符比较时。例如:s=”AAAAAAAAAABC”t=”BC”设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下的平均比较次数是下一页返回上一页5.3串的基本运算即最好情况下的时间复杂度是0(n+m)。在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符。例如:s=”AAAAAAAAAAAB"t=”AAAB”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是因为n>>m，所以最坏情况下的时间复杂度是0(n*m)。返回上一页5.4数组5.4.1数组的基本概念数组是n(n>1)个相同类型数据元素a1,a2,...,an构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。由此可见，数组的定义类似于采用顺序存储结构的线性表。数组具有以下性质。(1)数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组唯一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。下一页返回5.4数组5.4.2数组的存储结构在一维数组中，一旦a。的存储地址LOG(a1)确定，并假设每个数据元素占用k个存储单元，则任一数据元素a，的存储地址LOG(ai)就可由以下公式求出LOC(ai)=LOC(a1)+(i-1)*k(0«i«n)上式说明，一维数组中任一数据元素的存储地址可直接计算得到，即一维数组中任一数据元素可直接存取，因此，一维数组是一种随机存储结构。同样，二维及多维数组也满足随机存储特性。对于一个m行n列的二维数组Amxn,有下一页返回上一页5.4数组将Am*n，简记为A,A是这样的一维数组:显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。依次类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。下一页返回上一页5.4数组对于二维数组来说，由于计算机的存储结构是线性的，如何用线性的存储结构存放二维数组元素就有一个行/列次序排放问题。以行序为主序的存储方式:即先存储第1行，然后紧接着存储第2行，最后存储第m行。此时，二维数组的线性排列次序为对于一个已知以行序为主序的计算机系统，当二维数组第一个数据元素a1,1的存储地址LOC(a1,1)和每个数据元素所占用的存储单元k确定后，则该二维数组中任一数据元素ai,j的存储地址可由下式确定下一页返回上一页5.4数组LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k式中，n为列数。同理可推出在以列序为主序的计算机系统中有:LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k式中，m为行数。[例5-9]对二维数组floata[5][4]进行计算。(1)数组a中的数组元素数目;(2)若数组a的起始地址为2000，且每个数组元素长度为32位(即4个字节)，数组元素a[3][2]的内存地址。解由于G语言中数组的行、列下界均为0，该数组行上界为5-1=4，列上界为4-1=3，所以该数组的元素数目共有(4-0+1)*(3-0+1)=5*4=20个。下一页返回上一页5.4数组又由于G语言采用行序为主序的存储方式，则有LOC(a3,2)=LOC(a0,0)+(i*n-j)*k=2000+(3*4+2)*4=20565.4.3特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说，使多个相同的非零元素共享同一个存储单元，对零元素不分配存储空间。特殊矩阵的主要形式有对称矩阵、对角矩阵等，它们都是方阵，即行数和列数相同。下一页返回上一页5.4数组1.对称矩阵的压缩存储若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i(0«i,j«n-1),则称其为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。这样，就可以将个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，以行序为主序存储其下三角(包括对角线)的元素。个元素n(n+1)/2个元素下一页返回上一页5.4数组上三角矩阵:下一页返回上一页5.4数组下三角矩阵:2.对角矩阵的压缩存储若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线，称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0«b«(n-1)/2)的对角矩阵，其|i-j|«b的元素ai,j不为零，其余元素为零。如图5-6所示。下一页返回上一页5.4数组ABa[i][j]b[k]当b=1时称为三对角矩阵。其压缩地址计算公式为:k=2i+j。[例5-10]按行优先顺序和按列优先顺序列出四维数组A[2][2][2][2]所有元素在内存中的存储次序。解按行优先的存储次序下一页返回上一页5.4数组按列优先的存储次序:[例5-11]对于二维数组A[m][n]，其中m«80,n«80，先读入m和n，然后读该数组的全部元素，对如三种情况分别编写相应函数。(1)求数组A靠边元素之和;(2)求从A[0][0]开始的行、列互不相邻的各元素之和;(3)当m=n时，分别求两条对角线上的元素之和，否则打印出m≠n的信息。下一页返回上一页5.4数组解(1)对应算法如下:下一页返回上一页5.4数组(2)对应算法如下:下一页返回上一页5.4数组(3)对应算法如下:返回上一页5.5稀疏矩阵一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小，即s<<t时，称该矩阵为稀疏矩阵。例如一个100x100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。5.5.1稀疏矩阵的三元组表示稀疏矩阵的压缩存储方法是只存储非零元素。由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组(i，j，ai，j)唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表。下一页返回5.5稀疏矩阵假设有一个6x7阶稀疏矩阵A(为图示方便，这些所取的行列数都很小)，A中元素如下所示。则对应的三元组线性表为:下一页返回上一页5.5稀疏矩阵若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。则三元组顺序表的数据结构可定义如下:下一页返回上一页5.5稀疏矩阵其中，data域中表示的非零元素通常以行序为主序顺序排列，它是一种下标按行有序的存储结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设data域按行有序存储。(1)从一个二维矩阵创建其三元组表示以行序方式扫描二维矩阵A，将其非零的元素插人到三元组t的后面。算法如下:下一页返回上一页5.5稀疏矩阵(2)三元组元素赋值先在三元组t中找到适当的位置k，将k~t.nums个元素后移一位，将指定元素x插入到t.data[k]处。算法如下:下一页返回上一页5.5稀疏矩阵下一页返回上一页5.5稀疏矩阵(3)将指定位置的元素值赋给变量先在三元组t中找到指定的位置，将该处的元素值赋给x。算法如下:下一页返回上一页5.5稀疏矩阵(4)输出三元组从头到尾扫描三元组t，依次输出元素值。算法如下:下一页返回上一页5.5稀疏矩阵(5)矩阵转置对于一个mxn的矩阵Amxn，其转置矩阵是一个nxm的矩阵。设为尽Bnxm,满足ai,j=bj,i，其中1«i«m，1«j«n。其完整的转置算法如下:下一页返回上一页5.5稀疏矩阵下一页返回上一页5.5稀疏矩阵以上算法的时间复杂度为0(t.cols*t.nums)