四川建设行政主管部门官方网站,代理网页是干什么的,湖南优度网络科技有限公司,让芯片公司得到尊重的是原创技术目录
双链表的定义与接口函数
定义双链表 接口函数 详解接口函数的实现
创建新节点#xff08;BuyLTNode#xff09;
初始化双链表#xff08;ListInit#xff09;
双向链表打印#xff08;ListPrint#xff09;
双链表查找#xff08;ListFind#xff09;
双链…
目录
双链表的定义与接口函数
定义双链表 接口函数 详解接口函数的实现
创建新节点BuyLTNode
初始化双链表ListInit
双向链表打印ListPrint
双链表查找ListFind
双链表销毁ListDestory 1、双链表pos位置之前插入ListInsert 2、双链表删除pos位置ListEarse 3、双向链表尾插ListPushBack 4、双向链表头插ListPushFront 5、双链表头删ListPopFront 6、双链表尾删ListPopBack
总结
完整代码
链表OJ练习巩固 前言
为了更好地理解本节建议先阅读 数据结构 - c语言链表操作 实际中要实现的链表的结构非常多样以下情况组合起来有多种链表结构 单向、双向 带头、不带头 循环、非循环解读 带头 存在一个哨兵位的节点该节点不存储任何有效数据属于无效节点但通过这个无效节点当头节点让我们在某些方面使用会有一些优势。 双向 指的是节点中不再只有一个指针而是有两个指针一个指向前一个节点另一个指向后一个节点。 循环 尾指针不再指向NULL而是指向头节点。 然而现实中实用的只有两种分别是无头单向非循环链表带头双向循环链表。 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口insert 和 earse 头尾的插入和删除就可以搞定了双链表的定义与接口函数 定义双链表
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode; 接口函数
void ListPrint(LTNode* phead);
//void ListInit(LTNode** pphead);
LTNode* ListInit();
LTNode* BuyLTNode(LTDataType x);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);// 在pos之前插入
void ListInsert(LTNode* pos, LTDataType x);
//void ListInsert(int i, LTDataType x);// 删除pos位置的节点
void ListErase(LTNode* pos);
void ListDestory(LTNode* phead); 详解接口函数的实现 创建新节点BuyLTNode
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
} 初始化双链表ListInit
LTNode* ListInit()
{LTNode* phead BuyLTNode(0);phead-next phead;phead-prev phead;return phead;
}
这里我们使用 BuyLTNode 函数开辟一块空间作为 哨兵位 pHead 最后将其进行一个初始化。最后再将 pHead 作为结果返回回去外面就可以接收到了。这就是返回值的方法当然这里也可以采用二级指针的方法来完成。 双向链表打印ListPrint
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n\n);
} 双链表查找ListFind
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
} 双链表销毁ListDestory
void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;//ListErase(cur);free(cur);cur next;}free(phead);//phead NULL;
} 1、双链表pos位置之前插入ListInsert
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);/*LTNode* newnode BuyLTNode(x);pos-prev-next newnode;newnode-prev pos-prev;pos-prev newnode;newnode-next pos;*/LTNode* newnode BuyLTNode(x);LTNode* posPrev pos-prev;newnode-next pos;pos-prev newnode;posPrev-next newnode;newnode-prev posPrev;
}非常简单假设d2是新节点就是让新节点的两条链接在d3上然后把d1的两条链接新节点上 2、双链表删除pos位置ListEarse
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;free(pos);pos NULL;prev-next next;next-prev prev;
}假设要删除d2那么只需要直接把d1的两条链接d3上即可 3、双向链表尾插ListPushBack
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;} 4、双向链表头插ListPushFront
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
} 5、双链表头删ListPopFront
void ListPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);ListErase(phead-next);
} 6、双链表尾删ListPopBack
void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead-next ! phead);LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tail NULL;tailPrev-next phead;phead-prev tailPrev;} 总结
用ListInsert和ListEarse的复用优化后
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead-next ! phead);ListErase(phead-prev);
}void ListPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);ListErase(phead-next);
}void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}
所以双向链表严格来说只需要快速地实现 insert 和 earse 这两个接口就可以搞定了。如果以后让你快速实现一个双向链表你把 pos位置之前插入 和 删除pos位置 这两个接口写好头尾的插入和删除直接复用就可以搞定了。 完整代码 List.h
#pragma once#include stdio.h
#include assert.h
#include stdlib.htypedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;void ListPrint(LTNode* phead);
//void ListInit(LTNode** pphead);
LTNode* ListInit();
LTNode* BuyLTNode(LTDataType x);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);// 在pos之前插入
void ListInsert(LTNode* pos, LTDataType x);
//void ListInsert(int i, LTDataType x);// 删除pos位置的节点
void ListErase(LTNode* pos);
void ListDestory(LTNode* phead); List.c
#includeList.hLTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n\n);
}//void ListInit(LTNode** pphead)
//{
// assert(pphead);
// *pphead BuyLTNode(0);
// (*pphead)-next *pphead;
// (*pphead)-prev *pphead;
//}LTNode* ListInit()
{LTNode* phead BuyLTNode(0);phead-next phead;phead-prev phead;return phead;
}void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);//LTNode* tail phead-prev;//LTNode* newnode BuyLTNode(x);//tail-next newnode;//newnode-prev tail;//newnode-next phead;//phead-prev newnode;ListInsert(phead, x);
}void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead-next ! phead);/* LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tail NULL;tailPrev-next phead;phead-prev tailPrev;*/ListErase(phead-prev);
}void ListPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);ListErase(phead-next);
}void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);/*LTNode* newnode BuyLTNode(x);pos-prev-next newnode;newnode-prev pos-prev;pos-prev newnode;newnode-next pos;*/LTNode* newnode BuyLTNode(x);LTNode* posPrev pos-prev;newnode-next pos;pos-prev newnode;posPrev-next newnode;newnode-prev posPrev;
}// 驼峰法
// 函数和类型所有单词首字母大写
// 变量第一个单词小写后续单词首字母大写
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;free(pos);pos NULL;prev-next next;next-prev prev;
}void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;//ListErase(cur);free(cur);cur next;}free(phead);//phead NULL;
}------------------------------------------------------------------------------#include List.hListNode* BuyListNode(LTDataType x)
{ListNode* node (ListNode*)malloc(sizeof(ListNode));node-data x;node-next NULL;node-prev NULL;return node;
}ListNode* ListCreate()
{ListNode* head (ListNode*)malloc(sizeof(ListNode));head-next head;head-prev head;return head;
}void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){printf(%d-, cur-data);cur cur-next;}printf(\n);
}void ListDestroy(ListNode* pHead)
{ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next;}free(pHead);
}void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode BuyListNode(x);phead tail newnode//ListNode* tail pHead-prev;//tail-next newnode;//newnode-prev tail;//newnode-next pHead;//pHead-prev newnode;ListInsert(pHead, x);
}void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode BuyListNode(x);//ListNode* first pHead-next;//pHead-next newnode;//newnode-prev pHead;//newnode-next first;//first-prev newnode;/*ListNode* newNode BuyListNode(x);newNode-next pHead-next;pHead-next-prev newNode;pHead-next newNode;newNode-prev pHead;*/ListInsert(pHead-next, x);
}void ListPopBack(ListNode* pHead)
{assert(pHead);//ListNode* tail pHead-prev;//ListNode* tailPrev tail-prev;pHead tailPrev tail//tailPrev-next pHead;//pHead-prev tailPrev;//free(tail);/*ListNode* tail pHead-prev;pHead-prev tail-prev;tail-prev-next pHead;free(tail);*/ListErase(pHead-prev);
}void ListPopFront(ListNode* pHead)
{//...ListErase(pHead-next);
}// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev pos-prev;ListNode* newnode BuyListNode(x);// prev newnode posprev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev pos-prev;ListNode* next pos-next;prev-next next;next-prev prev;free(pos);
} 链表OJ练习巩固
138. 复制带随机指针的链表 - 力扣LeetCode 解题思路 此题可以分三步进行 1.拷贝链表的每一个节点拷贝的节点先链接到被拷贝节点的后面 2.复制随机指针的链接拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置 3.拆解链表把拷贝的链表从原链表中拆解出来
class Solution {
public:Node* copyRandomList(Node* head) {// 1.拷贝链表并插入到原节点的后面如图1Node* cur head;while(cur){Node* next cur-next;Node* copy (Node*)malloc(sizeof(Node));copy-val cur-val;// 插入cur-next copy;copy-next next;// 迭代往下走cur next;}// 2.置拷贝节点的random如图2cur head;while(cur){Node* copy cur-next;if(cur-random ! NULL)copy-random cur-random-next;elsecopy-random NULL;cur copy-next;}// 3.解拷贝节点链接拷贝节点如图3Node* copyHead NULL, *copyTail NULL;cur head;while(cur){Node* copy cur-next;Node* next copy-next;// copy解下来尾插if(copyTail NULL){copyHead copyTail copy;}else{ copyTail-next copy;copyTail copy;}cur-next next;cur next;}return copyHead;}
}; 图1 图2
图3 链表知识点题库 - 力扣LeetCode
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推求职就业一站解决_牛客网 (nowcoder.com)
