欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)循環(huán)單鏈表的示例代碼

 更新時間：2023年08月04日 10:14:49   作者：r1v0z  
這篇文章主要給大家詳細介紹了C語言如何實現(xiàn)循環(huán)單鏈表,文章通過代碼示例講解的非常詳細,對我們的學(xué)習(xí)或工作有一定的參考價值,感興趣的小伙伴跟著小編一起來看看吧

一、定義

  • 與單鏈表相似，只不過單鏈表最后一個節(jié)點的 next 指向 NULL，循環(huán)單鏈表最后一個節(jié)點指向鏈表的第一個節(jié)點

    image-20230802171836724.png

  • 循環(huán)單鏈表也是分為帶頭結(jié)點和不帶頭結(jié)點，部分操作對于不帶頭結(jié)點的循環(huán)單鏈表實現(xiàn)會復(fù)雜一些

  • 循環(huán)單鏈表最大的優(yōu)點就是只要知道其中一個節(jié)點就可以訪問鏈表中的全部節(jié)點

二、基本操作

1.初始化鏈表

本文主要討論不帶頭結(jié)點的循環(huán)單鏈表，初始化鏈表時不存在任何節(jié)點，所以將鏈表的指針指向 NULL

LinkList InitList()
{
    LinkList list = NULL;
    return list;
}

2.頭插法

有兩種方法可以實現(xiàn)頭插法

  1. 方法一（不太建議）：找到最后一個節(jié)點，然后修改它的 next 指向新的頭節(jié)點，很麻煩，要遍歷整個鏈表，就不多介紹了

    image-20230802203854732.png

  2. 方法二（建議）：創(chuàng)建新的節(jié)點，新節(jié)點的數(shù)據(jù)域存放，鏈表中第一個節(jié)點的數(shù)據(jù),將新節(jié)點插入到鏈表的第二位，將第一個節(jié)點的數(shù)據(jù)修改為要插入的數(shù)據(jù)

    image-20230802205206435.png

status HeadInsertList(LinkList* list, int data)
{
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    // 當(dāng) node 沒有成功分配內(nèi)存時，直接返回
    if(node == NULL)
        return EXIT_FAILURE;
    if((*list) != NULL)
    {
        node->data = (*list)->data;     // 將新節(jié)點的數(shù)據(jù)域，存放第一個節(jié)點的數(shù)據(jù)
        node->next = (*list)->next;     // 當(dāng)鏈表中存在節(jié)點，則將 node->next 設(shè)置為第一個節(jié)點
        (*list)->next = node;
        (*list)->data = data;
    }
    else
    {
        node->data = data;
        node->next = node;     // 鏈表中沒有節(jié)點，將 node->next 指向自己
        (*list) = node;        // 修改頭指針指向 node
    }
    return EXIT_SUCCESS;
}

3.尾插法

實現(xiàn)從尾部插入新節(jié)點，要先找到鏈表的最后一個節(jié)點：

image-20230802212207620.png

status TailInsertList(LinkList* list, int e)
{
    LinkNode* cur = (*list);
    // 判斷 cur != NULL,是為了避免鏈表中沒有節(jié)點而發(fā)生錯誤，當(dāng)節(jié)點的 next 指向第一個節(jié)點，表示該節(jié)點為最后一個節(jié)點
    while (cur != NULL && cur->next != (*list))       
        cur = cur->next;
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    if (node == NULL)
        return EXIT_FAILURE;
    node->data = e;
    if (cur == NULL)    // 鏈表中沒有節(jié)點
    {
        node->next = node;
        (*list) = node;
    }
    else                // 鏈表中有節(jié)點
    {
        node->next = (*list);
        cur->next = node;
    }
    return EXIT_SUCCESS;
}

4.按位插入

當(dāng)鏈表要在第一位插入節(jié)點時，需要進行特殊處理，可以使用頭插法解決，在其他位置插入時，先修改新建節(jié)點的 next 指針指向下一個節(jié)點，再修改前面節(jié)點的 next 指向新節(jié)點

image-20230802213703897.png

