PythonTip >> 博文 >> python

【原创】C++链表如何像Python List一样支持多种数据类型 - 流镡

zihua 2014-03-23 15:03:17 点击: 910 | 收藏


用过Python的码友都知道,Python中List支持多种数据类型,如下面代码所示链表li内的数据类型可以是整数,同时也可以是字符串,当然也可以是其他数据类型。

   1: >>> li = [1,2.5,"hello world"]
   2: >>> li
   3: [1, 2.5, 'hello world']
   4: >>>

对于一个C++爱好者来说,不由得想C++中是不是也有类似的容器或者方法来实现一个链表内可以支持多种数据类型呢?答案是肯定的。boost内有现成的类可以使用,但是我们先不着急看这个现成类的使用,看看能用几种方法来实现?

基本思路是 模板+继承

实现方法一

将链表节点中的数据类型template参数化(如下):

   1: template<typename DataType>
   2: class Node {
   3: private:
   4:     DataType data;
   5:     ??? *next;
   6: }

可是next节点的数据类型可能跟当前node的数据类型不同,那可怎么定义呢?不同的数据类型需要同样的接口,自然想到用“继承”的方法来解决,多说无益,上图,上代码:

image

   1: 
   2: class NodeBase {
   3: ...
   4: private:
   5:   NodeBase *next;
   6: };
   7: 
   8: template<typename DataType>
   9: class Node: public NodeBase {
  10: ...
  11: private:
  12:   DataType data;
  13: };

这样,当需要存入多个数据类型时,就会有相应的节点类型产生(例如,我们有三种类型int, double, string):

image

测试代码如下:

   1: class NodeBase {
   2:   friend class List;
   3:   friend ostream& operator<<(ostream &out, const List &list);
   4: public:
   5:   NodeBase() : next(NULL) {}
   6:   virtual ~NodeBase() {}
   7: 
   8:   virtual void operator<<(ostream &out) = 0;
   9: 
  10: private:
  11:   NodeBase *next;
  12: };
  13: 
  14: ///
  15: ///template class to create Node type based on data type
  16: ///
  17: template<typename DataType>
  18: class Node: public NodeBase {
  19:   friend class List;
  20: public:
  21:   Node(const DataType &idata): data(idata){}
  22: 
  23:   virtual void operator<<(ostream &out)
  24:   {
  25:     out<<data;
  26:   }
  27: 
  28: private:
  29:   DataType data;
  30: };
  31: 
  32: class List
  33: {
  34:   friend ostream& operator<<(ostream &out, const List &list);
  35: public:
  36:   List()
  37:   {
  38:     head = tail = NULL;
  39:   }
  40:   ~List()
  41:   {
  42:     for (; head;) {
  43:       NodeBase *next = head->next;
  44:       delete head;
  45:       head = next;
  46:     }
  47:     tail = NULL;
  48:   }
  49: 
  50:   ///
  51:   ///template function to add a new node
  52:   ///based on the input data type, to determine
  53:   ///the node type
  54:   ///
  55:   template <typename DataType>
  56:   void add(const DataType &data)
  57:   {
  58:     NodeBase *node = new Node<DataType>(data);
  59:     if (!tail) {
  60:       head = node;
  61:     }
  62:     else {
  63:       tail->next = node;
  64:     }
  65:     tail = node;
  66:   }
  67: 
  68: private:
  69:   NodeBase *head, *tail;
  70: };
  71: 
  72: ///
  73: ///test to output all datas in the input @a list 
  74: ///
  75: ostream& operator<<(ostream &out, const List &list)
  76: {
  77:   for (NodeBase *node = list.head; node; node = node->next)
  78:   {
  79:     node->operator<<(out);
  80:     out<<' ';
  81:   }
  82:   return out;
  83: }
  84: 
  85: ///
  86: ///test a list support multiple data types just like Python
  87: ///
  88: int main()
  89: {
  90: 
  91:   List *list = new List;
  92: 
  93:   list->add(1);
  94:   list->add(2.5);
  95:   list->add(string("hello world"));
  96: 
  97:   cout<<*list<<endl;
  98:
  99:   delete list; list = NULL;
 100:   return 0;
 101: }

实现方法二

用一个抽象数据类型作为接口,直接上图:

