一育特、線性表及其邏輯結(jié)構(gòu)

1啃憎、線性表的定義

線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。

該序列中所含的元素個(gè)數(shù)叫做線性表的長度次洼，用 n表示（n>=0）关贵。當(dāng) n=0時(shí)，表示線性表是一個(gè)空表卖毁，即表中不包含任何數(shù)據(jù)元素揖曾。

線性表中的第一個(gè)元素叫做表頭元素落萎，最后一個(gè)元素叫做表尾元素。

線性表在位置上是有序的炭剪，即第 i個(gè)元素處在第 i-1個(gè)元素后面练链、第 i+1個(gè)元素前面，這種位置上的有序性就是線性關(guān)系奴拦，所以線性表是一個(gè)線性結(jié)構(gòu)媒鼓。

2、線性表的抽象數(shù)據(jù)類型描述

ADT List{
    //數(shù)據(jù)對象 括號內(nèi)的 i是下標(biāo)
    D = {a(i)|1=<i<=n, n>=0, a（i）屬于 ElemType類型}
    //數(shù)據(jù)關(guān)系
    R = {<a(i), a(i+1)>, a(i+1)屬于 D, i=1,···,n-1}
    //基本運(yùn)算
    InitList(&L) //初始化線性表  該方法會將 L初始化為一個(gè)空的線性表
    DestroyList(&L) //銷毀線性表  該方法會釋放 L所占的儲存空間
    ListEmpty(L) //確定線性表是否為空  若 L為空表則返回真错妖，否則返回假
    DisPlayList(L) //輸出線性表  按順序輸出線性表中各個(gè)節(jié)點(diǎn)的值
    GetElem(L, i, &e) //獲取線性表中第 i個(gè)數(shù)據(jù)元素的值  并將該數(shù)據(jù)元素的值賦給 e（1=<i<=ListLength(L))
    LocateElem(L, e)  //返回 L中第一個(gè)和 e的值相等的數(shù)據(jù)元素的序號
    ListInsert(&L, i, e)  //在 L的第 i個(gè)元素之前插入 e绿鸣，L的長度增加 1
    ListDelete(&L, i, &e)  //刪除 L的第 i個(gè)元素并用 e返回其值
}

二、線性表的順序存儲結(jié)構(gòu)

1暂氯、順序表

線性表的順序存儲結(jié)構(gòu)就是：把線性表中的數(shù)據(jù)元素按照其邏輯順序一次存儲到計(jì)算機(jī)存儲器中指定存儲位置的一塊連續(xù)的存儲空間中潮模。這樣，表頭元素的存儲位置就是指定存儲空間的首地址痴施，第 i個(gè)元素就緊挨著第 i+1個(gè)元素前面擎厢。

假設(shè)線性表中的數(shù)據(jù)元素為 ElemType，則每個(gè)數(shù)據(jù)元素所占的存儲空間就是 sizeof(ElemType)辣吃，整個(gè)線性表占的存儲空間就是 n*sizeof(ElemType)动遭，其中 n是線性表的長度。

在 C/C++中數(shù)組中相鄰的兩個(gè)元素在內(nèi)存中的位置也是相鄰的齿尽，和順序表的存儲結(jié)構(gòu)剛好一樣沽损，所以在 C/C++中我們可以使用數(shù)組來實(shí)現(xiàn)順序表。

2循头、順序表的基本算法實(shí)現(xiàn)

我們先定義順序表和順序表中的數(shù)據(jù)元素的類型：

#define INIT_LIST_LEN 50
#define INCREACEMENT_NUM 20
#define ERROR -1
#define OK 1
#define NULL_VALUE -51

typedef char ElemType;
typedef struct {
    ElemType *data;
    int length;
    int max_size;
}LinerList;

這里 ElemType是順序表里的數(shù)據(jù)元素類型绵估，LinerList是順序表的類型。

