c/c++开发分享C语言超详细i讲解双向链表

一、双向链表的概念1、概念:概念:双向链表是每个结点除后继指针外还有⼀个前驱指针。双向链表也有带头结点结构和不带头结点结构两种,带头结点的双向链表更为常用;另外,双向链表也可以有循环和非循环两种结构,

一、双向链表的概念

1、概念:概念:双向链表是每个结点除后继指针外还有⼀个前驱指针。双向链表也有带头结点结构和不带头结点结构两种,带头结点的双向链表更为常用;另外,双向链表也可以有循环和非循环两种结构,循环结构的双向链表更为常用。

C语言超详细i讲解双向链表

二、双向链表的实现

头文件list.h

#pragma once  #include<stdio.h>  #include<assert.h>  #include<stdlib.h>  typedef int ltdatetype;  typedef struct listnode  {  	ltdatetype date;  	struct listnode* next;  	struct listnode* prev;  }ltnode;  //void listinit(ltnode** pphead);  void listprint(ltnode* phead);  void listpopback(ltnode* phead);  ltnode* listinit();//初始化  ltnode* buyltnode(ltdatetype x);  void listpushback(ltnode* phead, ltdatetype x);  void listpushfront(ltnode* phead, ltdatetype x);  void listpopfront(ltnode* phead);  ltnode* listfind(ltnode* phead, ltdatetype x);  //在pos前插入  void listinsert(ltnode* pos, ltdatetype x);  //删除pos位置的节点  void listerease(ltnode* pos);  void listdestory(ltnode* phead);

源文件list.c

#include"list.h"  ltnode* buyltnode(ltdatetype x)  {  	ltnode* newnode = (ltnode*)malloc(sizeof(ltnode));  	if (newnode == null)  	{  		printf("malloc failn");  		exit(-1);  	}  	newnode->date = x;  	newnode->next = null;  	newnode->prev = null;  	return newnode;  }  //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 listprint(ltnode* phead)  {  	assert(phead);  	ltnode* cur = phead->next;  	while (cur != phead)  	{  		printf("%d ", cur->date);  		cur = cur->next;  	}  	printf("n");  }  void listpushback(ltnode* phead, ltdatetype x)  {  	assert(phead);  	ltnode* tail = phead->prev;  	ltnode* newnode = buyltnode(x);  	tail->next = newnode;  	newnode->prev = tail;  	newnode->next = phead;  	phead->prev = newnode;  }  void listpushfront(ltnode* phead, ltdatetype x)  {  	assert(phead);  	listinsert(phead->next, x);  }  void listpopback(ltnode* phead)//尾删  {  	assert(phead);  	assert(phead->next != phead);//说明传进来的不只有phead,不然phead被free掉了。  	//ltnode* tail = phead->prev;  	//ltnode* tailprev = tail->prev;  	//free(tail);  	//tail = null;  	//tailprev->next = phead;  	//phead->prev = tailprev;  	listerease(phead->prev);  }  void listpopfront(ltnode* phead)//头删  {  	assert(phead);  	assert(phead->next != phead);  	listerease(phead->next);  }  ltnode* listfind(ltnode* phead, ltdatetype x)  {  	assert(phead);  	ltnode* cur = phead->next;  	while (cur != phead)  	{  		if (cur->date == x)  		{  			return cur;  		}  		cur = cur->next;  	}  	return null;  }  //void listinsert(ltnode* pos, ltdatetype x)  //{  //	assert(pos);  //	ltnode* newnode = buyltnode(x);  //	pos->prev->next = newnode;  //	newnode->prev = pos->prev;  //  //	pos->prev = newnode;  //	newnode->next = pos;  //  //}  //更好的写法  void listinsert(ltnode* pos, ltdatetype x)  {  	assert(pos);  	//无关写的顺序  	ltnode* newnode = buyltnode(x);  	ltnode* posprev = pos->prev;  	newnode->next = pos;  	pos->prev = newnode;  	posprev->next = newnode;  	newnode->prev = posprev;  }  // 驼峰法  //函数和类型所以单词首字母大写  //变量:第一个单词小写后续单词首字母大写  void listerease(ltnode* pos)  {  	assert(pos);  	ltnode* prev = pos->prev;  	ltnode* next = pos->next;  	free(pos);  	//此时要把pos置成空,不然pos就是野指针了  	pos = null;  	prev->next = next;//lt的新的prev指向pos->next;  	next->prev = prev;//lt的新的next的prev指向prev;  }  void listdestory(ltnode* phead)  {  	assert(phead);  	ltnode* cur = phead->next;//从头结点的下一个位置开始。  	while (cur != phead)  	{  		ltnode* next = cur->next;//先记录,再free  		//listerease(cur);//副用erease函数实现destory  		free(cur);//  		cur = next;  	}  	free(phead);  	//phead = null;形参的改变不影响实参  }

