单链表
1.带头节点的单链表
前置知识
先展示下链表的样子(这里我加了了个count 给写成了结构体) (count用来统计链表中的节点数量)
1.插入相关
插入新节点：1.引入辅助指针p，p找到待插入位置的前一个位置
2.创建新节点
3.更新新节点
4.最后更新老节点任意位置的插入，找到这个位置，效率低
头结点上插入（非常快直接插效率高），尾插入 先找到第n个元素然后再插（效率低）
- 引入辅助指针p，p找到待插入位置的前一个位置 ------> node_t *p=前驱节点
- 创建新节点 ------> node_t *new_node = malloc(sizeof(node_t));
3.更新新节点 ------> new_node->next = p->next;
- 最后更新老节点 p->next = new_node
1.引入辅助指针p，p找到待插入位置的前一个位置
2.创建新节点
3.更新新节点
4.最后更新老节点
node_t *p=前驱节点
node_t *new_node = malloc(sizeof(node_t))
new_node->next = p->next;
p->next = new_node
2.删除相关
删除某个节点：1.引入辅助指针p，p找到待删除位置的前一个节点
2.引入辅助指针备份待删除位置 tmp
3.修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表
4.删除tmp
-
引入辅助指针p，p找到待删除位置的前一个节点 ------> node_t *p = 前驱节点
-
引入辅助指针备份待删除位置 tmp ------> node_t *tmp = p->next;
- 修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表 ------> p->next = tmp->next;
- 删除tmp ------> free(tmp);
1.引入辅助指针p，p找到待删除位置的前一个节点
2.引入辅助指针备份待删除位置 tmp
3.修改前驱节点的 next 指针，跳过待删除节点，重新连接链表
4.删除tmp
node_t* p = 前驱节点
node_t* tmp = p->next;
p->next = tmp->next;
free(tmp);
3.额外补充一点(备份思想)
//如果我们把插入的代码反过来写呢
p->next = new_node
new_node->next = p->next;
//可以看到完全错误 //p->next在第一步就被更新了 即c的位置找不到了
换句话说就是c的位置特别的重要 即p->next的位置 一旦更改了就找不到后面节点的位置了 所以我们要先备份c的位置
new_node->next = p->next; //这一步相当于在备份p->next (等号右边)
p->next = new_node //备份了就可以用了
删除相关的代码也也用到了备份思想 这里就不过多赘述了
有些人一旦错过就不在
头文件部分
#include <stdio.h>
#include <stdlib.h>typedef int Element_t;
//1 定义链表的节点结构
typedef struct _node {Element_t val; //该节点的数据域struct _node* next; //指向下一个节点的指针
} node_t;//2 定义带头节点的链表头结构
typedef struct {node_t head;int count; //存储链表中的节点的数量
}LinkList_t;//1 创建头节点
LinkList_t *createLinkList();
//2 销毁单链表
void releaseLinkList(LinkList_t *table); //3 头插
int insertLinkListHeader(LinkList_t *table, Element_t val);
//4 在指定的pos位置插
int insertLinkListPos(LinkList_t *table, int pos, Element_t val);
//5 删除链表中的一个指定的值
int deleteLinkListElement(LinkList_t *table, Element_t val);
//6 显示单链表中的所有的内容
void showLinkList(const LinkList_t *table);
实现
1.创建头节点
LinkList_t* createLinkList() {//申请头节点LinkList_t* table = NULL; table = malloc(sizeof(LinkList_t));if (table == NULL) {return NULL;}//头节点初始化table->head.val = 0;table->head.next = NULL;table->count = 0;//返回该头节点return table;
}
2.销毁单链表
void releaseLinkList(LinkList_t *table) {if (table) {//从头节点后的第一个节点开始删除node_t* p = &table->head; //定义辅助指针node_t* temp; while (p->next) {//删除相关代码temp = p->next;p->next = temp->next;free(temp);//删除后减少链表中的节点数量--table->count;}//节点删除完后 看下链表中的节点数量 正确应该为0printf("LinkList have %d node! \n", table->count);//最后释放头节点free(table);}
}
3.头插
int insertLinkListHeader(LinkList_t* table, Element_t val) {//引入辅助指针p 指向头节点 可以把头节点当成要插入节点的前一个位置 node_t* p = &table->head; //申请新节点的空间node_t* new_node = malloc(sizeof(node_t)); if (new_node == NULL) {return -1;}//插入代码 new_node->val = val;new_node->next = p->next;p->next = new_node;//头插后 增加链表中节点的数量++table->count;return 0;
}
4.在指定的pos位置插
int insertLinkListPos(LinkList_t* table, int pos, Element_t val) {// 1. 判断边界值if (pos < 0 || pos > table->count) {printf("insert pos invalid!\n");return -1;}// 2. 找到pos - 1索引的节点首地址node_t *p = &table->head; int index = -1; //头节点的位置认为为-1//开始循环while (index < pos - 1) {// 遍历链表，找到 pos-1 位置的节点p = p->next;++index;}if (p == NULL) {return -1;}//循环结束index的位置在待插入位置的请一个位置 即此时index=pos-1//p在插入待位置的前一个位置//申请新节点的空间node_t *new_node = malloc(sizeof(node_t));//插入代码new_node->val = val;new_node->next = p->next;p->next = new_node;//插入后 增加链表中节点的数量++table->count;return 0;
}
5. 删除链表中的一个指定的值
int deleteLinkListElement(LinkList_t* table, Element_t val) {//引入辅助指针指向头节点node_t* p = &table->head; //向后遍历单链表中的节点while (p->next) { // 判断下一节点是否为待删除目标值if (p->next->val == val) {//找到了指定的要删除的节点(值) 退出循环break;}p = p->next;}if (p->next == NULL) {printf("Not Find!\n");return -1;}//此时就找到了待删除的节点 即p->next指的位置 p是待删除节点的前驱节点//删除代码 node_t* temp = p->next; p->next = temp->next; free(temp); //删除节点后 减少链表中节点的数量--table->count;return 0;
}
6.显示表中的所有的内容
void showLinkList(const LinkList_t* table) //这里加const是因为 该链表是只读的不可修改
{//引入辅助指针p (这里指向的是要展示的第一个节点 ) node_t* p = table->head.next; printf("link List: %d\n", table->count);//向后遍历单链表中的节点 并 打印while (p) {printf("%d ", p->val); p = p->next;}printf("\n");
}
测试案例
main函数
void test01() {printf("link Table!\n");//创建带头结点的空链表LinkList_t* table = createLinkList();if (table == NULL) {return ;}//循环头插10个节点for (int i = 0;i < 10;i++) {insertLinkListHeader(table, i + 100);}//插入指定位置节点insertLinkListpos(table, 1, 520);showLinkList(table);printf("=============================\n");//根据值删除指定的节点deleteLinkListElement(table, 520);//展示整个表中节点的值showLinkList(table);//释放整个表releaseLinkList(table);
}int main()
{test01();return 0;
}
输出结果
link Table!
link List: 11
109 520 108 107 106 105 104 103 102 101 100
=============================
link List: 10
109 108 107 106 105 104 103 102 101 100
LinkList have 0 node!
2.带头指针的单链表
前置知识
处理带头指针的单链表 最万金油的思路 ：引入辅助节点，充当头节点 用完就扔掉它
(所谓带头指针的单链表就是 头指针指向第一个节点)
先展示下链表的样子(这里我加了了个count 给写成了结构体) (count用来统计链表中的节点数量)
引入辅助节点，充当头节点
1.插入相关
插入新节点：
1.引入辅助节点，充当头节点
2.引入辅助指针p，p找到待插入位置的前一个位置
3.创建新节点
4.更新新节点
5.最后更新老节点
node_t dummy; //辅助头节点 放到栈区用完自动回收
dummy.next = header; //此时dunmmy.next 就指向链表中的第一个元素//这一部分就和带头节点的插入代码一样了
node_t *p = &dummy;
node_t* new_node = malloc(sizeof(node_t));
new_node->next = p->next;
p->next = new_node;// 辅助头节点(dummy)是栈局部变量，函数结束会自动销毁，需把新链表表头同步给原链表
table->header = dummy.next;
2.删除相关
删除某个节点：
1.引入辅助节点，充当头节点
2.引入辅助指针p，p找到待删除位置的前一个节点
3.引入辅助指针备份待删除位置 tmp
4.修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表
5.删除tmp
node_t dummy; //辅助头节点 放到栈区用完自动回收
dummy.next = table->header; //此时dunmmy.next 就指向链表中的第一个元素//这一部分就和带头节点的删除代码一样了
node_t* p = &dummy;
while(p){... p = p->next ...}; //找到待删除节点的前一个节点
node_t* tmp = p->next;
p->next = tmp->next;
free(tmp);// 辅助头节点(dummy)是栈局部变量，函数结束会自动销毁，需把新链表表头同步给原链表
table->header = dummy.next;
头文件部分
#include <stdio.h>
#include <stdlib.h>typedef int Element_t;
//1 定义链表的节点结构
typedef struct _node {Element_t val; //该节点的数据域struct _node* next; //指向下一个节点的指针
} node_t;//2 定义带头指针的链表头结构
typedef struct {node_t* header;int count;
}ChainList_t;//1 表头放到数据区 放到全局变量 (换一个思想)
void initChainList(ChainList_t* table);
//2 销毁该链表的元素区域，头置空
void destoryChainList(ChainList_t* table); //3 头插
int insertChainListHeader(ChainList_t* table, Element_t val);
//4 在指定的pos位置插
int insertChainListpos(ChainList_t* table, int pos, Element_t val);
//5 删除链表中的一个指定的值
int deleteChainListElement(ChainList_t* table, Element_t val);
//6 显示链表中的所有内容
void showChainList(const ChainList_t* table);
实现
带头指针的代码由于和带头节点的代码高度相似 注释尽量简略了 只写些主要的理清逻辑
1.初始化头节点
void initChainList(ChainList_t* table)
{table->count = 0;table->header = NULL; //初始表中没节点 置空
}
2.销毁单链表
void destoryChainList(ChainList_t* table) {node_t dummy;dummy.next = table->header; //删除代码node_t* p = &dummy;node_t* temp;while (p->next) {temp = p->next;p->next = temp->next;free(temp);--table->count;}printf("LinkList have %d node! \n", table->count);table->header = NULL; //头置空
}
3.头插
int insertChainListHeader(ChainList_t* table, Element_t val) {node_t dummy;dummy.next = table->header; //插入代码node_t* p = &dummy; node_t* new_node = malloc(sizeof(node_t)); if (new_node == NULL) {return -1;}new_node->val = val;new_node->next = p->next;p->next = new_node;++table->count;//更新table->header = dummy.next; return 0;
}
4.在指定的pos位置插
int insertChainListpos(ChainList_t* table, int pos, Element_t val) {node_t dummy;dummy.next = table->header;//1 判断边界值if (pos<0 || pos>table->count) {printf("insert pos invalid");return -1;}//2 找到pos-1索引的节点地址node_t* p = &dummy; int index = -1;while (index < pos - 1) {p = p->next;++index;}if (p == NULL) {return -1;}//插入代码node_t* new_node = malloc(sizeof(node_t));new_node->val = val;new_node->next = p->next;p->next = new_node;++table->count;//更新table->header = dummy.next;return 0;
}
5. 删除链表中的一个指定的值
int deleteChainListElement(ChainList_t* table, Element_t val) {node_t dummy;dummy.next = table->header;node_t* p = &dummy;while (p->next) { if (p->next->val == val) {break;}p = p->next;}/* while (p->next && p->next->val != val) {p = p->next;} */if (p->next == NULL) {printf("Not Find!\n");}//删除代码node_t* temp = p->next;p->next = temp->next;free(temp);--table->count;//更新table->header = dummy.next;return 0;
}
6.显示表中的所有的内容
void showChainList(const ChainList_t* table) //这里加const是因为 该链表是只读的不可修改
{node_t* p = table->header; printf("link List: %d\n", table->count);while (p) {printf("%d ", p->val);p = p->next;}printf("\n");
}
测试案例
main函数
//带头指针的单向链表测试//ChainList_t stu1;
void testc02() {ChainList_t stu1;//初始化带头指针的单链表initChainList(&stu1); //循环头插10个节点for (int i = 0;i < 10;i++) {insertChainListHeader(&stu1, i + 100);}//展示整个表中的节点showChainList(&stu1);//指定位置插入节点 并展示表中的节点insertChainListpos(&stu1, 1, 520);showChainList(&stu1);printf("=============================\n");//根据值删除指定的节点deleteChainListElement(&stu1, 520);//展示整个表中的节点showChainList(&stu1);//销毁该表的元素区域 头置空destoryChainList(&stu1);
}int main()
{test02();return 0;
}
输出结果
link List: 10
109 108 107 106 105 104 103 102 101 100
link List: 11
109 520 108 107 106 105 104 103 102 101 100
=============================
link List: 10
109 108 107 106 105 104 103 102 101 100
LinkList have 0 node!
嘻嘻嘻嘻 单链表部分到此结束😆😆
(有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