线性表算法设计题(五)
2019-10-26 本文已影响0人
搬砖的猫
题目
设计算法将一个带头结点的单链表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)