摘 要:鏈表是用一組任意的存儲(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é)生