第四章 字符串、數組和廣義表

第四章字符串、數組和廣義表

4.1

字符串的基本概念

4.2

字符串的存儲結構

4.3

字符串的模式匹配

4.4

數組的基本概念

4.5

矩陣的壓縮存儲

4.6

廣義表

4.1字符串基本概念

字符已成為非數值應用重要的處理對象.如文字編輯,情報檢索,自然語言翻譯和各種事務處理系統(tǒng)等。字符串是由某字符集上的字符所組成的任何有限字符序列.當一個字符串不包含任何字符時,稱它為空字符串。一個字符串所包含的有效字符個數稱為這個字符串的長度。一個字符串中任一連續(xù)的子序列稱為該字符串的子串。包含子串的串相應地稱為主串。在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’。字符串通常存于足夠大的字符數組中?！锶缫Q兩個串是相等的，當且僅當這兩面?zhèn)€串的值相等。也就是說，只有當兩個串的長度相等，并且各對應位置的字符都相等時才相等。4.2字符串的存儲結構對于字符串常量，只需作為一個字符的序列存儲。對于字符串變量，賦給它一個串名，對串運算時，通過變量名訪問其值。其存儲分配有兩種形式，一是將字符串設計成一種結構類型（如pascal語言和c語言中，字符串都是用字符數組來實現），從字符串名可直接訪問到字符串值，字符串值的存儲分配是在編譯時完成的；另一是字符串值的存儲分配在程序運行時完成，在字符串名和字符串值之間需建立一個對照表（稱為串名的存儲映象），字符串的訪問通過串名的存儲映象進行。我們稱前一種為順序存儲結構，后一種為鏈式存儲結構。4.2.1串的存儲結構和線性表的順序存儲結構類似，用一組地址連續(xù)的存儲單元存儲串的字符序列。在C語言中用一維數組來實現。（一）緊縮格式假定，一個存儲單元可存放K個字符，而且給出的串長度為N，那么此字符串的字符串值就要占[N/K]個存儲單元緊縮格式是以字符為單位依次將字符存放在存儲單元里。（PASCAL語言中的緊縮數組）（二）非緊縮格式在一個存儲單元中存放一個字符，所需存儲單元個數就是串長。緊縮格式可節(jié)省存儲空間，但在進行串運算時需要花費較時間去分離同一存儲單元中的字符。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的第一個字符起和模式的第一趟匹配。第一個字符比較之，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從主串的第二個字符起再重新和模式的字符比較之。依次類推，直至模式t中的每個字符依次和主串s中的一個連續(xù)的字符序列相等，則稱匹配成功，函數值為和模式t中第一個字符相等的字符在主串s中的序號，否則稱匹配不成功，函數值為零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配過程如下

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

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算法在執(zhí)行簡單匹配算法中的字符比較過程中，當出現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]開始繼續(xù)與模式字符串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算法（續(xù)）因此，可以模式T的t[k]開始與正文s的s[j+i]開始依次繼續(xù)比較，這就省去了前面的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]的失敗鏈接值再繼續(xù)尋找，直至找到一個失敗鏈接值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中的前導空白符和尾隨空白符刪去，并將字符中間部分的連續(xù)多個空白符刪減為一個空白符。例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語言按行優(yōu)先順序存放。如有以下數組定義：

inta1[10],a2[8][9],a3[7][8][9]；則數組a1是一維數組，a2是二維數組，a3是三維數組。記元素X的內存地址為Loc(x),設每個元素所需內存字節(jié)數為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當然數組也可按列優(yōu)先順序存放。4.5矩陣的壓縮存儲4.5.1特殊矩陣的壓縮特殊矩陣：假若值相同的數據元素或者零元素在矩陣的分布有一定的規(guī)律，則我們稱此類矩為特殊矩陣。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、對角矩陣所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元素之外，所有其它的元素皆為零。地址計算公式：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、稀疏矩陣的十字鏈表表示法：在十字鏈表中，稀疏矩陣的每一行用一個帶表頭節(jié)點的循環(huán)表示，每一列也用一個帶表頭的循環(huán)鏈表表示。在這個結構中，除表頭節(jié)點外，每一個節(jié)點都代表矩陣中的一個非零元素，它由五個域組成；行域（row），列域（col）,值域(val),向下域(down)和向右域(right)。節(jié)點結構和存儲表示如下：表結點行（列）頭結點表頭結點

Downrowrightcowvolrightdown^^00linkmnlink舉例（１）若有矩陣M如下:例４－８題目：求一個3*3矩陣對角線元素之和

1.程序分析：利用雙重for循環(huán)控制輸入二維數組，再將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廣義表在前面章節(jié)中，線性表被定義成一個有限序列（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為