链表定义
链表是一种常见的基础数据结构，它由一系列节点（Node）组成，每个节点包含数据域和指向列表中下一个节点的指针（在双向链表中还会有指向前一个节点的指针）。链表的一个优点是它允许有效地在序列中插入和删除元素。
节点（Node）
一个节点通常包含两个部分：
- 数据域（Data Field）：存储实际的数据
- 指针域（Pointer Field）：存储下一个节点的地址
在 C 语言中，一个单链表节点的定义可能如下：
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
} Node;
链表的类型
- 单向链表（Singly Linked List）：每个节点只有一个指向下一个节点的指针
- 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，另一个指向下一个节点
- 循环链表（Circular Linked List）：链表中最后一个节点的指针指向第一个节点，形成一个环
基本操作
以下是在链表上执行的一些基本操作：
- 初始化（Initialization）：创建一个空链表
- 插入（Insertion）：
- 在链表头部插入节点
- 在链表尾部插入节点
- 在链表中间插入节点（在指定节点之后或之前）
- 删除（Deletion）：
- 删除链表头部的节点
- 删除链表尾部的节点
- 删除链表中间的节点
- 查找（Search）：在链表中查找具有特定值的节点
- 遍历（Traversal）：访问链表中的每个节点，通常用于打印或处理数据
- 反转（Reversal）：反转链表中节点的链接方向
- 排序（Sorting）：对链表中的节点进行排序
代码示例
单向链表
头文件
typedef int datatype;//重定义数据类型
typedef struct node
{
datatype data; // 数据域：存放节点要保存的数据
struct node *next; // 指针域：保存下一个节点的地址，指向下一个节点（类似于自身结构体指针）
} node_t, *node_p;
//函数声明
node_p Create_Linklist();
int Lenth_Linklist(node_p p);
int Insert_Linklist(node_p p, int post, int data);
int Delete_Linklist_post(node_p p, int post);
node_p Delete_Linklist_data(node_p p, int data);
int Change_Linklist(node_p p, int post, int data);
void Serch_Linklist_post(node_p p, int post);
int Search_Linklist_data(node_p p, int data);
int Reverse_Linklist(node_p p);
void show(node_p p);
功能函数文件
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
// 创建一个空的有头单向链表,初始化
node_p Create_Linklist()
{
// 开辟链表节点大小空间
node_p head = (node_p)malloc(sizeof(node_t));
if (NULL == head)
{
perror("error");
return NULL;
}
// 初始化头节点
head->next = NULL;
return head;
}
// 计算链表长度
int Lenth_Linklist(node_p p)
{
int len = 0;
p = p->next;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
// 向单向链表的指定位置插入数据
int Insert_Linklist(node_p p, int post, int data)
{
// 容错判断
if (post < 0 || post > Lenth_Linklist(p)) // 插入位置小于零或者大于链表长度报错
{
perror("error");
printf("插入失败\n");
}
else
{
node_p new = (node_p)malloc(sizeof(node_t)); // 创建一个新节点
new->data = data; // 将插入数据存放到新结点的数据域
new->next = NULL; // 让新结点指针域指向空
int i = 0;
while (i < post) // 遍历链表，找到插入位置的前一个节点
{
p = p->next;
i++;
}
new->next = p->next; // 让新节点的指针域指向和插入位置的前一个节点的指针域指向相同
p->next = new; // 让插入位置的前一个节点的指针域指向新节点
printf("成功插入%d\n", data);
}
return 0;
}
// 删除单向链表中指定位置的数据
int Delete_Linklist_post(node_p p, int post)
{
node_p del = NULL; // 新建临时指针指向空
// 容错判断
if (post < 0 || post >= Lenth_Linklist(p) || Lenth_Linklist(p) == 0)
{
perror("error");
printf("删除失败\n");
}
else
{
int i = 0;
while (i < post) // 指针遍历到删除位置的前一个位置
{
p = p->next;
i++;
}
del = p->next; // 用指针del记录要删除的节点
p->next = del->next; // 跨越要删除的节点，让p的next指向要删除节点的下一个节点
free(del); // 释放要删除的节点
del = NULL;
printf("成功删除\n");
}
return 0;
}
// 删除单向链表中指定的数据
node_p Delete_Linklist_data(node_p p, int data)
{
node_p del = p->next;
while (del != NULL)
{
if (del->data == data)
{
p->next = del->next;
free(del);
del = p->next;
}
else
{
p = p->next;
del = del->next;
}
}
return 0;
}
// 修改单向链表指定位置的数据
int Change_Linklist(node_p p, int post, int data)
{
if (post < 0 || post >= Lenth_Linklist(p) || Lenth_Linklist(p) == 0)
{
perror("error");
printf("修改失败\n");
}
else
{
int i = 0;
p = p->next;
while (p != NULL)
{
if (i == post)
{
p->data = data;
}
p = p->next;
i++;
}
printf("成功修改下标%d位置的元素\n", post);
}
return 0;
}
// 查找单向链表指定位置的数据
void Serch_Linklist_post(node_p p, int post)
{
if (post < 0 || post >= Lenth_Linklist(p) || Lenth_Linklist(p) == 0)
{
perror("error");
printf("查找失败\n");
}
else
{
int i = 0;
p = p->next;
while (p != NULL)
{
if (i == post)
{
printf("find:%d\n", p->data);
}
p = p->next;
i++;
}
}
}
// 查找单向链表指定数据出现的位置
int Search_Linklist_data(node_p p, int data)
{
int i = 0;
while (p->next != NULL)
{
p = p->next;
if (p->data == data)
{
return i;
}
i++;
}
return -1;
}
// 逆置链表
int Reverse_Linklist(node_p p)
{
node_p p1;
node_p p2;
p1 = p->next;//定义指针p1保存头节点的下一个节点
p->next=NULL;//断开头节点
while (p1 != NULL)//用p1遍历无头链表
{
p2=p1->next;//p2指向p1的下一个节点，防止链表丢失
//将p1插到头节点后边，先连后面再连前面
p1->next = p->next;
p->next=p1;
//让p1找到p2继续遍历
p1 = p2;
}
return 0;
}
// 遍历单向链表
void show(node_p p)
{
printf("链表元素如下:\n");
p = p->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//清空链表
void Clear_Linklist(node_p p)
{
node_p pdel = NULL;
while (p->next != NULL)
{
pdel = p->next;
p->next = pdel->next;
free(pdel);
pdel = NULL;
}
}主函数文件
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
int main(int argc, char const *argv[])
{
node_p p = Create_Linklist();
int i=0,data;
while (scanf("%d", &data)!=EOF)
{
Insert_Linklist(p, i, data);
i++;
}
show(p);
// printf("链表长度：%d\n", Lenth_Linklist(p));
// Delete_Linklist_post(p, 0);
// show(p);
// printf("链表长度：%d\n", Lenth_Linklist(p));
// Change_Linklist(p, 1, 10);
// show(p);
// Serch_Linklist_post(p, 1);
// Clear_Linklist(p);
// show(p);
// Delete_Linklist_data(p, 1);
// show(p);
Reverse_Linklist(p);
show(p);
return 0;
}双向链表
头文件
typedef int data_t;//重定义数据类型
typedef struct node
{
data_t data; // 数据域
struct node *next; // 指向下一个节点的指针（后继指针）
struct node *prior; // 指向前一个节点的指针（前趋指针）
} node_t, *node_p;
typedef struct doublelinklist
{
node_p head; // 指向双向链表的头指针
node_p tail; // 指向双向链表的尾指针
int len; // 双向链表长度
} doublelinklist_t, *doublelinklist_p;
//函数声明
doublelinklist_p create_doublelinklist()；
int insert_doublelinklist(doublelinklist_p p, int post, data_t data)；
int delete_doublelinklist_post(doublelinklist_p p, int post)；
int delete_doublelinklist_data(doublelinklist_p p, data_t data)；
int change_doublelinklist(doublelinklist_p p, int post, data_t data)；
void search_doublelinklist(doublelinklist_p p, data_t data)；
int show(doublelinklist_p p)；功能函数文件
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
// 创建空的双向链表
doublelinklist_p create_doublelinklist()
{
// 开辟双向链表结构体大小空间
doublelinklist_p p = (doublelinklist_p)malloc(sizeof(doublelinklist_t));
if (NULL == p)
{
perror("error");
return NULL;
}
// 初始化双向链表结构体, 让头尾指针都指向开辟的头节点
p->len = 0;
p->head = p->tail = (node_p)malloc(sizeof(node_t));
if (NULL == p->head)
{
perror("p->front malloc err");
return NULL;
}
// 初始化头节点 前驱和后继指针都置空
p->head->next = NULL;
p->head->prior = NULL;
return p;
}
// 向双向链表指定位置插入数据
int insert_doublelinklist(doublelinklist_p p, int post, data_t data)
{
// 容错判断
if (post < 0 || post > p->len)
{
printf("error\n");
return -1;
}
// 创建新节点保存数据
node_p new = (node_p)malloc(sizeof(node_t));
if (NULL == new)
{
perror("error");
return -1;
}
new->data = data;
new->next = NULL;
new->prior = NULL;
// 将新节点插入链表，分情况讨论
if (post == p->len) // 尾插 直接插入就行
{
new->prior = p->tail;
p->tail->next = new;
p->tail = new;
}
else // 中间插入 需要判断前后段
{
// 创建一个临时指针用来找到插入位置
node_p temp = NULL;
if (post < p->len / 2) // 前半段
{
temp = p->head; // 临时指针从头开始遍历
for (int i = 0; i <= post; i++) // 将temp向后移动到插入位置
temp = temp->next;
}
else // 后半段
{
temp = p->tail; // 临时指针从尾开始遍历
for (int i = p->len - 1; i > post; i--) // 将temp向前移动到插入位置
temp = temp->next;
}
// 将新节点连接到链表
new->prior = temp->prior;
temp->prior->next = new;
temp->prior = new;
new->next = temp;
}
p->len++;
return 0;
}
// 删除双向链表指定位置的数据
int delete_doublelinklist_post(doublelinklist_p p, int post)
{
// 容错判断
if (post < 0 || post >= p->len || p->len == 0)
{
printf("error\n");
return -1;
}
if (post == p->len - 1) // 尾删
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next = NULL;
}
else // 删除中间 需要判断前后段
{
node_p del = NULL; // 创建一个临时指针用来找到删除位置
if (post < p->len / 2) // 前半段
{
del = p->head;
for (int i = 0; i <= post; i++)
del = del->next;
}
else // 后半段
{
del = p->tail;
for (int i = p->len - 1; i > post; i--)
del = del->next;
}
del->prior->next = del->next;
del->next->prior = del->prior;
free(del);
del = NULL;
}
p->len--;
return 0;
}
// 删除双向链表指定的数据
int delete_doublelinklist_data(doublelinklist_p p, data_t data)
{
node_p temp = p->head->next;
while (temp != NULL)
{
if (temp->data == data)
{
if (temp == p->tail)
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next = NULL;
}
else
{
node_p del = temp;
temp = temp->next;
del->prior->next = del->next;
del->next->prior = del->prior;
free(del);
// del = NULL;
}
p->len--;
}
else
{
temp = temp->next;
}
}
}
// 修改双向链表指定位置的数据
int change_doublelinklist(doublelinklist_p p, int post, data_t data)
{
// 容错判断
if (post < 0 || post >= p->len || p->len == 0)
{
printf("error\n");
return -1;
}
node_p temp = NULL;
if (post < p->len / 2) // 如果位置在前半段，从头开始遍历
{
temp = p->head->next;
for (int i = 0; i < post; i++)
{
temp = temp->next;
}
}
else // 如果位置在后半段，从尾开始遍历
{
temp = p->tail;
for (int i = p->len - 1; i > post; i--)
{
temp = temp->prior;
}
}
// 修改数据
temp->data = data;
return 0;
}
// 查找双向链表指定数据，打印下标
int search_doublelinklist(doublelinklist_p p, data_t data)
{
if (p->len == 0)
{
printf("error");
return -1;
}
node_p clr = p->head->next;
int top = 0;
while (clr != NULL)
{
if (clr->data == data)
printf("%d ", top);
clr = clr->next;
top++;
}
printf("\n");
}
// 双向链表的遍历
int show(doublelinklist_p p)
{
node_p temp = NULL;
printf("正向遍历：\n");
temp = p->head;
while (temp->next != NULL) // 相当于遍历有头链表
{
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n");
printf("反向遍历：\n");
temp = p->tail;
while (temp != p->head) // 相当于遍历无头链表
{
printf("%d ", temp->data);
temp = temp->prior;
}
printf("\n");
}主函数文件
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
int main(int argc, char const *argv[])
{
doublelinklist_p p = create_doublelinklist();
int i = 0, data;
while (scanf("%d", &data) != EOF)
{
insert_doublelinklist(p, i, data);
i++;
}
show(p);
// delete_doublelinklist_post(p, 5);
// change_doublelinklist(p, 0, 100);
// delete_doublelinklist_data(p, 2);
// show(p);
search_doublelinklist(p, 2);
return 0;
}循环链表
单向循环链表
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t,*link_node_p;
int main(int argc, const char *argv[])
{
int i;
link_node_p pdel = NULL;//用于指向被删除节点
link_node_p ptail = NULL;//永远指向当前链表的尾
link_node_p pnew = NULL;//永远指向新创建的节点
link_node_p h = NULL;
int all_num = 7;//猴子总数
int start_num = 2; //从几号猴子开始数
int kill_num = 3;//数到几杀死猴
printf("请您入猴子总数 起始号码 数到几杀死:\n");
scanf("%d%d%d",&all_num,&start_num,&kill_num);
//1.创建出一个单向循环链表
//(1)创建有all_num个节点的单向链表
h = (link_node_p)malloc(sizeof(link_node_t));
if(NULL == h)
{
perror("malloc failed");
return -1;
}
h->data = 1;
h->next = NULL;
ptail = h;//尾指针指向当前的第一个节点
for(i = 2; i <= all_num; i++)
{
//创建新的节点
pnew = (link_node_p)malloc(sizeof(link_node_t));
if(NULL == pnew)
{
perror("malloc failed");
return -1;
}
//将新节点装上数据
pnew->data = i;
pnew->next = NULL;
//将新节点链接到链表尾
ptail->next = pnew;//链接到链表的尾
ptail = pnew;//尾指针继续指向当前链表的尾
}
//(2)将头指针保存到链表的尾形成单向循环链表
ptail->next = h;//形成单向循环链表
#if 0 //用于调试程序
while(1)
{
printf("%d\n",h->data);
h = h->next;
sleep(1);
}
#endif
//2.开始杀猴子
//(1)将头指针移动到开始猴子的号码处
for(i = 1; i < start_num; i++)
h = h->next;
printf("start :%d\n",h->data);
//(2)循环进行杀猴子
while(h != h->next)//条件不成的时候，就剩一个猴子,只有一个节点
{
//将头指针移动到即将删除节点的前一个节点
for(i = 1; i < kill_num-1; i++)
h = h->next;
pdel = h->next;
//跨过删除节点
h->next = pdel->next;
printf("kill is -------------%d\n",pdel->data);
free(pdel);
pdel = NULL;
//杀死猴子猴，从下一个节点开始继续开始数,将头指针移动到开始数的地方
h = h->next;
}
printf("king is=================== %d\n",h->data);
return 0;
}双向循环链表
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct node
{
data_t data; // 数据域
struct node *next; // 指向下一个节点的指针（后继指针）
struct node *prior; // 指向前一个节点的指针（前趋指针）
} node_t, *node_p;
typedef struct doublelinklist
{
node_p head; // 指向双向链表的头指针
node_p tail; // 指向双向链表的尾指针
int len; // 双向链表长度
} doublelinklist_t, *doublelinklist_p;
// 创建空的双向链表
doublelinklist_p create_doublelinklist()
{
// 开辟双向链表结构体大小空间
doublelinklist_p p = (doublelinklist_p)malloc(sizeof(doublelinklist_t));
if (NULL == p)
{
perror("error");
return NULL;
}
// 初始化双向链表结构体, 让头尾指针都指向开辟的头节点
p->len = 0;
p->head = p->tail = (node_p)malloc(sizeof(node_t));
if (NULL == p->head)
{
perror("p->front malloc err");
return NULL;
}
// 初始化头节点 前驱和后继指针都置空
p->head->next = NULL;
p->head->prior = NULL;
return p;
}
// 向双向链表指定位置插入数据
int insert_doublelinklist(doublelinklist_p p, int post, data_t data)
{
// 容错判断
if (post < 0 || post > p->len)
{
printf("error\n");
return -1;
}
// 创建新节点保存数据
node_p new = (node_p)malloc(sizeof(node_t));
if (NULL == new)
{
perror("error");
return -1;
}
new->data = data;
new->next = NULL;
new->prior = NULL;
// 将新节点插入链表，分情况讨论
if (post == p->len) // 尾插 直接插入就行
{
new->prior = p->tail;
p->tail->next = new;
p->tail = new;
}
else // 中间插入 需要判断前后段
{
// 创建一个临时指针用来找到插入位置
node_p temp = NULL;
if (post < p->len / 2) // 前半段
{
temp = p->head; // 临时指针从头开始遍历
for (int i = 0; i <= post; i++) // 将temp向后移动到插入位置
temp = temp->next;
}
else // 后半段
{
temp = p->tail; // 临时指针从尾开始遍历
for (int i = p->len - 1; i > post; i--) // 将temp向前移动到插入位置
temp = temp->next;
}
// 将新节点连接到链表
new->prior = temp->prior;
temp->prior->next = new;
temp->prior = new;
new->next = temp;
}
p->len++;
return 0;
}
// 删除双向链表指定位置的数据
int delete_doublelinklist_post(doublelinklist_p p, int post)
{
// 容错判断
if (post < 0 || post >= p->len || p->len == 0)
{
printf("error\n");
return -1;
}
if (post == p->len - 1) // 尾删
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next = NULL;
}
else // 删除中间 需要判断前后段
{
node_p del = NULL; // 创建一个临时指针用来找到删除位置
if (post < p->len / 2) // 前半段
{
del = p->head;
for (int i = 0; i <= post; i++)
del = del->next;
}
else // 后半段
{
del = p->tail;
for (int i = p->len - 1; i > post; i--)
del = del->next;
}
del->prior->next = del->next;
del->next->prior = del->prior;
free(del);
del = NULL;
}
p->len--;
return 0;
}
// 删除双向链表指定的数据
int delete_doublelinklist_data(doublelinklist_p p, data_t data)
{
node_p temp = p->head->next;
while (temp != NULL)
{
if (temp->data == data)
{
if (temp == p->tail)
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next = NULL;
}
else
{
node_p del = temp;
temp = temp->next;
del->prior->next = del->next;
del->next->prior = del->prior;
free(del);
// del = NULL;
}
p->len--;
}
else
{
temp = temp->next;
}
}
}
// 修改双向链表指定位置的数据
int change_doublelinklist(doublelinklist_p p, int post, data_t data)
{
// 容错判断
if (post < 0 || post >= p->len || p->len == 0)
{
printf("error\n");
return -1;
}
node_p temp = NULL;
if (post < p->len / 2) // 如果位置在前半段，从头开始遍历
{
temp = p->head->next;
for (int i = 0; i < post; i++)
{
temp = temp->next;
}
}
else // 如果位置在后半段，从尾开始遍历
{
temp = p->tail;
for (int i = p->len - 1; i > post; i--)
{
temp = temp->prior;
}
}
// 修改数据
temp->data = data;
return 0;
}
// 查找双向链表指定数据，打印下标
void search_doublelinklist(doublelinklist_p p, data_t data)
{
if (p->len == 0)
{
printf("error");
return -1;
}
node_p clr = p->head->next;
int top = 0;
while (clr != NULL)
{
if (clr->data == data)
printf("%d ", top);
clr = clr->next;
top++;
}
printf("\n");
}
// 双向链表的遍历
int show(doublelinklist_p p)
{
node_p temp = NULL;
printf("正向遍历：\n");
temp = p->head;
while (temp->next != NULL) // 相当于遍历有头链表
{
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n");
printf("反向遍历：\n");
temp = p->tail;
while (temp != p->head) // 相当于遍历无头链表
{
printf("%d ", temp->data);
temp = temp->prior;
}
printf("\n");
}
int main(int argc, char const *argv[])
{
doublelinklist_p p = create_doublelinklist();
int i = 0, data;
while (scanf("%d", &data) != EOF)
{
insert_doublelinklist(p, i, data);
i++;
}
show(p);
// delete_doublelinklist_post(p, 5);
// change_doublelinklist(p, 0, 100);
// delete_doublelinklist_data(p, 2);
// show(p);
search_doublelinklist(p, 2);
return 0;
}