数据结构上机实验与习题解析 亱店↘打烊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的剩余