非固定類型數據結點鏈表的一種實現方法

摘 要：鏈表是用一組任意的存儲單元來存放線性表中的結點，這組存儲單元可以不連續地分布在內存中任何的位置上。鏈表存儲數據，對于結點的數據域來說，一旦確定了結點類型之后，數據域的數據類型就確定了，這導致了鏈表的不通用性。也就是說一條鏈表上只能存儲一種或者幾種已經確定的數據類型的數據。但是要想在此條鏈表上存儲另外一種或者幾種數據類型的數據就不能適用了。因此，我就解決此類問題，使得后一個結點的數據類型不受前一個結點數據類型的影響。這種方法不是單純的一種數據類型而是一種聯合體，它里面有很多種的數據類型，當一種數據類型輸入時，它就會自動匹配該數據的類型，并且可以最小化的節省空間。

關鍵詞：鏈表 數據域 指針域 結點 聯合體 結構體 回調函數

中圖分類號：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

作者簡介：王若，男，漢族，安徽省淮南市壽縣，工作單位：安徽師范大學，在校學生