第1章第2节练习题8 奇偶拆分单链表

问题描述

将一个带头结点的单链表分解为两个带头结点的单链表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<stdio.h>
#include<stdlib.h>

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("
");
}