【数据结构】线性表-单链表

编程语言：C++

前言：

• 节点：节点是链表的一个基本单元，包含两部分——数据域和指针域，数据域用于存储数据，指针域存储下一个节点的地址，形成链结。
  

  

• 什么是单链表：n个节点链结成一个链表，即为线性表（a1,a2,a3……）的链式存储结构，每个节点只包含一个指针域的链表叫做单链表。
• 链表组成：头节点、头指针、节点。头结点顾名思义就是第一个节点，并且头结点的数据域一般为空，有时用来存储链表的节点数等信息，在链表中，头结点不是必需要素。头指针就是指向头结点的指针，头指针一般冠以链表的名字，并且头指针是链表的必需要素。
• 空链表：没有任何有效数据的节点的链表。例：
  

  

1. 单链表的创建
   创建单链表之前先要创建节点：
   

   

然后开始创建链表：
我们将创建链表的功能包装成一个函数，参数如下：
第一个参数是我们在函数外创建的一个头指针（也即一张空链表（包含头结点）），第二个参数是我们希望链表所包含的节点个数

在此基础上，我们有两种创建链表的方式：头插法、尾插法。

头插法：
原理如下：将每次创建的新节点插入头节点和上一个创建的节点之间。

• 声明一个指针p（用来生成新节点），和一个计数器变量i
• 初始化一张空链表（也就是创建一个头指针），让头结点指针指向NULL
• 循环：
  ①生成一个新节点赋给p
  ②给节点赋值（例子中生成一个随机数存入p->data）
  ③将节点插入头结点和上一节点之间

代码实现：

尾插法：
原理如下：每次创建的新节点插在上一个节点后面（链表尾部）。

步骤：

• 声明一个指针p（用来生成新节点），声明一个尾指针r（方便往链表尾部插入新节点），一个计数器变量i
• 初始化一张链表（也就是创建一个头指针)，让头结点的指针指向NULL
• 让尾指针r指向头结点
• 循环：
  ①生成一个新节点赋给p
  ②给节点赋值
  ③将节点插入链表尾部
  ④保持尾节点的指针指向NULL（方便作为查找等操作的判断标志）

代码实现：

2. 链表数据的读取
   读取指定节点存取的数据，必需从头结点开始遍历链表，直到找到指定节点然后读取数据。
   步骤：
   ①创建一个指针p（用来遍历链表），和一个计数器i（p当前指向的节点）
   ②让p指向第一个节点开始遍历链表，同时i自增
   ③如果找到了指定节点，则读取节点数据，并反馈信息（以1为例）
   ④如果没找节点，则反馈信息（以返回0为例）
   代码实现：
   

   

3. 单链表数据的插入
   遍历链表到达指定位置后将数据插入即可。
   步骤：
   ①创建指针p（遍历链表），创建指针s（插入的节点），创建计数器变量i
   ②遍历链表，到达指定位置将s插入
   代码实现：
   

   

4. 单链表数据的删除
   用一个指针遍历到达指定节点处，然后进行删除操作（改变节点指针指向，绕过待删除节点即可），并索回所删除的数据。
   步骤：
   ①创建一个指针p遍历链表，创建一个指针辅助删除，一个计数器变量i
   ②遍历至指定位置进行删除操作
   代码实现：
   

   

   
   补充：其实完全可以不需要创建指针q，“q = p->next;p->next = q->next;”两步可用“p->next = p->next->next”替代，效果相同。

注：

• 涉及到改变链表数据的操作时，应当使用引用传递
• 对于链表的各种操作并非一成不变，应当根据实际情况灵活变换

热门相关：帝少宠妻有点甜   修罗武帝   明尊   惹火小辣妻：老公，用力点   美漫之大冬兵