概述
引言
C 语言中数组的缺陷:
- 静态空间, 一旦分配内存就不可以动态扩展
- 如果内存分配过多, 会造成资源浪费
- 对于头部插入/删除的效率低
什么是链表
链表是一种常用的数据结构, 它通过指针将一些数据节点, 连接成一个数据链. 相对于数组, 链表具有更好的动态性 (非顺序存储).
数据域用来存储数据, 指针域用于建立与下一个节点的联系.
建立链表时无需预先知道数据总量的. 可以随机的分配内存空间, 可以高效的在链表中任意位置实时插入或删除数据.
链表的组成
由节点组成
节点由数据域和指针域组成
- 数据域是用来维护数据的
- 指针域用来维护节点关系的
链表的分类
分类一
静态链表
在栈上分配内存
~ cat test.c #include <stdio.h> struct LinkNode { int num; // 数据域 struct LinkNode *next; // 指针域 }; void test() { // 创建节点 struct LinkNode node1 = {10, NULL}; struct LinkNode node2 = {20, NULL}; struct LinkNode node3 = {30, NULL}; struct LinkNode node4 = {40, NULL}; struct LinkNode node5 = {50, NULL}; // 建立关系 node1.next = &node2; node2.next = &node3; node3.next = &node4; node4.next = &node5; // 打印链表 struct LinkNode *pCurrent = &node1; while (pCurrent != NULL) { printf("%d\n", pCurrent -> num); pCurrent = pCurrent -> next; } } int main() { test(); return 0; }
~ gcc test.c -o test && ./test 10 20 30 40 50
动态链表
在堆区分配内存
~ cat test.c #include <stdio.h> #include <stdlib.h> struct LinkNode { int num; // 数据域 struct LinkNode *next; // 指针域 }; void test() { // 创建节点 struct LinkNode *node1 = malloc(sizeof(struct LinkNode)); struct LinkNode *node2 = malloc(sizeof(struct LinkNode)); struct LinkNode *node3 = malloc(sizeof(struct LinkNode)); struct LinkNode *node4 = malloc(sizeof(struct LinkNode)); struct LinkNode *node5 = malloc(sizeof(struct LinkNode)); // 给数据域赋值 node1 -> num = 100; node2 -> num = 200; node3 -> num = 300; node4 -> num = 400; node5 -> num = 500; // 建立关系 node1 -> next = node2; node2 -> next = node3; node3 -> next = node4; node4 -> next = node5; node5 -> next = NULL; // 打印链表 struct LinkNode *pCurrent = node1; while (pCurrent != NULL) { printf("%d\n", pCurrent -> num); pCurrent = pCurrent -> next; } // 释放内存 free(node1); free(node2); free(node3); free(node4); free(node5); node1 = NULL; node2 = NULL; node3 = NULL; node4 = NULL; node5 = NULL; } int main() { test(); return 0; }
~ gcc test.c -o test && ./test 100 200 300 400 500
分类二
单向链表
双向链表
单向循环链表
双向循环链表
分类三
带头链表
固定一个节点作为头节点 (数据域不保存有效数据), 起一个标志位的作用, 以后不管链表节点如何改变, 此头节点固定不变.
不带头链表
头节点不固定, 根据实际需要变换头节点 (如果在原来头节点前插入新节点, 然后新节点作为链表的头节点).
链表的基本操作
~ cat headers/linkList.h #pragma once #include <stdio.h> #include <string.h> #include <stdlib.h> struct LinkNode { int num; struct LinkNode *next; }; // 初始化链表 struct LinkNode *initLinkList(); // 遍历链表 void foreachLinkList(struct LinkNode *pHeader); // 插入链表 void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal); // 删除链表中某个节点 void deleteLinkList(struct LinkNode *pHeader, int val);
~ cat sources/linkList.c #include <linkList.h> // 初始化链表 struct LinkNode *initLinkList() { // 创建头节点 struct LinkNode *pHeader = malloc(sizeof(struct LinkNode)); if (pHeader == NULL) { return NULL; } // 初始化头节点 pHeader -> num = -1; pHeader -> next = NULL; // 记录尾节点位置, 方便插入新的数据 struct LinkNode *pTail = pHeader; int val = -1; while (1) { // 让用户初始化几个节点, 如果用户输入的是 -1, 代表结束 printf("请初始化链表, 如果输入 -1 代表结束\n"); scanf("%d", &val); if (val == -1) { break; } // 如果输入不是 -1, 插入节点到链表中 struct LinkNode *newNode = malloc(sizeof(struct LinkNode)); newNode -> num = val; newNode -> next = NULL; // 更改指针的指向 pTail -> next = newNode; // 更新新的尾节点的指向 pTail = newNode; } return pHeader; } // 遍历链表 void foreachLinkList(struct LinkNode *pHeader) { if (pHeader == NULL) { return; } struct LinkNode *curNode = pHeader -> next; // 指定第一个有真实数据的节点 while (curNode != NULL) { printf("%d\n", curNode -> num); curNode = curNode -> next; } } // 插入链表 void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal) { if (pHeader == NULL) { return; } // 创建两个临时节点 struct LinkNode *pPrev = pHeader; struct LinkNode *pCurrent = pHeader -> next; while (pCurrent != NULL) { if (pCurrent -> num == oldVal) { break; } // 如果没有找到对应的位置, 辅助指针向后移动 pPrev = pCurrent; pCurrent = pCurrent -> next; } // 创建新节点 struct LinkNode *newNode = malloc(sizeof(struct LinkNode)); newNode -> num = newVal; newNode -> next = NULL; // 建立关系 pPrev -> next = newNode; newNode -> next = pCurrent; } // 删除链表中某个节点 void deleteLinkList(struct LinkNode *pHeader, int val) { if (pHeader == NULL) { return; } // 创建两个临时节点 struct LinkNode *pPrev = pHeader; struct LinkNode *pCurrent = pHeader -> next; while (pCurrent != NULL) { if (pCurrent -> num == val) { break; } // 如果没有找到对应的位置, 辅助指针向后移动 pPrev = pCurrent; pCurrent = pCurrent -> next; } if (pCurrent == NULL) // 没有找到用户要删除的数据 { return; } // 更改指针指向进行删除 pPrev -> next = pCurrent -> next; free(pCurrent); pCurrent = NULL; }
~ cat sources/test.c
#include <linkList.h>
void test()
{
// 初始化链表
struct LinkNode *pHeader = initLinkList();
// 打印链表
printf("遍历链表结果为:\n");
foreachLinkList(pHeader);
// 插入链表
// 10 20 30 --> 10 1000 2000 20 30 500
insertLinkList(pHeader, 20, 1000);
insertLinkList(pHeader, 20, 2000);
insertLinkList(pHeader, -1, 500);
// 打印链表
printf("遍历链表结果为:\n");
foreachLinkList(pHeader);
// 删除链表
deleteLinkList(pHeader, 2000);
deleteLinkList(pHeader, 3000);
deleteLinkList(pHeader, 1000);
deleteLinkList(pHeader, -1);
// 打印链表
printf("遍历链表结果为:\n");
foreachLinkList(pHeader);
}
int main()
{
test();
return 0;
}
~ cd sources ~ gcc test.c linkList.c -I../headers -o test && ./test 请初始化链表, 如果输入 -1 代表结束 10 请初始化链表, 如果输入 -1 代表结束 20 请初始化链表, 如果输入 -1 代表结束 30 请初始化链表, 如果输入 -1 代表结束 -1 遍历链表结果为: 10 20 30 遍历链表结果为: 10 1000 2000 20 30 500 遍历链表结果为: 10 20 30 500
带头链表
初始化链表
// 初始化链表
struct LinkNode *initLinkList()
{
// 创建头节点
struct LinkNode *pHeader = malloc(sizeof(struct LinkNode));
if (pHeader == NULL)
{
return NULL;
}
// 初始化头节点
pHeader -> num = -1;
pHeader -> next = NULL;
// 记录尾节点位置, 方便插入新的数据
struct LinkNode *pTail = pHeader;
int val = -1;
while (1)
{
// 让用户初始化几个节点, 如果用户输入的是 -1, 代表结束
printf("请初始化链表, 如果输入 -1 代表结束\n");
scanf("%d", &val);
if (val == -1)
{
break;
}
// 如果输入不是 -1, 插入节点到链表中
struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
newNode -> num = val;
newNode -> next = NULL;
// 更改指针的指向
pTail -> next = newNode;
// 更新新的尾节点的指向
pTail = newNode;
}
return pHeader;
}
遍历链表
// 遍历链表
void foreachLinkList(struct LinkNode *pHeader)
{
if (pHeader == NULL)
{
return;
}
struct LinkNode *curNode = pHeader -> next; // 指定第一个有真实数据的节点
while (curNode != NULL)
{
printf("%d\n", curNode -> num);
curNode = curNode -> next;
}
}
插入链表
// 插入链表
void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal)
{
if (pHeader == NULL)
{
return;
}
// 创建两个临时节点
struct LinkNode *pPrev = pHeader;
struct LinkNode *pCurrent = pHeader -> next;
while (pCurrent != NULL)
{
if (pCurrent -> num == oldVal)
{
break;
}
// 如果没有找到对应的位置, 辅助指针向后移动
pPrev = pCurrent;
pCurrent = pCurrent -> next;
}
// 创建新节点
struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
newNode -> num = newVal;
newNode -> next = NULL;
// 建立关系
pPrev -> next = newNode;
newNode -> next = pCurrent;
}
删除链表中某个节点
// 删除链表中某个节点
void insertLinkList(struct LinkNode *pHeader, int val)
{
if (pHeader == NULL)
{
return;
}
// 创建两个临时节点
struct LinkNode *pPrev = pHeader;
struct LinkNode *pCurrent = pHeader -> next;
while (pCurrent != NULL)
{
if (pCurrent -> num == val)
{
break;
}
// 如果没有找到对应的位置, 辅助指针向后移动
pPrev = pCurrent;
pCurrent = pCurrent -> next;
}
if (pCurrent == NULL) // 没有找到用户要删除的数据
{
return;
}
// 更改指针指向进行删除
pPrev -> next = pCurrent -> next;
free(pCurrent);
pCurrent = NULL;
}
清空链表中所有节点
// 清空链表
void clearLinkList(struct LinkNode *pHeader)
{
if (pHeader == NULL)
{
return;
}
struct LinkNode *pCurrent = pHeader -> next;
while (pCurrent != NULL)
{
// 先保存下一个节点的位置
struct LinkNode *nextNode = pCurrent -> next;
free(pCurrent);
pCurrent = nextNode;
}
pHeader -> next = NULL;
}
销毁链表
// 销毁链表 void destroyLinkList(struct LinkNode *pHeader) { if (pHeader == NULL) { return; } struct LinkNode *pCurrent = pHeader -> next; while (pCurrent != NULL) { // 先保存下一个节点的位置 struct LinkNode *nextNode = pCurrent -> next; free(pCurrent); pCurrent = nextNode; } pHeader -> next = NULL; free(pHeader); pHeader = NULL; }