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

第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指向新的待排序结点*/

}

}