第四章 字符串、数组和广义表

《第四章 字符串、数组和广义表》由会员分享，可在线阅读，更多相关《第四章 字符串、数组和广义表（64页珍藏版）》请在装配图网上搜索。

1、第四章第四章 字符串、数组和广义表字符串、数组和广义表 4.1 字符串的基本概念 4.2 字符串的存储结构 4.3 字符串的模式匹配 4.4 数组的基本概念 4.5 矩阵的压缩存储 4.6 广义表 4.7 典型例题 4.1字符串基本概念字符串基本概念字符已成为非数值应用重要的处理对象.如文字编辑,情报检索,自然语言翻译和各种事务处理系统等。字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时,称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的串相应地称为主串。在C语言中,字符串常量是用一对双

2、引导括起来若干字符来表示。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示.例4.1:假如a,b,c,d为如下的四个串:a=“BEI”,b=“JING”c=“BEIJING”,d=“BEIJING”则它们的长度为：3，4，7和8；并且a和b都是c和d的子串；a在c和d中的位置都是1；而b在c中的位置是在d中的位置是5。另外，每个字符串的最后一个有效字符之后有一个字符串结束符，记为0。字符串通常存于足够大的字符数组中。如要称两个串是相等的，当且仅当这两面个串的值相等。也就是说，只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。4.

3、24.2字符串的存储结构字符串的存储结构对于字符串常量，只需作为一个字符的序列存储。对于字符串变量，赋给它一个串名，对串运算时，通过变量名访问其值。其存储分配有两种形式，一是将字符串设计成一种结构类型（如pascal语言和c语言中，字符串都是用字符数组来实现），从字符串名可直接访问到字符串值，字符串值的存储分配是在编译时完成的；另一是字符串值的存储分配在程序运行时完成，在字符串名和字符串值之间需建立一个对照表（称为串名的存储映象），字符串的访问通过串名的存储映象进行。我们称前一种为顺序存储结构，后一种为链式存储结构。4.2.14.2.1串的存储结构串的存储结构 和线性表的顺序存储结构类似，用一

4、组地址连续的存储单元存储串的字符序列。在C语言中用一维数组来实现。（一）紧缩格式假定，一个存储单元可存放K个字符，而且给出的串长度为N，那么此字符串的字符串值就要占N/K个存储单元紧缩格式是以字符为单位依次将字符存放在存储单元里。（PASCAL语言中的紧缩数组）（二）非紧缩格式在一个存储单元中存放一个字符，所需存储单元个数就是串长。紧缩格式可节省存储空间，但在进行串运算时需要花费较时间去分离同一存储单元中的字符。4.2.2串的链式存储结构和线性表的链式存储结构类似，也可采用链表方式存储串值。由于串结构的特殊性结构中的每个数据元素是一个字符，则可用链表存储串值时，存在一个“结点大小”的问题，即每

5、个结点可以存放一个字符，也可存放多个字符。head 结点大小为4示图 head 结点大小为1示图 A BDCE F GHI 000A B C D 4.3 字符串的模式匹配字符串的模式匹配设s和t是给定的两个串，在串s中寻找等于t的子串的位置的过程称为模式匹配，其中，s串称为主串，t串称为模式，如在s中找到等于t的子串，则称匹配成功，并返回模式t在s串的序号：反之匹配失败，并返回于序号为零。例4.2:1、s=“abcdefg”,t=“efg”则模式t在主串s中的序号等于52、s=“abcdefg”,t=“abcdg”则t在s中的序号等于03s=“abcdefabc”,t=“abc”如从s串的第一

6、个字符开始搜索则序号等于1；如从s第三个字符开始搜索，则序号等于7。4.3.1模式匹配的BF算法算法的基本思想是：从主串s的第一个字符起和模式的第一趟匹配。第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配过程如下 i=2第一趟匹配 a b a b c a b c a c b a b a b c j=2

7、 i=1第二趟匹配 a b a b c a b c a c b a b a j=0 i=6第三趟匹配 a b a b c a b c a c b a b a b c a c j=4 i=3 t在s中的模式匹配过程(续)i=3第四趟匹配 a b a b c a b c a c b a b a j=0 i=4第五趟匹配 a b a b c a b c a c b a b a j=0 i=10第六趟匹配 a b a b c a b c a c b a b a b c a c j=5方法一：BF算法的实现函数：intindex(chars,chart,intstart)intI,j,m,n;m=str

8、len(s);n=strlen(t);if(startm+1|n=0)return(0);elsei=start;/*从S中的第start位开始匹配*/j=0;while(im&j=n)return(i-n);elsereturn(0);方法二：BF算法也可用如下函数表示：intsimplematch(char*s,char*t)intn=strlen(s),m=strlen(t),i,j,k;for(j=0;jn-m;j+)/*顺序考察从si开始的子串*/for(i=0;im&sj+i=ti;i+)/*从sj开始的子串与t比较*/if(i=m)returnj+1;return04.3.2模式

