备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

C++实现通用双向链表

2017-03-08 1253
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 使用C++完成双向通用链表 双向链表不用多说，通用链表因为数据结构不确定的，使用一个VOID指针指向数据， 什么数据都可以挂上去，这样来封装链表，可以作为基础类也可以单独使用， 这里只是为了练习C++封装的语法，实现了简单的增加和删除链表由于实际数据 类型不能确定，打印链表数据使用公有函数来完成，完成了正向打印反向打印， 演示了数据类型为简单的int类型也演示了数据类型为class类型。
使用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. };


  32. class my_chain
  33. {
  34.         public:
  35.                 my_chain()
  36.                 {

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

  49.                         if(data == NULL)
  50.                         {
  51.                                 ret = -1;
  52.                                 return ret;
  53.                         }

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

  57.                         if(this->frist_node == NULL)
  58.                         {

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

  111.                 int addmodnode(unsigned int loc)//未实现
  112.                 {
  113.                         ret = 0;
  114.                         return ret;
  115.                 }
  116. //.....

  118.         public:
  119.                  node* frist_node;//用于外部访问
  120.                  unsigned int length;//用于外部访问
  121.              node* last_node;//用于外部访问
  122.         private:
  123.                  int ret;
  124. };
  125. #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;

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


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

  53. }

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

  72.         node_my = c_header->last_node;
  73. //反向访问
  74. cout<<"反向访问"<<endl;
  75.         while(node_my != NULL)
  76.         {
  77.                 cout<<"node num:"<<node_my->num<<" data is:"<<((cube*)(node_my->data))->get_size()<<endl;
  78.                 node_my = node_my->priv;
  79.         }

  81.         return 0;

  83. }

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

  124. }


点击(此处)折叠或打开

  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++
测试技术
关键词：
C++链表
C++双向链表
C++实现
重庆八怪
目录
相关文章
北飞的山羊
|
29天前
|
C++
【链表】还不会用C++实现链表？一文教会你各种链表的实现
【链表】还不会用C++实现链表？一文教会你各种链表的实现
北飞的山羊
36 0
凉开水白菜
|
25天前
|
存储 缓存 C++
C++链表常用的函数编写（增查删改）内附完整程序
C++链表常用的函数编写（增查删改）内附完整程序
凉开水白菜
24 0
泡沫o0
|
1月前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
38 0
泡沫o0
|
1月前
|
存储 缓存 算法
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
泡沫o0
51 0
醋溜马桶圈
|
2月前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
醋溜马桶圈
23 1
红目香薰
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
红目香薰
29 0
SarPro
|
2月前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
SarPro
60 1
HannYang
|
3月前
|
Python Linux Ubuntu
Linux系统部署Python语言开发运行环境
Linux系统部署Python语言开发运行环境
HannYang
93 0
Linux系统部署Python语言开发运行环境
HannYang
|
3月前
|
Go Unix 开发者
Go语言time库，时间和日期相关的操作方法
Go语言time库，时间和日期相关的操作方法
HannYang
51 0
Go语言time库，时间和日期相关的操作方法
HannYang
|
3月前
|
Java Go C++
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
HannYang
40 0
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii

热门文章

最新文章

  • 1
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 2
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 3
    【C++ 职业方向】C++ 职业方向探索：工作职责、编程技能与MBTI人格匹配
  • 4
    拓扑排序解析：计算机与数学的交汇点以及C++ 实现
  • 5
    【C++ 可调用对象的应用】C++设计模式与现代编程技巧：深入可调用对象的世界
  • 6
    【C/C++ 性能优化】提高C++程序的缓存命中率以优化性能
  • 7
    【C++ 软件设计思路】学习C++中如何生成唯一标识符：从UUID到自定义规则
  • 8
    C++代码复用策略及与标准兼容性指南
  • 9
    【C++ 基本知识】现代C++内存管理：探究std::make_系列函数的力量
  • 10
    深入对比：Qt 的 QFile/QFileInfo 和与 C++17 Filesystem 和标准文件流 的细节剖析
  • 1
    【C++】—— c++11之智能指针
    45
  • 2
    【C++】—— C++11之线程库
    36
  • 3
    【C++】—— C++11之可变参数模板
    28
  • 4
    【C++】—— c++11新的类功能
    27
  • 5
    【C++】—— C++11新特性之 “右值引用和移动语义”
    30
  • 6
    【C++】—— c++11新特性之 lambda
    25
  • 7
    【C++】容器篇（五）—— map和set的基本介绍
    35
  • 8
    【C++】容器篇（四）—— queue的基本介绍以及模拟实现
    28
  • 9
    【C++】容器篇（三）—— stack的基本介绍及其模拟实现
    25
  • 10
    【C++】容器篇（二）——List的基本概述以及模拟实现
    31

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）