数据结构课后习题2

《数据结构课后习题2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2-2.若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在【x，y】之间的所有元素。要求算法的时间复杂度为O（n），空间复杂度为O(l).voidDelete(squence*&L,intx,inty){inti,k=0;for(i=0;ilength;i++){if(L->data[i]>=x&&L->data[i]<=y)k++;elseL->data[i-k]=L->data[i];}L->length-=k;}2-3若一个线性表L采用顺序存储结构存储，其中所有元素为

2、整数。设计一个算法，将所有小于0的元素移到所有大于0的元素的前面，要求算法的时间复杂度为O(n)，空间复杂度为O（l）。voidsort(Sqlist*&L){inti=0,j=L->length-1,temp;while(idata[j]>0)j--;while(idata[i]<0)i++;if(idata[i];L->data[i]=L->data[j];L->data[j]=temp;}}}2.-4.设计一个算法，将一个带头结点的数据

3、域依次为a1，a2，…，an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为an，…，最后一个结点的数据域为a1。voidreverse(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(

4、h，x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。voidsort(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->fr

5、eq)pre=pre->next;p->next=pre->next;if(pre->next!=NULL)pre->next->prior=p;pre->next=p;p->prior=pre;p=q;}}voidLocateNode(DLinkList*&h,intx)//定位元素{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

6、,…,bm)是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表hc的算法。voidUnionList(LinkList*a,LinkList*b,LinkList*&c){LinkList*s,*r,*pa=a->next,*pb=b->next;inti;c=(LinkList*)malloc(sizeof(LinkList));c->next=NULL;r=c;while(pa!=a){s=(LinkList*)malloc(sizeof(LinkList));s->data=pa->data

7、;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;}运行结果：