《数据结构》-第五章 数组和广义表

《《数据结构》-第五章 数组和广义表》由会员分享，可在线阅读，更多相关《《数据结构》-第五章 数组和广义表（14页珍藏版）》请在装配图网上搜索。

1、第五章 数组和广义表 5.18 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.恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19 void Get_Saddle(int Amn)/求矩阵A中

2、的马鞍点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 5.20本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次

3、的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志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.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+;p

4、c+;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 5.

5、22 void TSMatrix_Addto(TSMatrix &A,TSMatrix B)/将三元组矩阵B加到A上for(i=1;i=A.tu;i+)A.dataMAXSIZE-A.tu+i=A.datai;/把A的所有元素都移到尾部以腾出位置pa=MAXSIZE-A.tu+1;pb=1;pc=1;for(x=1;x=A.mu;x+) /对矩阵的每一行进行加法while(A.datapa.ix) pa+;while(B.datapb.iB.datapb.j) A.datapc.i=x;A.datapc.j=B.datapb.j;A.datapc.e=B.datapb.e;pb+;pc+;el

6、seA.datapc.i=x;A.datapc.j=A.datapa.j;A.datapc.e=A.datapa.epa+;pc+;/whilewhile(A.datapa=x) /插入A中剩余的元素(第x行)A.datapc.i=x;A.datapc.j=A.datapa.j;A.datapc.e=A.datapa.epa+;pc+;while(B.datapb=x) /插入B中剩余的元素(第x行)A.datapc.i=x;A.datapc.j=B.datapb.j;A.datapc.e=B.datapb.e;pb+;pc+;/forA.tu=pc;for(i=A.tu;iMAXSIZE;i

7、+) A.datai=0,0,0; /清除原来的A中记录/TSMatrix_Addto 5.23 typedef struct int j; int e; DSElem; typedef structDSElem dataMAXSIZE;int cpotMAXROW;/这个向量存储每一行在二元组中的起始位置int mu,nu,tu; DSMatrix; /二元组矩阵类型 Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)/求二元组矩阵的元素Aij的值efor(s=cpoti;scpoti+1&A.datas.j!=j;s+);/注意查找范

8、围if(A.datas.i=i&A.datas.j=j) /找到了元素Aije=A.datas;return OK;return ERROR;/DSMatrix_Locate 5.24 typedef struct int seq; /该元素在以行为主序排列时的序号 int e; SElem; typedef struct SElem dataMAXSIZE; int mu,nu,tu; SMatrix; /单下标二元组矩阵类型 Status SMatrix_Locate(SMatrix A,int i,int j,int &e)/求单下标二元组矩阵的元素Aij的值es=i*A.nu+j+1;

9、p=1;while(A.datap.seqs) p+; /利用各元素seq值逐渐递增的特点if(A.datap.seq=s) /找到了元素Aije=A.datap.e;return OK;return ERROR;/SMatrix_Locate 5.25 typedef enum0,1 bool; typedef struct int mu,nu; int elemMAXSIZE; bool mapmunu; BMMatrix; /用位图表示的矩阵类型 void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)/位图矩阵的加法C.mu=A.mu;C

