c語(yǔ)言鏈表的用法

本文格式為Word版，下載可任意編輯——c語(yǔ)言鏈表的用法c語(yǔ)言鏈表的用法

鏈表是數(shù)據(jù)布局中對(duì)比根基也是對(duì)比重要的類型之一，那么有了數(shù)組，為什么我們還需要鏈表呢！或者說(shuō)設(shè)計(jì)鏈表這種數(shù)據(jù)布局的初衷在哪里？下面我就為大家介紹下c語(yǔ)言鏈表的用法。

c語(yǔ)言枚舉的用法如下：

這是由于，在我們使用數(shù)組的時(shí)候，需要預(yù)先設(shè)定目標(biāo)群體的個(gè)數(shù)，也即數(shù)組容量的大小，然而實(shí)時(shí)處境下我們目標(biāo)的個(gè)數(shù)我們是不確定的，因此我們總是要把數(shù)組的容量設(shè)置的很大，這樣以來(lái)就濫用了好多的空間。另外，數(shù)組在舉行插入操作和刪除操作的時(shí)候，在插入或者刪除制定元素之后，我們往往需要舉行循環(huán)移位，這增加了我們的線性開銷。

正是由于以上的兩種主要理由，鏈表被設(shè)計(jì)出來(lái)用于一般表的操作。為了制止上面描述數(shù)組的兩種弊端，我們夢(mèng)想鏈表有一下的特點(diǎn)

1可以生動(dòng)的擴(kuò)展自己的長(zhǎng)度。

2存儲(chǔ)地址不連續(xù)，刪除或者插入操作的時(shí)候不需要循環(huán)移位。

要實(shí)現(xiàn)以上兩個(gè)特點(diǎn)，我們需既要保證每個(gè)節(jié)點(diǎn)的獨(dú)立性，又要保存相鄰兩個(gè)節(jié)點(diǎn)的聯(lián)系。

為此，鏈表一般被設(shè)計(jì)為下面的形式。

NodeNodeNode

鏈表是由一個(gè)一個(gè)的節(jié)點(diǎn)組成的，可以便當(dāng)和自由的插入未知個(gè)Node，前一個(gè)節(jié)點(diǎn)中用指針保存著下一個(gè)節(jié)點(diǎn)的位置，這樣以來(lái)便順?biāo)斓耐瓿闪宋覀儗?duì)鏈表的兩點(diǎn)期望，但是唯一的缺點(diǎn)是增加了額外的空間消耗。

————————————————————————————————————————————————————————————————————————————

鏈表的定義：

鏈表的定義一般使用布局體，在看《數(shù)據(jù)布局與算法分析》這本書的時(shí)候察覺(jué)，書中頻繁的使用typedef的關(guān)鍵字，結(jié)果真的很棒不僅保持的代碼的感激程度，也讓我們?cè)谙旅娴木幋a過(guò)程中少見了好多煩人的指針（當(dāng)然指針還是一向存在的）。所以這里也借用了書中的定義方法。

structNode;

typedefstructNode*PtrNode;

typedefPtrNodePosition;

typedefPtrNodeList;

structNode

intValue;

PtrNodeNext;

;

下面接著書寫一個(gè)建立鏈表的函數(shù)，輸入每個(gè)節(jié)點(diǎn)的值，直到這個(gè)值是-1的時(shí)候函數(shù)終止。

在這個(gè)里面，我以前一向搞不明白為什么需要定義三個(gè)Node*，現(xiàn)在終究了解了，最終還是復(fù)習(xí)了指針的內(nèi)容明白的，這里說(shuō)一下指針實(shí)現(xiàn)鏈表對(duì)指針的操作很頻繁，需要對(duì)比扎實(shí)的掌管了指針之后，在來(lái)看鏈表會(huì)輕松好多。在下面的一段程序里，我分別定義了head/p/tmp這三個(gè)指向節(jié)點(diǎn)布局體的指針，head的主要作用就像一個(gè)傳銷頭目，他會(huì)主動(dòng)聯(lián)系上一個(gè)下線p，然后他就什么也不干了，p接著去進(jìn)展一個(gè)又一個(gè)的下線tmp，結(jié)果一串以head為首的鏈表就出來(lái)了。

起先，我總覺(jué)得有了head，為什么還要p，這是由于假設(shè)直接使用head去指向下一個(gè)節(jié)點(diǎn)，head的.位置也是不斷在移動(dòng)的，即它永遠(yuǎn)處于鏈表的尾端，這樣當(dāng)我們返回鏈表的時(shí)候，其實(shí)是空值。所以，我們需要p這個(gè)中轉(zhuǎn)環(huán)節(jié)。（其實(shí)，這種做法在指針中分外普遍，大片面有返回指針類型的函數(shù)中，都會(huì)首先定義一個(gè)指針變量來(lái)保存函數(shù)的傳入的參數(shù)，而不是對(duì)參數(shù)直接舉行操作）。

?