在順序表中卡骂，我們定義了一個(gè) ElemType類型的數(shù)組指針 data国裳，這個(gè)指針指向一塊用來保存 ElemType類型數(shù)據(jù)的儲存空間。

在使用中我們可以把 data直接看作一個(gè) ElemType類型的數(shù)組全跨，不過和數(shù)組不同的是 data的大蟹熳蟆（相當(dāng)于數(shù)組的長度）是可以動態(tài)改變的。

length就是順序表當(dāng)前的長度浓若，max_size就是順序表當(dāng)前能夠存儲的最大元素?cái)?shù)量渺杉。

當(dāng) length要大于 max_size時(shí)，我們會通過 realloc函數(shù)來為 data分配一塊更大的內(nèi)存（大小是原來的大小加上 INIT_LIST_LEN再乘以 sizeof(ElemType)）挪钓。

接下來我們來定義順序表的基本運(yùn)算：

void InitList(LinerList*& L) {
    L = (LinerList*)malloc(sizeof(LinerList));
    L->data = (ElemType*)malloc(INIT_LIST_LEN * sizeof(ElemType));
    L->max_size = INIT_LIST_LEN;
    L->length = 0;
}

void DestroyList(LinerList*& L) {
    free(L->data);
    free(L);
    L = NULL;
}

bool ListEmpty(LinerList L) {
    //當(dāng) L未初始化時(shí) L.length小于 0
    //當(dāng) L初始化但為空時(shí) L.length等于 0
    //兩種情況都認(rèn)為 L為空
    if (L->length <= 0) {
        return true;
    }
    else {
        return false;
    }
}

int ListLength(LinerList L) {
    //當(dāng) L未初始化時(shí)返回 -1
    if (L->length >= 0) {
        return L->length;
    }
    else{
        return ERROR;
    }
}

void DisplayList(LinerList L) {
    if (L->length < 0) {
        printf("This list is not inited.\n");
    }
    else if(L->length == 0){
        printf("This list is empty.\n");
    }
    else {
        for (int i = 1; i <= L->length; i++) {
            printf("ElmType %2d: %c\n", i, L->data[i]);
        }
    }
}

void GetElem(LinerList L, int i, ElemType* e) {
    if (i <= 0 || i > L.length) {
        printf("invalid integer i.\n");
    }
    else{
        *e = L.data[i];
    }
}

int LocateElem(LinerList L, ElemType e) {
    //包含對錯(cuò)誤的處理
    for (int i = 1; i <= L.length; i++) {
        if (L.data[i] == e) {
            return i;
        }
    }
    return 0;
}

ListInsert：

int ListInsert(LinerList* L, int i, ElemType e) {
    //當(dāng) length == max_size時(shí)再分配內(nèi)存最后一個(gè)數(shù)據(jù)元素會丟失
    if (L->length == L->max_size - 1) {
        L->data = (ElemType*)realloc(L->data, (L->max_size + INCREACEMENT_NUM) * sizeof(ElemType));
        L->max_size += INCREACEMENT_NUM;
    }

    if (i > L->length + 1 || i <= 0) {
        return ERROR;
    }
    else {
        for (int k = L->length; k >= i; k--) {
            L->data[k + 1] = L->data[k];
        }
        L->data[i] = e;
        L->length++;
    }

    return OK;
}

在插入數(shù)據(jù)元素之前是越，我們要先檢查順序表長度是否已達(dá)到最大容量，如果順序表已經(jīng)達(dá)到最大長度碌上，我們用 realloc重新分配一塊更大的內(nèi)存倚评，并且順序表的最大容量 max_size增加 INCREACEMENT_NUM（也就是 20）浦徊。

若順序表還沒達(dá)到最大容量，我們先對插入位置 i的有效性進(jìn)行檢查天梧。

顯然當(dāng) i小于或等于 0和 i大于順序表長度加 1的時(shí)候是無效的盔性。

當(dāng)確定 i是有效的時(shí)候，我們才執(zhí)行插入操作呢岗。

