ITPub博客

C++实现通用双向链表

原创 作者:gaopengtttt 时间:2017-03-08 23:05:21 0 删除 编辑
使用C++完成双向通用链表
双向链表不用多说,通用链表因为数据结构不确定的,使用一个VOID指针指向数据,
什么数据都可以挂上去,这样来封装链表,可以作为基础类也可以单独使用,
这里只是为了练习C++封装的语法,实现了简单的增加和删除链表由于实际数据
类型不能确定,打印链表数据使用公有函数来完成,完成了正向打印反向打印,
演示了数据类型为简单的int类型也演示了数据类型为class类型。
代码如下:


点击(此处)折叠或打开

  1. 链表实现:
  2. #include<iostream>
  3. #include<stdlib.h>
  4. using namespace std;
  5. /* data数据类型进行void封装,为通用链表
  6.  * node为节点的基本数据结构
  7.  * addnode使用void数据进行连接到链表中,造成链表
  8.  * frist_node为第一个结点位置,开放访问
  9.  * last_node为最后一个节点位置,开放访问
  10.  * length为节点长度,开放访问
  11.  * 只是完成增加节点和释放节点功能,其他功能也相应简单,用到再加,打印功能由于
  12.  * 数据类型不确定无法完成。
  13.  */
  14. #ifndef _CHAIN_
  15. #define _CHAIN_
  16. struct node
  17. {
  18.         void* data;
  19.         node* next;
  20.         node* priv;
  21.         unsigned int num;
  22.         node()
  23.         {
  24.                 data = NULL;
  25.                 next = NULL;
  26.                 priv = NULL;
  27.                 num = 0;
  28.         }
  29. };


  30. class my_chain
  31. {
  32.         public:
  33.                 my_chain()
  34.                 {

  35.                         this->frist_node = NULL;
  36.                         this->length = 0;
  37.                         this->last_node = NULL;
  38.                 }
  39. //-1 data is null;
  40. // 0 normal
  41. // 传入一个void指针的数据类型,链表增加一个节点
  42.                 int addnode(void* data)
  43.                 {
  44.                         ret = 0 ;

  45.                         if(data == NULL)
  46.                         {
  47.                                 ret = -1;
  48.                                 return ret;
  49.                         }

  50.                         node* c_node = new node; //分配节点内存

  51.                         if(this->frist_node == NULL)
  52.                         {

  53.                                 this->frist_node = c_node;
  54.                         }
  55.                         if(this->last_node == NULL)
  56.                         {
  57.                                 c_node->next = NULL;
  58.                                 c_node->priv = NULL;
  59.                                 c_node->data = data;
  60.                         }
  61.                         else
  62.                         {
  63.                                 c_node->next = NULL;
  64.                                 c_node->priv = this->last_node;
  65.                                 this->last_node->next = c_node;
  66.                                 c_node->data = data;
  67.                         }
  68.                         this->last_node = c_node;
  69.                         this->length++;
  70.                         c_node->num = this->length;
  71.                         return ret;
  72.                 }
  73. //ret=1 null list;
  74. //ret=0 normal list;
  75. //释放整个链表内存
  76.                 int freechain()
  77.                 {
  78.                         ret = 0;
  79.                         if(this->last_node == NULL)
  80.                         {
  81.                                 ret = 1;
  82.                                 cout<<"null list"<<endl;
  83.                                 return ret;
  84.                         }
  85.                         node* node_my = this->frist_node;
  86.                         while(node_my != NULL)
  87.                         {
  88. #ifdef DEBUG
  89.                                  cout<<"free node num:"<< node_my->num<<endl;
  90. #endif
  91.                                  node* temp = node_my;
  92.                                  node_my = node_my->next;
  93.                                  free(temp->data);//删除节点数据内存?跨函数free
  94.                                  delete temp;//删除节点node内存
  95.                         }
  96.                 }
  97. //....
  98.                 int delnode() //未实现
  99.                 {
  100.                         ret = 0;
  101.                         return ret;
  102.                 }

  103.                 int addmodnode(unsigned int loc)//未实现
  104.                 {
  105.                         ret = 0;
  106.                         return ret;
  107.                 }
  108. //.....

  109.         public:
  110.                  node* frist_node;//用于外部访问
  111.                  unsigned int length;//用于外部访问
  112.              node* last_node;//用于外部访问
  113.         private:
  114.                  int ret;
  115. };
  116. #endif


