数据结构上机例题及答案

习题二⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。2.3在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。Voidinsert(Lnode*h,inta,intb){Lnode*p,*q,*s;s=(Lnode*)malloc(sizeof(Lnode));s-data=b;p=h-next;while(p-data!=a&&p-next!=NULL){q=p;p=p-next;}if(p-data==a){q-next=s;s-next=p;}else{p-next=s;s-next=NULL;}}2.4设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。Lnode*cf(Lnode*ha){Lnode*p,*q,*s,*hb;intt;p=ha-next;q=ha;t=0;hb=(Lnode*)malloc(sizeof(Lnode));s=hb;while(p-next!=NULL){if(t==0){q=p;p=p-next;t=1;}else{q-next=p-next;p-next=s-next;s-next=p;s=p;p=p-next;t=0;}}s-next=NULL;return(hb);}2.5设线性表中的数据元素是按值非递减有序排列的，试以不同的存储结构，编写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。⑴顺序表；解：本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将x插入，并返回向量的新长度。实现本题功能的函数如下：intinsert(vectorA，intn，ElemTypex)/*向量A的长度为n*/{inti，j；if(x=A[n-1])A[n]=x/*若x大于最后的元素，则将其插入到最后*/else{i=0；while(x=A[i])i++；/*查找插入位置i*/for(j=n-1；j=i；j--)A[j+1]=A[j]；/*移出插入x的位置*/A[i]=x；n++；/*将x插入，向量长度增1*/}returnn;}⑵单链表。解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下：node*insertorder(head，x)node*head;ElemTypex;{node*s，*p，*q;s=(node*)malloc(sizeof(node));/*建立一个待插入的结点*/s-data=x;s-next=NULL;if(head==NULL||xhead-data)/*若单链表为空或x小于第一个结点的date域*/{s-next=head;/*则把s结点插入到表头后面*/head=s;}else{q=head;/*为s结点寻找插入位置，p指向待比较的结点，q指向p的前驱结点*/p=q-next;while(p!=NULL&&xp-data)/*若x小于p所指结点的data域值*/if(xp-data)/*则退出while循环*/{q=p;p=p-next;}s-next=p;/*将s结点插入到q和p之间*/q-next=s;}return(head);}2.6假设有A和B分别表示两个递增有序排列的线性表集合（即同一表中元素值各不相同），求A和B的交集C，表C中也依值递增有序排列。试以不同的存储结构编写求得C的算法。⑴顺序表；voidSqList_Intersect_True(SqList&A,SqListB)//求元素递增排列的线性表A和B的元素的交集并存回A中{i=1;j=1;k=0;while(A.elem[i]&&B.elem[j]){if(A.elem[i]B.elem[j])i++;elseif(A.elem[i]B.elem[j])j++;elseif(A.elem[i]!=A.elem[k]){A.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素i++;j++;//且C中没有,就添加到C中}}//whilewhile(A.elem[k])A.elem[k++]=0;}//SqList_Intersect_True⑵单链表。单链表chnode*or(chnode*head1,chnode*head2){chnode*p1,*p2,*q2,*h,*p;h=p=malloc(sizeof(chnode));p-next=NULL;p1=head1-next;while(p1){p2=head2;q2=p2-next;while((q2-data!=p1-data)&&q2){p2=q2;q2=q2-next;}if(p1-data==q2-data)p2-next=q2-next;if(q2){while(p-next)p=p-next;p-next=q2;p=q2;q2-next=NULL;}p1=p1-next;}return(h);}2.7设计一个算法求两个递增有序排列的线性表A和B的差集。（每个单链表中不存在重复的元素）提示：即在A中而不在B中的结点的集合。typedefintelemtype；typedefstructlinknode{elemtypedata；structlinknode*next；}nodetype；nodetype*subs(nodetype*heada,nodetype*headb){nodetype*p,*q,*r,*s；s=(nodetype*)malloc(sizeof(nodetype))；s-next=heada；heada=s；p=heada-next；r=heada；r-next=NULL；while(p!=NULL){q=headb；while(q!=NULL&&q-data!=p-data)q=q-next；if(q!=NULL){s=p-next；free(p)；p=s；}else{r-next=p；s=p-next；r=p；r-next=NULL；p=s；}}s=heada；heada=heada-next；free(s)；returnheada；}2.8设有线性表A=(a1,a2,...,am)，B=(b1,b2,...,bn)。试写一合并A、B为线性表C的算法，使得(a1,b1,...,am,bm,bm+1,...,bn)当m≤n时C＝｛(a1,b1,...,an,bn,an+1,...,am)当m＞n时A、B和C均以单链表作存储结构，且C表利用A和B中结点空间。解：假设A，B和C链表分别具有头结点的指针a，b和c。实现本题功能的函数如下：node*link(a，b)node*a，*b;{node*r，*s，*p，*q，*c;c=(node*)malloc(sizeof(node));/*建立一个头结点*/r=c;p=a;q=b;while(p!=NULL||q!=NULL){if(p!=NULL)/*如果A链表还存在可取的结点，则复制一个同样的结点链接到C中*/{s=(node*)malloc(sizeof(node));s-data=p-data;r-next=s;r=s;p=p-next;}if(q!=NULL)/*如果B链表还存在可取的结点，则复制一个同样的结点链接到C中*/{s=(node*)malloc(sizeof(node));s-data=q-data;r-next=s;r=s;q=q-next;}}r-next=NULL;s=c;c=c-next;/*删除头结点*/free(s);return(c);}2.9试用两种线性表的存储结构来解决约瑟夫问题。设有n个人围坐在圆桌周围，现从第s个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此重复直到所有的人全部出列为止。例如当n=8,m=4,s=1,得到的新序列为：4，8，5，2，1，3，7，6。写出相应的求解算法。解：先构造一个循环链表nodetype*crea(intn){nodetype*s,*r,*h;intI;for(i=1;i=n;i++){s=(nodetype*)malloc(sizeof(nodetype));s-data=I;s-next=NULL;if(i==1)h=s;elser-next=s;r=s;}r-next=h;returnh;}voidjese(nodetype*h,intm){nodetype*p=h,*q;intI;while(p-next!=p){for(i=1;im-1;i++)p=p-next;if(p-next!=p){q=p-next;printf(“%d”,q-data);p-next=q-next;free(q);}p=p-next;}printf(“%d”,p-data);}2.10已知单链表中的数据元素含有三类字符（即：字母字符、数字字符和其它字符），试编写算法构造三个环形链表，使每个环形链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：voidsplit(nodetype*ha,nodetype*hb,nodetype*hc){charc;nodetype*ra,*rb,*rc,*p=ha-next;ra=ha;ra-next=NULL;rb=hb;rb-next=NULL;rc=hc;rc-next=NULL;while(p!=ha){c=p-data;if((c=’a’&&c=’z’)||(c=’A’&&c=’Z’)){ra-next=p;ra=p;}elseif(c=’0’&&c=’9’){rb-next=p;rb=p;}else{rc-next=p;rc=p;}p=p-next;}ra-next=ha;rb-next=hb;rc-next=hc;}2.11假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知p为指向链表中某结点的指针，试编写算法在链表中删除结点p的前趋结点。解：nodetype*delprev(nodetype*p){nodetype*r=p,*q=r-next;while(q-next!=p){r=r-next;q=r-next;}r-next=p;free(q);return(p);}2.12假设有一个单向循环链表，其结点含三个域：pre、data和next，每个结点的pre值为空指针，试编写算法将此链表改为双向环形链表。分析：在遍历单链表时，可以利用指针记录当前访问结点和其前驱结点。知道了当前访问结点的前驱结点位置，就可以给当前访问结点的前驱指针赋值。这样在遍历了整个链表后，所有结点的前驱指针