第五章 数组和广义表.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

第五章 数组和广义表  



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=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.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.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;
　　　　　　  　　　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;
}//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(i=0;i<A.mu;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

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->j<pb->j)
　　　{
　　　　pre=pa;