10、.nu=A.nu;pa=1;pb=1;pc=1;for(i=0;iA.mu;i+) /每一行的相加for(j=0;jA.nu;j+) /每一个元素的相加if(A.mapij&B.mapij&(A.elempa+B.elempb)/结果不为0C.elempc=A.elempa+B.elempb;C.mapij=1;pa+;pb+;pc+;else if(A.mapij&!B.mapij)C.elempc=A.elempa;C.mapij=1;pa+;pc+;else if(!A.mapij&B.mapij)C.elempc=B.elempb;C.mapij=1;pb+;pc+;/BMMatrix

11、_Add 5.26 void Print_OLMatrix(OLMatrix A)/以三元组格式输出十字链表表示的矩阵for(i=0;iright) /逐次遍历每一个行链表printf(%d %d %dn,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+) cpj=A.cheadj; /向量cp存储每一列当前最后一个元素的指针for(i=1;ijpb-j) /新插入一个结点p=(OLNode*)malloc(sizeof(OLNode

12、);if(!pre) A.rheadi=p;else pre-right=p;p-right=pa;pre=p;p-i=i;p-j=pb-j;p-e=pb-e; /插入行链表中if(!A.cheadp-j)A.cheadp-j=p;p-down=NULL;elsewhile(cpp-j-down) cpp-j=cpp-j-down;p-down=cpp-j-down;cpp-j-down=p;cpp-j=p; /插入列链表中/ifelse if(pa-jj)pre=pa;pa=pa-right; /pa右移一步else if(pa-e+pb-e)pa-e+=pb-e;pre=pa;pa=pa-

13、right;pb=pb-right; /直接相加elseif(!pre) A.rheadi=pa-right;else pre-right=pa-right;p=pa;pa=pa-right; /从行链表中删除if(A.cheadp-j=p)A.cheadp-j=cpp-j=p-down;else cpp-j-down=p-down; /从列链表中删除free (p);/else/while/for/OLMatrix_Add分析:本题的具体思想在课本中有详细的解释说明. 5.28 void MPList_PianDao(MPList &L)/对广义表存储结构的多元多项式求第一变元的偏导for(

14、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乘以xfor(p=L;p;p=p-tp)if(!p-tag) p-coef*=x;else Mul(p-hp,x);/Mul5.29 void MPList_Add(MPList A,MPList B,MPList

15、 &C)/广义表存储结构的多项式相加的递归算法C=(MPLNode*)malloc(sizeof(MPLNode);if(!A-tag&!B-tag) /原子项,可直接相加C-coef=A-coef+B-coef;if(!C-coef)free(C);C=NULL;/ifelse 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-

16、tp;q=q-tp;else if(p-expq-exp)C=(MPLNode*)malloc(sizeof(MPLNode);C-exp=p-exp;C-hp=A-hp;pre-tp=C;pre=C;p=p-tp;elseC=(MPLNode*)malloc(sizeof(MPLNode);C-exp=q-exp;C-hp=B-hp;pre-tp=C;pre=C;q=q-tp;/whilewhile(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=(MPLNo

17、de*)malloc(sizeof(MPLNode);C-exp=q-exp;C-hp=q-hp;pre-tp=C;pre=C;q=q-tp; /将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题/else ifelse 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;elseq=(MPLNode*)malloc(sizeof(MPLNode);q-c

18、oef=x;q-exp=0;q-tag=0;q-tp=NULL;p-tp=q; /否则新建常数项,下同/else ifelsex=A-coef;for(p=B;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;elseq=(MPLNode*)malloc(sizeof(MPLNode);q-coef=x;q-exp=0;q-tag=0;q-tp=NULL;p-tp=q;/else/MPList_Add 5.30 int GList_Getdeph(GList L)/求广义表深度的递归算法

19、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 5.31 void GList_Copy(GList A,GList &B)/复制广义表的递归算法if(!A-tag) /当结点为原子时,直接复制B-tag=0;B-atom=A-atom;else /当结点为子表时B-tag=1;if(A-ptr.hp)B-ptr.hp=malloc(sizeof(GLNode);G

20、List_Copy(A-ptr.hp,B-ptr.hp); /复制表头if(A-ptr.tp)B-ptr.tp=malloc(sizeof(GLNode);GList_Copy(A-ptr.tp,B-ptr.tp); /复制表尾/else/GList_Copy 5.32 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(

21、GList_Equal(A-ptr.hp,B-ptr.hp)&GList_Equal(A-ptr.tp,B-ptr.tp)return 1; /表头表尾都相等return 0;/GList_Equal 5.33 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); /注

22、意尾表与原表是同一层次/GList_PrintElem 5.34 void GList_Reverse(GList A)/递归逆转广义表Aif(A-tag&A-ptr.tp) /当A不为原子且表尾非空时才需逆转D=C-ptr.hp;A-ptr.tp-ptr.hp=A-ptr.hp;A-ptr.hp=D; /交换表头和表尾GList_Reverse(A-ptr.hp);GList_Reverse(A-ptr.tp); /逆转表头和表尾/GList_Reverse 5.35 Status Create_GList(GList &L)/根据输入创建广义表L,并返回指针scanf(%c,&ch);if

23、(ch= )L=NULL;scanf(%c,&ch);if(ch!=) return ERROR;return OK;L=(GList)malloc(sizeof(GLNode);L-tag=1;if(isalphabet(ch) /输入是字母p=(GList)malloc(sizeof(GLNode); /建原子型表头p-tag=0;p-atom=ch;L-ptr.hp=p;else if(ch=() Create_GList(L-ptr.hp); /建子表型表头else return ERROR;scanf (%c,&ch);if(ch=) L-ptr.tp=NULL;else if(ch

24、=,) Create_GList(L-ptr.tp); /建表尾 else return ERROR;return OK;/Create_GList分析:本题思路见书后解答. 5.36 void GList_PrintList(GList A)/按标准形式输出广义表if(!A) printf(); /空表else if(!A-tag) printf(%d,A-atom);/原子elseprintf();GList_PrintList(A-ptr.hp);if(A-ptr.tp)printf(,);GList_PrintList(A-ptr.tp); /只有当表尾非空时才需要打印逗号printf

25、();/else/GList_PrintList 5.37 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&A-ptr.hp-atom=x)q=A;A=A-ptr.tp;/删去元素值为x的表头free(q);GList_DelElem(A,x);if(A-ptr.tp) GList_DelElem(A-ptr.tp,x);/GList_DelElem 5.39 void GList_PrintElem_LOrder(GList A)/按层序输出广义表A中的所有元素InitQueue(Q);for(p=L;p;p=p-ptr.tp) EnQueue(Q,p);while(!QueueEmpty(Q)DeQueue(Q,r);if(!r-tag) printf(%d,r-atom);elsefor(r=r-ptr.hp;r;r=r-ptr.tp) EnQueue(Q,r); /while/GList_PrintElem_LOrder 分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.