数组与广义表.doc

第五章 数组和广义表 1.试设计一个算法，将数组An中的元素A0至An-1循环右移K位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O（n）。void RSh(int An,int k)/把数组A的元素循环右移k位,只用一个辅助存储空间for(i=1;i=k;i+)if(n%i=0&k%i=0) p=i;/求n和k的最大公约数pfor(i=0;iA6,A6-A12,A12-A3,A3-A9,A9-A0.第二条链:A1-A7,A7-A13,A13-A4,A4-A10,A10-A1.第三条链:A2-A8,A8-A14,A14-A5,A5-A11,A11-A2.恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的. 2. 若矩阵Amn中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维也纳数组存储矩阵Amn，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。void Get_Saddle(int Amn)/求矩阵A中的马鞍点for(i=0;im;i+)for(min=Ai0,j=0;jn;j+)if(Aijmin) min=Aij; /求一行中的最小值for(j=0;jn;j+)if(Aij=min) /判断这个(些)最小值是否鞍点for(flag=1,k=0;km;k+)if(minAkj) flag=0;if(flag)printf(Found a saddle element!nA%d%d=%d,i,j,Aij);/for/Get_Saddle 3. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。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.datapa.ix) pa+;while(B.datapb.iB.datapb.j) C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;elseC.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;/whilewhile(A.datapa=x) /插入A中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;while(B.datapb=x) /插入B中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;/forC.tu=pc;/TSMatrix_Add 4.试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。void Print_OLMatrix(OLMatrix A)/以三元组格式输出十字链表表示的矩阵for(i=0;iright) /逐次遍历每一个行链表printf(%d %d %dn,i,p-j,p-e;/Print_OLMatrix 5. 试按表头、表尾的分析方法重写求广义表的深度的递归算法。int GList_Getdeph(GList L)/求广义表深度的递归算法if(!L-tag) return 0; /原子深度为0else if(!L) return 1; /空表深度为1m=GList_Getdeph(L-ptr.hp)+1;n=GList_Getdeph(L-ptr.tp);return mn?m:n;/GList_Getdeph 6. 试编写判别两个广义表是否相等的递归算法。Int Glist_Equal(Glist A,Glist B)/判断广义表A和B是否相等,是则返回1,否则返回0 /广义表相等可分三种情况:if(!A&!B) return 1; /空表是相等的if(!A-tag&!B-tag&A-atom=B-atom) return 1;/原子的值相等if(A-tag&B-tag)if(Glist_Equal(A-ptr.hp,B-ptr.hp)&Glist_Equal(A-ptr.tp,B-ptr.tp)return 1; /表头表尾都相等return 0;/Glist_Equal 7. 试编写递归算法，输出广义表中所有原子项及其所在层次void GList_PrintElem(GList A,int layer)/递归输出广义表的原子及其所在层次,layer表示当前层次if(!A) return;if(!A-tag) printf(%d %dn,A-atom,layer);elseGList_PrintElem(A-ptr.hp,layer+1);GList_PrintElem(A-ptr.tp,layer); /注意尾表与原表是同一层次/GList_PrintElem 8. 试编写递归算法，依次从左至右输出广义表中所有值等于X的原子项。void GList_DelElem(GList &A,int x)/从广义表A中删除所有值为x的原子if(A-ptr.hp-tag) GList_DelElem(A-ptr.hp,x);else if(!A-ptr.hp-tag