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

[算法讨论]因为本题并未要求链表中结点的数据值有序所以算法中采取最简单方式将新结点前插到头结点后面(即第一元素之前)

本题同上面第题除个别叙述不同外本质上完全相同故不再另作解答

()[题目分析]本题中的链表有头结点分解成表A和表B均带头结点分解后的A表含有原表中序号为奇数的元素B表含有原A表中序号为偶数的元素由于要求分解后两表中元素结点的相对顺序不变故采用在链表尾插入比较方便这使用一指向表尾的指针即可方便实现

void DisCreat(LinkedList A)∥A是带头结点的单链表本算法将其分解成两个带头结点的单链表A表中含原表中序号为奇数的结点B表中含原表中序号为偶数的结点链表中结点的相对顺序同原链表

{i=;∥i记链表中结点的序号

B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头

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

LinkedList rarb;∥ra和rb将分别指向将创建的A表和B表的尾结点

ra=A;rb=B;

p=A>next;∥p为链表工作指针指向待分解的结点

A>next=null;∥置空新的A表

while(p!=null)

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

i++;

if(i%==)∥处理原序号为偶数的链表结点

{p>next=rb>next;∥在B表尾插入新结点;

rb>next=p; rb=p;∥rb指向新的尾结点;

}

else∥处理原序号为奇数的结点

{p>next=ra>next; ra>next=p; ra=p; }

p=r;∥将p恢复为指向新的待处理结点

}∥算法结束

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