骚货久久一,思思热性操

對(duì)于非空的線(xiàn)性表和線(xiàn)性結(jié)構(gòu)，具有以下特點(diǎn)：

存在唯一的一個(gè)被稱(chēng)作 第一個(gè) 的數(shù)據(jù)元素
存在唯一的一個(gè)被稱(chēng)作 最后一個(gè) 的數(shù)據(jù)元素
除了第一個(gè)元素以外，其他每個(gè)數(shù)據(jù)元素都有 一個(gè)前驅(qū)
除了最后一個(gè)元素以外，其他每個(gè)數(shù)據(jù)元素都有 一個(gè)后繼

線(xiàn)性表是最基本也是最常用的一種線(xiàn)性結(jié)構(gòu)，同時(shí)它也是其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。尤其是 單鏈表 ，這篇文章主要講述一下單鏈表的結(jié)構(gòu)以及如何用 C語(yǔ)言 實(shí)現(xiàn)一個(gè)單鏈表。

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

單鏈表是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，我們考察的主要是它的初始化、添加、刪除、遍歷等方法

初始化

單向鏈表是由一個(gè)個(gè)節(jié)點(diǎn)組成的，每一個(gè)節(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)段和指針段，數(shù)據(jù)段主要保存節(jié)點(diǎn)的相關(guān)信息，指針段主要保存后繼節(jié)點(diǎn)的地址。

#define ERROR 0
#define TRUE 1
#define FAILURE 0
#define SUCCESS 1

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

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

typedef struct Node *LinkList;
// 初始化單鏈表
Status InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    return SUCCESS;
}

添加節(jié)點(diǎn)

既然鏈表的節(jié)點(diǎn)已經(jīng)定義而且鏈表的數(shù)據(jù)結(jié)構(gòu)已經(jīng)初始化，接下來(lái)我們看看如何去添加元素，這里我們看兩種情況：

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

如圖所示，我們要對(duì)單鏈表進(jìn)行插入操作的時(shí)候要進(jìn)行額外判斷，如果要在首元節(jié)點(diǎn)之前添加節(jié)點(diǎn)，就要挪動(dòng)List指針，如果其他位置則不用。

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

這里帶頭節(jié)點(diǎn)的插入就很簡(jiǎn)單了，所有的地方一視同仁，而不需要額外去操作鏈表的指針。PS：其中頭節(jié)點(diǎn)中的信息我們不需要關(guān)心，因?yàn)樗喈?dāng)于我們默認(rèn)放進(jìn)去的一個(gè)節(jié)點(diǎn)。

所以后續(xù)我們使用的單鏈表默認(rèn) 添加頭節(jié)點(diǎn)。

我們要插入節(jié)點(diǎn)，就要對(duì)鏈表進(jìn)行修改，那么我們需要把 鏈表的指針 作為參數(shù)傳入。

// location from 1...
Status InsertNode(LinkList *L,int location,ListData data) {
    // 找到需要location-1位置的節(jié)點(diǎn)
    Node *pre = *L;
    // 因?yàn)?位置被頭節(jié)點(diǎn)占了，所以要從1位置開(kāi)始
    int currentLocation = 1;
    while (pre && currentLocation < location) {
        pre = pre->next;
        currentLocation ++;
    }
    if (!pre || currentLocation < location) return ERROR;

    // 根據(jù)data生成一個(gè)新節(jié)點(diǎn)
    Node *insertNode = (Node *)malloc(sizeof(Node));
    insertNode->data = data;
    // 讓新節(jié)點(diǎn)的next 指向 pre->next
    insertNode->next = pre->next;
    // 讓前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
    pre->next = insertNode;
    return SUCCESS;
}

此處邏輯跟圖上一一對(duì)應(yīng)，接下來(lái)我們要驗(yàn)證就要打印鏈表每個(gè)位置的值，我們添加一個(gè)打印的方法，我們只是打印鏈表，沒(méi)必要把傳遞指針。

// 打印方法 我們不用修改鏈表 無(wú)需傳指針
Status printList (LinkList L) {
    LinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    return SUCCESS;
}

我們驗(yàn)證一下：

int main(int argc, const char * argv[]) {
    LinkList L;
    Status status = InitList(&L);
    printf("s is %d\n",status);
    // 插入元素
    for (int i = 10; i >= 1; i --) {
        InsertNode(&L, 1, i);// 此處1表示，總是從頭節(jié)點(diǎn)后面插入新節(jié)點(diǎn)，也就是頭插法，比較簡(jiǎn)單，因?yàn)槲膊宸ㄟ€要保留鏈表長(zhǎng)度
    }
    // 打印鏈表
    printList(L);
    return 0;
}

