C语言线性表的应用算法：两个链表合并一个递减链表

题目描述

C语言线性表的应用算法:构造一个递增有序的正整数链表，实现链表分解为 一个奇数表和一个偶数表，之后再将两个链表合井一个递减链表。

源代码

下面是一个C语言实现的例子，可以构造一个递增有序的正整数链表，并将其分解为一个奇数表和一个偶数表，然后再将两个链表合并为一个递减链表：

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

// 定义链表节点结构体
typedef struct ListNode* PtrToNode;
struct ListNode {
    int data;
    PtrToNode next;
};

// 创建新节点
PtrToNode NewNode(int data)
{
    PtrToNode p = (PtrToNode)malloc(sizeof(struct ListNode));
    p->data = data;
    p->next = NULL;
    return p;
}

// 插入新节点到递增有序链表
void InsertNode(PtrToNode* head, int data)
{
    PtrToNode p = NewNode(data);
    if (*head == NULL || data < (*head)->data) {
        p->next = *head;
        *head = p;
    } else {
        PtrToNode q = *head;
        while (q->next != NULL && data > q->next->data) {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
    }
}

// 分解链表为奇数表和偶数表
void SplitList(PtrToNode head, PtrToNode* oddHead, PtrToNode* evenHead)
{
    PtrToNode p = head;
    PtrToNode oddTail = NULL;
    PtrToNode evenTail = NULL;
    while (p != NULL) {
        if (p->data % 2 == 1) { // 奇数节点
            if (*oddHead == NULL) {
                *oddHead = p;
                oddTail = p;
            } else {
                oddTail->next = p;
                oddTail = p;
            }
        } else { // 偶数节点
            if (*evenHead == NULL) {
                *evenHead = p;
                evenTail = p;
            } else {
                evenTail->next = p;
                evenTail = p;
            }
        }
        p = p->next;
    }
    if (oddTail != NULL) {
        oddTail->next = NULL;
    }
    if (evenTail != NULL) {
        evenTail->next = NULL;
    }
}

// 合并两个链表为递减链表
PtrToNode MergeLists(PtrToNode list1, PtrToNode list2)
{
    PtrToNode head = NULL;
    PtrToNode p = NULL;
    while (list1 != NULL && list2 != NULL) {
        if (list1->data >= list2->data) {
            if (head == NULL) {
                head = list1;
                p = list1;
            } else {
                p->next = list1;
                p = list1;
            }
            list1 = list1->next;
        } else {
            if (head == NULL) {
                head = list2;
                p = list2;
            } else {
                p->next = list2;
                p = list2;
            }
            list2 = list2->next;
        }
    }
    if (list1 != NULL) {
        p->next = list1;
    }
    if (list2 != NULL) {
        p->next = list2;
    }
    return head;
}

// 打印链表
void PrintList(PtrToNode head)
{
    PtrToNode p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 释放链表内存
void FreeList(PtrToNode head)
{
    PtrToNode p = head;
    while (p != NULL) {
        PtrToNode q = p;
        p = p->next;
        free(q);
    }
}

int main()
{
    PtrToNode list = NULL;
    PtrToNode oddList = NULL;
    PtrToNode evenList = NULL;
    PtrToNode mergedList = NULL;

    // 构造递增有序链表
    InsertNode(&list, 1);
    InsertNode(&list, 3);
    InsertNode(&list, 5);
    InsertNode(&list, 2);
    InsertNode(&list, 4);
    InsertNode(&list, 6);

    // 分解链表为奇数表和偶数表
    SplitList(list, &oddList, &evenList);

    // 合并两个链表为递减链表
    mergedList = MergeLists(oddList, evenList);

    // 打印结果
    printf("Original List: ");
    PrintList(list);
    printf("Odd List: ");
    PrintList(oddList);
    printf("Even List: ");
    PrintList(evenList);
    printf("Merged List: ");
    PrintList(mergedList);

    // 释放内存
    FreeList(list);
    FreeList(oddList);
    FreeList(evenList);
    FreeList(mergedList);

    return 0;
}

在这个程序中，我们首先定义了一个链表节点的结构体ListNode，每个节点包含一个整数数据data和一个指向下一个节点的指针next。

然后，我们定义了一系列函数来操作链表。

在NewNode()函数中，我们创建一个新节点，并将给定的数据设置为节点的数据，然后将节点的next指针设置为NULL。

在InsertNode()函数中，我们将一个新节点插入到递增有序链表中。具体来说，我们首先判断链表是否为空或者新节点的数据是否小于链表的头节点的数据。如果是，则将新节点作为链表的新头节点；否则，我们遍历链表，找到第一个大于新节点数据的节点，然后将新节点插入到该节点之前。

在SplitList()函数中，我们将链表分解为奇数表和偶数表。具体来说，我们遍历链表的每个节点，如果节点的数据是奇数，则将其插入到奇数表中；如果节点的数据是偶数，则将其插入到偶数表中。

在MergeLists()函数中，我们合并两个链表为一个递减链表。具体来说，我们使用两个指针分别指向两个链表的头节点，然后逐个比较它们的节点数据。如果第一个链表的节点数据大于等于第二个链表的节点数据，则将第一个链表的节点插入到结果链表中；否则，将第二个链表的节点插入到结果链表中。最后，我们将剩余的节点插入到结果链表中。

在PrintList()函数中，我们遍历链表并打印每个节点的数据。

在FreeList()函数中，我们释放链表的内存。具体来说，我们遍历链表，依次释放每个节点的内存。

在main()函数中，我们首先构造一个递增有序链表。然后，我们调用SplitList()函数将链表分解为奇数表和偶数表。接下来，我们调用MergeLists()函数合并两个链表为一个递减链表。最后，我们打印结果链表，并释放所有链表的内存。