if(flag)
printf("Foundasaddleelement!
\nA[%d][%d]=%d",i,j,A[i][j]);
}
}//for
}//Get_Saddle
5.20
intexps[MAXSIZE];//exps数组用于存储某一项的各变元的指数
intmaxm,n;//maxm指示变元总数,n指示一个变元的最高指数
voidPrint_Poly_Descend(int*a,intm)//按降幂顺序输出m元多项式的项,各项的系数已经按照题目要求存储于m维数组中,数组的头指针为a
{
maxm=m;
for(i=m*n;i>=0;i--)//按降幂次序,可能出现的最高项次数为mn
Get_All(a,m,i,0);//确定并输出所有次数为i的项
}//Print_Poly_Descend
voidGet_All(int*a,intm,inti,intseq)//递归求出所有和为i的m个自然数
{
if(seq==maxm)Print_Nomial(a,exps);//已经求完时,输出该项
else
{
min=i-(m-1)*n;//当前数不能小于min
if(min<0)min=0;
max=n
n:
i;//当前数不能大于max
for(j=min;j<=max;j++)
{
exps[seq]=j;//依次取符合条件的数
Get_All(a,m-1,i-j,seq+1);//取下一个数
}
}//else
exps[seq]=0;//返回
}//Get_All
voidPrint_Nomial(int*a,intexps[])//输出一个项,项的各变元的指数已经存储在数组exps中
{
pos=0;
for(i=0;i {
pos*=n;
pos+=exps[i];
}
coef=*(a+pos);//取得该系数coef
if(!
coef)return;//该项为0时无需输出
elseif(coef>0)printf("+");//系数为正时打印加号
elseif(coef<0)printf("-");//系数为负时打印减号
if(abs(coef)!
=1)printf("%d",abs(coef));//当系数的绝对值不为1时打印系数
for(i=0;i if(exps[i])//打印各变元及其系数
{
printf("x");
printf("%d",i);
printf("E");
if(exps[i]>1)printf("%d",exp[i]);//系数为1时无需打印
}
}//Print_Nomial
分析:
本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.
5.21
voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C)//三元组表示的稀疏矩阵加法
{
C.mu=A.mu;C.nu=A.nu;C.tu=0;
pa=1;pb=1;pc=1;
for(x=1;x<=A.mu;x++)//对矩阵的每一行进行加法
{
while(A.data[pa].i while(B.data[pb].i while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
{
if(A.data[pa].j==B.data[pb].j)
{
ce=A.data[pa].e+B.data[pb].e;
if(ce)//和不为0
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++;pb++;pc++;
}
}//if
elseif(A.data[pa].j>B.data[pb].j)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
else
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
}//while
while(A.data[pa]==x)//插入A中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
while(B.data[pb]==x)//插入B中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
}//for
C.tu=pc;
}//TSMatrix_Add
5.22
voidTSMatrix_Addto(TSMatrix&A,TSMatrixB)//将三元组矩阵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(B.data[pb].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
elseif(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}//TSMatrix_Addto
5.23
typedefstruct{
intj;
inte;
}DSElem;
typedefstruct{
DSElemdata[MAXSIZE];
intcpot[MAXROW];//这个向量存储每一行在二元组中的起始位置
intmu,nu,tu;
}DSMatrix;//二元组矩阵类型
StatusDSMatrix_Locate(DSMatrixA,inti,intj,int&e)//求二元组矩阵的元素A[i][j]的值e
{
for(s=A.cpot[i];s=j;s++);//注意查找范围
if(s {
e=A.data[s];
returnOK;
}
returnERROR;
}//DSMatrix_Locate
5.24
typedefstruct{
intseq;//该元素在以行为主序排列时的序号
inte;
}SElem;
typedefstruct{
SElemdata[MAXSIZE];
intmu,nu,tu;
}SMatrix;//单下标二元组矩阵类型
StatusSMatrix_Locate(SMatrixA,inti,intj,int&e)//求单下标二元组矩阵的元素A[i][j]的值e
{
s=i*A.nu+j+1;p=1;
while(A.data[p].seq
if(A.data[p].seq==s)//找到了元素A[i][j]
{
e=A.data[p].e;
returnOK;
}
returnERROR;
}//SMatrix_Locate
5.25
typedefenum{0,1}bool;
typedefstruct{
intmu,nu;
intelem[MAXSIZE];
boolmap[mu][nu];
}BMMatrix;//用位图表示的矩阵类型
voidBMMatrix_Add(BMMatrixA,BMMatrixB,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++;
}
elseif(A.map[i][j]&&!
B.map[i][j])
{
C.elem[pc]=A.elem[pa];
C.map[i][j]=1;
pa++;pc++;
}
elseif(!
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
voidPrint_OLMatrix(OLMatrixA)//以三元组格式输出十字链表表示的矩阵
{
for(i=0;i {
if(A.rhead[i])
for(p=A.rhead[i];p;p=p->right)//逐次遍历每一个行链表
printf("%d%d%d\n",i,p->j,p->e;
}
}//Print_OLMatrix
5.27
voidOLMatrix_Add(OLMatrix&A,OLMatrixB)//把十字链表表示的矩阵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;
elsepre->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
elseif(pa->jj)
{
pre=pa;
pa=pa->right;
}//pa右移一步
elseif(pa->e+pb->e)
{
pa->e+=pb->e;
pre=pa;pa=pa->right;
pb=pb->right;
}//直接相加
else
{
if(!
pre)A.rhead[i]=pa->right;
elsepre->right=pa->right;
p=pa;pa=pa->right;//从行链表中删除
if(A.chead[p->j]==p)
A.chead[p->j]=cp[p->j]=p->down;
elsecp[p->j]->down=p->down;//从列链表中删除
free(p);
}//else
}//while
}//for
}//OLMatrix_Add
分析:
本题的具体思想在课本中有详细的解释说明.
5.28
voidMPList_PianDao(MPList&L)//对广义表存储结构的多元多项式求第一变元的偏导
{
for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp)
{
if(p->tag)Mul(p->hp,p->exp);
elsep->coef*=p->exp;//把指数乘在本结点或其下属结点上
p->exp--;
}
pre->tp=NULL;
if(p)free(p);//删除可能存在的常数项
}//MPList_PianDao
voidMul(MPList&L,intx)//递归算法,对多元多项式L乘以x
{
for(p=L;p;p=p->tp)
{
if(!
p->tag)p->coef*=x;
elseMul(p->hp,x);
}
}//Mul
5.29
voidMPList_Add(MPListA,MPListB,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
elseif(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;
}
elseif(p->exp>q->exp)
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=p->exp;
C->hp=A->hp;
pre->tp=C;pre=C;