status InsertList(LinkList* list, int pos, int data)
{
    // 初步判斷值是否有效，大于等于 1 不代表pos位置能夠插入，但小于 1 一定不能插入
    if(pos < 1)
        return EXIT_FAILURE;
    // 當(dāng)要在第一位插入時，可以使用頭差法插入
    if (pos == 1)
        return HeadInsertList(list, data);
    LinkNode* curNode = *list;
    int count = 1;      // 表示當(dāng)前的位置
    while (curNode->next != *list && count < pos - 1)
    {
        // 
        curNode = curNode->next;
        count++;
    }
    // 當(dāng) count < pos - 1時，代表已經(jīng)到最后一個節(jié)點了，但是還是沒有到達pos - 1的位置
    if(count < pos - 1)
        return EXIT_FAILURE;
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    if(node == NULL)
        return EXIT_FAILURE;
    node->data = data;
    node->next = curNode->next;
    curNode->next = node;
    return EXIT_SUCCESS;
}

5.頭刪法

頭刪法也有兩種方式刪除：

  • 第一種方法：將第一個節(jié)點刪除，修改最后一個節(jié)點的 next 指向新的頭結(jié)點，這會很麻煩，需要遍歷整個鏈表。

    image-20230803175327634.png

  • 第二種方法是：將第二個節(jié)點的數(shù)據(jù)放入到第一個節(jié)點中，然后刪除掉第二個節(jié)點，這樣可以不需要修改最后一個節(jié)點的 next 指針

    image-20230803120425092.png

status HeadDeleteList(LinkList* list)
{
    // 判斷 next 是否指向本身，如果是表示只有一個節(jié)點
    if((*list)->next == *list)
    {
        // 只有一個節(jié)點時，釋放后需要將指針指向 NULL
        free(*list);
        *list = NULL;
    }
    else
    {
        LinkNode* curNode = (*list)->next;
        (*list)->next = curNode->next;
        (*list)->data = curNode->data;
        free(curNode);
    }
    return EXIT_SUCCESS;
}

6.尾刪法

將倒數(shù)第二個節(jié)點的 next 指向第一個節(jié)點，然后將最后一個節(jié)點刪除

image-20230803180922490.png

status TailDeleteList(LinkList* list)
{
    LinkNode* cur = *list;
    LinkNode* pre = NULL;
    // 遍歷鏈表，cur 表示當(dāng)前的節(jié)點， pre 表示前一個節(jié)點
    while(cur->next != *list)
    {
        pre = cur;
        cur = cur->next;
    }
    free(cur);
    // 當(dāng) pre == NULL，則說明鏈表只有一個節(jié)點
    if(pre == NULL)
        *list = NULL;       // 只有一個節(jié)點，刪除后沒有節(jié)點，所以 *list 指向 NULL
    else
        pre->next = *list;  // 有多個節(jié)點, 將刪除后的最后一個節(jié)點，指向開頭
    return EXIT_SUCCESS;
}

7. 按位刪除

當(dāng)要刪除的是第一位時，需要修改 list 的指向，可以使用頭刪法刪除，在其他位置時，只需將刪除節(jié)點的前一節(jié)點的 next 修改為 刪除節(jié)點的 next ，最后將刪除節(jié)點

image-20230803183347287.png

status DeleteList(LinkList* list, int pos)
{
    // 判斷 pos 是否小于1，插入位置不能小于 1
    if (pos < 1)
        return EXIT_FAILURE;
    // 當(dāng) pos 等于 1 時，使用頭插法
    if (pos == 1)
        return HeadDeleteList(list);
    int curPos = 1;                 // 當(dāng)前節(jié)點的位置
    LinkNode* curNode = *list;     // 用于查找要刪除的節(jié)點
    LinkNode* preNode = NULL;      // 指向 curNode 的前一個節(jié)點，一開始沒有前一節(jié)點，所以初始化為NULL
    while (curNode->next != *list && curPos < pos)
    {
        // 移動 curNode，直到 curNode 指向第 pos 位節(jié)點
        preNode = curNode;
        curNode = curNode->next;
        curPos++;
    }
    // 當(dāng) curPos 小于 pos-1 時，curNode 已經(jīng)指向最后一個節(jié)點，故要插入的位置超出當(dāng)前鏈表長度
    if(curPos < pos - 1)
        return EXIT_FAILURE;
    preNode->next = curNode->next;
    free(curNode);
}

8.打印鏈表

循環(huán)遍歷鏈表的所有節(jié)點，并將節(jié)點的數(shù)據(jù)打印出來，使用do ... while 是為了更好的判斷最后一個節(jié)點，當(dāng)?shù)谝淮闻袛?cur != list 時，cur已經(jīng)不是指向開頭了，而是指向第二個節(jié)點的位置，使用 cur != list 判斷是否完全遍歷整個鏈表是沒有問題的，而要使用其他循環(huán)打印會變得麻煩

