将一个带头结点的单链表分解成两个单链表
题目描述:
/*
设计一个算法,将一个带头结点的单链表分解成两个具有相同结构的
链表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,*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 100 typedef 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,*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,LC); TraveList(LB); TraveList(LC); return 0; }