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

第五章数组和广义表 5.18 void rSh(int A[n, int k)/把数组A的元素循环右移k位,只用一个辅助存储空间 for(Fl; K<=k; i++) ifn%=0&&k%==0)p=/求n和k的最大公约数p for(F0; i<p: i++) 1; F(i+k)%n, temp=Ad while(l=i Alltemp: temp=A[l A[]A] j=1; F=0+k)%n; }∥循环右移一步 Altemp f J //RSh 分析要把A的元素循环右移k位,则A[O]移至A〖k],A队k]移至A[2k]…直到最终 回到A[0]然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有 被访问过而是被跳了过去分析可知当n和k的最大公约数为p时,只要分别以 A[0]A[l-.A[p-1.起点执行上述算法,就可以保证每一个元素都被且仅被右移 次,从而满足题目要求也就是说,A的所有元素分别处在p个"循环链"上面举例 如下 n=15k=6,则p=3 第一条链A[0]->A[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;i<=k;i++) if(n%i==0&&k%i==0) p=i;//求 n 和 k 的最大公约数 p for(i=0;i<p;i++) { j=i;l=(i+k)%n;temp=A[i]; while(l!=i) { A[j]=temp; temp=A[l]; A[l]=A[j]; j=l;l=(j+k)%n; }// 循环右移一步 A[i]=temp; }//for }//RSh 分析:要把 A 的元素循环右移 k 位,则 A[0]移至 A[k],A[k]移至 A[2k]......直到最终 回到 A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有 被访问过,而是被跳了过去.分析可知,当 n 和 k 的最大公约数为 p 时,只要分别以 A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移 一次,从而满足题目要求.也就是说,A 的所有元素分别处在 p 个"循环链"上面.举例 如下: n=15,k=6,则 p=3. 第一条链:A[0]->A[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: k<m: k++) if(min<Ak]o flag=0; if(flag) printf("Found a saddle element! nA%d j[%d%d",LjAQ0D; i/for i//Get Saddle 5.20 本题难度极大,故仅探讨一下思路这一题的难点在于,在多项式的元数m未知的 情况下,如何按照降幂次序输出各项可以考虑采取类似于层序遍历的思想,从最 高次的项开始依次对其每一元的次数减一,入一个队列附设访问标志 visited以 避免重复 5.21 void SMAtrix Add( ISMatⅸxA, ISMatrⅸB, SMAtrix&C∥三元组表示的稀疏矩 阵加法 C. muFA. mu C nu=A. nu C tuO for(x=1x<=Amux++)∥对矩阵的每一行进行加法 while(A catalpa]. i<x) pat while(B. datalpb] i<x) pb++ whie( A datal pa]=x&& B data[pb]==x》行列值都相等的元素 if(A catalpa]. j==B data[pb]j) ce=A data[pa] e+B data[pb]e, ifce∥和不为0 C. datalpc]F=x C. datalpc] FA data[pa] j C. datalpc pa++ pb++ i/if else if(A data[pa] j>B. 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;k<m;k++) if(min<A[k][j]) flag=0; if(flag) printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]); } }//for }//Get_Saddle 5.20 本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数 m 未知的 情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最 高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志 visited 以 避免重复. 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.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. 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; }