第2部分 习题解析 亱店↘打烊oO
else
{pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表 */
pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/
}
}
else
if(pa==NULL)pre->next=NULL; /*若A表已结束,置A表表尾*/
else /*处理原A表未到尾而B或C到尾的情况*/
{pre->next=NULL; /*置A表表尾标记*/
while(pa!=NULL) /*删除原A表剩余元素。*/
{u=pa;pa=pa->next;free(u);}
}
}
14.设 head为一单链表的头指针,单链表的每个结点由一个整数域data和指针域next组成,整数在单链表中是无序的。编一函数,将 head链中结点分成一个奇数链和一个偶数链,分别由p,q指向,每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。
【算法分析】本题要求将一个链表分解成两个链表,两个链表都要有序,两链表建立过程中不得使用malloc申请空间,这就是要利用原链表空间,随着原链表的分解,新建链表随之排序。
【算法源代码】
discreat(LinkList p, LinkList q, LinkList head)
{ p=NULL; q=NULL;/*p和q链表初始化为空表*/
s=head;
while(s!=NULL)
{r=s->next; /*暂存s的后继*/
if(s->data%2==0) /*处理偶数*/
if (p==NULL) {p=s;p->next=NULL;} /*第一个偶数结点*/
else { pre=p;
if(pre->data>s->data)
{s->next=pre;p=s;}/*插入当前最小值结点*/
else
{while (pre->next!=NULL)
if (pre->next->data<s->data) pre=pre->next;/*查找插入位置*/
s->next=pre->next; /*链入结点*/
pre->next=s;}
}
else/*处理奇数链
if (q==NULL) {q=s;q->next=NULL;} /*第一奇数结点*/
else
{pre=q;
if (pre->data>s->data) {s->next=pre; q=s;} /*修改头指针*/
else
{while (pre->next!=NULL) /*查找插入位置*/
if (pre->next->data<s->data) pre=pre->next;
s->next=pre->next; /*链入结点*/
pre->next=s; }
}/*结束奇数链结点*/
s=r; /*s指向新的待排序结点*/
}
}