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

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

4.1

字符串的基本概念

4.2

字符串的存储结构

4.3

字符串的模式匹配

4.4

数组的基本概念

4.5

矩阵的压缩存储

4.6

广义表

4.1字符串基本概念

字符已成为非数值应用重要的处理对象.如文字编辑,情报检索,自然语言翻译和各种事务处理系统等。字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时,称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的串相应地称为主串。在C语言中,字符串常量是用一对双引导括起来若干字符来表示。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示.例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.2字符串的存储结构对于字符串常量，只需作为一个字符的序列存储。对于字符串变量，赋给它一个串名，对串运算时，通过变量名访问其值。其存储分配有两种形式，一是将字符串设计成一种结构类型（如pascal语言和c语言中，字符串都是用字符数组来实现），从字符串名可直接访问到字符串值，字符串值的存储分配是在编译时完成的；另一是字符串值的存储分配在程序运行时完成，在字符串名和字符串值之间需建立一个对照表（称为串名的存储映象），字符串的访问通过串名的存储映象进行。我们称前一种为顺序存储结构，后一种为链式存储结构。4.2.1串的存储结构和线性表的顺序存储结构类似，用一组地址连续的存储单元存储串的字符序列。在C语言中用一维数组来实现。（一）紧缩格式假定，一个存储单元可存放K个字符，而且给出的串长度为N，那么此字符串的字符串值就要占[N/K]个存储单元紧缩格式是以字符为单位依次将字符存放在存储单元里。（PASCAL语言中的紧缩数组）（二）非紧缩格式在一个存储单元中存放一个字符，所需存储单元个数就是串长。紧缩格式可节省存储空间，但在进行串运算时需要花费较时间去分离同一存储单元中的字符。4.2.2串的链式存储结构和线性表的链式存储结构类似，也可采用链表方式存储串值。由于串结构的特殊性——结构中的每个数据元素是一个字符，则可用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可存放多个字符。

head

结点大小为4示图

head

结点大小为1示图

ABDCEFGHI\0\0^\0ABCD4.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中的序号等于03﹑s=“abcdefabc”,t=“abc”如从s串的第一个字符开始搜索则序号等于1；如从s第三个字符开始搜索，则序号等于7。4.3.1模式匹配的BF算法算法的基本思想是：从主串s的第一个字符起和模式的第一趟匹配。第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配过程如下

i=2第一趟匹配ababcabcacbababcj=2i=1第二趟匹配ababcabcacbabaj=0i=6第三趟匹配ababcabcacbababcacj=4i=3t在s中的模式匹配过程(续)

i=3第四趟匹配ababcabcacbabaj=0i=4第五趟匹配ababcabcacbabaj=0

i=10第六趟匹配ababcabcacbababcacj=5方法一：BF算法的实现函数：int

