第1章第2节练习题8 奇偶拆分单链表
最后更新于：2022-04-01 19:50:53
## 问题描述
> 将一个带头结点的单链表分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有元表中序号为偶数的元素，且保持其相对顺序不变。
## 算法思想
> 因为本题中涉及到到按序号拆分单链表的操作，因此我们对单链表的定义进行一次修改，加入序号元素num，这样只需要对num元素判断奇偶便可。因为题目中需要拆分成两个不同的链表，因此这里创建了两个空的单链表，头节点分别为head1，head2。用指针p对原来的单链表进行一次遍历，如果结点的num域为偶数，则将该结点拆下，为了让其相对顺序不发生变化，采用尾插法将该结点插入到第二个单链表中，这样以来，便成功的将一个链表拆分称为两张链表，head1表中存放的是原表中序号为奇数的元素，而head2表中含有元表中序号为偶数的元素。
## 算法描述
~~~
//单链表定义
typedef int ElemType;
typedef struct LNode{
ElemType data;
int num;
struct LNode *next;
}LNode, *LinkList;
/*------------------------------------------------------*/
//拆分单链表
LinkList SeparateList(LNode *head1)
{
LNode *head2;
head2=(LNode*)malloc(sizeof(LNode));
LNode *r=head2;
LNode *pre=head1;
LNode *p=pre->next;
while(p){
if(p->num%2){
pre=p;
p=p->next;
}else{
pre->next=p->next;
r->next=p;
r=p;
p=pre->next;
}
}
r->next=NULL;
return head2;
}
~~~
具体代码见附件。
## 附件
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
int num;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
LinkList SeparateList(LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head1;
head1=(LNode*)malloc(sizeof(LNode));
head1->next=NULL;
head1=CreatList(head1);
printf("head :");
Print(head1);
LNode *head2;
head2=SeparateList(head1);
printf("head1:");
Print(head1);
printf("head2:");
Print(head2);
return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode* head)
{
int cnt=1;
LNode *r=head;
LNode *s;
ElemType x;
scanf("%d",&x);
while(x!=999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->num=cnt++;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return head;
}
//拆分单链表
LinkList SeparateList(LNode *head1)
{
LNode *head2;
head2=(LNode*)malloc(sizeof(LNode));
LNode *r=head2;
LNode *pre=head1;
LNode *p=pre->next;
while(p){
if(p->num%2){
pre=p;
p=p->next;
}else{
pre->next=p->next;
r->next=p;
r=p;
p=pre->next;
}
}
r->next=NULL;
return head2;
}
//打印全部结点
void Print(LNode* head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
';