数据结构——顺序表和单向链表(2)

前言

一、单向链表

1、基本概念

2、单向链表的设计

（1）节点设计

（2）初始化空单向链表

（3）、初始化数据节点

（4）数据节点

（5）判断链表是否为空

（6）遍历链表

（7）删除数据

（8）销毁整个链表

（9）修改数据

前言

        在软件的世界里，程序 = 数据结构 + 算法。这句广为流传的名言，深刻地揭示了数据结构的核心地位。它是我们组织、存储和管理数据的艺术，是构建高效、稳定应用程序的基石。而在众多数据结构中，线性表作为最基础、最常用的一种，其重要性不言而喻。

        顺序表和单向链表，正是线性表两种最经典的实现方式。它们如同“一体两面”，代表了计算机中两种最根本的物理存储思想：连续的空间与离散的空间。

顺序表凭借其底层连续的物理结构，带来了无与伦比的随机访问性能，仿佛一本页码清晰的书籍，我们可以根据目录瞬间翻到任何一页。然而，这种连续性的代价便是在中间进行插入或删除时，可能引发大规模的“数据搬迁”，效率堪忧。

单向链表则巧妙地利用指针，将离散的内存空间“串联”起来。它牺牲了随机访问的能力，换来了在任意位置高效插入与删除的灵活性，如同一条环环相扣的链条，只需改变节点的指向，即可轻松完成结构的调整。

        理解二者的内在原理、优缺点以及适用场景，是每一位开发者内功修炼的必经之路。这不仅是为了应对面试官的考问，更是为了在未来的开发中，能够根据实际需求，做出最合理的技术选型，写出性能更优、更优雅的代码。

一、单向链表

1、基本概念

概念：

链式存储的线性表，简称链表(线性关系+链式存储)

图解：

说明：

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

2、单向链表的设计

1、节点设计
2、初始化空单向链表(初始化头节点)
3、初始化数据节点
4、增删查改单向链表// 前提：判断链表是否为空a、增：头插法、尾插法b、查：遍历链表c、删：删除链表中的某个数据、销毁整个链表d、改：修改链表中的某个数据

（1）节点设计

说明：

单向链表节点包含两个域，一个数据域一个指针域，数据域存放用户的数据，指针域指向本节点或指向相邻下一个节点。

