第四章串、數組和廣義表可表示為：（a1,a2,……,an）線性結構第2章線性表第3章棧和隊列第4章串、數組和廣義表

2串比較，strcmp(chars1,chars2)串復制，strcpy(charto,charfrom)串連接，strcat(charto,charfrom)求串長，strlen(chars)

……調用標準庫函數#include<string.h>補充：C語言中常用的串運算3第4章串、數組和廣義表4.1串4.2數組4.3廣義表

教學內容41.掌握串的存儲方法，理解串的兩種模式匹配算法；2.明確數組和廣義表這兩種數據結構的特點，掌握數組存儲時地址計算方法，了解幾種特殊矩陣的壓縮存儲方法。

教學目標1.了解串的存儲方法，理解串的兩種模式匹配算法，重點掌握BF、KMP算法。2.明確數組和廣義表這兩種數據結構的特點，掌握數組地址計算方法，了解幾種特殊矩陣的壓縮存儲方法。3.掌握廣義表的定義、性質及其GetHead和GetTail的操作。54.1串串(String)----零個或多個字符組成的有限序列串名串值串長n空串n=06a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串7數據對象:數據關系:基本操作:(1)

StrAssign(&T,chars)//串賦值(2)StrCompare(S,T)//串比較(3)StrLength(S)//求串長(4)Concat(&T,S1,S2)//串聯ADTString{串的抽象數據類型8

(5)SubString(&Sub,S,pos,len)//求子串

(6)StrCopy(&T,S)//串拷貝

(7)StrEmpty(S)//串判空

(8)ClearString(&S)//清空串

(9)Index(S,T,pos)//子串的位置

(10)Replace(&S,T,V)//串替換

(11)StrInsert(&S,pos,T)//子串插入

(12)StrDelete(&S,pos,len)//子串刪除

(13)DestroyString(&S)//串銷毀}ADTString9順序存儲鏈式存儲串的存儲結構10typedefstruct{char*ch;//若串非空,則按串長分配存儲區,//否則ch為NULLintlength;//串長度}HString;

順序存儲表示11鏈式存儲表示12#defineCHUNKSIZE80//可由用戶定義的塊大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的頭指針和尾指針

intcurlen;//串的當前長度}LString;

鏈式存儲表示13優點：操作方便缺點：存儲密度較低可將多個字符存放在一個結點中，以克服其缺點實際分配的存儲位串值所占的存儲位存儲密度=鏈式存儲表示算法目的：BF算法（又稱古典的、經典的、樸素的、窮舉的）KMP算法（特點：速度快）算法種類：確定主串中所含子串第一次出現的位置（定位）即如何實現教材P72Index(S,T,pos)函數串的模式匹配算法15

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯BF算法設計思想16將主串的第pos個字符和模式的第一個字符比較，若相等，繼續逐個比較后續字符；若不等，從主串的下一字符起，重新與模式的第一個字符比較。直到主串的一個連續子串字符序列與模式相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0BF算法設計思想Index(S,T,pos)17intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.1）18若n為主串長度，m為子串長度，最壞情況是BF算法時間復雜度主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位各比較了m次最后m位也各比較了1次總次數為：(n-m)*m+m＝(n-m+1)*m若m<<n，則算法復雜度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=119字符串的改進模式匹配算法TS≠Tcdabcdbaecdabcdbae例子：T中重復出現abcd，但是e和x不匹配時，可直接向右滑動4個字符開始匹配，可少匹配4趟cdabcdba…x…20字符串的改進模式匹配算法TSp2p3…pj-3pj-2pj-1pjp1p0si+2si+3…si+j-3si+j-2si+j-1si+jsi+1si……≠========p2p3…pj-3pj-2p1p0p2p3…pj-3p1p0設S[i,i+j-1]=T[0,j-1]，但S[i,i+j]≠T[0,j]TT若T[0,j-2]≠T[1,j-1]，可少匹配1趟若又T[0,j-3]≠T[2,j-1]，可少匹配2趟p2…pj-4p1p0T若又T[0,j-4]≠T[3,j-1]，可少匹配3趟……類推直到前綴T[0,k+1]≠