9、匹配的KMP算法在执行简单匹配算法中的字符比较过程中，当出现sj+I!=tI时，有s0sj,sj+1 sj+i-1,sj+i !=t0 t1 ti-1 ti 这时，简单匹配算法对字符串S要回溯，回溯到从sj+1开始继续与模式字符串T从头开始逐一字符比较，KMP算法是对正文字符串比较不回溯的算法。如果对于模式字符串t存在一个整数k(kp&*q-1=)/*设定字符串的结束符*/15（4）;16else*q=0;17return (5);1819voidmain()2021charstr=”weareChinese“22printf(“%sn”,sdel(str);234.4 4.4 数组的基本概念

10、数组的基本概念在概念上，数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。在C语言中，约定数组的第一个元素的下标为0，其余依次类推，由n个元素组成的数组，其最后一个元素的下标为n-1。数组元素可以是任何类型的，当元素本身又是数组时就构成多维数组。数组通常是顺序存储的，对于多维数组，C语言按行优先顺序存放。如有以下数组定义：int a110,a289,a3789；则数组a1是一维数组，a2是二维数组，a3是三维数组。记元素X的内存地址为Loc(x),设每个元素所需内存字节数为s，存储元素a

11、1 i,a2ij,a3ijk的内存地址分别可由以下算式确定：内存地址计算Loc(a1i)=Loc(a10)+i*sLoc(a2 ij)=Loc(a200)+(i*9+j)*sLoc(a3ijk)=Loc(a3000)+(i*8+j)*9+k)*s若用C语言的指针来描述，以上算式可分别简成：&a1i=&a10+i&a2ij=&a200+i*9+j&a3ijk)=&a3000+(i*8+j)*9+k当然数组也可按列优先顺序存放。4.5 4.5 矩阵的压缩存储矩阵的压缩存储4.5.1 特殊矩阵的压缩特殊矩阵：假若值相同的数据元素或者零元 素在矩阵的分布有一定的规律，则我们称此类矩为特殊矩阵。1对称矩

12、阵 若一个n阶矩阵A中的元素满足下述性质：aij=aji,0i,jn-1则称为n阶对称矩阵。一维数组下标k与i,j对应关系k=i(i+1)/2+j 当ij(下三角存贮)j(j-1)/2+i 当ij(上三角存贮)如一一对应需n2个存储单元的矩阵压缩存储仅需1+2+3+n=n(n+1)/2个存储单元。下三角存储数组sak，如图4-7所示。则LocAij=LocA00+(i(i+1)/2)+j*s2、三角矩阵若一个n阶矩阵中的元素满足下述性质；当ij时aij=0且oi,jn-1则称为上三角矩阵。下三角矩阵示图 3、对角矩阵所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角

13、线上、下方若干条对角线上的元素之外，所有其它的元素皆为零。地址计算公式：LocAij=LocA00+i(2d+1)+(2d+1)+(j-i)*s当非零元素的个数只占矩阵元素总数的25%30%或低于这个有百分数时，我们称这样的矩阵为稀疏矩阵。4.5.2稀疏矩阵1、用三元组数组表示稀疏矩阵可以用一元组（i,j,aij）唯一确定矩阵中的非零元素压缩存储概念，只存稀疏矩阵的非零元素。图4-9稀疏矩阵可表示为（0，1，12），（1，0，7）（1，4，1）（2，2，8）（3，1，6）（4，0，18）（4，2，7）的一维数组。在C语言描述算法的数据结构定义如下：#define MAX 100struct n

14、ode int row;int colum;int value;tyredef struct node NODE;NODE maxMAX;2、稀疏矩阵的十字链表表示法：在十字链表中，稀疏矩阵的每一行用一个带表头节点的循环表示，每一列也用一个带表头的循环链表表示。在这个结构中，除表头节点外，每一个节点都代表矩阵中的一个非零元素，它由五个域组成；行域（row），列域（col）,值域(val),向下域(down)和向右域(right)。节点结构和存储表示如下：表结点 行（列）头结点 表头结点 Down rowrightcowvolrightdown00linkmnlink举例（）若有矩阵M如下:例题

15、目：求一个3*3矩阵对角线元素之和1.程序分析：利用双重for循环控制输入二维数组，再将aii累加后输出。2.程序源代码：#includevoidmain()floata33,sum=0;inti,j;printf(pleaseinputrectangleelement:n);for(i=0;i3;i+)for(j=0;j3;j+)scanf(%f,&aij);for(i=0;i3;i+)sum=sum+aii;printf(duijiaoxianheis%6.2f,sum);例题目：将一个数组逆序输出。1.程序分析：用第一个与最后一个交换。2.程序源代码：#defineN5vodmain()

16、intaN=9,6,5,4,1,i,temp;printf(noriginalarray:n);for(i=0;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+)temp=ai;ai=aN-i-1;aN-i-1=temp;printf(nsortedarray:n);for(i=0;itag)x=(4);elsex=(5);if(x)return(6);return0;4.7典型例题1以下能正确定义一维数组的选项是_。A）intnum;B）#defineN100;intnumN;C）intnum0100D）intN=100;intnumN;答案B)（知识点：一维数组的定

