东北大学：《数据结构》课程教学资源（学习资料）第五章 数组和广义表

第五章数组和广义表 5.18 void rSh(int A[n, int k)/把数组A的元素循环右移k位,只用一个辅助存储空间 for(Fl; KA[6]A[6}->A[12]A[2]>A[3A[3→>A[9]A[9>A[0] 第二条链A[]>A[7]A[7>A3]A[13>A[4]A[4]>A[0A[10]->A[] 第三条链A[2]>A[8]A[8]>A[4A[4>A[5A[5]→>A[A->A[2] 恰好使所有元素都右移一次 虽然未经数学证明,但作者相信上述规律应该是正确的 void Get Saddle( int a[mn]y求矩阵A中的马鞍点 for(=0i<m;计++) for(min=A[JOJ j=0; j<n: j++) ifA]<min)min=A[∥求一行中的最小值 ifA[iU}=min)∥判断这个(些)最小值是否鞍点

第五章 数组和广义表 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=l, k=0: kB. datapb]j C data[pc].FX; C data[pc].B data[pb]j; C. datalpc] e=B data[pb]e

{ for(flag=1,k=0;kB.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. datapc] Fx; C. datalpc] FA data[pa].j C. datalpc] e=A catalpa]e i/while while( A data[pa]}x)/插入A中剩余的元素(第x行) C. datalpc] Fx C. datalpc]- j =A data[pa] j; C data[pc] e=Adata[pa]e pa+t' pc++ hile( B datap}x)/插入B中剩余的元素(第x行) C. datalpc] F-x; C data pc] F=B data[pb]. j: C. datalpc]e=B. datalpb]e pb++: pc++ C tu=pc: i//TSMatrix Add void SMAtrix Addto( TSMatrⅸx&A, SMAtrix B川将三元组矩阵B加到A上 for(F1; K<=A tu; i++) A data MAXSIZE-A tu+i= Adata把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-Atu+l; pb=l; pc=l for(x=1x<=Amux++)∥对矩阵的每一行进行加法 while(A data[pa]. i<x) pa while(B data[pb]. i<x) pb++ while( A catalpa]i=x&& B datap]i=x)行列值都相等的元素 if(A data[pa].j==Bdata[pb]) ne=A data[pa] e+B. datalpb]e; if(ne)∥和不为0

} 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=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) { ne=A.data[pa].e+B.data[pb].e; if(ne) //和不为 0 {

A. datalpc] Fx; A. datalpc] FA. data[pa] j; A. datalpc.e=ne, pa++ pb++ pc++; i/if else if(A data[pa].PB data[pb].j A. datalpc] i=x A. datalpc] j=B data[pb]j A. datalpc]e=B. datalpb]e A. datalpc] i-X; A. datalpc] jF=A data[]j A data[pc].e-A. data[ pa]e i//while while( A data[pa]}=x)/插入A中剩余的元素(第x行) A. datalpc] FX; A. datalpc] FA.data[pa]. A. datalpc] e=A data[].e whie( B datap]x)/插入B中剩余的元素(第x行) A. datalpc) ix A data[pc]. B data[pb].j A data[pc]e=B data[pb]e pb++;pc++; A tu=pc; for(i=Atui< MAXSIZE;++) Adata i}={0,0,0};/清除原来的A中记录 i//TSMatrix Addto 5.23 typedef struct( j

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<MAXSIZE;i++) A.data[i]={0,0,0}; //清除原来的 A 中记录 }//TSMatrix_Addto 5.23 typedef struct{ int j;

i SALem typedef struct( DSElem data MAXSIZE int cpot [ MAXROW∥/这个向量存储每一行在二元组中的起始 位置 Int mu. nu. tu: } SMAtrix,∥二元组矩阵类型 Status DSMatrix Locate(DSMatrix A, int i,ntj,int&ey求二元组矩阵的元素A[u 的值e for(s= cpot i: s<cpot[t+1k& A datas]j=;s++),注意查找范围 if(A data[s]=i&& A data[s]」=j)∥找到了元素A[ii e=A data[s]; return OK eturn error. i//DSMatrix Locate 5.24 typedef struct( Int seq;/该元素在以行为主序排列时的序号 3 SElem typedef structi SElem dataMAXSIZE]; Int mu. nu. t } SMatrix,单下标二元组矩阵类型 Status SMatrix Locate(SMatrix A, Int 1, int j, int&eM/求单下标二元组矩阵的元素 A[]的值e S-iA nu+j+1 p=l while( A datas]seq≤s)p++;∥利用各元素seq值逐渐递增的特点 if(A dataI]seq=s)∥找到了元素A[ji e=A. datalp]e return oK

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<cpot[i+1]&&A.data[s].j!=j;s++);//注意查找范围 if(A.data[s].i==i&&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 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 i//SMatrix Locate 5.25 ypedef enum( 0, 1) bool typedef struct( Int mu. nu: int elem MAXSIZEI: bool map[muju } BIMatrix,∥用位图表示的矩阵类型 void BImatrix Add( BMMatrix A BMMatrix B BImatrix&C位图矩阵的加法 C. muFA. mu C nu=A. nu pa=l; pb-l: pc=l for(i=0i<Amu;+)∥每一行的相加 for(j=0j<Anuj+)/每一个元素的相加 if(A. map[&&Bmap[订jk&( Aelem[pa]+ Belem[pb)结果不为0 C. elempc]A elem[pa+B elem[pb]: C mapEl pa++ pb++ else if(A map[jU]&&! B mapJ] C. elemlpc]F=Aelem[] C mapeL pat,pc++ else if(A map Jg]&&B mapoD C. elemlpc]=B elem[pb]; C mapOf=I i//BMMatrix Add 5.26 void Print olmatrixi( OLMatrix A)/以三元组格式输出十字链表表示的矩阵

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]; C.map[i][j]=1; pb++;pc++; } } }//BMMatrix_Add 5.26 void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵 {

