非固定類型數(shù)據(jù)結(jié)點(diǎn)鏈表的一種實(shí)現(xiàn)方法

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

關(guān)鍵詞：鏈表 數(shù)據(jù)域 指針域 結(jié)點(diǎn) 聯(lián)合體 結(jié)構(gòu)體 回調(diào)函數(shù)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-9082 （2017） 04-0003-01

//結(jié)點(diǎn)中數(shù)據(jù)域部分用聯(lián)合體代替

typedef union data_

{

double d；

float f；

int i；

char c；

}Data；

//鏈表的結(jié)點(diǎn)類型

typedef struct Clist_node

{

Data *data；//數(shù)據(jù)

struct Clist_node *next；//指向下一個(gè)結(jié)點(diǎn)的指針

}Clist_node；

typedef struct Clist

{

int size；//鏈表結(jié)點(diǎn)的大小

Clist_node *head；//頭結(jié)點(diǎn)，一般沒有有效數(shù)據(jù)（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；

程序分析：

在申明結(jié)點(diǎn)類型的時(shí)候，它的數(shù)據(jù)域是一個(gè)指向堆空間的指針，指針域就是一個(gè)指向下個(gè)結(jié)點(diǎn)類型的指針。

我們?cè)阪湵沓跏蓟臅r(shí)候，就可以把鏈表內(nèi)部的行為和（lish.c）中實(shí)際的行為處理函數(shù)相對(duì)應(yīng)，但是一般來說把初始化函數(shù)和銷毀函數(shù)都不放在鏈表內(nèi)部作為行為。

Clist_insert//此函數(shù)是用于插入結(jié)點(diǎn)，pos是需要插入的位置，而data是指向一個(gè)需要插入數(shù)據(jù)域的指針變量，該指針?biāo)邮盏牡刂肥亲鳛槠鹗嫉刂返牟⑶乙詾閟ize大小的字節(jié)的數(shù)據(jù)。為了適應(yīng)更多的類型的數(shù)據(jù)以及通用性，結(jié)點(diǎn)的數(shù)據(jù)域是一個(gè)聯(lián)合體類型的指針，然后開辟size個(gè)字節(jié)大小的堆空間。當(dāng)每次傳進(jìn)來的size不同也就是代表著以data指向的地址作為起始地址，開始往后取size個(gè)字節(jié)大小的數(shù)據(jù)，然后分類存儲(chǔ)在聯(lián)合體中的不同類型的基本類型變量中。

Clist_modify_pos_data//把pos位置上的數(shù)據(jù)修改為new_data。修改數(shù)據(jù)的時(shí)候，是根據(jù)結(jié)點(diǎn)位置來做修改，把原來數(shù)據(jù)域聯(lián)合體指針指向的堆空間內(nèi)存里存儲(chǔ)的數(shù)據(jù)修改為以new_data指針指向的大小為size字節(jié)的數(shù)據(jù)。

Clist_del_pos//刪除pos位置的結(jié)點(diǎn)

刪除操作是是根據(jù)結(jié)點(diǎn)的位置來刪除，我們根據(jù)提供的pos大小和鏈表的大小list->size做比較，不斷遍歷每個(gè)結(jié)點(diǎn)，當(dāng)?shù)降趐os結(jié)點(diǎn)時(shí)，注意，我在插入次結(jié)點(diǎn)的時(shí)候開辟了兩段堆內(nèi)存，一段是給數(shù)據(jù)域，另外一段是結(jié)點(diǎn)本身，所以在刪除的時(shí)候，要先釋放數(shù)據(jù)域指向的堆空間，再釋放結(jié)點(diǎn)空間。若順序操作反了，則會(huì)使數(shù)據(jù)域的指向的內(nèi)存空間找不到，造成內(nèi)存泄露。

Clist_search_node_pos//查詢鏈表上的pos位置結(jié)點(diǎn)，把數(shù)據(jù)利用回調(diào)函數(shù)顯示出來。

查詢操作是根據(jù)結(jié)點(diǎn)的位置來查詢的，當(dāng)查找到第pos個(gè)結(jié)點(diǎn)時(shí)候，把結(jié)點(diǎn)傳遞給print（）函數(shù)，該函數(shù)作為回調(diào)，把用戶在test.c申明的函數(shù)傳進(jìn)來。在test.c中的實(shí)現(xiàn)的打印函數(shù)是根據(jù)數(shù)據(jù)域的指針指向的數(shù)據(jù)類型分開處理的。

總結(jié)

起初在設(shè)計(jì)的時(shí)候就是單層的考慮需要在鏈表中插入一直已知的數(shù)據(jù)類型，比如說是int或者是double等，但是這不滿足通用性，如果說我第一次使用該鏈表插入的數(shù)據(jù)類型是int類型，但是第二次我需要插入double，那么由于數(shù)據(jù)類型的不匹配將導(dǎo)致數(shù)據(jù)被截?cái)嗷蛘卟缓戏?。為了解決這個(gè)問題，我用void *data類型來接收需要插入數(shù)據(jù)的地址，然后直接將data指針賦值給結(jié)點(diǎn)的數(shù)據(jù)域，這會(huì)導(dǎo)致一個(gè)問題，就是如果說傳進(jìn)來的地址不變，但是地址對(duì)應(yīng)的數(shù)據(jù)是在變化的，最終使得所有的結(jié)點(diǎn)中的數(shù)據(jù)類型全部是一樣，因?yàn)樗鼈兌际侵赶蛞粔K內(nèi)存區(qū)域，從而達(dá)不到原本的目的。所以我最終使用結(jié)點(diǎn)中數(shù)據(jù)域用一個(gè)指針指向一塊堆內(nèi)存，在堆內(nèi)存中用一個(gè)聯(lián)合體類型的變量來保存，聯(lián)合體可以實(shí)現(xiàn)數(shù)據(jù)共享，并且盡量占用更少的內(nèi)存這一很好的特點(diǎn)。

參考文獻(xiàn)

[1]（美）勞頓（Loudom.K.）著；肖翔陳舸譯.算法精解：C語言描述[R]北京：機(jī)械工業(yè)出版社，2012，8

[2]（美）霍爾頓（Horton，I.）著；楊浩譯.C語言入門經(jīng)典（第五版）北京：清華大學(xué)出版社.2013

[3]陸玲，周航慈著；嵌入式操作系統(tǒng)軟件設(shè)計(jì)中的數(shù)據(jù)結(jié)構(gòu)北京：北京航空航天大學(xué)出版社，2008，8

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