鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語(yǔ)言中單鏈表的存儲(chǔ)，感興趣的可以學(xué)習(xí)一下

如果說(shuō)，順序表的所占用的內(nèi)存空間是連續(xù)的，那么鏈表則是隨機(jī)分配的不連續(xù)的，那么為了使隨機(jī)分散的內(nèi)存空間串聯(lián)在一起形成一種前后相連的關(guān)系，指針則起到了關(guān)鍵性作用。

單鏈表的基本結(jié)構(gòu)：

頭指針：永遠(yuǎn)指向鏈表第一個(gè)節(jié)點(diǎn)的位置。

頭結(jié)點(diǎn)：不存任何數(shù)據(jù)的空節(jié)點(diǎn)，通常作為鏈表的第一個(gè)節(jié)點(diǎn)。對(duì)于鏈表來(lái)說(shuō)，頭節(jié)點(diǎn)不是必須的，它的作用只是為了方便解決某些實(shí)際問(wèn)題。

首元結(jié)點(diǎn)：首個(gè)帶有元素的結(jié)點(diǎn)。

其他結(jié)點(diǎn)：鏈表中其他的節(jié)點(diǎn)。

1、定義一個(gè)鏈表結(jié)點(diǎn)

包括數(shù)據(jù)域和指針域

typedef struct Link{
    char elem;//數(shù)據(jù)域 
    struct Link *next;//指針域，用來(lái)連接后繼元素 
}link;//link為節(jié)點(diǎn)名，每個(gè)結(jié)點(diǎn)都是一個(gè)link結(jié)構(gòu)體

2、初始化單鏈表

（1）創(chuàng)建一個(gè)頭結(jié)點(diǎn)

（2）聲明一個(gè)臨時(shí)指針指向頭結(jié)點(diǎn)

（3）用循環(huán)創(chuàng)建新的結(jié)點(diǎn)并賦值且依次相連

newLink a；

a->data=i;

a->next=null;

temp->next=a;

temp=a;

過(guò)程如下：

帶頭結(jié)點(diǎn)：

link * initLink(){
    link *p=(link*)malloc(sizeof(link));//創(chuàng)建頭結(jié)點(diǎn)
    link*temp = p;//聲明一個(gè)指針temp指向頭結(jié)點(diǎn)，也就是頭結(jié)點(diǎn)的地址賦值給指針變量(注意這不是頭指針而是用來(lái)連接數(shù)組的臨時(shí)指針變量)
    //生成鏈表
    for(int i=1;i<5;i++)
    {
        link *a=(link*)malloc(sizeof(link));//生成一個(gè)結(jié)點(diǎn) 
        a->elem=i;//給結(jié)點(diǎn)的數(shù)據(jù)域賦值
        a->next=NULL;//指針域設(shè)置為空 
        temp->next=a;//上一個(gè)結(jié)點(diǎn)的指針指向新增結(jié)點(diǎn) 
        temp=temp->next;//臨時(shí)指針向后移動(dòng)也可寫(xiě)成temp=a 
    } 
    //返回頭結(jié)點(diǎn)，通過(guò)頭節(jié)點(diǎn)的指針即可找到整個(gè)鏈表
    return p;
}

無(wú)頭結(jié)點(diǎn)的單鏈表初始化：

 link * initLink2(){
    link *p=NULL;//創(chuàng)建頭指針
    link*temp=(link*)malloc(sizeof(link));//創(chuàng)建首元結(jié)點(diǎn)
    //首元結(jié)點(diǎn)初始化
    temp->elem=1;
    temp->next=NULL;
    p=temp;//頭結(jié)點(diǎn)指向首元結(jié)點(diǎn)
    //接下來(lái)從第二個(gè)結(jié)點(diǎn)開(kāi)始創(chuàng)建
    for(int i=2;i<5;i++){
        //創(chuàng)建一個(gè)新結(jié)點(diǎn)并初始化
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        //將temp結(jié)點(diǎn)與新建的a結(jié)點(diǎn)建立邏輯關(guān)系
        temp->next=a;
        temp=a;    
    }
    //返回建立的節(jié)點(diǎn)，只返回頭指針 p即可，通過(guò)頭指針即可找到整個(gè)鏈表
    return p; 
}

