学习记录——day15 数据结构 链表

链表的引入

顺序表的优缺点

1、优点:能够直接通过下标进行定位元素，访问效率高，对元素进行查找和修改比较快

2、不足:插入和删除元素需要移动大量的元素，效率较低

3、缺点:存储数据元素有上限，当达到MAX后，就不能再添加元素了

链表的概率概念

1、链式存储的线性表叫做链表

        1）链式存储:表示数据元素的存储地址不一定连续

        2）线性表:数据元素之间存在一对一的关系

2、链表的原理

3、链表的基本单位

        1）节点:节点是链表的基本单位，由数据域和指针域组成

        2）数据域:存放数据元素的部分

        3）指针域:存放下一个节点地址的部分

        4）前驱节点:当前节点的上一个节点

        5）后继节点:当前节点的下一个节点

        6）头节点:虚设的一个节点，数据域不存放数据元素，可以存放链表的长度

        7）头指针:指向第一个节点的指针称为头指针

        8）第一个节点:实际存储数据元素的链表上的第一个节点

        注意：头节点的指针域其实就是头指针，也可以单独定义一个指针，指向第一个节点

4、链表的分类

        1）单向链表:只能从头节点或第一个节点出发，单向访问其后继节点的链表称为单向链表

        2）双向链表：双向链表:从头部出发，既可以访问前驱节点，也可以访问后继节点

        3）循环链表:首尾相接的链表称为循环链表

单向链表

        只能从头节点或第一个节点出发，单向访问其后继节点的链表称为单向链表

1、节点结构体类型

        1）头节点和普通节点数据域可以合到一起，使用一格共用体表示

        2）指针域都是指向普通节点的地址

//定义数据类型
typedef int datatype;//定义节点类型
typedef struct Node
{union {int len;datatype data;};struct Node *next; };

2、创建列表

        1）在堆区申请一格头节点的空间，就创建了一个链表

        2）

//创建列表
NodePrt list_create()
{//在堆区申请一个头节点NodePrt L = (NodePrt)malloc(sizeof(Node));if(NULL == L){printf("创建失败\n");  return NULL;}L->len = 0;L->next = NULL;printf("链表创建成功\n");return L;
}

3、申请节点封装数据

        1）需要将要封装的数据当做函数的参数进行传递

        2）同样在堆区申请节点，就传入的数据放入数据域

//申请节点 封装数据
NodePrt apply_node(datatype e)
{//申请节点大小NodePrt p = (NodePrt)malloc(sizeof(Node));if(NULL == p){printf("节点创建失败\n");  return NULL;}//给节点赋值 p->data = e;p->next = NULL;printf("节点创建成功\n");return p;
}

4、链表判空

        1）只需要判断头节点的指针域中是否为空即可

//链表判空
int list_empty(NodePrt L)
{return L->next == NULL;    
}

5、头插

        1）表示将新插入的节点放入第一个节点中

        2）插入数据时，不能先将前面节点与后面节点先断开。

        3）一定要从新节点出发，指向后面的节点，然后将前驱节点指向字节

//头插
int list_inser_head(NodePrt L,datatype e)
{if (NULL == L){printf("链表不合法\n");return -1;}NodePrt p = apply_node(e);if (NULL == p){return -1;}p->next = L->next;L->next = p;L->len++;printf("头插成功\n");return 0;
}

6、链表遍历

        需要使用一个遍历指针，将每一个节点进行遍历一遍，如果该指针指向的节点不为空，就访问其数据域，向后指向下一数据域

      

//链表遍历
int list_show(NodePrt L)
{if (NULL == L || list_empty(L)){printf("遍历失败\n");return -1;}NodePrt q = L->next;//定义遍历指针从第一个节点出发while(q){//输出数据域printf("%d\t",q->data);q = q->next;//指针指向下一数据域}putchar(10);printf("遍历结束\n");
}

7、通过位置查找节点

        1）参数：链表、位置

        2）返回值：目标节点的地址

        

//查找函数
NodePrt list_search(NodePrt L,int pos)
{if (NULL == L || list_empty(L) || pos < 0 || pos > L->len){printf("查找失败\n");return NULL;}//查找逻辑//定义遍历指针从头节点出发,找目标节点NodePrt q = L;for (int i = 0; i < pos; i++)//如果为0就不需要偏移（找下一个数据域）{q = q->next;}return q;  //将找到节点地址返回
}