打印結(jié)果如下：

刪除節(jié)點(diǎn)

結(jié)果如我們所愿，鏈表創(chuàng)建以及插入讀取都正常，接下來(lái)我們看看鏈表是如何刪除節(jié)點(diǎn)的：

創(chuàng)建臨時(shí)變量指向我們即將刪除的節(jié)點(diǎn)，一方面為了找到下一個(gè)節(jié)點(diǎn)，另外一個(gè)方面為了釋放內(nèi)存，否則就內(nèi)存泄漏了。
直接將臨時(shí)變量的上一個(gè)節(jié)點(diǎn)直接指向臨時(shí)變量的下一個(gè)節(jié)點(diǎn)
釋放臨時(shí)變量

Status DeleteNode (LinkList *L ,int location,ListData *deleteData) {
    Node *pre = *L;
    int currentLocation = 1;
    // 還是找到location-1位置的節(jié)點(diǎn)
    while (pre && currentLocation < location) {
        pre = pre->next;
        currentLocation++;
    }
    if (!pre || currentLocation < location) return ERROR;
    // 創(chuàng)建臨時(shí)變量 保存即將被刪除的節(jié)點(diǎn)
    Node *temp = pre->next;
    if (!temp) return ERROR;
    // 前驅(qū)節(jié)點(diǎn)指向后驅(qū)節(jié)點(diǎn)
    pre->next = temp->next;
    // 將我們刪除的內(nèi)容返回出去
    *deleteData = temp->data;
    // 釋放內(nèi)存
    free(temp);
    return SUCCESS;
}
//在main方法中添加如下代碼驗(yàn)證
// 刪除第五個(gè)節(jié)點(diǎn)
    ListData data;
    DeleteNode(&L, 5, &data);
    printf("刪除第五個(gè)元素后的鏈表是 :\n");
    printList(L);
    printf("被刪除的值是 %d\n",data);

清空單鏈表

指針指向首元節(jié)點(diǎn) 注意不是頭節(jié)點(diǎn) ，并將該節(jié)點(diǎn)釋放
指針偏移到下一個(gè)節(jié)點(diǎn) 中間節(jié)點(diǎn)
釋放下一個(gè)節(jié)點(diǎn) 中間節(jié)點(diǎn)
指針以此類(lèi)推到 尾節(jié)點(diǎn)
釋放 尾結(jié)點(diǎn)
頭節(jié)點(diǎn)指向 NULL 此處如果不處理，頭節(jié)點(diǎn)的 next就是 野指針了

Status clearList(LinkList *L) {
    // 由于第一個(gè)是頭節(jié)點(diǎn)，我們從第二個(gè)節(jié)點(diǎn)開(kāi)始刪除，這個(gè)地方可以根據(jù)實(shí)際情況來(lái)
    Node *pre = (*L)->next;
    Node *nextNode;
    while (pre) {
        // 用一個(gè)臨時(shí)變量保存當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)指向的下一個(gè)節(jié)點(diǎn)，有點(diǎn)像遞歸的意思
        nextNode = pre->next;
        // 釋放
        free(pre);
        // 將要?jiǎng)h除的指針偏移到下一個(gè)指針
        pre = nextNode;
    }
    // 此處將頭節(jié)點(diǎn)指向NULL ，否則就出現(xiàn)野指針了
    (*L)->next = NULL;
    return SUCCESS;
}

頭插法初始化

根據(jù)名字就知道了，從表頭處添加節(jié)點(diǎn)，之前一篇文章 @synchronized底層探索里的數(shù)據(jù)結(jié)構(gòu)用的就是哈希表，內(nèi)部就是通過(guò)頭插法進(jìn)行操作的。

Status InitFromHead(LinkList *L,int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    Node *pre = *L;
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = pre->next;
        pre->next = temp;
    }
    return SUCCESS;
}

// 在main中添加如下，會(huì)倒序打印30---1 就是頭插法
    clearList(&L);
    InitFromHead(&L, 30);
    printf("鏈表是 :\n");
    printList(L);

上述打印結(jié)果會(huì)從30倒序到1，足以證明是頭插法。

尾插法初始化

