Linux C 數(shù)據(jù)結(jié)構(gòu) ->單向鏈表

　之前看到一篇單向鏈表的博文债鸡，代碼也看著很舒服箩兽，于是乎記錄下來沃疮，留給自己~薇溃，循序漸進(jìn)菌赖，慢慢

　　延伸到真正的內(nèi)核鏈表~(敢問路在何方?路在腳下~)

　　1. 簡介

　　鏈表是Linux 內(nèi)核中最簡單，最普通的數(shù)據(jù)結(jié)構(gòu)痊焊。鏈表是一種存放和操作可變數(shù)量元素(常稱為節(jié)點)

　　的數(shù)據(jù)結(jié)構(gòu)，鏈表和靜態(tài)數(shù)組的不同之處在于忿峻，它所包含的元素都是動態(tài)創(chuàng)建并插入鏈表的薄啥，在編譯

　　時不必知道具體需要創(chuàng)建多少個元素，另外也因為鏈表中每個元素的創(chuàng)建時間各不相同逛尚，所以它們在

　　內(nèi)存中無須占用連續(xù)內(nèi)存區(qū)垄惧。正是因為元素不連續(xù)的存放，所以各個元素需要通過某種方式被鏈接在

　　一起绰寞，于是每個元素都包含一個指向下一個元素的指針到逊，當(dāng)有元素加入鏈表或從鏈表中刪除元素時，

　　簡單調(diào)整一下節(jié)點的指針就可以了滤钱。

　　根據(jù)它的特性觉壶，鏈表可分為：單鏈表，雙鏈表件缸，單向循環(huán)鏈表和雙向循環(huán)鏈表铜靶，今天總結(jié)記錄的就是

　　最簡單的單鏈表，

1.1 節(jié)點類型描述

　　1typedefstruct node_t {

　　2data_t data;/* 節(jié)點數(shù)據(jù)域 */3structnode_t *next;/* 節(jié)點的后繼指針域 */4}linknode_t, *linklist_t;

　　另一種寫法

1struct node_t {

　　2 data_t data;

　　3structnode_t *next;

　　4 }

　　5typedefstruct node_t linknode_t;

　　6typedefstructnode_t* linklist_t;

　　細(xì)看說明：

　　* linknode_t A;

　　* linklist_t p = &A;

　　* 結(jié)構(gòu)變量A為所描述的節(jié)點他炊，而指針變量p為指向此類型節(jié)點的指針(p值為節(jié)點的地址)

　　* 這樣看來 linknode_t 和 linklist_t 的作用是一樣的争剿，那么為什么我們要定義兩個數(shù)據(jù)類

　　* 型(同一種)呢? 答曰：主要為了代碼的可讀性已艰，我們要求標(biāo)識符要望文識義,便于理解

　　* linknode_t *pnode 指向一個節(jié)點

　　* linklist_t list 指向一個整體

　　1.2 頭節(jié)點 head (~黃河之水天上來~)

　　在順序存儲線性表，如何表達(dá)一個空表{ }蚕苇，是通過list->last = -1來表現(xiàn)的哩掺，所謂的空表就是

　　數(shù)據(jù)域為NULL，而鏈表有數(shù)據(jù)域和指針域涩笤，我們?nèi)绾伪憩F(xiàn)空鏈表呢?這時嚼吞，就引入了頭結(jié)點

　　的概念，頭結(jié)點和其他節(jié)點數(shù)據(jù)類型一樣辆它，只是數(shù)據(jù)域為NULL誊薄，head->next = NULL，下面

　　我們看一個創(chuàng)建空鏈表的函數(shù)锰茉，如何利用頭結(jié)點來創(chuàng)建一個空鏈表呢蔫，只要頭節(jié)點在，鏈表就還在~

1// 創(chuàng)建一個空鏈表2 linklist_t

　　3 CreateEmptyLinklist()

　　4 {

　　5 linklist_t list;

　　6list = (linklist_t)malloc(sizeof(linknode_t));

　　78if(NULL != list) {

　　9list->next = NULL;

　　10 }

　　1112return list;

　　13}

　　2. 鏈表基本運算的相關(guān)"算法"操作 or 操刀(~烹羊宰牛且為樂飒筑，會須一飲三百杯~)

　　鏈表的運算除了上面的創(chuàng)建空鏈表片吊，還有數(shù)據(jù)的插入，刪除协屡，查找等函數(shù)俏脊，鏈表的運算有各種實現(xiàn)方