8、任意位置插入函数

        1）参数：链表、位置、要插入的元素

        2）返回值：int

        3）注意：必须找到要插入位置的节点的前驱节点，将前驱节点当作头节点，进行头插操作

//任意位置插入
int list_insert_pos(NodePrt L,int pos,datatype e)
{if (NULL == L || pos < 1 || pos > L->len + 1){printf("插入位置不合法\n");return-1;}NodePrt p = apply_node(e);if (NULL == p){return -1;}NodePrt q = list_search(L,pos-1);//位置查找前驱节点（更新头节点）p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;}

9、链表头删

        1）参数：链表

        2）返回值： int

        3）注意：注意:需要将要删除的节点先标记一下，头节点的指针，指向第二个节点后，将标                            记的节点释放

//链表头删
int list_delete_head(NodePrt L)
{if (NULL == L || list_empty(L)){printf("头删失败\n");return -1;}NodePrt p = L->next;L->next = p->next;  //L->next->next;free(p);p =NULL;L->len--;printf("头删成功\n");return 0;
}

10、任意位置删除

        1）参数：链表、要删除的位置

        2）返回值：int

        3）注意：需要找到要删除的节点的前驱节点，将其当作头节点，进行头删逻辑

//任意位置删除
int list_delete_pos(NodePrt L,int pos)
{if (NULL == L || pos > L->len + 1 || pos < 1){printf("删除失败\n");return -1;}NodePrt q = list_search(L,pos-1);NodePrt p = q->next;q->next = p->next;free(p);p = NULL;L->len--;printf("删除成功\n");return 0;
}

11、按值查找返回位置

        1）参数：链表、要查找的值

        2）返回值：元素在链表中的位置

// 按值查找
int list_search_value(NodePrt L, datatype e)
{if (NULL == L || list_empty(L)){printf("查找失败\n");return -1;}NodePrt q = L->next;for (int i = 1; i <= L->len; i++){if (q->data == e){return i;}q = q->next;}printf("值不存在\n");return -1;
}

12、按位置修改

        1）参数：链表、要修改的位置、要更新的值

        2）返回值：int

        3）注意：先通过位置，找到对应的元素，更改该元素中的内容即可
 

//按位置修改
int list_update_pos(NodePrt L,int pos,datatype e)
{if (NULL == L || pos < 1 || pos >L->len || list_empty(L)){printf("按位置修改失败\n");return -1;}// list_search_pos(L,pos)->data = e;NodePrt p = list_search(L,pos);p->data = e;printf("按位置修改成功\n");return 0;
}

13、按值进行修改函数

        1）参数：链表、旧值、新值

        2）返回值：int

        3）思路:先通过旧值找到位置，通过位置进行修改

//按值修改
int list_update_value(NodePrt L,datatype old_e,datatype new_e)
{if (NULL == L ||list_empty(L)){printf("按值修改失败\n");return -1;}int res = list_search_value(L,old_e);if (res == -1){return -1;}list_update_pos(L,res,new_e);printf("按值修改成功\n");return 0;
}

14、链表的反转

        1）参数：链表

        2）返回值：int

        3）注意:在该操作中，没有节点被删除，也没有节点被释放

//反转
void list_reverse(NodePrt L)
{if (NULL == L || list_empty(L) || L->len <= 1){printf("反转失败\n");return ;}NodePrt H = L->next;L->next = NULL;NodePrt p = H;while (H){p = H;H = H->next;p->next = L->next;L->next = p;}printf("反转成功\n");return ;
}//释放内存
void list_dsetroy(NodePrt L)
{if(NULL == L){return;}while (!(list_empty(L))){list_delete_head(L);}free(L);L = NULL;printf("释放成功\n");}

15、链表的释放

        1）参数：链表

        2）返回值：无

        3）注意:需要先将所有的节点内存全部释放后，再将头节点释放

//释放内存
void list_dsetroy(NodePrt L)
{if(NULL == L){return;}while (!(list_empty(L))){list_delete_head(L);}free(L);L = NULL;printf("释放成功\n");}

16、排序

// 排序
int list_sort(NodePrt L)
{if (NULL == L || list_empty(L)){printf("排序失败\n");return -1;}// 遍历NodePrt q = L->next;NodePrt q1 = NULL;while (q){q1 = q->next; // 重置指针位置while (q1){if (q->data > q1->data) // 交换条件{datatype temp = q->data;q->data = q1->data;q1->data = temp;}q1 = q1->next; // 偏移}q = q->next; // 偏移}printf("排序成功\n");return 0;
}

17、去重

// 去重
int list_deduplication(NodePrt L)
{if (NULL == L || list_empty(L)){printf("去重失败\n");return -1;}list_sort(L);// 遍历NodePrt q = L->next;while (q){NodePrt q1 = q->next; // 重置指针位置while (q1){if (q->data == q1->data) // 判断{q1 = q->next;q->next = q1->next;free(q1);  q1 = NULL;L->len--;printf("重复值删除成功\n");}else{q1 = q1->next; // 偏移}}q = q->next; // 偏移}printf("去重成功\n");return 0;
}

18、去重（递归）

 19、有序的连接链表

完整代码

00.h

#ifndef LINKLIST_H
#define LINKLIST_H
#include <myhead.h>
// 定义数据类型
typedef int datatype;// 定义节点类型
typedef struct Node
{union{int len;datatype data;};struct Node *next;} Node, *NodePrt;// 创建列表
NodePrt list_create();// 申请节点 封装数据
NodePrt apply_node(datatype e);// 判空
int list_empty(NodePrt L);// 插入数据
// 头插
int list_inser_head(NodePrt L, datatype e);// 链表遍历
int list_show(NodePrt L);// 查找函数
NodePrt list_search(NodePrt L, int pos);// 任意位置插入
int list_insert_pos(NodePrt L, int pos, datatype e);// 删除
// 链表头删
int list_delete_head(NodePrt L);// 任意位置删除
int list_delete_pos(NodePrt L, int pos);// 按值查找
int list_search_value(NodePrt L, datatype e);//按位置修改
int list_update_pos(NodePrt L,int pos,datatype e);//按值修改
int list_update_value(NodePrt L,datatype old_e,datatype new_e);//反转
void list_reverse(NodePrt L);//释放内存
void list_dsetroy(NodePrt L);//排序
int list_sort(NodePrt L);//去重
int list_deduplication(NodePrt L);//反转（递归
void list_reverse_recursion(NodePrt L);
#endif // !LINKLIST_H

00.c

#include "00.h"// 创建列表
NodePrt list_create()
{// 在堆区申请一个头节点NodePrt L = (NodePrt)malloc(sizeof(Node));if (NULL == L){printf("创建失败\n");return NULL;}L->len = 0;L->next = NULL;printf("链表创建成功\n");return L;
}// 申请节点 封装数据
NodePrt apply_node(datatype e)
{// 申请节点大小NodePrt p = (NodePrt)malloc(sizeof(Node));if (NULL == p){printf("节点创建失败\n");return NULL;}// 给节点赋值p->data = e;p->next = NULL;// printf("节点创建成功\n");return p;
}// 链表判空
int list_empty(NodePrt L)
{return L->next == NULL;
}// 插入数据
// 头插
int list_inser_head(NodePrt L, datatype e)
{if (NULL == L){printf("链表不合法\n");return -1;}NodePrt p = apply_node(e);if (NULL == p){return -1;}p->next = L->next;L->next = p;L->len++;printf("头插成功\n");return 0;
}
// 链表遍历
int list_show(NodePrt L)
{if (NULL == L || list_empty(L)){printf("遍历失败\n");return -1;}NodePrt q = L->next; // 定义遍历指针从第一个节点出发while (q){// 输出数据域printf("%d\t", q->data);q = q->next; // 指针指向下一数据域}putchar(10);printf("遍历结束\n");
}// 查找函数
NodePrt list_search(NodePrt L, int pos)
{if (NULL == L || list_empty(L) || pos < 0 || pos > L->len){printf("查找失败\n");return NULL;}// 查找逻辑// 定义遍历指针从头节点出发,找目标节点NodePrt q = L;for (int i = 0; i < pos; i++) // 如果为0就不需要偏移（找下一个数据域）{q = q->next;}return q; // 将找到节点地址返回
}// 任意位置插入
int list_insert_pos(NodePrt L, int pos, datatype e)
{if (NULL == L || pos < 1 || pos > L->len + 1){printf("插入位置不合法\n");return -1;}NodePrt p = apply_node(e);if (NULL == p){return -1;}NodePrt q = list_search(L, pos - 1); // 位置查找前驱节点（更新头节点）p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;
}// 链表头删
int list_delete_head(NodePrt L)
{if (NULL == L || list_empty(L)){printf("头删失败\n");return -1;}NodePrt p = L->next;L->next = p->next; // L->next->next;free(p);p = NULL;L->len--;printf("头删成功\n");return 0;
}// 任意位置删除
int list_delete_pos(NodePrt L, int pos)
{if (NULL == L || pos > L->len + 1 || pos < 1){printf("删除失败\n");return -1;}NodePrt q = list_search(L, pos - 1);NodePrt p = q->next;q->next = p->next;free(p);p = NULL;L->len--;printf("删除成功\n");return 0;
}// 按值查找
int list_search_value(NodePrt L, datatype e)
{if (NULL == L || list_empty(L)){printf("查找失败\n");return -1;}NodePrt q = L->next;for (int i = 1; i <= L->len; i++){if (q->data == e){return i;}q = q->next;}printf("值不存在\n");return -1;
}// 按位置修改
int list_update_pos(NodePrt L, int pos, datatype e)
{if (NULL == L || pos < 1 || pos > L->len || list_empty(L)){printf("按位置修改失败\n");return -1;}// list_search_pos(L,pos)->data = e;NodePrt p = list_search(L, pos);p->data = e;printf("按位置修改成功\n");return 0;
}// 按值修改
int list_update_value(NodePrt L, datatype old_e, datatype new_e)
{if (NULL == L || list_empty(L)){printf("按值修改失败\n");return -1;}int res = list_search_value(L, old_e);if (res == -1){return -1;}list_update_pos(L, res, new_e);printf("按值修改成功\n");return 0;
}// 反转
void list_reverse(NodePrt L)
{if (NULL == L || list_empty(L) || L->len <= 1){printf("反转失败\n");return;}NodePrt H = L->next;L->next = NULL;NodePrt p = H;while (H){p = H;H = H->next;p->next = L->next;L->next = p;}printf("反转成功\n");return;
}// 释放内存
void list_dsetroy(NodePrt L)
{if (NULL == L){return;}while (!(list_empty(L))){list_delete_head(L);}free(L);L = NULL;printf("释放成功\n");
}// 排序
int list_sort(NodePrt L)
{if (NULL == L || list_empty(L)){printf("排序失败\n");return -1;}// 遍历NodePrt q = L->next;NodePrt q1 = NULL;while (q){q1 = q->next; // 重置指针位置while (q1){if (q->data > q1->data) // 交换条件{datatype temp = q->data;q->data = q1->data;q1->data = temp;}q1 = q1->next; // 偏移}q = q->next; // 偏移}printf("排序成功\n");return 0;
}// 去重
int list_deduplication(NodePrt L)
{if (NULL == L || list_empty(L)){printf("去重失败\n");return -1;}list_sort(L);// 遍历NodePrt q = L->next;while (q){NodePrt q1 = q->next; // 重置指针位置while (q1){if (q->data == q1->data) // 判断{q1 = q->next;q->next = q1->next;free(q1);  q1 = NULL;L->len--;printf("重复值删除成功\n");}else{q1 = q1->next; // 偏移}}q = q->next; // 偏移}printf("去重成功\n");return 0;
}/*// 反转（递归)
void list_reverse_recursion(NodePrt L)
{if (NULL == L || list_empty(L) || L->len <= 1){printf("反转失败\n");return;}}*/

00main.c

#include "00.h"int main(int argc, char const *argv[])
{NodePrt L = list_create();if (NULL == L){printf("error\n");return -1;}// 头插list_inser_head(L, 2024);list_inser_head(L, 2025);list_inser_head(L, 2027);list_inser_head(L, 2023);list_inser_head(L, 2025);list_inser_head(L, 2027);list_inser_head(L, 2023);// 遍历list_show(L);//任意位置插入list_insert_pos(L,2,2028);list_show(L);//尾插list_insert_pos(L,L->len+1,2030);list_show(L);// 头删list_delete_head(L);list_show(L);//任意位置删除list_delete_pos(L,3);list_show(L);//按值查找int res = list_search_value(L,2027);if (res != 0){printf("该值在链表的第%d个位置\n",res+1);}//按位置修改list_update_pos(L,2,1234);list_show(L);//按值修改list_update_value(L,1234,2029);list_show(L);//反转list_reverse(L);list_show(L);//排序list_sort(L);list_show(L);//去重list_insert_pos(L,3,2023);list_insert_pos(L,4,2028);list_insert_pos(L,5,2029);list_show(L);list_deduplication(L);list_show(L);//反转（递归）// list_reverse_recursion(L);// list_show(L);//销毁list_dsetroy(L);L = NULL;list_show(L);return 0;
}