第五章数组和广义表 5.18 void rSh(int A[n]intk/把数组A的元素循环右移k位,只用一个辅助存储空间 for(Fl; KA6]A6]→>A[12]A[2>AB3A[3]→>A[9]A[9]>A[O] 第二条链A[>A[7]A[7]>A3]A[1>A[4]A[4]->A[0]A[0]>A[1 第三条链A[2]>A[8]A[8]>A[41A[4->A[5A[5]→>A[->A[2] 恰好使所有元素都右移一次 虽然未经数学证明,但作者相信上述规律应该是正确的 5.19 void get saddle( int Amn]y求矩阵A中的马鞍点 for(F0; i<m; i++) for(min=A[LOJ 0: j< j++) fAj[<min)min=A[U∥求一行中的最小值 for(=0; j<n j++) iA[iu[=min)/判断这个(些)最小值是否鞍点 for(flag=1, k=0; k<m; k++)
第五章 数组和广义表 5.18 void RSh(int A[n],int k)//把数组 A 的元素循环右移 k 位,只用一个辅助存储空间 { for(i=1;iA[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次. 虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19 void Get_Saddle(int A[m][n])//求矩阵 A 中的马鞍点 { for(i=0;i<m;i++) { for(min=A[i][0],j=0;j<n;j++) if(A[i][j]<min) min=A[i][j]; //求一行中的最小值 for(j=0;j<n;j++) if(A[i][j]==min) //判断这个(些)最小值是否鞍点 { for(flag=1,k=0;k<m;k++)
if(min=0,-)按降幂次序可能出现的最高项次数为mn Get Al(am,i,O),∥确定并输出所有次数为i的项 i//Print Poly Descend void Get All(int* a, Int m, Int 1, Int seq递归求出所有和为i的m个自然数 if(seq=maxm) Print nomial(a,exps,∥已经求完时,输出该项 min=i(m-1)*n,∥当前数不能小于min if(mino)min=0 max=ni?ni,∥当前数不能大于max for(=min; j<=max: j++) exps[seq÷,∥依次取符合条件的数 Get All(am-1, 1-1, seq+1),/取下一个数 i/else exps[seq}=0;∥返回 i//Get All void print nomial(int* a,int exps[]输出一个项项的各变元的指数已经存储在数 组exps中 for(i=0 K<maxm++)∥求出该项的系数在m维数组a中低下标优先的存储位置 pos pos-n
if(min=0;i--) //按降幂次序,可能出现的最高项次数为 mn Get_All(a,m,i,0); //确定并输出所有次数为 i 的项 }//Print_Poly_Descend void Get_All(int *a,int m,int i,int seq)//递归求出所有和为 i 的 m 个自然数 { if(seq==maxm) Print_Nomial(a,exps); //已经求完时,输出该项 else { min=i-(m-1)*n; //当前数不能小于 min if(min<0) min=0; max=n<i?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 void Print_Nomial(int *a,int exps[ ])//输出一个项,项的各变元的指数已经存储在数 组 exps 中 { pos=0; for(i=0;i<maxm;i++) //求出该项的系数在 m 维数组 a 中低下标优先的存储位置 pos { pos*=n;
post=exps] coef=*ta+pos),/取得该系数coef if( I coef)return;∥该项为0时无需输出 else if((coef>0) printi("+"),∥系数为正时打印加号 else if(coef1) printf("%d"exp[i]),∥系数为1时无需打印 i//Print Nomial 分析本算法的关键在于如何按照降幂顺序输出各项这里采用了一个递归函数来 找到所有满足和为i的m个自然数作为各变元的指数只要先取第一个数为j然后 再找到所有满足和为的m-1个自然数就行了要注意j的取值范围必须使剩余 m-l个自然数能够找到,所以不能小于i(m-1)*maxn,也不能大于i只要找到了 组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置 并且在系数不为0时输出对应的项 5.21 void SMAtrix_Ad( TSMatriⅸA, ISMatrⅸB, TSMatrⅸ&CM三元组表示的稀疏矩 阵加法 C. muFA. mu: C nu=A. nu: CtuO for(x=1x<=Amux++)∥对矩阵的每一行进行加法 while(A catalpa). i<x)pa++ whileB data[pb).i<x) pb++ whie( A data[pa]=x&& B datap]=x川∥行列值都相等的元素 if(A catalpa]. j==B data[pb]j) e=A data[pa] e+B data[pb]e, if(ce)∥和不为0 C. datalpc]F=x C. datalpc] jFA datal j
pos+=exps[i]; } coef=*(a+pos); //取得该系数 coef if(!coef) return; //该项为 0 时无需输出 else if(coef>0) printf("+"); //系数为正时打印加号 else if(coef1) 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 void TSMatrix_Add(TSMatrix A,TSMatrix B,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<x) pa++; while(B.data[pb].i<x) pb++; 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. datalpc]e=ce, else if(A data[pa PB data[pb].j C. datalpc]F-x; C data[pc]-=B data[pb].j; C data[pc]e=B. datalpb]e C. datalpc]Fx C. datalpc] jA. data[pa] j C. datalpc] e=A data[pa]e M/while whie( A data[pa}x)/插入A中剩余的元素(第x行) C. datalpc) ix C. datalpc]- j=A data[pa].j; C data[pc]e=A catalpa]e whie( B data[pb]=x)/插入B中剩余的元素(第x行) C data[pc].i- C. datalpc]- j =B data[pb] j; C data[pc]e=B. datalpb]e, pb++ pc++, C tu=pc; i//SMAtrix Add void TSMatrix Addto( TSMatrⅸx&A, TSMatrⅸxBy将三元组矩阵B加到A上 for(Fl; <=A tu i++) A.dataMAXSIZE-Atu+i= A data[把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A tu+l; pb=l; pc=l
C.data[pc].e=ce; pa++;pb++;pc++; } }//if else if(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 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=1x<=Amux++)∥对矩阵的每一行进行加法 while(A data[pa]. i<x)pa++; nile(B. datapb]i<x)pb++, while( A datal pa]i=x&& B datap]i=xy行列值都相等的元素 if(A catalpa]. j==B. datalpb]j) ne=A. datalpa]- e+B. datalpb if(ne)∥和不为0 A. datalpc] FX A.datalpc]=A.datalpa] j A. datalpc.e=ne, pat+ pb++ pc++, else if(A data[pa]. jB. datalpb]j A. datalpc) i-x A. datalpc) j=B. datapb] j; A. datalpc] e=B. datalpb]e, else A. datalpc) i-X A. datalpc)- j=A data[pa] j A. datalpc) e=A data[pa]e i//while while( Acatalpa}=x)/插入A中剩余的元素(第x行 A. datalpc) Fx; A. datalpc] FA. datapa] j: A. datalpc) e=A data[pa).e while( B data[pb}=x)/插入B中剩余的元素(第x行) A. datalpc) Fx; A data[pc] jF=B data[pb]. j; A. datalpc) e=B. datalpb]e:
for(x=1;xB.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;
i//for A tupa, for(i=Atui< MAXSIZE;++) Adata i}={0,0,0};/清除原来的A中记录 i//SMAtrix Addto 5.23 typedef struct( Int 3 DSElem typedef struct( DSElem dataMAXSIZE] int cpot[MAXROW]J/这个向量存储每一行在二元组中的起始 位置 } SMAtrix,∥二元组矩阵类型 Status DSMatrix Locate(SMAtrix A, int I,ntj,int&ey求二元组矩阵的元素A[ 的值e for(s= AcpotI; s< A cpot[+1]&& A datas]jI=; s+)∥/注意查找范围 ifs< A cpotI+1]&& A data[s]. j=j)∥找到了元素A e=A data[s]; return OK return ErroR i//DSMatrix Locate 5.24 typedef struct( Int seq;∥该元素在以行为主序排列时的序号 El typedef structi SElem data MAXSIZE]; Iint mu. nu. ti } SMatrix,∥单下标二元组矩阵类型
pb++;pc++; } }//for A.tu=pc; for(i=A.tu;i<MAXSIZE;i++) A.data[i]={0,0,0}; //清除原来的 A 中记录 }//TSMatrix_Addto 5.23 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=A.cpot[i];s<A.cpot[i+1]&&A.data[s].j!=j;s++);//注意查找范围 if(s<A.cpot[i+1]&&A.data[s].j==j) //找到了元素 A[i][j] { 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 1, int J,nt&e》/求单下标二元组矩阵的元素 A[]的值e s=1*Anu+y+1;p=1 while( A. datalp]seq<s)p++,/利用各元素seq值逐渐递增的特点 f( A data[p]seq=s∥找到了元素A[l e=A data[].e; return OK eturn errol i//SMatrix Locate 5.25 typedef enum( 0, 1) bool typedef struct( int elem[MAXSIZE] bool map[mu nu] } BIMatrix,W用位图表示的矩阵类型 void BImatrix Add( BIMatrix A, BMMatrIx B, BIMatrix&C∥位图矩阵的加法 C. mu=A. mu C nu=A. nu for(i=0<Amu;++)∥每一行的相加 for(=0 j<A nu j++)∥每一个元素的相加 if(A. map[&&Bmap]]&&(Aeem[pa]+ Belem Ipb])结果不为0 C. elemlpcI=A elem[pa+B elem[pb Cmap[[]=1; else if(A mapid&&! B mapOD C. elemlpcF=A elem[pa] C maple else if(IA map[o]&&B mapiD C. elemlpcl=B elem[pbl
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<s) p++; //利用各元素 seq 值逐渐递增的特点 if(A.data[p].seq==s) //找到了元素 A[i][j] { 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<A.mu;i++) //每一行的相加 for(j=0;j<A.nu;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];
Cmap[[}=1; pb++: pc++ i//BMMatrix Add 5.26 void Print olmatrixi( OLMatrix A∥以三元组格式输出十字链表表示的矩阵 for(F0, Inght)/逐次遍历每一个行链表 printf("%d %d%d\n",i,p->j p->e: i//Print OLMatrix 5.27 void oLMatrix Add( amAtrix&A, OLMatrix B把十字链表表示的矩阵B加到A 上 for(=1jjpb->j)/新插入一个结点 p=(OLNode*)malloc(sizeof(OLNode) if(pre)A rhead j=p else pre->right=p: p->right=pa pre=p p>i=ip->j=pb->jip->e=pb->e;/插入行链表中 if( A head[p→>j) A chad [p->jF=p p->down=NULL; while(cplp->j1->down) cplp->J=cp[p->jJ->down;
C.map[i][j]=1; pb++;pc++; } } }//BMMatrix_Add 5.26 void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵 { for(i=0;iright) //逐次遍历每一个行链表 printf("%d %d %d\n",i,p->j,p->e; } }//Print_OLMatrix 5.27 void OLMatrix_Add(OLMatrix &A,OLMatrix B)//把十字链表表示的矩阵 B 加到 A 上 { for(j=1;jj>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=cplp->j1->down cpIp->J1->down=p; cpp->j}=p,/插入列链表中 else if(pa->jJ) tht }/pa右移一步 else if(pa->etpb->e pre=pa pa=pa->right pb=pb->right }∥直接相加 else if(pre)A rhead [=pa->right ght=pa-> p=papa=pa> right;∥从行链表中删除 if(A head [p->J-p A head p->j=cplp->j=p->down else cp[p->j->down=p->down,∥从列链表中删除 free(p) i//else //while i/OLMatrix Add 分析本题的具体思想在课本中有详细的解释说明 5.28 void plist pian dao( MPLiSt&L对广义表存储结构的多元多项式求第一变元 的偏导 for(p=L->hp->tp: p&&p->exp pre=p, p=p->tp) f(p->tag) Mul(p->hp, p->exp); else p->coe*=p->exp;/把指数乘在本结点或其下属结点上 p->exp--3 ifp)fre(p),∥删除可能存在的常数项 i//MPList PianDao
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 mu( PLIst&L,intx∥递归算法,对多元多项式L乘以ⅹ for(p=L; p, p=p->tp) if(p->tag) p->coef*= else Mul(p->hp, x) i//Mul 5.29 void pList add( MPList A PList e,MPLt&C广义表存储结构的多项式相加 的递归算法 C=(MPLNode*malloc(sizeof(MPLNode)) i(Atag&&B→tag)∥原子项可直接相加 C->coef=A->coef+B->coef: free(C) i//if else if(A->tag&&B->tag)/两个多项式相加 FA 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->hp=A->hp pre->tp=C, pre=C p=p→tp
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;