3、輸出鏈表數(shù)據(jù)

帶頭結(jié)點(diǎn)：

void display(link *p){
    link*temp=p;//將temp指向頭結(jié)點(diǎn)
    //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語(yǔ)句。
    while(temp->next){
        temp=temp->next;
        printf("%d ",temp->elem);
    } 
    printf("\n");
}

不帶頭結(jié)點(diǎn)：

void display2(link *p){
    link* temp=p;//將temp指針重新指向頭結(jié)點(diǎn)
    //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語(yǔ)句。
    while (temp) {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}

4、完整代碼

#include<stdio.h>
#include<stdlib.h>
 
typedef struct Link{
    int elem;//數(shù)據(jù)域 
    struct Link *next;//指針域，用來(lái)連接后繼元素 
}link;//link為節(jié)點(diǎn)名，每個(gè)結(jié)點(diǎn)都是一個(gè)link結(jié)構(gòu)體 
 
//帶頭結(jié)點(diǎn) 
link * initLink(){
    link *p=(link*)malloc(sizeof(link));//創(chuàng)建頭結(jié)點(diǎn)
    link*temp = p;//聲明一個(gè)指針temp指向頭結(jié)點(diǎn)，也就是頭結(jié)點(diǎn)的地址賦值給指針變量(注意這不是頭指針而是用來(lái)連接數(shù)組的臨時(shí)指針變量)
    //生成鏈表
    for(int i=1;i<5;i++)
    {
        link *a=(link*)malloc(sizeof(link));//生成一個(gè)結(jié)點(diǎn) 
        a->elem=i;//給結(jié)點(diǎn)的數(shù)據(jù)域賦值
        a->next=NULL;//指針域設(shè)置為空 
        temp->next=a;//上一個(gè)結(jié)點(diǎn)的指針指向新增結(jié)點(diǎn) 
        temp=temp->next;//臨時(shí)指針向后移動(dòng)也可寫(xiě)成temp=a 
    } 
    //返回頭結(jié)點(diǎn)，通過(guò)頭節(jié)點(diǎn)的指針即可找到整個(gè)鏈表
    return p;
} 
 
//不帶頭結(jié)點(diǎn) 
link * initLink2(){
    link *p=NULL;//創(chuàng)建頭指針
    link*temp=(link*)malloc(sizeof(link));//創(chuàng)建首元結(jié)點(diǎn)
    //首元結(jié)點(diǎn)初始化
    temp->elem=1;
    temp->next=NULL;
    p=temp;//頭結(jié)點(diǎn)指向首元結(jié)點(diǎn)
    //接下來(lái)從第二個(gè)結(jié)點(diǎn)開(kāi)始創(chuàng)建
    for(int i=2;i<5;i++){
        //創(chuàng)建一個(gè)新結(jié)點(diǎn)并初始化
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        //將temp結(jié)點(diǎn)與新建的a結(jié)點(diǎn)建立邏輯關(guān)系
        temp->next=a;
        temp=a;    
    }
    //返回建立的節(jié)點(diǎn)，只返回頭指針 p即可，通過(guò)頭指針即可找到整個(gè)鏈表
    return p; 
}
 
//帶頭結(jié)點(diǎn) 
void display(link *p){
    link*temp=p;//將temp指向頭結(jié)點(diǎn)
    //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語(yǔ)句。
    while(temp->next){
        temp=temp->next;
        printf("%d ",temp->elem);
    } 
    printf("\n");
} 
 
//不帶頭結(jié)點(diǎn) 
void display2(link *p){
    link* temp=p;//將temp指針重新指向頭結(jié)點(diǎn)
    //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語(yǔ)句。
    while (temp) {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}
 
int main()
{
    display(initLink());
    return 0;
}

輸出結(jié)果：