C++实现通用双向链表

使用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)

时间： 2024-09-09 17:34:14

C++实现通用双向链表的相关文章

MYSQL INNODB 中通用双向链表的实现

原创:如果有误请支持 源码在Ut0lst.h中 注意:这里我将链表中的实际的串联的数据叫做数据类比如:lock_t.mem_block_t 链表作为一种的非常重要的数据结构,在任何地方都会用到,这里简单解释一下innodb双向 链表的实现,让我们来看看innodb链表设计的魅力: 经常在某些结构体中看到 UT_LIST_BASE_NODE_T(mem_block_t) base; UT_LIST_NODE_T(mem_block_t) list;  作为最为基本的一种的数据结构innodb中实现

Nginx 数据结构 ngx_queue_t

ngx_queue_t不分配内存,只是将已分配好的内存用双向链表连接. 消耗内存少,虽太适合超大规模数据的排序,但胜在简单使用. 作为C语言提供的通用双向链表,其设计思路值得参考. 在理解设计的时候可以将其想象成环形结构. typedef struct ngx_queue_s  ngx_queue_t; struct ngx_queue_s  {     ngx_queue_t* prev;     ngx_queue_t* next; }; 比较迷惑的是该容器与其中的元素使用相同的结构体. 操

C实现通用数据结构--双向链表

双向链表概述 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别 指向直接后继next和直接前驱prev.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.为了标识链表的头和尾,将 第一个元素的prev指针和最后一个元素的next指针设置为NULL 要反向遍历整个双向链表,使用prev指针从尾到头的顺序访问各个元素,因此为每个元素增加了一个指针的代价,换来的是双向链表更加灵活的访问. 本文地址:http://www.cnblogs.com/arc

Linux 内核里的数据结构——双向链表

Linux 内核里的数据结构--双向链表 Linux 内核中自己实现了双向链表,可以在 include/linux/list.h 找到定义.我们将会首先从双向链表数据结构开始介绍内核里的数据结构.为什么?因为它在内核里使用的很广泛,你只需要在 free-electrons.com 检索一下就知道了. 首先让我们看一下在 include/linux/types.h 里的主结构体: struct list_head { struct list_head *next, *prev; }; 你可能注意到

最高效率的对象深拷贝通用方法

问题描述 曾有人发帖要高效的对象拷贝通用方法,当时只给了一个简单类型的拷贝,现在挤出点时间完成了这个功能,内部的引用类型依次深度拷贝.完整代码见博客:这里发帖收集建议意见,简单的测试了下,已经非常完美的运行了,目前能支持任何带无参数的构造函数的类的深拷贝,一元数组的深拷贝,数组和类的循环嵌套深拷贝(即父子关系的类,或双向链表).感兴趣的朋友,可以研究下Emit部分,这是C#的精华,也是能够提高效率的必备利器,嫌.NET慢的人不要光抱怨,那是因为你们不懂优化代码,会了Emit就可以最高限度的优化代

逆天通用水印扩展篇~新增剪贴板系列的功能和手动配置，卸除原基础不常用的功能

常用技能:http://www.cnblogs.com/dunitian/p/4822808.html#skill 逆天博客:http://dnt.dkil.net 逆天通用水印支持Winform,WPF,Web,WP,Win10.支持位置选择(9个位置 ==>[X]):http://www.cnblogs.com/dunitian/p/4939369.html 本次添加了一些新东西,比如剪贴板之类的水印操作.完善了部分功能(比如文件过滤,非Bitmap图片的处理,以及一些其他玩意等待你的发现)

FTP服务器的防火墙通用设置规则

  此FTP服务器的防火墙通用设置规则适用于Windows(包括服务器版和桌面版).Linux服务器以及可能的其他操作系统. 在配置好FTP服务器后将发起FTP服务的程序(如Windows的svchost.exe或FileZilla server.exe)而不仅仅是端口允许通过防火墙,程序(此处特指Windows的svchost.exe)不用带参数. svchost.exe这个例外,必须通过控制面板中的 " 允许程序通过 Windows 防火墙通信" ,使得 "Windows

网络子系统14_邻居子系统通用接口

//创建一个新的邻居项 //参考 深入理解linux网络技术内幕 // 1.邻居子系统为具体的邻居协议,提供通用的功能接口 // 2.系统中所有的邻居协议被链接在neigh_tables链表中 // 3.neigh_table代表一个具体的邻居协议 // 4.具体邻居协议在运行时的行为,可以通过struct neigh_parms调节, // neigh_params与设备关联,每个邻居协议neigh_table提供一个默认的neigh_params. //注册一个邻居协议到系统中 // 1.与

iphone-修改iPhone通用程序的方向

问题描述 修改iPhone通用程序的方向 我想要开发的程序能适应iPad所有方向,在iPhone中只要UIInterfaceOrientationPortrait 和UIInterfaceOrientationPortraitUpsideDown这两个.代码如下: -(BOOL)shouldAutorotate { if ([[UIDevice currentDevice] userInterfaceIdiom] == UIUserInterfaceIdiomPhone){ return NO;