i=1
n
其中αi∏（dk-ck+1）（1<=i<=n）
k=i+1
若从c开始，c数组下标从0开始，各维长度为bi（1<=i<=n）则：
LOC（aj1j2…jn）=LOC(a00…0)+(b2* b3*…* bn*j1+ b3* …* bn*+ j2…+ bn* jn-1+ jn)*l
n
=LOC(a00…0)+ ∑αiji 其中：αi=l，αi-1=bi*αi ，1 5.3 (1) k=2*i+j ( 0<=k<3n-2 ) (2) i=(k+1)3 ( 0<=k<3n-2 ) j=k-2*i 5.4 void saddlepoint(int a[m][n]); a是m行n列的二维数组,本算法求所有马鞍点 b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数 c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数 {for(i=0;i {min=a[i,0]; 最小值初始化 b[0]=0; k=1; b数组记最小值的列号，k记最小值的个数 for(j=1;j if (a[i][j] else if (a[i][j]==min) {b[k+1]=j; k++;} 有相等的最小值 for (jj=0;jj if(kk>=m)printf(“马鞍点 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]); } END OF for jj } END OF for i 最坏时间复杂度为O(m*(n+n*m)). (最坏时所有元素相同，都是马鞍点) 解法2: 若矩阵中元素值互不相同,则用一维数组row记下各行最小值，再用一维数组col记下各列最大值， 相等者为马鞍点。 for (i=0;i {row[i]=a[i][0]; 最小值初始化 for (j=1;j if (a[i][j] } for (j=0;j {col[j]=a[0,j]; 最大值初始化 for (i=1;i if (a[i][j]>col[j]) col[j]=a[i][j]; 重新确定最大值 } for (i=0;i 11 if(row[i]==col[j]) printf(“马鞍点 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]); 时间复杂度O( (m*n)). 解法3: 设定两个数组： max[0..n-1] 记各列的最大值所在行号 min[0..m-1] 记各行的最小值所在列号 第j 列的最大值为A[max[j]][j],第i行的最小值是A[i][min[i]] void saddlepoint(int a[m][n]); a是m行n列的二维数组,本算法求所有马鞍点 { int max[]=0,min[]=0;for(i=0;i for (j=0; j { if (A[i][j]>A[max[j]][j]) max[j]=i; 重新确定第j列最大值的行号 if (A[i][j] } for (i=0;i {j=min[i]; a[i][j]是否是马鞍点 if( max[j]==i) printf(“马鞍点 A[%d][%d]=%d”,i,j,a[i][j]); } END OF for jj } 时间复杂度为O(m*n+m). 5.5 （1）三元组表（行号 0—5，列号 0—5） S=（（0，0，15），（0，3，22），（0，5，-15），（1，1，11），（1，2，3），（2，3，-6），（4，0，91），（5，2，28）） （2） 5.6算法分析：两矩阵A和B相加的结果是一矩阵C，其元素Cij有三种情况；（1）Cij=Aij（Bij =0）；（2）Cij=Bij（Aij =0）；（3）Cij=Aij+Bij 。在（3）种情况下，要看结果是否为0， 12 C矩阵只有非零元素。 Void matrixaddition(crosslist *A,*B) 稀疏矩阵A和B用十字链表存储结构，本算法将稀疏矩阵B加到矩阵A上 {ca=A->next;cb=B->next; while(ca!=A&&cb!=B) 设pa和pb为矩阵A和B想加时的工作指针 {pa=ca->right;pb=cb->right;} if(pa==ca)ca=ca->next;A表在该行无非0元素； else if(pb==cb)cb=cb->nextB表在该行无非0元素； else if(pb->col pre->down=pt->down;该结点从B表相应列摘下 i=pb->right;pt=chb[i];pre=pt;取B表行表头指针 while(pt->right->row pre->right=pt->riht;该结点从B表相应行链表中摘下。 Pbt=pb;pb=pb->right;B表移至下一结点 以下是将pbt插入A表的相应列链表中 j=pbt->col;pt=cha[j];pre=pt; while(pt->down !=cha[j]&&pt->down->row pre->down=pbt;pbt->down=pt; 以下是将pbt插入A表相应行链表中 i=pbt->right;pt=cha[i];pre=pt; while(pt->right !=cha[i]&&pt->right-col }end of “if (pb->col else if(pa->col=pb->col)处理两表中行列相同的非0元素 {v=pa->data+pb->data; if(v !=0) {pa->data+=pb->data;pa=pa->right; 将pb从行链表中删除；pb=pb->right; } else{将pa,pb从链表中删除;然后 pa=pa->right; pb=pb->right; } 5.7 (1) ，则 n=n0+n1+n2+……+nm+ (1) 13 设树的分支数为B，有 n=B+1 n=1n1+2n2+……+mnm+1 (2) 由（1）和（2）有： n0=n2+2n3+……+(m-1)nm+1 6.4 i-1 (1) k (i为层数) (2) (n-2)k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D # E F # G # # # # H 注：#为空结点 A B ^ C ^ D ^ E ^ F ^ ^ G ^ ^ H ^ 6.6 (1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8 int (0); else { bl=(bl>br? bl+1: br+1); 左右子树高度的大者加1（根） } } 算法结束 6.9 void preorder(cbt[],int n,int i); cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 14 { int i=1,s[],top=0; s是栈，栈中元素是二叉树结点在cbt中的序号 top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0) { while(i<=n) {visit(cbt[i]); 访问根结点 if (2*i+1<=n) s[++top]=2*i+1; 若右子树非空，其编号进栈 i=2*i; 先序访问左子树 } if (top>0) i=s[top--]; 退栈，先序访问右子树 } END OF while (i<=n ||top>0) } 算法结束 以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示 void preorder(bt[],int n,int i); bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]); preorder(bt,n,2*i); preorder(bt,n,2*i+1); } 算法结束 6.10 int equal(bitree T1,bitree T2); T1和T2是两棵二叉树，本算法判断T1和T2是否等价 T1和T2都是空二叉树则等价 T1和T2只有一棵为空，另一棵非空，则不等价 T1和T2均非空，且根结点值相等，则比较其左、右子树 {if (T1==null && T2==null) return(1); 同为空二叉树 else if (T1==null || T2==null) return(0); 只有一棵为空 else if (T1->data!=T2->data) return(0); 根结点值不等 else return(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild)) 判左右子树等价 } 算法结束 6．11 void levelorder (bitree +1]; s是指针数组，数组中元素为二叉树节点的指针 top=0; while (t!=null || top!=0) { while (t!=null) { visit(*t); s[++top]=t; t=t->lchild } if (top!=0) { t=s[top--]; t=t->rchild;} } } 算法结束 void inorder (bitree *t); (中序非递归遍历) {bitree *s[n+1]; 15