数据结构考研分类复习真题 第二章 答案[24]

[算法讨论]由于算法要求不得使用NEW过程申请空间也没明确指出链表具有头结点所以上述算法复杂些它可能需要在第一个结点前插入新结点即链表的头指针会发生变化如有头结点算法不必单独处理在第一个结点前插入结点情况算法会规范统一下面的()是处理带头结点的例子算法中偶数链上结点是靠数据整除等于(DATA DIV =)判断的

类似本题的其它题解答如下

()[题目分析]本题基本类似于上面第题不同之处有二一是带头结点二是分解后的两个链表一个是数据值小于另一个是数据值大于由于没明确要求用类PASCAL书写算法故用C书写如下

void DisCreat(LinkedList A)∥A是带头结点的单链表链表中结点的数据类型为整型本算法将A分解成两个单链表B和CB中结点的数据小于零C中结点的数据大于零

{B=A;

C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间

C>next=null∥C初始化为空表

p=A>next;∥p为工作指针

B>next=null;∥B表初始化

while(p!=null)

{r=p>next;∥暂存p的后继

if (p>data<)∥小于的放入B表

{p>next=B>next; B>next=p; }∥将小于的结点链入B表

else {p>next=C>next; C>next=p; }

p=r;∥p指向新的待处理结点

}

}∥算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []