浅谈【数据结构】链表之单链表

1、什么是数据？

2、什么是结构

3、什么是数据结构？

4、线性结构(线性表）

4.1线性表的物理结构的实现

5、链表

5.1无头结点的单链表

5.2新内容、老面孔

5.3数组和链表的优缺点

5.4链表的概念

5.5链表的创建步骤

5.5.1创建过程

5.5.2尾插法

5.5.3头插法

5.5.4中间插入法

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

在IT界有一个公式：程序=数据结构+算法

1、什么是数据？

数据（data）是客观事物的一个符号表示，在计算机科学中式指所有能够输入到计算机中并能够被计算机程序处理的符号统称。

数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项（data item）组成。数据项是数据不可分割的最小单位。

数据对象（data object）是性质相同的数据元素的集合，是一个数据的子集。

2、什么是结构

结构：数据元素之间的关系的不同性质称之为：结构（structure）

根据数据元素之间的关系的性质不同，通常有四类基本结构：

集合：结构中的数据元素之间，除了“同属于一个集合的关系”之外，就没有其它关系了。
线性结构：（顺序）
树状结构：（层次）
网状结构：（图状）

3、什么是数据结构？

数据结构的形式定义：数据结构是一个二元组

Data_Sturcture = (D,S)

其中：D是数据元素的有限集，S是D上的关系的有限集（数据元素之间的关系的集合）

结构定义中的“关系”描述的是数据元素之间的逻辑关系（指向关系），因此又称之为：“逻辑结构”

“逻辑结构”并不一定是数据元素在计算机中的存储（称为：映像）表示，数据元素存储结构称为：数据的物理结构，又称：“存储结构”。

4、线性结构(线性表）

例子：

26个英文字母（A、B、C、D...Z）

班上同学的学号

日期

...

线性表的数据元素可以是各种各样、但是同一个线性表中的元素必须要具有相同的特性，即同属于同一个数据对象，相邻的元素之间存储序偶关系。

若将线性表记为：（a1、a2、a3....an）那么则会存在以下性质：

存在唯一的一个被称为："第一个"的数据元素
存在唯一的一个被称为：“最后一个”的数据元素
除了第一个元素之外，集合中的每一个数据元素均只有一个前驱结点
除了最后一个元素之外，集合中的每一个数据元素均只有一个后继结点
- 前驱结点：前面有结点
- 后继结点：后面有结点

4.1线性表的物理结构的实现

在计算机中是怎么存储线性表的

顺序结构
- 线性表的顺序表示的是用一组地址连续的存储单元依次存储线性表中数据元素
  - 数组
  - 动态开辟内存空间
链式结构
- 链式结构存储用的存储单元的地址不一定连续的

5、链表

链表：链式存储的线性表

5.1无头结点的单链表

无头结点的单链表：没有头结点的单向的链式存储的线性表。

问题：我们在定义数组的时候，需要规定数组的长度，定义好了就不能修改了。

int a[10]; // 定义了一个元素为int类型的数组，数组大小为10个int类型

// 修改数组的大小

a = malloc(sizeof(int) * 100); // 不行的，因为a是常量指针，不能改变a指向。

链表就是有一个或者是多个结构体通过指针去进行指向关系构成的。

5.2新内容、老面孔

先来看一下下面这种结构体类型（带指针的结构体）

struct data

{

int d_data; // 数据

struct data *p_data; // 指针存储数据元素的地址。在单链表结构里面，存储下一个数据元素的内存地址

};

即想要按需分配，又可以进行灵活的删除和增加元素的时候：链表就可以解决这样的问题。

5.3数组和链表的优缺点

数组：

优点：
- 数组将元素按顺序存放在内存中，而且元素的内存占用都是相同的，因为它的地址连续、所有可以通过下标快速的对数组元素进行访问。
- 内存不会有太多的碎片化
缺点：
- 有可能造成内存资源的浪费
- 数组元素的插入和删除比较复杂
- 有可能内存资源不够用，容易造成段错误（内存越界）

链表：

优点：
- 插入和删除很方便
- 可以按需分配，不会造成空间的浪费
缺点：
- 空间不是连续，访问相对数组而言效率要低很多碎片化比数组要高

获取结构体空间方式：

动态内存开辟：堆空间的内存
- 特性：空间的生存期是随进程持续性，需要手动释放
- 保存空间地址
通过定义变量：栈空间的内存
- 特性：作用域结束，空间就会被系统释放
- 用变量名

5.4链表的概念

链表就是由一个或者是多个包含指针成员变量的结构体，通过其指针变量来指向其他同类型结构体内存地址来形成一种逻辑上的链式的数据结构。我们把每一个结构体实例（变量/空间）称为该链表的：结点（node)

首结点
- 是链表中唯一一个没有前驱结点、只有后继结点的结点。是唯一一个指向其他的结点的结点
- 首结点同时也是整个链表的首地址。
尾结点
- 是链表中唯一一个没有后继结点，只有前驱结点的结点。是唯一一个被其他结点指向的结点。

注意：尾结点的指针成员是指向空的

可以保证尾结点的指针成员不会成为野指针
可以通过判断指针是否指向空来判断是不是查询到了最后一个元素

***无头结点单链表基础示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 申请了一个新结点的空间struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 增加到链表里面:向后增加（尾插法）// 做第一次判断：链表中有没有结点if(newList == nullptr){// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue; // 继续增加新结点}// 搞一个临时指针，来指向首结点struct node *node_ptr = newList;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;}return newList;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct node *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址return 0;
}

