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

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

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

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

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

　　void DisCreat (LinkedList A)∥A是带头结点的单链表 链表中结点的数据类型为整型 本算法将A分解成两个单链表B和C B中结点的数据小于零 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指向新的待处理结点 　　}　　}∥算法结束