第6講+字符串、數(shù)組和特殊矩陣

第6講

字符串、數(shù)組和特殊矩陣第6講

字符串、數(shù)組和特殊矩陣6.1字符串6.2字符串的模式匹配6.3

數(shù)組

6.4特殊矩陣

6.5

稀疏矩陣

6.1字符串串（或字符串）也是一個線性表，是由零個或多個字符組成的有限序列，一般記為：s=“a0a1…an-1”（n≥0）其中，s稱為串名；用雙引號括起來的字符序列稱為串值；每個ai都是字符。串的長度：n(≥0)為串的長度，表示串中字符的個數(shù)，其中表示方式中的""不是成員，是定界符。1、概念空串：當(dāng)n=0時，該串稱為空串，表示為""。空格串：一個串中有一個或多個空格組成，如："□

"、"□

□"子串：一個串中任何連續(xù)的字符序列都稱為該串的子串。如：s="abcdef"則："abc"、"cd"、"def"、"f"

都是s的子串。當(dāng)然，"abcdef"也是s的子串，""空串也是s的子串。主串：s相對于子串而言稱為主串。串相等：兩個串的長度相等且對應(yīng)位置上的子符都相同。子串在主串中的位置：子串的第一個字符在主串中首次出現(xiàn)的位置來表示。求串長復(fù)制串聯(lián)合兩個串比較兩個串的大小插入一個子串刪除一個子串模式匹配（檢查一個串是否是另一個串的子串）2、基本運算3、串的順序存儲結(jié)構(gòu)及運算實現(xiàn)

串的順序存儲——順序串(1)采用數(shù)組方式存儲

str數(shù)組：(2)數(shù)據(jù)類型定義0'a''b''c''d''e''f'…12345…MAX-1用順序表的形式表示：#defineMAX100typedefstruct{charstr[MAX];intlength;/*串長*/}seqstring;采用C語言的表示形式：#defineMAX100charstr[MAX];用

'\0'

作為串的結(jié)束標(biāo)記，則串的長度最大為MAX-1。串的基本運算(1)求串的長度intstrlen(chars[]){inti;for(i=0;s[i]!='\0';i++);returni;}0'a''b''c''d''e''\0'…12345…MAX-1intstrlen(chars[]){char*p=s;while(*p!='\0')p++;returnp-s;}(2)復(fù)制一個串voidstrcpy(chart[],chars[])/*s串到t串*/{inti;for(i=0;s[i];i++)t[i]=s[i];t[i]='\0';}(3)聯(lián)結(jié)兩個串在某個串的基礎(chǔ)上作聯(lián)結(jié)設(shè)聯(lián)結(jié)后的串長不超過MAX-1，則在s中形成聯(lián)結(jié)串；如超過MAX-1，則在t中適當(dāng)位置截斷。0'a''b''c''\0'…123…MAX-1s0'x''y''\0'…12…MAX-1tvoidstrcat(chars[],chart[]){inti,j;for(i=0;s[i];i++);/*s串掃描到空字符*/for(j=0;t[j]&&i<MAX-1;j++,i++)s[i]=t[j];s[i]='\0';}(3)聯(lián)結(jié)兩個串重新申請空間，存放聯(lián)結(jié)之后的串新申請的空間：0'a''b''c''\0'…123…MAX-1s0'x''y''\0'…12…MAX-1tchar*strcat(chars[],chart[]){intns,nt;char*p;ns=strlen(s);nt=strlen(t);p=(char*)malloc(ns+nt+1);strcpy(p,s);strcpy(p+ns,t);returnp;}0…123…strlen(s)+strlen(t)p4(4)串的比較兩個串相等：長度相等對應(yīng)位置上的字符都相等比較算法(s與t串比較)：依次比較對應(yīng)位置上的字符，兩者都未結(jié)束，找到第一個不相等的字符(s[i]≠t[i])若s[i]>t[i],返回s[i]-t[i](正數(shù)),則稱s>t若s[i]<t[i],返回s[i]-t[i](負(fù)數(shù)),則稱s<t其中一個字符串比較結(jié)束(s[i]≠t[i])若s[i]=='\0',有s[i]<t[i],返回s[i]-t[i](負(fù)數(shù)),則稱s<t若t[i]=='\0',有t[i]<s[i],返回s[i]-t[i](正數(shù)),則稱s>t兩串字符都比較結(jié)束(s[i]=‘\0’且t[i]='\0')有s[i]=='\0',t[i]=='\0',返回s[i]-t[i]

(0),則稱s==t算法實現(xiàn)intstrcmp(chars[],chart[]){inti;i=0;while(s[i]&&t[i]&&s[i]==t[i])i++;returns[i]-t[i];}s[i]&&s[i]==t[i]6.2字符串的模式匹配模式匹配：即子串在主串中定位運算概念設(shè)有兩個串s和t，檢查串t是否是s的子串，這種運算稱為模式匹配。其中：s串稱為正文(目標(biāo)串)，t串稱為模式串。匹配結(jié)果(順序串)匹配成功：返回t子串在s中第一次出現(xiàn)的起始位置(下標(biāo))匹配失敗：返回-1BF算法(Brute-Froce)

即樸素的模式匹配算法(1)BF算法的基本思想如：目標(biāo)串

s=“abbaba”，模式串t=“aba”。匹配結(jié)果：3設(shè)：i指示目標(biāo)串s當(dāng)前待比較的字符位置；j指示模式串t當(dāng)前待比較的字符位置。BF算法的模式匹配過程示意圖i=0開始i=1開始i=2開始i=3開始結(jié)果為3形參：兩個順序串返回：如出現(xiàn)送出起始位置下標(biāo)如不出現(xiàn)送出-1(2)順序串的BF模式匹配算法實現(xiàn)intBFindex(chars[],chart[]){inti,j,k;/*i為s串下標(biāo)，j為t串下標(biāo)，k為s串中比較時用的下標(biāo)*/for(i=0;s[i];i++)/*掃面s串*/{/*從s串下標(biāo)為i的字符開始與t串字符依次比較*/for(j=0,k=i;t[j]&&s[k]==t[j];k++,j++);if(t[j]=='\0')/*若t串被比較到空字符，則匹配成功*/returni;}return-1;}6.3數(shù)組1、概念一維數(shù)組由n(n≥1)個元素構(gòu)成的有限序列也是一個線性表，但該線性表不是空表，通常稱為向量。如：(a0,a1,

a2,…an-1)n≥16.3數(shù)組二維數(shù)組也是線性結(jié)構(gòu)，是一種線性表的線性表該線性表是由m(m≥1)個元素構(gòu)成而每個元素又是有n(n≥1)個元素構(gòu)成的線性表如：A(a0,a1,a2,…am-1)

其中：ai=(ai0,ai1,ai2,…ain-1)

通常A表示成：A=(aij)m×n()()()()()()()()()其中：數(shù)據(jù)元素類型相同三維數(shù)組

A=(aijk)m×n×p行列2、運算對于二維數(shù)組來說，只有對數(shù)組元素的訪問和修改，沒有刪除與插入運算。如：A=(aij)m×nB=(bij)m×nC=A+Bcij=aij+

bij3、數(shù)組的存儲結(jié)構(gòu)——采用順序存儲實現(xiàn)(1)一維數(shù)組

A=(a0,a1,

a2,…an-1)設(shè)ai為int型地址：1000a0a1a2…a1的地址=1004=a0的地址+(1-0)×4a2的地址=1008=a0的地址+(2-0)×4…………ai的地址=1000+4i=a0的地址+(i-0)×4若：a0的地址=LOC(a0)ai的地址=LOC(ai)元素所占字節(jié):l則：LOC(ai)=LOC(a0)+(i-0)*l3、數(shù)組的存儲結(jié)構(gòu)——采用順序存儲實現(xiàn)(2)二維數(shù)組

兩種存儲方式：()()()()()()()()()以行為主序(行優(yōu)先)——C采用以列為主序(列優(yōu)先)——FORTRAN采用a00a01…a02a10a11…a12a20a21…a220行1行2行a00a10…a20a01a11…a21a02a12…a220列1列2列問題：已知二維數(shù)組datatypea[m][n];若a00

的地址為：LOC(a00)=LOC(a[0][0])每個元素所占字節(jié)：l=sizeof(datatype)如何確定

LOC(aij)=LOC(a[i][j])的值？分析：二維數(shù)組以行為主序存放方法：假設(shè)a00

是第1個元素，求aij前有k各元素？(1)前面0行~i-1行所有元素的個數(shù)：k1=i*n(2)i行上aij前面有元素數(shù)：k2=j(3)aij之前共有元素數(shù)：k=k1+k2=i*n+j(4)則：LOC(aij)=LOC(a00)+(i*n+j)*lj列i行思考：若從a11開始存放，已知LOC(a11),求LOC(aij)？二維數(shù)組以列為主序存放方法：假設(shè)a00

是第1個元素，求aij前有k各元素？(1)前面0列~i-1列所有元素的個數(shù)：k1=j*m(2)第j列上aij前面有元素數(shù)：k2=i(3)aij之前共有元素數(shù)：k=k1+k2=j*m+i(4)則：LOC(aij)=LOC(a00)+(j*m+i)*lj列j行思考：若從a11開始存放，已知LOC(a11),求LOC(aij)？例：有一5×4的矩陣A,按行優(yōu)先存儲(1)已知：LOC(a00)=1000,l=sizeof(a00)=3

求：LOC(a42)=?

答：

