今天將給大家講述鏈表的學(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，將不會進行插入操作
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) //把鏈表為空的情況考慮進去了；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) //把鏈表為空的情況考慮進去了；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;
}
//對鏈表中的元素進行排序
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ù)元素；
