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

#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);

#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;形参的改变不影响实参  }

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;  }

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;  }

//构成环链表，造成死循环。  //设置哨兵位  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;      }  };

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;      }  };

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;  }