　　法，如何寫出一個高效的肤晓，封裝性較好的函數(shù)是我們要考慮的爷贫，比如數(shù)據(jù)插入函數(shù)，我們就要盡可能

　　考慮所有能出現(xiàn)的結(jié)果补憾，比如：1)如果需插入數(shù)據(jù)的鏈表是個空表;2)所插入的位置超過了鏈表的

　　長度;如果我們的函數(shù)能包含所有能出現(xiàn)的情況漫萄，不僅能大大提高我們的開發(fā)效率，也會減少代碼的

　　錯誤率盈匾。下面看一個可用性較強的鏈表插入操作的函數(shù)實現(xiàn)~

int　　InsertLinklist(linklist_t list, int at, data_t x)

　　{

　　linknode_t * node_prev, * node_at, * node_new;

　　int pos_at;

　　intfound =0;

　　if(NULL == list)return-1;

　　/* at must >= 0 */if(at <0)return-1;

　　/*第一步腾务、新節(jié)點分配空間*/　　node_new = (linklist_t)malloc(sizeof(linknode_t));

　　if(NULL == node_new) {

　　return-1;

　　}

　　node_new->data = x;/* assigned value *//*　　*節(jié)點如果插入超過鏈表長度的位置，會接到尾節(jié)點后面削饵，

　　*這樣岩瘦，node_new成了尾節(jié)點，node_new->next = NULL

　　*/　　node_new->next = NULL;

　　/*第二步窿撬、定位*/　　node_prev = list;//跟隨指針启昧，幫助我們更好的定位　　node_at = list->next;//遍歷指針　　pos_at =0;

　　while(NULL != node_at) {

　　if(pos_at == at){

　　found =1;//找到正確的位置，跳出循環(huán)break;

　　}

　　/* move to the next pos_at */　　node_prev = node_at;//跟隨指針先跳到遍歷指針的位置　　node_at = node_at->next;//遍歷指針跳到下一個節(jié)點的位置　　pos_at++;

　　}

　　/*第三步劈伴、插入*/if(found) {

　　/* found = 1,找到正確的位置箫津，插入 */　　node_new->next = node_at;//插入的節(jié)點next指向node_at　　node_prev->next = node_new;//插入節(jié)點的前一個節(jié)點　　}

　　else {

　　/*若是沒找到正確的位置，即所插入位置超越了鏈表的長度，

　　*則接到尾節(jié)點的后面苏遥，同樣饼拍，這樣適用于{ }即空鏈表，這樣

　　*我們可以建立一個空鏈表田炭，利用這個函數(shù)师抄，實現(xiàn)鏈表的初始化

　　*/　　node_prev->next = node_new;

　　}

　　return0;

　　}

　　3. 正文開始 Demo(~與君歌一曲，請君為我傾耳聽~)

　　listlink.h

1 #ifndef _LIST_LINK_H_

　　2#define_LIST_LINK_H_34typedefint data_t;

　　56typedefstruct node_t {

　　7data_t data;/* 節(jié)點數(shù)據(jù)域 */8structnode_t * next;/* 節(jié)點的后繼指針域 */9}linknode_t, * linklist_t;

　　10111213/* 鏈表操作函數(shù)*/1415// 創(chuàng)建一個空鏈表16 linklist_t CreateEmptyLinklist();

　　1718// 銷毀鏈表19void DestroyLinklist(linklist_t list);

　　2021// 清空鏈表22void ClearLinklist(linklist_t list);

　　2324// 是否為空鏈表25int IsEmptyLinklist(linklist_t list);

　　2627// 鏈表長度28int LengthLinklist(linklist_t list);

　　2930// 獲去鏈表節(jié)點數(shù)據(jù)31intGetLinklist(linklist_t list,intat, data_t * x);

　　3233// 設(shè)置鏈表節(jié)點數(shù)據(jù)34intSetLinklist(linklist_t list,int at, data_t x);

　　3536// 插入節(jié)點37intInsertLinklist(linklist_t list,int at, data_t x);

　　3839// 刪除節(jié)點40intDeleteLinklist(linklist_t list,int at);

　　4142// 鏈表轉(zhuǎn)置43 linklist_t ReverseLinklist(linklist_t list);

　　4445// 打印鏈表46int Display(linklist_t list);

　　474849#endif// _LIST_LINK_H_

　　listlink.c

1 #include

　　2 #include

　　3#include"listlink.h"45// 創(chuàng)建一個空鏈表6 linklist_t

　　7 CreateEmptyLinklist()

　　8 {

　　9 linklist_t list;

　　10list = (linklist_t)malloc(sizeof(linknode_t));

　　1112if(NULL != list) {

　　13list->next = NULL;

　　14 }

　　1516return list;

　　17 }

　　1819// 銷毀鏈表20void21 DestroyLinklist(linklist_t list)

　　22 {

　　23if(NULL != list) {

　　24 ClearLinklist(list);

　　25free(list);

　　26 }

　　27 }

　　2829// 清空鏈表30void31 ClearLinklist(linklist_t list)

　　32 {

　　33linknode_t * node;/* pointer to the node to be remove */34if(NULL == list)return;

　　3536while(NULL != list->next) {

　　37node = list->next;

　　38list->next = node->next;//此時node->next是第二node節(jié)點元素依次往后39free(node);

　　40 }

　　41return;

　　42 }

　　4344// 是否為空鏈表45int46 IsEmptyLinklist(linklist_t list)

　　47 {

　　48if(NULL != list) {

　　49if(NULL == list->next)// 只有頭節(jié)點50return1;// 返回1,是個空鏈表51else52return0;// 返回0,鏈表非空5354}else55return-1;// 返回-1, 錯誤的類型56 }

　　5758// 鏈表長度59int60 LengthLinklist(linklist_t list)

　　61 {

　　62intlen =0;

　　63linknode_t * node;// 遍歷指針6465if(NULL == list)return-1;

　　6667node = list->next;// node指針指向第一個節(jié)點68while(NULL != node) {

　　69len++;

　　70node = node->next;

　　71 }

　　7273return len;

　　74 }

　　7576// 獲去一個鏈表指定節(jié)點數(shù)據(jù)域的數(shù)據(jù)值77int78GetLinklist(linklist_t list,intat, data_t * x)

　　79 {

　　80linknode_t *node;// 遍歷節(jié)點的指針81intpos;// 用于遍歷比較8283if(NULL == list)return-1;

　　84/*at 必須要 >= 0*/85if(at <0)return-1;

　　8687/* 從第一個元素開始 */88node = list->next;// node指針指向一個元素89pos =0;

　　90while(NULL != node) {

　　91if(at == pos) {

　　92if(NULL != x)

　　93*x = node->data;

　　94return0;

　　95 }

　　96// 下一個元素97node = node->next;

　　98pos++;

　　99 }

　　100return-1;

　　101 }

　　102103// 設(shè)置一個指定鏈表節(jié)點的數(shù)據(jù)域值104int105SetLinklist(linklist_t list,int at, data_t x)

　　106 {

　　107linknode_t * node;// 遍歷鏈表108int pos;

　　109intfound =0;

　　110111if(!list)return-1;

　　112/*at 必須 >= 0*/113if(at <0)return-1;

　　114115/* node指針指向第一個元素 */116node = list->next;

　　117pos =0;

　　118while(NULL != node) {

　　119if(at == pos) {

　　120found =1;// 找到了位置121node->data = x;

　　122break;

　　123 }

　　124/*往后移動元素*/125node = node->next;

　　126pos++;

　　127 }

　　128if(1== found)

　　129return0;

　　130else131return-1;

　　132 }

　　133134// 插入節(jié)點135int136InsertLinklist(linklist_t list,int at, data_t x)

　　137 {

　　138/*　　139 * node_at and pos_at are used to locate the position of node_at.

　　140 * node_prev follows the node_at and always points to previous node

　　141 * of node_at.

　　142 * node_new is used to point to the new node to be inserted.

　　143 */144linknode_t * node_prev, * node_at, * node_new;

　　145int pos_at;

　　146intfound =0;

　　147148if(NULL == list)return-1;

　　149150/* at 必須 >= 0 */151if(at <0)return-1;

　　152153node_new =malloc(sizeof(linknode_t));

　　154if(NULL == node_new)

　　155return-1;

　　156node_new->data = x;// assigned value157node_new->next = NULL;

　　158159node_prev = list;// head160node_at = list->next;//node_at指針指向第一元素161pos_at =0;

　　162while(NULL != node_at) {

　　163if(pos_at == at) {

　　164found =1;// found the node ‘a(chǎn)t'165break;

　　166 }

　　167/* move to the next pos_at */168node_prev = node_at;

　　169node_at = node_at->next;

　　170pos_at++;

　　171 }

　　172173if(found) {

　　174/* insert */175node_new->next = node_at;

　　176node_prev->next = node_new;

　　177}else{

　　178/*　　179 * If not found,means the provided 'at'

　　180 * exceeds the upper limit of the list, just

　　181 * append the new node to the end of the list

　　182 */183node_prev->next = node_new;

　　184 }

　　185186return0;

　　187 }

　　188189// 刪除節(jié)點190int191DeleteLinklist(linklist_t list,int at)

　　192 {

　　193/*　　194 * node_at and pos_at are used to locate the position of node_at.

　　195 * node_prev follows the node_at and always points to previous node

　　196 * of node_at.

　　197 */198linknode_t * node_prev, * node_at;

　　199int pos_at;

　　200intfound =0;

　　201202if(!list)return-1;

　　203if(at <0)return-1;

　　204205node_prev = list;// node_prev指針指向鏈表頭206node_at = list->next;// node_at指針指向第一元素207pos_at =0;

　　208209while(NULL != node_at) {

　　210if(pos_at == at) {

　　211// found the node 'at'212found =1;

　　213break;

　　214 }

　　215// move to the next pos_at216node_prev = node_at;

　　217node_at = node_at->next;

　　218pos_at++;

　　219 }

　　220if(found) {

　　221// remove222node_prev->next = node_at->next;

　　223free(node_at);

　　224return0;

　　225}else226return-1;

　　227 }

　　228229// 鏈表轉(zhuǎn)置230 linklist_t

　　231 ReverseLinklist(linklist_t list)

　　232 {

　　233linknode_t * node;// iterator234linknode_t * node_prev;// previous node of iterator235linknode_t * node_next;/* next node of iterator

　　236 * used to backup next of iterator

　　237 */238if(NULL == list)return NULL;

　　239node_prev = NULL;

　　240node = list->next;// node指針指向第一個元素241while(NULL != node) {

　　242/*　　243 * step1: backup node->next

　　244 * due to the next of iterator will be

　　245 * modified in step2

　　246 */247node_next = node->next;

　　248/*　　249 * when iterator reaches the last node

　　250 * of original list, make the list head

　　251 * point to the last node, so the original

　　252 * last one becomes the first one.

　　253 */254if(NULL == node_next)

　　255list->next = node;

　　256/*　　257 * step2: reverse the linkage between nodes

　　258 * make the node pointer to the previous node,

　　259 * not the next node

　　260 */261node->next = node_prev;

　　262/*　　263 * step3: move forward

　　264 */265node_prev = node;

　　266node = node_next;

　　267 }

　　268269return list;

　　270 }

　　271272// 打印鏈表273int274 Display(linklist_t list)

　　275 {

　　276linknode_t * node;

　　277278if(NULL == list)return-1;

　　279280node = list->next;

　　281while(node != NULL) {

　　282printf(" %d ", node->data);

　　283node = node->next;

　　284 }

　　285printf("\n");

　　286287return0;

　　288 }

　　289290291intmain(intargc,char* argv[])

　　292 {

　　293int i;

　　294 data_t x;

　　295 linklist_t p;

　　296297/*創(chuàng)建鏈表*/298p = CreateEmptyLinklist();

　　299 Display(p);

　　300data_t a[10] = {1,3,5,7,9,11,13,15,17,19};

　　301302for(i =0; i <10; i++) {

　　303/*插入鏈表*/304 InsertLinklist(p, i, a[i]);

　　305 }

　　306 Display(p);

　　307308/*鏈表轉(zhuǎn)置*/309 ReverseLinklist(p);

　　310/*鏈表長度*/311printf("The length of the list is [%d]\n", LengthLinklist(p));

　　312 Display(p);

　　313314/*獲取特定節(jié)點值*/315GetLinklist(p,4, &x);

　　316printf("The No.4 of this list is [%d]\n", x);

　　317318/*設(shè)置特定節(jié)點的值*/319SetLinklist(p,4,100);

　　320GetLinklist(p,4, &x);

　　321printf("After updating! The No.4 of this list is [%d]\n", x);

　　322 Display(p);

　　323324/*刪除節(jié)點*/325DeleteLinklist(p,5);

　　326printf("After delete!The length of list is [%d]\n", LengthLinklist(p));

　　327 Display(p);

　　328329/*清空鏈表*/330 ClearLinklist(p);

　　331if(IsEmptyLinklist(p))

　　332printf("This list is empty!\n");

　　333/*銷毀鏈表*/334 DestroyLinklist(p);

　　335printf("This list is destroyed!\n");

　　336337338return0;

　　339340}