【数据结构】单链表的使用

单链表的使用

- 1、基本概念
- 2、链表的分类
- 3、链表的基本操作
- - a、单链表节点设计
  - b、单链表初始化
  - c、单链表增删节点
  - - **节点头插：**
    - **节点尾插：**
    - **新节点插入指定节点后：**
    - 节点删除：
  - d、单链表修改节点
  - e、单链表遍历，并打印数据
- 4、链表优缺点
- 5、完整示例代码

1、基本概念

顺序表：顺序存储的线性表。
链式表：链式存储的线性表，简称链表。
既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所谓的链表。

顺序表和链表在内存在的基本样态如下图所示：

顺序表：

在这里插入图片描述
链表：

2、链表的分类

$\quad$ 根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：
1.单向链表
2.单向循环链表
3.双向循环链表
$\quad$ 这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图如下所示：
在这里插入图片描述上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。
另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。

3、链表的基本操作

节点设计
初始化空链表
增删节点
链表遍历(改查)
销毁链表

下面着重针对这几项常见操作，讲解单向链表的处理。

a、单链表节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外（这里以整型数据为例），只需要增加一个指向本类节点的指针即可，如下所示：

typedef struct single_list{// 数据域--》真实的数据int data;    				// 以整型数据为例// 指针域struct single_list *next; 	// //用来指向下一个元素在内存中的首地址
}single_list_t;

b、单链表初始化

$\quad$ 首先，空链表有两种常见的形式。一种是带头结点的，一种是不带头结点的。所谓的头结点是不存放有效数据的节点，仅仅用来方便操作，如下：
在这里插入图片描述
而不带头结点的空链表如下所示：

$\quad$ 由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，这会给以后的链表操作带来些许便捷。
下面以带头结点的链表为例，展示单向链表的初始化的示例代码：

single_list_t *single_list_init()
{single_list_t *head_node = malloc(sizeof(single_list_t));if (head_node != NULL){head_node->next = NULL;}return head_node;
}

c、单链表增删节点

$\quad$ 相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。
$\quad$ 与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码：

节点头插：

int insert_list_head(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// 插入节点new_node->next = list->next;list->next = new_node;return 0;
}

节点尾插：

int insert_list(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// 定义指针p去找到链表的尾部single_list_t *p = list;while (p->next != NULL){p = p->next;}// 此时p已经到最后一个节点的位置p->next = new_node;return 0;
}

新节点插入指定节点后：

int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的节点single_list_t *p = list;while (p->next != NULL){p = p->next;if (p->data == olddata) // 待插入的节点在链表中间{break;}}// 申请一个新的节点 single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// p指向最后一个节点if (p->next == NULL){// 最后一个节点是要插入的节点if (p->data == olddata){new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点p->next = new_node;   // 再将该节点指向新增加的节点}else{printf("要插入的数据不存在\n");return -1;}}else // 遍历到中间找到需要插入的节点{new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点p->next = new_node;   // 再将该节点指向新增加的节点}return 0;
}

节点删除：

int list_delnode(int deldata, single_list_t *list)
{single_list_t *q = list;single_list_t *p = list->next;while (p->next != NULL){// 找到要删除的节点并进行删除if (p->data == deldata){q->next = p->next;  // 将q指向的节点指向被删除节点的下一个节点p->next = NULL;     // p节点的next指针指向NULLfree(p);    // 释放p后此时p是野指针p = q->next;// 将p指向被删除节点的下一个节点}else{p = p->next;q = q->next;}  }// 遍历到最后一个节点if (p->next == NULL){// 若最后一个节点是要删除的节点，则删除if (p->data == deldata){q->next = p->next;p->next = NULL;free(p);}else{printf("最后一个节点不是要删除的节点\n");return 0;}}
}

d、单链表修改节点

int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;  // p指向下一个节点if (p->data == old_data){p->data = new_data;}}return 0;
}

e、单链表遍历，并打印数据

int list_show(single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;printf("当前p指向的节点数据:%d\n", p->data);}
}

4、链表优缺点

