设C={a1, b1, a2, b2, …, an, bn}为线性表,用带头结点的hc单链表存放,设计一个就地算法,将其拆分为两个线性表,使得A={a1, a2,…, an}, B={bn, …, b2, b1}。
算法思想:用上题的思路,不设序号变量。二者的差别仅在于对B,表的建立不采用尾插法,而是用头插法。
LinkList DisCreat_2(LinkList &A){
LinkList B= (LinkList)malloc(sizeof(LNode)) ; //创建B 表表头
B->next=NULL; //B 表的初始化
LNode *p=A->next, *q; //p 为工作指针
LNode *ra=A; //ra始终指向A的尾结点
while(p!=NULL){
ra->next=p; ra=p; //将*p 链到 A 的表尾
p=p->next;
q=p->next; //头插后,将断链,因此用q记忆*p的后继
p->next=B->next; //将插入到 B 的前端
B->next=p;
p=q
}
ra->next=NULL; //A尾结点的next域置空
return B;
}
该算法特别需要注意的是,用头插法插入结点后,*p的指针域已改变,如果不设变量保存其后继结点会引起断链,从而导致算法出错。