C++实现通用双向链表
使用C++完成双向通用链表
双向链表不用多说,通用链表因为数据结构不确定的,使用一个VOID指针指向数据,
什么数据都可以挂上去,这样来封装链表,可以作为基础类也可以单独使用,
这里只是为了练习C++封装的语法,实现了简单的增加和删除链表由于实际数据
类型不能确定,打印链表数据使用公有函数来完成,完成了正向打印反向打印,
演示了数据类型为简单的int类型也演示了数据类型为class类型。
代码如下:
内存泄露检测:
==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)
双向链表不用多说,通用链表因为数据结构不确定的,使用一个VOID指针指向数据,
什么数据都可以挂上去,这样来封装链表,可以作为基础类也可以单独使用,
这里只是为了练习C++封装的语法,实现了简单的增加和删除链表由于实际数据
类型不能确定,打印链表数据使用公有函数来完成,完成了正向打印反向打印,
演示了数据类型为简单的int类型也演示了数据类型为class类型。
代码如下:
点击(此处)折叠或打开
-
链表实现:
-
#include<iostream>
-
#include<stdlib.h>
-
using namespace std;
-
/* data数据类型进行void封装,为通用链表
-
* node为节点的基本数据结构
-
* addnode使用void数据进行连接到链表中,造成链表
-
* frist_node为第一个结点位置,开放访问
-
* last_node为最后一个节点位置,开放访问
-
* length为节点长度,开放访问
-
* 只是完成增加节点和释放节点功能,其他功能也相应简单,用到再加,打印功能由于
-
* 数据类型不确定无法完成。
-
*/
-
#ifndef _CHAIN_
-
#define _CHAIN_
-
struct node
-
{
-
void* data;
-
node* next;
-
node* priv;
-
unsigned int num;
-
node()
-
{
-
data = NULL;
-
next = NULL;
-
priv = NULL;
-
num = 0;
-
}
-
};
-
-
-
class my_chain
-
{
-
public:
-
my_chain()
-
{
-
-
this->frist_node = NULL;
-
this->length = 0;
-
this->last_node = NULL;
-
}
-
//-1 data is null;
-
// 0 normal
-
// 传入一个void指针的数据类型,链表增加一个节点
-
int addnode(void* data)
-
{
-
ret = 0 ;
-
-
if(data == NULL)
-
{
-
ret = -1;
-
return ret;
-
}
-
-
node* c_node = new node; //分配节点内存
-
-
if(this->frist_node == NULL)
-
{
-
-
this->frist_node = c_node;
-
}
-
if(this->last_node == NULL)
-
{
-
c_node->next = NULL;
-
c_node->priv = NULL;
-
c_node->data = data;
-
}
-
else
-
{
-
c_node->next = NULL;
-
c_node->priv = this->last_node;
-
this->last_node->next = c_node;
-
c_node->data = data;
-
}
-
this->last_node = c_node;
-
this->length++;
-
c_node->num = this->length;
-
return ret;
-
}
-
//ret=1 null list;
-
//ret=0 normal list;
-
//释放整个链表内存
-
int freechain()
-
{
-
ret = 0;
-
if(this->last_node == NULL)
-
{
-
ret = 1;
-
cout<<"null list"<<endl;
-
return ret;
-
}
-
node* node_my = this->frist_node;
-
while(node_my != NULL)
-
{
-
#ifdef DEBUG
-
cout<<"free node num:"<< node_my->num<<endl;
-
#endif
-
node* temp = node_my;
-
node_my = node_my->next;
-
free(temp->data);//删除节点数据内存?跨函数free
-
delete temp;//删除节点node内存
-
}
-
}
-
//....
-
int delnode() //未实现
-
{
-
ret = 0;
-
return ret;
-
}
-
-
int addmodnode(unsigned int loc)//未实现
-
{
-
ret = 0;
-
return ret;
-
}
-
//.....
-
-
public:
-
node* frist_node;//用于外部访问
-
unsigned int length;//用于外部访问
-
node* last_node;//用于外部访问
-
private:
-
int ret;
-
};
- #endif
点击(此处)折叠或打开
-
测试用例:
-
#include<iostream>
-
#define DEBUG
-
#include"chain.h"
-
using namespace std;
-
//测试类
-
class cube
-
{
-
public:
-
cube(int a,int b,int c):a(a),b(b),c(c)
-
{
-
;
-
}
-
int get_size() const
-
{
-
return a*b*c;
-
}
-
private:
-
int a;
-
int b;
-
int c;
-
};
-
//完成打印操作
-
int printchain(my_chain* c_header)
-
{
-
if(c_header->frist_node == NULL)
-
{
-
cout<<"NULL chain" <<endl;
-
return -1;
-
}
-
node* node_my = c_header->frist_node;
-
cout<<"chain total number:"<<c_header->length<<endl;
-
-
//正向访问
-
cout<<"正向访问"<<endl;
-
while(node_my != NULL)
-
{
-
cout<<"node num:"<<node_my->num<<" data is:"<<*((int*)(node_my->data))<<endl;
-
node_my = node_my->next;
-
}
-
-
-
node_my = c_header->last_node;
-
//反向访问
-
cout<<"反向访问"<<endl;
-
while(node_my != NULL)
-
{
-
cout<<"node num:"<<node_my->num<<" data is:"<<*((int*)(node_my->data))<<endl;
-
node_my = node_my->priv;
-
}
-
return 0;
-
-
}
-
-
int printchain_cube(my_chain* c_header)
-
{
-
if(c_header->frist_node == NULL)
-
{
-
cout<<"NULL chain" <<endl;
-
return -1;
-
}
-
node* node_my = c_header->frist_node;
-
cout<<"chain total number:"<<c_header->length<<endl;
-
//正向访问
-
cout<<"正向访问"<<endl;
-
while(node_my != NULL)
-
{
-
cout<<"node num:"<<node_my->num<<" data is:"<<((cube*)(node_my->data))->get_size()<<endl;
-
node_my = node_my->next;
-
}
-
-
node_my = c_header->last_node;
-
//反向访问
-
cout<<"反向访问"<<endl;
-
while(node_my != NULL)
-
{
-
cout<<"node num:"<<node_my->num<<" data is:"<<((cube*)(node_my->data))->get_size()<<endl;
-
node_my = node_my->priv;
-
}
-
-
return 0;
-
-
}
-
-
int main()
-
{
-
cout<<"---int data chain:"<<endl;
-
{ //3个测试int数据
-
my_chain* chain_int = new my_chain;//建立my_chain双向链表头
-
int i = 0;
-
for(i = 0;i<3;i++)
-
{
-
//最好使用malloc族函数使用free来释放void类型内存
-
int* data = (int*)calloc(1,sizeof(int));
-
//int* data = new int(i);
-
(*chain_int).addnode((void*)data);
-
}
-
printchain(chain_int);
-
#ifdef DEBUG
-
cout<<"释放内存"<<endl;
-
#endif
-
(*chain_int).freechain();
-
delete chain_int;
-
}
-
cout<<"---class data chain:"<<endl;
-
{//5个测试类数据
-
my_chain* chain_cube = new my_chain;//建立my_chain双向的链表头
-
int i = 0;
-
for(i = 0;i<5;i++)
-
{
-
//cube* data = new cube(i,i,i);
-
cube* data = (cube*)calloc(1,sizeof(cube));
-
(*data)=cube(i,i,i);//默认浅拷贝,这里无碍
-
(*chain_cube).addnode((void*)data);
-
}
-
printchain_cube(chain_cube);
-
#ifdef DEBUG
-
cout<<"释放内存"<<endl;
-
#endif
-
(*chain_cube).freechain();
-
delete chain_cube;
-
}
-
- }
点击(此处)折叠或打开
-
测试结果:
-
---int data chain:
-
chain total number:3
-
正向访问
-
node num:1 data is:0
-
node num:2 data is:0
-
node num:3 data is:0
-
反向访问
-
node num:3 data is:0
-
node num:2 data is:0
-
node num:1 data is:0
-
释放内存
-
free node num:1
-
free node num:2
-
free node num:3
-
---class data chain:
-
chain total number:5
-
正向访问
-
node num:1 data is:0
-
node num:2 data is:1
-
node num:3 data is:8
-
node num:4 data is:27
-
node num:5 data is:64
-
反向访问
-
node num:5 data is:64
-
node num:4 data is:27
-
node num:3 data is:8
-
node num:2 data is:1
-
node num:1 data is:0
-
释放内存
-
free node num:1
-
free node num:2
-
free node num:3
-
free node num:4
- 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)