for(F0; I right)∥逐次遍历每一个行链表 printf("%d%d %d\n", i, p->j.p->e; i//Print OLMatri 5.27 void olmatrix add( AmAtrix& A. OLMatrix B把十字链表表示的矩阵B加到A for(=1j=Anuj++)cpi} A head;∥向量cp存储每一列当前最后一个元素 的指针 for(Fl; Kjpb->j)/新插入一个结点 p=(OLNode*)malloc(sizeof(OLNode)); if(pre)A rhead[=p right=p: p->right=pa pre=p p>i=ip→>jpb->jip->e=pb->e;/插入行链表中 if(!A head [p->D) A head [p-j=p; p->down=NULL; else hile(cplp->Jl->down)cplp->J=cplp->J1->down p→>down=cp[p->}> >dowr cplp->j1->down=p cpp→>j}=p,/插入列链表中 else if(pa->jJ) pa=pa->right

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=cp[p->j]->down; cp[p->j]->down=p; } cp[p->j]=p; //插入列链表中 }//if else if(pa->jj) { pre=pa; pa=pa->right;

}/a右移一步 else if(pa->e+pb->e pre=pa pa=pa->right }∥直接相加 else if(pre)A rhead d=pa->right ight= p=papa=pa> right;∥从行链表中删除 if(A.chad [p->J-p) A. chead [p-J=cp[p->jF=p->down else cp[p->j->down=p->down,∥从列链表中删除 free(p); ielse //while ∥for J//OLMatrix Add 分析本题的具体思想在课本中有详细的解释说明 5.28 void plist pian dao( MPLiSt&L对广义表存储结构的多元多项式求第一变元 的偏导 for(p=L->hp->tp p&&p->exp pre=pp=p->tp) if(p->tag) Mul(p->hp, p->exp); else p->coe*=p->exp;/把指数乘在本结点或其下属结点上 p->exp-, pre-tp=NULL fp)fiee(p),∥删除可能存在的常数项 i//MPList PianDao void mul( MPList&L,intx)∥/递归算法对多元多项式L乘以ⅹ forp=Lp;p=p→tp) if(p->tag) p->coef* else Mul(p->hp, x) i//Mul

} //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 pList add( MPList A, MPList B, PLIsT&C广义表存储结构的多项式相加 的递归算法 C=(MPLNode*)malloc(sizeof(MPLNode)); i(A-tag&&B-→tag)∥原子项可直接相加 C->coef=A->coef+B->coef. if(!C f free(C); C=NULL. 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) MPList Add(A->hp, B->hp, C->hp); else if(p->exp>q->exp) C=(MPLNode")malloc(sizeof(MPLNode)) C->hp=A->hp pre->tp=C pre=C else C=(MPLNode")malloc(sizeof(MPLNode)); C->hp=B->hp pre->tp=C, pre=C q=q->tp;

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;

i/while while(p C=(MPLNode*)malloc(sizeof(MPLNode)) pre->tp=C pre=C while(g) C=(MPLNode*)malloc(sizeof(MPLNode) C->exp=q->exp, C->hp=q->hp pre->tp=C, pre=C qq->tp }将其同次项分别相加得到新的多项式原理见第二章多项式相加一题 ilelse if else if((A->tag&&!B->tag)∥多项式和常数项相加 for(p=A, p->tp->tp: p=p->tp); ifp->tp>exp=0)p→tp>coef+=x;∥当多项式中含有常数项时加上常数项 if(p->tp->coef) free(p→>tp) p- tp=NULL q=(MPLNode*)malloc(sizeof(MPLNode)); q→>coef=xq-→>exp=0 tag=0 q->tp=NULL; }∥否则新建常数项,下同 i/else if X=A->coef: for(p=B p->tp->tp: p=p->tp); if(p->tp->exp==0) p->tp->coef+=> if(p->tp->coef)

} }//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) {