字符串與數(shù)組

第4章字符串和數(shù)組1一、字符串——存儲(chǔ)方式（1）一個(gè)由多個(gè)字符構(gòu)成以零(‘\0’)結(jié)尾的線性表就是字符串。C語言中沒有字符串?dāng)?shù)據(jù)類型。C語言中字符串被存儲(chǔ)在字符型數(shù)組中，這個(gè)數(shù)組可以靜態(tài)定義，也可動(dòng)態(tài)分配。堆存儲(chǔ)：利用一塊連續(xù)的內(nèi)存來存放字符串的存儲(chǔ)結(jié)構(gòu)＃defineMAXSIZE100charstr1[MAXSIZE+1];/*靜態(tài)定義的字符數(shù)組，可容納最大字符串長度是MAXSIZE*/char*pstr=NULL;/*字符指針，將指向存放字符串的內(nèi)存*/intlen;scanf(“%d”,&len);/*獲得字符串的長度*/pstr=(char*)malloc(len+1);/*根據(jù)字符串的長度分配一塊內(nèi)存*/2一、字符串——存儲(chǔ)方式（2）塊鏈存儲(chǔ)typedefstructstrnode{char*block;/*根據(jù)需要?jiǎng)討B(tài)分配的內(nèi)存，存放一段字符串*/intsize;/*block所指內(nèi)存的大小*/structstrnode*next;/*指向下一段字符串*/}STRNODE,*STRNODEPTR,*BLOCKLINKSTR;3一、字符串——簡(jiǎn)單模式匹配(1)【任務(wù)描述】已知一字符串S和字符串T，請(qǐng)確定字符串T在S中的位置，即字符串T的首字母在字符串S中的下標(biāo)值。這里字符串S被稱為主串，T被稱為子串，又稱為模式串。通常情況下，S串的長度比T大。【算法思想】以pos作為S串的下標(biāo)。設(shè)T串的長度是lent。pos從0開始從左向右掃描字符串S，檢查以S[pos]為起點(diǎn)的長度為lent的子串是否與T串完全相同。如果完全相同，則意味著匹配成功，返回pos值；如果不同，說明匹配失敗，需要將pos向后移動(dòng)一個(gè)單元，繼續(xù)檢查以S[pos]為起點(diǎn)的長度為lent的子串是否與T串完全相同。這樣循環(huán)反復(fù)，直到匹配成功或者以S[pos]為起點(diǎn)的子串長度不夠?yàn)橹埂?一、字符串——簡(jiǎn)單模式匹配(2)intStrIndex(char*s,char*t)/*返回t在s中的位置，找不到t，則返回-1*/{inti,j;intpos=0;/*匹配的起點(diǎn)*/while(1){ i=pos;j=0; while(s[i]&&t[j]&&s[i]==t[j])/*匹配循環(huán)*/{i++;j++;} if(t[j]==0)returnpos;/*匹配成功*/ elseif(s[i]==0)return-1;/*匹配到了主串的末尾還沒有成功*/ elsepos++;/*匹配的起點(diǎn)向后移動(dòng)一個(gè)單元，重新匹配*/ }//while(1)}時(shí)間復(fù)雜度：5一、字符串——*模式匹配的KMP算法(1)簡(jiǎn)單匹配算法的最大問題是：每次匹配失敗時(shí)，S串要回到S[pos+1]處，而T串要回到T[0]處，從頭開始比較。下面的例子蘊(yùn)含著改進(jìn)的空間已知主串是："aabcdabcdabceab"模式串是："abcdabce“KMP算法的基本思想：只要發(fā)現(xiàn)S[i]≠T[j]時(shí)，i保持不動(dòng)，j跳到k處(滑動(dòng)T串)，直到k是-1時(shí)，i才向右移動(dòng)1位。k被稱為j的next值，即k=next(j)。j跳到k處的條件是：k是T串在j處的自身最大重復(fù)子串的長度。K值的真正含義：是子串T[0..j-1]自身重復(fù)子串T[0..k-1]的長度特點(diǎn)：有重復(fù)子串6一、字符串——*模式匹配的KMP算法(2)關(guān)鍵是next(j)如何求解next(j)表達(dá)的是T串自身的特征，與S串無關(guān)next函數(shù)的數(shù)學(xué)定義next(j)函數(shù)值的求解算法已知k=next(j)，說明T[0..j-1]之間最大重復(fù)子串的長度是k。下面的循環(huán)可以求出next(j+1)的值：①比較T[j]和T[k]，如果T[j]=T[k]，那么T[0..j]之間最大重復(fù)子串的長度就是k+1，也就是說next(j+1)=k+1，求值完畢；②如果T[j]≠T[k]，我們只能在T[0..k-1]內(nèi)尋找最大重復(fù)子串。T[0..k-1]最大重復(fù)子串長度是next(k)，這時(shí)設(shè)定k=next(k)，也就是說，k回退到自己的next值處。我們?cè)俅伪容^T[j]和T[k]，即轉(zhuǎn)到步驟①。因?yàn)閚ext值只和T串內(nèi)容有關(guān)，一旦T串確定，就可以計(jì)算出所有next值，并用一個(gè)數(shù)組保存，以供字符串匹配時(shí)使用。7一、字符串——*模式匹配的KMP算法(2)關(guān)鍵是next(j)如何求解next(j)表達(dá)的是T串自身的特征，與S串無關(guān)next函數(shù)的數(shù)學(xué)定義

next(j)函數(shù)值的求解算法已知k=next(j)，說明T[0..j-1]之間最大重復(fù)子串的長度是k。下面的循環(huán)可以求出next(j+1)的值：①比較T[j]和T[k]，如果T[j]=T[k]，那么T[0..j]之間最大重復(fù)子串的長度就是k+1，也就是說next(j+1)=k+1，求值完畢；②如果T[j]≠T[k]，我們只能在T[0..k-1]內(nèi)尋找最大重復(fù)子串。T[0..k-1]最大重復(fù)子串長度是next(k)，這時(shí)設(shè)定k=next(k)，也就是說，k回退到自己的next值處。我們?cè)俅伪容^T[j]和T[k]，即轉(zhuǎn)到步驟①。8一、字符串——*模式匹配的KMP算法(3)voidNextVal(char*T,int*next)/*求模式串T各單元的next值*/{intj,k,len;next[0]=-1;j=0;len=strlen(T);while(j<len-1){/*已知next[j]，推算next[j+1]*/k=next[j];while(k>=0&&T[j]!=T[k])k=next[k];/*k回退到自己的next值處，重復(fù)子串的長度變小*/next[j+1]=k+1;/*無論是k==-1,還是T[j]==T[k],next[j+1]的值都是k+1*/j++;/*準(zhǔn)備推算下一個(gè)next值*/ }}9一、字符串——*模式匹配的KMP算法(4)#defineMAXSIZE50intnext[MAXSIZE];intStrIndexKMP(char*S,char*T)/*返回T在S中的位置，查找失敗，返回-1*/{inti=0,j=0;NextVal(T,next);/*計(jì)算T串的next值*/while(S[i]!=0&&T[j]!=0)/*如果沒到字符串末尾，就循環(huán)繼續(xù)匹配*/{if(S[i]==T[j])/*i和j都向后移動(dòng)一個(gè)單元*/{i++;j++;}else{j=next[j];/*匹配失敗，j滑動(dòng)到自己的next值處*/if(j==-1)/*說明滑動(dòng)之前j已經(jīng)是0，需要將i向后移動(dòng)，同時(shí)置j為0*/ {i++;j=0;} }//else}/*屬于while語句*/if(T[j]==0)returni-j;/*匹配成功，返回位置*/elsereturn-1;/*查找失敗*/}10解疑01234567next-1000012301234567891011二、數(shù)組與矩陣——數(shù)組的定義#defineN10#defineM20#defineP10elemtypea[N];/*定義了一個(gè)N個(gè)單元的一維數(shù)組*/假設(shè)a[0]的地址是Loc，elemtype數(shù)據(jù)類型的大小是S(字節(jié))，那么數(shù)組單元a[i]的地址就是:Loc+i×S。elemtypeb[M][N];/*定義了一個(gè)M×N個(gè)單元的二維數(shù)組*/假設(shè)b[0][0]的地址是Loc，那么數(shù)組單元b[i][j]的前面一共有i行（i×N個(gè)）單元，外加j個(gè)單元，它的地址就是：Loc+(i×N+j)×S12二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(1)1．特殊矩陣之三角矩陣的壓縮存儲(chǔ)三角矩陣A[i][j]和數(shù)組B[k]的關(guān)系：上三角矩陣：k=(N+(N-1)+…+(N-(i-1))+(j-i)=i×(2×N-i+1)/2+j-I(j≥i)下三角矩陣：k=(1+2+3+…+i)+j=i×(i+1)/2+j(i≥j)13二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(2)2．特殊矩陣之對(duì)稱矩陣的壓縮存儲(chǔ)，按照三角矩陣的方式

