今天將給大家講述鏈表的學(xué)習(xí)心得河咽。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)钠右，毋庸置疑鏈表必須學(xué)好，后面的棧忘蟹、隊列飒房、樹、圖都是以鏈表為基礎(chǔ)的媚值；鏈表的種類很多狠毯，有單鏈表、雙鏈表褥芒、循環(huán)鏈表嚼松、非循環(huán)鏈表；在此，我們以非循環(huán)單鏈表為例献酗，來講鏈表的創(chuàng)建祭刚、求長度扶镀、排序呻率、插入和排序陌知。
1.什么是鏈表
鏈表我的理解要包含以下特征：
（1）.由n個節(jié)點離散分配；
（2）.每個節(jié)點通過指針連接
（3）每一個節(jié)點由一個前驅(qū)節(jié)點和一個后驅(qū)節(jié)點
（4）.首節(jié)點沒有前驅(qū)節(jié)點颜及，尾節(jié)點沒有后驅(qū)節(jié)點甩苛；
滿足上面的4條，我們就稱為鏈表器予；鏈表既然由很多個節(jié)點浪藻，那節(jié)點又由什么組成？節(jié)點由兩個部分組成乾翔，一是數(shù)據(jù)域爱葵，用來存放有效數(shù)據(jù)；二是指針域反浓，用來指向下一個節(jié)點萌丈；下面用C語言來構(gòu)建鏈表數(shù)據(jù)結(jié)構(gòu)，首先應(yīng)該構(gòu)造出節(jié)點雷则，然后再把所有的節(jié)點連起來辆雾，就構(gòu)成了鏈表；
（1）節(jié)點的構(gòu)造
typedef struct Node
{
int data;//數(shù)據(jù)域月劈，用來存放數(shù)據(jù)域度迂；
struct Node *pNext;//定義一個結(jié)構(gòu)體指針，指向下一次個與當(dāng)前節(jié)點數(shù)據(jù)類型相同的節(jié)點
}NODE,*PNODE; //NODE等價于 struct Node; PNODE等價于struct Node *猜揪； 此處用大寫是為了與變量區(qū)分惭墓，可以讓人容易變出是個數(shù)據(jù)類型
typedef 只是給數(shù)據(jù)類型取個別名，即 typedef 數(shù)據(jù)類型 別名而姐；我們知道struct Node 是我們定義的數(shù)據(jù)類型腊凶；
（2）鏈表的創(chuàng)建
在創(chuàng)建鏈表之前，我們需要需要了解一下專業(yè)術(shù)語：
首節(jié)點：存放第一個有效數(shù)據(jù)的節(jié)點拴念；
尾節(jié)點：存放最后一個有效數(shù)據(jù)的節(jié)點钧萍；
頭節(jié)點：頭節(jié)點的數(shù)據(jù)類型與首節(jié)點的數(shù)據(jù)類型相同，并且頭節(jié)點是首節(jié)點前面的那個節(jié)點政鼠，并不存放有效數(shù)據(jù)风瘦；頭節(jié)點的存在只是為了方便鏈表的操作。
頭指針：指向頭節(jié)點的指針公般；
尾指針：指向尾節(jié)點的指針弛秋；
首先器躏，我們應(yīng)該創(chuàng)建一個頭節(jié)點，并用頭指針指向它蟹略，用C語言描述：用malloc向計算機申請一塊內(nèi)存，并定義一個指向與頭節(jié)點數(shù)據(jù)類型相同的指針（一定要判斷申請內(nèi)存是否成功）遏佣；
然后挖炬，要知道要創(chuàng)建鏈表的長度，用一個循環(huán)來每次創(chuàng)建一個節(jié)點状婶，并把每個節(jié)點連在一起意敛；
假如我們要在頭節(jié)點phead后面插入節(jié)點p：
（1）把頭節(jié)點的指針域指向P節(jié)點，即pHead->pNext=p;
（2）把p節(jié)點的指針域指向NULL膛虫，即p->pNext=NULL;
這樣就可以了嗎草姻？ 想想我們就可以發(fā)現(xiàn)，當(dāng)我們要插入多個節(jié)點時稍刀，頭節(jié)點始終指向最后添加的一個數(shù)據(jù)撩独，以前的節(jié)點通過頭指針此時已經(jīng)找不到了；我們定義一個尾指針pTail账月，始終用來指向鏈表的結(jié)尾综膀，每次只在pTail后面添加節(jié)點。
偽算法：
（1）定義一個尾指針pTail局齿，并初始化剧劝，使它指向頭節(jié)點，即pTail=pHead抓歼；
（2）在pTail后面添加節(jié)點讥此，修改指針：
pTail->pNext=p;
p->pNext=NULL;
pTail=p; //使pTail指向鏈表最后一個元素
PNODE Create_List(void)
{
int len; //存放鏈表的長度
int i; //循環(huán)變量
int val;//用來臨時存放用戶輸入的結(jié)點的值
PNODE List;
PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配一個頭節(jié)點
if(NULL==pHead)
{
printf("Memory allocation failure");
exit(-1);
}
else
{ PNODE pTail=pHead;
pHead->pNext=NULL;
printf("please input the length of list: "); //需要一個指針始終指向鏈表的結(jié)尾
scanf("%d",&len);
for(i=0;i
{
PNODE p=(PNODE)malloc(sizeof(NODE));
if(NULL==p)
{
printf("Memory allocation failure");
exit(-1);
}
else
{
printf("please input the value of list: ");
scanf("%d",&val);
p->data=val;
pTail->pNext=p;
p->pNext=NULL;
pTail=p;
}
}
}
return pHead;
}
小編給大家推薦一個學(xué)習(xí)氛圍超好的地方，C/C++交流企鵝裙：870963251谣妻！適合在校大學(xué)生萄喳，小白，想轉(zhuǎn)行拌禾，想通過這個找工作的加入取胎。裙里有大量學(xué)習(xí)資料，有大神解答交流問題湃窍，每晚都有免費的直播課程
2.向鏈表中插入元素
假如要在節(jié)點2的前面插入節(jié)點p闻蛀，我們首先要找到節(jié)點2的前驅(qū)節(jié)點1，假設(shè)現(xiàn)在q指針指向節(jié)點1您市，則
（1）p->pNext=q->pNext;
（2）q->pNext=p;
程序代碼如下：
//鏈表的第pos有效元素前面插入元素val觉痛，首先我們應(yīng)該找到第pos個元素前面一個元素的位置；
//當(dāng)鏈表有3個元素時茵休，pos=4薪棒，將不會進(jìn)行插入操作
bool Insert_List(PNODE pHead,int pos,int val)
{
int i=0;
PNODE p=pHead;
while((NULL!=p)&&(i
{
p=p->pNext;
i++;
}
if(p==NULL||i>pos-1) //把鏈表為空的情況考慮進(jìn)去了手蝎；i>pos-1 可以防止用戶輸入錯誤；
return false;
//程序執(zhí)行到這之后俐芯，i=pos-1棵介；p指針指向鏈表第pos個有效節(jié)點的前驅(qū)，即指向第pos-1節(jié)點吧史；
PNODE q=(PNODE)malloc(sizeof(NODE));
q->data=val;
q->pNext=p->pNext;
p->pNext=q;
}
3.刪除鏈表中的元素
假如要刪除節(jié)點2邮辽，只需要把節(jié)點1指針域指針指向節(jié)點3，但不要忘記釋放節(jié)點2所占的內(nèi)存贸营，否則將會造成內(nèi)存泄漏吨述；首先必須找到節(jié)點2的前驅(qū)節(jié)點1，假設(shè)p指向節(jié)點1钞脂。
（1）q=p->pNext; //首先用q保存要刪除節(jié)點的地址揣云；
（2）p->pNext=q->pNext; //q->pNext=p->pNext->pNext; 修改指針使節(jié)點1指向節(jié)點3；
（3）free(q); //釋放節(jié)點2所占的內(nèi)存冰啃；
bool Delete_List(PNODE pHead,int pos,int *val)
{
int i=0;
PNODE p=pHead;
while((NULL!=p)&&(i
{
p=p->pNext;
i++;
}
if(p==NULL||i>pos-1) //把鏈表為空的情況考慮進(jìn)去了邓夕；i>pos-1 可以防止用戶輸入錯誤；
return false;
//程序執(zhí)行到這之后亿笤，i=pos-1翎迁；
PNODE q=p->pNext; //q指向待刪除的節(jié)點；
*val=q->data;
p->pNext=q->pNext; //修改鏈表指針指向净薛；
free(q); //釋放q所指向節(jié)點的內(nèi)存汪榔；
q=NULL;//千萬不可以忘記，否則會出現(xiàn)野指針肃拜；
}
4.鏈表元素的排序
快速排序和冒泡排序的思想對于鏈表這個數(shù)據(jù)結(jié)構(gòu)同樣適用痴腌，下面是一個用選擇排序來實現(xiàn)鏈表的排序；
//鏈表有效元素的個數(shù)
int Length_List(PNODE pHead)
{ int len=0; //定義變量要記得初始化燃领；
PNODE p=pHead->pNext;
while(NULL!=p)
{
len++;
p=p->pNext;
}
return len;
}
//對鏈表中的元素進(jìn)行排序
void Sort_List(PNODE pHead)
{
int i,j;
int temp;
int len=Length_List(pHead);
PNODE p,q;//指向鏈表第一個有效元素
for(i=0,p=pHead->pNext;ipNext)
{
for(j=i+1,q=p->pNext;jpNext)
{
//交換數(shù)據(jù)
if(p->data>q->data)
{
temp=p->data;
p->data=q->data;
q->data=temp;
}
}
}
}
和數(shù)組排序很像士聪，只是這里需要兩個指針p、q不停地移動猛蔽，來獲取鏈表中的數(shù)據(jù)元素剥悟；