/*

函數(shù)功能：創(chuàng)造一個(gè)鏈表

函數(shù)描述：每次輸入一個(gè)新的整數(shù)，即把新增加一個(gè)節(jié)點(diǎn)存放該整數(shù)，

當(dāng)輸入的整數(shù)為-1時(shí)，函數(shù)終止。

*/

Listcreate

intn=0;

Positionp,head,tmp;

head=NULL;

tmp=mallocsizeofstructNode;

iftmp==NULL

printftmpmallocfailed!;

returnNULL;

else

p=tmp;

printfpleaseinputthefirstnodesmessage!;

scanf%d,tmp-Value;

whiletmp-Value!=-1

n+=1;

ifn==1

head=p;

tmp-Next=NULL;

else

p-Next=tmp;

p=tmp;

tmp=mallocsizeofstructNode;

printfpleaseinputthe%dnode!,n+1;

scanf%d,tmp-Value;

p-Next=NULL;

freetmp;//free函數(shù)free掉的只是申請(qǐng)的空間，但是指針還是照舊存在的。

tmp=NULL;

returnhead;

接下來(lái)，在寫一個(gè)刪除鏈表節(jié)點(diǎn)的函數(shù)，輸入一個(gè)整數(shù)然后遍歷鏈表節(jié)點(diǎn)，當(dāng)鏈表節(jié)點(diǎn)的值與該整數(shù)相等的時(shí)候，即把該節(jié)點(diǎn)刪除。

在完成這個(gè)函數(shù)首先確定要把這個(gè)過(guò)程斟酌領(lǐng)會(huì)，不成否認(rèn)我之前是一個(gè)上來(lái)就敲代碼的人，看了《劍指offer》感覺(jué)這種習(xí)慣是程序員的大忌，甚至還想寫一篇博客，名字都想好了《程序員的自我修養(yǎng)之斟酌在前，代碼在后》。其實(shí)想想也是，我們寫程序的目的是為了解決問(wèn)題，而不是為了簡(jiǎn)樸的寫程序，純粹的讓程序跑起來(lái)約莫只會(huì)在上學(xué)那會(huì)存在吧！真實(shí)的程序開發(fā)中需要考慮幾乎全體能想到的實(shí)際問(wèn)題，所以無(wú)論程序再下，一要學(xué)會(huì)先斟酌領(lǐng)會(huì)，再下筆寫程序。

關(guān)于這個(gè)函數(shù),我們要想到的是：

1假設(shè)鏈表為空，我們?cè)撛趺醋?，?dāng)然是直接返回。

2假設(shè)要?jiǎng)h除的元素為頭節(jié)點(diǎn)該怎么辦？

3假設(shè)要?jiǎng)h除的元素為尾節(jié)點(diǎn)該怎么辦？

當(dāng)留神到以上三個(gè)片面，我們的程序就可能制止掉了輸入鏈表為空，程序直接崩潰的現(xiàn)象，也可以制止刪除元素值為頭節(jié)點(diǎn)時(shí)刪不掉的難堪。我們的程序就有了確定的魯棒性。

下面著重考慮鏈表的刪除的實(shí)現(xiàn)：

list：????Node_a-Node_b-Node_c-Node_d;

??????????????list??????tmp????????p

?

???????????tmp-Next=p-Next;

?

?

list:??????Node_a-Node_bNode_d

?????????????????????????????????????freep

假設(shè)我們要?jiǎng)h除的節(jié)點(diǎn)為上圖的Node_c;假設(shè)我們能夠找到Node_c的前一個(gè)位置tmp和被刪除節(jié)點(diǎn)位置p的話;這個(gè)時(shí)候我們只需要執(zhí)行tmp-Next=p-Next即可。

只要完成上面的分析以及考慮到各種處境，我們完成下面的代碼就水到渠成了。

/*

函數(shù)功能：刪除鏈表中指定值的節(jié)點(diǎn)（假設(shè)存在多個(gè)，只刪除第一個(gè)）

本例中輸入一個(gè)整數(shù)，刪除鏈表節(jié)點(diǎn)值為這個(gè)整數(shù)的節(jié)點(diǎn)。

*/

ListDeleteNodeListlist

Positionp,tmp;

intvalue;

iflist==NULL

printfThelistisnull,functionreturn!;

returnNULL;

else

printfpleaseinputtheNodesvalue:;

scanf%d,value;

p=list;

ifp-Value==value

list=p-Next;

freep;

p=NULL;

returnlist;

whilep!=NULLp-Value!=value

tmp=p;

p=p-Next;

ifp-Value==value

ifp-Next!=NULL

tmp-Next=p-Next;

else

tmp-Next=NULL;

freep;

p=NULL;

returnlist;

?關(guān)于鏈表的使用場(chǎng)景分析:

