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

更新時間：2023年08月04日 10:14:49 作者：r1v0z

這篇文章主要給大家詳細介紹了C語言如何實現(xiàn)循環(huán)單鏈表,文章通過代碼示例講解的非常詳細,對我們的學習或工作有一定的參考價值,感興趣的小伙伴跟著小編一起來看看吧

一、定義

與單鏈表相似，只不過單鏈表最后一個節(jié)點的 next 指向 NULL，循環(huán)單鏈表最后一個節(jié)點指向鏈表的第一個節(jié)點
循環(huán)單鏈表也是分為帶頭結(jié)點和不帶頭結(jié)點，部分操作對于不帶頭結(jié)點的循環(huán)單鏈表實現(xiàn)會復雜一些
循環(huán)單鏈表最大的優(yōu)點就是只要知道其中一個節(jié)點就可以訪問鏈表中的全部節(jié)點

二、基本操作

1.初始化鏈表

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

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

2.頭插法

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

方法一（不太建議）：找到最后一個節(jié)點，然后修改它的 next 指向新的頭節(jié)點，很麻煩，要遍歷整個鏈表，就不多介紹了
方法二（建議）：創(chuàng)建新的節(jié)點，新節(jié)點的數(shù)據(jù)域存放，鏈表中第一個節(jié)點的數(shù)據(jù),將新節(jié)點插入到鏈表的第二位，將第一個節(jié)點的數(shù)據(jù)修改為要插入的數(shù)據(jù)

status HeadInsertList(LinkList* list, int data)
{
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    // 當 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;     // 當鏈表中存在節(jié)點，則將 node->next 設置為第一個節(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é)點：

status TailInsertList(LinkList* list, int e)
{
    LinkNode* cur = (*list);
    // 判斷 cur != NULL,是為了避免鏈表中沒有節(jié)點而發(fā)生錯誤，當節(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.按位插入

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

status InsertList(LinkList* list, int pos, int data)
{
    // 初步判斷值是否有效，大于等于 1 不代表pos位置能夠插入，但小于 1 一定不能插入
    if(pos < 1)
        return EXIT_FAILURE;
    // 當要在第一位插入時，可以使用頭差法插入
    if (pos == 1)
        return HeadInsertList(list, data);
    LinkNode* curNode = *list;
    int count = 1;      // 表示當前的位置
    while (curNode->next != *list && count < pos - 1)
    {
        // 
        curNode = curNode->next;
        count++;
    }
    // 當 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é)點，這會很麻煩，需要遍歷整個鏈表。
第二種方法是：將第二個節(jié)點的數(shù)據(jù)放入到第一個節(jié)點中，然后刪除掉第二個節(jié)點，這樣可以不需要修改最后一個節(jié)點的 next 指針

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é)點刪除

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

7. 按位刪除

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

status DeleteList(LinkList* list, int pos)
{
    // 判斷 pos 是否小于1，插入位置不能小于 1
    if (pos < 1)
        return EXIT_FAILURE;
    // 當 pos 等于 1 時，使用頭插法
    if (pos == 1)
        return HeadDeleteList(list);
    int curPos = 1;                 // 當前節(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++;
    }
    // 當 curPos 小于 pos-1 時，curNode 已經(jīng)指向最后一個節(jié)點，故要插入的位置超出當前鏈表長度
    if(curPos < pos - 1)
        return EXIT_FAILURE;
    preNode->next = curNode->next;
    free(curNode);
}

8.打印鏈表

循環(huán)遍歷鏈表的所有節(jié)點，并將節(jié)點的數(shù)據(jù)打印出來，使用do ... while 是為了更好的判斷最后一個節(jié)點，當?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);    // 打印當前節(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é)點，當有節(jié)點的 next 指向當前鏈表的第一個節(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)  // 當 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)  // 當 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));
    // 當 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;     // 當鏈表中存在節(jié)點，則將 node->next 設置為第一個節(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ā)生錯誤，當節(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 表示當前的節(jié)點， pre 表示前一個節(jié)點
    while(cur->next != *list)
    {
        pre = cur;
        cur = cur->next;
    }
    free(cur);
    // 當 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);    // 打印當前節(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;
    // 當要在第一位插入時，可以使用頭差法插入
    if (pos == 1)
        return HeadInsertList(list, data);
    LinkNode* curNode = *list;
    int count = 1;      // 表示當前的位置
    while (curNode->next != *list && count < pos - 1)
    {
        // 
        curNode = curNode->next;
        count++;
    }
    // 當 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;
    // 當 pos 等于 1 時，使用頭插法
    if (pos == 1)
        return HeadDeleteList(list);
    int curPos = 1;                 // 當前節(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++;
    }
    // 當 curPos 小于 pos-1 時，curNode 已經(jīng)指向最后一個節(jié)點，故要插入的位置超出當前鏈表長度
    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)容，更多關于C 循環(huán)單鏈表的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

C++中vector模擬實現(xiàn)中的迭代器失效問題
本文主要介紹了C++中vector插入操作導致迭代器失效的問題,插入后返回的迭代器位置變化,需及時更新以避免錯誤,具有一定的參考價值,感興趣的可以了解一下
2025-06-06
OpenCV實現(xiàn)雙邊濾波算法
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)雙邊濾波算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-10-10
c++中socketpair函數(shù)示例詳解
socketpair()創(chuàng)建已連接的匿名Unix套接字對,用于高效進程間通信,無需綁定或連接,支持雙向流式/數(shù)據(jù)報通信,適用于父子進程和線程,相比管道,提供全雙工能力,結(jié)合了易用性與靈活性,本文給大家介紹c++中socketpair函數(shù)示例,感興趣的朋友一起看看吧
2025-07-07
C語言中的常量詳解
本文主要講解C語言常量,這里整理了 C語言常量的基礎知識，并附代碼示例和示例詳細講解，希望能幫助開始學習C 語言的同學
2021-09-09
C++共用體的定義與應用總結(jié)
共同體的定義類似結(jié)構(gòu)體，不過共同體的所有成員都在同一段內(nèi)存中存放，起始地址一樣，并且同一時刻只能使用其中的一個成員變量
2013-10-10
C++數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹的實現(xiàn)
了解搜索二叉樹是為了STL中的map和set做鋪墊，我們所熟知的AVL樹和平衡搜索二叉樹也需要搜索二叉樹的基礎。本文將詳解如何利用C++實現(xiàn)搜索二叉樹，需要的可以參考一下
2022-05-05
C++ 兩個vector對象拼接方式
這篇文章主要介紹了C++ 兩個vector對象拼接方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-11-11
深入分析C++中deque的使用
本篇文章介紹了，深入分析C++中deque的使用。需要的朋友參考下
2013-05-05
C++11并發(fā)編程關于原子操作atomic的代碼示例
今天小編就為大家分享一篇關于C++11并發(fā)編程關于原子操作atomic的代碼示例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2018-12-12
C語言之如何求三次方根
這篇文章主要介紹了C語言之如何求三次方根問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-12-12