數(shù)據(jù)結(jié)構(gòu)就是將大量而復(fù)雜的數(shù)據(jù)類型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器，并在此基礎(chǔ)上為了實(shí)現(xiàn)某個(gè)功能而執(zhí)行的相應(yīng)操作。 -- by 郝斌視頻

今天研究并實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)之一的鏈表實(shí)現(xiàn)。

鏈表是有 n 個(gè)結(jié)點(diǎn)離散分配，彼此通過指針相連的數(shù)據(jù)集合。

與數(shù)組相比，鏈表擁有無限空間，插入刪除元素快，但是鏈表的存取速度很慢。

實(shí)現(xiàn)鏈表的功能

1. 拼接 append
2. 添加 insert
3. 刪除 delete
4. 排序 sort
5. 獲取數(shù)組長度 len
6. 判斷數(shù)組是否為空 isempty
7. 打印顯示數(shù)組數(shù)據(jù) show

// 1. 創(chuàng)建鏈表
void init_list(PLINKLIST pHead);
// 2. 獲取鏈表長度
int  len_list(PLINKLIST pHead);
// 3. 判斷鏈表是否為空
bool isempty_list(PLINKLIST pHead);
// 5. 拼接鏈表
bool append_list(PLINKLIST pHead, int val);
// 6. 插入數(shù)據(jù)
bool insert_list(PLINKLIST pHead, int pos, int val);
// 7. 刪除數(shù)據(jù)
bool delete_list(PLINKLIST pHead, int pos, int * pVal);
// 8. 數(shù)組排序
void sort_list(PLINKLIST pHead);
// 9. 打印顯示
void show_list(PLINKLIST pHead);

按照上一篇數(shù)組實(shí)現(xiàn)的步驟，首先我們需要聲明一個(gè)鏈表。

鏈表的結(jié)構(gòu)體

1. 鏈表是一個(gè)離散存儲(chǔ)，使用指針連接，因此就不需要數(shù)組，但是需要一個(gè)指針連接下一個(gè)對(duì)象；
2. 每個(gè)對(duì)象都要保存一個(gè)一個(gè)數(shù)據(jù)

typedef struct LinkList {
    int data;// 數(shù)據(jù)域
    struct LinkList * pNext; // 指針域
}LINKLIST, *PLINKLIST;

然后創(chuàng)建鏈表頭結(jié)點(diǎn)并動(dòng)態(tài)分配空間，每個(gè)結(jié)點(diǎn)都指向下一個(gè)結(jié)點(diǎn)，通過一個(gè)頭結(jié)點(diǎn)我們可以獲取整個(gè)鏈表的數(shù)據(jù)，因此需要知道一個(gè)頭結(jié)點(diǎn)。

/**
 創(chuàng)建鏈表

 @param pHead 操作鏈表
 */
void init_list(PLINKLIST pHead)
{
    pHead = (PLINKLIST)malloc(sizeof(LINKLIST));
    if (NULL == pHead) {
        printf("內(nèi)存分配失敗!\n");
        exit(-1);
    }
    
    pHead->pNext = NULL;
    
    return;
}

首先，實(shí)現(xiàn)我們第一個(gè)方法，獲取鏈表的長度，大家也看到了這次聲明的鏈表結(jié)構(gòu)體并不存在長度 len 和 有效長度 cnt。

所以，獲取鏈表長度就沒有那么簡單了。

知道鏈表頭結(jié)點(diǎn)，通過獲取下一個(gè)結(jié)點(diǎn)，可以獲取到所有的結(jié)點(diǎn)和數(shù)據(jù)，那么我們就要遍歷所有的結(jié)點(diǎn)，知道這個(gè)結(jié)點(diǎn)指向的下一個(gè)結(jié)點(diǎn)為 NULL 為止，表示整個(gè)鏈表結(jié)束了。

/**
 獲取鏈表長度

 @param pHead 操作鏈表
 @return 鏈表長度
 */
int  len_list(PLINKLIST pHead)
{
    int len = 0;
    PLINKLIST pNext = pHead;
    while (NULL != pNext->pNext) {
        pNext = pNext->pNext;
        len ++;
    }
    
    return len;
}

判斷整個(gè)鏈表是否空，只要知道鏈表頭結(jié)點(diǎn)是否有指向下一個(gè)結(jié)點(diǎn)

/**
 判斷鏈表是否為空

 @param pHead 操作鏈表
 @return 鏈表長度
 */
bool isempty_list(PLINKLIST pHead)
{
    return NULL != pHead->pNext;
}

鏈表的拼接，需要我們經(jīng)過 n 次取下一個(gè)結(jié)點(diǎn)的操作，獲取最后一個(gè)結(jié)點(diǎn)，然后創(chuàng)建一個(gè)新的結(jié)點(diǎn)，讓鏈表最后一個(gè)結(jié)點(diǎn)的 pNext 指向我們新的結(jié)點(diǎn)。這里 n 就是當(dāng)前鏈表的長度。