index(char

s[],chart[],intstart){int

I,j,m,n;m=strlen(s);n=strlen(t);if(start<0||start+n>m+1||n==0)return(0);else{i=start;/*从S中的第start位开始匹配*/j=0;

while(i<m&&j<n)if(s[i]==t[j]){i++;j++}

else{i=i-j+1;j=0;}

if(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;j<n-m;j++)/*

顺序考察从s[i]开始的子串*/{for(i=0;i<m&&s[j+i]=t[i];i++)/*从s[j]开始的子串与t比较*/

if(i==m)returnj+1;}return0}4.3.2模式匹配的KMP算法在执行简单匹配算法中的字符比较过程中，当出现s[j+I]!=t[I]时，有s[0]…s[j],s[j+1]…s[j+i-1],s[j+i]…!=t[0]t[1]t[i-1]t[i]…这时，简单匹配算法对字符串S要回溯，回溯到从s[j+1]开始继续与模式字符串T从头开始逐一字符比较，KMP算法是对正文字符串比较不回溯的算法。如果对于模式字符串t存在一个整数k(k<i)，使得模式t的开头k个字符（t[0],t[1],…,t[k-1]）依次与t[I]的前面k个字符（t[i-k],t[i+k-1],…,t[i-1]）相同，即KMP算法t[0]…t[i-k],t[i-k+1]…t[i-1],t[i]…

t[0]t[1]…t[k-1]t[k]…

由以上两个对应关系有s[0]…s[j]…s[j+i-k]…s[j+i-1]s[j+I]s[i+]…

t[0]…t[i-k]…t[i-1]t[i]…

t[0]…t[k-1]t[k]…KMP算法（续）因此，可以模式T的t[k]开始与正文s的s[j+i]开始依次继续比较，这就省去了前面的k次比较。如对应t[i]的k有多个，应取最大的k。这样，在匹配比较过程中，一旦出现t[i]!=s[j+i]时，就要找出t[i]的k，称k为t[i]的失败链接值。寻找t的各字符的失败链接值，只与模式t本身有关，与正文S无关。求t的各字符的失败链接值算法如下：设置一个一维数组next[]，其元素个数与t的长度相同，依次存放t的各字符的失败链接值。首先置next[0]=-1,然后假定在next[0],…,next[j-1]已知情况下，求next[j]。如，next[j-1]=k，又有t[k]=t[j-1]，那么置next[j]为next[j-1]+1;如t[k]!=t[j-1],令k1=next[k],如t[k1]=t[j-1]，置next[j]为ki+1;如t[k1]!=t[j-1],则按t[k1]的失败链接值再继续寻找，直至找到一个失败链接值kn,使得t[kn]=t[j-1],或kn=-1,这时置next[j]=kn+1。寻找模式各字符失败链接值的函数

voidfaillink(char*t,intnext[]){intj,k;next[0]=-1;j=1;do{k=next[j-1];while(k!=-1&&t[k]!=t[j-1])k=next[k];next[j++]=k++;}while(p[j]!=’\0’);}KMP模式匹配函数

int

kmp_match(char*t,char*p,intnext[]){intk,j;if(*s==’\o’)return0;for(k=j=0;s[k]!=’\0’;){while(j!=-1&&t[j]!=s[k])j=next[j];

k++;j++;if(t[j]==’\0’)returnk-j;}return–1;例4-3(1)例4.3：本程序中定义的函数sdel(s)实现的功能是将已知字符串s中的前导空白符和尾随空白符删去，并将字符中间部分的连续多个空白符删减为一个空白符。例4-3(2)程序1：1#include"stdio.h"2char*sdel(char*s)3{4char*p=s,*q=s;5for(;(1);s++)/*删去前导空白符*/6for(;*s;)/*遍历s字符串的其他字符串*/7{8*q++=*s;9if(*s!=’’)(2);例4-3(3)

10else11while((3))12s++;13}14if(q>p&&*q-1==’’)/*设定字符串的结束符*/15

（4）;16else*q=’\0’;17return

(5);18}19voidmain()20{21charstr[]=”weareChinese“22printf(“%s\n”,sdel(str));23}4.4数组的基本概念

在概念上，数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。在C语言中，约定数组的第一个元素的下标为0，其余依次类推，由n个元素组成的数组，其最后一个元素的下标为n-1。数组元素可以是任何类型的，当元素本身又是数组时就构成多维数组。数组通常是顺序存储的，对于多维数组，C语言按行优先顺序存放。如有以下数组定义：

inta1[10],a2[8][9],a3[7][8][9]；则数组a1是一维数组，a2是二维数组，a3是三维数组。记元素X的内存地址为Loc(x),设每个元素所需内存字节数为s，存储元素a1[i],a2[i][j],a3[i][j][k]的内存地址分别可由以下算式确定：内存地址计算Loc(a1[i])=Loc(a1[0])+i*sLoc(a2[i][j])=Loc(a2[0][0])+(i*9+j)*sLoc(a3[i][j][k])=Loc(a3[0][0][0])+((i*8+j)*9+k)*s若用C语言的指针来描述，以上算式可分别简成：

