《数据结构与算法》课后答案(2)

{k=R[low]; R[low]=R[high]; R[high]=k; }

}

low=low+1; high=n-1; while(low

{while(low

R[low]=R[high]; R[high]=k; }

}

5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表： （a1, a2, … , am, b1, b2, … , bn）改变为： （b1, b2, … , bn , a1, a2, … , am）。 }

/*将数字放在字母后

【提示】比较m和n的大小，若m

{if(m<=n)

for(i=1;i<=m;i++)

{x=L->data[0];

for(k=1;k<=L->last;k++)

L->data[k-1]=L->data[k];

L->data[L->last]=x; }

else for(i=1;i<=n;i++)

{x=L->data[L->last];

for(k=L->last-1;k>=0;k- -) L->data[k+1]=L->data[k]; L->data[0]=x; } }

6．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。 LinkList insert(LinkList L, int x) {p=L;

while(p->next && x>p->next->data) p=p->next;

/*寻找插

入位置*/

s=(LNode *)malloc(sizeof(LNode)); s->data=x;

/*申请结点空间*/

/*填装

结点*/

s->next=p->next; p->next=s;

/*将结点插入

到链表中*/

return(L);

}

7．假设有两个已排序（递增）的单链表A和B，编写算法将它们合并成一个链表C而不改变其排序性。 LinkList Combine(LinkList A, LinkList B)

{C=A; rc=C; pa=A->next; pb=B->next; free(B);

头结点*/

while (pa && pb)

/*将pa、pb所指向结点中，值

/*pa指向表A的第一个结点*/ /*pb指向表B的第一个结点*/

/*释放B的

较小的一个插入到链表C的表尾*/

if(pa->datadata)

{rc->next=pa; rc=pa; pa=pa->next; } else

{rc->next=pb; rc=pb; pb=pb->next; }

if(pa)

rc->next=pa;

/*将链表A或B中剩余的部分链接到

else rc->next=pb;

链表C的表尾*/

return(C);

}

8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。 【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。 viod delepre(LNode *s) {LNode *p, *q; p=s;

while (p->next!=s) {q=p; p=p->next; } q->next=s; free(p); }

9．已知两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C，要求C同样以元素递增的单链表形式存储。

【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。 LinkList Intersect(LinkList A, LinkList B)

{LNode *q, *p, *r, *s; LinkList C;

C= (LNode *)malloc(sizeof(LNode)); C->next=NULL; r=C; p=A;