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

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

(１)［问题分析］与上题类似不同之处在于一是链表无头结点为处理方便给加上头结点处理结束再删除之;二是数据相同的结点不合并到结果链表中;三是hb链表不能被破坏即将hb的结点合并到结果链表时要生成新结点

LinkedList Union(LinkedList ha hb)∥ha和hb是两个无头结点的数据域值递增有序的单链表本算法将hb中并不出现在ha中的数据合并到ha中合并中不能破坏hb链表

｛LinkedList la;

la=(LinkedList)malloc(sizeof(LNode));

la>next=ha;∥申请头结点以便操作

pa=ha;∥pa是ha链表的工作指针

pb=hb;∥pb是hb链表的工作指针

pre=la;∥pre指向当前待合并结点的前驱

while(pa&&pb)

if(pa>data<pb>data)∥处理ha中数据

{pre>next=pa;pre=pa;pa=pa>next;}

else if(pa>data>pb>data)∥处理hb中数据

{r=(LinkedList)malloc(sizeof(LNode));∥申请空间

r>data=pb>data; pre>next=r;

pre=r;∥将新结点链入结果链表

pb=pb>next;∥hb链表中工作指针后移

}

else∥处理pa>data=pb>data;

{pre>next=pa; pre=pa;

pa=pa>next;∥两结点数据相等时只将ha的数据链入

pb=pb>next;∥不要hb的相等数据

}

if(pa!=null)pre>next=pa;∥将两链表中剩余部分链入结果链表

else pre>next=pb;

free(la);∥释放头结点hahb指针未被破坏

}∥算法nion结束

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