首先我們先把第 i個(gè)元素及其后面的所有元素向后移一個(gè)位置冕香，然后再將數(shù)據(jù)元素 e插入到第 i個(gè)位置，并將順序表的長度加 1.

ListDelete：

int ListDelete(LinerList* L, int i, ElemType* e) {
    if (i > L->length || i <= 0) {
        return ERROR;
    }
    else {
        *e = L->data[i];
        for (int k = i; k < L->length; k++) {
            L->data[k] = L->data[k + 1];
        }
        L->data[L->length] = NULL_VALUE;
        L->length--;
    }
}

和插入數(shù)據(jù)元素時(shí)一樣敷燎，我們在執(zhí)行刪除操作之前先檢查 i的有效性暂筝，當(dāng) i的值有效時(shí)我們才進(jìn)行下一步執(zhí)行刪除操作。

在刪除目標(biāo)數(shù)據(jù)元素之前硬贯，我們先將它的值賦給數(shù)據(jù)元素 e，然后再將其在順序表中刪除陨收，并且順序表的長度減 1饭豹。

在刪除一個(gè)數(shù)據(jù)元素的時(shí)候，我們跟在該數(shù)據(jù)元素之后的所有數(shù)據(jù)元素向前移一個(gè)位置务漩，然后將最后一個(gè)數(shù)據(jù)元素的值賦值為空值拄衰，最后將順序表的長度減一。

測試：

int main() {
    LinerList* L = NULL;
    
    InitList(L);

    ElemType t;
    ElemType a = 'a';
    ElemType b = 'b';

    //檢查順序表是否為空
    if (ListEmpty(*L)) {
        printf("true\n");
    }
    else {
        printf("false\n");
    }

    //順序表為空時(shí)刪除
    ListDelete(L, 1, &t);
    //順序表為空時(shí)輸出順序表
    DisplayList(*L);
    //順序表為空時(shí)定位
    printf("the locate is %d\n", LocateElem(*L, b));
    //獲取順序表長度
    printf("list length: %d\n", ListLength(*L));

    for (int i = 0; i < 100; i++) {
        ListInsert(L, 1, a);
    }

    //檢查順序表是否為空
    if (ListEmpty(*L)) {
        printf("true\n");
    }
    else {
        printf("false\n");
    }


    //順序表達(dá)到最大長度時(shí)插入
    ListInsert(L, 10, b);
    //順序表達(dá)到最大長度時(shí)刪除
    ListDelete(L, 1, &t);
    ListDelete(L, 1, &t);
    //給定過大的 i
    ListInsert(L, 100, a);
    ListInsert(L, 101, a);
    //順序表不為空時(shí)定位
    printf("the locate is %d\n", LocateElem(*L, b));
    //獲取順序表長度
    printf("list length: %d\n", ListLength(*L));
    //輸出順序表
    DisplayList(*L);


    int c;
    scanf_s("%d", &c);
}

三饵骨、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1翘悉、鏈表

在鏈?zhǔn)酱鎯χ校總€(gè)節(jié)點(diǎn)不僅包含有元素本省的信息（這稱為數(shù)據(jù)域）居触，還包含了元素之間的邏輯關(guān)系的信息妖混，即前驅(qū)節(jié)點(diǎn)包含了后繼節(jié)點(diǎn)的地址信息（這稱為指針域），這樣可以通過前驅(qū)節(jié)點(diǎn)指針域中的信息方便地找到后繼節(jié)點(diǎn)地位置轮洋。

由于順序表中每個(gè)數(shù)據(jù)元素最多只有一個(gè)前驅(qū)節(jié)點(diǎn)和一個(gè)后繼節(jié)點(diǎn)制市，所以當(dāng)采用鏈?zhǔn)酱鎯r(shí)，一般在每個(gè)節(jié)點(diǎn)中只設(shè)置一個(gè)指針域弊予，用來指向后繼節(jié)點(diǎn)地位置祥楣，這樣構(gòu)成的鏈接表稱為單向鏈接表，簡稱單鏈表汉柒。

