目录

• • 单链表（线性表的链式存储）---C语言版
  • • 一、相关说明
    • 二、单链表的定义
    • 三、单链表上具体操作的实现和时间复杂度
    • • 1、初始化表。构造一个空表。
      • 2、根据数组创建单链表
      • 3、求表长
      • 4、插入操作。在表L中的第i个位置上插入指定元素e。
      • 5、删除操作。删除表中L中第i个位置的元素，并用e返回删除的元素。
      • 6、按位查找操作。获取表L中第i个位置的元素的值。
      • 7、按值查找操作。在表L中查找具有给定关键字值的元素,返回序号
      • 8、输出操作。按前后顺序输出表L的所有元素值。
      • 9、销毁表
    • 四、完整代码实现

单链表（线性表的链式存储）—C语言版 一、相关说明
逻辑上相邻的元素在物理位置上不一定相邻。
优点：

没有了顺序存储所具有的弱点（也就是说：插入和删除不需要移动元素，而只需要修改指针。）
同时，由于不借助数组实现，在定义链表时，无需指定它的长度。

缺点：

也失去了顺序存储的优点

1. 非随机存取（不能直接找到某个特定序号的结点，需要从表头开始遍历）
2. 存储密度降低（除了存储本身信息外链表还要存储指针）

二、单链表的定义
定义

线性表的链式存储又称为单链表，它是指通过一组任意的存储单位来存储线性表中的元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素的自身信息外，还需要存放一个指向其后继的指针。

仍旧使用该例子，我们要如何存储该表呢？

id	name	description
1	史强	最强辅助
2	章北海	我不需要钢印，我是自己思想的主人
3	罗辑	人类不感谢罗辑
4	维德	失去人性，失去很多。失去兽性，失去一切

步骤一：声明数据元素类型

首先我们使用结构体声明数据元素（对应表中的一行数据）的类型