尾插法就是從鏈表尾部依次插入數(shù)據(jù)，這樣就跟我們平常的數(shù)組的邏輯差不多了，相當(dāng)于addObject,這里跟頭插法不同的是，頭插法依賴(lài)頭節(jié)點(diǎn)，此處依賴(lài)尾節(jié)點(diǎn)，所以我們要用一個(gè)臨時(shí)的指針指向尾結(jié)點(diǎn)并依次保存。

Status InitFromTail(LinkList *L,int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    // 初始化的時(shí)候尾結(jié)點(diǎn)就是頭節(jié)點(diǎn)
    Node *tail = *L;
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = NULL;
        tail->next = temp;
        // 尾節(jié)點(diǎn)偏移
        tail = tail->next;
    }
    return SUCCESS;
}
// 在main函數(shù)中添加如下代碼
    clearList(&L);
    InitFromTail(&L, 30);
    printf("鏈表是 :\n");
    printList(L);

但是細(xì)心的觀(guān)察你會(huì)發(fā)現(xiàn)，這個(gè)往鏈表尾部添加節(jié)點(diǎn)的方法的關(guān)鍵點(diǎn)在于先要找到尾節(jié)點(diǎn)，無(wú)非是通過(guò)循環(huán)直到找到一個(gè)節(jié)點(diǎn)的 next 是 NULL ,對(duì)于這個(gè)方法如果要初始化一個(gè)包含100個(gè)數(shù)字的的鏈表就要循環(huán)1+2+3+....+100 = 5050次，而用它上面那個(gè)函數(shù)添加的話(huà)只用循環(huán)100次，這個(gè)函數(shù)的時(shí)間復(fù)雜度是n*(n+1)/2 即是 O(n^2) 而上面那個(gè)是 O(n),所以這個(gè)方法只能針對(duì)初始化之后需要從尾部額外添加一個(gè)節(jié)點(diǎn)使用。

單向循環(huán)鏈表

看到 循環(huán) 兩個(gè)字我們就大概知道了，就是所有的節(jié)點(diǎn)組成一個(gè) 閉合的環(huán)，看起來(lái)應(yīng)該是這樣：

因?yàn)樯厦娴膯捂湵砦覀冞x用了使用頭節(jié)點(diǎn)的方式，下面我沒(méi)使用不帶頭節(jié)點(diǎn)的方式實(shí)現(xiàn)單向循環(huán)鏈表。具體以代碼體現(xiàn)，其原理跟單向鏈表差不多，有不清楚的結(jié)合單向鏈表的圖連接首位即可。

初始化

這里我們采用符合我們正常邏輯的尾插法來(lái)實(shí)現(xiàn)單向循環(huán)鏈表的初始化，因?yàn)槲覀兪褂貌粠ь^節(jié)點(diǎn)的方式，這里我們就要對(duì)鏈表的首元節(jié)點(diǎn)進(jìn)行判斷：

首元節(jié)點(diǎn)不存在，初始化并創(chuàng)建賦值給鏈表地址
存在即找到當(dāng)前鏈表的尾節(jié)點(diǎn)，依次插入后續(xù)節(jié)點(diǎn)

// 輸入的方式尾插法創(chuàng)建單向循環(huán)鏈表
Status InitList(LinkList *L) {
    int number;
    Node *tail = NULL;
    while (1) {
        scanf("%d",&number);
        // 輸入0結(jié)束創(chuàng)建
        if (number == 0) break;
        if (*L == NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if (*L == NULL)return ERROR;
            (*L)->data = number;
            (*L)->next = *L;
            tail = *L;
        } else {
            //找尾結(jié)點(diǎn)  方法1
            for (tail = *L; tail->next != *L; tail = tail->next);
            Node *temp = (Node *)malloc(sizeof(Node));
            if (!temp) return ERROR;
            temp->data = number;
            temp->next = *L;
            tail->next = temp;
            if (tail == NULL) return ERROR;
            //方法2
            Node *node = (Node *)malloc(sizeof(Node));
            if (!node) return ERROR;
            node->data = number;
            node->next = *L;
            tail->next = node;
            tail = tail->next;
        }
    }
    return SUCCESS;
}

上述我們找尾節(jié)點(diǎn)展示了兩種方法：

方法①：每次從首元節(jié)點(diǎn)依次循環(huán)直至找到 節(jié)點(diǎn)的next = 首元節(jié)點(diǎn) 即是當(dāng)前的尾結(jié)點(diǎn)。
方法②：用一個(gè)臨時(shí)變量指向尾節(jié)點(diǎn)（初始化的時(shí)候尾結(jié)點(diǎn)指向首元節(jié)點(diǎn)），每次插入新節(jié)點(diǎn)，臨時(shí)變量進(jìn)行偏移繼續(xù)指向尾結(jié)點(diǎn)。

