1.單鏈表

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)。鏈表中的數(shù)據(jù)是以節(jié)點(diǎn)來表示的，每個(gè)節(jié)點(diǎn)由元素和指針構(gòu)成，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個(gè)元素的地址數(shù)據(jù)。在單鏈表中指針只指向他的后繼節(jié)點(diǎn)。

2.單鏈表的實(shí)現(xiàn)

2.1 定義一些輔助元素

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存儲空間初始分配量 */

typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

2.2 設(shè)計(jì)單鏈表的節(jié)點(diǎn)

節(jié)點(diǎn).png

實(shí)現(xiàn)代碼：

//定義結(jié)點(diǎn)
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

2.3 設(shè)計(jì)一個(gè)單鏈表

單鏈表.png

帶頭結(jié)點(diǎn)的單鏈表

一個(gè)單鏈表的基本結(jié)構(gòu)可以由上圖所示。在設(shè)計(jì)單鏈表的時(shí)候我們可以給單鏈表初始化一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)不存儲數(shù)據(jù)，可以存儲一些輔助信息，例如鏈表的長度。頭結(jié)點(diǎn)的指針域可以指向首元節(jié)點(diǎn)，在后續(xù)的鏈表增刪的時(shí)候會很方便，不用修改首指針?biāo)赶虻牡刂贰１阌诳毡砗头强毡淼奶幚怼?/p>

初始化單鏈表的代碼實(shí)現(xiàn)：

/// 初始化一個(gè)帶頭結(jié)點(diǎn)的單鏈表
/// @param L 單鏈表
Status InitLinkList(LinkList *L){
    // 分配內(nèi)存
    *L = (LinkList)malloc(sizeof(Node));
    // 分配失敗，報(bào)錯
    if (*L==NULL) { return ERROR; }
    // 頭結(jié)點(diǎn)指針置空
    (*L)->next = NULL;
    
    return OK;
}

2.4 遍歷打印單鏈表

代碼實(shí)現(xiàn)：

void PrintLinkList(LinkList L){
    LinkList p = L->next;
    // 判斷一下首元節(jié)點(diǎn)是否有值，有值在遍歷打印
    if (p == NULL) { return; }
    while (p) {
        printf("該節(jié)點(diǎn)的值是：%d\n",p->data);
        p = p->next;
    }
}

2.5 指定位置插入新節(jié)點(diǎn)

由于我們引入了頭結(jié)點(diǎn)的概念，所以插入變的相對簡單，不用在插入第一個(gè)位置的時(shí)候修改鏈表起始位置的指針。

插入新節(jié)點(diǎn).png

核心算法：

• 1.找到要插入位置的前一個(gè)節(jié)點(diǎn)
• 2.將新節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)的next
• 3.將前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)

實(shí)現(xiàn)代碼：

/// 在指定位置插入新節(jié)點(diǎn)
/// @param L 單鏈表
/// @param location 位置
/// @param e 新節(jié)點(diǎn)的數(shù)據(jù)
Status InsertLinkList(LinkList *L, int location, ElemType e){
    //取出頭節(jié)點(diǎn)的指針
    LinkList p = *L;
    // 記錄位置的中間變量
    int j = 1;
    // 如果指針一直有值就可以繼續(xù)尋找，直到找到要插入的位置的前一個(gè)節(jié)點(diǎn)
    while (p && j<location) {
        p = p->next;
        j++;
    }
    // p為NULL或者位置的值大于要插入的位置則直接報(bào)錯
    if (!p || j>location) { return ERROR; }
    // 創(chuàng)建要插入的節(jié)點(diǎn)
    LinkList new = (LinkList)malloc(sizeof(Node));
    new->data = e;
    new->next = p->next;
    // 前一個(gè)位置的next指向新的
    p->next = new;
    
    return OK;
}

2.6 根據(jù)指定位置獲取元素

這個(gè)查找沒什么難的，由于我們引入了頭結(jié)點(diǎn)，遍歷可以從1開始，找到要找的位置返回該節(jié)點(diǎn)的值即可。相關(guān)容錯處理在代碼中可見。
實(shí)現(xiàn)代碼：

/// 根據(jù)指定位置獲取元素
/// @param L 鏈表
/// @param location 位置
/// @param e 取到的值
Status GetElemFromList(LinkList L, int location, ElemType *e) {
    
    // 初始化一些臨時(shí)變量
    LinkList p = L->next;
    int j = 1;
    // 查找要取值得位置
    while (p && j<location) {
        p = p->next;
        j++;
    }
    // 沒取到或者位置不合法就報(bào)錯
    if (!p || j>location) { return ERROR; }
    // 返回取到的值
    *e = p->data;
    
    return OK;
}

2.7 根據(jù)指定位置刪除節(jié)點(diǎn)

由于引入了頭結(jié)點(diǎn)的概念，我們從頭結(jié)點(diǎn)開始就是可能待刪除節(jié)點(diǎn)的前驅(qū)，一直遍歷查找到前一個(gè)幾點(diǎn)。

