C++를 이용 하여 더 블 링크 기본 인터페이스 예제 코드 를 실현 합 니 다.

체인 테이블
링크 는 물리 적 저장 장치 에서 비 연속 적 이 고 비 순서 적 인 저장 구조 로 데이터 요소 의 논리 적 순 서 는 링크 의 포인터 링크 순 서 를 통 해 이 루어 진다.체인 테이블 은 일련의 결점(체인 테이블 의 모든 원 소 를 결점 이 라 고 부른다)으로 구성 되 어 있 으 며 결점 은 운행 할 때 동적 으로 생 성 될 수 있다.각 노드 는 두 부분 을 포함한다.하 나 는 데이터 요 소 를 저장 하 는 데이터 필드 이 고 다른 하 나 는 다음 노드 주 소 를 저장 하 는 포인터 필드 이다.선형 표 순서 구조 에 비해 링크 는 삽입 과 삭제 작업 이 비교적 편리 하 다.
본 고 는 주로 C++더 블 링크 의 기본 인 터 페 이 스 를 실현 하 는 데 관 한 내용 을 소개 하고 참고 학습 을 제공 하 며 더 이상 말 하지 않 고 상세 한 소 개 를 해 보 겠 습 니 다.
먼저 그림 을 통 해 단일 체인 표 와 더 블 체인 표 의 구조 차 이 를 간단하게 구분 합 니 다.

단일 체인 표 의 기본 인터페이스 실현 은 참고 할 수 있다단일 체인 표 단순 실현
다음은 더 블 링크 의 기본 인터페이스 실현 이다.

#include <iostream>
#include <assert.h>
using namespace std;

typedef int DataType;

struct ListNode
{
 ListNode* _next;
 ListNode* _prev;
 DataType _data;

 ListNode(DataType x)
  :_next(NULL)
  , _prev(NULL)
  , _data(x)
 {}
};

typedef ListNode Node;

class List
{

public:
 List()
  :_head(NULL)
  ,_tail(NULL)
 {}

 List(const List& l)
  :_head(NULL)
  ,_tail(NULL)
 {
  Copy(l);
 }

 void Copy(const List& l)
 {
  Node* cur = l._head;
  while (cur)
  {
   PushBack(cur->_data);
   cur = cur->_next;
  }
 }

 List& operator=(const List& l)
 {
  Destory();
  Copy(l);
  return *this;
 }

 ~List()
 {
  Destory();
 }

 void Destory()
 {
  if (_head)
  {
   Node* cur = _head;
   while (_head)
   {
    cur = _head;
    _head = _head->_next;
    delete cur;
   }
   _head = _tail = NULL;
  }
 }

 void PushBack(DataType x)
 {
  if (_head == NULL)
  {
   Node* tmp = new Node(x);
   tmp->_next = tmp->_prev = NULL;
   _head = _tail = tmp;
  }
  else
  {
   Node* tmp = new Node(x);
   _tail->_next = tmp;
   tmp->_prev = _tail;
   _tail = tmp;
  }
 }

 void PopBack()
 {
  if (_head == NULL)
  {
   return;
  }
  else if (_head->_next == NULL)
  {
   delete _head;
   _head = _tail = NULL;
  }
  else
  {
   Node* tmp = _tail;
   _tail = _tail->_prev;
   _tail->_next = NULL;
   delete tmp;
  }
 }

 void PushFront(DataType x)
 {
  if (_head == NULL)
  {
   _head = _tail = new Node(x);
  }
  else
  {
   Node* tmp = new Node(x);
   tmp->_next = _head;
   _head->_prev = tmp;
   _head = _head->_prev;
  }
 }

 void PopFront()
 {
  if (_head == NULL)
  {
   return;
  }
  else if (_head->_next == NULL)
  {
   delete _head;
   _head = _tail = NULL;
  }
  else
  {
   Node* tmp = _head;
   _head = _head->_next;
   delete tmp;
   _head->_prev = NULL;
  }
 }

 Node* Find(DataType x)
 {
  Node* cur = _head;
  while (cur)
  {
   if (cur->_data == x)
    return cur;
   cur = cur->_next;
  }
  return NULL;
 }

 //  pos     x
 void Insert(Node* pos, DataType x)
 {
  assert(pos);
  if ((pos == 0) || (pos->_prev == NULL))
  {
   PushFront(x);
  }
  else
  {
   Node* font = pos->_prev;
   Node* tmp = new Node(x);
   tmp->_prev = font;
   tmp->_next = pos;
   font->_next = tmp;
   pos->_prev = tmp;
  }
 }

 //  pos     
 void Erase(Node* pos)
 {
  assert(pos);
  if ((pos == 0) || (pos->_prev == NULL))
  {
   PopFront();
  }
  else if (pos->_next == NULL)
  {
   PopBack();
  }
  else
  {
   Node* font = pos->_prev;
   Node* last = pos->_next;
   font->_next = last;
   last->_prev = font;
   delete pos;
  }
 }

 //       
 void Reverse()
 {
  Node* cur = _head;
  while (cur)
  {
   swap(cur->_next,cur->_prev);
   cur = cur->_prev;
  }
  swap(_head, _tail);
 }


 void Print()
 {
  Node* cur = _head;
  while (cur)
  {
   cout << cur->_data << "->";
   cur = cur->_next;
  }
  cout << "NULL" << endl;
 }

private:
 Node* _head;
 Node* _tail;
};

주:일부 조작 이 실 현 될 때 반드시 각종 상황 을 고려 한 다음 에 상황 의 분 류 를 진행 하여 코드 의 복용 정 도 를 최대한 높 여야 한다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 십시오.저희 에 대한 지지 에 감 사 드 립 니 다.