&a1[i]=&a1[0]+i&a2[i][j]=&a2[0][0]+i*9+j&a3[i][j][k])=&a3[0][0][0]+((i*8+j)*9+k当然数组也可按列优先顺序存放。4.5矩阵的压缩存储4.5.1特殊矩阵的压缩特殊矩阵：假若值相同的数据元素或者零元素在矩阵的分布有一定的规律，则我们称此类矩为特殊矩阵。1﹑对称矩阵若一个n阶矩阵A中的元素满足下述性质：aij=aji,0≤i,j≤n-1则称为n阶对称矩阵。一维数组下标k与i,j对应关系k=i(i+1)/2+j当i≥j(下三角存贮)j(j-1)/2+i当i<j(上三角存贮)如一一对应需n2个存储单元的矩阵压缩存储仅需1+2+3+…+n=n(n+1)/2个存储单元。下三角存储数组sa[k]，如图4-7所示。则LocA[i][j]=LocA[0][0]+[(i(i+1)/2)+j]*s

2、三角矩阵

若一个n阶矩阵中的元素满足下述性质；当i<j时，aij=0且o≤i,j≤n-1则称为下三角矩阵（如图4-5-3所示），当i>j时aij=0且o≤i,j≤n-1则称为上三角矩阵。下三角矩阵示图

3、对角矩阵所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素皆为零。地址计算公式：LocA[i][j]=LocA[0][0]+[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语言描述算法的数据结构定义如下：#defineMAX100structnode{introw;int

colum;intvalue;}tyredef

structnodeNODE;NODEmax[MAX];2、稀疏矩阵的十字链表表示法：在十字链表中，稀疏矩阵的每一行用一个带表头节点的循环表示，每一列也用一个带表头的循环链表表示。在这个结构中，除表头节点外，每一个节点都代表矩阵中的一个非零元素，它由五个域组成；行域（row），列域（col）,值域(val),向下域(down)和向右域(right)。节点结构和存储表示如下：表结点行（列）头结点表头结点

Downrowrightcowvolrightdown^^00linkmnlink举例（１）若有矩阵M如下:例４－８题目：求一个3*3矩阵对角线元素之和

1.程序分析：利用双重for循环控制输入二维数组，再将a[i][i]累加后输出。

2.程序源代码：#include<stdio.h>

voidmain()

{

floata[3][3],sum=0;

int

i,j;

printf("pleaseinputrectangleelement:\n");

for(i=0;i<3;i++)

for(j=0;j<3;j++)

scanf("%f",&a[i][j]);

for(i=0;i<3;i++)

sum=sum+a[i][i];

printf("duijiaoxianheis%6.2f",sum);

}例４－９题目：将一个数组逆序输出。

1.程序分析：用第一个与最后一个交换。

2.程序源代码：#defineN5

vodmain()

{int

a[N]={9,6,5,4,1},i,temp;

printf("\noriginalarray:\n");

for(i=0;i<N;i++)

printf("%4d",a[i]);

for(i=0;i<N/2;i++)

{temp=a[i];

a[i]=a[N-i-1];

a[N-i-1]=temp;

}

printf("\nsortedarray:\n");

for(i=0;i<N;i++)

printf("%4d",a[i]);

}4.6广义表在前面章节中，线性表被定义成一个有限序列（a1,a2,a3,…,an），其中ai限定为数据元素，有时这种限制需要拓宽。例如：描述世界女排邀请赛的参加国以及部分国家的参赛队的情况：（古巴，巴西，（国家，四川，江苏），秘鲁，俄罗斯，美国，(),日本）在这个拓宽了的线性表中，韩国队应排在美国队后，但未出席，成为空表。国家队，四川队，江苏队做为东道主的代表队参赛，构成一个小线性表，成为原线性表的一个数据项。这种推广了的线性表就称为广义表。定义1、广义表是n(n≥0)个数据元素d0,d1,d2,…dn-1的有限序列。其中di(0≤i≤n-1)或是单个数据元素，或仍是一个广义表，通常记为L=（d0,d2,…,dn-1）。L为广义表的名字，n是其长度，如果di也是一个广义表，称它为L的子表。d0是表头，d1,d2,…,dn-1为表尾。2、为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素。广义表用圆括号括起来，括号内数据元素之间用逗号间隔。定义例4.13：D=（）空表，其长度为零；A=（a,(b,c)）长度为2的广义表；其中第一元素为数据项’a’，第二个元素为线性表（b,c）。B=(A,A,())长度为3的广义表，前二个元素为表A，第三个元素为空表。C=(a,C)长度为2的递归的广义表，C相当于无穷表C=（a,(a,（…）)）。由例4.13可以得出两个结论：广义表可以为其它表共享广义表可以具有递归性。广义表除数据元素之间存在次序关系外，还存在层次关系。例4.14：G=（a,b,(c,(d))）中数据元素a,b为