双向链表的插入算法C

以下是双向链表的插入算法C语言实现：

// 在pos位置之前插入数据
void list_insert(list_t *list, list_node_t *pos, list_node_t *node) {
    if (list == NULL || node == NULL) {
        return;
    }
    if (pos == NULL) { // 如果pos为空，则插入到链表头部
        list_push_front(list, node);
        return;
    }
    if (pos == list->head) { // 如果pos为链表头部，则插入到链表头部
        list_push_front(list, node);
        return;
    }
    node->prev = pos->prev;
    node->next = pos;
    pos->prev->next = node;
    pos->prev = node;
    list->size++;
}

该算法的实现思路是：首先判断链表和节点是否为空，然后判断要插入的位置是否为链表头部，如果是，则直接调用list_push_front()函数插入到链表头部；否则，将要插入的节点的prev指针指向pos的前一个节点，将要插入的节点的next指针指向pos，pos的前一个节点的next指针指向要插入的节点，pos的prev指针指向要插入的节点，最后链表的size加1。

相关问题

用c语言写一个循环双链表插入算法

循环双链表插入算法的C语言实现如下：

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

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

// 定义循环双向链表结构体
typedef struct List {
    Node* head;
    Node* tail;
} List;

// 初始化循环双向链表
void initList(List* list) {
    list->head = NULL;
    list->tail = NULL;
}

// 创建新节点
Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 在链表尾部插入节点
void insertAtTail(List* list, int data) {
    Node* node = createNode(data);
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
        node->prev = node;
        node->next = node;
    } else {
        node->prev = list->tail;
        node->next = list->head;
        list->tail->next = node;
        list->head->prev = node;
        list->tail = node;
    }
}

// 在链表中间插入节点
void insertAtMiddle(List* list, int data, int position) {
    Node* node = createNode(data);
    Node* current = list->head;
    int i = 1;
    while (i < position && current != NULL) {
        current = current->next;
        i++;
    }
    if (current == NULL) {
        printf("Invalid position\n");
        return;
    }
    node->prev = current->prev;
    node->next = current;
    current->prev->next = node;
    current->prev = node;
}

// 打印链表
void printList(List* list) {
    Node* current = list->head;
    if (current == NULL) {
        printf("List is empty\n");
        return;
    }
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != list->head);
    printf("\n");
}

int main() {
    List list;
    initList(&list);
    insertAtTail(&list, 1);
    insertAtTail(&list, 2);
    insertAtTail(&list, 3);
    insertAtTail(&list, 4);
    insertAtMiddle(&list, 5, 3);
    printList(&list);
    return ;
}

该算法实现了循环双向链表的初始化、在链表尾部插入节点、在链表中间插入节点和打印链表等功能。其中，insertAtMiddle函数实现了在链表中间插入节点的功能，需要传入链表、要插入的数据和插入的位置三个参数。如果插入位置不合法，会输出"Invalid position"。最后，通过调用printList函数打印链表。

请用c语言写两种双向链表排序算法

当涉及到双向链表的排序算法时，常见的方法有插入排序和归并排序。以下是使用C语言实现这两种算法的示例代码。

1. 插入排序（Insertion Sort）：

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

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

void insert(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        if (current->next != NULL) {
            current->next->prev = newNode;
        }
        newNode->next = current->next;
        newNode->prev = current;
        current->next = newNode;
    }
}

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void freeList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current->next;
        free(current);
        current = temp;
    }
}

int main() {
    Node* head = NULL;

    insert(&head, 5);
    insert(&head, 3);
    insert(&head, 8);
    insert(&head, 1);
    insert(&head, 6);

    printf("Before sorting: ");
    printList(head);

    // 插入排序
    for (Node* i = head->next; i != NULL; i = i->next) {
        int key = i->data;
        Node* j = i->prev;
        while (j != NULL && j->data > key) {
            j->next->data = j->data;
            j = j->prev;
        }
        if (j == NULL) {
            head->data = key;
        } else {
            j->next->data = key;
        }
    }

    printf("After sorting: ");
    printList(head);

    freeList(head);

    return 0;
}

2. 归并排序（Merge Sort）：

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

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

Node* merge(Node* left, Node* right) {
    Node dummy;
    Node* tail = &dummy;

    while (left != NULL && right != NULL) {
        if (left->data <= right->data) {
            tail->next = left;
            left->prev = tail;
            left = left->next;
        } else {
            tail->next = right;
            right->prev = tail;
            right = right->next;
        }
        tail = tail->next;
        tail->prev = NULL;
    }

    if (left != NULL) {
        tail->next = left;
        left->prev = tail;
    } else {
        tail->next = right;
        right->prev = tail;
    }

    return dummy.next;
}

Node* mergeSort(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    Node* slow = head;
    Node* fast = head->next;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* right = slow->next;
    slow->next = NULL;

    Node* left = mergeSort(head);
    right = mergeSort(right);

    return merge(left, right);
}

void insert(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

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

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void freeList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current->next;
        free(current);
        current = temp;
    }
}

int main() {
    Node* head = NULL;

    insert(&head, 5);
    insert(&head, 3);
    insert(&head, 8);
    insert(&head, 1);
    insert(&head, 6);

    printf("Before sorting: ");
    printList(head);

    // 归并排序
    head = mergeSort(head);

    printf("After sorting: ");
    printList(head);

    freeList(head);

    return 0;
}

这两种算法都可以对双向链表进行排序，插入排序每次将一个元素插入到已排序的部分，而归并排序则将链表分割为较小的部分并进行合并。您可以根据需要选择适合您情况的算法。