中国建设银行北京市互联网网站,做付费网站好,中国建工社微课程官网,国内永久免费服务器#x1f493;博主个人主页:不是笨小孩#x1f440; ⏩专栏分类:数据结构与算法#x1f440; 刷题专栏#x1f440; C语言#x1f440; #x1f69a;代码仓库:笨小孩的代码库#x1f440; ⏩社区#xff1a;不是笨小孩#x1f440; #x1f339;欢迎大家三连关注… 博主个人主页:不是笨小孩 ⏩专栏分类:数据结构与算法 刷题专栏 C语言 代码仓库:笨小孩的代码库 ⏩社区不是笨小孩 欢迎大家三连关注一起学习一起进步 复杂链表OJ 链表的分类带头双向循环链表的实现结构接口有哪些呢初始化打印链表尾插头插尾删头删查找在pos前面插入删除pos位置的数据销毁链表 链表和顺序表的区别用随机指针复制列表 链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1.单向or双向
2.带头or不带头哨兵位头结点
3.循环or不循环 它们组合起来一共有8种结构虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1.无头单向非循环链表 这个链表我们前面已经讲过了想详细了解的可以去看单链表详解。
2.带头双向循环链表 这个是我们本章节的重点下面细讲。
总结 1.无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2.带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 带头双向循环链表的实现
结构 既然是双向那么这个结构体种就需要两个指针一个用来存储下一个节点的指针一个用来存储上一个节点的指针。 typedef int LTDateType;typedef struct ListNode
{//存储数据LTDateType date;//保存下一个节点的地址struct ListNode* next;//保存上一个节点的地址struct ListNode* prev;
}ListNode;
接口有哪些呢
// 创建返回链表的头结点.初始化
ListNode* ListCreate();// 双向链表销毁
void ListDestory(ListNode* pHead);// 双向链表打印
void ListPrint(ListNode* pHead);// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDateType x);// 双向链表尾删
void ListPopBack(ListNode* pHead);// 双向链表头插
void ListPushFront(ListNode* pHead, LTDateType x);// 双向链表头删
void ListPopFront(ListNode* pHead);// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDateType x);// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDateType x);// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);接下来我们来一一实现
初始化 我们这里讲的是带头双向循环链表所以我们在初始化的时候由于只有一个哨兵位头结点所以我们直接让他的next和prev先指向自己里面的数据可以是任何数。 // 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* node (ListNode*)malloc(sizeof(ListNode));//判断是否开辟成功if (node NULL){perror(malloc fail);exit(-1);}//初始化node-next node;node-prev node;node-date 0;return node;
}打印链表 打印链表很简单只需要遍历链表就可以了但是这里的头结点是哨兵位不需要遍历所以我们从phead的next开始由于他是循环的所以到phead结束。 // 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){printf(%d-, cur-date);cur cur-next;}printf(\n);
}尾插 由于插入数据我们都需要开辟新的节点所以我们下一个函数专门来创建节点 ListNode* BuyListNode(int x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail);exit(-1);}//节点里面的指针可以初始化为NULL因为他们暂时无任何指向。newnode-date x;newnode-next NULL;newnode-prev NULL;return newnode;
}有了节点以后我们可以利用pHead的prev找到尾并保存在tail中然后开始改变链接关系让tail-next指向newnodenewnode-prev指向tail,然后将pHead-prev指向newnodenewnode-next指向pHead。在没有节点的情况下同样使用这就体现了结构的优势。 // 双向链表尾插
void ListPushBack(ListNode* pHead, LTDateType x)
{assert(pHead);ListNode* newnode BuyListNode(x);ListNode* tail pHead-prev;tail-next newnode;newnode-next pHead;pHead-prev newnode;newnode-prev tail;
}头插 头插同样需要新的节点有了新的节点以后我们保存pHead-next到first中去然后改变链接关系将first-prev指向newnode,将newnode-next指向first将newnode的prev指向pHead,将pHead的next指向newnode。 // 双向链表头插
void ListPushFront(ListNode* pHead, LTDateType x)
{assert(pHead);ListNode* newnode BuyListNode(x);newnode-prev pHead;newnode-next pHead-next;pHead-next-prev newnode;pHead-next newnode;
}尾删 尾删我们可以先保存一下尾节点在保存尾节点的前一个节点然后释放尾节点在改变链接关系将新的尾节点的next指向pHead将pHead的prev指向新的尾。 // 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//链表为空就别删了assert(pHead-next ! pHead);//保存尾节点ListNode* tail pHead-prev;//保存尾节点的前一个节点ListNode* tailPrev tail-prev;//释放尾节点free(tail);//改变链接关系tailPrev-next pHead;pHead-prev tailPrev;
}头删 我们保存第一个节点也就是pHead-next到first中去然后改变链接关系将pHead-next改为first-next然后将first后面的一个节点的prev,也就是first-next-prev改为pHead然后释放first即可。 // 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead);ListNode* first pHead-next;pHead-next first-next;first-next-prev pHead;free(first);
}
查找 查找和打印的方法一样遍历链表找到就返回该节点找不到返回NULL。 // 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDateType x)
{ListNode* cur pHead-next;while (cur ! pHead){if (cur-date x){return cur;}cur cur-next;}return NULL;
}在pos前面插入 我们可以先保存pos前面的的节点到posPrev中去在开辟一个新的节点然后改变链接关系将posPrev-next改为newnode然后将newnode-prev指向posPrev然后将newnode-next指向pos最后将pos-prev指向newnode即可。 // 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDateType x)
{assert(pos);ListNode* posPrev pos-prev;ListNode* newnode BuyListNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}删除pos位置的数据 删除就更简单了只需要将pos前一个节点的next指向pos的next将pos的下一个节点的prev指向pos的prev然后释放pos即可。 // 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);
}销毁链表 遍历链表依次销毁最后销毁头即可。 // 双向链表销毁
void ListDestory(ListNode* pHead)
{ListNode* cur pHead-next;while (cur ! pHead){ListNode* del cur;cur cur-next;free(del);}free(pHead);
} 双向带头循环链表到这里基本上就讲完了它的结构复杂但是代码写起来比起单链表还是非常简单的接下来我们来比较一下链表和顺序表的区别。 链表和顺序表的区别 下图是缓存的一些知识 用随机指针复制列表 如果我们单纯的拷贝一个链表那非常简单只需要遍历原链表在遍历的同时开辟新的节点存储原链表的值然后将新的节点尾插起来就可以了。 但是这个题目出除了需要拷贝这个以外每个结构中还有一个random指针他们在原链表中指向原链表的任意节点或者空我们还要拷贝这个但是问题是我们在新的链表中无法找到原链表中random所对应的新的链表中的地址所以我们原链表中找random的同时还有在新的链表中找对应的random这是比较麻烦的而且时间复杂度是ON^2效率也低。 这里我们还有另外一个方法就是我们先将每个节点都拷贝一份放个拷贝的节点放在对应节点的后面将他们重新链接起来我们的问题就是找不到random对应的节点的地址这样我们的节点的next即使random对应节点的地址然后我们将拷贝的链表摘下来尾插起来形成新的链表同时恢复原链表这样就可以了这样做时间复杂度是O(N)而且没有额外的空间损耗是个非常厉害的思路。 第一步
第二步; 改变拷贝链表的random的值他就是原链表的random的next。
第三步 就是恢复链表并且将拷贝的拿来尾插成新的链表。
代码如下
struct Node* copyRandomList(struct Node* head)
{struct Node* cur head;//第一步插入copywhile(cur){struct Node* next cur-next;struct Node* copy (struct Node*)malloc(sizeof(struct Node));//拷贝copy-val cur-val;//改变链接关系cur-next copy;copy-next next;//cur迭代cur copy-next;}cur head;//第二步改变copy的randomwhile(cur){struct Node* copy cur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-random cur-random-next;}cur copy-next;}//第三步 尾插并且恢复原链表cur head;struct Node* copyhead NULL,*copytail NULL;while(cur){struct Node* copy cur-next;struct Node* next copy-next;//尾插copyif(copyheadNULL){copyheadcopytailcopy;}else{copytail-next copy;copytail copytail-next;}//恢复原链表cur-next next;cur next; }return copyhead;
}今天的分享就到这里感谢大家的关注和支持。