鏈表在程序開發(fā)中用到的頻率還是分外高的，所以在高級(jí)語(yǔ)言中往往會(huì)對(duì)鏈表舉行一些實(shí)現(xiàn)，譬如STL中l(wèi)ist以及Java中也有類似的東西。在目前的服務(wù)器端開發(fā)，主要運(yùn)用鏈表來(lái)接收一些從數(shù)據(jù)中取出來(lái)的數(shù)據(jù)舉行處理。

即使你不知道鏈表的底層實(shí)現(xiàn)，依舊可以告成的運(yùn)用STL里面的現(xiàn)成的東西。但是作為一個(gè)學(xué)習(xí)者，我覺(jué)得會(huì)使用和從底層掌管依舊是兩個(gè)不同的概念，linux之父說(shuō)：“talkisless，showyoucode”。

以下的程序，用鏈表模擬了一個(gè)電話通訊錄的功能，包括添加聯(lián)系人，查找聯(lián)系人，以及刪除聯(lián)系人。

PS：關(guān)于魯棒性，程序中最大的危害是使用了gets這個(gè)函數(shù)，目前先留存使用gets，等待找到工作之后在做進(jìn)一步的程序完善。（尼瑪，讀書去。。。應(yīng)屆生，找個(gè)工作***咋這么難呢！??工作閱歷，工作閱歷，艸，那個(gè)大牛一出校門就什么都會(huì)。）

?

/**************************************************************************

Programe:

Thisisaphonelistwritebylist

Theprogrameisjustprictiseforlist

Author:heatnan

Mail:964465194@.com

Data:2022/07/27

**************************************************************************/

#include

#include

#include

#defineN25

#defineM15

structnode;

typedefstructnode*p_node;

typedefp_nodeList;

typedefp_nodePosition;

typedefstructnode**PList;

structnode

charname[N];

charnumber[M];

Positionnext;

;

intJudgeNameExistListlist,char*name;

voidAddPersonPListlist;

voidPrintListListlist;

ListFindPersonListlist;

ListFindPersonByNameListlist,char*name;

intAddPersonByNamePListlist,Listnode;

intDeletePersonByNamePListlist,char*name;

voidDeletePersonPListlist;

intmain

Listlist=NULL;

Positionp;

charcmd[100];

while1

printfMAIN;

printf*******1addaperson*******;

printf*******2showthephonelist*******;

printf*******3findfromphonelist*******;

printf*******4fromphonelist*******;

printfPleaseinputthecmdnumber:;

getscmd;

switchcmd[0]

case1:

AddPersonlist;

break;

case2:

PrintListlist;

break;

case3:

FindPersonlist;

break;

case4:

DeletePersonlist;

break;

default:

printfwrongcmd!;

break;

return0;

/*

Function:判斷要添加的聯(lián)系人名稱是否已經(jīng)存在于電話簿中.

Input:List電話列表,name要添加的聯(lián)系人的姓名.

Return:已經(jīng)存在返回1,不存在返回0.

*/

intJudgeNameExistListlist,char*name

ifFindPersonByNamelist,name!=NULL

return1;

else

return0;

/*

Function:根據(jù)輸入的姓名查找聯(lián)系人的信息節(jié)點(diǎn)

Input:要輸入的電話列表list,姓名name

Return:返回查找到的節(jié)點(diǎn)

*/

ListFindPersonByNameListlist,char*name

whilelist!=NULL

ifstrcmplist-name,name==0

break;

list=list-next;

returnlist;

/*

Function:根據(jù)姓名添加新的聯(lián)系人到聯(lián)系人列表

Input:指向聯(lián)系人列表地址的指針，新用戶節(jié)點(diǎn)

Return:添加告成返回1，添加失敗返回0

*/

intAddPersonByNamePListlist,Listnode

ifnode==NULL

printfthenodeisNULL!;

return0;

if*list==NULL

*list=node;

return1;

ListpHead=*list;

whilepHead-next!=NULL

pHead=pHead-next;

pHead-next=node;

return1;

voidAddPersonPListlist

Positiontmp;

Positionp_head;

tmp=structnode*mallocsizeofstructnode;

charname[N];

charnumber[M];

iftmp==NULL

printfmallocthetmpnodefailedinfunctionaddperson!;

else

printfpleaseinputthename:;

getsname;

printfpleaseinputthenumber:;

getsnumber;

strcpytmp-name,name;

strcpytmp-number,number;

tmp-next=NULL;

ifJudgeNameExist*list,name==1

freetmp;

printfthenamehavealreadyexist!;

return;

AddPersonByNamelist,tmp;

/*

Function:打印聯(lián)系人列表

Input：聯(lián)系人列表

*/

voidPrintListListlist

Positionshow;

show=list;

ifshow==NULL

return;

printfNow,weprintthephonelist:;

whileshow!=NULL

printfName:%sNumber:%s,show-name,show-number;

show=show-next;

ListFindPersonListlist

charname[N];

PositionpHead=list;

printfpleaseinputthenameyouwillfind:;

getsname;

Positionnode=FindPersonByNamelist,name;

ifnode!=NULL

printffindsuccess!name-%snumber-