点击(此处)折叠或打开

  1. 测试用例:
  2. #include<iostream>
  3. #define DEBUG
  4. #include"chain.h"
  5. using namespace std;
  6. //测试类
  7. class cube
  8. {
  9.         public:
  10.                 cube(int a,int b,int c):a(a),b(b),c(c)
  11.         {
  12.                 ;
  13.         }
  14.                 int get_size() const
  15.                 {
  16.                         return a*b*c;
  17.                 }
  18.         private:
  19.                 int a;
  20.                 int b;
  21.                 int c;
  22. };
  23. //完成打印操作
  24. int printchain(my_chain* c_header)
  25. {
  26.         if(c_header->frist_node == NULL)
  27.         {
  28.                 cout<<"NULL chain" <<endl;
  29.                 return -1;
  30.         }
  31.         node* node_my = c_header->frist_node;
  32.    cout<<"chain total number:"<<c_header->length<<endl;

  33. //正向访问
  34. cout<<"正向访问"<<endl;
  35.         while(node_my != NULL)
  36.         {
  37.                 cout<<"node num:"<<node_my->num<<" data is:"<<*((int*)(node_my->data))<<endl;
  38.                 node_my = node_my->next;
  39.         }


  40.         node_my = c_header->last_node;
  41. //反向访问
  42. cout<<"反向访问"<<endl;
  43.         while(node_my != NULL)
  44.         {
  45.                 cout<<"node num:"<<node_my->num<<" data is:"<<*((int*)(node_my->data))<<endl;
  46.                 node_my = node_my->priv;
  47.         }
  48.         return 0;

  49. }

  50. int printchain_cube(my_chain* c_header)
  51. {
  52.         if(c_header->frist_node == NULL)
  53.         {
  54.                 cout<<"NULL chain" <<endl;
  55.                 return -1;
  56.         }
  57.         node* node_my = c_header->frist_node;
  58.         cout<<"chain total number:"<<c_header->length<<endl;
  59. //正向访问
  60. cout<<"正向访问"<<endl;
  61.         while(node_my != NULL)
  62.         {
  63.                 cout<<"node num:"<<node_my->num<<" data is:"<<((cube*)(node_my->data))->get_size()<<endl;
  64.                 node_my = node_my->next;
  65.         }

  66.         node_my = c_header->last_node;
  67. //反向访问
  68. cout<<"反向访问"<<endl;
  69.         while(node_my != NULL)
  70.         {
  71.                 cout<<"node num:"<<node_my->num<<" data is:"<<((cube*)(node_my->data))->get_size()<<endl;
  72.                 node_my = node_my->priv;
  73.         }

  74.         return 0;

  75. }

  76. int main()
  77. {
  78.         cout<<"---int data chain:"<<endl;
  79.         { //3个测试int数据
  80.                 my_chain* chain_int = new my_chain;//建立my_chain双向链表头
  81.                 int i = 0;
  82.                 for(i = 0;i<3;i++)
  83.                 {
  84.                         //最好使用malloc族函数使用free来释放void类型内存
  85.                         int* data = (int*)calloc(1,sizeof(int));
  86.                         //int* data = new int(i);
  87.                         (*chain_int).addnode((void*)data);
  88.                 }
  89.                 printchain(chain_int);
  90. #ifdef DEBUG
  91.                 cout<<"释放内存"<<endl;
  92. #endif
  93.                 (*chain_int).freechain();
  94.                 delete chain_int;
  95.         }
  96.    cout<<"---class data chain:"<<endl;
  97.         {//5个测试类数据
  98.                 my_chain* chain_cube = new my_chain;//建立my_chain双向的链表头
  99.                 int i = 0;
  100.                 for(i = 0;i<5;i++)
  101.                 {
  102.                         //cube* data = new cube(i,i,i);
  103.                         cube* data = (cube*)calloc(1,sizeof(cube));
  104.                         (*data)=cube(i,i,i);//默认浅拷贝,这里无碍
  105.                         (*chain_cube).addnode((void*)data);
  106.                 }
  107.                 printchain_cube(chain_cube);
  108. #ifdef DEBUG
  109.                 cout<<"释放内存"<<endl;
  110. #endif
  111.                 (*chain_cube).freechain();
  112.                 delete chain_cube;
  113.         }

  114. }


点击(此处)折叠或打开

  1. 测试结果:
  2. ---int data chain:
  3. chain total number:3
  4. 正向访问
  5. node num:1 data is:0
  6. node num:2 data is:0
  7. node num:3 data is:0
  8. 反向访问
  9. node num:3 data is:0
  10. node num:2 data is:0
  11. node num:1 data is:0
  12. 释放内存
  13. free node num:1
  14. free node num:2
  15. free node num:3
  16. ---class data chain:
  17. chain total number:5
  18. 正向访问
  19. node num:1 data is:0
  20. node num:2 data is:1
  21. node num:3 data is:8
  22. node num:4 data is:27
  23. node num:5 data is:64
  24. 反向访问
  25. node num:5 data is:64
  26. node num:4 data is:27
  27. node num:3 data is:8
  28. node num:2 data is:1
  29. node num:1 data is:0
  30. 释放内存
  31. free node num:1
  32. free node num:2
  33. free node num:3
  34. free node num:4
  35. free node num:5
内存泄露检测:
==4624== 
==4624== HEAP SUMMARY:
==4624==     in use at exit: 0 bytes in 0 blocks
==4624==   total heap usage: 18 allocs, 18 frees, 392 bytes allocated
==4624== 
==4624== All heap blocks were freed -- no leaks are possible
==4624== 
==4624== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==4624== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


下一篇: C++操作符重载
请登录后发表评论 登录
全部评论

注册时间:2008-10-13

  • 博文量
    622
  • 访问量
    2741479