status PrintList(LinkList  list)
{
    // list == NULL 鏈表中沒有節(jié)點；
    LinkNode* cur = list;
    do
    {
        printf("%d -> ", cur->data);    // 打印當(dāng)前節(jié)點的數(shù)據(jù)
        cur = cur->next;    // cur 指向下一個節(jié)點
    }while (cur != list);   // cur == list 時表示已經(jīng)遍歷了整個鏈表，如果使用 cur->next != list 進行判斷最后一個節(jié)點會無法打印     
    printf("NULL\n");
    return EXIT_SUCCESS;
}

9.銷毀鏈表

遍歷所有的節(jié)點，當(dāng)有節(jié)點的 next 指向當(dāng)前鏈表的第一個節(jié)點則結(jié)束，刪除遍歷的節(jié)點，最后將鏈表指針指向 NULL（可以理解為循環(huán)調(diào)用頭刪法，直到鏈表中沒有節(jié)點）

status DestroyList(LinkList* list)
{
    if((*list) == NULL)
        return EXIT_FAILURE;
    LinkNode* curNode = *list;     // curNode指向要釋放的節(jié)點
    LinkNode* nextNode = NULL;     // nextNode 指向要釋放節(jié)點的下一節(jié)點
    while (curNode->next != *list)  // 當(dāng) curNode->next 指向頭指針，curNode指向的是最后一個節(jié)點
    {
        nextNode = curNode->next;
        free(curNode);
        curNode = nextNode;
    }
    *list = NULL;
    return EXIT_SUCCESS;
}

三、完整代碼

  • LoopLinkList.h
#include<stdio.h>
#include<stdlib.h>
typedef int status;
typedef struct Node
{
    int data;
    struct Node* next;
}LinkNode, *LinkList;
// 初始化
LinkList InitList();
// 銷毀鏈表
status DestroyList(LinkList* list);
// 頭插法
status HeadInsertList(LinkList* list, int e);
// 尾插法
status TailInsertList(LinkList* list, int e);
// 頭刪法
status HeadDeleteList(LinkList* list);
// 尾刪法
status TailDeleteList(LinkList* list);
// 打印鏈表
status PrintList(LinkList list);
// 按位插入節(jié)點
status InsertList(LinkList* list, int pos, int data);
// 按位刪除節(jié)點
status DeleteList(LinkList* list, int pos);
// 求表長
int Length(LinkList list);
// 按位置查找節(jié)點
LinkNode* GetElem(LinkList list, int pos);
// 按值查找節(jié)點
LinkNode* LocateElem(LinkList list, int data);
  • LoopLinkList.c
