1. 單鏈表概念&設(shè)計(jì)

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，，鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。以“結(jié)點(diǎn)的序列”表示的線性表稱作線性鏈表（單鏈表），單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)。

對(duì)于鏈表的每一個(gè)結(jié)點(diǎn)，我們使用結(jié)構(gòu)體（struct）進(jìn)行設(shè)計(jì)，其主要內(nèi)容有：

其中，DATA數(shù)據(jù)元素，可以為你想要儲(chǔ)存的任何數(shù)據(jù)格式，可以是數(shù)組，可以是int，甚至可以是結(jié)構(gòu)體（這就是傳說中的結(jié)構(gòu)體套結(jié)構(gòu)體）

NEXT為一個(gè)指針，其代表了一個(gè)可以指向的區(qū)域，通常是用來指向下一個(gè)結(jié)點(diǎn)，鏈表的尾部NEXT指向NULL（空），因?yàn)槲膊繘]有任何可以指向的空間了

故，對(duì)于一個(gè)單鏈表的結(jié)點(diǎn)定義，可以代碼描述成：

//定義結(jié)點(diǎn)類型
typedef struct Node {
    int data;       //數(shù)據(jù)類型，你可以把int型的data換成任意數(shù)據(jù)類型，包括結(jié)構(gòu)體struct等復(fù)合類型
    struct Node *next;          //單鏈表的指針域
} Node,*LinkedList;  
//Node表示結(jié)點(diǎn)的類型，LinkedList表示指向Node結(jié)點(diǎn)類型的指針類型

2. 單鏈表的初始化

同任何的結(jié)構(gòu)，類型一樣，鏈表也需要初始化操作，初始化是創(chuàng)建一個(gè)單鏈表的前置節(jié)點(diǎn)并向后逐步添加節(jié)點(diǎn)，一般來說，我們所謂的初始化單鏈表一般指的是申請(qǐng)結(jié)點(diǎn)的空間，同時(shí)對(duì)一個(gè)結(jié)點(diǎn)輔以空值(NULL)，其代碼可以表示為：

LinkedList listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //開辟空間 
    if(L==NULL){                     //判斷是否開辟空間失敗，這一步很有必要
        printf("申請(qǐng)空間失敗");
        //exit(0);                  //開辟空間失敗可以考慮直接結(jié)束程序
    }
    L->next=NULL;       //指針指向空
}

在這里我們有一個(gè)注意點(diǎn)，就是一定要記住判斷是否開辟空間失敗，雖然在很多試題中以及常用的環(huán)境提供的環(huán)境非常安全，幾乎沒有開辟失敗的存在，但是也一定要養(yǎng)成判斷是否開辟失敗并且判斷失敗后執(zhí)行代碼，但在生產(chǎn)中由于未知的情況造成一旦空間開辟失敗任然在繼續(xù)執(zhí)行代碼，后果將不堪設(shè)想，因此養(yǎng)成這樣的判斷是很有必要的，在C++中可以使用try-catch這樣的語(yǔ)句進(jìn)行優(yōu)化。

3. 創(chuàng)建單鏈表（頭插入法）

在初始化之后，就可以著手開始創(chuàng)建單鏈表了，單鏈表的創(chuàng)建分為頭插入法和尾插入法兩種，兩者并無本質(zhì)上的不同，都是利用指針指向下一個(gè)結(jié)點(diǎn)元素的方式進(jìn)行逐個(gè)創(chuàng)建，只不過使用頭插入法最終得到的結(jié)果是逆序的。

如圖，為頭插法的創(chuàng)建過程：

該方法從一個(gè)空表開始，生成新結(jié)點(diǎn)，并將讀取到的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭，即頭結(jié)點(diǎn)之后。

//單鏈表的建立1，頭插法建立單鏈表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申請(qǐng)頭結(jié)點(diǎn)空間
    L->next = NULL;                      //初始化一個(gè)空鏈表
 
    int x;                         //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申請(qǐng)新的結(jié)點(diǎn)
        p->data = x;                     //結(jié)點(diǎn)數(shù)據(jù)域賦值
        p->next = L->next;     //將結(jié)點(diǎn)插入到表頭L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;

4. 創(chuàng)建單鏈表（尾插入法）

如圖，為尾插入法的創(chuàng)建過程。

頭插法建立單鏈表的算法雖然簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致。若希望兩者次序一致，可采用尾插法。

該方法是將新結(jié)點(diǎn)逐個(gè)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針 r, 使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)，否則就無法正確的表達(dá)鏈表。

//單鏈表的建立2，尾插法建立單鏈表
 
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申請(qǐng)頭結(jié)點(diǎn)空間
    L->next = NULL;                  //初始化一個(gè)空鏈表
    Node *r;
    r = L;                          //r始終指向終端結(jié)點(diǎn)，開始時(shí)指向頭結(jié)點(diǎn)
    int x;                         //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申請(qǐng)新的結(jié)點(diǎn)
        p->data = x;                     //結(jié)點(diǎn)數(shù)據(jù)域賦值
        r->next = p;            //將結(jié)點(diǎn)插入到表頭L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}

(待續(xù))