做动图网站,怎样做响应式网站,中国河北建设银行官网招聘网站,logo设计vi这里是只讲干货不讲废话的炽念#xff0c;这个系列的文章是为了我自己以后复习数据结构而写#xff0c;所以可能会用一种我自己能够听懂的方式来描述#xff0c;不会像书本上那么枯燥和无聊#xff0c;且全系列的代码均是可运行的代码#xff0c;关键地方会给出注释^_^
全…这里是只讲干货不讲废话的炽念这个系列的文章是为了我自己以后复习数据结构而写所以可能会用一种我自己能够听懂的方式来描述不会像书本上那么枯燥和无聊且全系列的代码均是可运行的代码关键地方会给出注释^_^
全文1W字
版本C17
编译器Clion 2023.3.24
暂时只给出代码不会涉及到基础知识的讲解 1.链表的定义
1.1定义链表结点
// 链表的核心是定义结点
typedef struct list_node{ // C语言中必须要先声明 list_node,不然编译器会报错C可以忽略这个问题Element value; // 结点存储的数据元素struct list_node *next; // 指向下一个结点的指针
}ListNode; 1.2定义链表头结点
// 链表的表头
typedef struct {ListNode head; // 头结点,通常不存储实际数据,用作链表的起始点int len; // 链表的长度,用于记录链表中实际结点的数量
}LinkList;2.链表的实现函数 2.1.表的创建以及删除
// 创建链表和删除链表
LinkList *createLinkList(); // 创建一个链表void releaseLinkList(LinkList* linkList); // 释放一个链表 2.2.向表中插入元素
// 三种插入方式
int insertLinkList(LinkList *linkList, int pos, Element val); // 任意位置上插入int headInsertLinkList(LinkList *linkList, Element val); // 头插法int tailInsertLinkList(LinkList *linkList, Element val); // 尾插法 2.3.表的展示
void showLinkList(LinkList *linkList); // 显示链表内的元素 2.4.删除表中的元素
int deleteLinkList(LinkList *linkList, Element val); // 删除链表中的特定元素 2.5逆转链表
void reverseLinklist(LinkList *linkList); // 逆转链表 3.实现函数的代码 3.1 createLinkList函数的实现
函数定义
LinkList *createLinkList(); 函数功能
该函数用于创建一个空的链表并返回链表的头结点指针 实现思路
a.申请一个类型为LinkList大小为sizeof(LinkList)的头结点b.判空判断申请是否成功c.初始化LinkList-len 0, LinkList-head.value 0(根据实际情况来定义这个值)d.初始化LinkList-head.next NULLe.返回指向新创建链表头结点的指针 具体实现代码
LinkList *createLinkList() {LinkList *linkList (LinkList *) malloc(sizeof (LinkList));if (!linkList){printf(Malloc linklist failed\n);return NULL;}linkList-len 0; // 表示链表的长度linkList-head.value 0; // 根据具体的场景来定义这个值linkList-head.next NULL;printf(Create linklist success!\n);return linkList;
} 测试代码
int main(){LinkList *linkList createLinkList();return 0;
} 测试结果 3.2 releaseLinkList函数的实现
函数定义
void releaseLinkList(LinkList* linkList); 函数功能
释放链表中的所有节点(包括头节点)避免内存泄漏 实现思路
方法一头删法
a.初始化:
获取链表头结点地址并赋值给 node 指针。
node-next 指向待删除结点的下一个结点用于备份b.循环删除:
循环遍历链表条件为 node-next 不为空。
使用 tmp 指针指向要删除的结点 (node-next)。
将 node 的 next 指针指向 tmp 的下一个结点 (tmp-next)移除 tmp 指向的结点。
释放 tmp 指向的结点内存。
更新链表长度减去 1c.释放头结点:
循环结束后释放头结点的内存
方法二循环删除法
a.初始化:
将 node 指针指向链表的头结点的下一个结点准备开始遍历链表b.循环删除:
使用 while 循环遍历链表直到到达链表末尾。在循环中
备份当前要删除的结点到 tmp 指针
将当前结点的 next 指针指向下一个结点从而将 tmp 指向的结点从链表中移除
释放 tmp 指向的结点的内存
更新链表长度减去 1c.释放头结点:
最后释放头结点的内存 具体实现代码
方法一头删法(不断删除头结点后的那个结点直到为空)
void releaseLinkList1(LinkList *linkList) {if (linkList){ListNode *node linkList-head;// 不断的删除头结点的下一个指向直到为空头删法while (node-next){ListNode *tmp node-next; // 备份要删除的结点node-next tmp-next; // 这里为什么不是node node-next;free(tmp); // 因为这样已经移动了头结点会失去对前一个节点的引用可能导致内存泄露linkList-len--;}printf(Release success! LinkList have %d node\n,linkList-len);free(linkList);}
} 方法二循环删除法
void releaseLinkList2(LinkList *linkList){if (linkList) {ListNode *node linkList-head.next;// 使用循环遍历链表释放除头结点外的每个节点(循环删除法)while (node) {ListNode *tmp node; // 备份当前节点node node-next; // 移动到下一个节点free(tmp); // 释放当前节点linkList-len--;}printf(Release success! LinkList have %d node\n,linkList-len);free(linkList);}
} 测试代码
因为需要知道链表中还剩下多少元素所以先引入加入函数
1.头删法测试代码
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);tailInsertLinkList(linkList, 999);showLinkList(linkList);tailInsertLinkList(linkList, 111);showLinkList(linkList);releaseLinkList1(linkList);return 0;
} 2.循环删除法测试代码
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);tailInsertLinkList(linkList, 999);showLinkList(linkList);tailInsertLinkList(linkList, 111);showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 测试结果
1.头删法测试结果 2.循环删除法测试结果 3.3 insertLinkList headInsertLinkList tailInsertLinkList 函数的实现
函数定义
int insertLinkList(LinkList *linkList, int pos, Element val); // 任意位置上插入int headInsertLinkList(LinkList *linkList, Element val); // 头插法int tailInsertLinkList(LinkList *linkList, Element val); // 尾插法 函数功能
1.insertLinkList
在链表的指定位置插入新节点 2.headInsertLinkList
在链表头部插入新节点 3.tailInsertLinkList 在链表尾部插入新节点 实现思路
1.insertLinkList
a.判断链表是否为空判断插入位置是否合法* 在 pos 的位置上插入就要找到 pos-1 的位置* pos 1 逻辑位置上的插入就定义 cnt 0 是头节点的位置* pos 0 逻辑位置上的插入就定义 cnt -1 是头节点的位置b.通过遍历找到待插入结点的前一个结点c.判断 node 是否为空(逻辑完备性)d.申请结点将新节点 newNode-next 设为 NULL将新节点的 value 设为 vale.将 newNode-next 赋值为 node-next //这两步一定要注意顺序f.将 node-next 赋值为 newNode //这两步一定要注意顺序g.更新链表长度LinkList-len2.headInsertLinkList
a.判断链表是否为空b.申请结点将新节点 newNode-next 设为 NULL将新节点的 value 设为 valc.将 newNode-next 赋值为 LinkList-head.next //这两步一定要注意顺序d.将 LinkList-head.next 赋值为 newNode-next //这两步一定要注意顺序e.更新链表长度LinkList-len 3.tailInsertLinkList
a.判断链表是否为空b.申请结点将新节点 newNode-next 设为 NULL将新节点的 value 设为 valc.判断 LinkList 是否为只有头节点的链表d.如果是只有头节点的链表则直接插入到头节点后*即 LinkList-head.next newNode;e.如果不是则不断循环找到尾节点之后插入到尾节点后*即 node-next newNode;g.更新链表长度LinkList-len具体实现代码
1.insertLinkList
int insertLinkList(LinkList *linkList, int pos, Element val) {if (!linkList){printf(LinkList is null. Insert error!\n);return -1;}if (pos 1 || pos linkList-len 1){printf(Insert position out of range!\n);return -1;}ListNode *node linkList-head;int cnt 0;while (node cnt pos - 1){ // 找到待插入位置的前一个位置node node-next;cnt;}// 判断是找到了pos-1的位置还是遍历完链表都没有找到if (node NULL){ // 为了逻辑完备性多加一段代码printf(Insert position out of range!\n);return -1;}ListNode *newNode (ListNode *) malloc(sizeof (ListNode)); //这段是核心代码newNode-next NULL;newNode-value val;newNode-next node-next; // 这里注意顺序一定要先保存当前结点的下一个结点的位置node-next newNode;linkList-len;return 0;
} 2.headInsertLinkList
int headInsertLinkList(LinkList *linkList, Element val) {if (!linkList){printf(LinkList is null. Insert error!\n);return -1;}ListNode *newNode (ListNode *) malloc(sizeof (ListNode));if (newNode NULL) {printf(Memory allocation failed.\n);return -1;}newNode-next NULL;newNode-value val;newNode-next linkList-head.next;linkList-head.next newNode;linkList-len;return 0;
} 3.tailInsertLinkList
int tailInsertLinkList(LinkList *linkList, Element val) {if (!linkList) {printf(LinkList is null. Insert error!\n);return -1;}ListNode *newNode (ListNode *) malloc(sizeof(ListNode));if (newNode NULL) {printf(Memory allocation failed.\n);return -1;}newNode-value val;newNode-next NULL; // 初始化新节点的 next 指针为空if (linkList-head.next NULL) { // 链表为空直接将新节点插入到头节点linkList-head.next newNode;} else {ListNode *node linkList-head.next;while (node-next ! NULL) { // 找到最后一个节点node node-next;}node-next newNode; // 将最后一个节点的 next 指向新节点}linkList-len;return 0;
} 测试代码
1.insertLinkList
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);insertLinkList(linkList, 5, 888);showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);insertLinkList(linkList,999, 888);showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 2.headInsertLinkList
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 3.tailInsertLinkList
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){tailInsertLinkList(linkList, i100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 测试结果
1.insertLinkList 2.headInsertLinkList 3.tailInsertLinkList 3.4 void showLinkList(LinkList *linkList);
函数定义
void showLinkList(LinkList *linkList); // 显示链表内的元素 函数功能
将链表中的所有元素依次打印到控制台 实现思路
a.判断传入链表是否为空b.定义 node 为头节点后的第一个节点c.遍历链表同时打印node-val直到链表为空具体实现代码
void showLinkList(LinkList *linkList) {if (!linkList){printf(LinkList is null. Show error!\n);return;}ListNode *node linkList-head.next;while (node){printf(%d , node-value);node node-next;}printf(\n);
}测试代码
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 测试结果 3.5 deleteLinkList函数的实现
函数定义
int deleteLinkList(LinkList *linkList, Element val) 函数功能
从链表中删除第一个值为 val 的节点 实现思路
a.判断传入的链表是否为空b.用循环找到待删除节点的 前一个 结点c.判断链表的下一个结点是否为空(逻辑完备性)d.用一个指针 tmp 指向待删除的结点e.将 node-next(待删除结点的前一个结点) 设为 tmp-next(删除结点的下一个结点)f.释放掉 tmp 的空间g.更新链表长度LinkList-len-- 具体实现代码
int deleteLinkList(LinkList *linkList, Element val) {if (!linkList) {printf(LinkList is null. Delete error!\n);return -1;}ListNode *node linkList-head;while (node-next node-next-value ! val){node node-next;}if (!node-next){printf(Find element failed! Delete failed!\n);return -1;}ListNode *tmp node-next; // 注意顺序node-next tmp-next;free(tmp);linkList-len--;return 0;
}测试代码
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);deleteLinkList(linkList, 104);showLinkList(linkList);deleteLinkList(linkList, 100);showLinkList(linkList);deleteLinkList(linkList, 104);showLinkList(linkList);deleteLinkList(linkList, 102);showLinkList(linkList);releaseLinkList2(linkList);return 0;
} 测试结果 3.6 reverseLinklist函数的实现
函数定义
void reverseLinklist(LinkList *linkList); 函数功能
将给定的单链表反转 实现思路
方法一
a.判断当前链表是否为空b.初始化
cur LinkList-head.next (头节点的下一个)
pre NULL
LinkList-head.next NULL (注意cur一定要在之前就要赋值)c.循环
备份当前结点 (pre cur)
移动cur避免丢失 (cur cur-next)
将pre-next LinkList-head.next (不断往头节点后插入结点)
将 LinkList-head.next pre (将头节点指向正确的位置) 方法二
a.判断当前链表是否为空b.初始化
cur LinkList-head.next (头节点的下一个)
nxt NULL
LinkList-head.next NULL (注意cur一定要在之前就要赋值)c.循环
备份下一个结点 (nxt cur-next)
将 cur-next LinkList-head.next (不断往头节点后插入结点)
将 LinkList-head.next cur (将头节点指向正确的位置)
cur nxt (避免结点丢失) 方法三
a. 将链表所有的结点全部压入到栈中(除了头节点)
b. 利用栈先进后出的特性出栈一个元素头节点就连接一个元素
c. 注意使用 尾插法 来连接元素 具体实现代码
方法一(备份当前节点反转当前结点) void reverseLinklist1(LinkList *linkList) {if (!linkList) {printf(LinkList is null. Delete error!\n);return;}ListNode *cur linkList-head.next;ListNode *pre NULL;linkList-head.next NULL;while(cur){pre cur;cur cur-next;pre-next linkList-head.next;linkList-head.next pre;}printf(Reverse success!\n);
} 方法二(备份下一个结点反转当前结点) void reverseLinklist2(LinkList *linkList) {if (!linkList) {printf(LinkList is null. Delete error!\n);return;}ListNode *cur linkList-head.next;ListNode *nxt NULL;linkList-head.next NULL;while (cur){nxt cur-next;cur-next linkList-head.next;linkList-head.next cur;cur nxt;}printf(Reverse success!\n);
}
方法三
这里在栈的部分写到时候放一个链接 测试代码
方法一
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);reverseLinklist1(linkList);releaseLinkList2(linkList);return 0;
}
方法二
int main(){LinkList *linkList createLinkList();for (int i 0; i 5; i){headInsertLinkList(linkList, i100);}showLinkList(linkList);reverseLinklist2(linkList);releaseLinkList2(linkList);return 0;
} 测试结果
方法一 方法二