typedef struct node
{// 数据域int data;  // 指针域struct node* next_p;    // 指向相邻的下一个节点的指针}node_t, *node_p;

（2）初始化空单向链表

概念：

首先链表有两种常见的形式，一种是带有所谓的头节点的，一种是不带头节点的，所谓的头节点是不存放有效数据的节点，仅仅用来方便操作

图解：

注意：

头节点head_node是可选的，为了方便某些操作，建议大家有头节点好一些

头节点的指针：head_node的next_p

说明：

由于头节点不存放有效数据的，因此如果空链表中带有头节点，那么头指针(head_node的next_p)将永远不变，这会给以后的链表操作带来些许便捷

图解：

示例代码：

/*** @brief  初始化空单向链表(初始化头节点)* @note   None* @param  None* @retval 成功：返回指向这个头节点的指针*         失败：返回NULL
*/
node_p LINK_LIST_InitHeadNode(void)
{// 1、给头节点申请一个内存空间(堆内存)node_p p = malloc(sizeof(node_t));bzero(p, sizeof(node_t));// 2、将头节点的next_p指针指向NULLif ( p!= NULL){// 数据域// 指针域p->next_p = NULL;   // 防止指针乱指}else{return NULL;}// 3、成功返回头节点return p;
}

（3）、初始化数据节点

说明：

数据节点

图解：

示例代码：

/*** @brief  初始化数据节点* @note   None* @param  data：数据节点中的数据* @retval 成功：返回指向这个数据节点的指针*         失败：返回NULL
*/
node_p LINK_LIST_InitDataNode(int data)
{// 1、给数据节点申请一个内存空间(堆内存)node_p p = malloc(sizeof(node_t));bzero(p, sizeof(node_t));// 2、将数据节点的next_p指针指向NULL，并且将传进来的数据对此节点的数据进行赋值if ( p != NULL){// 数据域p->data   = data;   // 数据赋值// 指针域p->next_p = NULL;   // 防止指针乱指}else{return NULL;}// 3、成功返回数据节点return p;}

（4）数据节点

说明：

将数据节点插入到链表中，一种头插法(链表中的头节点的后面插进去)，一种尾插法(链表中的最后一个节点后面插入进去)

图解：

头插法：

尾插法：

示例代码：

/*** @brief  插入数据(头插法)* @note   None* @param  head_node：头节点*         new_node： 要插入的数据节点* @retval None
*/
void LINK_LIST_InsertHeadDataNode(node_p head_node, node_p new_node)
{// 1、先让new_node里面的next_p指向data_node  (head_node->next_p里面有data_node的地址)new_node->next_p = head_node->next_p;// 2、再让head_node里面的next_p指向new_nodehead_node->next_p = new_node;
}/*** @brief  插入数据(尾插法)* @note   None* @param  head_node：头节点    *         new_node： 要插入的数据节点* @retval None
*/
void LINK_LIST_TailInsertDataNode(node_p head_node, node_p new_node)
{// 1、设置一个中间指针，将指针指向单向链表的末尾节点node_p tmp_p = NULL;for (tmp_p = head_node; tmp_p->next_p != NULL; tmp_p = tmp_p->next_p);// 2、让tmp_p的next_p指向新节点tmp_p->next_p = new_node;// 3、再让new_node的next_p指向NULLnew_node->next_p = NULL;
}

（5）判断链表是否为空

说明：

如果头节点的next_p指向的是NULL，那么就可以证明这个链表是空的

图解：

示例代码：

/*** @brief  判断链表是否为空* @note   None* @param  head_node：头节点    * @retval 如果链表为空：返回true*         如果链表非空：返回false
*/
bool LINK_LIST_IfEmpty(node_p head_node)
{return head_node->next_p == NULL;
}

（6）遍历链表

说明：

遍历整个链表，并逐个打印里面的数据

图解：

示例代码：

/*** @brief  遍历整个链表并打印出里面的数据* @note   None* @param  head_node：头节点    * @retval 成功：返回0*         失败：返回-1
*/
int LINK_LIST_ShowListData(node_p head_node)
{// 1、判断链表是否为空，是的话，返回-1if (LINK_LIST_IfEmpty(head_node))return -1;// 2、遍历整个链表，并逐个打印里面的数据node_p tmp_p = NULL;int    i     = 0;printf("======================链表中的数据==========================\n");for ( tmp_p = head_node->next_p; tmp_p!=NULL; tmp_p=tmp_p->next_p){printf("链表中的第%d的节点, 数据为: %d\n", i, tmp_p->data);i++;}printf("===========================================================\n");// 3、成功返回0return 0;
}

（7）删除数据

说明：

根据数据来删除链表中的节点

图解：

示例代码：

/*** @brief  删除数据* @note   根据数据的值找到链表中的节点，并将其删除* @param  head_node：头节点  *         del_data： 要删除的数据   * @retval 成功：返回0*         失败：返回-1
*/
int LINK_LIST_DelDataNode(node_p head_node, int del_data)
{// 1、判断链表是否为空，是的话，返回-1if (LINK_LIST_IfEmpty(head_node))return -1;// 2、移动到要删除的节点数据那里去node_p tmp_p     = NULL;node_p last_node = NULL;node_p del_node  = NULL;node_p next_node = NULL;// a、从头到尾遍历一遍，找到要删除的数据for (tmp_p = head_node; tmp_p->next_p!=NULL; tmp_p=tmp_p->next_p){// b、判断要删除的数据if ( (tmp_p->next_p->data) == del_data){// c、保存删除数据的上一个节点和下一个节点、及删除节点last_node = tmp_p;del_node  = tmp_p->next_p;next_node = del_node->next_p; break;}}// 3、绕过原链表要删除的节点last_node->next_p = next_node;del_node->next_p  = NULL;// 4、释放要删除节点的资源free(del_node);// 5、成功返回0return 0;}

（8）销毁整个链表

说明：

从头节点开始，将其后面的数据节点一个个删除，最后再删除头节点本身

图解：

示例代码：

/*** @brief  销毁链表* @note   None* @param  head_node：头节点    * @retval None
*/
void LINK_LIST_UnInit(node_p head_node)
{// 1、如果链表为空，那么直接释放头节点空间即可if (LINK_LIST_IfEmpty(head_node)){free(head_node);return;}// 2、node_p tmp_p      = NULL;               // 遍历node_p last_node  = head_node;node_p del_node   = head_node->next_p;node_p next_node  = del_node->next_p;int num = 0;// 如果链表只有一个数据节点if (next_node == NULL){last_node->next_p = next_node;free(del_node);}// 否则else{for (tmp_p = head_node; tmp_p->next_p!=NULL; tmp_p=tmp_p->next_p){// a、删除节点并释放其内存last_node->next_p = next_node;free(del_node);printf("num == %d\n", num);num++;// b、轮回继续del_node  = next_node;next_node = next_node->next_p;}// 少删除了一个节点数据last_node->next_p = next_node;free(del_node);}// 3、释放头节点free(head_node);  
}

（9）修改数据

说明：

通过数据值，找到链表中的节点，并修改里面的数据

图解：

示例代码：

/*** @brief  修改数据* @note   根据数据的值来找到链表中的节点，对里面的数据进行修改* @param  head_node：  头节点  *         data：       要修改的数据*         change_data：修改的数据* @retval 成功：返回0*         失败：返回-1
*/
int LINK_LIST_ChangeNodeData(node_p head_node, int data, int change_data)
{// 1、如果链表为空，那么直接释放头节点空间即可if (LINK_LIST_IfEmpty(head_node))return -1;// 2、遍历整个链表，找到数据的节点，并修该节点的相应的数据node_p tmp_p = NULL;// a、遍历所有可能for (tmp_p = head_node->next_p; tmp_p!=NULL; tmp_p=tmp_p->next_p){// b、找到要修改的数据if ((tmp_p->data) == data)      // 根据学号{tmp_p->data = change_data;  // 修改这个学生的其它信息break;}   }// 3、成功返回0return 0;
}