第十二章动态数据结构

第十二章——动态数据结构——课后作业及参考答案第1页共9页第十二章_动态数据结构12.1设有变量说明int*p1,*p2,*p3,指出下列程序段的执行结果。1)p1=(int*)malloc(sizeof(int));p2=(int*)malloc(sizeof(int));*p1=9;*p2=5*(*p1%5);p3=p1;p1=p2;p2=p3;printf(“%5d%5d%5d\n”,*p1,*p2,*p3);2)p1=(int*)malloc(sizeof(int));*p1=25;p3=(int*)malloc(sizeof(int));*p3=*p1;p2=(int*)malloc(sizeof(int));*p2=3;*p3=*p3/*p2;*p2=*p1/*p3;printf(“%5d%5d%5d\n”,*p1,*p2,*p3);3)p1=(int*)malloc(sizeof(int));*p1=5;p2=(int*)malloc(sizeof(int));*p2=8;*p1=*p1+*p2;printf(“d%5d%5d\n”,*p1,*p2);4)p1=(int*)malloc(sizeof(int));*p1=12;p2=p1;p1=(int*)malloc(sizeof(int));*p1=*p2+7;printf(“d%5d%5d\n”,*p1,*p2);参考答案：20992538d138d191212.2设有数据类型如下：structtr{intd;structtr*n;}分别用循环和递归方法编函数，求结点类型为tr的链表长度。参考答案：第十二章——动态数据结构——课后作业及参考答案第2页共9页循环方法：#includestdlib.h#includemalloc.hstructtr{intd;structtr*n;};intlen(structtr*x){intl=0;structtr*tp=x;while(tp!=NULL){l++;tp=tp-n;}returnl;}voidmain(){structtr*tr1=(structtr*)malloc(sizeof(structtr));structtr*tr2=(structtr*)malloc(sizeof(structtr));structtr*tr3=(structtr*)malloc(sizeof(structtr));tr1-d=1;tr2-d=2;tr3-d=3;tr1-n=tr2;tr2-n=tr3;tr3-n=NULL;printf(%d\n,len(tr1));}递归方法：#includestdlib.h#includestdio.hstructtr{intd;structtr*n;};intlen(structtr*x){if(x==NULL)return0;elsereturnlen(x-n)+1;}voidmain(){structtr*tr1=(structtr*)malloc(sizeof(structtr));structtr*tr2=(structtr*)malloc(sizeof(structtr));structtr*tr3=(structtr*)malloc(sizeof(structtr));structtr*tr4=NULL;tr1-d=1;tr2-d=2;tr3-d=3;tr1-n=tr2;tr2-n=tr3;第十二章——动态数据结构——课后作业及参考答案第3页共9页tr3-n=NULL;printf(%d\n,len(tr4));}12.3分别用循环和递归方法写函数,把给定的结点类型为tr的单向链表倒过来。参考答案：循环方法：#includestdio.h#includemalloc.htypedefstructitem{intkey;structitem*next;}itemType;itemType*initial(intn){//构造链表itemType*p,*base,*q;base=(itemType*)malloc(sizeof(itemType));base-key=1;q=base;for(inti=2;i=n;i++){p=(itemType*)malloc(sizeof(itemType));p-key=i;p-next=NULL;q-next=p;q=q-next;}p=NULL;returnbase;}voidprint(itemType*base){itemType*tmp=base;while(tmp!=NULL){printf(%d\t,tmp-key);tmp=tmp-next;}}itemType*reverse(itemType*base){itemType*p0,*p,*q,*rs=NULL,*p1,*r0;/*申请哨兵变量r0,用r0和p0标识要插入的位置构造初始化的r0、p0构成的链,而真正开始插入的元素由p标识*/r0=(itemType*)malloc(sizeof(itemType));r0-next=base;p0=base;p=base-next;base-next=NULL;/*将p插到r0和p0之间,修改p,p0为下次操作准备*/while(p!=NULL){q=p;p=p-next;q-next=p0;第十二章——动态数据结构——课后作业及参考答案第4页共9页r0-next=q;p0=q;}/*释放哨兵变量,返回结果*/rs=r0-next;free(r0);returnrs;}voidmain(){intm=9;itemType*begin=NULL,*re=NULL;begin=initial(m);print(begin);printf(\n);re=reverse(begin);print(re);}递归方法：#includestdio.h#includemalloc.hstructitem{intkey;structitem*next;};typedefstructitem*itempointer;itempointerreverse(itempointerhead,itempointercur){//将cur项插入到head前itempointertmp;if(cur!=NULL){tmp=cur-next;cur-next=head;reverse(cur,tmp);}else{returnhead;}}itempointerinitial(intn){//构造链表itempointerp,base,q;base=(itempointer)malloc(sizeof(structitem));base-key=1;q=base;for(inti=2;i=n;i++){p=(itempointer)malloc(sizeof(structitem));p-key=i;p-next=NULL;q-next=p;q=q-next;}p=NULL;第十二章——动态数据结构——课后作业及参考答案第5页共9页returnbase;}voidprint(itempointerbase){itempointertmp=base;while(tmp!=NULL){printf(%d\t,tmp-key);tmp=tmp-next;}}voidmain(){intm=9;itempointerbegin=NULL,re=NULL;begin=initial(m);print(begin);printf(\n);re=reverse(re,begin);print(re);}12.9设a、b是已按递增排序的单向链表。把即在a中出现又在b中出现的数从a、b上摘下来，按递增顺序生成链表c。参考答案：#includestdlib.h#includemalloc.hstructitem{intd;structitem*next;};typedefstructitem*itempointer;itempointercom(itempointerp,itempointerq){itempointerguard=(itempointer)malloc(sizeof(structitem));//结果链表表头哨兵guard-next=NULL;itempointertemp=guard;itempointeranew;//负责申请空间，增加新链表项itempointerl=p,b=q//l代表当前第一项小的链表，b代表当前第一项大的链表itempointers;//s代表临时变量intdl,db;do{if(l-db-d){//最开始比较两个链表第一哪个大s=b;b=l;l=s;}db=b-d;while(l!=NULL&&l-ddb){//寻找较小链表上第一个大于或等于较大链表上的第一项l=l-next;}第十二章——动态数据结构——课后作业及参考答案第6页共9页if(l!=NULL){//在较小链表上可以找到这一项时进行操作dl=l-d;if(db==dl){//如果所找数据项相等，则增加新表项anew=(itempointer)malloc(sizeof(structitem));anew-d=db;anew-next=NULL;temp-next=anew;temp=anew;l=l-next;b=b-next;}else{//否则l上找到的表项大于b上当前表相，则b下移一项b=b-next;}}}while(l!=NULL&&b!=NULL);temp=guard-next;//释放空的哨兵变量free(guard);returntemp;}voidprint(itempointerp){//打印单个链表itempointers=p;while(s!=NULL){printf(%d\t,s-d);s=s-next;}printf(\n);}voidmain(){itempointers1;itempointers2;itempointers3;itempointertmp=(itempointer)malloc(sizeof(structitem));//构造s1链表tmp-d=3;tmp-next=NULL;s1=tmp;tmp=(itempointer)malloc(sizeof(structitem));tmp-d=3;tmp-next=NULL;s1-next=tmp;tmp=(itempointer)malloc(sizeof(structitem));tmp-d=4;tmp-next=NULL;s1-next-next=tmp;tmp=(itempointer)malloc(sizeof(structitem));tmp-d=5;tmp-next=NULL;第十二章——动态数据结构——课后作业及参考答案第7页共9页s1-next-next-next=tmp;tmp=(itempointer)malloc(sizeof(structitem));//构造s2链表tmp-d=2;tmp-next=NULL;s2=tmp;tmp=(itempointer)malloc(sizeof(structitem));tmp-d=3;tmp-next=NULL;s2-next=tmp;tmp=(itempointer)malloc(sizeof(structitem));tmp-d=3;tmp-next=NULL;s2-next-next=tmp;s3=com(s1,s2);//求s3链表printf(s1:);print(s1);//打印printf(s2:);print(s2);printf(s3:);print(s3);}12.45定义:若两棵树满足如下条件则称它们是相似的。1