数据结构课后习题2.doc

2-2.若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在【x，y】之间的所有元素。要求算法的时间复杂度为O（n），空间复杂度为O(l).void Delete(squence *&L,int x,int y)int i,k=0;for(i=0;ilength;i+)if(L-datai=x & L-dataidatai-k=L-datai;L-length-=k;2-3若一个线性表L采用顺序存储结构存储，其中所有元素为整数。设计一个算法，将所有小于0的元素移到所有大于0的元素的前面，要求算法的时间复杂度为O(n)，空间复杂度为O（l）。void sort(Sqlist *&L) int i=0,j=L-length-1,temp; while(ij) while(idataj0) j-; while(idatai0) i+; if(idatai; L-datai=L-dataj; L-dataj=temp; 2. -4.设计一个算法，将一个带头结点的数据域依次为a1，a2，an（n3）的单链表的所有结点逆置，即第一个结点的数据域变为an，最后一个结点的数据域为a1。void reverse(Sqlist *&L)Sqlist *p=L-next,*q;L-next=NULL;while(p!=NULL)q=p-next;p-next=L-next;L-next=p;p=q;2-5设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。void sort(DLinkList *&L) /根据访问频度域排序DLinkList *pre,*p,*q;p=L-next-next;L-next-next=NULL;while(p!=NULL)q=p-next;pre=L;while(pre-next!=NULL & pre-next-freq p-freq)pre=pre-next;p-next=pre-next;if(pre-next!=NULL)pre-next-prior=p;pre-next=p;p-prior=pre;p=q; void LocateNode(DLinkList *&h,int x) /定位元素DLinkList *q;q=h-next;while(q!=NULL)if(q-data=x)q-freq+=1;q=q-next; sort(h);运行结果：2-6设ha=(a1,a2,an)和hb=(b1,b2, ,bm) 是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表hc的算法。void UnionList(LinkList *a,LinkList *b,LinkList *&c) LinkList *s,*r,*pa=a-next,*pb=b-next;int i;c=(LinkList*)malloc(sizeof(LinkList);c-next=NULL;r=c; while(pa!=a )s=(LinkList*)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;while(pb!=b)s=(LinkList*)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;r-next=c;运行结果：