typedef struct{ int id; //对应表中的id char name[100]; //对应表中的姓名 char description[200]; //对应表中的描述 }ElemType; //此处的ElemType是个类型名

步骤二：声明结点
由于逻辑上相邻的元素在物理位置上不一定相邻，那么我们如何确定下一个元素的存储位置呢？

解决办法，增加一个变量。用来存储一个指示其后继位置的指针。

我们把这两部分的信息组成数据元素a的存储映像，称为结点。它包含两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。
单链表中结点定义如下：

typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList;

相关概念
1.头指针

整个链表的存储必须从头指针开始
头指针指示链表中第一个结点的存储位置
同时，由于最后一个数据元素没有直接后继，则单链表中最后一个一个结点的指针为NULL

//头指针定义1 LinkList L; //头指针定义2 LNode *L;

如图所示：

文章图片

2.头结点

在单链表的第一个结点之前附设一个结点，称为头结点。
头结点的数据域可以不存储任何信息，也可以存储如线性表的长度之类的附加信息。
头结点的指向第一个结点的指针（即第一个元素结点的存储位置）
此时，单链表的头指针指向头结点。

如图所示：

文章图片

逻辑图：

文章图片

关于引入头结点的优缺点，后续会根据有无头结点，创建链表操作（3.2）的具体实现来介绍。

空表
含头结点

LinkList L;
L->next==NULL时为空表

文章图片

不含头结点

LinkList L;
L==NULL时为空表；

三、单链表上具体操作的实现和时间复杂度
1、初始化表。构造一个空表。

int InitList_Link(LinkList *L){ *L=(LinkList)malloc(sizeof(LNode)); //创建头结点，并让头指针指向头结点 if (!(*L)) return FALSE; //分配失败 (*L)->next=NULL; //初始化为空 return TRUE; //初始化成功 }

时间复杂度：

时间复杂度为O(1)

2、根据数组创建单链表 分类一：含头结点
1.头插法

int create_HeadInsert(LinkList *L,ElemType a[],int n){ // InitList_Link(L); LNode *s; //用来指示新创建的结点 int i; for(i=n-1; i>=0; i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历 s=(LinkList)malloc(sizeof(LNode)); //创建一个新结点 s->data=https://www.it610.com/article/a[i]; //为结点赋值 s->next=(*L)->next; //让该结点指向第一个结点 (*L)->next=s; //让头结点指向该结点 } }

2.尾插法

int create_TailInsert(LinkList *L,ElemType a[],int n){ // InitList_Link(L); LNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表 int i; for(i=0; idata=https://www.it610.com/article/a[i]; //为结点赋值 r->next=s; //r始终指向链表的尾端，这里将新结点连接到r的后面 r=s; //r移动到链表尾端 } r->next=NULL; //结束时，最后一个结点的指针域赋值为空 }

分类二：不含头结点
1.头插法

int create_HeadInsert(LinkList *L,ElemType a[],int n){ *L=NULL; LNode *s; //用来指示新创建的结点 int i; for(i=n-1; i>=0; i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历 s=(LinkList)malloc(sizeof(LNode)); //创建一个新结点 s->data=https://www.it610.com/article/a[i]; //为结点赋值 if((*L)==NULL){//对第一个结点需要特殊处理 *L=s; //头指针指向插入结点 s->next=NULL; //倒序插入，最后一个结点的指针域赋值为NULL }else{ s->next=*(L); //新插入的结点指向第一个结点 *(L)=s; //头指针指向新的插入节点 } } }

2.尾插法

int create_TailInsert(LinkList *L,ElemType a[],int n){ // InitList_Link(L); (*L)=NULL; LNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表 int i; for(i=0; idata=https://www.it610.com/article/a[i]; //为结点赋值 if((*L)==NULL){//对第一个结点需要特殊处理 (*L)=s; //头指针指向第一个结点 r=s; //尾指针移动到最后一个结点 }else{ r->next=s; //r始终指向链表的尾端，这里将新结点连接到r的后面 r=s; //r移动到链表尾端 } } r->next=NULL; //结束时，最后一个结点的指针域赋值为空 }

含头结点优点：

使得链表第一个结点的操作和其他位置一样，无需特殊处理。

含头结点缺点：

头结点的数据域一般不存储数据，该空间被浪费。

时间复杂度：

每个结点插入的时间为O(1),设表长为n
所有方式的时间复杂度均为O(n)

3、求表长

int Length_Link(LinkList L){ int i=0; //空表返回0 while (L->next!=NULL){//遍历，直到尾结点，空表不进入循环 L=L->next; //向后移动一个 i++; //表长加一 } return i; //返回表长 }

时间复杂度：

设表长为n
时间复杂度为O(n)

4、插入操作。在表L中的第i个位置上插入指定元素e。

int ListInsert_Link(LinkList *L,int i,ElemType e){ int j=0; //空表序号为0 LNode *p=(*L); //p指向头结点 LNode *s; //s用来指示新创建的结点 while (p&&jnext; //向后移动一个 j++; } if(!p||i<1) return FALSE; //序号在无效范围内 s=(LinkList)malloc(sizeof(LNode)); //创建一个新结点 s->data=https://www.it610.com/article/e; //赋值 s->next=p->next; //让该结点指向p（插入位置的前一个结点）的下一个结点 p->next=s; //让p指向该结点 }

时间复杂度：

在给定的结点后插入新结点的时间复杂度为O(1)
查找第i-1个节点的时间复杂度为O(n)
综上：时间复杂度为O(n)

文章图片

5、删除操作。删除表中L中第i个位置的元素，并用e返回删除的元素。

int ListDelete_Link(LinkList *L,int i,ElemType *e){ int j=0; //空表序号为0 LNode *p=(*L); //p指向头结点 LNode *q; //q用来指向被删除的结点 while (p->next&&jnext; //向后移动一个 j++; } if (!(p->next)||i<1) return FALSE; //序号在无效范围内 q=p->next; //让q指向被删除的结点 p->next=q->next; //让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开 *e=q->data; //把被删除的结点的值返回 free(q); //释放该结点 return TRUE; //删除成功 }

文章图片

时间复杂度：

在给定的结点后删除结点的时间复杂度为O(1)
查找第i-1个节点的时间复杂度为O(n)
综上：时间复杂度为O(n)

6、按位查找操作。获取表L中第i个位置的元素的值。

int GetElem_List(LinkList L,int i,ElemType *e){ LNode *p=L; //p指向头结点 int j=0; //空表序号为0 while (p&&jnext; //向后移动一个 ++j; } if(!(p)||i<1)return FALSE; //i不在有效范围内 *e=p->data; //把第i个结点的值用e返回 return TRUE; }

时间复杂度：

时间复杂度为O(n)

7、按值查找操作。在表L中查找具有给定关键字值的元素,返回序号

int LocateElem_List(LinkList L,ElemType e,int *i){ int j=0; //空表序号为0 while (L->next!=NULL){//遍历链表 L=L->next; //向后移动 j++; //序号加一 if (L->data.id==e.id){//这里我们只用id来判断元素的值是否相等，假设id唯一 *i=j; //如果相等，用i返回序号 return TRUE; //查找成功 } } return FALSE; }

时间复杂度：

时间复杂度为O(n)

8、输出操作。按前后顺序输出表L的所有元素值。

void PrintList_Link(LinkList L){ int i=0; //空表序号为0 while (L->next!=NULL)//遍历表 { L=L->next; i++; printf("第%d行：id=%d,name=%s,description=%s\n",i,L->data.id,L->data.name,L->data.description); } }

时间复杂度：

时间复杂度为O(n)

9、销毁表

void DestroyList(LinkList *L){ while((*L)->next!=NULL) {//遍历链表 LNode *p=(*L)->next; //p指示头结点的下一个，要被删除的结点 (*L)->next=p->next; //让头结点指向p的下一个，把p从链表断开 free(p); //删除p } }

时间复杂度：

时间复杂度为O(n)

四、完整代码实现

#include #include#define TRUE 1 #define FALSE 0typedef struct{ int id; //对应表中的id char name[100]; //对应表中的姓名 char description[200]; //对应表中的描述 }ElemType; //此处的ElemType是个类型名typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; /*初始化*/ int InitList_Link(LinkList *L){ *L=(LinkList)malloc(sizeof(LNode)); //创建头结点，并让头指针指向头结点 if (!(*L)) return FALSE; //分配失败 (*L)->next=NULL; //初始化为空 return TRUE; //初始化成功 }/*头插法创建链表*/ int create_HeadInsert(LinkList *L,ElemType a[],int n){ // InitList_Link(L); LNode *s; //用来指示新创建的结点 int i; for(i=n-1; i>=0; i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历 s=(LinkList)malloc(sizeof(LNode)); //创建一个新结点 s->data=https://www.it610.com/article/a[i]; //为结点赋值 s->next=(*L)->next; //让该结点指向第一个结点 (*L)->next=s; //让头结点指向该结点 } }/*尾插法创建链表*/ int create_TailInsert(LinkList *L,ElemType a[],int n){ // InitList_Link(L); LNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表 int i; for(i=0; idata=https://www.it610.com/article/a[i]; //为结点赋值 r->next=s; //r始终指向链表的尾端，这里将新结点连接到r的后面 r=s; //r移动到链表尾端 } r->next=NULL; //结束时，最后一个结点的指针域赋值为空 }/*求表长*/ int Length_Link(LinkList L){ int i=0; //空表返回0 while (L->next!=NULL){//遍历，直到尾结点，空表不进入循环 L=L->next; //向后移动一个 i++; //表长加一 } return i; //返回表长 }/*插入*/ int ListInsert_Link(LinkList *L,int i,ElemType e){ int j=0; //空表序号为0 LNode *p=(*L); //p指向头结点 LNode *s; //s用来指示新创建的结点 while (p&&jnext; //向后移动一个 j++; } if(!p||i<1) return FALSE; //序号在无效范围内 s=(LinkList)malloc(sizeof(LNode)); //创建一个新结点 s->data=https://www.it610.com/article/e; //赋值 s->next=p->next; //让该结点指向p（插入位置的前一个结点）的下一个结点 p->next=s; //让p指向该结点 }/*删除*/ int ListDelete_Link(LinkList *L,int i,ElemType *e){ int j=0; //空表序号为0 LNode *p=(*L); //p指向头结点 LNode *q; //q用来指向被删除的结点 while (p->next&&jnext; //向后移动一个 j++; } if (!(p->next)||i<1) return FALSE; //序号在无效范围内 q=p->next; //让q指向被删除的结点 p->next=q->next; //让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开 *e=q->data; //把被删除的结点的值返回 free(q); //释放该结点 return TRUE; //删除成功 }/*按位查找*/ int GetElem_List(LinkList L,int i,ElemType *e){ LNode *p=L; //p指向头结点 int j=0; //空表序号为0 while (p&&jnext; //向后移动一个 ++j; } if(!(p)||i<1)return FALSE; //i不在有效范围内 *e=p->data; //把第i个结点的值用e返回 return TRUE; }/*按值查找*/ int LocateElem_List(LinkList L,ElemType e,int *i){ int j=0; //空表序号为0 while (L->next!=NULL){//遍历链表 L=L->next; //向后移动 j++; //序号加一 if (L->data.id==e.id){//这里我们只用id来判断元素的值是否相等，假设id唯一 *i=j; //如果相等，用i返回序号 return TRUE; //查找成功 } } return FALSE; }/*打印*/ void PrintList_Link(LinkList L){ int i=0; //空表序号为0 while (L->next!=NULL)//遍历表 { L=L->next; i++; printf("第%d行：id=%d,name=%s,description=%s\n",i,L->data.id,L->data.name,L->data.description); } }/*销毁单链表*/ void DestroyList(LinkList *L){ while((*L)->next!=NULL) {//遍历 LNode *p=(*L)->next; (*L)->next=p->next; free(p); } }int main(){ LinkList L; int i=InitList_Link(&L); if(i==1){ printf("初始化成功\n"); } printf("\n"); /// ElemType a[4]={ {1,"史强","最强辅助"}, {2,"章北海","我不需要钢印，我是自己思想的主人"}, {3,"罗辑","人类不感谢罗辑"}, {4,"维德","失去人性，失去很多。失去兽性，失去一切"} }; create_HeadInsert(&L,a,4); //create_TailInsert(&L,a,4); PrintList_Link(L); printf("\n"); /// ElemType e={5,"xxx","xxxxxxxxxxxxxxxxxxxx"}; ListInsert_Link(&L,5,e); PrintList_Link(L); printf("\n"); /// ListDelete_Link(&L,5,&e); PrintList_Link(L); printf("被删除的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description); printf("\n"); /// GetElem_List(L,4,&e); printf("查询到的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description); printf("\n"); // LocateElem_List(L,a[2],&i); printf("查询到的位序为：%d\n",i); printf("\n"); // i=Length_Link(L); printf("表长为：%d\n",i); printf("\n"); // DestroyList(&L); PrintList_Link(L); }

【c语言|单链表（线性表的链式存储）---C语言版】运行结果：

初始化成功第1行：id=1,name=史强,description=最强辅助 第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人 第3行：id=3,name=罗辑,description=人类不感谢罗辑 第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切第1行：id=1,name=史强,description=最强辅助 第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人 第3行：id=3,name=罗辑,description=人类不感谢罗辑 第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切 第5行：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx第1行：id=1,name=史强,description=最强辅助 第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人 第3行：id=3,name=罗辑,description=人类不感谢罗辑 第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切 被删除的元素：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx查询到的元素：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切查询到的位序为：3表长为：4

推荐阅读

• 

  手机微信语音为什么发不出去
• 

  空调为什么要接外边插座,搞懂后也就那么回事
• 

  实现对外接口，要注意哪些问题
• 

  夏季来了，多吃3种食品，降脂减肥，匡助消化，早吃早好
• 

  柯基犬和哈士奇哪个好
• 

  治疗颈椎病的枕头
• 

  双十一的活动时间
• 

  食用黄藤的注意事项及禁忌 食用黄藤的注意事项
• 

  Soapui接口功能测试数据传递
• 

  三十六天罡和七十二地煞是什么？
• 

  安神补肾 刺五加治疗失眠的偏方有哪些？
• 

  qq游戏怎么屏蔽房间对话 我来分享在QQ空间里屏蔽游戏邀请的操作过程
• 

  分析数据分析三种方法,数据分析最为基本的三种方法
• 

  家里空调故障分析,空调故障怎么排除
• 

  白帆布鞋干了有黄渍怎么办
• 

  五花肉用平底锅煎几分钟能熟 五花肉用平底锅煎几分钟
• 

  电脑网络如何桥接
• 

  新鲜冬枣皮可以吃吗
• 

  公司隐名股东向外借款如何起诉？
• 

  售价|三星Galaxy S22新爆料，骁龙898+2亿像素+200倍变焦，售价再创新高

• 数据结构|栈(操作受限的线性表)---C语言版
• c语言|垃圾回收GC经典算法
• 单片机|单片机学会了有出路吗（学单片机有什么用？）
• 蓝桥杯|蓝桥杯 试题 基础练习 杨辉三角形
• 没事就吃树莓派|【树莓派C语言开发】实验05（激光传感器模块）
• #|kuangbin线段树专题
• Codeforces|Codeforces940F Machine Learning (带修莫队)
• 总结|关于c++中的临时变量
• 竞赛习题|蓝桥杯第十二届个人省赛C/C++B组（欢迎大家在底部评论留下自己疑问）