《数据结构》将一个带头结点的单链表分解成两个单链表

本文主要是介绍《数据结构》将一个带头结点的单链表分解成两个单链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将一个带头结点的单链表分解成两个单链表

题目描述：

/*
设计一个算法，将一个带头结点的单链表分解成两个具有相同结构的
链表B和C，其中B白哦的结点为A中小于0的结点，C表的结点为A中大于0 的结点，
要求B和C 仍利用A表的结点。 (A表的元素都是非0元素)
*/

 

算法思想：‘

假设原来的链表是LA，将LA，分解成LB和LC，首先需要生成两个头结点，LB和LC；设置三个指针*pa,*pb,*pc，初始时，pa指向LA的第一个结点，pb指向LB的头结点，pc指向LC的头结点；然后遍历LA，当pa->data>0时，就将pa指向的结点插入到LB的后面，即pb->next=pa，然后让pb指向该结点,即pb=pb->next，指针pa后移pa=pa->next，表LB最后一个结点的指针域置空。当pa->data<0时，就将pa指向的结点插入到LC的后面，即pc->next=pa，然后让pc指向该结点,即pc=pc->next，指针pa后移pa=pa->next，表LC最后一个结点的指针域置空。

描述如下：

 

void Resolve(LinkList &LA,LinkList &LB,LinkList &LC){struct LNode *pa,*pb,*pc;pa=LA->next;LB=new LNode;LC=new LNode;//要生成两个新的头结点！！！ //LB=LC=LA;//不能这样写，这样写最后输出的LB和LChi一样的表，居然会一样？？为什么？？ pb=LB;pc=LC;struct LNode *p;p=pa;while(pa){if(pa->data>0){pb->next=pa;pa=pa->next;pb=pb->next;pb->next=NULL;}else if(pa->data<0){pc->next=pa;pa=pa->next;pc=pc->next;pc->next=NULL;}}
}

 

 

 

实现：

 

/*
设计一个算法，将一个带头结点的单链表分解成两个具有相同结构的
链表B和C，其中B白哦的结点为A中小于0的结点，C表的结点为A中大于0 的结点，
要求B和C 仍利用A表的结点。 (A表的元素都是非0元素)
*/
#include<stdio.h>
#define MAX 100typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;int InitList(LinkList &L){L=new LNode;L->next=NULL;return 1;
} int ListLength(LinkList L){int length=0;struct LNode *p;p=L->next;while(p){++length;p=p->next;}return length;
}void TraveList(LinkList L){struct LNode *p;p=L->next;while(p){printf("%d ",p->data);p=p->next;}printf("\n");
}void CreateList(LinkList &L,int n){L=new LNode;L->next=NULL;struct LNode *p;p=L;for(int i=0;i<n;i++){struct LNode *s;s=new LNode;printf("请输入%d个结点的值:",i+1);scanf("%d",&s->data);s->next=NULL;p->next=s;p=s;}
}void Resolve(LinkList &LA,LinkList &LB,LinkList &LC){struct LNode *pa,*pb,*pc;pa=LA->next;LB=new LNode;LC=new LNode;//要生成两个新的头结点！！！ //LB=LC=LA;//不能这样写，这样写最后输出的LB和LChi一样的表，居然会一样？？为什么？？ pb=LB;pc=LC;struct LNode *p;p=pa;while(pa){if(pa->data>0){pb->next=pa;pa=pa->next;pb=pb->next;pb->next=NULL;}else if(pa->data<0){pc->next=pa;pa=pa->next;pc=pc->next;pc->next=NULL;}}
}int main(){LinkList LA,LB,LC;if(LinkList(LA)){printf("LA初始化成功!\n");}else{printf("LA初始化失败!\n");}if(LinkList(LB)){printf("LB初始化成功!\n");}else{printf("LB初始化失败!\n");}if(LinkList(LC)){printf("LC初始化成功!\n");}else{printf("LC初始化失败!\n");}printf("请输入LA的长度:");int n1;scanf("%d",&n1);CreateList(LA,n1);TraveList(LA);Resolve(LA,LB,LC);TraveList(LB);TraveList(LC);return 0;
}

 

 

//修改一下，上面那个main方法里写的有问题，我们这里把初始化的InitList()方法用上，将新的链表LB和LC的初始化工作使用InitList()里进行：

 

#include<stdio.h>
#define MAX 100typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;int InitList(LinkList &L){L=new LNode;L->next=NULL;return 1;
} int ListLength(LinkList L){int length=0;struct LNode *p;p=L->next;while(p){++length;p=p->next;}return length;
}void TraveList(LinkList L){struct LNode *p;p=L->next;while(p){printf("%d ",p->data);p=p->next;}printf("\n");
}void CreateList(LinkList &L,int n){L=new LNode;L->next=NULL;struct LNode *p;p=L;for(int i=0;i<n;i++){struct LNode *s;s=new LNode;printf("请输入%d个结点的值:",i+1);scanf("%d",&s->data);s->next=NULL;p->next=s;p=s;}
}void Resolve(LinkList &LA,LinkList &LB,LinkList &LC){struct LNode *pa,*pb,*pc;pa=LA->next;//LB=new LNode;//LC=new LNode;//要生成两个新的头结点！！！ //LB=LC=LA;//不能这样写，这样写最后输出的LB和LChi一样的表，居然会一样？？为什么？？ pb=LB;pc=LC;while(pa){if(pa->data>0){pb->next=pa;pa=pa->next;pb=pb->next;pb->next=NULL;}else if(pa->data<0){pc->next=pa;pa=pa->next;pc=pc->next;pc->next=NULL;}}
}int main(){LinkList LA,LB,LC;if(InitList(LA)){printf("LA初始化成功!\n");}else{printf("LA初始化失败!\n");}if(InitList(LB)){printf("LB初始化成功!\n");}else{printf("LB初始化失败!\n");}if(InitList(LC)){printf("LC初始化成功!\n");}else{printf("LC初始化失败!\n");}printf("请输入LA的长度:");int n1;scanf("%d",&n1);CreateList(LA,n1);if(ListLength(LA)>0){printf("输出链表A:");}TraveList(LA);Resolve(LA,LB,LC);if(ListLength(LB)>0){printf("输出链表B:");} TraveList(LB);if(ListLength(LC)>0){printf("输出链表C:");} TraveList(LC);return 0;
}

 

 

 

这篇关于《数据结构》将一个带头结点的单链表分解成两个单链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---