数据结构 C++ 实现双链表

link.h 

#ifndef LINK_H
#define LINK_H
#pragma once
#include 

template
class Node{
public:
  T *data;
  Node *pre;
  Node *next;
};

template
class Link{
private:
  Node *pheader;
  Node *pfooter;
  int length;
public:
  // 初始化链表
  Link();
  // 析构
  ~Link();
  // 拷贝构造
  Link(const Link &pl);
  // 添加到指定位置
  bool link_insert(int pos,T *value);
  // 删除指定位置节点
  T * link_splice(int pos);
  // 获取指定为节点
  T * link_index(int pos);
  T * operator[](int pos);
  // 遍历链表
  void link_foreach(void(print)(T *));
  // 倒序遍历
  void link_reverse_foreach(void(print)(T *));
  // 头插
  bool link_unshift(T *value);
  // 头删
  T * link_shift();
  // 尾插
  bool link_push(T *value);
  // 尾删
  T * link_pop();
  // 查找节点
  T * link_find(bool(print)(T *));
  // 清空节点
  bool link_clear();
  // 销毁链表
  bool link_destory();
  // 获取链表长度
  int link_length();
  // 连接链表
  Link& operator+(const Link &plink);
  Link& operator+=(const Link &plink);
  // 比较大小
  bool operator>(const Link &plink);
  bool operator<(const Link &plink);
  bool operator==(const Link &plink);
};

#endif //TEST1_LINK_H

link.cpp

#include "link.h"
#include
using namespace std;

// 创建双链表
template
Link::Link(){
  this->pheader=new Node;
  this->pfooter=new Node;
  this->pheader->next=this->pfooter;
  this->pheader->pre=this->pfooter;
  this->pfooter->next=this->pheader;
  this->pfooter->pre=this->pheader;
  this->length=0;
}

// 拷贝构造
template
Link::Link(const Link &pl){
  this->pheader=new Node;
  this->pfooter=new Node;
  this->length=pl.length;

  this->pheader->next=this->pfooter;
  this->pheader->pre=this->pfooter;
  this->pfooter->next=this->pheader;
  this->pfooter->pre=this->pheader;

  Node *tCur=pl.pheader->next;
  Node *pCur=this->pheader;

  for(int i=0;ilength;++i){
    Node *newNode=new Node;
    newNode->data=tCur->data;

    newNode->next=pCur->next;
    newNode->pre=pCur;

    pCur->next=newNode;
    pCur=newNode;
    tCur=tCur->next;
  }
  pCur->next=this->pfooter;
  this->pfooter->pre=pCur;
}

// 连接链表
template 
Link& Link::operator+(const Link &plink){
  Node *tCur=plink.pheader->next;
  for(int i=0;ilink_push(tCur->data);
    tCur=tCur->next;
  }
  return *this;
}
template 
Link& Link::operator+=(const Link &plink){
  Node *tCur=plink.pheader->next;
  for(int i=0;ilink_push(tCur->data);
    tCur=tCur->next;
  }
  return *this;
}

// 比较大小
template
bool Link::operator>(const Link &plink){
  return this->length>plink.length;
}

