1.假设按行优先存储整数数组A[9][3][5][8]时,第一个元素的字节地址是100,每个整数占4 个字节。问下列元素的存储地址是什么? (1)a000(2)a111(3a3125(4)a8247 (1)a000存储地址是100 (2)a11的存储地址是776 (3)a3125的存储地址是1784 (4)a247的存储地址是4416。 2设有三对角矩阵Anxn,将其三条对角线上的元素存于数组B[3][n中,使得元素B[u][v]=aj, 试推导出从(i,j)到(u,v)的下标变换公式 i≤2|j-i+2ifi>2 3假设一个准对角矩阵: 1a2m-1,2m 按以下方式存储于一维数组B[4m]中: a22a33a34a43 a2m-1, 2m a2m, 2m 写出由一对下标(i,j求k的转换公式 略 4现有如下的稀疏矩阵A(如图所示),要求画出以下各种表示方法。 (1)三元组表示法。 (2)十字链表法 0-15 000 0 000 0 9100000 0 略 5画出下列广义表的存储结构示意图。 (1)A=((a,b,c),d,(a,b,c)) (2)B=(a,(b,(c,d),e),f)
⒈假设按行优先存储整数数组 A[9][3][5][8]时，第一个元素的字节地址是１００，每个整数占４ 个字节。问下列元素的存储地址是什么？ ⑴a0000 ⑵a1111 ⑶a3125 ⑷a8247 ⑴a0000 的存储地址是 100。 ⑵a1111 的存储地址是 776。 ⑶a3125 的存储地址是 1784。 ⑷a8247 的存储地址是 4416。 ⒉设有三对角矩阵 An×n，将其三条对角线上的元素存于数组 B[3][n]中，使得元素 B[u][v]=aij， 试推导出从(i,j)到(u,v)的下标变换公式。 u = i v = {j if i≤2 | j-i+2 if i>2} ⒊假设一个准对角矩阵： 按以下方式存储于一维数组 B[4m]中: 0 1 2 3 4 5 6 … k … 4m-1 4m a 11 a 12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出由一对下标(i,j)求 k 的转换公式。 略 ⒋现有如下的稀疏矩阵 A（如图所示），要求画出以下各种表示方法。 ⑴三元组表示法。 ⑵十字链表法。 略 ⒌画出下列广义表的存储结构示意图。 ⑴A=((a,b,c),d,(a,b,c)) ⑵B=(a,(b,(c,d),e),f) a11 a12 a21 a22 a33 a34 a43 a44 …. aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m ０ 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0
略 6对于二维数组A[m][n],其中mdata=1 rear
略 ⒍对于二维数组 A[m][n],其中 mdata=1; L->next =L; rear =L;
for(i=2;next-rear->next rear while(p->next=p) 1; while(is next t-p coutdatanext; coutdata<<endl 9.假设稀疏矩阵A和B(具有相同的大小m*n)都采用三元组表示,编写一个算法计算C=A+B,要求 也采用三元组表示。 参见教科书 10假设稀疏矩阵A和B(分别为m*n和n+1矩阵)采用三元组表示,编写一个算法计算c=A*B,要 求C也是采用稀疏矩阵的三元组表示 #define smax 1024 typedef struct( datatype v ISPNode
for (i=2 ;idata=i; s->next=rear->next; rear->next = s; rear = s; } p=L; while (p->next != p) { i=1; while (inext; i++; } q->next=p->next; coutdatanext; } coutdata<<endl; } ⒐假设稀疏矩阵 A 和 B（具有相同的大小 m*n）都采用三元组表示，编写一个算法计算 C=A+B，要求 C 也采用三元组表示。 参见教科书 ⒑假设稀疏矩阵 A 和 B（分别为 m*n 和 n*1 矩阵）采用三元组表示，编写一个算法计算 C=A*B，要 求 C 也是采用稀疏矩阵的三元组表示。 #define SMAX 1024 typedef struct{ int i; int j; datatype v; }SPNode;
SPNode data[SMAⅪ; /*0号单元未用* Int mu; Int nu 1, SPMat SPMatrix *Matrix add(SPMatrix *A, SPMatrix *B) SPMatrix *C A->1 C->nu= A->nu C->tu=0: pe while(patu & pbtu) if(A->datalpa] i=B->datalpb] 1&& (A->data[pa).j=B->data[pb]D) C->datalpc] i=A->datalpc] i C->datalpc] j=A->datalpc]j C->data[pc]V=A->data[pa]V+ B->data[pb]V C->tu++ pc++; pa++, pb++ else if((A->-datalpa] i B->datalpb]. i)ll (A->data[pa] i ==B-data[pb.i&& A->datalpa]jdatalpb]D) C->datapc] i=A->datalpa] 1; C->data[pc]j=A->data[].j C->datalpc]V=A->datalpa]V C->tu++, pc++ pa++, se C->datalpc] i=B->data[pb].i
typedef struct{ SPNode data[SMAX]; /*0 号单元未用*/ int mu; int nu; int tu; }SPMatrix; SPMatrix *Matrix_add (SPMatrix *A,SPMatrix *B) { SPMatrix *C; C->mu = A->mu; C->nu = A->nu; C->tu = 0; pa=1 ; pb =1 ; pc=1; while (patu && pbtu) { if ((A->data[pa].i==B->data[pb].i)&& (A->data[pa].j==B->data[pb].j)) { C->data[pc].i=A->data[pc].i; C->data[pc].j=A->data[pc].j; C->data[pc].v=A->data[pa].v + B->data[pb].v; C->tu++ ;pc++ ; pa++ ; pb++ ; } else if ((A->data[pa].i data[pb].i)|| (A->data[pa].i==B->data[pb].i&& A->data[pa].jdata[pb].j)) { C->data[pc].i = A->data[pa].i; C->data[pc].j = A->data[pa].j; C->data[pc].v = A->data[pa].v; C->tu++; pc++ ;pa++; } else { C->data[pc].i = B->data[pb].i;
C->datalpc]j=B->data[pb]. C->datalpc] v=B->datalpb]v C-→>tu++;,pc++;pb++; while( patu) C->data[pc]. i=A->datalpa] i C->datalpc]j=A->datalpa]. C->datalpc] v=A->datalpa]V pc++;pa++; while( pbtu C->datalpc] 1= B->data[pb].i C->datalpc]j=B->datalpb]. C->datalpc] v=B->datalpb] V pc++; pb++; return(c) 1假设稀疏矩阵只存放其非0元素的行号、列号和数值,以一维数组顺次存放,行号为-1结束标志。 例 如:如图所示的稀疏矩阵M: 0 0 0 0 0 0 0 0 则存在一维数组D中 [0]=1,D[1]=1,D[2]=1,D[3]=1,D[4]=5 D[5]=10,D[6]=3,D[7]=9,D[8]=5,D[9]=-1 现有两个如上方法存储的稀疏矩阵A和B,它们均为m行n列,分别存放在数组A和B中,编写求矩 阵加法C=A+B的算法,C亦放在数组c中。 void add(int a[l, int bl, int CLD) pa=0;pb=0;,pc=0 while(alpat2]&& blpb+2D)
C->data[pc].j = B->data[pb].j; C->data[pc].v = B->data[pb].v; c->tu++; pc++; pb++; } } while ( patu) { C->data[pc].i = A->data[pa].i; C->data[pc].j = A->data[pa].j; C->data[pc].v = A->data[pa].v; pc++; pa++; } while ( pbtu ) { C->data[pc].i = B->data[pb].i; C->data[pc].j = B->data[pb].j; C->data[pc].v = B->data[pb].v; pc++; pb++; } return(c); } ⒒假设稀疏矩阵只存放其非 0 元素的行号、列号和数值，以一维数组顺次存放，行号为-1 结束标志。 例 如：如图所示的稀疏矩阵 M： M = 则存在一维数组 D 中： D[0]=1， D[1]=1，D[2]=1，D[3]=1，D[4]=5 D[5]=10，D[6]=3，D[7]=9，D[8]=5，D[9]=-1 现有两个如上方法存储的稀疏矩阵 A 和 B，它们均为 m 行 n 列，分别存放在数组 A 和 B 中，编写求矩 阵加法 C=A+B 的算法，C 亦放在数组 C 中。 void add (int A[ ], int B[ ], int C[ ]) { pa=0; pb=0; pc=0; while (A[pa+2] && B[pb+2]) 1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
if(A[pa]==Blpb]&& alpat1]==blpb+lD) CIpc]=alpal; CLpc+1=Alpc+1] CLpc+2]=Alpa+2+Blpb+2 pa+=3;pb+=3;pc+=3 else if(A[<](Alpa==blob]&& Alpatl]Bpb+lD) CLpc]=Alpa]: CIpc+1=Alpc+1]; C[pc+2}=A[pc+2]; pa+=3 Clpc]=blob] C[pc+1]}=B[pb+1 C[pc+2]}=B[pb+2] pb+=3: pc while(alpa+]=0) Clpc]=Alpa] C[pc+1}=A[pa+1] C[pc+2}=A[pc+2] pat=3, pc while(blpat2]=0) Clpc]=blob]: CLpc+1=B[pb+1];
{ if (A[pa]= =B[pb] && A[pa+1]= =B[pb+1]) { C[pc]=A[pa]; C[pc+1]=A[pc+1]; C[pc+2]=A[pa+2]+B[pb+2] ; pa+=3; pb+=3; pc+=3; } else if (A[pa]<B[pb]||(A[pa]= =B[pb] && A[pa+1]<B[pb+1])) { C[pc]=A[pa]; C[pc+1]=A[pc+1]; C[pc+2]=A[pc+2]; pa+=3; pc+=3; } else { C[pc]=B[pb]; C[pc+1]=B[pb+1]; C[pc+2]=B[pb+2]; pb+=3; pc+=3; } } while (A[pa+2]!=0) { C[pc]=A[pa]; C[pc+1]=A[pa+1]; C[pc+2]=A[pc+2]; pa+=3; pc+=3; } while (B[pa+2]!=0) { C[pc]=B[pb]; C[pc+1]=B[pb+1];
C[pc+2}=B[pb+2] pb+=3;pc+=3 return 12已己知A和B为两个n*n阶的对称矩阵,输入时,对称矩阵只输入下三角形元素,按压缩存储方法 存入一维数组A和B中,编写一个计算对称矩阵A和B的乘积的算法 void mul(int a[l, int b[, int Cl l int n) for (i=0 for (=0; j<n: j++) mi=max(1,j); mj=min (i,j) x=mi*(mi-1)/2+ mj-1 C[x]=0 for(K=0; K<N; K++) ul=max(.K); vi=min(I, k) u2=max(K j):v2=min(K j); wl=ul*(ul-1)/2+v1-1 w2=u2*(u2-1)2+v2-1; C[x]+=A[w1]*B[w2]; return 13假设I为非递归并且不带共享子表的广义表,设计一个复制广义表L的算法。 略
C[pc+2]=B[pb+2]; pb+=3; pc+=3; } return; } ⒓已知 A 和 B 为两个 n*n 阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法 存入一维数组 A 和 B 中，编写一个计算对称矩阵 A 和 B 的乘积的算法。 void mul(int A[ ] , int B[ ], int C[ ], int n) { for (i=0;i<n;i++) for (j=0;j<n;j++) { mi=max(i,j); mj=min(i,j); x=mi*(mi-1)/2 + mj-1; C[x]=0; for (K=0; K<N; K++) { u1=max(i.K); vi=min(I,K); u2=max(K,j); v2=min(K,j); w1=u1*(u1-1)/2 +v1-1; w2=u2*(u2-1)/2 +v2-1; C[x] += A[w1]*B[w2]; } } return; } ⒔假设 L 为非递归并且不带共享子表的广义表，设计一个复制广义表 L 的算法。 略