刪除指定位置的節(jié)點(diǎn).png

核心算法：

• 1.找到待刪除位置的前一個(gè)節(jié)點(diǎn)
• 2.將前一個(gè)節(jié)點(diǎn)的next指向待刪除節(jié)點(diǎn)的next
• 3.釋放待刪除節(jié)點(diǎn)的內(nèi)存
  實(shí)現(xiàn)代碼：

/// 刪除指定位置的節(jié)點(diǎn)
/// @param L 鏈表
/// @param location 位置
/// @param e 返回刪除的數(shù)據(jù)
Status DeleteLinkList(LinkList *L, int location, ElemType *e){
    
    // 初始化一些輔助變量
    LinkList p = (*L);
    LinkList q;
    // 要找要刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，所以從0開始，如果要刪除首元節(jié)點(diǎn)的時(shí)候，其實(shí)他的前一個(gè)節(jié)點(diǎn)是頭結(jié)點(diǎn)（輔助節(jié)點(diǎn)）
    int j = 0;
    
    // 查找要刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    while (p->next && j<(location-1)) {
        p = p->next;
        j++;
    }
    // 沒找到要刪除的節(jié)點(diǎn)，或者位置非法就報(bào)錯
    if (!p->next && j>(location-1)) { return ERROR; }
    
    // 臨時(shí)存放要刪除的節(jié)點(diǎn)
    q = p->next;
    // 要刪除的前一個(gè)節(jié)點(diǎn)的next指向要刪除節(jié)點(diǎn)的next
    p->next = q->next;
    // 返回刪除的數(shù)據(jù)
    *e = q->data;
    // 釋放節(jié)點(diǎn)內(nèi)存
    free(q);
    
    return OK;
}

2.8 清空鏈表

清空主要是把鏈表恢復(fù)到初始狀態(tài)，刪除所有的除去頭節(jié)點(diǎn)的節(jié)點(diǎn)，并把頭結(jié)點(diǎn)的next置為NULL。

/// 清空單鏈表
/// @param L 單鏈表
Status ClearLinkList(LinkList *L){
    // 找到第一個(gè)節(jié)點(diǎn)
    LinkList p = (*L)->next;
    // 頭結(jié)點(diǎn)的next置空
    (*L)->next = NULL;
    // 輔助節(jié)點(diǎn)
    LinkList q;
    // 循環(huán)遍歷清空
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }

    return OK;
}

2.9 單鏈表頭插法

頭插法，顧名思義，就是一直在最前面插入數(shù)據(jù)，所以如果一組有序的數(shù)據(jù)插入完成后就是倒序的。
核心算法：

• 1.將新節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的next
• 2.將頭結(jié)點(diǎn)的next指向新節(jié)點(diǎn)

實(shí)現(xiàn)代碼：

/// 創(chuàng)建單鏈表，頭插法
/// @param L 鏈表
/// @param n 初始長度
void CreateLinkListHeader(LinkList *L, int n) {
    // 分配內(nèi)存
    *L = (LinkList)malloc(sizeof(Node));
    // 頭結(jié)點(diǎn)指針置空
    (*L)->next = NULL;
    
    LinkList p;
    for (int i = 1; i<=n; i++) {
        // 創(chuàng)建新節(jié)點(diǎn)
        p = (LinkList)malloc(sizeof(Node));
        // 新節(jié)點(diǎn)賦值
        p->data = i;
        //新節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的next
        p->next = (*L)->next;
        // 頭結(jié)點(diǎn)的next指向新節(jié)點(diǎn)
        (*L)->next = p;
    }
}

2.9 單鏈表尾插法

跟頭插法一樣，尾插法就是將新數(shù)據(jù)一直插入到單鏈表的尾部，所以如果一組有序的數(shù)據(jù)插入完成后就是正序的。
核心算法：

• 1.開辟一個(gè)輔助節(jié)點(diǎn)，不斷存儲新的尾節(jié)點(diǎn)初始化為頭結(jié)點(diǎn)
• 2.將輔助節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
• 3.將新節(jié)點(diǎn)賦值給輔助節(jié)點(diǎn)

實(shí)現(xiàn)代碼：

/// 尾插法
/// @param L 鏈表
/// @param n 長度
void CreateLinkListTail(LinkList *L, int n) {
    // 分配內(nèi)存
    *L = (LinkList)malloc(sizeof(Node));
    // 頭結(jié)點(diǎn)指針置空
    (*L)->next = NULL;
    LinkList p,r;
    r = *L;
    for (int i = 1; i<=n; i++) {
        // 創(chuàng)建新節(jié)點(diǎn)
        p = (LinkList)malloc(sizeof(Node));
        // 新節(jié)點(diǎn)賦值
        p->data = i;
        // 新節(jié)點(diǎn)的next為NULL
        p->next = NULL;
        // 輔助節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
        r->next = p;
        // 將新節(jié)點(diǎn)賦值給輔助節(jié)點(diǎn)
        r = p;
    }
}