C语言实现线性表的链式存储实现 单链表的插入、删除、查找、求表长、置逆以及有序单链表的合并算法

链式存储的单链表是一种常见的数据结构，以下是C语言实现单链表的插入、删除、查找、求表长、置逆以及有序单链表的合并算法的示例代码：

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

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

// 在单链表中插入一个节点
void insertNode(Node** head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

// 从单链表中删除一个节点
void deleteNode(Node** head, int value) {
    Node* curr = *head;
    Node* prev = NULL;

    while (curr != NULL && curr->data != value) {
        prev = curr;
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("Node not found.\n");
        return;
    }

    if (prev == NULL) {
        *head = curr->next;
    } else {
        prev->next = curr->next;
    }

    free(curr);
}

// 在单链表中查找一个节点
Node* searchNode(Node* head, int value) {
    Node* curr = head;

    while (curr != NULL) {
        if (curr->data == value) {
            return curr;
        }
        curr = curr->next;
    }

    return NULL;
}

// 求单链表的长度
int getLength(Node* head) {
    int length = 0;
    Node* curr = head;

    while (curr != NULL) {
        length++;
        curr = curr->next;
    }

    return length;
}

// 将单链表置逆
void reverseList(Node** head) {
    Node* prev = NULL;
    Node* curr = *head;
    Node* next = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    *head = prev;
}

// 合并两个有序单链表
Node* mergeLists(Node* list1, Node* list2) {
    Node* mergedList = NULL;
    Node** tail = &mergedList;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data <= list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }

    if (list1 != NULL) {
        *tail = list1;
    } else {
        *tail = list2;
    }

    return mergedList;
}

// 打印单链表中的元素
void printList(Node* head) {
    Node* curr = head;

    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

// 析构单链表
void destroyList(Node** head) {
    Node* curr = *head;
    Node* next;

    while (curr != NULL) {
        next = curr->next;
        free(curr);
        curr = next;
    }

    *head = NULL;
}

int main() {
    Node* head = NULL;

    // 插入节点
    insertNode(&head, 3);
    insertNode(&head, 2);
    insertNode(&head, 1);

    // 打印链表
    printf("Linked List: ");
    printList(head);

    // 查找节点
    Node* node = searchNode(head, 2);
    if (node != NULL) {
        printf("Found node with value %d\n", node->data);
    } else {
        printf("Node not found.\n");
    }

    // 删除节点
    deleteNode(&head, 2);

    // 打印链表
    printf("Linked List after deletion: ");
    printList(head);

    // 求链表长度
    int length = getLength(head);
    printf("Length of Linked List: %d\n", length);

    // 置逆链表
    reverseList(&head);

    // 打印链表
    printf("Reversed Linked List: ");
    printList(head);

    // 析构链表
    destroyList(&head);

    return 0;
}