当前位置：首页 > article >正文

对一个双向链表，从尾部遍历找到第一个值为x的点，将node p插入这个点之前，如果找不到，则插在末尾。使用C语言实现

article 2025/3/6 23:06:42

以下是一个用C语言实现的双向链表（Doubly Linked List）插入操作的代码。该代码从尾部遍历找到第一个值为x的节点，并在其前插入新节点p，或者在未找到时将其插入链表末尾。

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

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

// 创建新节点
DoublyListNode* createNode(int val) {
    DoublyListNode *newNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));
    newNode->val = val;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 在双向链表中插入新节点
DoublyListNode* insertBeforeXOrAppend(DoublyListNode *head, int x, int pVal) {
    if (head == NULL) {
        // 如果链表为空，直接创建新节点并返回
        return createNode(pVal);
    }

    DoublyListNode *curr = head;
    // 从头部开始遍历直到尾部
    while (curr->next != NULL) {
        curr = curr->next;
    }

    // 从尾部开始向前遍历找到第一个值为x的节点
    while (curr != NULL && curr->val != x) {
        curr = curr->prev;
    }

    // 如果找到了值为x的节点
    if (curr != NULL) {
        DoublyListNode *newNode = createNode(pVal);
        newNode->next = curr->next;
        newNode->prev = curr;
        if (curr->next != NULL) {
            curr->next->prev = newNode;
        }
        curr->next = newNode;
    } else {
        // 如果没有找到值为x的节点，则插入到末尾
        DoublyListNode *newNode = createNode(pVal);
        newNode->prev = curr; // curr此时为链表的最后一个节点或NULL（当链表为空时，但这种情况已在开头处理）
        if (curr != NULL) {
            curr->next = newNode;
        }
        // 如果链表原本为空，则newNode既是头节点也是尾节点，无需额外设置head
        // 否则，head不变，因为新节点是插入到末尾的，不影响头节点
    }

    // 注意：此函数不改变头节点的地址，因此无需返回新的头节点（除非链表原本为空）
    // 但为了保持接口的一致性，这里仍然返回头节点（尽管它可能没变）
    return head; // 在这个特定实现中，头节点要么不变，要么在函数外部已经处理（如链表为空时）
}

// 打印双向链表
void printList(DoublyListNode *head) {
    DoublyListNode *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

// 释放双向链表内存
void freeList(DoublyListNode *head) {
    DoublyListNode *curr = head;
    while (curr != NULL) {
        DoublyListNode *next = curr->next;
        free(curr);
        curr = next;
    }
}

int main() {
    // 创建双向链表 1 <-> 2 <-> 3 <-> 4
    DoublyListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = createNode(4);
    head->next->next->next->prev = head->next->next;

    int x = 3;
    int pVal = 99;

    // 插入新节点
    insertBeforeXOrAppend(head, x, pVal);

    // 打印双向链表
    printList(head);

    // 释放双向链表内存
    freeList(head);

    return 0;
}

注意：

上述代码中的insertBeforeXOrAppend函数实际上不需要返回新的头节点地址，因为插入操作要么在链表末尾进行（不改变头节点），要么在链表中间进行（同样不改变头节点）。但是，为了保持函数接口的一致性（比如，如果以后需要修改这个函数以处理链表为空时的特殊情况，并返回新的头节点），这里仍然返回了头节点。在实际应用中，如果确定头节点不会改变，可以省略返回值。
在main函数中，我们创建了一个简单的双向链表，并调用了insertBeforeXOrAppend函数来插入新节点。然后，我们打印链表并释放其内存。

带头链表：在链表的首部增加一个不存储有效数据的头节点。头节点的作用主要是简化链表的操作，特别是在处理空表时，无论表是否为空，头指针都指向头节点，从而使得空表和非空表的操作一致。
带头单向非循环链表：结构简单，但一般不会单独用来存储数据，而是作为其他数据结构的子结构，如哈希桶、图的邻接表等。
带头双向循环链表：结构最复杂，但一般用在单独存储数据的场景。实际中使用的链表数据结构，很多都是带头双向循环链表。虽然结构复杂，但使用代码实现后会发现，这种结构能带来很多优势。

查看全文

http://www.kler.cn/a/467301.html