C语言链表操作：合并、拆分与素数判断

C语言链表操作：合并、拆分与素数判断

本文介绍如何使用C语言进行链表的合并和拆分操作，并结合素数判断演示链表的应用。

1. 链表的合并

以下代码将输入的链表复制并扩展为两倍大小，形成一个前后对称的链表：

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

struct Node {
    int data;
    struct Node* next;
};

// 合并线性表，将链表扩大成2倍大小，变成前后对称的链表
struct Node* mergeLinkedList(struct Node* head) {
    struct Node* current = head;
    struct Node* newHead = NULL;
    struct Node* newTail = NULL;

    while (current != NULL) {
        // 创建新节点1
        struct Node* newNode1 = (struct Node*)malloc(sizeof(struct Node));
        newNode1->data = current->data;
        newNode1->next = NULL;

        // 创建新节点2
        struct Node* newNode2 = (struct Node*)malloc(sizeof(struct Node));
        newNode2->data = current->data;
        newNode2->next = NULL;

        // 将新节点1插入到新链表的末尾
        if (newHead == NULL) {
            newHead = newNode1;
            newTail = newNode1;
        } else {
            newTail->next = newNode1;
            newTail = newNode1;
        }

        // 将新节点2插入到新链表的头部
        newNode2->next = newHead;
        newHead = newNode2;

        current = current->next;
    }

    return newHead;
}

2. 链表的拆分

以下代码将输入的链表根据元素是否为素数拆分为两个链表：

#include <math.h>

// 判断一个数是否是素数
int isPrime(int num) {
    if (num < 2) {
        return 0;
    }

    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return 0;
        }
    }

    return 1;
}

// 拆分线性表，将链表中的整数按照是否是素数拆成两个链表
void splitLinkedList(struct Node* head, struct Node** primeList, struct Node** nonPrimeList) {
    struct Node* current = head;
    struct Node* primeHead = NULL;
    struct Node* primeTail = NULL;
    struct Node* nonPrimeHead = NULL;
    struct Node* nonPrimeTail = NULL;

    while (current != NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = current->data;
        newNode->next = NULL;

        if (isPrime(current->data)) {
            // 插入到素数链表
            if (primeHead == NULL) {
                primeHead = newNode;
                primeTail = newNode;
            } else {
                primeTail->next = newNode;
                primeTail = newNode;
            }
        } else {
            // 插入到非素数链表
            if (nonPrimeHead == NULL) {
                nonPrimeHead = newNode;
                nonPrimeTail = newNode;
            } else {
                nonPrimeTail->next = newNode;
                nonPrimeTail = newNode;
            }
        }

        current = current->next;
    }

    *primeList = primeHead;
    *nonPrimeList = nonPrimeHead;
}

3. 完整代码示例

// ... (以上代码)

// 打印链表元素
void printLinkedList(struct Node* head) {
    while (head != NULL) {
        printf('%d ', head->data);
        head = head->next;
    }
    printf('
');
}

// 释放链表节点的内存
void freeLinkedList(struct Node* head) {
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    struct Node* head = NULL;
    struct Node* primeList = NULL;
    struct Node* nonPrimeList = NULL;

    // 输入链表元素
    int n, num;
    printf('请输入链表的长度：');
    scanf('%d', &n);

    printf('请输入整型元素序列：');
    for (int i = 0; i < n; i++) {
        scanf('%d', &num);

        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = num;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
        } else {
            struct Node* current = head;
            while (current->next != NULL) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 合并线性表
    struct Node* mergedList = mergeLinkedList(head);
    printf('合并后的链表：');
    printLinkedList(mergedList);

    // 拆分线性表
    splitLinkedList(head, &primeList, &nonPrimeList);
    printf('素数链表：');
    printLinkedList(primeList);
    printf('非素数链表：');
    printLinkedList(nonPrimeList);

    // 释放内存
    freeLinkedList(head);
    freeLinkedList(mergedList);
    freeLinkedList(primeList);
    freeLinkedList(nonPrimeList);

    return 0;
}

这段代码演示了如何创建、合并和拆分链表，并结合素数判断展示了链表的实际应用。 通过学习这段代码，您可以更好地理解链表数据结构以及如何在C语言中使用链表。