C++循环双链表带头节点

源码如下:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <malloc.h>
//带头节点双向循环
//带头节点优点容易写删除操作 双向优点可以找到节点前一个，循环优点容易找到尾节点
typedef  int LTDateType;

typedef struct ListNode//节点的属性有单和双向之分但是无法区别带头还是不带头
{
	LTDateType _data;
	struct ListNode *_next;
	struct ListNode *_prev;
}ListNode;

typedef struct List
{
	ListNode *_head;
}List;
//函数的声明
void ListInit(List *list);//建立
void ListDestory(List *plist);//销毁
void ListPrint(List *plist);//显示，可以传List型参数但效率低，因为要构造新的List变量

ListNode *BuyListNode();
void ListPushBack(List *plist,LTDateType x);
void ListPopBack(List *plist);
void ListPushFront(List *plist,LTDateType x);
void ListPopFront(List *plist);

ListNode* ListFind(List* plist,LTDateType x);

void ListInsert(ListNode* pos,LTDateType x);//在pos节点前链接值为x的节点
void ListErase(ListNode* pos);
void ListRemove(List* plist,LTDateType x);//找到x的节点删除

int ListSize(List* plist);
int ListEmpty(List* plist);
//函数的实现
ListNode *BuyListNode(LTDateType x)
{
	ListNode *node= (ListNode*)malloc(sizeof(ListNode));
	node->_data = x;
	node->_next = NULL;//初始化要有头尾节点
	node->_prev = NULL;
	return node;
}

void ListInit(List *plist)
{
	assert(plist);
	plist->_head = BuyListNode(-1);
	plist->_head->_next = plist->_head;
	plist->_head->_prev = plist->_head;
}

void ListDestory(List *plist)
{
	assert(plist);
	ListNode* cur = plist->_head->_next;
	ListNode* next ;
	while(cur!=plist->_head)
	{
	    next = cur->_next;
		free(cur);
		cur = next;
	}
	free(plist->_head);
	plist->_head = NULL;

}

void ListPushBack(List *plist,LTDateType x)
{
	assert(plist);
	ListNode* head = plist->_head;
	ListNode* tail = head->_prev;
	ListNode* newnode =   BuyListNode(x);
	tail->_next = newnode;
	newnode->_prev = tail;
	head->_prev = newnode;
	newnode->_next = head;

}

void ListPopBack(List *plist)
{
	ListNode *cur = plist->_head;
	while(cur->_next!=plist->_head)
	{
		cur = cur->_next;
	}
	if(cur!=plist->_head)
	{
	cur->_prev->_next = cur->_next;
	cur->_next->_prev = cur->_prev;
	free(cur);
	cur = NULL;
	}
}

void ListPushFront(List *plist,LTDateType x)
{
	assert(plist);

	ListNode* newnode =   BuyListNode(x);
	ListNode* next = plist->_head->_next;
	plist->_head->_next = newnode;
	newnode->_prev = plist->_head;
	next->_prev = newnode;
	newnode->_next = next;
}

void ListPopFront(List *plist)
{
	assert(plist&& plist->_head->_next!=plist->_head);
	ListNode *cur = plist->_head->_next;
	plist->_head->_next = cur->_next;
	cur->_next->_prev = plist->_head;
	free(cur);

}

