严蔚敏《数据结构（c语言版）习题集》全答案(6)

void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上 {

for(i=1;i<=A.tu;i++)

A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A.tu+1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ne=A.data[pa].e+B.data[pb].e; if(ne) //和不为0 {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=ne; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

A.data[pc].i=x;

A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } else {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

A.data[pc].i=x;

A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } }//for A.tu=pc;

for(i=A.tu;i

typedef struct{

int j; int e; } DSElem;

typedef struct{

DSElem data[MAXSIZE];

int cpot[MAXROW];//这个向量存储每一行在二元组中的起始位置 int mu,nu,tu;

} DSMatrix; //二元组矩阵类型

Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元组矩阵的元素A[i][j]的值e {

for(s=cpot[i];s

e=A.data[s]; return OK; }

return ERROR;

}//DSMatrix_Locate 5.24

typedef struct{

int seq; //该元素在以行为主序排列时的序号 int e; } SElem;

typedef struct{

SElem data[MAXSIZE]; int mu,nu,tu;

} SMatrix; //单下标二元组矩阵类型

Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e {

s=i*A.nu+j+1;p=1;

while(A.data[p].seq

e=A.data[p].e; return OK; }

return ERROR; }//SMatrix_Locate 5.25

typedef enum{0,1} bool;

typedef struct{

int mu,nu;

int elem[MAXSIZE]; bool map[mu][nu];

} BMMatrix; //用位图表示的矩阵类型

void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法 {

C.mu=A.mu;C.nu=A.nu; pa=1;pb=1;pc=1;

for(i=0;i

for(j=0;j

if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0 {

C.elem[pc]=A.elem[pa]+B.elem[pb]; C.map[i][j]=1; pa++;pb++;pc++; }

else if(A.map[i][j]&&!B.map[i][j]) {

C.elem[pc]=A.elem[pa]; C.map[i][j]=1; pa++;pc++; }

else if(!A.map[i][j]&&B.map[i][j]) {

C.elem[pc]=B.elem[pb]; C.map[i][j]=1; pb++;pc++; } }

}//BMMatrix_Add 5.26

void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵 {

for(i=0;i

if(A.rhead[i])

for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表 printf(\ }

}//Print_OLMatrix 5.27

void OLMatrix_Add(OLMatrix &A,OLMatrix B)//把十字链表表示的矩阵B加到A上 {

for(j=1;j<=A.nu;j++) cp[j]=A.chead[j]; //向量cp存储每一列当前最后一个元素的指针 for(i=1;i<=A.mu;i++) {

pa=A.rhead[i];pb=B.rhead[i];pre=NULL; while(pb) {

if(pa==NULL||pa->j>pb->j) //新插入一个结点 {

p=(OLNode*)malloc(sizeof(OLNode)); if(!pre) A.rhead[i]=p; else pre->right=p; p->right=pa;pre=p;

p->i=i;p->j=pb->j;p->e=pb->e; //插入行链表中 if(!A.chead[p->j]) {

A.chead[p->j]=p; p->down=NULL; } else {

while(cp[p->j]->down) cp[p->j]=cp[p->j]->down; p->down=cp[p->j]->down; cp[p->j]->down=p; }

cp[p->j]=p; //插入列链表中 }//if

else if(pa->jj) {

pre=pa;

pa=pa->right; } //pa右移一步

else if(pa->e+pb->e) {

pa->e+=pb->e;

pre=pa;pa=pa->right; pb=pb->right; } //直接相加 else {

if(!pre) A.rhead[i]=pa->right; else pre->right=pa->right;

p=pa;pa=pa->right; //从行链表中删除 if(A.chead[p->j]==p)

A.chead[p->j]=cp[p->j]=p->down;

else cp[p->j]->down=p->down; //从列链表中删除 free (p); }//else }//while }//for

}//OLMatrix_Add

分析:本题的具体思想在课本中有详细的解释说明. 5.28

void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导 {

for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp) {

if(p->tag) Mul(p->hp,p->exp);

else p->coef*=p->exp; //把指数乘在本结点或其下属结点上 p->exp--; }

pre->tp=NULL;

if(p) free (p); //删除可能存在的常数项 }//MPList_PianDao

void Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x {

for(p=L;p;p=p->tp) {

if(!p->tag) p->coef*=x; else Mul(p->hp,x); } }//Mul 5.29

void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法 {

C=(MPLNode*)malloc(sizeof(MPLNode)); if(!A->tag&&!B->tag) //原子项,可直接相加 {

C->coef=A->coef+B->coef; if(!C->coef) {

free(C); C=NULL; } }//if

else if(A->tag&&B->tag) //两个多项式相加 {

p=A;q=B;pre=NULL; while(p&&q) {

if(p->exp==q->exp) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp;

MPList_Add(A->hp,B->hp,C->hp); pre->tp=C;pre=C; p=p->tp;q=q->tp; }

else if(p->exp>q->exp) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=A->hp; pre->tp=C;pre=C; p=p->tp; } else {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=B->hp; pre->tp=C;pre=C; q=q->tp; }

}//while while(p) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=p->hp;

pre->tp=C;pre=C; p=p->tp; }

while(q) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=q->hp;

pre->tp=C;pre=C; q=q->tp;

} //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题 }//else if

else if(A->tag&&!B->tag) //多项式和常数项相加 {

x=B->coef;

for(p=A;p->tp->tp;p=p->tp);

if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项 if(!p->tp->coef) {

free(p->tp); p->tp=NULL; } else {

q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q;

} //否则新建常数项,下同 }//else if else {

x=A->coef;

for(p=B;p->tp->tp;p=p->tp);

if(p->tp->exp==0) p->tp->coef+=x; if(!p->tp->coef) {

free(p->tp); p->tp=NULL; } else {

q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q; }

}//else

}//MPList_Add 5.30

int GList_Getdeph(GList L)//求广义表深度的递归算法 {

if(!L->tag) return 0; //原子深度为0 else if(!L) return 1; //空表深度为1 m=GList_Getdeph(L->ptr.hp)+1; n=GList_Getdeph(L->ptr.tp); return m>n?m:n; }//GList_Getdeph 5.31

void GList_Copy(GList A,GList &B)//复制广义表的递归算法 {

if(!A->tag) //当结点为原子时,直接复制 {

B->tag=0;

B->atom=A->atom; }

else //当结点为子表时 {

B->tag=1; if(A->ptr.hp) {

B->ptr.hp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.hp,B->ptr.hp); } //复制表头 if(A->ptr.tp) {

B->ptr.tp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.tp,B->ptr.tp); } //复制表尾 }//else

}//GList_Copy