N階矩陣，存在A[i][j]=A[j][i]3．特殊矩陣之帶狀矩陣的壓縮存儲(chǔ)N階矩陣，只有主對(duì)角線和它的上下兩條對(duì)角線上有數(shù)據(jù)，其他位置都是0或者某個(gè)固定常量。k=(i×3-1)+(j-(i-1))=2×i+j14二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(3)4．特殊矩陣之稀疏矩陣的壓縮存儲(chǔ)在一個(gè)M×N的矩陣中，非零元素的個(gè)數(shù)是T，我們將稱為稀疏因子。通常認(rèn)為，當(dāng)稀疏因子小于等于0.05時(shí)，這個(gè)矩陣就稱為稀疏矩陣。⑴稀疏矩陣的順序存儲(chǔ)#defineMAXSIZE500typedefstruct{inti,j;/*在矩陣中的位置下標(biāo)*/elemtypev;/*非零元素*/}TRIPLE;/*三元組*/typedefstruct{TRIPLEdata[MAXSIZE];/*三元組數(shù)組*/intrnum,cnum,sum;/*行數(shù)、列數(shù)、非零元素的個(gè)數(shù)*/}TRIPLEMATRIX;15二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(4)下面的算法創(chuàng)建一個(gè)順序存儲(chǔ)結(jié)構(gòu)的稀疏矩陣：voidInputData(TRIPLEMATRIX*m){intcount;TRIPLEt;/*開始輸入稀疏矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/scanf("%d,%d,%d",&m->rnum,&m->cnum,&m->sum);count=0;while(1){scanf("%d,%d,%d",&t.i,&t.j,&t.v);/*獲取三元組數(shù)據(jù)，要求按行序輸入*/if(t.i>=0&&t.i<m->rnum&&t.j>=0&&t.j<m->cnum)/*三元組數(shù)據(jù)合法*/{m->data[count]=t;count++;/*計(jì)數(shù)器增1*/if(count==m->sum)break;/*所有數(shù)據(jù)都輸入完畢*/

}elsebreak;/*遇到非法輸入*/}}16二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(5)4．特殊矩陣之稀疏矩陣的壓縮存儲(chǔ)⑵稀疏矩陣的十字鏈表存儲(chǔ)將所有同一行的非零元素按列序鏈接，所有同一列的非零元素按行序鏈接。這樣，同一個(gè)三元組單元同時(shí)存在于行鏈和列鏈兩個(gè)鏈表中。typedefstructcrsnode_tag{inti,j;elemtypev;/*三元組數(shù)據(jù)*/structcrsnode_tag*right,*down;/*行鏈指針和列鏈指針，right指向同一行下一列非零元素，down指向同一列下一行非零元素*/}CROSSNODE,*CROSSNODEPTR;/*定義十字鏈表結(jié)點(diǎn)及其指針*/typedefstruct{CROSSNODEPTRrhead,chead;/*指向行鏈數(shù)組和列鏈數(shù)組*/intrnum,cnum,sum;/*行數(shù)、列數(shù)、非零元素的個(gè)數(shù)*/}CROSSLINKLIST;17二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(6)1．初始化十字鏈表intInitCrossLinklist(CROSSLINKLIST*m,introw,intcol,intsum){/*初始化一個(gè)十字鏈表，成功則返回1，否則返回0*/inti;/*根據(jù)行數(shù)和列數(shù)分配相應(yīng)數(shù)量的行鏈和列鏈的表頭結(jié)點(diǎn)*/m->rhead=(CROSSNODEPTR)malloc(row*sizeof(CROSSNODE));m->chead=(CROSSNODEPTR)malloc(col*sizeof(CROSSNODE));if(m->rhead==NULL||m->chead==NULL)return0;/*分配失敗*/for(i=0;i<row;i++) m->rhead[i].right=NULL;/*將所有行鏈設(shè)為空鏈*/for(i=0;i<col;i++) m->chead[i].down=NULL;/*將所有列鏈設(shè)為空鏈*/m->rnum=row;m->cnum=col;m->sum=sum;/*設(shè)置行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/return1;}18二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(7)2.建立一個(gè)十字鏈表的稀疏矩陣voidInputData(CROSSLINKLIST*m)/*建立一個(gè)存儲(chǔ)數(shù)據(jù)的十字鏈表*/{intlen,count;CROSSNODEPTRp,q;inti,j;elemtypev;introw,col,sum;scanf("%d,%d,%d",&row,&col,&sum);/*獲取行數(shù)、列數(shù)和非零元素個(gè)數(shù)*/if(!InitCrossLinklist(m,row,col,sum))/*初始化十字鏈表*/{printf("noenoughmemory\n");exit(0); }count=0;/*計(jì)數(shù)器清零*/while(1){scanf("%d,%d,%d",&i,&j,&v);/*輸入三元組數(shù)據(jù)*/if(i>=0&&i<m->rnum&&j>=0&&j<m->cnum)/*三元組數(shù)據(jù)合法*/ {p=(CROSSNODEPTR)malloc(sizeof(CROSSNODE)); if(!p)/*分配失敗*/ {printf("noenoughmemory\n");return;} p->i=i;p->j=j;p->v=v;/*設(shè)置三元組結(jié)點(diǎn)p的數(shù)據(jù)域*/19二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(8)/*開始按列序插入行鏈，讀者應(yīng)該很熟悉操作細(xì)節(jié)了*/q=&m->rhead[i];while(q->right!=NULL&&q->right->j<j)

//遍歷到行鏈表尾結(jié)點(diǎn)q=q->right;

p->right=q->right;q->right=p;

//在行鏈尾插入結(jié)點(diǎn)p/*開始按行序插入列鏈*/q=&m->chead[j];while(q->down!=NULL&&q->down->i<i)

//遍歷到列鏈表尾結(jié)點(diǎn)q=q->down;p->down=q->down;q->down=p;count++;if(count==m->sum)break;/*數(shù)據(jù)輸入完畢*/

}else/*三元組數(shù)據(jù)非法*/{printf("illegalinputdata\n");break;}}//while}20二、數(shù)組與矩陣——矩陣的壓縮存儲(chǔ)(9)3．銷毀十字鏈表voidDestroyCrossLinklist(CROSSLINKLIST*m)/*銷毀一個(gè)十字鏈表*/{CROSSNODEPTRp;inti;for(i=0;i<m->rnum;i++){/*沿著行鏈，釋放鏈上所有的三元組結(jié)點(diǎn)*/while(m->rhead[i].right!=NULL) { p=m->rhead[i].right; m->rhead[i].right=p->right; free(p); }

}free(m->rhead);free(m->chead);/*釋放行鏈和列鏈表頭結(jié)點(diǎn)數(shù)組*/m->rhead=m->chead=NULL;m->rnum=0;m->cnum=0;m->sum=0;/*其他成員設(shè)置成安全值*/}21二、數(shù)組與矩陣——稀疏矩陣的轉(zhuǎn)置(1)轉(zhuǎn)置的含義：A[i][j]和A[j][i]交換位置，則M*N矩陣轉(zhuǎn)置后變成N*M矩陣三元組數(shù)組的轉(zhuǎn)置算法遍歷三元組數(shù)組，記下這個(gè)稀疏矩陣中每列的非零元素個(gè)數(shù)，存儲(chǔ)數(shù)組count推算出轉(zhuǎn)置后矩陣的各三元組數(shù)據(jù)的正確的存儲(chǔ)位置，存儲(chǔ)位置存放在數(shù)組rpos中再次遍歷三元組數(shù)組，對(duì)每個(gè)數(shù)據(jù)單元進(jìn)行轉(zhuǎn)置，按照rpos中的數(shù)據(jù)存放到新的三元組數(shù)組中(0,1,12)(0,2,5)(1,0,3)(1,2,9)(2,1,6)(2,3,20)(0,1,3)(1,0,12)(1,2,6)(2,0,5)(2,1,9)(3,2,20)i0123count[i]1221rpos[i]0135(1,0,12)(2,0,5)(0,1,3)(2,1,9)(1,2,6)(3,2,20)012345轉(zhuǎn)置前轉(zhuǎn)置后轉(zhuǎn)置后（無序）22練習(xí)：書101頁，練一練4.323二、數(shù)組與矩陣——稀疏矩陣的轉(zhuǎn)置(2)TRIPLEMATRIXTransposeMatrix(TRIPLEMATRIXm){/*返回矩陣m的轉(zhuǎn)置矩陣*/int*count,*rpos;TRIPLEMATRIXT;intk,i,r;count=(int*)malloc(sizeof(int)*um);/*count[i]將存放矩陣m第i列非零元素的個(gè)數(shù)*/rpos=(int*)malloc(sizeof(int)*um);/*rpos[i]將存放轉(zhuǎn)置后的矩陣行非零元素的存儲(chǔ)起點(diǎn)*/if(count==NULL||rpos==NULL){printf("noenoughmemory\n");return;}for(i=0;i<um;i++)count[i]=0;/*計(jì)數(shù)器清零*/for(i=0;i<m.sum;i++)/*遍歷三元組數(shù)組，記錄各列非零元素的個(gè)數(shù)*/{ k=m.data[i].j; count[k]++; }rpos[0]=0;/*第0行的存儲(chǔ)起點(diǎn)是0*/for(i=1;i<um;i++)/*計(jì)算各行非零元素的存儲(chǔ)起點(diǎn)*/rpos[i]=rpos[i-1]+count[i-1];24二、數(shù)組與矩陣——稀疏矩陣的轉(zhuǎn)置(3)T.sum=m.sum;T.rnum=um;T.cnum=m.rnum;/*行、列轉(zhuǎn)置，非零元素總量不變*/for(i=0;i<m.sum;i++){k=m.data[i].j;r=rpos[k];/*r是轉(zhuǎn)置后三元組數(shù)據(jù)的正確的存儲(chǔ)位置*/T.data[r].i=m.data[i].j;T.data[r].j=m.data[i].i;T.data[r].v=m.data[i].v;/*三元組轉(zhuǎn)置*/rpos[k]++;/*存儲(chǔ)起點(diǎn)增1，是下一個(gè)同一行三元組數(shù)據(jù)的存儲(chǔ)位置*/}free(count);free(rpos);returnT;}25二、數(shù)組與矩陣——稀疏矩陣的乘法(1)矩陣相乘的含義已知一個(gè)M×N的矩陣A和N×P的矩陣B，令C=A×B，則C是一個(gè)M×P的矩陣，并且：