17、义）2假设int类型变量占用两个字节，其有定义：intx10=0,2,4;，则数组x在内存中所占的字节数是_。A）3B）6C）10D）20答案D)（知识点：一维数组的定义）4.7典型例题3以下程序运行后的输出结果是_。main()inti,n=0,0,0,0,0;for(i=1;i=4;i+)ni=ni-1*2+1;printf(%d,ni);答案13715（知识点：一维数组的定义与引用）4.7典型例题4以下数组定义中不正确的是_。A）inta23;B）intb3=0,1,2,3;C）intc100100=0；D）int3=1,2,1,2,3,1,2,3,4;分析二维数组初始化时，对数组第一维

18、的长度可以不指定，但第二维的长度不能省略。答案D）（知识点：二维数组的初始化）4.7典型例题5有以下程序：main()intaa44=1,2,3,4,5,6,7,8,3,9,10,2,4,2,9,6;inti,s=0;for(i=0;i4;i+)s+=aailprintf(%dn,s)执行后的输出结果是_。A）11B）19C）13D）20分析该程序是求aa0l、aa1l、aa2l、aa3l之和并输出。答案B）（知识点：二维数组的定义、引用及初始化）4.7典型例题6以下不能正确进行字符串赋初值的语句是_。A）charstr5=good!;B）charstr=good!;C）charstr6=go

19、od!;D）charstr5=g,o，o，d;分析每个字符串末尾都有一个结束0，因此，字符串good!在内存中占6个字符型存储单元，在初始化时，可以不指定数组的大小，或指定一个大于或等于6的值。选项D中给出的初值个数小于数组的大小5，则将初值赋给数组前面的元素，其后的元素值为0。答案A）（知识点：字符数组的初始化）4.7典型例题7以下程序的输出结果是_。main()charch35=AAAA,BBB,CC；printf(%sn,ch1);A）AAAA B）BBBC）BBBCCD）CC分析程序中定义ch是一个字符型的二维数组，由于二维数组可以看做是由一维数组构成的一维数组，ch35是由ch0、c

20、h1、ch2构成的，而ch0、ch1、ch2又都是由5个字符型元素构成的一维数组，因此ch1即是二维数组ch35的第二行的字符串BBB所在一维数组的名字，因为其元素是字符类型，可以用数组的名字（即数组的首地址）来表示所存储的字符串BBB，输出时去掉字符串定界符“”。答案B）（知识点：字符数组的初始化）4.7典型例题8有下列程序：main()chars=n123printf(%d,%dn,strlen(s),sizeof(s);程序运行后的输出结果是_。A）赋初值的字符串有错B）6,7C）5,6D）6,6分析程序的输出结果是strlen(s)和sizeof(s)两个函数的值。函数strlen(s

21、)是求字符串s（用字符数组存储）的长度，即字符串s中有效字符的个数，不包括字符串结束标志0,根据对s的初始化处理，字符串s中包含两个转义字符n和，因此字符串s的长度为5。函数sizeof(s)是求字符数组s在内存中所占的字节数，根据程序中对s的初始化处理，字符数组s的长度省略，即由其后的初始值来确定，是字符串s中有效字符的个数加1（即加上字符串结束标志0），为6，由于每个数组元素是字符类型，在内存中占一个字节，所以字符数组s在内存中所占的字节数为6。注意，如果字符串s的长度在定义时给出了确定的值，则计算其在内存中所占字节数时，按给定的长度计算。答案C）（知识点：字符串处理函数、转义字符）4.7

22、典型例题9当执行下面的程序时，如果输入ABC，则输出是_。#include#includemain()charss10=12345;gets(ss);strcat(ss,6789);printf(%s,ss);A）ABC6789B）ABC67C）12345ABC6D）ABC456789分析程序开始虽然对字符数组ss进行了初始化，但其后又用函数gets(ss)从键盘上重新输入为字符串ABC，再通过函数strcat(ss,6789)将字符串6789连接到ss的尾部，字符串ss即为ABC6789。答案A）（知识点：字符串处理函数）4.7典型例题10下列程序执行后的输出结果是_。main()chara

23、rr24;strcpy(arr0,you);strcpy(arr1,me);arr03=&;printf(%sn,arr0);A）you&meB）youC）meD）err分析程序中定义了二维字符数组arr24，即包括两个字符型一维数组arr0和arr1，通过两个字符串复制函数strcpy(arr0,you)和strcpy(arr1,me)将字符串you和字符串me分别复制到arr0和arr1，这时，再赋arr03的值为字符&，即覆盖了字符串you后的字符串结束标志0，由于二维数组在内存中是按行连续存放的，当输出字符串arr0时，将从arr0的第一个字符开始输出，直到遇到第一个字符串结束标志0（即arr1中字符串me后的结束标志）为止。答案A）（知识点：字符串处理函数）4.7典型例题作业P62二.4P62三.1,4