$\quad$ 链式存储中，所有节点的存储位置是随机的，他们之间的逻辑关系用指针来确定，跟物理存储位置无关，因此从上述示例代码可以很清楚看到，增删数据都非常迅速，不需要移动任何数据。另外，又由于位置与逻辑关系无关，因此也无法直接访问某一个指定的节点，只能从头到尾按遍历的方式一个个找到想要的节点。简单讲，链式存储的优缺点跟顺序存储几乎是相对的。
总结其特点如下：

优点
a.插入、删除时只需要调整几个指针，无需移动任何数据
b.当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存
c.当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快
缺点
a.在节点中，需要多余的指针来记录节点之间的关联
b.所有数据都是随机存储的，不支持立即访问任意一个随机数据。

5、完整示例代码

#include <stdio.h>
#include <stdlib.h>// 1.封装一个结构体来表示单链表
typedef struct single_list{int data;struct single_list *next;
}single_list_t;// 2.初始化单链表-->定义结构体变量 创建头节点
single_list_t *single_list_init()
{single_list_t *head_node = malloc(sizeof(single_list_t));if (head_node != NULL){head_node->next = NULL;}return head_node;
}// 头插
int insert_list_head(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// 插入节点new_node->next = list->next;list->next = new_node;return 0;
}
/*@brief:3.插入数据-->尾插(在最后一个有效成员的后面插入数据)*@param(in):  newdata :待插入的数据  list:待插入的链表*@param(out):  *@retval:    
*/
int insert_list(int newdata, single_list_t *list)
{// 申请一个节点 -堆空间single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// 定义指针p去找到链表的尾部single_list_t *p = list;while (p->next != NULL){p = p->next;}// 此时p已经到最后一个节点的位置p->next = new_node;return 0;
}// 中间插入
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的节点single_list_t *p = list;while (p->next != NULL){p = p->next;if (p->data == olddata){break;}}// 申请一个节点 -堆空间single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化数据域new_node->data = newdata;new_node->next = NULL;// p指向最后一个节点if (p->next == NULL){if (p->data == olddata){new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点p->next = new_node;   // 再将该节点指向新增加的节点}else{printf("要插入的数据不存在\n");return -1;}}else // 遍历到中间找到需要插入的节点{new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点p->next = new_node;   // 再将该节点指向新增加的节点}return 0;
}
// 删除节点
int list_delnode(int deldata, single_list_t *list)
{single_list_t *q = list;single_list_t *p = list->next;while (p->next != NULL){// 找到要删除的节点并进行删除if (p->data == deldata){q->next = p->next;  // 将q指向的节点指向被删除节点的下一个节点p->next = NULL;     // p节点的next指针指向NULLfree(p);    // 释放p后此时p是野指针p = q->next;// 将p指向被删除节点的下一个节点}else{p = p->next;q = q->next;}  }// 遍历到最后一个节点if (p->next == NULL){// 若最后一个节点是要删除的节点，则删除if (p->data == deldata){q->next = p->next;p->next = NULL;free(p);}else{printf("最后一个节点不是要删除的节点\n");return 0;}}
}
// 修改节点
int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;  // p往后移动if (p->data == old_data){p->data = new_data;}}return 0;
}// 4.遍历链表,打印节点数据
int list_show(single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;printf("当前p指向的节点数据:%d\n", p->data);}
}int main(int argc, char const *argv[])
{// 初始化单链表single_list_t *my_list = single_list_init();// 往链表插入数据insert_list(15, my_list);insert_list(18, my_list);insert_list(15, my_list);insert_list(25, my_list);insert_list(666, my_list);insert_list(123, my_list);insert_list(11111111, my_list);insert_list_mid(666, 777, my_list);insert_list_mid(1, 222, my_list);insert_list_head(15, my_list);printf("============插入的节点============\n");list_show(my_list);printf("============插入的节点============\n");// 删除节点list_delnode(25,my_list);printf("============删除后的节点============\n");list_show(my_list); // 打印数据printf("============删除后的节点============\n");// 修改数据list_update_node(123, 234, my_list);printf("============修改后的节点============\n");list_show(my_list); // 打印数据printf("============修改后的节点============\n");return 0;
}
/*
执行结果：
要插入的数据不存在
============插入的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:25
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
============插入的节点============
最后一个节点不是要删除的节点
============删除后的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
============删除后的节点============
============修改后的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:234
当前p指向的节点数据:11111111
============修改后的节点============
*/