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

C链表的一些基础知识

article 2025/1/21 23:19:59

一、链表的基本概念

链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（单链表情况）。通过指针将各个节点连接起来，与数组不同，链表在内存中的存储不是连续的，其优点是可以灵活地进行插入、删除操作，无需像数组那样移动大量元素。

二、单链表的实现

定义节点结构体：

// 定义单链表节点结构体
typedef struct ListNode {
    int data;  // 数据域，这里以整型数据为例，可根据需求修改类型
    struct ListNode *next;  // 指针域，指向下一个节点
} ListNode;

创建链表节点函数：

// 创建一个新的链表节点
ListNode *createNode(int value) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

插入节点（尾插法为例）：

// 尾插法向链表插入节点
void insertTail(ListNode **head, int value) {
    ListNode *newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        ListNode *temp = *head;
        while (temp->next!= NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

遍历链表函数：

// 遍历链表并输出节点数据
void traverseList(ListNode *head) {
    ListNode *current = head;
    while (current!= NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

释放链表内存函数：

// 释放链表占用的内存
void freeList(ListNode *head) {
    ListNode *current = head;
    ListNode *next;
    while (current!= NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

三、双链表的实现

定义双链表节点结构体：

// 定义双链表节点结构体
typedef struct DoublyListNode {
    int data;
    struct DoublyListNode *prev;  // 指向前一个节点的指针
    struct DoublyListNode *next;  // 指向后一个节点的指针
} DoublyListNode;

创建双链表节点函数：

// 创建双链表节点
DoublyListNode *createDoublyNode(int value) {
    DoublyListNode *newNode = (DoublyListNode *)malloc(sizeof(DoublyListNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

插入节点（尾插法为例）：

// 尾插法向双链表插入节点
void insertTailDoubly(DoublyListNode **head, int value) {
    DoublyListNode *newNode = createDoublyNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        DoublyListNode *temp = *head;
        while (temp->next!= NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

遍历双链表（正向）函数：

// 正向遍历双链表并输出节点数据
void traverseDoublyListForward(DoublyListNode *head) {
    DoublyListNode *current = head;
    while (current!= NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

遍历双链表（反向）函数：

// 反向遍历双链表并输出节点数据
void traverseDoublyListBackward(DoublyListNode *head) {
    DoublyListNode *current = head;
    if (current == NULL) return;
    while (current->next!= NULL) {
        current = current->next;
    }
    while (current!= NULL) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

释放双链表内存函数：

// 释放双链表占用的内存
void freeDoublyList(DoublyListNode *head) {
    DoublyListNode *current = head;
    DoublyListNode *next;
    while (current!= NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

四、循环链表

循环单链表：
循环单链表与普通单链表的区别在于，其最后一个节点的指针不是指向 NULL，而是指向链表的头节点，形成一个环形结构。在实现插入、遍历等操作时，需要注意循环的终止条件有所不同，例如遍历循环单链表时，判断节点是否回到头节点来结束循环。
循环双链表：
循环双链表中，头节点的 prev 指针指向尾节点，尾节点的 next 指针指向头节点，构成双向循环结构。其操作函数在处理边界情况和指针修改时要考虑这种循环特性，比如插入节点时要正确更新节点间的双向指针关系。