C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)鏈表的示例代碼
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱為結(jié)點(diǎn))組成,結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分:一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域,另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
結(jié)構(gòu)體定義已經(jīng)函數(shù)聲明
節(jié)點(diǎn)結(jié)構(gòu)體定義
typedef struct SNode{ void *pdata; //存儲(chǔ)數(shù)據(jù),這個(gè)數(shù)據(jù)可以是任意類型 struct SNode *next; //節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)地址 }SNode; typedef struct SNode* SLink; //定義一個(gè)鏈表
函數(shù)聲明
//創(chuàng)建一個(gè)鏈表 SLink create_slink(); //初始化一個(gè)鏈表 void init_slink(SLink *link); //判斷鏈表是否為空 bool is_empty(SLink link); //獲得鏈表存儲(chǔ)的個(gè)數(shù) size_t size(SLink link); //插入元素 元素存儲(chǔ)在pdata,一共size個(gè)字節(jié) int insert(SLink link,size_t index,void *pdata,size_t size); //獲得指定下標(biāo)的節(jié)點(diǎn)元素,并且返回其地址 void *get(SLink link,size_t index); //刪除一個(gè)節(jié)點(diǎn) int remove_data(SLink link,size_t index); //鏈表逆序 SLink reverse(SLink link); //清空鏈表 void clear(SLink link); //銷毀鏈表 void destroy(SLink link); //遍歷鏈表(通過(guò)函數(shù)指針完成用戶需要的要求) void foreach(SLink link,void (*func)(const void *)); //通過(guò)值查找某個(gè)節(jié)點(diǎn) void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)); //通過(guò)值刪除所有需要?jiǎng)h除的節(jié)點(diǎn) int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)); //鏈表排序,通過(guò)冒泡排序 void sort(SLink link,int (*compare)(const void *,const void *));
函數(shù)實(shí)現(xiàn)
創(chuàng)建一個(gè)鏈表
首先動(dòng)態(tài)鏈表一般有一個(gè)頭結(jié)點(diǎn)(也不是必須有,但是頭結(jié)點(diǎn)可以讓后面的算法變得簡(jiǎn)單些),這個(gè)頭結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù),只存放第一個(gè)節(jié)點(diǎn)(存放數(shù)據(jù)的節(jié)點(diǎn),也叫作首節(jié)點(diǎn))的地址,所以我們可以讓節(jié)點(diǎn)的pdata為null。
具體實(shí)現(xiàn)如下:
首先我們寫一個(gè)函數(shù)實(shí)現(xiàn)生成一個(gè)節(jié)點(diǎn),這樣在我們以后只要有插入節(jié)點(diǎn)的操作就可以用這個(gè)靜態(tài)方法來(lái)實(shí)現(xiàn);這個(gè)函數(shù)我們需要傳數(shù)據(jù)的地址,數(shù)據(jù)的大小(這樣我們才能把數(shù)據(jù)拷貝到節(jié)點(diǎn)里面去),還有下一個(gè)節(jié)點(diǎn)的地址;
static SNode *create_node(void *pdata,size_t size,SNode *next){ SNode *node = malloc(sizeof(SNode)); //先用malloc申請(qǐng)一塊動(dòng)態(tài)內(nèi)存 if(pdata == NULL){ //如果傳進(jìn)來(lái)的數(shù)據(jù)地址為null node->pdata = NULL; }else{ node->pdata = malloc(size); //否則為數(shù)據(jù)也申請(qǐng)一塊大小為size的動(dòng)態(tài)內(nèi)存, memcpy(node->pdata,pdata,size); //把pdata指向的數(shù)據(jù)通過(guò)memcpy拷貝到node->pdata里去,拷貝size個(gè)字節(jié) } node->next = next; //讓節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn) return node; //返回這個(gè)節(jié)點(diǎn) }
所以有了上面這個(gè)靜態(tài)方法,后面的創(chuàng)建一個(gè)鏈表還是插入一個(gè)節(jié)點(diǎn)就變得很簡(jiǎn)單了
因?yàn)槲覀儎傞_始創(chuàng)建的是一個(gè)空鏈表,即只有一個(gè)頭結(jié)點(diǎn),因此不傳數(shù)據(jù)
SLink create_slink(){ //return create_node(NULL,0,NULL); SNode *head = create_node(NULL,0,NULL); return head; }
除了創(chuàng)建一個(gè)鏈表,我們還可以初始化一個(gè)鏈表,(即在其他函數(shù)里先定義一個(gè)節(jié)點(diǎn))再給它初始化。
這里我們傳進(jìn)來(lái)一個(gè)鏈表的地址,鏈表類型為SNode *,它的地址即為SNode **類型,因?yàn)橹挥袀鬟f一個(gè)元素得地址,我們才能在一個(gè)函數(shù)中改變這個(gè)元素得值(函數(shù)間的傳參是值賦值)。
void init_slink(SLink *link){ *link = create_node(NULL,0,NULL); //同樣調(diào)用生成節(jié)點(diǎn)的靜態(tài)方法 }
判斷鏈表是否為空
所謂空鏈表就是指只有一個(gè)頭結(jié)點(diǎn),這個(gè)頭結(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù),只是記錄首節(jié)點(diǎn)的地址,如果這個(gè)首節(jié)點(diǎn)的地址為空,那么這就是一個(gè)空鏈表
bool is_empty(SLink link){ return link->next == NULL; }
獲得鏈表中節(jié)點(diǎn)的個(gè)數(shù)
鏈表中的節(jié)點(diǎn)是指存儲(chǔ)了元素的節(jié)點(diǎn),所以不能包含頭結(jié)點(diǎn),我們只需要把這個(gè)節(jié)點(diǎn)遍歷一遍,如果某個(gè)節(jié)點(diǎn)的下一個(gè)地址(next)為空,那這個(gè)節(jié)點(diǎn)就是尾結(jié)點(diǎn)
} size_t size(SLink link){ size_t cnt = 0; //用來(lái)記錄節(jié)點(diǎn)個(gè)數(shù) SNode *node = link->next; //從首節(jié)點(diǎn)開始算起 while(node != NULL){ //遍歷這個(gè)鏈表 ++cnt; node = node->next; } return cnt; }
在某個(gè)特定的位置插入一個(gè)元素
在index的位置插入一個(gè)元素,就是我們需要把index的位置變成我們新插入的節(jié)點(diǎn)。
在鏈表中插入一個(gè)節(jié)點(diǎn),并不像在線性表(數(shù)組)中那么復(fù)雜,在線性表中插入一個(gè)元素我們需要把插入節(jié)點(diǎn)后面的元素都往后移,這樣增加了很多負(fù)擔(dān),但是在鏈表中的插入節(jié)點(diǎn)(或者刪除節(jié)點(diǎn)),都只需要改變一下附近節(jié)點(diǎn)的指針指向就OK了,所以操作變得簡(jiǎn)單了很多,下面我們來(lái)詳細(xì)講解一下如何插入一個(gè)節(jié)點(diǎn)。
首先肯定是找到我們插入的位置
如上圖所示,我們需要在下標(biāo)為3的位置插入一個(gè)節(jié)點(diǎn),那我們?cè)撛趺醋瞿?
是的我們可以想辦法獲得下標(biāo)為2這個(gè)節(jié)點(diǎn),然后斷開2和3之間的連線,再把new節(jié)點(diǎn)插入進(jìn)去
如圖,我們把2節(jié)點(diǎn)的next指向了新插入的new節(jié)點(diǎn),把new的next指向了3的節(jié)點(diǎn),那2和3之間的連系就順利成章的斷掉了,那我們的插入就算完成了。
所以我們來(lái)看一下代碼
首先當(dāng)然是獲得我們需要插入位置的前一個(gè)節(jié)點(diǎn),即上圖的2節(jié)點(diǎn)
static SNode *get_prev_node(SLink link,size_t index){ //獲得前一個(gè)節(jié)點(diǎn) SNode *node = link;//從頭結(jié)點(diǎn)開始找,比如我們插入在鏈表首插入一個(gè)節(jié)點(diǎn)就是插入到頭結(jié)點(diǎn)后面 //我們?cè)阪湵砦膊迦胍粋€(gè)節(jié)點(diǎn)就是當(dāng)node->next為null的時(shí)候插入 size_t i; for(i=0;i<index && node != NULL;i++){ node = node->next; } return node; //這里的返回值可能為null,比如當(dāng)node為尾結(jié)點(diǎn)的時(shí)候,它的node->next就為null }
插入操作
int insert(SLink link,size_t index,void *pdata,size_t size){ if(pdata == NULL){ //如果沒(méi)有傳進(jìn)來(lái)數(shù)據(jù),那就插入失敗 return -1; } SNode *prev = get_prev_node(link,index); if(prev == NULL){ //獲得插入位置的前一個(gè)節(jié)點(diǎn),當(dāng)它為Null時(shí)也不能插入數(shù)據(jù), return -1; } SNode *node = create_node(pdata,size,prev->next); //調(diào)用生成節(jié)點(diǎn)的靜態(tài)方法生成一個(gè)節(jié)點(diǎn), //并且傳入pdata,size,如上圖所示,新插入的節(jié)點(diǎn)的next指向的是原本前一個(gè)節(jié)點(diǎn)prev的next prev->next = node; //把prev->next重新指向新插入的節(jié)點(diǎn),這樣插入就完成了 //完成了new節(jié)點(diǎn)旁邊兩條線的鏈接工作 //prev->next = create_node(pdata,size,prev->next); return 0; }
關(guān)于在鏈表首或者鏈表尾插入數(shù)據(jù)
這里其實(shí)很簡(jiǎn)單,就是新插入的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為頭結(jié)點(diǎn)或者尾結(jié)點(diǎn)的問(wèn)題,大家可以自己寫一下
獲得指定下標(biāo)的節(jié)點(diǎn)的元素
這個(gè)操作比較簡(jiǎn)單,只需要在滿足條件下把這個(gè)下標(biāo)遍歷完就可以了,沒(méi)有什么難點(diǎn)
void *get(SLink link,size_t index){ SNode *node = link->next; //這里我們不能從頭結(jié)點(diǎn)開始遍歷,因?yàn)轭^結(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)所以只能從首節(jié)點(diǎn)開始遍歷 size_t i; for(i=0;i<index && node != NULL;i++){ node = node->next; } if(node == NULL){ return NULL; } return node->pdata; //遍歷完成并且返回這個(gè)數(shù)據(jù)的地址即可 }
刪除一個(gè)節(jié)點(diǎn)
刪除可以說(shuō)是插入的反過(guò)來(lái)的操作
比如上圖,我們需要?jiǎng)h除3這個(gè)節(jié)點(diǎn),那我們?cè)撛趺崔k呢?其實(shí)比插入更簡(jiǎn)單,我們只需要讓2的next指向需要?jiǎng)h除節(jié)點(diǎn)的next(也就是3的next),并且把3節(jié)點(diǎn)給釋放掉,把里面的數(shù)據(jù)也釋放掉就OK了
首先我們也可以寫一個(gè)靜態(tài)方法來(lái)實(shí)現(xiàn)刪除某個(gè)節(jié)點(diǎn)
static void remove_node(SNode *prev){ //這里的prev為需要被刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) SNode *node = prev->next; //記錄被刪除的節(jié)點(diǎn) SNode *next = node->next; //記錄被刪除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) free(node->pdata); free(node); prev->next = next; }
然后刪除節(jié)點(diǎn)的操作
int remove_data(SLink link,size_t index){ SNode *prev = get_prev_node(link,index); //獲得被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) if(link == NULL || prev == NULL || prev->next == NULL){ //如果鏈表不存在或者被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)不存在或者被刪除的節(jié)點(diǎn)不存在,那就刪除失敗 return -1; } remove_node(prev); return 0; }
大家自己也可以寫一下刪除首節(jié)點(diǎn)或者尾結(jié)點(diǎn)
鏈表逆序
所謂鏈表逆序就是將鏈表的存儲(chǔ)順序反過(guò)來(lái),
比如上圖,它的逆序結(jié)果是什么呢?
我們來(lái)看一下,就是讓5節(jié)點(diǎn)的next指向4節(jié)點(diǎn),4指向3,3指向2,2指向1,1的next指向NULL,然后再把頭結(jié)點(diǎn)指向5,就完成了逆序,如下圖所示
那我們?cè)撛趺从么a實(shí)現(xiàn)呢?
SLink reverse(SLink link){ if(link==NULL || link->next == NULL || link->next->next == NULL){ //如果鏈表不存在或者只存在頭結(jié)點(diǎn)或者只存在一個(gè)節(jié)點(diǎn),那么我們就不需要進(jìn)行逆序操作 return link; } SNode *prev = link->next;//記錄第一個(gè)節(jié)點(diǎn) SNode *curr = link->next->next;//記錄第二個(gè)節(jié)點(diǎn) SNode *next; while(curr != NULL){ //只要當(dāng)前節(jié)點(diǎn)不為空就繼續(xù)執(zhí)行下去 next = curr->next; //記錄curr的下一個(gè)節(jié)點(diǎn) curr->next = prev; //讓指針?lè)催^(guò)來(lái)指向,即當(dāng)前節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn) prev = curr; //然后往后移 curr = next; } //最后還有兩條線沒(méi)有連上 //即以前的首節(jié)點(diǎn)(即上圖的節(jié)點(diǎn)1)的next應(yīng)該指向null,首節(jié)點(diǎn)再變?yōu)閜rev,即上圖的節(jié)點(diǎn)5 link->next->next = NULL; // link->next = prev; return link; }
鏈表的清空
清空鏈表只需要一個(gè)一個(gè)的遍歷,把節(jié)點(diǎn)里的數(shù)據(jù)釋放掉,再釋放掉該節(jié)點(diǎn)
void clear(SLink link){ SNode *node = link->next; //從首節(jié)點(diǎn)開始遍歷 while(node != NULL){ SNode *next = node->next; //記錄需要被釋放的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) free(node->pdata); free(node); node = next; } link->next = NULL; }
鏈表的銷毀
這個(gè)更為簡(jiǎn)單,只需要先清空里面的節(jié)點(diǎn),在把頭結(jié)點(diǎn)釋放掉即可
void destroy(SLink link){ clear(link); free(link); }
鏈表的遍歷
鏈表的遍歷也無(wú)需多說(shuō),我們只需要從首節(jié)點(diǎn)開始遍歷,并且把節(jié)點(diǎn)的數(shù)據(jù)傳給函數(shù)指針,這樣也更加靈活,一直遍歷到null為止
void foreach(SLink link,void (*func)(const void *)){ SNode *node = link->next; //從首節(jié)點(diǎn)開始遍歷 for(;node != NULL; node = node->next){ func(node->pdata); //把節(jié)點(diǎn)的數(shù)據(jù)傳給func這個(gè)函數(shù), //然后用戶需要對(duì)這個(gè)數(shù)據(jù)進(jìn)行什么樣的處理由用戶自己決定,不僅僅是局限于把這些數(shù)據(jù)給打印出來(lái) //這樣的好處是對(duì)數(shù)據(jù)的處理更加靈活了 } }
按特定的元素查找節(jié)點(diǎn)
我們也是從首節(jié)點(diǎn)開始遍歷,對(duì)首節(jié)點(diǎn)里的數(shù)據(jù)進(jìn)行比較,如果找到相同的數(shù)據(jù),那就返回這個(gè)數(shù)據(jù)的地址
void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)){ SNode *node = link->next; //從首節(jié)點(diǎn)開始查找 for(;node != NULL; node = node->next){ if(compare(node->pdata,pdata)==0){ //如果該節(jié)點(diǎn)的數(shù)據(jù)和帶查找的數(shù)據(jù)相等 return node->pdata; //那就返回這個(gè)數(shù)據(jù)的地址 } } return NULL; //如果沒(méi)有找到就返回null }
這里的compare也是函數(shù)指針,都是同樣的道理,對(duì)于需要找什么由用戶自己決定,不在局限于查找某個(gè)特定的元素
比如在一個(gè)學(xué)生信息的結(jié)構(gòu)體中,我們可以按學(xué)號(hào)進(jìn)行查找,也可以按姓名進(jìn)行查找,也可以按年齡、班級(jí)、等等進(jìn)行查找,讓這些使用起來(lái)更加靈活
比如我給大家寫一個(gè)查找的函數(shù),就按學(xué)生的學(xué)號(hào)進(jìn)行查找
int compare(const void* v1,const void* v2){ Stu *stu1 = (Stu *)v1; Stu *stu2 = (Stu *)v2; return v1->no-v2->no; }
按某些特定的條件刪除所有符合情況的節(jié)點(diǎn)
這個(gè)刪除的操作其實(shí)和上面的刪除特定下標(biāo)的節(jié)點(diǎn)的操作大同小異,都是找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn),然后進(jìn)行操作,這里找到后并不急于退出,而是繼續(xù)往下查找,直到找完整個(gè)鏈表并且刪除所有符合條件的節(jié)點(diǎn)
int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)){ SNode *prev = link; int cnt = 0; while(prev->next != NULL){ if(compare(prev->next->pdata,pdata)==0){ //找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) remove_node(prev); //刪除該節(jié)點(diǎn) cnt++; //刪除的個(gè)數(shù)++ }else{ prev = prev->next; //否則沒(méi)找到就是往下繼續(xù)查找 } } return cnt>0?0:-1; }
鏈表的排序
排序我這里選擇冒泡排序,如果大家想看更多的排序方法也可以看我以前寫的博客,我總共寫了12種排序方法
這里的排序和我以前寫的幾乎一模一樣,我就不再多說(shuō)了,唯一需要講解的還是函數(shù)指針的應(yīng)用,比如我們可以選擇對(duì)學(xué)生的學(xué)號(hào)進(jìn)行排序,也可以對(duì)學(xué)生的姓名、成績(jī)、身高、年齡等等都可以進(jìn)行升降序的排序
void sort(SLink link,int (*compare)(const void *,const void *)){ if(link->next == NULL || link->next->next == NULL){ return; } size_t i; SNode *tail = NULL; SNode *n = link->next; for(;n != NULL;n = n->next){ SNode *node; bool swap = false; for(node = link->next;node->next != tail;node = node->next){ SNode *prev = node; SNode *next = prev->next; if(compare(prev->pdata,next->pdata)>0){ //這里選擇的排序方式或者進(jìn)行排序的元素 swap(prev->pdata,next->pdata); swap = true; } } tail = node; if(!swap){ break; } } }
我再來(lái)寫一個(gè)對(duì)學(xué)生的姓名按照升序進(jìn)行排序的方法
int cmopare(const void *v1,const void* v2){ Stu *s1 = (Stu *)v1; Stu *s2 = (Stu *)v2; return strcmp(s1->name,s2->name); }
總結(jié)
一個(gè)鏈表的功能的實(shí)現(xiàn)就這樣完成了,實(shí)現(xiàn)的功能也比較齊全,由于存儲(chǔ)的數(shù)據(jù)可以是任意類型的數(shù)據(jù),可以是整型,也可以是浮點(diǎn)型,結(jié)構(gòu)體類型等等都可以存儲(chǔ),并且在實(shí)現(xiàn)的過(guò)程中也大量用到了函數(shù)指針,這樣讓這些操作的適用性更加廣泛,可以在許多項(xiàng)目中直接使用。
到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)鏈表的示例代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言 動(dòng)態(tài)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)簡(jiǎn)單的掃雷游戲(控制臺(tái)版)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單的掃雷游戲,控制臺(tái)版的掃雷游戲希望大家喜歡,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-05-05Qt學(xué)習(xí)教程之對(duì)話框消失動(dòng)畫效果
這篇文章主要給大家介紹了關(guān)于Qt學(xué)習(xí)教程之對(duì)話框消失動(dòng)畫效果的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-07-07C語(yǔ)言開發(fā)中的常見(jiàn)錯(cuò)誤詳解
這個(gè)分欄是對(duì)于使用C語(yǔ)言編程過(guò)程中可能會(huì)出現(xiàn)的一些錯(cuò)誤而進(jìn)行的說(shuō)明,更多的錯(cuò)誤示例將會(huì)在后面的內(nèi)容里進(jìn)行演示。希望這個(gè)分欄的內(nèi)容可以幫助剛學(xué)編程的小白少走一些彎路,以及吸取更多的編碼經(jīng)驗(yàn)2022-05-05詳細(xì)對(duì)比C語(yǔ)言中的chmod()函數(shù)和fchmod()函數(shù)
這篇文章主要介紹了C語(yǔ)言中的chmod()函數(shù)和fchmod()函數(shù)的詳細(xì)對(duì)比,兩個(gè)都是用于修改文件權(quán)限但是請(qǐng)注意實(shí)際使用上的差異,需要的朋友可以參考下2015-09-09Qt中QtWebEngine加載本地網(wǎng)頁(yè)跨域問(wèn)題的總結(jié)
本文主要介紹了Qt中QtWebEngine加載本地網(wǎng)頁(yè)跨域問(wèn)題的總結(jié),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04