template
bool Link::operator<(const Link &plink){
  return this->length
bool Link::operator==(const Link &plink){
  return this->length==plink.length;
}

template
int Link::link_length(){
  if(this->pheader==NULL||this->pfooter==NULL)
    return 0;
  return this->length;
}

// 在指定位置插入节点
template
bool Link::link_insert(int pos,T *value){
  if(!value)
    return false;
  if(pos>this->length||pos<0)
    pos=this->length;
  Node *pCur=this->pheader;
  for(int i=0;inext;
  }
  Node *newNode=new Node;
  newNode->data=value;

  Node *pNext=pCur->next;
  newNode->next=pCur->next;
  newNode->pre=pCur;
  pCur->next=newNode;
  pNext->pre=newNode;
  this->length++;
  return true;
}

// 删除指定为节点
template 
T * Link::link_splice(int pos){
  if(pos<0||pos>this->length)
    return NULL;
  Node *pCur=this->pheader;
  for(int i=0;inext;
  }
  Node *deleteNode=pCur->next;
  T*data=deleteNode->data;
  deleteNode->next->pre=pCur;
  pCur->next=deleteNode->next;
  delete deleteNode;
  this->length--;
  return data;
}

// 获取指定位置节点
template
T * Link::link_index(int pos){
  if(pos<0||pos>=this->length)
    return NULL;
  if(this->pheader==NULL||this->pfooter==NULL)
    return NULL;
  Node *pCur=this->pheader->next;
  for(int i=0;inext;
  }
  return pCur->data;
}

template
T * Link::operator[](int pos){
  if(pos<0||pos>=this->length)
    return NULL;
  if(this->pheader==NULL||this->pfooter==NULL)
    return NULL;
  Node *pCur=this->pheader->next;
  for(int i=0;inext;
  }
  return pCur->data;
}

// 正序遍历
template
void Link::link_foreach(void(print)(T *)){
  if(!this->length||!this->pheader)
    return ;
  Node *pCur=this->pheader->next;
  for(int i=0;ilength;++i){
    print(pCur->data);
    pCur=pCur->next;
  }
}

// 倒序遍历
template
void Link::link_reverse_foreach(void(print)(T *)){
  if(!this->length||!this->pheader)
    return ;
  Node *pCur=this->pfooter->pre;
  for(int i=0;ilength;++i){
    print(pCur->data);
    pCur=pCur->pre;
  }
}

// 头插
template
bool Link::link_unshift(T *value){
  if(this->pheader==NULL||this->pfooter==NULL||!value)
    return false;
  Node *pCur=this->pheader->next;
  Node *newNode=new Node;
  newNode->data=value;

  newNode->next=this->pheader->next;
  newNode->pre=this->pheader;
  this->pheader->next=newNode;
  pCur->pre=newNode;
  this->length++;
  return true;
}

// 头删
template
T *Link::link_shift(){
  if(this->pheader==NULL||this->pheader==NULL||!this->length)
    return NULL;
  Node *deleteNode=this->pheader->next;
  T *data=deleteNode->data;
  this->pheader->next=deleteNode->next;
  deleteNode->next->pre=this->pheader;
  this->length--;
  delete deleteNode;
  return data;
}

// 尾插
template
bool Link::link_push(T *value){
  if(this->pheader==NULL||this->pfooter==NULL||!value)
    return false;
  Node *pCur=this->pfooter->pre;
  Node *newNode=new Node;
  newNode->data=value;

  newNode->pre=this->pfooter->pre;
  newNode->next=this->pfooter;
  this->pfooter->pre=newNode;
  pCur->next=newNode;
  this->length++;
  return true;
}

// 尾删
template
T * Link::link_pop(){
  if(this->pheader==NULL||this->pheader==NULL||!this->length)
    return NULL;
  Node *pCur=this->pfooter;
  Node *deleteNode=this->pfooter->pre;
  T *data=deleteNode->data;
  pCur->pre=deleteNode->pre;
  deleteNode->pre->next=pCur;
  delete deleteNode;
  this->length--;
  return data;
}

// 查找节点
template
T * Link::link_find(bool(print)(T *)){
  if(this->pheader==NULL||this->pheader==NULL||!this->length)
    return NULL;
  Node *pCur=this->pheader->next;
  for(int i=0;ilength;++i){
    if(print(pCur->data)){
      return pCur->data;
    }
    pCur=pCur->next;
  }
  return NULL;
}

// 清空节点
template
bool Link::link_clear(){
  if(this->length==0||this->pheader==NULL||this->pfooter==NULL)
    return true;
  Node *pCur=this->pheader->next;
  for(int i=0;ilength;++i){
    Node *t=pCur->next;
    delete pCur;
    pCur=t;
  }
  this->length=0;
  return true;
}

// 销毁链表
template
bool Link::link_destory(){
  this->link_clear();
  if(this->pheader==NULL||this->pfooter==NULL)
    return true;
  delete this->pheader;
  delete this->pfooter;
  this->pheader=NULL;
  this->pfooter=NULL;
  return true;
}

// 析构
template
Link::~Link(){
  this->link_destory();
}

test.cpp

#include "link/link.cpp"
#include 
using namespace std;

class person{
private:
  int id;
  string name;
  int age;
public:
  person(int id,string name,int age):id(id),name(name),age(age){}
  void info(){
    cout<<"id:"<id<<" name:"<name<<" age:"<age<name==tp.name&&this->id==tp.id&&this->age==tp.age){
      return true;
    }else{
      return false;
    }
  }
};

template
void myPrint(T *value){
  class person *p=(class person *)value;
  p->info();
}

template
bool findValue(T *value){
  class person *p=(class person *)value;
  class person *p0=new person(4,"Tom",21);
  return *p0==*p;
}

void test(){
  class person *p1=new person(1,"Andy",21);
  class person *p2=new person(2,"Sam",21);
  class person *p3=new person(3,"Tim",21);
  class person *p4=new person(4,"Tom",21);
  class person *p5=new person(5,"John",21);
  class person *p6=new person(6,"Jack",21);
  class Link *k1=new Link();
  k1->link_insert(0,p1);
  k1->link_insert(1,p2);
  k1->link_insert(2,p3);
  k1->link_insert(3,p4);
  k1->link_splice(2);
  k1->link_splice(2);
  k1->link_splice(0);
  class person *p=(class person *)k1->link_splice(0);
  // p->info();
  k1->link_insert(0,p1);
  k1->link_insert(1,p2);
  k1->link_insert(2,p3);
  k1->link_insert(3,p4);
  k1->link_unshift(p5);
  class Link *k2=new Link(*k1);
  cout<<"k1==k2:"<<(*k1==*k2)<link_foreach(myPrint);
 
  cout<<"k1 length:"<link_length()<link_length()<k2:"<<(*k1>*k2)<link_index(14);
  if(p)
  p->info();
  p=(class person *)k1->link_find(findValue);
  if(p)
  p->info();
  // p=(class person *)(*k1)[0];
  p=(class person *)k1[0][0];
  p->info();
  k1->link_clear();
  k1->link_destory();
  k2->link_destory();
}

int main(){
  test();
  system("pause");
  return EXIT_SUCCESS;
}

运行结果

k1==k2:1
id:5 name:John age:21
id:1 name:Andy age:21
id:2 name:Sam age:21
id:3 name:Tim age:21
id:4 name:Tom age:21
id:5 name:John age:21
id:1 name:Andy age:21
id:2 name:Sam age:21
id:3 name:Tim age:21
id:4 name:Tom age:21
id:5 name:John age:21
id:1 name:Andy age:21
id:2 name:Sam age:21
id:3 name:Tim age:21
id:4 name:Tom age:21
k1 length:15
k2 length:5
k1>k2:1
id:4 name:Tom age:21
id:4 name:Tom age:21
id:5 name:John age:21
请按任意键继续. . .