C语言之链表
1.知识百科
链表（Linked List）是计算机科学中一种基础的数据结构，通过节点（Node）的链式连接来存储数据。每个节点包含两部分：存储数据的元素和指向下一个节点的指针（单链表）或前后两个指针（双链表）。以下是关键知识点：
-
链表的核心特性
动态内存分配：节点在内存中分散存储，通过指针逻辑连接，无需预先分配固定空间（与数组不同）。
插入/删除高效：在已知位置插入或删除节点时，时间复杂度为 O(1)（但需先找到位置，查找时间为 O(n)）。
访问效率低：无法直接通过下标访问元素，需从头节点遍历，时间复杂度为 O(n)。 -
链表的类型
单链表：每个节点仅指向下一个节点；
双链表：每个节点指向前一个和后一个节点，需频繁双向遍历（如文本编辑器）。
循环链表 尾节点指向头节点，形成环； -
常见操作
插入：在头部、尾部或指定位置插入节点。
删除：删除指定节点（需处理指针指向）。
遍历：从头节点依次访问每个节点。
查找：按值或位置查找节点（需遍历）。 -
链表 vs 数组
2.C语言链表实现示例
如下图所示，创建一个学生信息管理链表，数据域包含有姓名、学号id和成绩，指针域用于保存下一个节点的地址。
2.1创建链表节点
1.定义结构体格式,保存学生信息。结果体中包含有指针域和数据域
typedef struct STU{
/*数据域*/
char name[50];
char id[20];
float score;
/*指针域*/
struct STU *next;//保存下一个成员的地址
}STU_INFO,*P_STU;
2.创建链表节点，用于保存成员信息。采用尾插法添加。
/*添加节点:尾插法*/
STU_INFO *STU_AddNode(STU_INFO *head)
{
STU_INFO *phead=head;
if(phead==NULL)//链表头不存在
{
phead=malloc(sizeof(STU_INFO));//动态分配空间
phead->next=NULL;//下一个成员指向NULL
STU_Input(phead);
return phead;//返回链表头
}
else //链表头存在
{
//1.偏移链表头，指向末尾位置
while(phead->next!=NULL)
{
phead=phead->next;
}
//2.创建新的节点
STU_INFO *new=malloc(sizeof(STU_INFO));
//关联节点
phead->next=new;
new->next=NULL;
phead=phead->next;
//3.赋值
STU_Input(new);
}
return head;//返回链表头
}
3.为节点信息赋值。从键盘上录入学生信息数据。
/*赋值*/
void STU_Input(STU_INFO *node)
{
if(node==NULL)return ;//地址为NULL
printf("请输入姓名、学号、成绩:\n");
scanf("%s%s%f",node->name,node->id,&node->score);
while(getchar()!='\n');//清空缓冲区
}
2.2 链表节点遍历
遍历链表节点，输出学生信息。
/*链表遍历*/
void STU_Output(STU_INFO *head)
{
STU_INFO *phead=head;
while(phead!=NULL)
{
printf("姓名:%s 学号:%s 成绩:%.1f\n",phead->name,phead->id,phead->score);
phead=phead->next;
}
}
2.3 链表测试
int main()
{
/*1.创建链表头*/
STU_INFO *head=NULL;
int i=0;
for(i=0;i<4;i++)
{
//创建链表头,添加节点
head=STU_AddNode(head);
}
//链表遍历
STU_Output(head);
}
运行效果：
wbyq@wbyq-virtual-machine:$ ./a.out
请输入姓名、学号、成绩:
小王 2025001 88
请输入姓名、学号、成绩:
小刘 2025002 99
请输入姓名、学号、成绩:
阿水 2025003 98
请输入姓名、学号、成绩:
小林 2025004 88
姓名:小王 学号:2025001 成绩:88.0
姓名:小刘 学号:2025002 成绩:99.0
姓名:阿水 学号:2025003 成绩:98.0
姓名:小林 学号:2025004 成绩:88.0
2.4 节点有序插入
在一个有序的链表中，插入一个新的节点，保证链表依然有序。代码实现如下，以学号为例。
/*有序链表插入：按从小到大顺序
*/
P_STU STU_InserNodeOrder(P_STU head)
{
if(!head){ //链表头位NULL
head=malloc(sizeof(STU_INFO));
head->next=NULL;
STU_Input(head);
return head;
}
//链表头不为NULL
P_STU new=malloc(sizeof(STU_INFO));//添加新的节点
STU_Input(new);//录入信息
P_STU phead=head;
P_STU temp=head;
while(phead!=NULL)
{
if(strcmp(phead->id,new->id)>0)//条件成立，则将该节点插入到当前节点前面
{
if(phead==head)//当前插入的节点则作为整个链表的头节点
{
//节点插入代码
/*
插入新的数据： 小王 2 99 <----头
链表头数据： 小李 5 88
按从小到大顺序
*/
new->next=phead;
head=new;
return head;
}
else
{
/*
链表头数据： 小王 5 88
节点1： 小李 8 99
插入的新节点：小陈 9 99 <----中间位置
节点2 ： 小刘 10 66
*/
temp->next=new;
new->next=phead;
return head;
}
}
temp=phead;
phead=phead->next;//偏移到下一个节点
}
/*
情况3：
链表头数据： 小王 5 88
节点1： 小李 8 99
节点2 ： 小陈 10 66
插入的新节点：小刘 11 66 <---尾插法
*/
temp->next=new;
new->next=NULL;
return head;
}
有序插入测试示例：
int main()
{
P_STU head=NULL;//定义一个结构体指针
int i=0;
//添加节点
while(1)
{
head=STU_InserNodeOrder(head);
STU_Output(head);
}
return 0;
}
运行效果：
wbyq@wbyq-virtual-machine:/mnt/hgfs/ubuntu/c_progma$ ./a.out
请输入姓名、学号、成绩:
小王 005 88
姓名:小王 学号:005 成绩:88.0
请输入姓名、学号、成绩:
小红 002 89
姓名:小红 学号:002 成绩:89.0
姓名:小王 学号:005 成绩:88.0
请输入姓名、学号、成绩:
小陈 003 99
姓名:小红 学号:002 成绩:89.0
姓名:小陈 学号:003 成绩:99.0
姓名:小王 学号:005 成绩:88.0
请输入姓名、学号、成绩:
小林 001 100
姓名:小林 学号:001 成绩:100.0
姓名:小红 学号:002 成绩:89.0
姓名:小陈 学号:003 成绩:99.0
姓名:小王 学号:005 成绩:88.0
请输入姓名、学号、成绩:
2.5 清空链表
//清空链表
P_STU STU_NodeClear(P_STU head)
{
if(head==NULL)return head;
P_STU phead=head;
P_STU temp;
#if 0
//链表头存在(从第一个子节点开始删除)
while(phead->next!=NULL)
{
temp=phead->next;//保存当前要删除的地址
printf("释放节点:%p\n",temp);
phead->next=temp->next;
free(temp);//释时节点
}
printf("释放链表头:%p\n",phead);
//释放phead
free(phead);
return NULL;
#endif
//从链表头开始释放
while(phead!=NULL)
{
temp=phead;//保存要删除的节点
phead=phead->next;//保存下一个节点地址
free(temp);
}
return NULL;
}