另一種方法是误褪，在每個(gè)節(jié)點(diǎn)中設(shè)置兩個(gè)指針域，分別用來指向前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)碾褂，這樣構(gòu)成的鏈表稱為雙鏈表兽间。

在單鏈表中，由于每個(gè)節(jié)點(diǎn)只有一個(gè)指向后繼節(jié)點(diǎn)的指針斋扰，所以當(dāng)我們訪問過一個(gè)節(jié)點(diǎn)后渡八，只能接著訪問它的后繼節(jié)點(diǎn)啃洋，而無法訪問它的前驅(qū)節(jié)點(diǎn)。在雙鏈表中屎鳍，由于每個(gè)節(jié)點(diǎn)既包含有指向前驅(qū)節(jié)點(diǎn)的指針宏娄，也包含了指向后繼節(jié)點(diǎn)的指針，所以我們在訪問過一個(gè)節(jié)點(diǎn)后逮壁，既可以依次訪問它的前驅(qū)節(jié)點(diǎn)孵坚，也可以依次訪問它的后繼節(jié)點(diǎn)。

在線性表的鏈?zhǔn)酱鎯χ锌瑸榱朔奖悴迦牒蛣h除算法的實(shí)現(xiàn)卖宠，每個(gè)鏈表帶有一個(gè)頭節(jié)點(diǎn)，并通過頭節(jié)點(diǎn)的指針唯一標(biāo)識該鏈表忧饭。

在單鏈表中扛伍，每個(gè)節(jié)點(diǎn)應(yīng)該包含存儲元素的數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的指針域，我們使用 C語言的結(jié)構(gòu)體來定義單鏈表的節(jié)點(diǎn)類型：

typedef char ElemType;
typedef struct ListNode {
    ElemType data;
    ListNode* next;
} LinkList;

對于雙鏈表词裤。采用類似單鏈表的類型定義刺洒，不過和單鏈表不同的是，雙鏈表有兩個(gè)指針域吼砂。

typedef char ElemType;
typedef struct DListNode {
    ElemType data;
    DListNode* pre;
    DListNode* next;
} DLinkList;

2逆航、單鏈表的基本運(yùn)算實(shí)現(xiàn)

（1）頭插法創(chuàng)建單鏈表

頭插法創(chuàng)建鏈表的方法是：先創(chuàng)建一個(gè)頭節(jié)點(diǎn)，然后將新節(jié)點(diǎn)插入到頭節(jié)點(diǎn)的后面渔肩。注意這里的頭節(jié)點(diǎn)只保存鏈表開始節(jié)點(diǎn)的地址因俐，并不保數(shù)據(jù)，也就是說鏈表的第一個(gè)節(jié)點(diǎn)應(yīng)該是頭節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)周偎，頭插法的算法實(shí)現(xiàn)如下：

void CreateLinkList(LinkList*& L, ElemType data[], int n) {
    L = (LinkList*)malloc(sizeof(LinkList));
    L->next = NULL;

    for (int i = 0; i < n; i++) {
        LinkList* p = (LinkList*)malloc(sizeof(LinkList));
        p->data = data[i];
        p->next = L->next;
        L->next = p;
    }
}

思考：

既然頭節(jié)點(diǎn)不保存任何數(shù)據(jù)抹剩，能否另外再定義一個(gè)頭節(jié)點(diǎn)類型來表示一個(gè)鏈表？

如：

typedef char ElemType;
typedef struct ListNode {
    ElemType data;
    ListNode* next;
} ListNode;
typedef struct {
    int length;
    ListNode *first_node
} LinkList;

這里 ElemType是要保存的數(shù)據(jù)類型栏饮，ListNode是鏈表的節(jié)點(diǎn)類型吧兔，LinkLIst是鏈表類型。

我們用 LInkList類型的變量來表示一個(gè)鏈表，它包含了一個(gè)指向鏈表開始節(jié)點(diǎn)的指針和表示鏈表長度的變量 length。

