合并有序单链表降序8802.doc

合并有序单链表(降序)(8802)一、题目1、问题描述各依次输入非递减有序若干个(最多20个)不超过100的整数,分别建立两个非递减单链表,将这两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。合并后的单链表中允许有重复的数据。然后输出合并后的单链表。2、输入输入数据的第一行为一个正整数T,表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行和第二行分别为若干个(最多20个)依次非递减有序的不超过100的整数,输入-1000作为输入结束标志(-1000本身不作为输入的数据)。3、输出输出合并后的单链表,每两个数据之间一个空格。4、输入例3182122223334384952596473747478-10001923262627535960758384-1000293232404547475056666778819697-100022343537455360678**********-1000171823283641414360677183849498-100016313142495864687879899496-10005、输出例84837875747473646059595352493834332726262322222119189796959485848381817867676660565350474745454037353432322922989694948984837978716867646058494342414136313**********二、算法指导1、数据结构根据题目要求,数据要存储于单链表,首先要确定建立的单链表的结点类型,结点类型可为:typedefstructnode{ intdata; node*next;}*linklist;这里的linklist为指针类型,其变量为指向node的结点。2、算法思路(1)设计初始化单链表的函数intinitlist_l(linklist&l);以建立带头结点的空单链表。intinitlist_l(linklist&l){//构造一个带头结点的空单链表l,l是引用参数,是变参,其值其他函数要用。}(2)设计建立非递减单链表的函数voidcreatelist_l(linklistl)。可用后插法建立单链表,当输入-1000时建立结束,这里的l开始时已指向单链表的头结点,l的值已不会变,所以只要值参就可以。voidcreatelist_l(linklistl){输入数据d;while(d!=-1000){产生新结点;把d赋值给新结点;把新结点链接到链表l的尾部;输入数据d;}}(3)输出单链表。voidprint(linklistl){//按输出格式要求输出单链表l中结点的值}(4)设计将两个非递减的有序单链表合并为一个非递增的有序单链表的函数voidmergelist_l(linklistla,linklistlb),la和lb分别为两个非递减的有序单链表。合并思想是把lb表中与la表中的数据依次取小的一个,前插法插入到到开始只