数据结构课后习题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;i<L->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(i<j)
{
while(i<j && L->data[j]>0)
j--;
while(i<j && L->data[i]<0)
i++;
if(i<j)
{
temp=L->data[i];
L->data[i]=L->data[j];
L->data[j]=temp;
}
}
}

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