image

   1: class DataBase {
   2: ...
   3: };
   4: 
   5: template <typename InnerType>
   6: class Data : public DataBase {
   7: public:
   8:   Data(const InnerType &idata) : innerData(idata)  {}
   9: ...
  10: private:
  11:     InnerType innerData;
  12: };
  13: 
  14: class Node {
  15: public:
  16:   template <typename InnerType>
  17:   Node(const InnerType &idata)
  18:     : data(new Data<InnerType>(idata)), next(NULL) {}
  19:   ~Node()
  20:   {
  21:     delete data; data = NULL;
  22:   }
  23: 
  24: private:
  25:   DataBase *data;
  26:   Node     *next;
  27: };

测试代码如下:

   1: 
   2: #include <iostream>
   3: 
   4: using namespace std;
   5: 
   6: class List;
   7: 
   8: class DataBase {
   9: public:
  10:   virtual ~DataBase() {}
  11: 
  12:   virtual void operator<<(ostream &out) = 0;
  13: };
  14: 
  15: template <typename InnerType>
  16: class Data : public DataBase {
  17: public:
  18:   Data(const InnerType &idata) : innerData(idata)  {}
  19: 
  20:   virtual void operator<<(ostream &out)
  21:   {
  22:     out<<innerData;
  23:   }
  24: private:
  25:     InnerType innerData;
  26: };
  27: 
  28: ///
  29: ///template class to create Node type based on data type
  30: ///
  31: class Node {
  32:   friend class List;
  33:   friend ostream& operator<<(ostream &out, const List &list);
  34: public:
  35:   template <typename InnerType>
  36:   Node(const InnerType &idata)
  37:     : data(new Data<InnerType>(idata)), next(NULL) {}
  38:   ~Node()
  39:   {
  40:     delete data; data = NULL;
  41:   }
  42: 
  43: private:
  44:   DataBase *data;
  45:   Node     *next;
  46: };
  47: 
  48: class List
  49: {
  50:   friend ostream& operator<<(ostream &out, const List &list);
  51: public:
  52:   List()
  53:   {
  54:     head = tail = NULL;
  55:   }
  56:   ~List()
  57:   {
  58:     for (; head;) {
  59:       Node *next = head->next;
  60:       delete head;
  61:       head = next;
  62:     }
  63:     tail = NULL;
  64:   }
  65: 
  66:   ///
  67:   ///template function to add a new node
  68:   ///based on the input data type, to determine
  69:   ///the node type
  70:   ///
  71:   template <typename InnerType>
  72:   void add(const InnerType &data)
  73:   {
  74:     Node *node = new Node(data);
  75:     if (!tail) {
  76:       head = node;
  77:     }
  78:     else {
  79:       tail->next = node;
  80:     }
  81:     tail = node;
  82:   }
  83: 
  84: private:
  85:   Node *head, *tail;
  86: };
  87: 
  88: ///
  89: ///test to output all datas in the input @a list 
  90: ///
  91: ostream& operator<<(ostream &out, const List &list)
  92: {
  93:   for (Node *node = list.head; node; node = node->next)
  94:   {
  95:     if (node->data) {
  96:       node->data->operator<<(out);
  97:       out<<' ';
  98:     }
  99:   }
 100:   return out;
 101: }
 102: 
 103: ///
 104: ///test a list support multiple data types just like Python
 105: ///
 106: int main()
 107: {
 108: 
 109:   List *list = new List;
 110: 
 111:   list->add(1);
 112:   list->add(2.5);
 113:   list->add(string("hello world"));
 114: 
 115:   cout<<*list<<endl;
 116:
 117:   delete list; list = NULL;
 118:   return 0;
 119: }

实现方法三

boost::any ,关于它的介绍,这个博客不错: http://blog.csdn.net/hityct1/article/details/4186962 ,感兴趣的码友可以去深入了解。

参考文献

http://stackoverflow.com/questions/17528657/python-list-equivalent-in-c

http://www.cnblogs.com/kex1n/archive/2011/04/11/2013098.html

http://blog.csdn.net/debugm/article/details/8241759

http://www.360doc.com/content/14/0103/17/15099545_342367928.shtml

http://blog.csdn.net/hityct1/article/details/4186962

原文链接:http://www.tuicool.com/articles/f2MNZf

作者:zihua | 分类: python | 标签: python | 阅读: 910 | 发布于: 2014-03-23 15时 |