三、链表与顺序表的差别

四、链表oj

1、链表中倒数第k个结点_牛客题霸_牛客网(链接)

思路:快慢指针法,fast先走k步, slow和fast同时走, fast走到尾时,slow就是倒数第k个

代码示例:

struct listnode* findkthtotail(struct listnode* plisthead, int k ) {      struct listnode* slow, *fast;      slow = fast = plisthead;      while(k --)//走k步      {          //判断k是否大于链表的长度。          if(fast == null) return null;          fast = fast->next;      }      while(fast)//当fast 指针走到尾时      {          slow = slow->next;          fast = fast->next;      }      return slow;  }  第二种写法:  struct listnode* findkthtotail(struct listnode* plisthead, int k )  {      struct listnode* p1 = null, *p2 = null;      p1 = plisthead;      p2 = plisthead;      int a = k;      int c = 0;//记录节点个数        //p1指针先跑,并且记录节点数,当p1指针跑了k-1个节点后,p2指针开始跑,          //当p1指针跑到最后时,p2所指指针就是倒数第k个节点      while(p1)//当p1 不为空时      {          p1 = p1->next;          c ++;//节点个数增加          if(k < 1) p2 = p2->next;          k --;          }      if(c < a) return null;      return p2;  }

2、21. 合并两个有序链表(链接)

思路:归并的思想,将小的值尾插到新链表。时间复杂度为n^2;如果再定义一个尾指针, 每次记录尾。

C语言超详细i讲解双向链表

C语言超详细i讲解双向链表

struct listnode* mergetwolists(struct listnode* list1, struct listnode* list2)  {      if(list1 == null)//list1和list2分别是两个链表的头指针          return list2;      if(list2 == null)          return list1;      struct listnode* head = null, *tail = null;//head是新链表的头指针,tail是新链表的尾指针      while(list1 && list2)      {              if(list1->val < list2->val)              {                  if(tail == null)//这一步不太理解                  {                      head = tail = list1;                  }                  else                  {                      tail->next = list1;//先传指针指向                      tail = list1;//再把list 的地址传给tail,相当于tail往前挪了一步。                  }                  list1 = list1->next;              }              else              {                  if(tail == null)                  {                      head = tail = list2;                  }                  else                  {                      tail->next = list2;                      tail = list2;//传地址                  }                   list2 = list2->next;              }      }      if(list1)      {          tail->next = list1;//如果链表1不为空,而此时链表二为空,则直接把链表二的值连接过去就好了。      }      if(list2)      {          tail->next = list2;      }      return head;  }  //方法二:设置一个哨兵位头结点  //head存随机值, head->next存第一个链表的值。起到简化代码的作用。  //一般的链表没有设置哨兵位头结点。  struct listnode* mergetwolists(struct listnode* list1, struct listnode* list2)  {      struct listnode* head = null, *tail = null;      head = tail = (struct listnode*)malloc(sizeof(struct listnode));      head->next = null;      while(list1 && list2)      {              if(list1->val < list2->val)              {                      tail->next = list1;//先传指针指向                      tail = list1;//再把list 的地址传给tail,相当于tail往前挪了一步。                  list1 = list1->next;              }              else              {                      tail->next = list2;                      tail = list2;//传地址                      list2 = list2->next;              }      }      if(list1)      {          tail->next = list1;//如果链表1不为空,而此时链表二为空,则直接把链表二的值连接过去就好了。      }      if(list2)      {          tail->next = list2;      }      //解决内存泄漏问题;      struct listnode* list = head->next;      free(head);      return list;  }

3、链表分割_牛客题霸_牛客网(链接)

思路:新设置两个链表,小于x的插到第一个链表,大于x的插到第二个链表。

C语言超详细i讲解双向链表

定义四个指针:lesshead, lesstail,greathead, greattail.

原链表的值分别尾插到这两个链表, 然后分别更新lesstail,和greattail;

最后lesstail的指针再指向greathead。完成两个链表的连接。

想极端场景:

1、所有值比x小

2、所有值比x大

3、比x大和小都有,最后一个值是比x小

4、比x大和小都有,最后一个值是比x大

C语言超详细i讲解双向链表

//构成环链表,造成死循环。  //设置哨兵位  class partition {    public:      listnode* partition(listnode* phead, int x) {          struct listnode* lesshead, *lesstail, *greathead, *greattail;          lesshead = lesstail = (struct listnode*)malloc(sizeof(struct listnode));          greathead = greattail = (struct listnode*)malloc(sizeof(struct listnode));          lesstail->next = greattail->next = null;          struct listnode* cur = phead;          while (cur) {              if (cur->val < x) {                  lesstail->next = cur;                  lesstail = lesstail->next;              } else {                  greattail->next = cur;                  greattail = greattail->next;              }              cur = cur->next;          }          //完成链接工作          lesstail->next = greathead->next;          greattail->next = null;//切断greettail的最后与greethead的链接          struct listnode* list = lesshead->next;          free(lesshead);          free(greathead);          return list;      }  };

4、链表的回文结构_牛客题霸_牛客网(链接)

思路:找出链表的中间节点, 然后逆置,判断前后链表是否一致,若一致,则说明该链表是回文结构。

C语言超详细i讲解双向链表

为什么奇数个时也能过,

例如:1 2 3 2 1

逆置完变为了 1 2 1 2 3 ;

当a走到2的位置时2->next = 3, rhead走到的 2->next = 3, 相等。

class palindromelist {  public:      struct listnode* middlenode(struct listnode* head)  {      struct listnode* slow, * fast;      slow = fast = head;      while(fast && fast->next) //想的是结束的条件,写的是继续的条件      {          slow = slow->next;          fast = fast->next->next;      }      return slow;  }      struct listnode* reverselist(struct listnode* head)  {      struct listnode* newhead = null;      struct listnode* cur = head;      while(cur)      {          struct listnode* next = cur->next;          //头插          cur->next = newhead;//更多代表链表的指向方向。          newhead = cur;//接着把地址传过来(更新)          cur = next;//(更新)      }      return newhead;      }      bool chkpalindrome(listnode* a) {          struct listnode* mid = middlenode(a);          struct listnode*rhead = reverselist(mid);//应该逆置mid,中间结点。          while(a && rhead)          {              if(a->val == rhead->val)              {                  a = a->next;                  rhead = rhead->next;              }              else              {                  return false;              }          }          return true;      }  };

5、力扣相交链表(链接)

思路1:a链表每个节点b跟链表依次比较,如果有相等,就是相交,第一个相等就是交点。

时间复杂度:o(n*m);

思路二:如果两个链表相交,则这两个链表的最后一个元素的地址相同。

包含思路二三:

C语言超详细i讲解双向链表

代码示例:

struct listnode *getintersectionnode(struct listnode *heada, struct listnode *headb)   {      struct listnode* taila, *tailb;//因为之后还要用到heada,和headb,所以要用tail来进行迭代。      taila = heada, tailb = headb;      int lena = 1, lenb = 1;      while(taila)//求出a的尾      {          taila = taila->next;          ++lena;//求出a的长度      }         while(tailb)//求出链表b的尾      {          tailb = tailb->next;          ++lenb;//求出b的长度      }      if(taila != tailb)//如果两个链表的尾不相等,则返回空      {          return null;      }      //相交,求交点,长的先走差距步,再同时找交点。      struct listnode* shortlist = heada, *longlist = headb;//默认a短b长      if(lena > lenb)      {          shortlist = headb;          longlist = heada;      }      int gap = abs(lena - lenb);//求出差距      while(gap--)//减gap次,若是--gap,就是减了gap - 1次      {          longlist = longlist->next;      }      while(shortlist && longlist)      {          if(shortlist == longlist)          return shortlist;//此时shortlist == longlist;          longlist = longlist->next;          shortlist = shortlist->next;      }      //最最关键的一步:就是要在外面返回一个值,因为编译器不会判断代码在哪返回,只会检查你的代码的语法问题。      return null;  }

总结

c/c++开发分享C语言超详细i讲解双向链表分别从双向链表的概念、实现,还比较了顺序表和链表的区别,以及5道链表oj题四个方面介绍了链表进阶的知识,希望大家读后能够有所收获。

到此这篇关于c语言超详细i讲解双向链表的文章就介绍到这了,更多相关c语言双向链表内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C语言超详细i讲解双向链表,都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/1240207.html

(0)
上一篇 4天前
下一篇 4天前

精彩推荐

发表回复

您的电子邮箱地址不会被公开。