C++实现通用双向链表

发布时间：2020-08-04 16:50:27 来源：ITPUB博客阅读：504 作者：gaopengtttt 栏目：互联网科技

使用C++完成双向通用链表
双向链表不用多说，通用链表因为数据结构不确定的，使用一个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)

向AI问一下细节

C++实现通用双向链表

猜你喜欢

最新资讯

相关推荐

相关标签