目录
源代码:
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define OK 1
#define ERROR 0
typedef int Status;//函数返回状态,ok,error
typedef int Elemtype;//链表元素为整形
typedef struct Lnode//定义结构体
{
Elemtype data;//数据域
struct Lnode* next;//指针域
}Lnode,*LinkList;//单个结点,整个链表(指向结点的指针)
//初始化链表(建立一个头结点)
Status InitLinkList(LinkList* L){
*L=(LinkList)malloc(sizeof(Lnode));//分配头结点内存
if(*L==NULL){
return ERROR;//判断是否分配成功
}
(*L)->next=*L;//头结点的指针域指向他自己(循环链表)
return OK;
}
//判断链表是否为空
Status IsEmptyLinkList(const LinkList* L){
if((*L)->next==(*L)){//看看是否指向他自己
printf("该链表为空!\n");
return ERROR;
}else{
printf("该链表不为空!\n");
return OK;
}
}
//求链表的长度
Status LenLinkList(const LinkList* L){
IsEmptyLinkList(L);//判断链表是否为空
int i=0;//计数
Lnode* p;//定义一个临时的结点
p=(*L)->next;
while (p!=*L)//仍然是看看是否指向自己(回到头结点)
{
i++;//每循环一次计数加一
p=p->next;
}
printf("该链表的长度为:%d\n",i);
return OK;
}
//清空链表
Status ClearLinkList(LinkList* L){
Lnode* p;
Lnode* q;
p=(*L)->next;
while (p!=*L)//回到头结点时结束
{
q=p;
p=p->next;
free(q);
}
(*L)->next=*L;
printf("该链表已清空!\n");
return OK;
}
//销毁链表
Status DestoryLinkList(LinkList* L){
LinkList p;//定义一个临时的指向结点的指针
LinkList q=(*L)->next;
while (q!=*L)
{
p=*L;//储存原来的指针(结点)
*L=(*L)->next;//往后移动结点
free(p);//释放原来的指针
}
printf("该链表已销毁!\n");
return OK;
}
//链表的插入,头插法
Status CreateLinkList_h(LinkList* L,int n){//n是插入几条数据
InitLinkList(L);//创建头结点
for(int i=0;i<n;i++){
LinkList newlnode;//创建一个新结点
newlnode=(Lnode*)malloc(sizeof(Lnode));//为新节点分配内存
if(newlnode==NULL){
return ERROR;//判断是否分配成功
}
printf("请输入数据:\n");
scanf("%d",&newlnode->data);
newlnode->next=(*L)->next;//使新结点指向原指针
(*L)->next=newlnode;//使头指针指向新结点
}
return OK;
}
//链表的插入,尾插入
Status CreateLinkList_r(LinkList* L,int n){
InitLinkList(L);//创建头结点
LinkList p=*L;//定义临时尾结点
for(int i=0;i<n;i++){
LinkList newlnode;
newlnode=(Lnode*)malloc(sizeof(Lnode));//给新结点分配内存
if(newlnode==NULL){
return ERROR;//判断是否分配成功
}
printf("请输入数据:\n");
scanf("%d",&newlnode->data);
newlnode->next=*L;//使新结点指向头结点
p->next=newlnode;//使原结点指向新结点
p=p->next;//后移一次,定义新的尾结点
}
return OK;
}
//查看链表
Status ShowLinkList(const LinkList* L){
IsEmptyLinkList(L);
Lnode* p=(*L)->next;//定义个临时结点
int i=1;
printf("该链表的数据为:\n");
while (p!=*L)//指向头结点
{
printf("%d : %d\n", i, p->data); // 打印序号和数据
i++; // 序号递增
p = p->next; // p 移动到下一个结点
}
return OK;
}
//单链表插入,在第i个结点之前插入一个结点
Status InsertLinkList(LinkList *L, int i, Elemtype value)
{
Lnode* p;//定义临时结点
p = (*L)->next;//初始化为第一个结点
int j = 1;
while (p && j < i - 1) //找到第i-1个结点(就是i的前面)
{
j++;
p = p->next;
}
if (!p || j > i - 1) //i大于表长+1,或者小于1,插入位置非法
return ERROR;
Lnode* newlnode;//定义新结点
newlnode = (Lnode*)malloc(sizeof(Lnode));
newlnode->data = value;//插入的数据
newlnode->next = p->next;
p->next = newlnode;
return OK;
}
//删除第i个结点
Status DelLinkList(LinkList* L,int i){
int j=i;
i=1;
Lnode* p=(*L);
Lnode* q;
while (j!=i)//找到第i个结点
{
i++;
p=p->next;
}
if (p->next == *L || j > i) return ERROR;//检查是否越界
q=p->next;
p->next=q->next;
free(q);
return OK;
}
//查看第i个元素
Status LocatElem(const LinkList* L,int i){
int j=i;//赋值给j
i=1;//初始化i
LinkList p=(*L)->next;//创建临时结点表示第一个结点
IsEmptyLinkList(L);//检查是否为空
//逐步后移,直到i和j相等
while (i!=j)
{
i++;
p=p->next;
}
if (p->next == *L || j > i) return ERROR;//检查是否越界
printf("第%d个 : %d\n", j, p->data); // 打印第i个序号,和数据
return OK;
}
//主函数
int main(){
LinkList mylist;
mylist=NULL;
//CreateLinkList_h(&mylist,4);//头插
CreateLinkList_r(&mylist,4);//尾插
ShowLinkList(&mylist);
InsertLinkList(&mylist, 3, 9);
ShowLinkList(&mylist);
LenLinkList(&mylist);
DelLinkList(&mylist,3);
ShowLinkList(&mylist);
LocatElem(&mylist,2);
IsEmptyLinkList(&mylist);
ClearLinkList(&mylist);
DestoryLinkList(&mylist);
}
代码详解:
1. 头文件和宏定义
#include <stdio.h> #include <stdlib.h> //函数结果状态代码 #define OK 1 #define ERROR 0
#include <stdio.h>
:引入标准输入输出库,这样就能使用printf
和scanf
等函数了。#include <stdlib.h>
:引入标准库,可使用malloc
和free
等内存管理函数。#define OK 1
和#define ERROR 0
:定义宏,用于表示函数执行的状态,OK
代表操作成功,ERROR
代表操作失败。2. 类型定义
typedef int Status;//函数返回状态,ok,error typedef int Elemtype;//链表元素为整形 typedef struct Lnode//定义结构体 { Elemtype data;//数据域 struct Lnode* next;//指针域 }Lnode, * LinkList;//单个结点,整个链表(指向结点的指针)
typedef int Status
:将int
类型重命名为Status
,用来表示函数的返回状态。typedef int Elemtype
:把int
类型重命名为Elemtype
,意味着链表中存储的元素类型为整数。typedef struct Lnode
:定义一个结构体Lnode
,它包含两个成员:
Elemtype data
:数据域,用于存储结点的数据。struct Lnode* next
:指针域,指向链表中的下一个结点。Lnode, * LinkList
:Lnode
表示单个结点的类型,LinkList
表示指向结点的指针类型,也就是整个链表。3. 初始化链表
//初始化链表(建立一个头结点) Status InitLinkList(LinkList* L) { *L = (LinkList)malloc(sizeof(Lnode));//分配头结点内存 if (*L == NULL) { return ERROR;//判断是否分配成功 } (*L)->next = *L;//头结点的指针域指向他自己(循环链表) return OK; }
LinkList* L
:传入的是指向链表指针的指针,这样就能修改调用者的链表指针了。*L = (LinkList)malloc(sizeof(Lnode))
:为头结点分配内存。if (*L == NULL)
:检查内存分配是否成功,若失败则返回ERROR
。(*L)->next = *L
:让头结点的next
指针指向自身,形成循环链表。return OK
:若初始化成功,返回OK
。图解:
+--------+ | 头结点 | +--------+ | ^ | | +----+
4. 判断链表是否为空
//判断链表是否为空 Status IsEmptyLinkList(const LinkList* L) { if ((*L)->next == (*L)) {//看看是否指向他自己 printf("该链表为空!\n"); return ERROR; } else { printf("该链表不为空!\n"); return OK; } }
const LinkList* L
:传入指向链表指针的常量指针,不修改链表指针。if ((*L)->next == (*L))
:检查头结点的next
指针是否指向自身,若是则链表为空,输出提示信息并返回ERROR
。- 反之,输出链表不为空的提示信息并返回
OK
。5. 求链表的长度
//求链表的长度 Status LenLinkList(const LinkList* L) { IsEmptyLinkList(L);//判断链表是否为空 int i = 0;//计数 Lnode* p;//定义一个临时的结点 p = (*L)->next; while (p != *L)//仍然是看看是否指向自己(回到头结点) { i++;//每循环一次计数加一 p = p->next; } printf("该链表的长度为:%d\n", i); return OK; }
IsEmptyLinkList(L)
:先判断链表是否为空。int i = 0
:初始化计数器。Lnode* p
:定义一个临时结点指针。p = (*L)->next
:让p
指向头结点的下一个结点。while (p != *L)
:当p
不等于头结点时,继续循环。
i++
:计数器加一。p = p->next
:p
指向下一个结点。- 最后输出链表的长度并返回
OK
。6. 清空链表
//清空链表 Status ClearLinkList(LinkList* L) { Lnode* p; Lnode* q; p = (*L)->next; while (p != *L)//回到头结点时结束 { q = p; p = p->next; free(q); } (*L)->next = *L; printf("该链表已清空!\n"); return OK; }
Lnode* p
和Lnode* q
:定义两个临时结点指针。p = (*L)->next
:p
指向头结点的下一个结点。while (p != *L)
:当p
不等于头结点时,继续循环。
q = p
:用q
保存当前结点。p = p->next
:p
指向下一个结点。free(q)
:释放q
指向的结点。(*L)->next = *L
:让头结点的next
指针指向自身,恢复为空链表状态。- 输出清空提示信息并返回
OK
。7. 销毁链表
//销毁链表 Status DestoryLinkList(LinkList* L) { LinkList p; LinkList q = (*L)->next; while (q != *L) { p = q; q = q->next; free(p); } free(*L); printf("该链表已销毁!\n"); return OK; }
LinkList p
和LinkList q
:定义两个链表指针。q = (*L)->next
:q
指向头结点的下一个结点。while (q != *L)
:当q
不等于头结点时,继续循环。
p = q
:用p
保存当前结点。q = q->next
:q
指向下一个结点。free(p)
:释放p
指向的结点。free(*L)
:释放头结点。- 输出销毁提示信息并返回
OK
。8. 链表的插入(头插法)
//链表的插入,头插法 Status CreateLinkList_h(LinkList* L, int n) {//n是插入几条数据 InitLinkList(L);//创建头结点 for (int i = 0; i < n; i++) { LinkList newlnode;//创建一个新结点 newlnode = (Lnode*)malloc(sizeof(Lnode));//为新节点分配内存 if (newlnode == NULL) { return ERROR;//判断是否分配成功 } printf("请输入数据:\n"); scanf("%d", &newlnode->data); newlnode->next = (*L)->next;//使新结点指向原指针 (*L)->next = newlnode;//使头指针指向新结点 } return OK; }
InitLinkList(L)
:初始化链表,创建头结点。for (int i = 0; i < n; i++)
:循环n
次,插入n
个结点。
LinkList newlnode
:定义一个新结点指针。newlnode = (Lnode*)malloc(sizeof(Lnode))
:为新结点分配内存。if (newlnode == NULL)
:检查内存分配是否成功,若失败则返回ERROR
。scanf("%d", &newlnode->data)
:从用户输入读取数据存入新结点的数据域。newlnode->next = (*L)->next
:让新结点的next
指针指向头结点原来指向的结点。(*L)->next = newlnode
:让头结点的next
指针指向新结点。- 最后返回
OK
。图解:
插入前:+--------+ +--------+ | 头结点 | -> | 结点1 | +--------+ +--------+
插入后:
+--------+ +--------+ +--------+ | 头结点 | -> | 新结点 | -> | 结点1 | +--------+ +--------+ +--------+
9. 链表的插入(尾插法)
//链表的插入,尾插入 Status CreateLinkList_r(LinkList* L, int n) { InitLinkList(L);//创建头结点 LinkList p = *L;//定义临时尾结点 for (int i = 0; i < n; i++) { LinkList newlnode; newlnode = (Lnode*)malloc(sizeof(Lnode));//给新结点分配内存 if (newlnode == NULL) { return ERROR;//判断是否分配成功 } printf("请输入数据:\n"); scanf("%d", &newlnode->data); newlnode->next = *L;//使新结点指向头结点 p->next = newlnode;//使原结点指向新结点 p = p->next;//后移一次,定义新的尾结点 } return OK; }
InitLinkList(L)
:初始化链表,创建头结点。LinkList p = *L
:定义一个临时尾结点指针,初始指向头结点。for (int i = 0; i < n; i++)
:循环n
次,插入n
个结点。
LinkList newlnode
:定义一个新结点指针。newlnode = (Lnode*)malloc(sizeof(Lnode))
:为新结点分配内存。if (newlnode == NULL)
:检查内存分配是否成功,若失败则返回ERROR
。scanf("%d", &newlnode->data)
:从用户输入读取数据存入新结点的数据域。newlnode->next = *L
:让新结点的next
指针指向头结点。p->next = newlnode
:让原尾结点的next
指针指向新结点。p = p->next
:更新尾结点指针,使其指向新结点。- 最后返回
OK
。10. 查看链表
//查看链表 Status ShowLinkList(const LinkList* L) { IsEmptyLinkList(L); Lnode* p = (*L)->next;//定义个临时结点 int i = 1; printf("该链表的数据为:\n"); while (p != *L)//指向头结点 { printf("%d : %d\n", i, p->data); // 打印序号和数据 i++; // 序号递增 p = p->next; // p 移动到下一个结点 } return OK; }
IsEmptyLinkList(L)
:先判断链表是否为空。Lnode* p = (*L)->next
:定义一个临时结点指针,指向头结点的下一个结点。int i = 1
:初始化序号。while (p != *L)
:当p
不等于头结点时,继续循环。
printf("%d : %d\n", i, p->data)
:打印序号和结点的数据。i++
:序号加一。p = p->next
:p
指向下一个结点。- 最后返回
OK
。11. 单链表插入(在第
i
个结点之前插入)//单链表插入,在第i个结点之前插入一个结点 Status InsertLinkList(LinkList* L, int i, Elemtype value) { Lnode* p;//定义临时结点 p = (*L); int j = 0; while (p && j < i - 1) //找到第i-1个结点(就是i的前面) { j++; p = p->next; } if (!p || j > i - 1) //i大于表长+1,或者小于1,插入位置非法 return ERROR; Lnode* newlnode;//定义新结点 newlnode = (Lnode*)malloc(sizeof(Lnode)); newlnode->data = value;//插入的数据 newlnode->next = p->next; p->next = newlnode; return OK; }
Lnode* p
:定义一个临时结点指针,初始指向头结点。int j = 0
:初始化计数器。while (p && j < i - 1)
:循环找到第i - 1
个结点。
j++
:计数器加一。p = p->next
:p
指向下一个结点。if (!p || j > i - 1)
:检查插入位置是否合法,若不合法则返回ERROR
。Lnode* newlnode
:定义一个新结点指针。newlnode = (Lnode*)malloc(sizeof(Lnode))
:为新结点分配内存。newlnode->data = value
:将插入的值存入新结点的数据域。newlnode->next = p->next
:让新结点的next
指针指向第i
个结点。p->next = newlnode
:让第i - 1
个结点的next
指针指向新结点。- 最后返回
OK
。12. 删除第
i
个结点//删除第i个结点 Status DelLinkList(LinkList* L, int i) { if (i < 1) return ERROR; int j = 1; Lnode* p = *L; Lnode* q; while (p->next != *L && j < i) { j++; p = p->next; } if (p->next == *L || j > i) return ERROR; q = p->next; p->next = q->next; free(q); return OK; }
if (i < 1)
:检查i
是否小于 1,若小于 1 则返回ERROR
。int j = 1
:初始化计数器。Lnode* p = *L
:定义一个临时结点指针,初始指向头结点。while (p->next != *L && j < i)
:循环找到第i - 1
个结点。
j++
:计数器加一。p = p->next
:p
指向下一个结点。if (p->next == *L || j > i)
:检查i
是否超出链表长度,若超出则返回ERROR
。q = p->next
:用q
保存第i
个结点。p->next = q->next
:让第i - 1
个结点的next
指针指向第i + 1
个结点。free(q)
:释放第i
个结点的内存。- 最后返回
OK
。13. 查看第
i
个元素//查看第i个元素 Status LocatElem(const LinkList* L, int i) { if (i < 1) return ERROR; int j = 1; LinkList p = (*L)->next; IsEmptyLinkList(L);//检查是否为空 while (p != *L && j < i) { j++; p = p->next; } if (p == *L) { printf("位置超出链表长度!\n"); return ERROR; } printf("第%d个 : %d\n", i, p->data); // 打印第i个序号,和数据 return OK; }
if (i < 1)
:检查i
是否小于 1,若小于 1 则返回ERROR
。int j = 1
:初始化计数器。LinkList p = (*L)->next
:定义一个临时结点指针,指向头结点的下一个结点。IsEmptyLinkList(L)
:检查链表是否为空。while (p != *L && j < i)
:循环找到第i
个结点。
j++
:计数器加一。p = p->next
:p
指向下一个结点。if (p == *L)
:检查i
是否超出链表长度,若超出则输出提示信息并返回ERROR
。printf("第%d个 : %d\n", i, p->data)
:打印第i
个结点的数据。- 最后返回
OK
。14. 主函数
//主函数 int main() { LinkList mylist; mylist = NULL; //CreateLinkList_h(&mylist,4);//头插 CreateLinkList_r(&mylist, 4);//尾插 ShowLinkList(&mylist); InsertLinkList(&mylist, 3, 9); ShowLinkList(&mylist); LenLinkList(&mylist); DelLinkList(&mylist, 3); ShowLinkList(&mylist); LocatElem(&mylist, 2); IsEmptyLinkList(&mylist); ClearLinkList(&mylist); DestoryLinkList(&mylist); }
LinkList mylist
:定义一个链表指针。mylist = NULL
:初始化链表指针为NULL
。CreateLinkList_r(&mylist, 4)
:使用尾插法插入 4 个结点。ShowLinkList(&mylist)
:显示链表内容。InsertLinkList(&mylist, 3, 9)
:在第 3 个结点之前插入值为 9 的结点。ShowLinkList(&mylist)
:再次显示链表内容。LenLinkList(&mylist)
:计算并输出链表长度。DelLinkList(&mylist, 3)
:删除第 3 个结点。ShowLinkList(&mylist)
:再次显示链表内容。LocatElem(&mylist, 2)
:查看第 2 个结点的数据。IsEmptyLinkList(&mylist)
:判断链表是否为空。ClearLinkList(&mylist)
:清空链表。DestoryLinkList(&mylist)
:销毁链表。
知识原理:
1. 基础结构定义
typedef struct Lnode { int data; // 数据域(存储整型数据) struct Lnode* next; // 指针域(指向下一个结点) } Lnode, *LinkList; // Lnode是结点类型,LinkList是指向结点的指针类型图示:
[data|next] → [data|next] → ... → [头结点]
2. 初始化链表
Status InitLinkList(LinkList* L) { *L = (LinkList)malloc(sizeof(Lnode)); // 创建头结点 (*L)->next = *L; // 头结点指向自己,形成空环 return OK; }原理:
分配头结点内存
让头结点的
next
指向自己,表示空链表内存状态:
头结点 ↓ [NULL|] ←┐ ↑_____┘
3. 头插法创建链表(动图演示)
newNode->next = (*L)->next; // ① 新结点指向原首结点 (*L)->next = newNode; // ② 头结点指向新结点插入过程:
初始:头结点 → [A] 步骤1:newNode → [A] 步骤2:头结点 → newNode → [A]
4. 尾插法创建链表
newNode->next = *L; // 新结点指向头结点 p->next = newNode; // 尾结点指向新结点 p = newNode; // 更新尾指针特点:
需要维护尾指针
p
插入顺序与数据顺序一致
5. 遍历链表(带图解)
while (p != *L) { // 回到头结点时停止 printf("%d ", p->data); p = p->next; }遍历路径:
头结点 → [10] → [20] → [30] → 头结点 ↑_________________________|
6. 插入结点(步骤分解)
// 在位置i前插入 newNode->next = p->next; // ① 新结点指向原i位置结点 p->next = newNode; // ② i-1结点指向新结点示例(在第2个位置插入9):
插入前:头结点 → [10] → [20] → [30] 插入后:头结点 → [10] → [9] → [20] → [30]
7. 删除结点(安全版)
q = p->next; // ① 保存待删除结点 p->next = q->next; // ② 绕过待删除结点 free(q); // ③ 释放内存边界检查:
if (p->next == *L) return ERROR; // 防止删除不存在的结点
8. 内存管理要点
操作 关键步骤 注意事项 创建结点 malloc
分配内存检查是否分配成功 删除结点 free
释放内存必须先保存 next
再释放清空链表 循环释放所有结点 最后重置头结点指针 销毁链表 先清空再释放头结点 将头指针设为NULL
运行结果:
请输入数据:
12
请输入数据:
23
请输入数据:
34
请输入数据:
45
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 34
4 : 45
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 9
4 : 34
5 : 45
该链表不为空!
该链表的长度为:5
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 34
4 : 45
该链表不为空!
第2个 : 23
该链表不为空!
该链表已清空!
该链表已销毁!
请按任意键继续. . .
单链表教程:
(C语言)单链表(2.0)数据结构(指针,单链表教程)-CSDN博客
注:该代码是本人自己所写,可能不够好,不够简便,欢迎大家指出我的不足之处。如果遇见看不懂的地方,可以在评论区打出来,进行讨论,或者联系我。上述内容全是我自己理解的,如果你有别的想法,或者认为我的理解不对,欢迎指出!!!如果可以,可以点一个免费的赞支持一下吗?谢谢各位彦祖亦菲!!!!!