（2）尾插法創(chuàng)建單鏈表

頭插法創(chuàng)建鏈表雖然簡單山涡，但是頭插法創(chuàng)建的鏈表中的數(shù)據(jù)元素的順序和原數(shù)組元素的順序相反。如果希望兩者的順序一致箍土，我們可以使用尾插法來創(chuàng)建鏈表。

尾插法建表時(shí)將數(shù)據(jù)元素添加到鏈表的尾部罐监，所以我們需要一個(gè)指針來指向鏈表的尾部（這個(gè)指針指只在創(chuàng)建鏈表時(shí)使用）吴藻。

尾插法創(chuàng)建鏈表的算法如下：

void ECreateLinkList(LinkList*& L, ElemType data[], int n) {
    L = (LinkList*)malloc(sizeof(LinkList));
    L->next = NULL;

    LinkList* end = L; // end始終指向鏈表尾部

    for (int i = 0; i < n; i++) {
        LinkList* p = (LinkList*)malloc(sizeof(LinkList));
        p->data = data[i];
        end->next = p;
        end = p;
    }
    end->next = NULL;
}

銷毀鏈表需要把每個(gè)節(jié)點(diǎn)的空間都釋放：

void DestroyList(LinkList*& L){
    LinkList* p = L;
    LinkList* q = p->next;

    while(q != NULL) {
        free(p);
        p = q;
        q = p->next;
    }
    free(p);
}

（3）單鏈表的基本運(yùn)算

void DestroyList(LinkList*& L){
    LinkList* p = L;
    LinkList* q = p->next;

    while(q != NULL) {
        free(p);
        p = q;
        q = p->next;
    }
    free(p);
}

bool ListEmpty(LinkList* L) {
    if (L->next == NULL) {
        return true;
    }
    else {
        return false;
    }
}

int ListLength(LinkList* L) {
    int i = 0;
    LinkList* t = L;

    while (t->next != NULL) {
        i++;
        t = t->next;
    }

    return i;
}

void DisplayList(LinkList* L) {
    if (L->next == NULL) {
        printf("list is empty.\n");
    }
    else {
        while (L->next != NULL) {
            L = L->next;
            printf("node data: %c\n", L->data);

        }
    }
}

void GetElem(LinkList* L, int i, ListNode*& e) {
    int count = 0;
    while (L->next != NULL && count < i) {
        L = L->next;
        count++;
    }

    if (count == i) {
        e = (ListNode*)malloc(sizeof(ListNode));
        e->data = L->data;
        e->next = L->next;
    }
    else {
        e = NULL;
    }
}

int LocateElem(LinkList* L, ListNode* e) {
    int i = 1;
    L = L->next;

    while (L != NULL && L->data != e->data) {
        L = L->next;
        i++;
    }

    if (L == NULL) {
        return 0;
    }
    else {
        return i;
    }
}

向鏈表中插入節(jié)點(diǎn)：

int ListInsert(LinkList* L, int i, ListNode* e) {
    int count = 0;
    while (count < i - 1 && L != NULL) {
        count++;
        L = L->next;
    }

    if (L == NULL || count == 0) {
        return 0;
    }
    else {
        LinkList* t = L->next;
        L->next = e;
        e->next = t;
        return 1;
    }
}

在向鏈表中插入節(jié)點(diǎn)時(shí)，我們先定位到第 i-1個(gè)節(jié)點(diǎn)弓柱。

如果第 i-1個(gè)節(jié)點(diǎn)存在沟堡，則 count=i-1侧但，且 L不為空；如果第 i-1個(gè)節(jié)點(diǎn)不存在航罗，則 L為空禀横；如果輸入的 i為非法值（比如負(fù)數(shù)），則 count為 0粥血。