#include "./head/LoopLinkList.h"
// 初始化
LinkList InitList()
{
    LinkList list = NULL;
    return list;
}
// 銷毀鏈表
status DestroyList(LinkList* list)
{
    if((*list) == NULL)
        return EXIT_FAILURE;
    LinkNode* curNode = *list;     // curNode指向要釋放的節(jié)點
    LinkNode* nextNode = curNode->next;     // nextNode 指向要釋放節(jié)點的下一節(jié)點
    while (curNode->next != *list)  // 當(dāng) curNode->next 指向頭指針，curNode指向的是最后一個節(jié)點
    {
        nextNode = curNode->next;
        free(curNode);
        curNode = nextNode;
    }
    *list = NULL;
    return EXIT_SUCCESS;
}
// 頭插法
status HeadInsertList(LinkList* list, int data)
{
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    // 當(dāng) node 沒有成功分配內(nèi)存時，直接返回
    if(node == NULL)
        return EXIT_FAILURE;
    if((*list) != NULL)
    {
        node->data = (*list)->data;     // 將新節(jié)點的數(shù)據(jù)域，存放第一個節(jié)點的數(shù)據(jù)
        node->next = (*list)->next;     // 當(dāng)鏈表中存在節(jié)點，則將 node->next 設(shè)置為第一個節(jié)點
        (*list)->next = node;
        (*list)->data = data;
    }
    else
    {
        node->data = data;
        node->next = node;     // 鏈表中沒有節(jié)點，將 node->next 指向自己
        (*list) = node;        // 修改頭指針指向 node
    }
    return EXIT_SUCCESS;
}
// 尾插法
status TailInsertList(LinkList* list, int e)
{
    LinkNode* cur = (*list);
    // 判斷 cur != NULL,是為了避免鏈表中沒有節(jié)點而發(fā)生錯誤，當(dāng)節(jié)點的 next 指向第一個節(jié)點，表示該節(jié)點為最后一個節(jié)點
    while (cur != NULL && cur->next != (*list))       
        cur = cur->next;
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    if (node == NULL)
        return EXIT_FAILURE;
    node->data = e;
    if (cur == NULL)    // 鏈表中沒有節(jié)點
    {
        node->next = node;
        (*list) = node;
    }
    else                // 鏈表中有節(jié)點
    {
        node->next = (*list);
        cur->next = node;
    }
    return EXIT_SUCCESS;
}
// 頭刪法
status HeadDeleteList(LinkList* list)
{
    // 判斷 next 是否指向本身，如果是表示只有一個節(jié)點
    if((*list)->next == *list)
    {
        // 只有一個節(jié)點時，釋放后需要將指針指向 NULL
        free(*list);
        *list = NULL;
    }
    else
    {
        LinkNode* curNode = (*list)->next;
        (*list)->next = curNode->next;
        (*list)->data = curNode->data;
        free(curNode);
    }
    return EXIT_SUCCESS;
}
// 尾刪法
status TailDeleteList(LinkList* list)
{
    LinkNode* cur = *list;
    LinkNode* pre = NULL;
    // 遍歷鏈表，cur 表示當(dāng)前的節(jié)點， pre 表示前一個節(jié)點
    while(cur->next != *list)
    {
        pre = cur;
        cur = cur->next;
    }
    free(cur);
    // 當(dāng) pre == NULL，則說明鏈表只有一個節(jié)點
    if(pre == NULL)
        *list = NULL;       // 只有一個節(jié)點，刪除后沒有節(jié)點，所以 *list 指向 NULL
    else
        pre->next = *list;  // 有多個節(jié)點, 將刪除后的最后一個節(jié)點，指向開頭
    return EXIT_SUCCESS;
}
// 打印鏈表
status PrintList(LinkList  list)
{
    // list == NULL 鏈表中沒有節(jié)點；
    LinkNode* cur = list;
    do
    {
        printf("%d -> ", cur->data);    // 打印當(dāng)前節(jié)點的數(shù)據(jù)
        cur = cur->next;    // cur 指向下一個節(jié)點
    }while (cur != list);   // cur == list 時表示已經(jīng)遍歷了整個鏈表，如果使用 cur->next != list 進行判斷最后一個節(jié)點會無法打印     
    printf("NULL\n");
    return EXIT_SUCCESS;
}
// 按位插入節(jié)點
status InsertList(LinkList* list, int pos, int data)
{
    // 判斷值是否合法，大于等于 1 不代表pos有效，但小于1一定不能插入
    if(pos < 1)
        return EXIT_FAILURE;
    // 當(dāng)要在第一位插入時，可以使用頭差法插入
    if (pos == 1)
        return HeadInsertList(list, data);
    LinkNode* curNode = *list;
    int count = 1;      // 表示當(dāng)前的位置
    while (curNode->next != *list && count < pos - 1)
    {
        // 
        curNode = curNode->next;
        count++;
    }
    // 當(dāng) count < pos - 1時，代表已經(jīng)到最后一個節(jié)點了，但是還是沒有到達pos - 1的位置
    if(count < pos - 1)
        return EXIT_FAILURE;
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    if(node == NULL)
        return EXIT_FAILURE;
    node->data = data;
    node->next = curNode->next;
    curNode->next = node;
    return EXIT_SUCCESS;
}
// 按位刪除節(jié)點
status DeleteList(LinkList* list, int pos)
{
    // 判斷 pos 是否小于1，插入位置不能小于 1
    if (pos < 1)
        return EXIT_FAILURE;
    // 當(dāng) pos 等于 1 時，使用頭插法
    if (pos == 1)
        return HeadDeleteList(list);
    int curPos = 1;                 // 當(dāng)前節(jié)點的位置
    LinkNode* curNode = *list;     // 用于查找要刪除的節(jié)點
    LinkNode* preNode = NULL;      // 指向 curNode 的前一個節(jié)點，一開始沒有前一節(jié)點，所以初始化為NULL
    while (curNode->next != *list && curPos < pos)
    {
        // 移動 curNode，直到 curNode 指向第 pos 位節(jié)點
        preNode = curNode;
        curNode = curNode->next;
        curPos++;
    }
    // 當(dāng) curPos 小于 pos-1 時，curNode 已經(jīng)指向最后一個節(jié)點，故要插入的位置超出當(dāng)前鏈表長度
    if(curPos < pos - 1)
        return EXIT_FAILURE;
    preNode->next = curNode->next;
    free(curNode);
}
// 求表長
int Length(LinkList list)
{
    int len = 1;
    LinkNode* curNode = list;
    while (curNode->next != list)
    {
        len++;
        curNode = curNode->next;
    }
    return len;
}
// 按位置查找節(jié)點
LinkNode* GetElem(LinkList list, int pos)
{
    LinkNode* curNode = list;
    int curPos = 1;
    while (curNode->next == list && curPos < pos)
    {
        curNode = curNode->next;
        curPos++;
    }
    if (curPos == pos)
        return curNode;
    else
        return NULL;
}
// 按值查找節(jié)點
LinkNode* LocateElem(LinkList list, int data)
{
    LinkNode* curNode = list;
    while (curNode->next == list)
    {
        if(curNode->data == data)
            return curNode;
        curNode = curNode->next;
    }
    return NULL;
}

