第五章+数组和广义表

第五章数组和广义表5.18voidRSh(intA[n],intk)//把数组A的元素循环右移k位,只用一个辅助存储空间{for(i=1;i=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公约数pfor(i=0;ip;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.19voidGet_Saddle(intA[m][n])//求矩阵A中的马鞍点{for(i=0;im;i++){for(min=A[i][0],j=0;jn;j++)if(A[i][j]min)min=A[i][j];//求一行中的最小值for(j=0;jn;j++)if(A[i][j]==min)//判断这个(些)最小值是否鞍点{for(flag=1,k=0;km;k++)if(minA[k][j])flag=0;if(minA[k][j])flag=0;if(flag)printf(Foundasaddleelement!\nA[%d][%d]=%d,i,j,A[i][j]);}}//for}//Get_Saddle5.20本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复.5.21voidTSMatrix_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].ix)pa++;while(B.data[pb].ix)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++;}}//ifelseif(A.data[pa].jB.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].eC.data[pc].e=A.data[pa].epa++;pc++;}}//whilewhile(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].epa++;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++;}}//forC.tu=pc;}//TSMatrix_Add5.22voidTSMatrix_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].ix)pa++;while(B.data[pb].ix)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++;}}//ifelseif(A.data[pa].jB.data[pb].j)elseif(A.data[pa].jB.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].epa++;pc++;}}//whilewhile(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].epa++;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++;}}//forA.tu=pc;for(i=A.tu;iMAXSIZE;i++)A.data[i]={0,0,0};//清除原来的A中记录}//TSMatrix_Addto5.23typedefstruct{intj;inte;}DSElem;typedefstruct{DSElemdata[MAXSIZE];intcpot[MAXROW];//这个向量存储每一行在二元组中的起始位置intmu,nu,tu;}DSMatrix;//二元组矩阵类型StatusDSMatrix_Locate(DSMatrixA,inti,intj,int&e)//求二元组矩阵的元素A[i][j]的值e][j]的值e{for(s=cpot[i];scpot[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];returnOK;}returnERROR;}//DSMatrix_Locate5.24typedefstruct{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].seqs)p++;//利用各元素seq值逐渐递增的特点if(A.data[p].seq==s)//找到了元素A[i][j]{e=A.data[p].e;returnOK;}returnERROR;}//SMatrix_Locate5.25typedefenum{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;iA.mu;i++)//每一行的相加for(j=0;jA.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++;}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_Add5.26voidPrint_OLMatrix(OLMatrixA)//以三元组格式输出十字链表表示的矩阵{for(i=0;iA.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_OLMatrix5.27voidOLMatrix_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-jpb-j)//新插入一个结点{p=(OLNode*)malloc(sizeof(OLNode));if(!pre)A.rhead[i]=p;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;//插入列链表中}//ifelseif(pa-