做网站要费用多少,云南省安宁市建设厅官方网站,手机如何制作小程序,传媒公司做网站编辑_如何?链表的引入
顺序表的优缺点
1、优点:能够直接通过下标进行定位元素#xff0c;访问效率高#xff0c;对元素进行查找和修改比较快
2、不足:插入和删除元素需要移动大量的元素#xff0c;效率较低
3、缺点:存储数据元素有上限#xff0c;当达到MAX后#xff0c;就不能再…链表的引入
顺序表的优缺点
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.hint 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-len1,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,res1);}//按位置修改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;
}
