APP下载

非固定类型数据结点链表的一种实现方法

2017-05-23王若

中文信息 2017年4期
关键词:链表联合体结点

摘 要:链表是用一组任意的存储单元来存放线性表中的结点,这组存储单元可以不连续地分布在内存中任何的位置上。链表存储数据,对于结点的数据域来说,一旦确定了结点类型之后,数据域的数据类型就确定了,这导致了链表的不通用性。也就是说一条链表上只能存储一种或者几种已经确定的数据类型的数据。但是要想在此条链表上存储另外一种或者几种数据类型的数据就不能适用了。因此,我就解决此类问题,使得后一个结点的数据类型不受前一个结点数据类型的影响。这种方法不是单纯的一种数据类型而是一种联合体,它里面有很多种的数据类型,当一种数据类型输入时,它就会自动匹配该数据的类型,并且可以最小化的节省空间。

关键词:链表 数据域 指针域 结点 联合体 结构体 回调函数

中图分类号:TP311 文献标识码:A 文章编号:1003-9082 (2017) 04-0003-01

//结点中数据域部分用联合体代替

typedef union data_

{

double d;

float f;

int i;

char c;

}Data;

//链表的结点类型

typedef struct Clist_node

{

Data *data;//数据

struct Clist_node *next;//指向下一个结点的指针

}Clist_node;

typedef struct Clist

{

int size;//鏈表结点的大小

Clist_node *head;//头结点,一般没有有效数据(data)

int (*insert)(struct Clist *,size_t pos,void* data,size_t size); int (*modify_pos_data)(struct Clist*,int pos,void * new_data,size_t size);

int (*del_pos)(struct Clist *,int pos);

int(*search_node_pos)(struct Clist*,int pos,\

void (*print)(Clist_node *));

int (*is_empty)(struct Clist *);

}Clist;

程序分析:

在申明结点类型的时候,它的数据域是一个指向堆空间的指针,指针域就是一个指向下个结点类型的指针。

我们在链表初始化的时候,就可以把链表内部的行为和(lish.c)中实际的行为处理函数相对应,但是一般来说把初始化函数和销毁函数都不放在链表内部作为行为。

Clist_insert//此函数是用于插入结点,pos是需要插入的位置,而data是指向一个需要插入数据域的指针变量,该指针所接收的地址是作为起始地址的并且以为size大小的字节的数据。为了适应更多的类型的数据以及通用性,结点的数据域是一个联合体类型的指针,然后开辟size个字节大小的堆空间。当每次传进来的size不同也就是代表着以data指向的地址作为起始地址,开始往后取size个字节大小的数据,然后分类存储在联合体中的不同类型的基本类型变量中。

Clist_modify_pos_data//把pos位置上的数据修改为new_data。修改数据的时候,是根据结点位置来做修改,把原来数据域联合体指针指向的堆空间内存里存储的数据修改为以new_data指针指向的大小为size字节的数据。

Clist_del_pos//删除pos位置的结点

删除操作是是根据结点的位置来删除,我们根据提供的pos大小和链表的大小list->size做比较,不断遍历每个结点,当到第pos结点时,注意,我在插入次结点的时候开辟了两段堆内存,一段是给数据域,另外一段是结点本身,所以在删除的时候,要先释放数据域指向的堆空间,再释放结点空间。若顺序操作反了,则会使数据域的指向的内存空间找不到,造成内存泄露。

Clist_search_node_pos//查询链表上的pos位置结点,把数据利用回调函数显示出来。

查询操作是根据结点的位置来查询的,当查找到第pos个结点时候,把结点传递给print()函数,该函数作为回调,把用户在test.c申明的函数传进来。在test.c中的实现的打印函数是根据数据域的指针指向的数据类型分开处理的。

总结

起初在设计的时候就是单层的考虑需要在链表中插入一直已知的数据类型,比如说是int或者是double等,但是这不满足通用性,如果说我第一次使用该链表插入的数据类型是int类型,但是第二次我需要插入double,那么由于数据类型的不匹配将导致数据被截断或者不合法。为了解决这个问题,我用void *data类型来接收需要插入数据的地址,然后直接将data指针赋值给结点的数据域,这会导致一个问题,就是如果说传进来的地址不变,但是地址对应的数据是在变化的,最终使得所有的结点中的数据类型全部是一样,因为它们都是指向一块内存区域,从而达不到原本的目的。所以我最终使用结点中数据域用一个指针指向一块堆内存,在堆内存中用一个联合体类型的变量来保存,联合体可以实现数据共享,并且尽量占用更少的内存这一很好的特点。

参考文献

[1](美)劳顿(Loudom.K.)著;肖翔陈舸译.算法精解:C语言描述[R]北京:机械工业出版社,2012,8

[2](美)霍尔顿(Horton,I.)著;杨浩译.C语言入门经典(第五版)北京:清华大学出版社.2013

[3]陆玲,周航慈著;嵌入式操作系统软件设计中的数据结构北京:北京航空航天大学出版社,2008,8

作者简介:王若,男,汉族,安徽省淮南市寿县,工作单位:安徽师范大学,在校学生

猜你喜欢

链表联合体结点
基于二进制链表的粗糙集属性约简
基于链表多分支路径树的云存储数据完整性验证机制
Ladyzhenskaya流体力学方程组的确定模与确定结点个数估计
创新思维——打造智库联合体
链表方式集中器抄表的设计
归脾汤加减联合体针治疗心脾两虚型失眠48例
基于Raspberry PI为结点的天气云测量网络实现
工程联合体小议
基于DHT全分布式P2P-SIP网络电话稳定性研究与设计