當(dāng)?shù)?i-1個(gè)節(jié)點(diǎn)存在時(shí)柏锄，直接將第 i-1個(gè)節(jié)點(diǎn)的 next指針指向要插入的節(jié)點(diǎn)，并將要插入的節(jié)點(diǎn)的 next指針指向第 i+1個(gè)節(jié)點(diǎn)（原來的第 i個(gè)節(jié)點(diǎn)）复亏。

當(dāng)?shù)?i-1個(gè)節(jié)點(diǎn)不存在時(shí)趾娃，第 i個(gè)節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，所以不能將節(jié)點(diǎn)插入到第 i個(gè)節(jié)點(diǎn)處缔御。

刪除鏈表中的節(jié)點(diǎn)：

int ListDelete(LinkList* L, int i, ListNode*& e) {
    int count = 0;
    while (count < i - 1 && L != NULL) {
        count++;
        L = L->next;
    }
    
    if (L != NULL && L->next != NULL && count != 0) {
        ListNode *t = L->next;
        e = (ListNode*)malloc(sizeof(ListNode));
        e->data = t->data;
        e->next = t->next;
        L->next = t->next;
        free(t);
        return 1;
    }
    else {
        e = NULL;
        return 0;
    }
}

和插入節(jié)點(diǎn)一樣抬闷，在刪除節(jié)點(diǎn)時(shí)我們也要先定位第 i-1個(gè)節(jié)點(diǎn)，不過和插入節(jié)點(diǎn)有一點(diǎn)不同的是耕突，我們要先檢查第 i個(gè)節(jié)點(diǎn)是否存在饶氏，只有當(dāng)?shù)?i個(gè)節(jié)點(diǎn)存在時(shí)我們才執(zhí)行刪除操作。

這里我們?yōu)槭裁匆ㄎ坏?i-1個(gè)節(jié)點(diǎn)有勾，而不是第 i個(gè)節(jié)點(diǎn)呢？

這是因?yàn)閱捂湵碇荒軉蜗蛟L問古程，第 i個(gè)節(jié)點(diǎn)時(shí)無法訪問第 i-1個(gè)節(jié)點(diǎn)的蔼卡。所以如果我們定位到第 i個(gè)節(jié)點(diǎn)的話，就無法將第 i-1個(gè)節(jié)點(diǎn)指向后面一個(gè)節(jié)點(diǎn)了挣磨。

3雇逞、雙鏈表的基本運(yùn)算實(shí)現(xiàn)

雙鏈表中有兩個(gè)指針域，一個(gè)指向前驅(qū)節(jié)點(diǎn)茁裙、另一個(gè)指向后繼節(jié)點(diǎn)塘砸。

typedef char ElemType;
typedef struct DListNode {
    ElemType data;
    DListNode* pre;
    DListNode* next;
} DLinkList;

和單鏈表類似，建立雙鏈表也有兩種方法：頭插法和尾插法晤锥。

（1）頭插法建立雙鏈表

void CreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
    L = (DLinkList*)malloc(sizeof(DLinkList));
    L->pre = NULL;
    L->next = NULL;

    for (int i = 0; i < n; i++) {
        DLinkList *t = (DLinkList*)malloc(sizeof(DLinkList));

        t->next = L->next;
        t->pre = L;
        t->data = data[i];

        L->next = t;

        if (t->next != NULL) {
            t->next->pre = t;
        }
    }
}

在頭插法建立雙鏈表的算法中掉蔬，我們先為頭節(jié)點(diǎn)分配存儲空間并將頭節(jié)點(diǎn)的兩個(gè)指針域都賦值為 NULL。

在向雙鏈表中插入節(jié)點(diǎn)時(shí)矾瘾，我們總是將待插入的節(jié)點(diǎn)插入到頭節(jié)點(diǎn)和開始節(jié)點(diǎn)之間女轿。

插入節(jié)點(diǎn)時(shí)，我們先將待插入節(jié)點(diǎn)的 next指針指開始節(jié)點(diǎn)（也就是 L->next所指向的節(jié)點(diǎn)）壕翩，再將待插入節(jié)點(diǎn)的 pre指針指向頭節(jié)點(diǎn)蛉迹，這時(shí)我們已經(jīng)建立了待插入節(jié)點(diǎn)與頭節(jié)點(diǎn)和開始節(jié)點(diǎn)之間的關(guān)系。

