C0EEBDA1-leajian-又一个链表操作程序（C++）

之前用C写过一个通用的双向链表管理程序（《一个通用的双向链表管理程序》），主要是利用了C中强制类型转换带来的副作用。

今天闲来无事，用C++重写了一份，本来是希望利用C++的类的继承的特性，使得在一个基本链表的基础上，可以派生出拥有多种数据成员的节点。然而并没有像我一开始想象的那样简单：本来希望用一个类来描述一个链表，然而，除非这个类当做为一个节点来看待，否则数据成员是不太容易继承并增加的。这样一来，对链表的操作就变成了对n多个对象的操作，跟C语言中的做法好像差别不大，意义也不大。

后来想起C++中的template，之前很少有使用过，不过知道它具有类型无关的特性。其实想一想，所谓的“通用”链表管理程序，不就是希望让对链表的操作与节点本身的数据无关吗？所以，就有了下面这个C++ template版本的链表操作程序：

（该程序仅有一个.h文件，直接包含即可）

   1: #ifndef _LNKLST_H_

   2: #define _LNKLST_H_

3:

   4: #ifdef __cplusplus

   5: namespace LinkList

   6: {

   7: /************************************************************************

   8: CLinkList Class

   9:   提供基本的单项链表操作支持

  10: How To USE:

  11:   如果链表的节点数据是基础类型, 可直接以如下形式派生(以int为例):

  12:   typedef ClinkList<int> CIntList;

  13:   CIntList myList;

  14:   如果链表的节点数据是复合类型,

  15:   建议以类来表示, 并重载"=="和">"操作符

  16:   class MyStruct {

  17:   public:

  18:       // 以下是数据成员

  19:       int a, b, c;

  20:       struct {

  21:           int aa;

  22:           int bb;

  23:       } d;

  24:       // 下面重载"=="运算符, 以便支持链表操作

  25:       friend int operator==(MyStruct &s1, MyStruct &s2)

  26:       {

  27:           if((s1.a == s2.a)

  28:              && (s1.b == s2.b)

  29:              && (s1.c == s2.c))

  30:               return (1 == 1);

  31:           return (1 == 0);

  32:       }

  33:       friend int operator>(MyStruct &s1, MyStruct &s2)

  34:       {

  35:           int res = s1.a - s2.a;

  36:           if(res == 0)

  37:               res = s1.b - s2.b;

  38:           if(res == 0)

  39:               res = s1.c - s2.c;

  40:           return res > 0;

  41:       }

  42:   };

  43:   之后, 可使用如下形式派生

  44:   typedef CLinkList<MyStruct> CStructList;

  45: ************************************************************************/

  46: template <class T>

  47: class CLinkList {

  48: public:

  49:     struct nod_t {

  50:         struct nod_t *next;

  51:         T data;

  52:     };

  53:     typedef struct nod_t NODE, *PNODE, *LISTHEAD;

  54:     typedef enum { POS_HEAD, POS_BEFORE, POS_AFTER, POS_TAIL } NODE_POSITION;

  55:     typedef int (*DUMP_CALLBACK)(PNODE, int);

56:

  57: public:

  58:     PNODE AddTo(T &data, PNODE to = NULL, NODE_POSITION pos = POS_TAIL);

  59:     PNODE AddTo(PNODE newNode, PNODE to = NULL, NODE_POSITION pos = POS_TAIL);

  60:     PNODE Add(T &data)                                  { return AddTo(data); }

  61:     PNODE Add(PNODE nod)                                { return AddTo(nod); }

  62:     PNODE AddSorted(T &data);

  63:     PNODE AddSorted(PNODE nod);

  64:     // freemem用于决定在将节点从链表删除之后, 是否被销毁

  65:     // freemem = 1是一个比较危险的操作, 请确保节点可以被delete完整回收

  66:     PNODE Delete(T t, int freemem = 0)                  { return Delete(Find(t), freemem); }

  67:     PNODE Delete(PNODE node, int freemem = 0);

  68:     PNODE Find(T t);

  69:     PNODE GetAt(int id);

  70:     int GetCount(void) { return count; }

  71:     void Move(PNODE nod, PNODE to, NODE_POSITION pos);

  72:     void Swap(PNODE n1, PNODE n2);

  73:     int Dump(DUMP_CALLBACK fun);

  74:     void Sort(void);

75:

  76: public:

  77:     T operator[](int nIndex)                            { return GetAt(nIndex)->data; }

  78:     // 以下四个操作符等同于Add操作

  79:     CLinkList& operator += (PNODE nod)                  { AddTo(nod); return *this; }

  80:     CLinkList& operator += (T &data)                    { AddTo(data); return *this; }

  81:     friend PNODE operator + (CLinkList &l, PNODE nod)   { return l.AddTo(nod); }

  82:     friend PNODE operator + (CLinkList &l, T data)      { return l.AddTo(data); }

  83:     // 以下两个操作符等同于Delete操作, 并且同时将delete节点

  84:     CLinkList& operator -= (PNODE nod)                  { Delete(nod, 1); return *this; }

  85:     CLinkList& operator -= (T data)                     { Delete(data, 1); return *this; }

  86:     // 以下两个操作符等同于Delete操作, 并且节点不会被delete, 可以继续使用

  87:     friend PNODE operator - (CLinkList &l, PNODE nod)   { return l.Delete(nod); }

  88:     friend PNODE operator - (CLinkList &l, T data)      { return l.Delete(data); }

  89: public:

  90:     CLinkList()                                         { head = NULL; count = 0; }

  91:     ~CLinkList()                                        { removeAll(); }

92:

  93: private:

  94:     void removeAll(void);

  95:     PNODE prevNode(PNODE nod);

  96:     PNODE lastNode(void);

97:

  98: private:

  99:     LISTHEAD head;

 100:     int count;

 101: };

 102:

 103: /************************************************************************/

 104: /* CLinkList 类的实现                                                   */

 105: /************************************************************************/

 106: template <class T>

 107: void inline CLinkList<T>::removeAll(void)

 108: {

 109:     PNODE nod = head;

 110:     while(nod)

 111:     {

 112:         PNODE tmp = nod->next;

 113:         delete nod;

 114:         nod = tmp;

 115:     }

 116:     count = 0;

 117: }

 118:

 119: template <class T>

 120: CLinkList<T>::PNODE inline CLinkList<T>::prevNode(PNODE nod)

 121: {

 122:     if(nod == head)

 123:         return NULL;

 124:     PNODE tmp = head;

 125:     while(tmp)

 126:     {

 127:         if(tmp->next == nod)

 128:             break;

 129:         tmp = tmp->next;

 130:     }

 131:     return tmp;

 132: }

 133:

 134: template <class T>

 135: CLinkList<T>::PNODE inline CLinkList<T>::lastNode(void)

 136: {

 137:     PNODE tmp = head;

 138:     while(tmp)

 139:     {

 140:         if(tmp->next == NULL)

 141:             break;

 142:         tmp = tmp->next;

 143:     }

 144:     return tmp;

 145: }

 146:

 147: template <class T>

 148: CLinkList<T>::PNODE inline CLinkList<T>::AddTo(PNODE newNode, PNODE to, NODE_POSITION pos)

 149: {

 150:     if(head == NULL)

 151:     {

 152:         head = newNode;

 153:         head->next = NULL;

 154:         count = 1;

 155:     }

 156:     else

 157:     {

 158:         switch(pos)

 159:         {

 160:         case POS_HEAD:

 161:             to = head;

 162:         case POS_BEFORE:

 163:             if(head == to)

 164:                 head = newNode;

 165:             newNode->next = to;

 166:             {

 167:                 PNODE tmp = prevNode(to);

 168:                 if(tmp != NULL)

 169:                     tmp->next = newNode;

 170:             }

 171:             break;

 172:         case POS_TAIL:

 173:         default:

 174:             to = lastNode();

 175:         case POS_AFTER:

 176:             newNode->next = to->next;

 177:             to->next = newNode;

 178:             break;

 179:         }

 180:         count++;

 181:     }

 182:     return newNode;

 183: }

 184:

 185: template <class T>

 186: CLinkList<T>::PNODE inline CLinkList<T>::AddTo(T &data, PNODE to, NODE_POSITION pos)

 187: {

 188:     PNODE newNode = new NODE;

 189:     newNode->data = data;

 190:     return AddTo(newNode, to, pos);

 191: }

 192:

 193: template <class T>

 194: CLinkList<T>::PNODE inline CLinkList<T>::AddSorted(T &data)

 195: {

 196:     if(head)

 197:     if(head->data > data)

 198:         return AddTo(data, NULL, POS_HEAD);

 199:     PNODE tmpNod = head;

 200:     while(tmpNod)

 201:     {

 202:         if(tmpNod->next->data > data)

 203:             break;

 204:         tmpNod = tmpNod->next;

 205:     }

 206:     return AddTo(data, tmpNod, POS_AFTER);

 207: }

 208:

 209: template <class T>

 210: CLinkList<T>::PNODE inline CLinkList<T>::AddSorted(PNODE nod)

 211: {

 212:     if(head)

 213:         if(head->data > nod->data)

 214:             return AddTo(nod, NULL, POS_HEAD);

 215:     PNODE tmpNod = head;

 216:     while(tmpNod)

 217:     {

 218:         if(tmpNod->next->data > nod->data)

 219:             break;

 220:         tmpNod = tmpNod->next;

 221:     }

 222:     return AddTo(nod, tmpNod, POS_AFTER);

 223: }

 224:

 225: template <class T>

 226: CLinkList<T>::PNODE inline CLinkList<T>::Delete(PNODE node, int freemem)

 227: {

 228:     if(node == NULL)

 229:         return NULL;

 230:     if(node == head)

 231:     {

 232:         head = node->next;

 233:     }

 234:     else

 235:     {

 236:         PNODE prev = prevNode(node);

 237:         if(prev != NULL)

 238:         {

 239:             prev->next = node->next;

 240:         }

 241:         else

 242:             return NULL;

 243:     }

 244:     count--;

 245:     if(freemem)

 246:     {

 247:         delete node;

 248:         node = NULL;

 249:     }

 250:     return node;

 251: }

 252:

 253: template <class T>

 254: CLinkList<T>::PNODE inline CLinkList<T>::Find(T t)

 255: {

 256:     PNODE tmpNod = head;

 257:     while(tmpNod)

 258:     {

 259:         if(tmpNod->data == t)

 260:             break;

 261:         tmpNod = tmpNod->next;

 262:     }

 263:     return tmpNod;

 264: }

 265:

 266: template <class T>

 267: CLinkList<T>::PNODE inline CLinkList<T>::GetAt(int id)

 268: {

 269:     PNODE tmpNode = head;

 270:     if(id >= count)

 271:         return NULL;

 272:     while(tmpNode)

 273:     {

 274:         if(id-- == 0)

 275:             break;

 276:         tmpNode = tmpNode->next;

 277:     }

 278:     return tmpNode;

 279: }

 280:

 281: template <class T>

 282: void inline CLinkList<T>::Move(PNODE nod, PNODE to, NODE_POSITION pos)

 283: {

 284:     if((head == NULL) || (nod == to))

 285:         return;

 286:     Delete(nod, 0);

 287:     AddTo(nod, to, pos);

 288: }

 289:

 290: template <class T>

 291: void inline CLinkList<T>::Swap(PNODE n1, PNODE n2)

 292: {

 293:     PNODE prev1, prev2;

 294:     PNODE tmpNode;

 295:     if(n1 == n2)

 296:         return;

 297:     if((n1 == NULL) || (n2 == NULL))

 298:         return;

 299:     prev1 = prevNode(n1);

 300:     prev2 = prevNode(n2);

 301:     if((prev1 == NULL) && (n1 != head))

 302:         return;

 303:     if((prev2 == NULL) && (n2 != head))

 304:         return;

 305:     if(n1->next == n2)

 306:     {

 307:         if(prev1 != NULL)

 308:             prev1->next = n2;

 309:         else

 310:             head = n2;

 311:         n1->next = n2->next;

 312:         n2->next = n1;

 313:     }

 314:     else if(n2->next == n1)

 315:     {

 316:         if(prev2 != NULL)

 317:             prev2->next = n1;

 318:         else

 319:             head = n1;

 320:         n2->next = n1->next;

 321:         n1->next = n2;

 322:     }

 323:     else

 324:     {

 325:         tmpNode = n2->next;

 326:         n2->next = n1->next;

 327:         n1->next = tmpNode;

 328:         if(prev1 == NULL)

 329:             head = n2;

 330:         else

 331:             prev1->next = n2;

 332:         if(prev2 == NULL)

 333:             head = n1;

 334:         else

 335:             prev2->next = n1;

 336:     }

 337: }

 338:

 339: template <class T>

 340: int inline CLinkList<T>::Dump(DUMP_CALLBACK fun)

 341: {

 342:     int i = 0;

 343:     PNODE tmpNode = head;

 344:     while(tmpNode)

 345:     {

 346:         if((*fun)(tmpNode, i) != 0)

 347:             break;

 348:         i++;

 349:         tmpNode = tmpNode->next;

 350:     }

 351:     (*fun)(NULL, -1);

 352:     return i;

 353: }

 354:

 355: template <class T>

 356: void inline CLinkList<T>::Sort(void)

 357: {

 358:     PNODE nod1 = head;

 359:     if(nod1 == NULL)

 360:         return;

 361:     PNODE nod2 = head->next;

 362:     if(nod2 == NULL)

 363:         return;

 364:     int swaped = 1;

 365:     while(swaped)

 366:     {

 367:         swaped = 0;

 368:         while(1)

 369:         {

 370:             if(nod1->data > nod2->data)

 371:             {

 372:                 Swap(nod1, nod2);

 373: //                Move(nod1, nod2, POS_AFTER);

 374:                 nod2 = nod1->next;

 375:                 swaped = 1;

 376:             }

 377:             else

 378:             {

 379:                 nod1 = nod2;

 380:                 nod2 = nod2->next;

 381:             }

 382:             if(nod2 == NULL)

 383:             {

 384:                 nod1 = head;

 385:                 nod2 = nod1->next;

 386:                 break;

 387:             }

 388:         }

 389:     }

 390: }

 391:

 392: };

 393: #else

 394: # error This file must be used in c++ project!

 395: #endif

 396: #endif//_LNKLST_H_