二維數(shù)組的矩陣乘法voidMatrixMulti(intA[M][N],intB[N][P],intC[M][P]){inti,j,k;for(i=0;i<M;i++) for(j=0;j<P;j++) {C[i][j]=0;/*矩陣C的數(shù)據(jù)單元清零*/ for(k=0;k<N;k++) C[i][j]+=A[i][k]*B[k][j];/*見矩陣乘法公式*/ }}26二、數(shù)組與矩陣——稀疏矩陣的乘法(2)例子：書105頁，練一練4.427二、數(shù)組與矩陣——稀疏矩陣的乘法(2)稀疏矩陣十字鏈表的矩陣乘法voidMatrixMulti(CROSSLINKLIST*A,CROSSLINKLIST*B,CROSSLINKLIST*C){/*矩陣C將是矩陣A乘以矩陣B的結(jié)果*/inti,j,k;elemtypev;CROSSNODEPTRp,q,pC,qC;InitCrossLinklist(C,A->rnum,B->cnum,0);/*初始化矩陣C的十字鏈表*/for(i=0;i<A->rnum;i++)/*遍歷矩陣A的所有的行鏈*/{p=A->rhead[i].right;while(p!=NULL)/*找到非零元素結(jié)點(diǎn)p，某個(gè)(i,j,v)*/{ k=p->j;/*k是A[i][j]的列號(hào)j,也就是矩陣B的行號(hào)*/ q=B->rhead[k].right; while(q!=NULL)/*遍歷矩陣B的第k行行鏈，找到所有非零元素結(jié)點(diǎn)q*/ {j=q->j; v=p->v*q->v;/*計(jì)算A[i][k]×B[k][j]*/28二、數(shù)組與矩陣——稀疏矩陣的乘法(3) /*試圖將(i,j,v)插入到矩陣C中*/ pC=&C->rhead[i]; while(pC->right!=NULL&&pC->right->j<j)/*尋找插入的位置*/ pC=pC->right; if(pC->right!=NULL&&pC->right->j==j) pC->right->v+=v;/*原行鏈中有(i,j,v’)結(jié)點(diǎn)，執(zhí)行累加*/ else/*否則新生成結(jié)點(diǎn)(i,j,v)結(jié)點(diǎn)qC，插入到pC的后面*/ {qC=(CROSSNODEPTR)malloc(sizeof(CROSSNODE)); if(qC==NULL){printf("noenoughmemory\n");return;} qC->i=i;qC->j=j;qC->v=v; qC->right