不過這時(shí)的關(guān)系還是單向的放妈，我們還需要讓頭節(jié)點(diǎn)的 next指針指向待插入節(jié)點(diǎn)北救，這時(shí)頭節(jié)點(diǎn)和待插入節(jié)點(diǎn)之間的雙向關(guān)系就已經(jīng)建立好了荐操。

我們可以用同樣的方法將待插入節(jié)點(diǎn)和其后繼節(jié)點(diǎn)建立雙向連接，不過在建立連接之前我們需要檢查一下是否存在后繼節(jié)點(diǎn)珍策，存在后繼節(jié)點(diǎn)才建立雙向連接托启。

（2）尾插法建立雙鏈表

void ECreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
    L = (DLinkList*)malloc(sizeof(DLinkList));
    L->pre = NULL;
    L->next = NULL;

    //始終指向雙鏈表尾部的指針
    DLinkList *end = L;

    for (int i = 0; i < n; i++) {
        DLinkList* t = (DLinkList*)malloc(sizeof(DLinkList));

        t->pre = end;
        t->data = data[i];

        end->next = t;

        end = t;
    }
    end->next = NULL;
}

4、循環(huán)鏈表

循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)膛壹，它的特點(diǎn)是鏈表中最后一個(gè)節(jié)點(diǎn)的 next指針不再是空驾中，而是指向鏈表的頭節(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)模聋。

這樣我們在鏈表的任一節(jié)點(diǎn)出發(fā)都可以訪問到鏈表中的其他節(jié)點(diǎn)

循環(huán)鏈表分為循環(huán)雙鏈表和循環(huán)單鏈表肩民，基本操作與單鏈表和雙鏈表一樣，我們主要講一下如何創(chuàng)建循環(huán)鏈表链方。

（1）創(chuàng)建循環(huán)單鏈表

//創(chuàng)建循環(huán)單鏈表
void createLoopLink(ListNode *&L, ElemType* e, int l) {
    //創(chuàng)建頭節(jié)點(diǎn)
    L = (LinkList*)malloc(sizeof(ListNode));
    ListNode* p = L;

    for (int i = 0; i < l; i++) {
        ListNode* t = (ListNode*)malloc(sizeof(LinkList));
        p->next = t;
        t->data = e[i];
        p = t;
    }
    //將尾節(jié)點(diǎn)和頭節(jié)點(diǎn)連接起來
    p->next = L;
}

前面的部分和創(chuàng)建單鏈表時(shí)一樣持痰，只是在最后我們需要將尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)，這樣才能構(gòu)成一個(gè)循環(huán)祟蚀。

（2）創(chuàng)建循環(huán)雙鏈表

//創(chuàng)建循環(huán)雙鏈表
void createLoopDLink(DListNode *&D, ElemType* e, int l) {
    //創(chuàng)建頭節(jié)點(diǎn)
    D = (DLinkList*)malloc(sizeof(DListNode));
    D->pre = NULL;
    DListNode* p = D;

    for (int i = 0; i < l; i++) {
        DListNode* t = (DListNode*)malloc(sizeof(DLinkList));
        p->next = t;
        t->pre = p;
        t->data = e[i];
        p = t;
    }
    //將尾節(jié)點(diǎn)和頭節(jié)點(diǎn)連接起來
    p->next = D;
    D->pre = p;
}

和創(chuàng)建循環(huán)單鏈表一樣簡單工窍，創(chuàng)建循環(huán)雙鏈表只需要將前后節(jié)點(diǎn)都連接起來就行

轉(zhuǎn)載自：
數(shù)據(jù)結(jié)構(gòu)教程（第二版）
李春葆 等 編著
清華大學(xué)出版社
ISBN：978-7-302-14229-4