后綴T[j-k-2,j-1]但是前綴T[0,k]=后綴T[j-k-1,j-1]時，可少匹配j-k-1趟，相當于T直接向右滑動j-k-1個字符21字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況Tcdabcdbae下標j234567108next(j)0001230-14next(j)直觀含義：[0,j-1]中前綴和后綴相等的最大長度next(j)直觀作用：可滑過j-next(j)位不用匹配22字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況TS≠Tcdabcdbaecdabcdbaecb……next(j)=-1表示匹配失敗時，S的指針加1，T的指針指向p[0]next(j)=k+1表示匹配失敗時，T的指針指向p[k+1]，next(j)=0表示匹配失敗時，T的指針指向p[0]此例中模式串T的next[0]=-1，S指針加1，T指向p[0]，即S中c與T中p[0]=a進行比較23字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況TS≠Tcdabcdbaecdabcdbaecdabcdba…x…next(j)=-1表示匹配失敗時，T的指針加1，P的指針指向p[0]next(j)=k+1表示匹配失敗時，P的指針指向p[k+1]，next(j)=0表示匹配失敗時，P的指針指向p[0]此例中模式串T的next[8]=4，S中x直接與T中p[4]=a比較24字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況TS≠Tcdabcdbaecdabcdbaecxba……next(j)=-1表示匹配失敗時，T的指針加1，P的指針指向p[0]next(j)=k+1表示匹配失敗時，P的指針指向p[k+1]，next(j)=0表示匹配失敗時，P的指針指向p[0]此例中模式串T的next[3]=0，S中x直接與T中p[0]=a比較25字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符26-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況可按定義直接計算next，下面介紹一種快速的計算next的方法假設已知next(j)=x，現在計算next(j+1)若px=pj，則next(j+1)=x+1=next(j)+1否則，設next(x)=h，(此時有p[0,h-1]=p[x-h,x-1]=p[j-h,j-1])

若ph=pj，則next(j+1)=h+1

否則，令next(h)=t,(此時有p[0,t-1]=p[h-t,h-1]=p[j-t,j-1])

繼續判斷是否pt=pj，直到找到或者到next(0)=-1……j=0;k=-1;next[0]=-1;while(j<pLength){if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}elsek=next[k];}字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況可按定義直接計算next，下面介紹一種快速的計算next的方法j=0;k=-1;next[0]=-1;while(j<pLength){if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}elsek=next[k];}Pabcabababaxnext(j)0120120-134?下標j234567108910≠=next(10)=2+1=327字符串的改進模式匹配算法對模式串T進行預處理，計算可以滑過多少個字符-1，當

j=

0k+1，當

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數next(j)=0，其他情況可按定義直接計算next，下面介紹一種快速的計算next的方法j=0;k=-1;next[0]=-1;while(j<pLength){if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}elsek=next[k];}Pabcabababexnext(j)0120120-134?下標j234567108910≠≠≠，-1next(10)=028KMP（KnuthMorrisPratt）算法/~knuth/《計算機程序設計藝術第1卷基本算法》

《計算機程序設計藝術第2卷半數值算法》《計算機程序設計藝術第3卷排序與查找》29利用已經部分匹配的結果而加快模式串的滑動速度，且主串S的指針i不必回溯！可提速到O(n+m)！S=‘ababcabcacbab’T=‘abcac’S=‘ab

abca

bcacbab’T=‘abca

c’S=‘ab

abcabcacbab’T=‘abcac’iiikk

a

b

aa

b

ckiiKMP算法例子30串操作應用舉例－－文本編輯文本可被看作一個字符串，稱為文本串頁則是文本串的子串行又是頁的子串。頁號起始行號頁表…………行號起始地址長度行表…………31本節所討論的數組與高級語言中的數組區別：高級語言中的數組是順序結構；而本章的數組既可以是順序的，也可以是鏈式結構，用戶可根據需要選擇。4.2數組32數組的抽象數據類型數據對象:數據關系:ADTArray{33

(1)InitArray(&A,n,bound1,boundn)//構造數組A(2)DestroyArray(&A)//銷毀數組A(3)Value(A,&e,index1,…,indexn)//取數組元素值

(4)Assign(A,&e,index1,…,indexn)//給數組元素賦值基本操作:}ADTArray34一維數組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la35二維數組36以行序為主序C,PASCAL數組的順序存儲以列序為主序FORTRAN38

a[n][m]設數組開始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二維數組的行序優先表示39②③三維數組按頁/行/列存放，頁優先的順序存儲

①a[m1][m2][m3]

各維元素個數為

m1,m2,m3

下標為i1,i2,i3的數組元素的存儲位置：

LOC(i1,i2,i3)=a+

i1*m2*m3+i2*m3+i3前i1頁總元素個數第i1頁的前i2行總元素個數第i2行前i3列元素個數三維數組41

各維元素個數為

m1,m2,m3,…,mn

下標為i1,i2,i3,…,in

的數組元素的存儲位置：

n維數組42n維數組43設有一個二維數組A[m][n]按行優先順序存儲，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。設數組元素A[i][j]存放在起始地址為Loc(i,j)的存儲單元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.練習44設有二維數組A[10,20]，其每個元素占兩個字節，A[0][0]存儲地址為100，若按行優先順序存儲，則元素A[6,6]的存儲地址為

，按列優先順序存儲，元素A[6,6]的存儲地址為

。練習352232(6*20+6)*2+100=352(6*10+6)*2+100=232451.什么是壓縮存儲？若多個數據元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。2.什么樣的矩陣能夠壓縮？

一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素的個數較少（一般小于5%）特殊矩陣的壓縮存儲464.3廣義表

廣義表（列表）：n(0)個表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數據元素(稱為原子)。

n為表的長度。n=0的廣義表為空表。47線性表的成分都是結構上不可分的單元素廣義表的成分可以是單元素，也可以是有結構的表