简单的解释一下：

这个template的核心部件就是那个struct nod_t结构体，在这个结构体中包含了一个类型无关的成员data。当希望链表表示不同的数据时，只需要按照程序中的介绍，生成一个新的类型即可：

   1: typedef CLinkList<int> CIntList;

这样一来，就相当于构造了一个下面这样的节点：

   1: struct nod_t {

   2:     struct nod_t *next;

   3:     int data;

   4: };

而这个新产生的类中的Add、Delete等函数，即可对拥有这种类型节点的链表进行操作：

   1: CIntList myList;

   2: int data = 10;

   3: myList.Add(data);

   4: myList.Delete(data, 1);

   5: myList += data;

   6: myList -= data;

而当希望将这个链表用于其他的数据结构时,比如现在需要有一个用于描述用户的链表,希望包含用户名、机器名、IP地址等相关信息，则可以这样构造一个新的链表类：

   1: #include "lnklst.h"

   2: using namespace LinkList;

3:

   4: class userInfo {

   5: public:

   6:     userInfo() { name = host = NULL; }

   7: //    ~userInfo(){ if(name) delete []name; if(host) delete []host; }

   8:     char *name;

   9:     char *host;

  10:     unsigned long addr;

  11:     friend int operator==(userInfo &u1, userInfo &u2)

  12:     {

  13:         if((strcmp(u1.name, u2.name) == 0)

  14:             && (strcmp(u1.host, u2.host) == 0)

  15:             && (u1.addr == u2.addr))

  16:         {

  17:             return (1 == 1);

  18:         }

  19:         return (1 == 0);

  20:     }

  21:     friend int operator>(userInfo &u1, userInfo &u2)

  22:     {

  23:         int res = strcmp(u1.name, u2.name);

  24:         if(res == 0)

  25:             res = strcmp(u1.host, u2.host);

  26:         if(res == 0)

  27:             res = u1.addr - u2.addr;

  28:         return res > 0;

  29:     }

  30: };

