合并有序单链表(升序) (8801)
拆分单链表(8805)
一、
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目
1、问题描述
输入若干个(最多20个)不含整数0的绝对值不超过100的整数，建立单链表A，
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
算法将单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点(链表A的元素类型为整型，
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
B、C表利用A表的结点,不另外占用其它的存储空间)。然后分两行按原数据顺序输出链表B和C。 2、输入
输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据为若干个(最多20个)不含整数0的绝对值不超过100的整数，输入-1000作为输入结束
标志
禁止坐卧标志下载饮用水保护区标志下载桥隧标志图下载上坡路安全标志下载地理标志专用标志下载
(-1000本身不作为输入的数据)。
3、输出
分两行按原数据顺序输出链表B和C，每两个数据之间一个空格。 4、输入例
4
49 53 -26 79 -69 -69 18 -96 -11 68 -1000 54 87 68 -71 -54 -14 -19 92 72 21 -35 -88 83 86 -1000
12 -38 -35 62 37 -32 -86 54 45 47 23 -90 -1000 87 48 68 30 -47 -68 -41 30 -41 -38 92 98 -1000 5、输出例
-69 -69 -96 -11 -26
49 53 79 18 68
-71 -54 -14 -19 -35 -88
54 87 68 92 72 21 83 86
-38 -35 -32 -86 -90
12 62 37 54 45 47 23
-47 -68 -41 -41 -38
87 48 68 30 30 92 98
二、算法指导
1、数据结构
根据题目要求，数据要存储于单链表，首先要确定建立的单链表的结点类型，结点类型可为:
typedef struct node
{
int data;
1
node *next;
}*linklist;
这里的linklist为指针类型，其变量为指向node的结点。
2、算法思路
(1) 设计初始化单链表的函数int initlist_l(linklist &l);以建立带头结点的空单链表。
int initlist_l(linklist &l)
{
// 构造一个带头结点的空单链表l，l是引用参数，是变参，其值其他函数要用。 }
(2) 设计建立单链表的函数void createlist_l(linklist l)。可用后插法建立单链表，当输入-1000时建立结束，这里的l开始时已指向单链表的头结点，l的值已不会变，所以只要值参就可以。
void createlist_l(linklist l) {
输入数据d;
while(d!=-1000)
{
产生新结点;
把d 赋值给新结点;
把新结点链接到链表l的尾部;
输入数据d;
}
}
(3) 输出单链表。
void print(linklist l)
{
// 按输出格式要求输出单链表l中结点的值
}
(4) 设计将单链表la拆分成两个单链表的函数void separate(linklist la,linklist lb linklist lc)，la为待拆分的单链表，lb和lc分别为两个拆分好的单链表(开始时，lb和lc均只有头结点)。拆分单链表的思想是依次扫描la表中的每个元素x，若x小于0，则可用后插法把元素x 的结点链接到lb的尾部;删除该元素，否则把元素x 的结点链接到lc的尾部。最后lb和lc单链表中就是所要拆分的两个单链表。 void separate(linklist la,linklist lb linklist lc)
2
{
a指向la表的第一个结点; p
pb、pc分别指向lb、lc的头结点;// 作为生成拆分后两个单链表的尾指针
while(pa不空) // 扫描la表中的每个元素
{
if(pa所指结点的元素值小于0) // 处理la表中结点元素值小于0的结点
,
pa所指结点链接在pb所指结点后面;// 后插法生成元素小于0的单链表
设置好lb表新的尾指针;
}
else // pa所指结点的元素值大于0
{
// 类似于pa所指结点的元素值小于0的情况
}
pa指向其下一个结点;
}
设置lb和lc单链表的结束标记;
删除la的头结点;
}
3、主函数
main()
{
调用initlist_l()，初始化单链表la,lb,lc;
调用createlist_l()，建立单链表la;
调用complement()，将la拆分成单链表lb和lc;
，输出lb和lc单链表; 调用print()
}
3
浙公网安备 33021202002483