以上就是C語言實現(xiàn)循環(huán)單鏈表的示例代碼的詳細內(nèi)容，更多關(guān)于C 循環(huán)單鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • C++實現(xiàn)推箱子功能附加回撤示例

    C++實現(xiàn)推箱子功能附加回撤示例

    本文主要介紹了C++實現(xiàn)推箱子功能附加回撤示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-10-10
  • C++入門指南之貪吃蛇游戲的實現(xiàn)

    C++入門指南之貪吃蛇游戲的實現(xiàn)

    這篇文章主要給大家介紹了關(guān)于C++入門指南之貪吃蛇游戲?qū)崿F(xiàn)的相關(guān)資料,文章通過示例代碼介紹的非常詳細,可以讓大家能短時間內(nèi)寫出一個貪吃蛇,需要的朋友可以參考下
    2021-10-10
  • C++之多態(tài)(內(nèi)容不錯)

    C++之多態(tài)(內(nèi)容不錯)

    什么是多態(tài)？顧名思義就是同一個事物在不同場景下的多種形態(tài),需要的朋友可以參考下
    2020-01-01
  • C語言之整數(shù)劃分問題（遞歸法）實例代碼

    C語言之整數(shù)劃分問題（遞歸法）實例代碼

    這篇文章主要介紹了C語言之整數(shù)劃分問題（遞歸法）實例代碼的相關(guān)資料,需要的朋友可以參考下
    2017-02-02
  • C語言圖書借閱系統(tǒng)源碼

    C語言圖書借閱系統(tǒng)源碼

    這篇文章主要為大家分享了C語言圖書借閱系統(tǒng)源碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-02-02
  • C語言數(shù)組元素循環(huán)右移問題及解決方法

    C語言數(shù)組元素循環(huán)右移問題及解決方法

    這篇文章主要介紹了C語言數(shù)組元素循環(huán)右移問題,本文通過多種方法給大家分享解決方案，通過實例代碼講解，對大家的工作或?qū)W習(xí)具有一定的參考借鑒價值，需要的朋友可以參考下
    2020-03-03
  • C++左值和右值學(xué)習(xí)筆記

    C++左值和右值學(xué)習(xí)筆記

    這篇文章主要為大家介紹了C++左值和右值學(xué)習(xí)筆記的重點講解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-10-10
  • C語言實現(xiàn)猜數(shù)字小游戲

    C語言實現(xiàn)猜數(shù)字小游戲

    這篇文章主要介紹了C語言實現(xiàn)猜數(shù)字小游戲，附有詳細代碼,需要的小伙伴可以參考一下，希望對你的遼西有所幫助
    2021-10-10
  • C++線程池實現(xiàn)代碼

    C++線程池實現(xiàn)代碼

    C++11中，線程我們可以理解為對應(yīng)一個thread對象，任務(wù)可以理解為要執(zhí)行的函數(shù)，通常是耗時的函數(shù)。線程過多或者頻繁創(chuàng)建和銷毀線程會帶來調(diào)度開銷，進而影響緩存局部性和整體性能
    2021-12-12
  • VS2019+MPI配置過程的實現(xiàn)步驟

    VS2019+MPI配置過程的實現(xiàn)步驟

    本文介紹了在VS2019上配置MPI,包括下載和安裝MPI、創(chuàng)建項目、配置屬性、導(dǎo)入頭文件和庫文件、添加依賴項等步驟,具有一定的參考價值,感興趣的可以了解一下
    2024-12-12

最新評論