31:

  32: typedef CLinkList<userInfo> CUserList;

在上面的程序中class userInfo用于描述一个用户的信息，相当于链表中的一个节点。为何要用类而不用结构体，是因为在template中，一旦将一个符合类型做为模板数据类型，则在使用“==”“>”等操作符时，将引起失败。所以，没办法，只能使用类来表示，从而可以用重载操作符的方式来对符合类型进行操作。

由于在CLinkList模板类中设计了排序、查找等操作，所以，在userInfo类中，需要重载“==”和“>”两个操作符，以便对CLinkList做支持。

接下来的使用也是很简单的：

   1: CUserList userList;

2:

   3: userInfo newUser;

   4: newUser.addr = 0;

   5: newUser.name = "name";

   6: newUser.host = "host";

   7: CUserList::PNODE nod1 = userList.Add(newUser);

   8: newUser.addr = 1;

   9: CUserList::PNODE nod2 = userList.Add(newUser);

  10: newUser.addr = 2;

  11: CUserList::PNODE nod3 = userList.Add(newUser);

  12: newUser.addr = 3;

  13: CUserList::PNODE nod4 = userList.Add(newUser);

  14: newUser.addr = 4;

  15: userList += newUser;

  16: newUser.addr = 5;

  17: CUserList::PNODE nod5 = userList + newUser;

欢迎讨论和批评指正。

C0EEBDA1

在梦中，我是有超能力的。。。

导航

2009-7-24 10:9:9

又一个链表操作程序（C++）

Tags: c 链表 template

发布:lijian | 分类:技术原创 | 评论:4 | 引用:0 | 浏览:

日历

最新评论及回复

最近发表

Powered By Z-Blog 1.8 Spirit Build 80722 theme by BokeZhuti

Copyright 2008-2009 C0EEBDA1. Some Rights Reserved. 备案号:京ICP备09020681号