1. 链表（linklist）
链表：数据之间呈现线性关系，且在内存上非连续存储（链式存储）
链表由节点构成：节点 = 数据域(data) + 指针域(next)
多个节点通过指针域串连形成链表
链表分有头链表和无头链表，有头链表实现功能更便捷，本文介绍有头链表的使用
以Linux系统的多文件操作为基础：linklist.h、linklist.c、main.c
2. 链表的附属功能函数
包括创建、回收、判空、判满、清空、显示链表、求链表长度。
（1）linklist.h
在头文件linklist.h中，做重命名数据类型、创建链表节点结构体、附属功能函数定义等功能。
#ifndef _linklist_h_
#define _linklist_h_
#include
#include
#include
//重命名数据类型
typedef int data_t;
//定义节点结构体
typedef struct node
{
data_t data; //数据域
struct node *next; //指针域（指向节点的指针）
} node;
//创建链表
node * linklist_create();
//判空
int linklist_empty(node *head);
//判满
int linklist_full(node *head);
//清空链表
void linklist_clear(node *head);
//回收链表
void linklist_destroy(node **head);
//显示链表所有元素
void linklist_display(node *head);
//求链表长度
int linklist_length(node *head);
（2）linklist.c
在linklist.c文件中封装函数功能。
#include "linklist.h"
//创建链表
node * linklist_create()
{
//为头节点开辟空间
node *head = (node *)malloc(sizeof(node));
if (NULL == head){
printf("malloc failed!\n");
return NULL;
}
//给开辟的空间填充0
memset(head, 0, sizeof(node));
//初始化头节点的指针域
head->next = NULL;
//返回头节点
return head;
}
//判空
int linklist_empty(node *head)
{
return (NULL == head->next) ? 1 : 0;
}
//判满（一般不会满）
int linklist_full(node *head)
{
return 0;
}
//清空链表
void linklist_clear(node *head)
{
node *p = head->next;
node *q = NULL;
while(p)
{
q = p->next; //先记录下一个节点的地址
free(p); //再删除这个节点
p = q; //去到下一个节点
}
head->next = NULL; //最后回到初始状态
}
//回收链表
void linklist_destroy(node **head)
{
linklist_clear(*head); //清空链表
free(*head); //释放头节点
*head = NULL;
}
//显示链表所有元素
void linklist_display(node *head)
{
node *p = head->next;
while(p)
{
printf("%-3d", p->data);
p = p->next;
}
puts("");
}
//求链表长度
int linklist_length(node *head)
{
node *p = head->next;
int len = 0; //链表的有效长度
while (p)
{
len++;
p = p->next;
}
return len;
}
3. 链表 的“ 增删改查 ”
（1）linklist.h
在头文件中进行函数声明。
//按位置插入数据
int linklist_pos_insert(node *head, int pos, data_t data);
//按位置删除数据
int linklist_pos_delete(node *head, int pos);
//按数据删除元素
int linklist_data_delete(node *head, data_t data);
//按位置修改数据
int linklist_pos_update(node *head, int pos, data_t data);
//按数据修改数据
int linklist_data_update(node *head, data_t old_data, data_t new_data);
//按位置查找数据
data_t linklist_pos_search(node *head, int pos);
//按数据查找位置
int linklist_data_search(node *head, data_t data);
（2）linklist.c
封装 “ 增删改查 ” 函数功能。
//按位置插入数据
int linklist_pos_insert(node *head, int pos, data_t data)
{
//判断pos是否有效
int len = linklist_length(head);
if (pos < 0 || pos > len)
{
printf("Insert pos is invalid!\n");
return -1;
}
//把data包装成节点q
node *q = (node *)malloc(sizeof(node));
if (NULL == q){
printf("malloc failed!\n");
return -1;
}
memset(q, 0, sizeof(node));
q->data =data;
//找到插入位置的前一个节点
node *p = head;
for (int i = 0; i < pos; i++)
p = p->next;
//先连接后一个节点，再连接前一个节点
q->next = p->next;
p->next = q;
return 0;
}
//按位置删除数据
int linklist_pos_delete(node *head, int pos)
{
//判断pos是否有效
int len = linklist_length(head);
if (pos < 0 || pos >= len)
{
printf("Delete pos is invalid!\n");
return -1;
}
//找pos对应节点的前一个节点
node *p = head;
for(int i = 0; i < pos; i++)
{
p = p->next;
}
//先连接后一个节点和前一个节点，再断开与后一个节点的连接
node *q = p->next;
p->next = q->next;
free(q); //节点都是malloc出来的，所以可以直接free
return 0;
}
//按数据删除元素
int linklist_data_delete(node *head, data_t data)
{
//判空
if (linklist_empty(head) == 1)
{
printf("Linklist is empty!\n");
return -1;
}
//找data对应的位置
node *p = head->next;
int len = linklist_length(head);
for(int i = 0; i < len; i++)
{
if(p->data == data)
{
//找到位置后，直接调用按位置删除元素函数
linklist_pos_delete(head, i);
return 0;
}
else
p = p->next;
}
return 0;
}
//按位置修改数据
int linklist_pos_update(node *head, int pos, data_t data)
{
//判断pos是否有效
int len = linklist_length(head);
if (pos < 0 || pos >= len)
{
printf("Search pos is invalid!\n");
return (data_t)-1;
}
//找data对应的位置
node *p = head->next;
for(int i = 0; i < pos; i++)
{
p = p->next;
}
//给节点赋新值
p->data = data;
return 0;
}
//按数据修改数据
int linklist_data_update (node *head, data_t old_data, data_t new_data)
{
//判空
if (linklist_empty(head) == 1)
{
printf("Linklist is empty!\n");
return -1;
}
//找data对应的位置并修改数据
node *p = head->next;
int len = linklist_length(head);
for(int i = 0; i < len; i++)
{
if(old_data == p->data)
{
p->data = new_data;
return 0;
}
else
p = p->next;
}
return 0;
}
//按位置查找数据
data_t linklist_pos_search(node *head, int pos)
{
//判断pos是否有效
int len = linklist_length(head);
if (pos < 0 || pos >= len)
{
printf("Search pos is invalid!\n");
return (data_t)-1;
}
//找pos对应的元素
node *p = head->next;
for(int i = 0; i < pos; i++)
{
p = p->next;
}
return p->data;
}
//按数据查找位置
int linklist_data_search(node *head, data_t data)
{
//判空
if (linklist_empty(head) == 1)
{
printf("Linklist is empty!\n");
return -1;
}
//找data对应的位置
node *p = head->next;
for(int i = 0; i < linklist_length(head); i++)
{
if(data == p->data)
return i;
p = p->next;
}
}
（3）main.c
1）在主函数中简单验证 “ 增删改查 ” 的函数功能。
#include "linklist.h"
int main(int argc, char *argv[])
{
//创建链表
node *head = linklist_create ();
if (head == NULL)
{
printf("malloc failed!\n");
return -1;
}
//插入10个数
printf("插入十个数：\n");
int i = 11;
while (--i)
{
linklist_pos_insert(head, 0, i);
}
linklist_display(head);
//按位置插入数据
printf("在位置标号2上插入数据7.\n");
linklist_pos_insert (head, 2, 7);
linklist_display (head);
//按位置查找数据
printf("在位置标号4上的数据为：%d\n",linklist_pos_search (head, 4));
linklist_display (head);
//按数据查找位置
printf("数据1的位置标号为：%d\n",linklist_data_search (head, 1));
linklist_display (head);
//按位置删除数据
printf("删除位置标号6上的数据.\n");
linklist_pos_delete (head, 6);
linklist_display (head);
//按数据删除数据
printf("删除数据10.\n");
linklist_data_delete (head, 10);
linklist_display (head);
//按位置修改数据
printf("修改位置标号为5的数据为9.\n");
linklist_pos_update (head, 5, 9);
linklist_display (head);
//按数据修改数据
printf("修改数据1为0.\n");
linklist_data_update (head, 1, 0);
linklist_display (head);
//销毁链表
linklist_destroy(&head);
return 0;
}
2）运行结果展示
插入十个数：
1 2 3 4 5 6 7 8 9 10
在位置标号2上插入数据7.
1 2 7 3 4 5 6 7 8 9 10
在位置标号4上的数据为：4
1 2 7 3 4 5 6 7 8 9 10
数据1的位置标号为：0
1 2 7 3 4 5 6 7 8 9 10
删除位置标号6上的数据.
1 2 7 3 4 5 7 8 9 10
删除数据10.
1 2 7 3 4 5 7 8 9
修改位置标号为5的数据为9.
1 2 7 3 4 9 7 8 9
修改数据1为0.
0 2 7 3 4 9 7 8 9
数据倒置.
9 8 7 9 4 3 7 2 0
5. 总结
1. 链表在元素的插入和删除操作上，比顺序表更高效，适合用于查找数据较少，插入、删除数据较多的情况。
2. 除了单向链表，还有单向循环链表、双向链表，这些链表与单向链表相比，具有独特的特点。
敬请期待下集：Linux中C语言单向循环链表和双向链表的基本操作
感谢观看！如有疑问欢迎提出！
----香菜小猫祝这位uu天天开心----