线性表算法设计题（五）

题目

设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）

算法思想

关键点在于：（1）B表的头结点可以使用原来A表的头结点，而需要为C表新申请一个头结点；（2）对A表进行遍历的同时进行分解，完成结点的重新链接，在此过程中需要记录遍历的后继结点以防止链接后丢失后继结点；（3）本题并未要求链表中结点的数据值有序，所以在摘取满足条件的结点进行链接时，可以采取前插法，也可以采取后插法。

完整代码

#include <iostream>
using namespace std;
 
typedef struct LNode
{
    int data;
    LNode *next;
}LNode,*LinkList;
 
//创建链表
int CreateList(LinkList &L,int n){
    LNode *p,*r;int i;
    L=new LNode;
    L->next=NULL;
    r=L;
    for(i=0;i<n;i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=NULL;r->next=p;
        r=p;
    }
    return 0;
}
 
 
 
//输出链表
void display(LinkList L)
{
    LNode *p;
    p=L->next;
    cout<<"(";
    while(p)
    {cout<<p->data<<" ";
    p=p->next;}
    cout<<")"<<endl;
}
 
//拆分
int SplitList_L(LinkList &LA,LinkList &LB,LinkList &LC)
{
    LNode *pa;LNode *pb;LNode *pc;
    pa=LA->next;pb=LB;pc=LC;
    while(pa)
    {
       if(pa->data<0)
        {
            pb->next=pa;
            pa=pa->next;
            pb=pb->next;
            pb->next=NULL;
        }
        else
        {
            pc->next=pa;
            pa=pa->next;
            pc=pc->next;
            pc->next=NULL;
        }
 
    }
}
 
 
 
int main()
{
    LinkList LA;LinkList LB;LinkList LC;int n;;
 
 
    cout<<"请输入需要创建单链表A的长度："<<endl;
    cin>>n;
    cout<<"请依次输入需要存入的数据(尾插法&&非零)："<<endl;
    CreateList (LA,n);
 
    cout<<"单链表A为：";
    display(LA);
 
    LB=new LNode;LC=new LNode;
    LB->next=NULL;LC->next=NULL;
 
    SplitList_L(LA,LB,LC);
    cout<<"分解后单链表B为：";
    display(LB);
    cout<<"分解后单链表C为：";
    display(LC);
 
    return 0;
}

结果显示

![945KWQ]G`A3CMF5PFW3_FKP.png](https://img.haomeiwen.com/i1673319/710892117d702541.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)