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

C链表的一些基础知识

news 2025/7/19 23:32:36

一、链表的基本概念

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

二、单链表的实现

定义节点结构体：

// 定义单链表节点结构体
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 指针指向头节点，构成双向循环结构。其操作函数在处理边界情况和指针修改时要考虑这种循环特性，比如插入节点时要正确更新节点间的双向指针关系。