单链表按奇、偶数拆分

lixiangrong
2024-01-29 / 0 评论 / 38 阅读 / 正在检测是否收录...

单链表按奇、偶数拆分

将一个结点值为自然数的单链表拆分成两个单链表,原表为偶数结点值为奇数的结点按原表相对次序组成新链表

#include <stdio.h>
#include <stdlib.h>

typedef int dataType;

typedef struct linkNode
{
    dataType data;
    struct linkNode *next;
}node,*linkList;

// 1.初始化不带头结点的单链表
void init(linkList *head)
{
    *head = NULL;
}

// 2.输出单链表元素
void display(linkList list)
{
    node *p = list; // p为工作指针,初值为头指针
    if(!p)
    {
        printf("链表为空!\n");
        return;
    }
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}

// 3.根据用户输入构造单链表
void scanInsert(linkList *head)
{
    node *p,*q;
    dataType x;
    printf("请输入(以9999作为结束标识)...\n");
    scanf("%d",&x);
    while (x!=9999)
    {
        q = (node*) malloc(sizeof(node));
        q->data = x;
        q->next = NULL;
        if(!*head) // 创建第一个结点时
        {
            *head = q;
            p = *head;
        }
        else
        {
            p->next = q;
            p = p->next;
        }
        scanf("%d",&x);
    }
}

// 3.8.7 将一个结点值为自然数的单链表拆分成两个单链表,原表为偶数结点
// 值为奇数的结点按原表相对次序组成新链表
void split(linkList *head, linkList *oddList)
{
    // p为当前链表工作指针,p为奇数链表工作指针,pre为当前链表前驱指针
    node *p = *head,*q,*pre;
    while (p)
    {
        if(p->data%2 == 1) // 如果是奇数
        {
           if(p == *head) // 如果当前结点是头结点
           {
               *head = p->next; // 更新原链表头结点
               if(!*oddList) // 如果奇数链表为空
                   *oddList = q = p; // 更新奇数链表头指针和工作指针
               else
               {
                   q->next = p;
                   q = p; // 更新奇数链表工作指针
               }
           } else
           {
               pre->next = p->next; // 逻辑删除当前结点
               if(!*oddList) // 如果奇数链表为空
                   *oddList = q =  p; // 更新奇数链表
               else
               {
                   q->next = p;
                   q = p;
               }
           }
           p = p->next; // 向后遍历
           q->next = NULL; // 奇数链表结束标识
        } else // 如果是偶数
        {
            pre  = p; // 保存前驱指针
            p = p->next;
        }
    }
}

int main()
{
    linkList list,oddList;
    init(&list);
    init(&oddList);
    scanInsert(&list);
    split(&list,&oddList);
    display(list);
    printf("\n");
    display(oddList);
    return 0;
}
0

评论 (0)

取消