void ListPrint(List *plist)
{
	assert(plist&&plist->_head);
	ListNode *cur = plist->_head->_next;
	if(cur!=plist->_head)
	{
	printf("%d->",cur->_data);
		cur = cur->_next;
	}

	while(cur!=plist->_head)
	{
		printf("<-%d->",cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}

ListNode* ListFind(List* plist,LTDateType x)
{
	ListNode *cur = plist->_head;
	while(cur->_next!=plist->_head)
	{
		if(cur->_data == x)
		return cur;
		cur = cur->_next;
	}
	return NULL;
}

void ListInsert(ListNode* pos,LTDateType x)
{
	ListNode* prev = pos->_prev;
	ListNode* cur =BuyListNode(x);
	prev->_next = cur;
	cur->_prev  = prev;
	cur->_next = pos;
	pos->_prev = cur;

}

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* next = pos->_next;
	ListNode* prev = pos->_prev;
	next->_prev = pos->_prev;
	prev->_next = pos->_next;
	free(pos);
}

void ListRemove(List* plist,LTDateType x)
{
	ListNode *cur = ListFind(plist,x);
	if(cur!=NULL)
	{
		ListErase(cur);
	}
}

int ListSize(List* plist)
{
	assert(plist);
ListNode *cur = plist->_head;
int size = 0;

		while(cur->_next!=plist->_head)
	{
		size++;
		cur = cur->_next;
	}
	return size;
}

int ListEmpty(List* plist)
{
	assert(plist);
	ListNode *cur = plist->_head;
	if(cur->_next!=cur)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
//测试函数
void test()
{
	List plist;
	ListInit(&plist);
	ListPushBack(&plist,1);
	ListPushBack(&plist,2);
	ListPushBack(&plist,3);
	ListPushBack(&plist,4);
	ListPushBack(&plist,5);
	ListPrint(&plist);
	ListRemove(&plist,4);
	ListPrint(&plist);
	printf("%d   ",ListSize( &plist));
	ListDestory(&plist);
	ListInit(&plist);
	printf("%d   ",ListEmpty(&plist));
}


//主函数
int main()
{
	test();
}

另有一份模板设定的双链表代码，对模板还不是很熟悉，先放在这，日后再看

• 头文件

  //header.h
  #include<iostream>
  #include <cstdlib>
  
  using namespace std;
  /*
   * 双向循环链表头文件，
   * 其声明中封装有指向链表附加头节点的头x指针first
   */
  
  template<class T>
  struct DbNode
  {
      T data;
      DbNode<T> *pred, *next;
      DbNode(T value, DbNode<T> *a = NULL, DbNode<T> *b = NULL):\
          data(value), pred(a), next(b) {}
      DbNode(DbNode<T> *a = NULL, DbNode<T> *b = NULL):pred(a), next(b) {}
  };
  
  template<class T>
  class Dblist
  {
  private:
      DbNode<T> *first;
  public:
      Dblist(T value);
      ~Dblist()
      {
          makeEmpty();
      }
      void makeEmpty();
      int Length()const;
      bool IsEmpty()
      {
          return (this->first->pred == this->pred);
      }
      DbNode<T> *getHead()const
      {
          return this->first;
      }
      DbNode<T> *Locate(int i, int d);
      DbNode<T> *Search(const T& x);
      bool Insert(int i, const T& x, int d);
      bool Remove(int i, T& x, int d);
      void Print(int d);
  };
  template<class T>
  int Dblist<T>::Length()const
  {
      DbNode<T> *tmp = this->first;
      int i = 1;
      while(tmp->next!=this->first)
      {
          ++i;
          tmp = tmp->next;
      }
      return i;
  }
  template<class T>
  bool Dblist<T>::Remove(int i, T& x, int d)
  {
      DbNode<T> *p = this->Locate(i, d);
      if(!p)
          return false;
      x = p->data;
      if(p==this->first && this->Length()>1)
          this->first = p->next;
      else
          cout<<"仅有头节点的双向循环链表已被删除！请勿在没添加新元素前对其调用。"<<endl;
      p->pred->next = p->next;
      p->next->pred = p->pred;
      delete p;
      return true;
  }
  template<class T>
  DbNode<T>* Dblist<T>::Search(const T& x)
  {
      DbNode<T> *tmp = this->first;
      do
      {
          if(tmp->data==x)
          {
              cout<<"address of x is "<<tmp<<"   x = "<<tmp->data<<endl;
              return tmp;
          }
          tmp = tmp->pred;
      }
      while(tmp!=this->first);
      return NULL;
  }
  template<class T>//定位元素，d=0时从头节点向前(pred)查第i个元素，d!=0时，从头节点向后(next)找第i个元素
  DbNode<T>* Dblist<T>::Locate(int i, int d)
  {
      if(this->first->next==this->first || i==0)
          return this->first;
      int t = 1;
      DbNode<T>* tmp = this->first;
      if(d)               //向后找
      {
          while(tmp->next!=this->first && t!=i)//查找到的条件为，在没把双向循环链表遍历一遍前，t=i
          {
              tmp = tmp->next;
              ++t;
          }
          if(tmp->next==this->first&&t!=i)
              return NULL;
          else
              return tmp;
  
      }
      else                //向前找
      {
          while(tmp->pred!=this->first && t!=i)
          {
              tmp = tmp->pred;
              ++t;
          }
          if(tmp->pred==this->first&&t!=i)
              return NULL;
          else
              return tmp;
      }
  }
  template<class T>
  bool Dblist<T>::Insert(int i, const T& x, int d)
  {
      DbNode<T> *p = this->Locate(i, d);
      if(!p)
          return false;
      DbNode<T> *newnode = new DbNode<T>;
      if(newnode==NULL)
      {
          cout<<"申请内存错误！"<<endl;
          exit(1);
      }
      newnode->data = x;
      if(d)           //p节点后插入
      {
          p->next->pred = newnode;
          newnode->pred = p;
          newnode->next = p->next;
          p->next = newnode;
      }
      else            //p节点前插入
      {
          p->pred->next = newnode;
          newnode->next = p;
          newnode->pred = p->pred;
          p->pred = newnode;
      }
      return true;
  }
  template<class T>
  void Dblist<T>::makeEmpty()
  {
      DbNode<T> *p, *q = this->first->pred;
      while(q != this->first)
      {
          p = q;
          q = q->pred;
          delete p;
      }
  }
  template<class T>
  void Dblist<T>::Print(int d)
  {
      if(d)           //正序打印
      {
          cout<<"Positive order: ";
          DbNode<T> *tmp = this->first;
          while(tmp->next != this->first)
          {
              cout<<tmp->data<<"->";
              tmp = tmp->next;
          }
          cout<<tmp->data<<"->over."<<endl;
  
      }
      else            //逆序打印
      {
          DbNode<T> *tmp = this->first;
          cout<<"Reverse sequence: ";
          while(tmp->pred != this->first)
          {
              cout<<tmp->data<<"->";
              tmp = tmp->pred;
          }
          cout<<tmp->data<<"->over."<<endl;
      }
  }
  
  template<class T>
  Dblist<T>::Dblist(T value)
  {
      this->first = new DbNode<T>(value);
      if(this->first == NULL)
      {
          cerr<<"内存分配错误！"<<endl;
          exit(1);
      }
      this->first->next = this->first->pred = this->first;
  }

• main文件

  //main.cpp
  #include"dlinklist.h"
  
  int main()
  {
      Dblist<int> dl(888);
      dl.Print(0);
      for(int i=1; i<=4; ++i)
      {
          dl.Insert(1, i, 0);
      }
      dl.Print(1);
      int l = 999, k = 0;
      dl.Insert(0, l, 0);
      //int k = 0;
      dl.Print(1);
      dl.Remove(0, k, 0);
      dl.Print(1);
      k = 5;
      dl.Search(k);
      dl.Print(0);
      return 0;
  }

至此，链表的学习就告一段落。