💟作者简介：大家好，我是锡兰Ceylan_，可以叫我CC ❣️    
📝个人主页：锡兰Ceylan_的博客
🏆博主信息：平凡的大一学生，有着不平凡的梦

        专栏

• 【备战蓝桥，冲击省一】
• 【开卷数据结构】

⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努努力💪

​

目录

🌺链表的定义

🌺链表的存储方式

🌺单链表的初始化

🌺头插法建立单链表

🌺尾插法建立单链表

🌺按序号寻找结点值

🌺按值寻找结点

🌺插入结点

🌺删除结点

🌺链表的定义

线性表的链式存储又称为单链表，其特点是用一组任意的存储单元来存储线性表的数据元素。

为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系，a1除了存储自身的信息之外，还需要存储一个指向其后续内容的信息（一般为后续内容的地址）。这两部分信息组成数据元素ai的存储映像，称为结点。

​

单链表中结点类型的描述如下：

typedef struct LNode//定义单链表结点类型 {ElemType data;//数据元素 struct LNode *next;//指向下一地址 }LNode, *LinkList;

🌺链表的存储方式

整个链表的存取必须从头指针开始进行，头指针指向链表的第一个结点的存储位置。同时由于最后一个元素没有直接后继，则单链表的最后一个结点的指针为空（NULL）

我们来想一想，如果用链表来存储【Ceylan】，它的逻辑状态是什么样的呢？

​

首先应该需要一个头指针L，它指向第一个元素 'C'，通过 'C' 所在结点的信息，可以访问下一节点 'e' 所在位置，以此类推，就可以完整找到整个【Ceylan】

​

🌺单链表的初始化

单链表的初始化就是建立一个新的空的单链表。

🔺实现原理

1️⃣生成新结点作为头结点，用头指针L指向头结点

2️⃣头结点指向空

💬 代码演示

Status InilList(LinkList &L){//构建一个空的链表L L=new LNode;//生成新结点作为头结点，用头指针L指向头结点 L->next=NULL;//头结点指向空 return OK; }

🌺头插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的表头，也就是头结点之后

​

 💬 代码演示

void CreateList_H(LinkList &L,int n){L=new LNode;L->next=NULL; //先建立一个带头结点的空链表 for(int i=0;i>p->data;//输入p结点的数据 p->next=L->next;L->next=p;//将新结点*p插入到头结点之后 }} 

❗️注意：

因为每次插入都是在链表头部，所以应该逆位序输入数据。输入顺序和线性表中的逻辑顺序是相反的。

🌺尾插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的尾部

​💬 代码演示

void CreateList_R(LinkList &L,int n){L=new LNode;//先建立一个带头结点的空链表 r=L;//尾指针指向头结点 for(int i=0;i>p->data;//输入p结点的数据 p->next=NULL;r->next=p;//将新结点*p插入尾结点*r之后 r=p }} 

🌺按序号寻找结点值

🔺实现原理

1️⃣从第一个结点开始，顺指针next逐个向下搜索，直到找到第  i  个结点，

2️⃣若没有找到，返回最后一个指针域NULL

💬 代码演示

LNode *GetElem(LinkList L,int i){int j=1;//计数，初始为1 LNode *p=L->next;//头结点指针赋值给p if(i==0)return L;//若i为 0，返回头指针 if(i<1)return NULL;//若i无效，则返回 NULL while(p&&jnext;j++;}return p;//返回第 i 个结点的指针 } 

LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e)//从第一个结点开始查找数据域为 e 的结点 {p=p->next;}return p;//找到后返回该结点指针，否则返回NULL } 

p=GetElem(L,i-1)//查找插入位置的前驱结点 s->next=p->next;//新结点*s的指针域指向*p的后续结点p->next=s;//令结点*p的指针域指向新的插入的结点*s

p=GetElem(L,i-1)//查找删除位置的前驱结点 q=p->next;//令q指向被删除结点 p->next=q->next;//将*q结点从链中断开 free(q);//释放结点的存储空间