异质链表，是一种每个节点可以存储不同类型对象的链表。
C++实现异质链表，的关键技术是模版元编程和多态性，不多说，直接看代码。

代码主要分为两部分：AnyElement.h 和 AnyList.h

AnyElement.h
包含AnyElment、ElementBase、Element 三个类；
ElementBase和Element嵌套在AnyElment类之中；
Element类继承ElementBase类；
Element类是一个模版类；
在AnyElement中通过ElementBase类的指针来存储不同类型的Element类。

# ifndef ANYELEMENT_H# define ANYELEMENT_H# include/ * The class that can store any type of value implement by polymorphism.*/class AnyElement{  class ElementBase{//virtual class for inherit  public:    virtual ~ElementBase(){ }//virtual destructor  };  template  class Element : public ElementBase{  public:    T value;    Element(const T& _value)      :value(_value){ }  };  ElementBase* pelement; //a base class pointerpublic:  AnyElement() //default constructor    :pelement(nullptr){ }   template  AnyElement(const T& _value) //constructor    :pelement(new Element(_value)){ }  ~AnyElement(){ //destructor    delete pelement;  }  template  T& get(){ //get the Element's value by pelement    auto pderived = dynamic_cast*>(pelement);    if(nullptr == pderived){      throw std::invalid_argument("The type to dynamic_cast is wrong");    }    return pderived->value;  }};# endif //ANYELEMENT_H

AnyList.h
包含了链表的节点类和主体类，其内容与一般的链表差别不大;
其主要函数列表如下：
基本功能
AnyList();
~AnyList();
iterator begin();
iterator end();
bool isempty();
void clear();
void reverse();
void merge(AnyList& anotherList);

(以下为模版函数，为了简洁，template省略不写)
功能：在不同位置插入节点
void push_back(const T& _data,Type _type);
void push_front(const T& _data,Type _type);
void insert(const T& _data,ListNode _prev,Type _type);
功能：获得不同位置的对象
T& peek_back();
T& peek_front();
T& get(ListNode position);
功能：删除不同位置的节点
bool pop_back();
bool pop_front();
bool drop(iterator position);

# ifndef ANYLIST_ANYLIST_H# define ANYLIST_ANYLIST_H# include # include "AnyElement.h"/                             * Before using this list you should add all types that you ** need to use to the enum Type.                           *                             */typedef enum TYPE{  INT = 0,  FLOAT = 1,  DOUBLE = 2,  STRING = 3,  TEST = 4} Type;/   *NOTE:Don't change code after the hr        *//  The Node of the LinkList */struct ListNode{  Type type;  AnyElement data;  ListNode *prev;  ListNode *next;  template  ListNode(const T& _data,ListNode* _prev,ListNode* _next,const Type& _type)    :data(_data),prev(_prev),next(_next),type(_type){ }};/  The AnyList class */class AnyList{  ListNode* head;  ListNode* tail;public:  using iterator = ListNode*;  AnyList()//constructor    :head(nullptr),tail(nullptr){ }  ~AnyList(){//destructor    while(head){      ListNode* temp = head;      head = head->next;      delete head;    }  }  iterator begin(){//get the head pointer    return head;  }  iterator end(){//get the pointer after tail    return nullptr;  }  bool isempty(){//is empty    return nullptr == head;  }  void clear(){//destroy all content    while(head){      ListNode* temp = head;      head = head->next;      delete head;    }    head = tail = nullptr;  }  void clear_for_merge(){//just foe merge    head = tail = nullptr;  }  void reverse(){//reverse the order of the node    if(head==tail) return ;    ListNode *pres = tail,             *oriTail = tail,             *ptem = tail->prev;    tail = head;    head = oriTail;    pres->prev = nullptr;    while(nullptr != ptem){      pres->next = ptem;      ptem = ptem->prev;      pres->next->prev = ptem;      pres = pres->next;    }    pres->next = nullptr;  }  void merge(AnyList& anotherList){//merge anotherList to this list    if(anotherList.head==nullptr)      return ;    tail->next = anotherList.head;    anotherList.head->prev = tail;    tail = anotherList.tail;    anotherList.clear_for_merge();  }  template  void push_back(const T& _data,Type _type){//insert after tail    ListNode* newNode = new ListNode(_data,tail,nullptr,_type);    if(nullptr == head){      head = newNode;      tail = newNode;      return ;    }    tail->next = newNode;    tail = newNode;  }  template  void push_front(const T& _data,Type _type){//insert before head    ListNode* newNode = new ListNode(_data,nullptr,head,_type);    if(nullptr == tail){      head = newNode;      tail = newNode;      return ;    }    head->prev = newNode;    head = newNode;  }  template//insert after _prev  void insert(const T& _data,ListNode* _prev,Type _type){    if(nullptr == _prev){      std::cerr next,_type);    _prev->next = newNode;    if(newNode->next)      newNode->next->prev = newNode;    if(tail == _prev)      tail = newNode;  }  //before execute these function you must execute isempty()  template  T& get(ListNode* position){//get data in position    return position->data.get();  }  template  T& peek_back(){//get data in tail    return get(tail);  }  template  T& peek_front(){//get data in head    return get(head);  }  bool drop(iterator position){//delete node in position    if(isempty()){      std::cerrnext;      head->prev = nullptr;      delete ptem;    }else if(position == tail){      ptem = tail;      tail = tail->prev;      tail->next = nullptr;      delete ptem;    }else{      position->prev->next = position->next;      position->next->prev = position->prev;      delete position;    }    return true;  }  bool pop_back(){//drop tail    return drop(tail);  }  bool pop_front(){//drop head    return drop(head);  }};# endif //ANYLIST_ANYLIST_H

测试程序

# include# include"AnyList.h"using namespace std;class Test{// for testpublic:  int real;  int virt;  Test(int _real,int _virt)    :real(_real),virt(_virt){}  friend ostream& operatornext){    switch(i->type){      case INT:      {        auto data = list.get(i);        cout(i);        cout(i);        cout(i);        coutoriginal list:"reverse list:"mergte list:"delete list:"<<endl;  list.pop_back();  list.pop_front();  print(list);  return 0;}

c++

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！