/**
 追加鏈表

 @param pHead 操作鏈表
 @param val 追加數(shù)據(jù)值
 @return 是否追加成功
 */
bool append_list(PLINKLIST pHead, int val)
{
    PLINKLIST pNext = pHead;
    
    while (NULL != pNext->pNext) {
        pNext = pNext->pNext;
    }
    
    PLINKLIST pNew = (PLINKLIST)malloc(sizeof(LINKLIST));
    if (NULL == pNew) {
        printf("內(nèi)存分配失敗!\n");
        exit(-1);
    }
    pNew->data   = val;
    pNext->pNext = pNew;
    pNew->pNext  = NULL;
    
    return true;
}

鏈表的插入和拼接需要添加過濾條件，即插入的 pos(操作位置) 不能小于 1 并且不要大與當(dāng)前鏈表數(shù)據(jù)總數(shù) +1 ，刪除的 pos 不能小于 1 并且不要大于當(dāng)前鏈表數(shù)據(jù)總數(shù)。

然后通過循環(huán)遍歷，找到 pos - 1 對(duì)應(yīng)的結(jié)點(diǎn)，在此節(jié)點(diǎn)進(jìn)行插入和刪除操作。

插入操作

1. 需要?jiǎng)?chuàng)建一個(gè)新節(jié)點(diǎn)
2. 新節(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)是 pos - 1 節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
3. pos - 1 結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)則變成了新節(jié)點(diǎn)。

刪除操作，我們需要釋放 pos 結(jié)點(diǎn)

1. 現(xiàn)在我們知道了 pos - 1 結(jié)點(diǎn)
2. 那么 pos 結(jié)點(diǎn)就是 pos - 1 節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
3. 在釋放 pos 結(jié)點(diǎn)前我們需要修改 pos - 1 結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的指向，也就是說 pos - 1 結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向 pos 結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。

/**
 插入數(shù)據(jù)v

 @param pHead 操作鏈表
 @param pos 插入數(shù)據(jù)位置
 @param val 插入數(shù)據(jù)值
 @return 是否插入成功
 */
bool insert_list(PLINKLIST pHead, int pos, int val)
{
    int index = 0;
    PLINKLIST pNext = pHead;
    while (NULL != pNext->pNext && index < pos - 1) {
        pNext = pNext->pNext;
        index ++;
    }
    
    if (NULL == pNext || index >= pos) {
        printf("插入位置有問題\n");
        return false;
    }
    
    PLINKLIST pNew = (PLINKLIST)malloc(sizeof(LINKLIST));
    if (NULL == pNew) {
        printf("內(nèi)存分配失敗!\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->pNext = pNext->pNext;
    pNext->pNext = pNew;
    
    return true;
}

/**
 刪除數(shù)據(jù)

 @param pHead 操作鏈表
 @param pos 刪除數(shù)據(jù)位置
 @param pVal 刪除數(shù)據(jù)值
 @return 是否刪除數(shù)據(jù)成功
 */
bool delete_list(PLINKLIST pHead, int pos, int * pVal)
{
    int index = 0;
    PLINKLIST pNext = pHead;
    while (NULL != pNext->pNext && index < pos - 1) {
        pNext = pNext->pNext;
        index ++;
    }
    if (NULL == pNext->pNext || index >= pos) {
        printf("刪除位置有問題\n");
        return false;
    }
    
    PLINKLIST pCurrent = pNext->pNext;
    *pVal = pCurrent->data;
    pNext->pNext = pCurrent->pNext;
    free(pCurrent);
    pCurrent = NULL;
    
    return true;
}

最后就是排序和顯示操作了，原理跟數(shù)組相似，都是通過遍歷來實(shí)現(xiàn)。

/**
 數(shù)組排序

 @param pHead 操作鏈表
 */
void sort_list(PLINKLIST pHead)
{
    int i, j, t;
    PLINKLIST p, q;
    int len = len_list(pHead);
    
    for (i = 0, p = pHead->pNext; i < len - 1; ++ i, p = p->pNext) {
        for (j = i, q = p; j < len; ++ j, q = q->pNext) {
            if (p->data > q->data) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
    return;
}

/**
 打印顯示
 
 @param pHead 操作鏈表
 */
void show_list(PLINKLIST pHead)
{
    PLINKLIST pNext = pHead->pNext;
    while (NULL != pNext) {
        printf("%d ", pNext->data);
        pNext = pNext->pNext;
    }
    
    printf("\n");
    return;
}

到目前為止，C 語言實(shí)現(xiàn)鏈表的任務(wù)基本完工，剩下的就是測試和拓展新功能了。

如果各位客官有興趣可以在此基礎(chǔ)上完善，或者有什么需求也可以提出，如果我能完成也可以分享出來。

各路大牛輕噴，新手練手，有錯(cuò)請(qǐng)指出。

下面放出完整代碼供大家學(xué)習(xí)，喜歡請(qǐng) star 謝謝！