5.5链表的创建步骤

每获取一个数据，就一个创建一个结构体空间来存储数据
把数据存放到结构体体空间中
把这个新的结构体加入到链表中

5.5.1创建过程

从无到有的过程：
- 第一个结点诞生，此时首结点和尾结点都是第一个结点本身
从少到多的过程
- 在链表中增加结点，可以在链表尾部增加（尾插法）、也可以在链表的中间增加（中间插入法）、也可以在链表头部增加（头插法）
图示：

5.5.2尾插法

新节点增加在链表原尾结点的后面，即链表原尾结点要指向新结点（成为原尾结点的后继结点），然后新结点就代替原尾结点成为新的尾结点

特点：先加入的链表的结点在前面，而后加入结点在后面

5.5.3头插法

新结点在原首结点的前面，即新结点指向首结点（成为原首结点的前驱结点），然后新结点代替原首结点称为新的首结点

特点：先加入链表的结点在后面，后加入链表的结点在前面

5.5.4中间插入法

通过和每个结点数据进行比对，从而找到新结点存放的位置。通过中间插入法创建的链表是有序的。

特点：链表的结点数据是有序的。

***单链表基础操作示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};/*@brief：头部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeHead(struct node *list,int data)
{// list 表示就是一个链表（链表首地址/首结点的地址）头插法其实就是在它的首结点前面插入struct node *newNode = new struct node;newNode->data = data; // 数据存入结点数据域newNode->next = list; // 因为新结点作为新的首结点存入链表，那么原有的首结点就变成了新节点后继结点return newNode; // 返回newNode因为newNode变成了新的首结点了。更新链表的首地址
}/*@brief: 尾部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeTail(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 搞一个临时指针，来指向首结点struct node *node_ptr = list;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;return list;
}/*@brief : 中间插入法@param : list 需要增加数据的链表首地址@param : data 需要增加到链表的数据@return : 链表首地址
*/
struct node *addNodeMid(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 循环比较数据 大到小  小到大// struct node *node_previce = nullptr;// struct node *node_current = list;// 第一种方法两个指针// while(node_current)// {//     if(node_current->data > data)//         break; // 找到插入位置了//     // 把两个指针往后移//     node_previce = node_current;//     node_current = node_current->next;// }// // 进行插入// if(node_previce == nullptr) // 说明需要作为首结点插入（头插入)// {//     // 头插代码// }// else// {//     // 直接插入到node_previce的后面//     newNode->next = node_previce->next; // 要成为node_previce下一个结点的前驱结点//     node_previce->next = newNode; // 然后让newNode成为node_previce的后继结点// }// 第二种方法提前判断struct node *node_ptr = list;// 如果第一个结点就比data大说明要插入到最前面（头插法）if(node_ptr->data > data){// 头插法list = addNodeHead(list,data);return list;} while(node_ptr&&node_ptr->next){std::cout << node_ptr->data << std::endl;if(node_ptr->data < data && node_ptr->next->data >= data) // 大于前一个小于后一个{// 将新结点的next指向当前结点的后继结点node_ptr->nextnewNode->next = node_ptr->next;// 让newNode成为node_ptr的后继结点node_ptr->next = newNode;return list; // 退出增加}// 把指针往后移node_ptr = node_ptr->next;}// 严谨判断一下node_ptr->next是不是为空if(node_ptr->next == nullptr) // 尾插法{node_ptr->next = newNode;}return list;
}/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 做第一次判断：链表中有没有结点if(newList == nullptr){struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue;}// 通过中间插入法增加结点newList = addNodeMid(newList,data);// 通过尾插法增加结点// newList = addNodeTail(newList,data);}return newList;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct node *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址// 删除元素int data = 0;std::cin >> data ;delNodeData(newList,data);// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址return 0;
}