专升本数据结构试题解析(6)

数据结构上机实验与习题解析 亱店↘打烊oO

r=q;

q=q->next;

free(r);

}

p->next=q;p=q;q=p->next;

}/*else*/

}/*while*/

}/*Delete_Equal */

7．试设计一个算法，对带头结点的单链表实现就地逆置。

【算法分析】

1）空表或长度为1的表，不做任何处理；

2）表长大于2时，做如下处理：

①首先将整个链表一分为二，即从链表的第一元素结点处断开；

②逐个地把剩余链表的当前元素q插入到链表的头部。

【算法源代码】

void LinkList_reverse(LinkList L)

{ if(!L->next||!L->next->next) return;

p=L->next; q=p->next; s=q->next;

p->next=NULL; /*从链表的第一元素结点处断开*/

while(s->next)

{q->next=p;p=q;

q=s;s=s->next; /*把L的元素逐个插入新表表头*/

}

q->next=p;s->next=q;L->next=s;

}/*LinkList_reverse*/

8．设线性表A=（a1，a2，…，am） 和 B=（b1，b2，…，bn），试设计一个按下列规则合并A，B为线性表C的算法，即使得

C=（a1，b1，…，am，bm，bm+1 ，…，bn ）当 m≤n时；

或者

C=（a1，b1，…，an，bn，an+1 ，…，am ）当m＞n时。

线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

【算法分析】

1）初始化指针p指向链表A的当前元素，指针q指向链表B的当前元素；

2）当链表A和B均为结束时，做如下处理：

①将B的元素插入

②若A非空，将A的元素插入

③指针p和q同时后移

【算法源代码】

void merge1(LinkList A,LinkList B,LinkList *C)

{p=A->next;q=B->next;*C=A;

while(p&&q)

{ s=p->next;p->next=q; /*将B的元素插入*/

if(s)

{ t=q->next;

q->next=s; /*若A非空，将A的元素插入*/

}

p=s;q=t; /*指针p和q同时后移*/

}/*while*/

}/*merge1 */

9．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请设计一个算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即 A表和B表）的结点空间构造C表。

【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余