数据结构课后习题2.docVIP

2-2.若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在【x，y】之间的所有元素。要求算法的时间复杂度为O（n），空间复杂度为O(l). void Delete(squence *L,int x,int y) { int i,k=0; for(i=0;iL-length;i++) { if(L-data[i]=x L-data[i]=y) k++; else L-data[i-k]=L-data[i]; } 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(ij L-data[j]0) j--; while(ij L-data[i]0) i++; if(ij) { temp=L-data[i]; L-data[i]=L-data[j]; L-data[j]=temp; } } } -4.设计一个算法，将一个带头结点的数据域依次为a1，a2，…，an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为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; } 运行结果：