【正文】 “aaaaaaa”【答】：1012345（3）“babbabab”【答】：10011232 已知正文t =“ababbaabaa”，模式p =“aab”，試使用KMP 快速模式匹配算法尋找p在t 中首次出現(xiàn)的起始位置，給出具體的匹配過程分析?！敬稹浚耗Ｊ絧 的next 向量如下表所示：0 1 2a a b1 0 1第一趟匹配：0 1 2 3 4 5 6 7 8 9a b a b b a a b a aa ai=1，j=1，匹配失敗，此時j 取next[1]=0，即下一趟匹配從i=1，j=0 開始；第二趟匹配：0 1 2 3 4 5 6 7 8 9a b a b b a a b a aai=1，j=0，匹配失敗，此時j=next[0]=1，下一趟匹配從i=2，j=0 開始；第三趟匹配：0 1 2 3 4 5 6 7 8 9a b a b b a a b a aa ai=3，j=1，匹配失敗，此時j=next[1]=0，下一趟匹配從i=3，j=0 開始；第四趟匹配：0 1 2 3 4 5 6 7 8 9a b a b b a a b a aai=3，j=0，匹配失敗，此時j=next[0]=1，下一趟匹配從i=4，j=0 開始；第五趟匹配：0 1 2 3 4 5 6 7 8 9a b a b b a a b a aai=4，j=0，匹配失敗，此時j=next[0]=1，下一趟匹配從i=5，j=0 開始；第五趟匹配：0 1 2 3 4 5 6 7 8 933a b a b b a a b a aa a bi=8，j=3，匹配完成，表明匹配成功的位置是：ij=5。 已知三維數(shù)組A[3][2][4]，數(shù)組首地址為100，每個元素占用1 個存儲單元，分別計算數(shù)組元素A[0][1][2]在按行優(yōu)先和按列優(yōu)先存儲方式下的地址?！敬稹浚篈[0][1][2]按行優(yōu)先方式在內(nèi)存的存儲地址為：100+0*8+1*4+2=106A[0][1][2]按列優(yōu)先方式在內(nèi)存的儲儲地址為：100+2*6+1*3+0*8=115 已知兩個稀疏矩陣A 和B，其行數(shù)和列數(shù)均對應(yīng)相等，編寫一個函數(shù)，計算A 和B之和，假設(shè)稀疏矩陣采用三元組表示。【參考程序1】：includetypedef struct {int data[100][100]。int m,n。 /*分別存放稀疏矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/} matrix。typedef int spmatrix[100][3]。 //三元組存儲結(jié)構(gòu)spmatrix c。void add(spmatrix a,spmatrix b,spmatrix c) //基于三元組結(jié)構(gòu)的矩陣相加算法{int i,j,k,t,r。i=j=k=1。while(i=a[0][2]amp。amp。j=b[0][2]){if(a[i][0]b[j][0]||(a[i][0]==b[j][0]amp。amp。a[i][1]b[j][1])){ c[k][0]=a[i][0]。c[k][1]=a[i][1]。c[k][2]=a[i][2]。i++。k++。}elseif(a[i][0]b[j][0]||(a[i][0]==b[j][0]amp。amp。a[i][1]b[j][1])){ c[k][0]=b[j][0]。c[k][1]=b[j][1]。c[k][2]=b[j][2]。j++。k++。}elseif(a[i][0]==b[j][0]amp。amp。(a[i][1]==b[j][1]) ){ c[k][0]=a[i][0]。34c[k][1]=a[i][1]。c[k][2]=a[i][2]+b[j][2]。i++。j++。if (c[k][2]!=0 ) k++。 /*如果相加的和不為0,則生成一個有效項(xiàng)*/}}while(j=b[0][2]){ c[k][0]=b[j][0]。c[k][1]=b[j][1]。c[k][2]=b[j][2]。j++。k++。}while(i=a[0][2]){c[k][0]=a[i][0]。c[k][1]=a[i][1]。c[k][2]=a[i][2]。i++。k++。}c[0][0]=a[0][0]。c[0][1]=a[0][1]。c[0][2]=k1。}//函數(shù)pressmatrix 將普通矩陣存儲轉(zhuǎn)換為三元組存儲結(jié)構(gòu)void pressmatrix(matrix *A , spmatrix B){ int i, j, k。k=1。for ( i=0。 iAm。 i++)for (j=0。jAn。 j++)if (Adata[i][j] !=0){ B[k][0]=i。B[k][1]=j。B[k][2]=Adata[i][j]。k++。}B[0][0]=Am。B[0][1]=An。B[0][2]=k1。35i=0。printf(the spmatrix is:\n)。while(i=B[0][2]){ printf(%d%5d%5d\n,B[i][0],B[i][1],B[i][2])。i++。}}void creat(int r,int w,matrix *s){ int i,j,data。printf(input numbers:\n)。for(i=0。ir。i++)for(j=0。jw。j++){scanf(%d,amp。data)。sdata[i][j]=data。}printf(the array is:\n)。for(i=0。ir。i++){ for(j=0。jw。j++)printf(%5d,sdata[i][j])。printf(\n)。}sm=r。sn=w。}int main(){matrix p,q。spmatrix a,b,c。int r,w,i。i=0。printf(input r,w:)。 /*輸入行和列*/scanf(%d%d,amp。r,amp。w)。creat(r,w,amp。p)。creat(r,w,amp。q)。pressmatrix(amp。p,a)。pressmatrix(amp。q,b)。i=0。add(a,b,c)。printf(the spmatrix c is:\n)。36while(i=c[0][2]){ printf(%d%5d%5d\n,c[i][0],c[i][1],c[i][2])。i++。}}程序運(yùn)行時先輸入矩陣的行和列，然后按普通矩陣格式輸入矩陣值，一組程序測試用例運(yùn)行結(jié)果如下圖：【參考程序2】：37include include define MAX 100typedef struct{int data[MAX][3]。int m,n,value。}matrix。matrix *Input(matrix *A){ int i,j。A = (matrix*)malloc(sizeof(matrix))。scanf(%d%d%d,amp。Am,amp。An,amp。Avalue)。Adata[0][0] = Am。Adata[0][1] = An。Adata[0][2] = Avalue。for(i = 1。i = Avalue。i ++){for(j = 0。j 3。 j ++)scanf(%d,amp。Adata[i][j])。}return A。}void Output(matrix *A){ int i,j。printf(************************************\n)。for(i = 0。i = Avalue。i ++){for(j = 0。j 3。j ++)printf(%d ,Adata[i][j])。printf(\n)。}printf(************************************\n)。}matrix *addmatrix(matrix *A,matrix *B,matrix *C){ int i = 1,j =1,k = 1。C = (matrix*)malloc(sizeof(matrix))。while(i = Avalue amp。amp。 j = Bvalue){if(Adata[i][0] == Bdata[j][0]){38if(Adata[i][1] == Bdata[j][1]){Cdata[k][0] = Adata[i][0]。Cdata[k][1] = Adata[i][1]。Cdata[k][2] = Adata[i][2] + Bdata[j][2]。if(Cdata[k][2] != 0) k ++。i ++。j ++。}else if(Adata[i][1] Bdata[j][1]){Cdata[k][0] = Adata[i][0]。Cdata[k][1] = Adata[i][1]。Cdata[k][2] = Adata[i][2]。k ++。i ++。}else{Cdata[k][0] = Bdata[j][0]。Cdata[k][1] = Bdata[j][1]。Cdata[k][2] = Bdata[j][2]。k ++。j ++。}}else if(Adata[i][0] Bdata[j][0]){Cdata[k][0] = Adata[i][0]。Cdata[k][1] = Adata[i][1]。Cdata[k][2] = Adata[i][2]。k ++。i ++。}else{Cdata[k][0] = Bdata[j][0]。Cdata[k][1] = Bdata[j][1]。Cdata[k][2] = Bdata[j][2]。39k ++。j ++。}}while(i = Avalue){Cdata[k][0] = Adata[i][0]。Cdata[k][1] = Adata[i][1]。Cdata[k][2] = Adata[i][2]。k ++。i ++。}while(j = Bvalue){Cdata[k][0] = Bdata[j][0]。Cdata[k][1] = Bdata[j][1]。Cdata[k][2] = Bdata[j][2]。k ++。j ++。}Cdata[0][0] = (Adata[0][0]=Bdata[0][0])?Adata[0][0]:Bdata[0][0]。Cdata[0][1] = (Adata[0][1]=Bdata[0][1])?Adata[0][1]:Bdata[0][1]。Cdata[0][2] = k1。Cvalue = k1。return C。}int main(){matrix * A = NULL,*B = NULL,*C = NULL。printf(提示：請按三元組格式輸入矩陣內(nèi)容。\n)。printf(Input A matrix:\n)。A = Input(A)。printf(Input B matrix:\n)。B = Input(B)。C = addmatrix(A,B,C)。Output(C)。free(A)。free(B)。40free(C)。return 0。}程序運(yùn)行時按照三元組的格式輸入矩陣信息，程序運(yùn)行結(jié)果如下圖所示： 寫出兩個稀疏矩陣相乘的算法，計算：Cpn = Apm?Bmn其中，A、B 和C 都采用三元組表示法存儲?！敬稹浚篿nclude include define MAX 100typedef struct{int data[MAX][3]。int m,n,value。}matrix。matrix *Input(matrix *A){ int i,j。A = (matrix*)malloc(sizeof(matrix))。scanf(%d%d%d,amp。Am,amp。An,amp。Avalue)。Adata[0][0] = Am。41Adata[0][1] = An。Adata[0][2] = Avalue。for(i = 1。i = Avalue。i ++){for(j = 0。j 3。 j ++)scanf(%d,amp。Adata[i][j])。}return A。}void Output(matrix *A){int i,j。printf(*******************************\n)。for(i = 0。i = Avalue。i ++){for(j = 0。j 3。j