loadings->data=i;
s->next=rear->next; rear->next = s; rear = s;
} p=L;
while (p->next != p) {
i=1;
while (i p=p->next; i++; } q->next=p->next; cout< delete p; p=q->next; } cout<<”the last monky is : ” < ⒐假设稀疏矩阵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; 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 (pa<=A->tu && pb<=B->tu) { 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 < B->data[pb].i)|| (A->data[pa].i==B->data[pb].i&& A->data[pa].j< B->data[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->data[pc].j = B->data[pb].j; C->data[pc].v = B->data[pb].v; c->tu++; pc++; pb++; } } while ( pa<=A->tu) { 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 ( pb<=B->tu ) { 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[5]=10，D[6]=3，D[7]=9，D[8]=5， 1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 D[4]=5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 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]) { 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] A[pa+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; } ⒓已知A和B为两个n*n阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法存入一维数组A和B中，编写一个计算对称矩阵A和B的乘积的算法。 void mul(int A[ ] , int B[ ], int C[ ], int n) { for (i=0;i mi=max(i,j); mj=min(i,j); x=mi*(mi-1)/2 + mj-1; C[x]=0; for (K=0; 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的算法。 略 第六单元 本章解答只给出算法描述，1~10题略。 算法中二叉树的二叉存储结构描述如下： typedef struct BTNode{ datatype data; struct BTNode *lchild,*rchild; }BTNode ,*BiTree; ⒈对于下图所示二叉树，试给出： ⑴它的顺序存储结构示意图； ⑵它的二叉链表存储结构示意图； ⑶它的三叉链表存储结构示意。 ⒉证明：在结点数多于1的哈夫曼树中不存在度为1的结 A C B D F E G ( 1题图) H