数据结构习题及答案——严蔚敏

{for(j=0;jnext;

if(p==NULL||j>i) return(1); p->prior->next=p->next; p->next->prior=p->proir; free(p); return(0); } 8. 顺序存储:

void convert(elemtype list[],int l,int h) /* 个到第h个元素逆置*/ { int i;

elemtype temp;

for(i=h;i<=(l+h)/2;i++) {

temp=list[i]; list[i]=list[l+h-i]; list[l+h-i]=temp; } }

word文档 可自由复制编辑

将数组中第l

void exchange(elemtype list[],int n,int m); {

convert(list,0,n+m-1); convert(list,0,m-1); convert(list,m,n+m-1); }

该算法的时间复杂度为O(n+m),空间复杂度为O(1) 链接存储:(不带头结点的单链表) typedef struct node {

elemtype data; struct node *link; }NODE;

void convert(NODE **head,int n,int m) {

NODE *p,*q,*r; int i; p=*head; q=*head;

for(i=0;i

q=q->link; /*q指向an-1结点 */ r=q->link; q->link=NULL;

word文档 可自由复制编辑

while(r->link!=NULL)

r=r->link; /*r指向最后一个bm-1结点 */ *head=q; r->link=p; }

该算法的时间复杂度为O(n+m),但比顺序存储节省时间(不需要移动元素,只需改变指针),空间复杂度为O(1) 9.

typedef struct node {

elemtype data; struct node *link; }NODE;

NODE *union(NODE *ah,NODE *bh) {

NODE *a,*b,*head,*r,*q; head=ah; a=ah; b=bh;

while(a->link!=ah&&b->link!=bh) {

r=a->link; q=b->link;

word文档 可自由复制编辑

a->link=b; b->link=r; a=r; b=q; }

if(a->link==ah) /*a的结点个数小于等于b的结点个数 */ {

a->link=b;

while(b->link!=bh) b=b->link; b->link=head; }

if(b->link==bh) /*b的结点个数小于a的结点个数 */ {

r=a->link; a->link=b; b->link=r; }

return(head); }

该算法的时间复杂度为O(n+m),其中n和m为两个循环链表的结点个数. 10.

word文档 可自由复制编辑