目录
1、顺序表的优缺点
顺序表的优点是：
由于顺序表数据元素的内存地址都是连续的，所以可以实现随机访问，而且不需要多余的信息来描述相关的数据，所以存储密度高。
顺序表的缺点是：
顺序表的数据在进行增删的时候，需要移动成片的内存，另外，当数据元素的数量较多的时候，需要申请一块较大的连续的内存，同时当数据元素的数量的改变比较剧烈，顺序表不灵活。
2、链式存储的线性表
链式存储指的是采用离散的内存单元来存储数据元素，用户需要使用某种方式把所有的数据元素连接起来，这样就可以变为链式线性表，简称为链表，链表可以高效的使用碎片化内存。
顺序表和链式表的区别：顺序表使用连续的内存，链式表使用离散的内存空间。
链表中的每个数据元素的地址是不固定的，所以每个数据元素都应该使用一个指针指向直接后继的内存地址，当然最后一个数据元素没有直接后继，所以最后一个数据元素指向NULL即可，作为用户只需要知道第一个数据元素的内存地址，就可以访问后继元素了。
链式存储，则线性表中每一个数据元素除了存储自身数据之外，还需要额外存储直接后继的地址，所以链表中的每一个数据元素都是由两部分组成：存储自身数据的部分被称为数据域，存储直接后继地址的部分被称为指针域，数据域和指针域组成的数据元素被称为结点（Node）。
链表中的数据元素=数据域+指针域
根据链表的结点的指针域的数量以及根据链表的首尾是否相连，把链式线性表分为以下几种：
- 单向链表
- 单向循环链表
- 双向链表
- 双向循环链表
- 内核链表
这几种链表的使用规则差不多，只不过指针域数量不同。
3、单向不循环链表实现
/*******************************************************
* @file：LinkedList.c
* @brief：单向不循环链表封装
* @author：[email protected]
* @date：2024/06/15
* @version：V1.0
* @attention：
* 头节点不存放数据
* 链表中所有节点的指针域都指向下一个节点
* 链表中最后一个节点的指针域指向NULL
* 链表中所有节点是动态分配内存的
* 链表中所有节点的数据域类型是相同的
* @history
* Date Version Author Notes
* 2024-6-15 0.0.1 demon_xing first version
* Copyright (c) 2024, [email protected] All Rights Reserved.
* *******************************************************/
/*****************************************************************
* @brief:头文件
******************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/*****************************************************************
* @brief:构建数据结构体和节点结构体
******************************************************************/
// 1.构建数据类型(或结构体)
typedef int ElemType;
// 2.构建链表节点结构体
typedef struct LinkedList
{
// 数据域
ElemType data;
// 指针域
struct LinkedList *next;
} LinkedList_t;
/*****************************************************************
* @brief:单向不循环链表函数声明
******************************************************************/
// 3.创建链表
LinkedList_t *creatList();
// 4.判断链表是否为空
bool isEmpty(LinkedList_t *head);
// 5.创建节点
LinkedList_t *creatNode(ElemType data);
// 6.插入节点--头插与尾插
bool insertNode(LinkedList_t *head, ElemType data);
// 7.删除节点
bool DeleteNode(LinkedList_t *head, ElemType data);
// 8.遍历显示链表
void displayNode(LinkedList_t *head);
// 9.销毁链表
bool distroyNode(LinkedList_t *head);
/***********************creatList()************************************
* @functionname:creatList()
* @function:创建链表
* @brief:该函数用于创建链表
* @param
* head：头节点指针
@return:
Sqlist_t* 返回顺序表结构体指针
* @author:demon_xing
* @date:2024/06/15
* @version：V1.0
* @history
* Date Version Author Notes
* 2024-6-15 0.0.1 demon_xing first version
* @note:头节点不存放数据，尾节点指向NULL
**************************END*************************************/
// 1.创建链表
struct LinkedList *creatList()
{
// （1）为链表申请堆内存(头节点)
LinkedList_t *head = (LinkedList_t *)calloc(1, sizeof(LinkedList_t));
// 判断是否申请成功,如果申请失败则返回NULL
if (NULL == head)
{
perror("calloc head is failed");
return NULL;
}
// （2）若申请成功，则初始化成员
// 头节点不存放数据
// head->data = 0;
head->next = NULL;
// （3）返回链表头节点指针
return head;
}
/**************************creatNode()***************************************
* @functionname:creatNode()
* @function:创建节点
* @param:
* data：节点数据
* @return: LinkedList_t* 返回节点指针
* @author:demon_xing
* @date:2024/06/15
* @version：V1.0
* @history
* Date Version Author Notes
* 2024-6-15 0.0.1 demon_xing first version
* @attention:
* （1）为节点申请堆内存
* （2）初始化节点成员
* （3）返回节点指针
*************************END*****************************************/
// 2.创建节点
LinkedList_t *creatNode(ElemType data)
{
// （1）为新节点申请堆内存
LinkedList_t *node = (LinkedList_t *)calloc(1, sizeof(LinkedList_t));
// 判断是否申请成功,如果申请失败则返回NULL
if (NULL == node)
{
perror("calloc node is failed");
return NULL;
}
// （2）若申请成功，则初始化成员
node->data = data;
node->next = NULL;
// （3）返回新节点指针
return node;
}
/***********************isEmpty()******************************************
* @functionname:isEmpty()
* @function:判断链表是否为空
* @param:
* head：头节点指针
* @return: bool
* @author:demon_xing
* @date:2024/06/14 16:49:56
* history
* Date Version Author Notes
* 2024-6-14 0.0.1 demon_xing first version
* @note:
* 如果链表为NULL，则返回true；否则返回false
*************************END*****************************************/
// 3.链表是否为空
bool isEmpty(LinkedList_t *head)
{
if (NULL == head)
{
perror("LinkedList_t is NULL");
return true;
}
return false;
}
/***********************insertNode*******************************
* @functionname:insertNode()
* @function:插入节点
* @param:
* head：头节点指针
* data：要插入的数据
* @return: bool
* @author:demon_xing
* @date:2024/06/14 16:49:56
* history
* Date Version Author Notes
* 2024-6-14 0.0.1 demon_xing first version
* @note:
* 插入节点时，要判断链表是否为空，如果为空则返回false；否则插入节点
* 插入节点时，要先将新节点的next指针指向头节点的next指针所指向的节点
* 然后将头节点的next指针指向新节点，防止数据丢失，最后返回true
* ***********************END***************************************/
// 4.插入节点
bool insertNode(LinkedList_t *head, ElemType data)
{
// 判断链表是否为空,如果为空则返回false
if (isEmpty(head))
{
perror("LinkedList_t is NULL");
return false;
}
// 如果链表不为空，则插入节点
// 创建一个节点
LinkedList_t *node = creatNode(data);
// // 头插法
// node->next = head->next;
// head->next = node;
// 尾插法
LinkedList_t *p = head;
while (!isEmpty(head) && p->next)
{
p = p->next;
}
p->next = node;
node->next = NULL;
// 插入完成返回true
return true;
}
/**************************deleteNode**********************************
* @functionname:deleteNode()
* @function:删除节点
* @param:
* head：头节点指针
* data：要删除的数据
* @return:
* bool 删除成功返回true，删除失败返回false
* @author:demon_xing
* @date:2024/06/14 16:49:56
* history
* Date Version Author Notes
* 2024-6-14 0.0.1 demon_xing first version
* @note:
* 删除节点时，要判断链表是否为空，如果为空则返回false；否则删除节点
* 删除节点时，要遍历查找要删除的数据，如果找到则删除节点，否则返回false
* 删除节点时，通常是将要删除的节点的前一个节点的next指针指向要删除的节点的下一个节点
* 然后释放要删除的节点的内存，最后返回true
*
* 如果删除节点时，要删除头节点，则需要先将头节点的next指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存，最后返回true
* 如果删除节点时，要删除尾节点，则需要先将尾节点的前一个节点的next指针指向NULL，然后释放要删除的节点的内存，最后返回true
* 如果删除节点时，要删除中间节点，则需要先将尾节点的前一个节点的next指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存，最后返回true
* 删除节点时，通常需要通过指针变量指向头节点，然后通过遍历查找要删除的数据，如果找到则删除节点，否则返回false
* 原因是：如果通过头节点直接删除节点，则需要先将头节点的next指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存，最后返回true
* 在删除节点时，需要修改链表的头指针，使得链表的头指针指向新的头节点。如果不使用指针变量指向头节点，直接在函数内部修改头节点，会导致修改不生效。
* 遍历链表时，需要使用指针变量指向当前节点，然后通过遍历查找要删除的数据，如果找到则删除节点，否则返回false。
* ***************************END*********************************/
// 5.删除节点
bool deleteNode(LinkedList_t *head, ElemType data)
{
// 判断链表是否为空
if (isEmpty(head))
{
perror("LinkedList is NULL");
return false;
}
// 如果链表不为空，则删除节点
if (isEmpty(head) == false)
{
// 定义一个指针指向头节点
LinkedList_t *p = head;
// 遍历查找要删除的数据，如果未找到要删除的数据，则将p指向p->next继续查找数据，直到找到该数据为止
while (p->next->data != data)
{
p = p->next;
}
// 找到该数据之后，定义一个指针q指向要删除的节点
LinkedList_t *q = p->next;
// p指向要删除的数据的前驱，p->next指向要删除的数据,q指向要删除的节点,则q->next指向要删除的节点的下一个节点
// p q=p->next q->next
p->next = q->next;
q = NULL; // 防止野指针
}
} /**************************displayNode********************************************
* @functionname:displayNode()
* @function:遍历链表
* @param:
* head：头节点指针
* @return:
* void
* @author:demon_xing
* @date:2024/06/14 16:49:56
* history
* Date Version Author Notes
* 2024-6-14 0.0.1 demon_xing first version
* @note:
* 遍历链表,如果链表为空则返回false,否则遍历链表,将链表中的数据依次输出
* ***************************END*****************************************/
// 6.遍历显示链表
void displayNode(LinkedList_t *head)
{
if (isEmpty(head))
{
perror("LinkedList is NULL");
return;
}
// 定义一个结构体指针变量p指向头节点的下一个节点
LinkedList_t *p = head->next;
// 如果头节点的下一个节点不为空，则遍历链表，将链表中的数据依次输出
while (NULL != p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
/*************************distroyNode****************************************
* @functionname:distroyNode()
* @function:销毁链表
* @param:
* head：头节点指针
* @return:
* bool 销魂成功返回true，销魂失败返回false
* @author:demon_xing
* @date:2024/06/14 16:49:56
* history
* Date Version Author Notes
* 2024-6-14 0.0.1 demon_xing first version
* @note:
* notes
* *************************END************************************************/
// 7.销毁链表
bool distroyNode(LinkedList_t *head)
{
// 判断链表是否为空,如果为空则返回false
if (isEmpty(head))
{
perror("LinkedList_t is NULL");
return false;
}
// 如果链表不为空，则释放节点内存和链表内存
free(head);
}
// 8.测试代码
int main(int argc, char *argv[])
{
// （1）创建链表
LinkedList_t *head = creatNode(10);
// （2）插入节点
insertNode(head, 50);
insertNode(head, 40);
insertNode(head, 30);
insertNode(head, 20);
// （3）遍历显示
displayNode(head);
// （4）删除节点
deleteNode(head, 50);
// （5）遍历显示
displayNode(head);
// （6）销毁节点
distroyNode(head);
// 遍历显示，如果段错误则说明销毁成功
// 也可以用valgrind内存检测工具或内存泄漏检测器来证所有的内存已经被正确释放，确保没有内存泄漏。
displayNode(head);
return 0;
}