LOC(a42)=1000+(4*4+2)*3=1054(2)已知：LOC(a00)=1000,LOC(a42)=1054

求：LOC(a33)=?

答：

1054=1000+(4*4+2)*l

∴l(xiāng)=sizeof(a00)=3∴LOC(a33)=1000+(3*4+3)*3=10456.4特殊矩陣的壓縮存儲

矩陣是n×n的方陣，包括：對稱矩陣、三角矩陣、對角矩陣等。以主對角線對稱1、對稱矩陣的壓縮存儲

即：

aij=aji采用一維數(shù)組以行為主序存儲下三角部分a00a10a20a11a21a22…0行1行2行1、對稱矩陣的壓縮存儲如下對稱矩陣壓縮存儲一維數(shù)組最大元素個數(shù)至少是多少？下三角元素個數(shù)：1+2+3+…+n=問題：

對于二維數(shù)組A來講，都是以行號i(0≤i＜n-1)，列號j(0≤j＜n-1)來訪問aij的，則：當(dāng)用一維數(shù)組B壓縮存儲A時,如何根據(jù)(i,j)去找aij對應(yīng)的元素B[k]呢？如何根據(jù)(i,j)判斷元素在二維數(shù)組中的位置？

i＝j(luò)對角線處i＜j上三角陣處i＞j下三角陣處必須給出：

k=f(i,j)(1)先計算(i,j)位置上放的是下三角陣中的第幾個元素？

0行~i-1行共存在B中的元素有：

m1=1+2+3+…i=i(i+1)/2

i行存到B中的元素有：

m2=j+1

由此：aij是存到

B中的第m個元素：

m=m1+m2=

i(i+1)/2+(j+1)

則：矩陣A中aij在數(shù)組B中的下標(biāo)：

k=m-1=

i(i+1)/2+j

推導(dǎo)：k=f(i,j)(2)而對上三角陣中的元素aij

只需存取下三角陣中aji

對應(yīng)的B[k]

故：對稱矩陣的壓縮存儲有

k=i(i+1)/2+ji≥jk=j(j+1)/2+ii＜j推導(dǎo)：k=f(i,j)2、三角矩陣的壓縮存儲三角矩陣：上三角矩陣、下三角矩陣一般情況下，常數(shù)C為0(1)下三角矩陣aij=0i<j時可能不為0i≥j時下三角部分以行優(yōu)先壓縮存儲到一維數(shù)組B中，B的最大元素個數(shù)至少為：n(n+1)/2若aij對應(yīng)B[k],則：

k=i(i+1)/2+ji≥j若

i<j時，aij=0(2)上三角矩陣aij=0i>j時可能不為0i≤j時上三角部分以行優(yōu)先壓縮存儲到一維數(shù)組B中，B的最大元素個數(shù)至少為：n(n+1)/2若aij對應(yīng)B[k],則：

k=i.n-i(i-1)/2+j-ii≤j若

i>j時，aij=0推導(dǎo)k=f(i,j)計算(i,j)位置上放的是上三角陣中的第幾個元素？

0行~i-1行共存在B中的元素有：

m1=i.n-(1+2+3+…(i-1))=i.n-i(i-1)/2

i行存到B中的元素有：

m2=(j+1)-i=j-i+1由此：aij是存到

B中的第m個元素：

m=m1+m2=

i.n-i(i-1)/2+j-i+1則：矩陣A中aij在數(shù)組B中的下標(biāo)：

k=m-1=

i.n-i(i-1)/2+j-i推導(dǎo)：k=f(i,j)6.5稀疏矩陣矩陣Am×n非0元素很少，分布無規(guī)律，稱為稀疏矩陣。若非0元素的個數(shù)為t，總元素個數(shù)為m*n

則當(dāng)

f=t/(m*n)≤5%時1、三元組順序存儲(1)存儲思想只存非零元素的行號、列號和對應(yīng)元素值，按行優(yōu)先存儲到數(shù)組中去。021

042

105

158

313

351

ijv012345

三元組存儲結(jié)構(gòu)：(2)數(shù)據(jù)類型定義假設(shè)：矩陣元素類型int

三元組最大元素數(shù)定義

#defineMAX100三元組一個結(jié)點類型typedefstruct{inti,j;intv;}TripletNode;

其中：i—行號

j—列號

v—矩陣元素值三元組順序存儲類型typedefstruct{intmu,nu,tu;TripletNodedata[MAX];}TripletList;

其中：mu—矩陣行數(shù)

nu—矩陣列數(shù)

tu—非0元素的個數(shù)約定：三元組元素按行優(yōu)先存儲(3)運算實現(xiàn)把一個稀疏矩陣轉(zhuǎn)化為三元組存儲voidMatoTri(inta[][MAX],intm,intn,TripletList*b){inti,j,k=0;/*k為三元組下標(biāo)*/for(i=0;i