字符串與數(shù)組課件

1、第4章 字符串和數(shù)組第4章 字符串和數(shù)組一、字符串存儲方式（1）一個由多個字符構成以零(0)結尾的線性表就是字符串。C語言中沒有字符串數(shù)據(jù)類型。C語言中字符串被存儲在字符型數(shù)組中，這個數(shù)組可以靜態(tài)定義，也可動態(tài)分配。2堆存儲：利用一塊連續(xù)的內存來存放字符串的存儲結構define MAXSIZE 100char str1MAXSIZE+1; /*靜態(tài)定義的字符數(shù)組，可容納最大字符串長度是MAXSIZE*/char *pstr=NULL; /*字符指針，將指向存放字符串的內存*/int len;scanf(“%d”,&len); /*獲得字符串的長度*/pstr=(char *)malloc(le

2、n+1); /*根據(jù)字符串的長度分配一塊內存*/一、字符串存儲方式（1）一個由多個字符構成以零(0一、字符串存儲方式（2）塊鏈存儲typedef struct strnode char *block; /*根據(jù)需要動態(tài)分配的內存，存放一段字符串*/ int size; /*block所指內存的大小*/ struct strnode *next; /*指向下一段字符串*/ STRNODE,*STRNODEPTR,*BLOCKLINKSTR;3一、字符串存儲方式（2）塊鏈存儲3一、字符串簡單模式匹配(1)【任務描述】已知一字符串S和字符串T，請確定字符串T在S中的位置，即字符串T的首字母在字符串S

3、中的下標值。這里字符串S被稱為主串，T被稱為子串，又稱為模式串。通常情況下，S串的長度比T大?！舅惴ㄋ枷搿恳詐os作為S串的下標。設T串的長度是lent。pos從0開始從左向右掃描字符串S，檢查以Spos為起點的長度為lent的子串是否與T串完全相同。如果完全相同，則意味著匹配成功，返回pos值；如果不同，說明匹配失敗，需要將pos向后移動一個單元，繼續(xù)檢查以Spos為起點的長度為lent的子串是否與T串完全相同。這樣循環(huán)反復，直到匹配成功或者以Spos為起點的子串長度不夠為止。4一、字符串簡單模式匹配(1)【任務描述】已知一字符串S和一、字符串簡單模式匹配(2)int StrIndex(ch

4、ar *s,char *t) /*返回t在s中的位置，找不到t，則返回-1*/ int i,j; int pos=0; /*匹配的起點*/ while(1) i=pos;j=0; while(si&tj&si=tj)/*匹配循環(huán)*/ i+; j+; if(tj=0)return pos; /*匹配成功*/ else if(si=0) return -1; /*匹配到了主串的末尾還沒有成功*/ else pos+;/*匹配的起點向后移動一個單元，重新匹配*/ /while(1) 時間復雜度：5一、字符串簡單模式匹配(2)int StrIndex(一、字符串*模式匹配的KMP算法(1)簡單匹配算法

5、的最大問題是：每次匹配失敗時，S串要回到Spos+1處，而T串要回到T0處，從頭開始比較。下面的例子蘊含著改進的空間已知主串是：aabcdabcdabceab模式串是：abcdabce“KMP算法的基本思想：只要發(fā)現(xiàn)SiTj時，i保持不動，j跳到k處(滑動T串)，直到k是-1時，i才向右移動1位。k被稱為j的next值，即k=next(j)。j跳到k處的條件是：k是T串在j處的自身最大重復子串的長度。6K值的真正含義：是子串T0.j-1自身重復子串T0.k-1的長度特點：有重復子串一、字符串*模式匹配的KMP算法(1)簡單匹配算法的最大一、字符串*模式匹配的KMP算法(2)關鍵是next(j)

6、如何求解next(j)表達的是T串自身的特征，與S串無關next函數(shù)的數(shù)學定義next(j)函數(shù)值的求解算法已知k=next(j)，說明T0.j-1之間最大重復子串的長度是k。下面的循環(huán)可以求出next(j+1)的值：比較Tj和Tk，如果Tj=Tk，那么T0.j之間最大重復子串的長度就是k+1，也就是說next(j+1)=k+1，求值完畢；如果Tj Tk，我們只能在T0.k-1內尋找最大重復子串。T0.k-1最大重復子串長度是next(k)，這時設定k=next(k)，也就是說，k回退到自己的next值處。我們再次比較Tj和Tk，即轉到步驟。7因為next值只和T串內容有關，一旦T串確定，就可

7、以計算出所有next值，并用一個數(shù)組保存，以供字符串匹配時使用。一、字符串*模式匹配的KMP算法(2)關鍵是next(j一、字符串*模式匹配的KMP算法(2) 關鍵是next(j)如何求解next(j)表達的是T串自身的特征，與S串無關next函數(shù)的數(shù)學定義 next(j)函數(shù)值的求解算法已知k=next(j)，說明T0.j-1之間最大重復子串的長度是k。下面的循環(huán)可以求出next(j+1)的值：比較Tj和Tk，如果Tj=Tk，那么T0.j之間最大重復子串的長度就是k+1，也就是說next(j+1)=k+1，求值完畢；如果Tj Tk，我們只能在T0.k-1內尋找最大重復子串。T0.k-1最大重

8、復子串長度是next(k)，這時設定k=next(k)，也就是說，k回退到自己的next值處。我們再次比較Tj和Tk，即轉到步驟。8一、字符串*模式匹配的KMP算法(2) 關鍵是next一、字符串*模式匹配的KMP算法(3)void NextVal(char *T,int *next)/*求模式串T各單元的next值*/ int j,k,len; next0=-1; j=0; len=strlen(T); while(j=0&Tj!=Tk) k=nextk; /*k回退到自己的next值處，重復子串的長度變小*/ nextj+1=k+1; /*無論是k=-1,還是Tj=Tk,nextj+1的值

9、都是k+1*/ j+; /*準備推算下一個next值*/ 9一、字符串*模式匹配的KMP算法(3)void Nex一、字符串*模式匹配的KMP算法(4)#define MAXSIZE 50int nextMAXSIZE; int StrIndexKMP(char *S, char *T)/*返回T在S中的位置，查找失敗，返回-1*/ int i=0, j=0; NextVal(T,next); /*計算T串的next值*/ while(Si!=0&Tj!=0) /*如果沒到字符串末尾，就循環(huán)繼續(xù)匹配*/ if(Si=Tj) /*i和j都向后移動一個單元*/ i+; j+; else j=nex

10、tj; /*匹配失敗，j滑動到自己的next值處*/ if(j=-1) /*說明滑動之前j已經(jīng)是0，需要將i向后移動，同時置j為0*/ i+; j=0; /else /*屬于while語句*/ if(Tj=0)return i-j; /*匹配成功，返回位置*/ else return -1; /*查找失敗*/10一、字符串*模式匹配的KMP算法(4)#define M解疑1101234567next-10000123012345678910解疑1101234567next-1000012301234二、數(shù)組與矩陣數(shù)組的定義#define N 10#define M 20#define P 10

11、elemtype aN;/*定義了一個N個單元的一維數(shù)組*/假設a0的地址是Loc，elemtype數(shù)據(jù)類型的大小是S(字節(jié))，那么數(shù)組單元ai的地址就是: Loc+iS。elemtype bMN;/*定義了一個MN個單元的二維數(shù)組*/假設b00的地址是Loc，那么數(shù)組單元bij的前面一共有i行（iN個）單元，外加j個單元，它的地址就是：Loc+(iN+j)S12二、數(shù)組與矩陣數(shù)組的定義#define N 1012二、數(shù)組與矩陣矩陣的壓縮存儲(1)1特殊矩陣之三角矩陣的壓縮存儲13三角矩陣Aij和數(shù)組Bk的關系：上三角矩陣：k=(N+(N-1)+(N-(i-1)+(j-i)=i(2N-i+1)

12、/2+j-I (ji)下三角矩陣：k=(1+2+3+i)+j=i(i+1)/2+j (ij)二、數(shù)組與矩陣矩陣的壓縮存儲(1)1特殊矩陣之三角矩陣二、數(shù)組與矩陣矩陣的壓縮存儲(2)2特殊矩陣之對稱矩陣的壓縮存儲，按照三角矩陣的方式 N階矩陣，存在Aij=Aji3特殊矩陣之帶狀矩陣的壓縮存儲N階矩陣，只有主對角線和它的上下兩條對角線上有數(shù)據(jù)，其他位置都是0或者某個固定常量。 k=(i3-1)+(j-(i-1)=2i+j14二、數(shù)組與矩陣矩陣的壓縮存儲(2)2特殊矩陣之對稱矩陣二、數(shù)組與矩陣矩陣的壓縮存儲(3)4特殊矩陣之稀疏矩陣的壓縮存儲在一個MN的矩陣中，非零元素的個數(shù)是T，我們將 稱為稀疏因

13、子。通常認為，當稀疏因子小于等于0.05時，這個矩陣就稱為稀疏矩陣。稀疏矩陣的順序存儲#define MAXSIZE 500typedef struct int i,j; /*在矩陣中的位置下標*/ elemtype v; /*非零元素*/ TRIPLE;/*三元組*/typedef struct TRIPLE dataMAXSIZE; /*三元組數(shù)組*/ int rnum,cnum,sum; /*行數(shù)、列數(shù)、非零元素的個數(shù)*/ TRIPLEMATRIX;15二、數(shù)組與矩陣矩陣的壓縮存儲(3)4特殊矩陣之稀疏矩陣二、數(shù)組與矩陣矩陣的壓縮存儲(4)下面的算法創(chuàng)建一個順序存儲結構的稀疏矩陣：voi

14、d InputData(TRIPLEMATRIX *m) int count; TRIPLE t; /*開始輸入稀疏矩陣的行數(shù)、列數(shù)和非零元素的個數(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.irnum&t.j=0&t.jcnum) /*三元組數(shù)據(jù)合法*/ m-datacount=t; count+; /*計數(shù)器增1*/ if(count=m-sum) break; /*所有數(shù)據(jù)都輸入完畢*/

15、else break; /*遇到非法輸入*/ 16二、數(shù)組與矩陣矩陣的壓縮存儲(4)下面的算法創(chuàng)建一個順序二、數(shù)組與矩陣矩陣的壓縮存儲(5)4特殊矩陣之稀疏矩陣的壓縮存儲稀疏矩陣的十字鏈表存儲將所有同一行的非零元素按列序鏈接，所有同一列的非零元素按行序鏈接。這樣，同一個三元組單元同時存在于行鏈和列鏈兩個鏈表中。typedef struct crsnode_tag int i,j; elemtype v; /*三元組數(shù)據(jù)*/ struct crsnode_tag * right, * down; /*行鏈指針和列鏈指針，right指向同一行下一列非零元素，down指向同一列下一行非零元素*/ C

16、ROSSNODE,* CROSSNODEPTR; /*定義十字鏈表結點及其指針*/typedef struct CROSSNODEPTR rhead,chead; /*指向行鏈數(shù)組和列鏈數(shù)組*/ int rnum,cnum,sum; /*行數(shù)、列數(shù)、非零元素的個數(shù)*/ CROSSLINKLIST;17二、數(shù)組與矩陣矩陣的壓縮存儲(5)4特殊矩陣之稀疏矩陣二、數(shù)組與矩陣矩陣的壓縮存儲(6)1初始化十字鏈表int InitCrossLinklist(CROSSLINKLIST *m,int row,int col,int sum)/*初始化一個十字鏈表，成功則返回1，否則返回0*/ int i;

17、/*根據(jù)行數(shù)和列數(shù)分配相應數(shù)量的行鏈和列鏈的表頭結點*/ m-rhead=(CROSSNODEPTR)malloc(row*sizeof(CROSSNODE); m-chead=(CROSSNODEPTR)malloc(col*sizeof(CROSSNODE); if(m-rhead=NULL|m-chead=NULL) return 0; /*分配失敗*/ for(i=0;irheadi.right=NULL; /*將所有行鏈設為空鏈*/ for(i=0;icheadi.down=NULL; /*將所有列鏈設為空鏈*/ m-rnum=row; m-cnum=col; m-sum=sum;

18、/*設置行數(shù)、列數(shù)和非零元素的個數(shù)*/ return 1; 18二、數(shù)組與矩陣矩陣的壓縮存儲(6)1初始化十字鏈表18二、數(shù)組與矩陣矩陣的壓縮存儲(7)2.建立一個十字鏈表的稀疏矩陣void InputData(CROSSLINKLIST *m) /*建立一個存儲數(shù)據(jù)的十字鏈表*/ int len,count; CROSSNODEPTR p,q; int i,j; elemtype v; int row,col,sum; scanf(%d,%d,%d,&row,&col,&sum); /*獲取行數(shù)、列數(shù)和非零元素個數(shù)*/ if(!InitCrossLinklist(m,row,col,sum)

19、/*初始化十字鏈表*/ printf(no enough memoryn); exit(0); count=0;/*計數(shù)器清零*/ while(1) scanf(%d,%d,%d,&i,&j,&v);/*輸入三元組數(shù)據(jù)*/ if(i=0&irnum&j=0&jcnum) /*三元組數(shù)據(jù)合法*/ p=(CROSSNODEPTR)malloc(sizeof(CROSSNODE); if(!p) /*分配失敗*/ printf(no enough memoryn); return; p-i=i; p-j=j; p-v=v; /*設置三元組結點p的數(shù)據(jù)域*/19二、數(shù)組與矩陣矩陣的壓縮存儲(7)2.建

20、立一個十字鏈表的二、數(shù)組與矩陣矩陣的壓縮存儲(8) /*開始按列序插入行鏈，讀者應該很熟悉操作細節(jié)了*/ q=&m-rheadi; while(q-right!=NULL&q-right-jright; p-right=q-right; q-right=p; /在行鏈尾插入結點p /*開始按行序插入列鏈*/ q=&m-cheadj; while(q-down!=NULL&q-down-idown; p-down=q-down; q-down=p; count+; if(count=m-sum)break;/*數(shù)據(jù)輸入完畢*/ else/*三元組數(shù)據(jù)非法*/ printf(illegal inp

21、ut datan); break; /while20二、數(shù)組與矩陣矩陣的壓縮存儲(8) /*開始按列二、數(shù)組與矩陣矩陣的壓縮存儲(9)3銷毀十字鏈表void DestroyCrossLinklist(CROSSLINKLIST *m) /*銷毀一個十字鏈表*/ CROSSNODEPTR p; int i; for(i=0;irnum;i+) /*沿著行鏈，釋放鏈上所有的三元組結點*/ while(m-rheadi.right!=NULL) p=m-rheadi.right; m-rheadi.right=p-right; free(p); free(m-rhead); free(m-chead

22、); /*釋放行鏈和列鏈表頭結點數(shù)組*/ m-rhead=m-chead=NULL; m-rnum=0; m-cnum=0; m-sum=0; /*其他成員設置成安全值*/ 21二、數(shù)組與矩陣矩陣的壓縮存儲(9)3銷毀十字鏈表21二、數(shù)組與矩陣稀疏矩陣的轉置(1)轉置的含義：Aij和Aji交換位置，則M*N矩陣轉置后變成N*M 矩陣三元組數(shù)組的轉置算法遍歷三元組數(shù)組，記下這個稀疏矩陣中每列的非零元素個數(shù)，存儲數(shù)組count推算出轉置后矩陣的各三元組數(shù)據(jù)的正確的存儲位置 ，存儲位置存放在數(shù)組rpos中再次遍歷三元組數(shù)組，對每個數(shù)據(jù)單元進行轉置，按照rpos中的數(shù)據(jù)存放到新的三元組數(shù)組中01234

23、5轉置前轉置后轉置后（無序）二、數(shù)組與矩陣稀疏矩陣的轉置(1)轉置的含義：Ai練習： 書101頁，練一練4.323練習：23二、數(shù)組與矩陣稀疏矩陣的轉置(2)TRIPLEMATRIX TransposeMatrix(TRIPLEMATRIX m)/*返回矩陣m的轉置矩陣*/ int *count,*rpos; TRIPLEMATRIX T; int k,i,r; count=(int *)malloc(sizeof(int)*um);/*counti將存放矩陣m第i列非零元素的個數(shù)*/ rpos=(int *)malloc(sizeof(int)*um);/*rposi將存放轉置后的矩陣行非零

24、元素的存儲起點*/ if(count=NULL|rpos=NULL) printf(no enough memoryn); return; for(i=0;um;i+) counti=0;/*計數(shù)器清零*/ for(i=0;im.sum;i+) /*遍歷三元組數(shù)組，記錄各列非零元素的個數(shù)*/ k=m.datai.j; countk+; rpos0=0;/*第0行的存儲起點是0*/ for(i=1;um;i+)/*計算各行非零元素的存儲起點*/ rposi=rposi-1+counti-1;24二、數(shù)組與矩陣稀疏矩陣的轉置(2)TRIPLEMATRI二、數(shù)組與矩陣稀疏矩陣的轉置(3) T.sum

25、=m.sum; T.rnum=um; T.cnum=m.rnum; /*行、列轉置，非零元素總量不變*/ for(i=0;im.sum;i+) k=m.datai.j; r=rposk;/*r是轉置后三元組數(shù)據(jù)的正確的存儲位置*/ T.datar.i=m.datai.j; T.datar.j=m.datai.i; T.datar.v=m.datai.v;/*三元組轉置*/ rposk+;/*存儲起點增1，是下一個同一行三元組數(shù)據(jù)的存儲位置*/ free(count); free(rpos); return T; 25二、數(shù)組與矩陣稀疏矩陣的轉置(3) T.sum=m.s二、數(shù)組與矩陣稀疏矩陣的

26、乘法(1)矩陣相乘的含義已知一個MN的矩陣A和NP的矩陣B，令C=AB，則C是一個MP的矩陣，并且： 二維數(shù)組的矩陣乘法void MatrixMulti(int AMN,int BNP,int CMP) int i,j,k; for(i=0;iM;i+)for(j=0;jP;j+) Cij=0;/*矩陣C的數(shù)據(jù)單元清零*/ for(k=0;krnum,B-cnum,0); /*初始化矩陣C的十字鏈表*/ for(i=0;irnum;i+) /*遍歷矩陣A的所有的行鏈*/ p=A-rheadi.right; while(p!=NULL) /*找到非零元素結點p，某個(i,j,v)*/ k=p-j

27、; /*k是Aij的列號j,也就是矩陣B的行號*/q=B-rheadk.right;while(q!=NULL) /*遍歷矩陣B的第k行行鏈，找到所有非零元素結點q*/ j=q-j; v=p-v*q-v; /*計算AikBkj*/二、數(shù)組與矩陣稀疏矩陣的乘法(2)稀疏矩陣十字鏈表的矩陣二、數(shù)組與矩陣稀疏矩陣的乘法(3) /*試圖將(i,j,v)插入到矩陣C中*/ pC=&C-rheadi; while(pC-right!=NULL&pC-right-jright; if(pC-right!=NULL&pC-right-j=j) pC-right-v+=v; /*原行鏈中有(i,j,v)結點，執(zhí)

28、行累加*/ else/*否則新生成結點(i,j,v)結點qC，插入到pC的后面*/ qC=(CROSSNODEPTR)malloc(sizeof(CROSSNODE); if(qC=NULL) printf(no enough memoryn); return; qC-i=i; qC-j=j; qC-v=v; qC-right=pC-right; pC-right=qC; /*再將結點qC插入到列鏈中*/ pC=&C-cheadj; while(pC-down!=NULL&pC-down-idown; qC-down=pC-down; pC-down=qC; C-sum+; /*矩陣非零元素個

29、數(shù)增1*/ /*屬于else語句 */29二、數(shù)組與矩陣稀疏矩陣的乘法(3) /*試圖將(i,二、數(shù)組與矩陣稀疏矩陣的乘法(4) /*尋找矩陣B第k行的下一個非零元素*/ q=q-right; /while(q) /*尋找矩陣A第i行的下一個非零元素*/ p=p-right; /while(p) /for /*下面清除十字鏈表中的零元素結點*/ for(i=0;irnum;i+) /*檢查所有的行鏈*/ p=&C-rheadi; while(p-right!=NULL) /*遍歷行鏈，摘除所有的零元素結點*/ if(p-right-v=0)/*發(fā)現(xiàn)零元素結點，從行鏈中摘除*/ p-right=p-right-right;else p=p-right; /*否則p向后移動*/ 30二、數(shù)組與矩陣稀疏矩陣的乘法(4) /*尋找矩陣二、數(shù)組與矩陣稀疏矩陣的乘法(5)for(i=0;icnum;i+) /*檢查所有的列鏈*/ p=&C-cheadi; while(p-down!=NULL) /*遍歷列鏈，摘除零元素結點*/if(p-down-v=0) /*發(fā)現(xiàn)零元素結點，這時它已經(jīng)從行鏈中被摘除了*/ q=p-down; p-down=q-down; fr