顯然方法②的時(shí)間復(fù)雜度更小一點(diǎn) O(n)，方法①每插入一個(gè)新數(shù)據(jù)都要循環(huán)遍歷整個(gè)鏈表其時(shí)間復(fù)雜度是O(n^2) 。

插入節(jié)點(diǎn)

插入節(jié)點(diǎn)的邏輯其實(shí)跟單向鏈表差不多，無(wú)非就是指針的一些指向，但是這里要注意一些細(xì)節(jié)點(diǎn)：

插入新的首元節(jié)點(diǎn)，就要找到尾節(jié)點(diǎn)，然后尾節(jié)點(diǎn)指向新首元節(jié)點(diǎn)，新首元節(jié)點(diǎn)指向原首元節(jié)點(diǎn)，鏈表地址指向新首元節(jié)點(diǎn)。
其他地方同單向鏈表邏輯

void InsertNode(LinkList *List,int location, ListData data) {
    // 創(chuàng)建待插入節(jié)點(diǎn)
    Node *insertNode = (Node *)malloc(sizeof(Node));
    if (insertNode == NULL) return;
    insertNode->data = data;
    insertNode->next = NULL;
    if (location == 1) {
        // 找到最后一個(gè)節(jié)點(diǎn)即尾結(jié)點(diǎn)
        Node *tail = NULL;
        for (tail = *List; tail->next != *List; tail = tail->next);
        insertNode->next = tail->next;
        tail->next = insertNode;
        *List = insertNode;
    } else {
        Node *preNode = *List;
        // 找到插入位置的的前一個(gè)節(jié)點(diǎn)
        for (int i = 1; preNode->next != *List && i != location-1; preNode = preNode->next,i++);
        insertNode->next = preNode->next;
        preNode->next = insertNode;
    }
}

刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)同樣我們也要對(duì)首元節(jié)點(diǎn)的處理單獨(dú)拎出來(lái)：

Status DeleteNode(LinkList *List,int location,ListData *deleteData) {
    Node *temp = *List;
    if (temp == NULL) return ERROR;
    Node *target;
    if (location == 1) {// 刪除首元節(jié)點(diǎn)
        // 找到尾節(jié)點(diǎn)
        for (target = *List; target->next != *List; target = target->next);
        if (target == *List) {
            target->next = NULL;
            *List = NULL;
            *deleteData = temp->data;
            free(target);
            return SUCCESS;
        }
        target->next = temp->next;
        *List = target->next;
        *deleteData = temp->data;
        free(temp);
    } else {
        // 找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        target = *List;
        int i;
        for (i = 1,target = *List; i < location-1; i ++) {
            target = target->next;
        }
        Node *deleteNode = target->next;
        target->next = deleteNode->next;
        *deleteData = deleteNode->data;
        free(deleteNode);
    }
    return SUCCESS;
}

總結(jié)

至此我們 單鏈表 、單向循環(huán)鏈表 的一系列方法都已實(shí)現(xiàn)，使用頭節(jié)點(diǎn)、不使用頭節(jié)點(diǎn) 的方式都有，最后對(duì)比我們發(fā)現(xiàn)使用頭節(jié)點(diǎn)讓我們對(duì)于處理鏈表的插入數(shù)據(jù)以及刪除數(shù)據(jù)的處理會(huì)更簡(jiǎn)單，因?yàn)闆](méi)有針對(duì)首節(jié)點(diǎn)的單獨(dú)處理，針對(duì)此大家可以根據(jù)具體情況自行斟酌。其實(shí)還有很多方法和實(shí)現(xiàn)等著你去發(fā)掘，希望這篇文章能將單鏈表的概念和實(shí)現(xiàn)講清楚。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)與算法 - 單鏈表

數(shù)據(jù)結(jié)構(gòu)與算法 - 單鏈表

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

初始化

添加節(jié)點(diǎn)

刪除節(jié)點(diǎn)

清空單鏈表

頭插法初始化

尾插法初始化

單向循環(huán)鏈表

初始化

插入節(jié)點(diǎn)

刪除節(jié)點(diǎn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)與算法 - 單鏈表

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

初始化

添加節(jié)點(diǎn)

刪除節(jié)點(diǎn)

清空單鏈表

頭插法初始化

尾插法初始化

單向循環(huán)鏈表

初始化

插入節(jié)點(diǎn)

刪除節(jié)點(diǎn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av