数据结构实验之链表五:单链表的拆分

3/8/2017来源:ASP.NET技巧人气:1395

*点击获取原题链接

数据结构实验之链表五:单链表的拆分 Time Limit: 1000MS Memory Limit: 65536KB PRoblem Description 输入N个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。 Input 第一行输入整数N;; 第二行依次输入N个整数。 Output 第一行分别输出偶数链表与奇数链表的元素个数; 第二行依次输出偶数子链表的所有数据; 第三行依次输出奇数子链表的所有数据。 Example Input

10 1 3 22 8 15 999 9 44 6 1001

Example Output

4 6 22 8 44 6 1 3 15 999 9 1001

Hint 不得使用数组! Author

///

个人觉得做链表一定要耐心 耐心的找BUG

#include <string.h> #include <stdio.h> #include <stdlib.h> struct node { int data;///链表数据域 struct node *next;///链表指针域 }; int m,n;/// 储存两个链表的个数 struct node *creat(int n)///顺序建立链表 { struct node *head=NULL,*tail,*p; head=(struct node *)malloc(sizeof(struct node ));///为头结点分配内存 tail=head; for(int i=1;i<=n;i++) { p=(struct node *)malloc(sizeof(struct node ));///新节点 scanf("%d",&p->data); p->next=NULL; tail->next=p; tail=p; } return head; }; void output(struct node *head)/// 遍历链表 { struct node *p=head->next; while(p) { printf("%d%c",p->data,p->next==NULL?'\n':' '); p=p->next; } } void change(struct node *head,struct node *head1,struct node *head2) { head1->next=NULL; head2->next=NULL; struct node *t;///对应原链表 struct node *p,*q;///两个游动指针 t=head->next;///用t来遍历原链表 p=head1; q=head2; head1->next=NULL; head2->next=NULL; while(t) { if(t->data%2==0)/// 如果是偶数则加在head1的后面 { n++;/// 偶数数量加一 p->next=t; p=t; t=t->next; p->next=NULL; } else ///奇数 { m++; q->next=t; q=t; t=t->next; q->next=NULL; } } } int main() { scanf("%d",&n); struct node *head=creat(n);///顺序简练表 struct node *head1=NULL,*head2=NULL;/// 建立两个分链表的头结点 /********两个分链表的头结点分配内存******/ head1=(struct node *)malloc(sizeof(struct node )); head2=(struct node *)malloc(sizeof(struct node )); m=0; n=0;/// m奇数n 偶数 change(head,head1,head2);///拆分单链表 printf("%d %d\n",n,m);/// 输出 奇数和偶数的个数 output(head1);/// 遍历分开的链表 output(head2); return 0; }