动态速写网站,wordpress 调用豆瓣,下百度安装,自主设计和创建网站目录
1. 双向链表的结构#x1f98a;
2. 实现双向链表#x1f41d;
2.1 要实现的目标#x1f3af;
2.2 创建初始化#x1f98b;
2.2.1 List.h
2.2.2 List.c
2.2.3 test.c
2.2.4 代码测试运行
2.3 尾插打印头插#x1fabc;
思路分析
2.3.1 List.h
2.3.2 List.… 目录
1. 双向链表的结构
2. 实现双向链表
2.1 要实现的目标
2.2 创建初始化
2.2.1 List.h
2.2.2 List.c
2.2.3 test.c
2.2.4 代码测试运行
2.3 尾插打印头插
思路分析
2.3.1 List.h
2.3.2 List.c
2.3.3 test.c
2.3.4 代码测试运行
2.4 尾删头删
2.4.0 思路分析
2.4.1 List.h
2.4.2 List.c
2.4.3 test.c
2.4.4 代码测试运行
2.5 查找数据pos节点后插入删除pos节点
2.5.0 思路分析
2.5.1 List.h
2.5.2 List.c
2.5.3 test.c
2.5.4 代码测试运行
2.6 销毁☄️
2.6.0思路分析
1. 一级指针
2.6.1 List.h
2.6.2 List.c
2.6.3 test.c
2.6.4 代码测试运行
2. 二级指针
2.6.1 List.h
2.6.2 List.c
2.6.3 test.c
2.6.4 代码测试运行
2.7 完整代码
2.7.1 List.h
2.7.2 List.c
2.7.3 test.c
3. 顺序表和双向链表的分析 1. 双向链表的结构 这里的双向链表准确的说是带头双向循环链表 这里的“头节点”指的是“哨兵位”哨兵位节点不存储任何有效元素只是站在这⾥“放哨 的”。 “哨兵位”存在的意义遍历循环链表避免死循环。 注意⚠️ 双向链表的每一个节点存储一个有效数据下一个节点的地址上一个节点的地址 头节点和尾节点有些特殊头节点指向的上一个节点的地址是尾节点尾节点指向的下一个节点的地址是头节点 2. 实现双向链表
2.1 要实现的目标 我们需要多个接口帮助我们实现创建、一系列具体操作、销毁 具体操作包括头部/尾部插入数据、头部/尾部删除数据、打印出双向链表、指定节点之后插入数据、删除指定节点的数据、查找指定节点 2.2 创建初始化
2.2.1 List.h
#includeassert.h
#includestring.h
#includestdbool.htypedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//初始化
ListNode* LTInit();//不用传入参数直接调用接口返回一个头节点 2.2.2 List.c
#includeList.h
//初始化
ListNode* LTInit()//不用传入参数直接调用接口返回一个头节点
{//为头节点申请空间ListNode* phead (ListNode*)malloc(sizeof(ListNode));//判断开辟是否成功if (phead NULL){perror(malloc error!\n);return;}//开辟成功---初始化头节点phead-data -1;//头节点不存储有效数据可以任意赋值//只有哨兵位的时候要实现双向链表不能指向NULL否则无法双向循环所以我们指向自己phead-prev phead-next phead;return phead;
} 2.2.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();
}
int main()
{ListTest();return 0;
} 2.2.4 代码测试运行 2.3 尾插打印头插
思路分析 2.3.1 List.h
//在双向链表中不会改变哨兵位所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);//打印
void LTPrint(ListNode* phead);//头插
void LTPushFront(ListNode* phead, LTDataType x); 2.3.2 List.c
//在双向链表中不会改变哨兵位所以这里都可以传一级指针
// 只改变数据不改变地址//开辟空间
ListNode* ListBuyNode(LTDataType x)
{ListNode* node (ListNode*)malloc(sizeof(ListNode));if (node NULL){perror(malloc error!\n);return;}node-data x;node-next node-prev NULL;return node;
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node ListBuyNode(x);//先处理node的前驱指针和后继指针node-prev phead-prev;node-next phead;//再处理之前的尾节点和pheadphead-prev-next node;phead-prev node;
}//打印
void LTPrint(ListNode* phead)
{//哨兵位不能改变ListNode* cur phead-next;while (cur ! phead)//当cur再次指向phead的时候循环结束{printf(%d-, cur-data);cur cur-next;}printf(\n);
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node ListBuyNode(x);//node插入头节点之后才算头插//先处理node的前驱指针和后继指针node-prev phead;node-next phead-next;//再处理phead和phead-nextphead-next-prev node;phead-next node;
} 2.3.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4
}
int main()
{ListTest();return 0;
} 2.3.4 代码测试运行 2.4 尾删头删
2.4.0 思路分析 2.4.1 List.h
//尾删
void LTPopBack(ListNode* phead);//头删
void LTPopFront(ListNode* phead); 2.4.2 List.c
//尾删
void LTPopBack(ListNode* phead)
{//不能为空链表只有一个哨兵位不能尾删assert(phead(phead-prev!phead||phead-next!phead));ListNode* del phead-prev;//phead-prev就是尾节点//先处理deldel-prev-next phead;//再处理pheadphead-prev del-prev;free(del);del NULL;
}//头删
void LTPopFront(ListNode* phead)
{//不能为空链表只有一个哨兵位不能头删assert(phead (phead-prev ! phead || phead-next ! phead));ListNode* del phead-next;del-next-prev phead;phead-next del-next;free(del);del NULL;
} 2.4.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3
}
int main()
{ListTest();return 0;
} 2.4.4 代码测试运行 2.5 查找数据pos节点后插入删除pos节点
2.5.0 思路分析 2.5.1 List.h
//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);//删除pos节点
void LTErase(ListNode* pos); 2.5.2 List.c
//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node ListBuyNode(x);//nodenode-next pos-next;node-prev pos;//pospos-next node;node-next-prev node;
}//删除pos节点
void LTErase(ListNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
} 2.5.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3ListNode* find LTFind(plist, 1);/*LTPushAfter(find, 4);*/ //LTPrint(plist);//1 4 2 3LTErase(find);LTPrint(plist);//2 3}
int main()
{ListTest();return 0;
} 2.5.4 代码测试运行 2.6 销毁☄️
2.6.0思路分析 一开始的初始化我们直接调用了接口返回头节点进行初始化。我们没有考虑一级指针还是二级指针的问题。 那么最后的销毁又该怎么办是一级指针还是二级指针下面我们一一来尝试 1. 一级指针
2.6.1 List.h
//销毁
void LTDestroy(ListNode* phead); 2.6.2 List.c
//销毁
void LTDestroy(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while(cur!phead){ListNode* next cur-next;free(cur);cur next;}//注意哨兵位还没有释放free(phead);phead NULL;
} 2.6.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 //LTPushFront(plist, 5);//LTPrint(plist);//5 1 2 3 4 //LTPopBack(plist);//LTPrint(plist);//5 1 2 3//LTPopFront(plist);//LTPrint(plist);//1 2 3//ListNode* find LTFind(plist, 1);/*LTPushAfter(find, 4);*/ LTPrint(plist);//1 4 2 3//LTErase(find);//LTPrint(plist);//2 3LTDestroy(plist);}
int main()
{ListTest();return 0;
} 2.6.4 代码测试运行 一级指针 phead的改变不影响plistphead释放之后plist指向已经释放掉的空间——把plist置为空 那么置为空之前还要不要将plist指向的空间再free一次 我们尝试一下 那么再思考一下一级指针是会导致phead的改变不影响plist那么plist是什么没有改变是指plist保存的值没有被改变还是plist的这块空间的地址没有被释放 这里报错指的是plist指向无效地址 注意⚠️ 如果plist的地址没有被释放那么直接freeplist是不会报错的 所以在一级指针的情况下plist的地址已经被释放了没有被置为空的可以理解是plist的地址名称 2.6.5 一级指针的改进---test.c 2. 二级指针
2.6.1 List.h
//销毁
//void LTDestroy(ListNode* phead);
void LTDestroy(ListNode** phead); 2.6.2 List.c
//销毁
void LTDestroy(ListNode** phead)
{assert(phead *phead);ListNode* cur (*phead)-next;while (cur ! *phead){ListNode* next cur-next;free(cur);cur next;}free(*phead);*phead NULL;
} 2.6.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 //LTPushFront(plist, 5);//LTPrint(plist);//5 1 2 3 4 //LTPopBack(plist);//LTPrint(plist);//5 1 2 3//LTPopFront(plist);//LTPrint(plist);//1 2 3//ListNode* find LTFind(plist, 1);///*LTPushAfter(find, 4);*/ LTPrint(plist);//1 4 2 3//LTErase(find);//LTPrint(plist);//2 3//LTDestroy(plist);//plist NULL;LTDestroy(plist);
}
int main()
{ListTest();return 0;
} 2.6.4 代码测试运行 虽然二级指针不用手动将plist置为空 但是更推荐一级指针因为其他接口基本上都是一级指针——保持接口的一致性 2.7 完整代码
2.7.1 List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestring.h
#includestdbool.htypedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//初始化
ListNode* LTInit();//不用传入参数直接调用接口返回一个头节点//在双向链表中不会改变哨兵位所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);//打印
void LTPrint(ListNode* phead);//头插
void LTPushFront(ListNode* phead, LTDataType x);//尾删
void LTPopBack(ListNode* phead);//头删
void LTPopFront(ListNode* phead);//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);//删除pos节点
void LTErase(ListNode* pos);//销毁
void LTDestroy(ListNode* phead); 2.7.2 List.c
#includeList.h
//初始化
ListNode* LTInit()//不用传入参数直接调用接口返回一个头节点
{//为头节点申请空间ListNode* phead (ListNode*)malloc(sizeof(ListNode));//判断开辟是否成功if (phead NULL){perror(malloc error!\n);return;}//开辟成功---初始化头节点phead-data -1;//头节点不存储有效数据可以任意赋值//只有哨兵位的时候要实现双向链表不能指向NULL否则无法双向循环所以我们指向自己phead-prev phead-next phead;return phead;
}//在双向链表中不会改变哨兵位所以这里都可以传一级指针
// 只改变数据不改变地址//开辟空间
ListNode* ListBuyNode(LTDataType x)
{ListNode* node (ListNode*)malloc(sizeof(ListNode));if (node NULL){perror(malloc error!\n);return;}node-data x;node-next node-prev NULL;return node;
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node ListBuyNode(x);//先处理node的前驱指针和后继指针node-prev phead-prev;node-next phead;//再处理之前的尾节点和pheadphead-prev-next node;phead-prev node;
}//打印
void LTPrint(ListNode* phead)
{//哨兵位不能改变ListNode* cur phead-next;while (cur ! phead)//当cur再次指向phead的时候循环结束{printf(%d-, cur-data);cur cur-next;}printf(\n);
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node ListBuyNode(x);//node插入头节点之后才算头插//先处理node的前驱指针和后继指针node-prev phead;node-next phead-next;//再处理phead和phead-nextphead-next-prev node;phead-next node;
}//尾删
void LTPopBack(ListNode* phead)
{//不能为空链表只有一个哨兵位不能尾删assert(phead(phead-prev!phead||phead-next!phead));ListNode* del phead-prev;//phead-prev就是尾节点//先处理deldel-prev-next phead;//再处理pheadphead-prev del-prev;free(del);del NULL;
}//头删
void LTPopFront(ListNode* phead)
{//不能为空链表只有一个哨兵位不能头删assert(phead (phead-prev ! phead || phead-next ! phead));ListNode* del phead-next;del-next-prev phead;phead-next del-next;free(del);del NULL;
}//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node ListBuyNode(x);//nodenode-next pos-next;node-prev pos;//pospos-next node;node-next-prev node;
}//删除pos节点
void LTErase(ListNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}//销毁
void LTDestroy(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while(cur!phead){ListNode* next cur-next;free(cur);cur next;}//注意哨兵位还没有释放free(phead);phead NULL;
} 2.7.3 test.c
#includeList.h
void ListTest()
{ListNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3ListNode* find LTFind(plist, 1);/*LTPushAfter(find, 4);*/ //LTPrint(plist);//1 4 2 3LTErase(find);LTPrint(plist);//2 3LTDestroy(plist);plist NULL;
}
int main()
{ListTest();return 0;
} 3. 顺序表和双向链表的分析
不同点顺序表链表单链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O1不支持ON任意位置插入或者删除元素看你需要搬移元素效率低ON只需要改变指针指向插入动态顺序表空间不够的时候需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁 本次的分享到这里就结束了
PS小江目前只是个新手小白。欢迎大家在评论区讨论哦有问题也可以讨论的
如果对你有帮助的话记得点赞收藏⭐️关注➕
