C語言實(shí)現(xiàn)循環(huán)單鏈表的示例代碼
更新時(shí)間：2023年08月04日 10:14:49 作者：r1v0z
這篇文章主要給大家詳細(xì)介紹了C語言如何實(shí)現(xiàn)循環(huán)單鏈表,文章通過代碼示例講解的非常詳細(xì),對(duì)我們的學(xué)習(xí)或工作有一定的參考價(jià)值,感興趣的小伙伴跟著小編一起來看看吧
一、定義
與單鏈表相似，只不過單鏈表最后一個(gè)節(jié)點(diǎn)的
next指向NULL，循環(huán)單鏈表最后一個(gè)節(jié)點(diǎn)指向鏈表的第一個(gè)節(jié)點(diǎn)
循環(huán)單鏈表也是分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)，部分操作對(duì)于不帶頭結(jié)點(diǎn)的循環(huán)單鏈表實(shí)現(xiàn)會(huì)復(fù)雜一些
循環(huán)單鏈表最大的優(yōu)點(diǎn)就是只要知道其中一個(gè)節(jié)點(diǎn)就可以訪問鏈表中的全部節(jié)點(diǎn)
二、基本操作
1.初始化鏈表
本文主要討論不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，初始化鏈表時(shí)不存在任何節(jié)點(diǎn)，所以將鏈表的指針指向 NULL
LinkList InitList()
{
LinkList list = NULL;
return list;
}2.頭插法
有兩種方法可以實(shí)現(xiàn)頭插法
方法一（不太建議）：找到最后一個(gè)節(jié)點(diǎn)，然后修改它的
next指向新的頭節(jié)點(diǎn)，很麻煩，要遍歷整個(gè)鏈表，就不多介紹了
方法二（建議）：創(chuàng)建新的節(jié)點(diǎn)，新節(jié)點(diǎn)的數(shù)據(jù)域存放，鏈表中第一個(gè)節(jié)點(diǎn)的數(shù)據(jù),將新節(jié)點(diǎn)插入到鏈表的第二位，將第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)修改為要插入的數(shù)據(jù)
status HeadInsertList(LinkList* list, int data)
{
LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
// 當(dāng) node 沒有成功分配內(nèi)存時(shí)，直接返回
if(node == NULL)
return EXIT_FAILURE;
if((*list) != NULL)
{
node->data = (*list)->data; // 將新節(jié)點(diǎn)的數(shù)據(jù)域，存放第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)
node->next = (*list)->next; // 當(dāng)鏈表中存在節(jié)點(diǎn)，則將 node->next 設(shè)置為第一個(gè)節(jié)點(diǎn)
(*list)->next = node;
(*list)->data = data;
}
else
{
node->data = data;
node->next = node; // 鏈表中沒有節(jié)點(diǎn)，將 node->next 指向自己
(*list) = node; // 修改頭指針指向 node
}
return EXIT_SUCCESS;
}3.尾插法
實(shí)現(xiàn)從尾部插入新節(jié)點(diǎn)，要先找到鏈表的最后一個(gè)節(jié)點(diǎn)：
status TailInsertList(LinkList* list, int e)
{
LinkNode* cur = (*list);
// 判斷 cur != NULL,是為了避免鏈表中沒有節(jié)點(diǎn)而發(fā)生錯(cuò)誤，當(dāng)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)，表示該節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)
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é)點(diǎn)
{
node->next = node;
(*list) = node;
}
else // 鏈表中有節(jié)點(diǎn)
{
node->next = (*list);
cur->next = node;
}
return EXIT_SUCCESS;
}4.按位插入
當(dāng)鏈表要在第一位插入節(jié)點(diǎn)時(shí)，需要進(jìn)行特殊處理，可以使用頭插法解決，在其他位置插入時(shí)，先修改新建節(jié)點(diǎn)的 next 指針指向下一個(gè)節(jié)點(diǎn)，再修改前面節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)
status InsertList(LinkList* list, int pos, int data)
{
// 初步判斷值是否有效，大于等于 1 不代表pos位置能夠插入，但小于 1 一定不能插入
if(pos < 1)
return EXIT_FAILURE;
// 當(dāng)要在第一位插入時(shí)，可以使用頭差法插入
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時(shí)，代表已經(jīng)到最后一個(gè)節(jié)點(diǎn)了，但是還是沒有到達(dá)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.頭刪法
頭刪法也有兩種方式刪除：
第一種方法：將第一個(gè)節(jié)點(diǎn)刪除，修改最后一個(gè)節(jié)點(diǎn)的
next指向新的頭結(jié)點(diǎn)，這會(huì)很麻煩，需要遍歷整個(gè)鏈表。
第二種方法是：將第二個(gè)節(jié)點(diǎn)的數(shù)據(jù)放入到第一個(gè)節(jié)點(diǎn)中，然后刪除掉第二個(gè)節(jié)點(diǎn)，這樣可以不需要修改最后一個(gè)節(jié)點(diǎn)的
next指針
status HeadDeleteList(LinkList* list)
{
// 判斷 next 是否指向本身，如果是表示只有一個(gè)節(jié)點(diǎn)
if((*list)->next == *list)
{
// 只有一個(gè)節(jié)點(diǎn)時(shí)，釋放后需要將指針指向 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ù)第二個(gè)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)，然后將最后一個(gè)節(jié)點(diǎn)刪除
status TailDeleteList(LinkList* list)
{
LinkNode* cur = *list;
LinkNode* pre = NULL;
// 遍歷鏈表，cur 表示當(dāng)前的節(jié)點(diǎn)， pre 表示前一個(gè)節(jié)點(diǎn)
while(cur->next != *list)
{
pre = cur;
cur = cur->next;
}
free(cur);
// 當(dāng) pre == NULL，則說明鏈表只有一個(gè)節(jié)點(diǎn)
if(pre == NULL)
*list = NULL; // 只有一個(gè)節(jié)點(diǎn)，刪除后沒有節(jié)點(diǎn)，所以 *list 指向 NULL
else
pre->next = *list; // 有多個(gè)節(jié)點(diǎn), 將刪除后的最后一個(gè)節(jié)點(diǎn)，指向開頭
return EXIT_SUCCESS;
}7. 按位刪除
當(dāng)要?jiǎng)h除的是第一位時(shí)，需要修改 list 的指向，可以使用頭刪法刪除，在其他位置時(shí)，只需將刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)的 next 修改為 刪除節(jié)點(diǎn)的 next ，最后將刪除節(jié)點(diǎn)
status DeleteList(LinkList* list, int pos)
{
// 判斷 pos 是否小于1，插入位置不能小于 1
if (pos < 1)
return EXIT_FAILURE;
// 當(dāng) pos 等于 1 時(shí)，使用頭插法
if (pos == 1)
return HeadDeleteList(list);
int curPos = 1; // 當(dāng)前節(jié)點(diǎn)的位置
LinkNode* curNode = *list; // 用于查找要?jiǎng)h除的節(jié)點(diǎn)
LinkNode* preNode = NULL; // 指向 curNode 的前一個(gè)節(jié)點(diǎn)，一開始沒有前一節(jié)點(diǎn)，所以初始化為NULL
while (curNode->next != *list && curPos < pos)
{
// 移動(dòng) curNode，直到 curNode 指向第 pos 位節(jié)點(diǎn)
preNode = curNode;
curNode = curNode->next;
curPos++;
}
// 當(dāng) curPos 小于 pos-1 時(shí)，curNode 已經(jīng)指向最后一個(gè)節(jié)點(diǎn)，故要插入的位置超出當(dāng)前鏈表長度
if(curPos < pos - 1)
return EXIT_FAILURE;
preNode->next = curNode->next;
free(curNode);
}8.打印鏈表
循環(huán)遍歷鏈表的所有節(jié)點(diǎn)，并將節(jié)點(diǎn)的數(shù)據(jù)打印出來，使用do ... while 是為了更好的判斷最后一個(gè)節(jié)點(diǎn)，當(dāng)?shù)谝淮闻袛?cur != list 時(shí)，cur已經(jīng)不是指向開頭了，而是指向第二個(gè)節(jié)點(diǎn)的位置，使用 cur != list 判斷是否完全遍歷整個(gè)鏈表是沒有問題的，而要使用其他循環(huán)打印會(huì)變得麻煩
status PrintList(LinkList list)
{
// list == NULL 鏈表中沒有節(jié)點(diǎn)；
LinkNode* cur = list;
do
{
printf("%d -> ", cur->data); // 打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
cur = cur->next; // cur 指向下一個(gè)節(jié)點(diǎn)
}while (cur != list); // cur == list 時(shí)表示已經(jīng)遍歷了整個(gè)鏈表，如果使用 cur->next != list 進(jìn)行判斷最后一個(gè)節(jié)點(diǎn)會(huì)無法打印
printf("NULL\n");
return EXIT_SUCCESS;
}9.銷毀鏈表
遍歷所有的節(jié)點(diǎn)，當(dāng)有節(jié)點(diǎn)的 next 指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)則結(jié)束，刪除遍歷的節(jié)點(diǎn)，最后將鏈表指針指向 NULL（可以理解為循環(huán)調(diào)用頭刪法，直到鏈表中沒有節(jié)點(diǎn)）
status DestroyList(LinkList* list)
{
if((*list) == NULL)
return EXIT_FAILURE;
LinkNode* curNode = *list; // curNode指向要釋放的節(jié)點(diǎn)
LinkNode* nextNode = NULL; // nextNode 指向要釋放節(jié)點(diǎn)的下一節(jié)點(diǎn)
while (curNode->next != *list) // 當(dāng) curNode->next 指向頭指針，curNode指向的是最后一個(gè)節(jié)點(diǎn)
{
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é)點(diǎn)
status InsertList(LinkList* list, int pos, int data);
// 按位刪除節(jié)點(diǎn)
status DeleteList(LinkList* list, int pos);
// 求表長
int Length(LinkList list);
// 按位置查找節(jié)點(diǎn)
LinkNode* GetElem(LinkList list, int pos);
// 按值查找節(jié)點(diǎn)
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é)點(diǎn)
LinkNode* nextNode = curNode->next; // nextNode 指向要釋放節(jié)點(diǎn)的下一節(jié)點(diǎn)
while (curNode->next != *list) // 當(dāng) curNode->next 指向頭指針，curNode指向的是最后一個(gè)節(jié)點(diǎn)
{
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)存時(shí)，直接返回
if(node == NULL)
return EXIT_FAILURE;
if((*list) != NULL)
{
node->data = (*list)->data; // 將新節(jié)點(diǎn)的數(shù)據(jù)域，存放第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)
node->next = (*list)->next; // 當(dāng)鏈表中存在節(jié)點(diǎn)，則將 node->next 設(shè)置為第一個(gè)節(jié)點(diǎn)
(*list)->next = node;
(*list)->data = data;
}
else
{
node->data = data;
node->next = node; // 鏈表中沒有節(jié)點(diǎn)，將 node->next 指向自己
(*list) = node; // 修改頭指針指向 node
}
return EXIT_SUCCESS;
}
// 尾插法
status TailInsertList(LinkList* list, int e)
{
LinkNode* cur = (*list);
// 判斷 cur != NULL,是為了避免鏈表中沒有節(jié)點(diǎn)而發(fā)生錯(cuò)誤，當(dāng)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)，表示該節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)
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é)點(diǎn)
{
node->next = node;
(*list) = node;
}
else // 鏈表中有節(jié)點(diǎn)
{
node->next = (*list);
cur->next = node;
}
return EXIT_SUCCESS;
}
// 頭刪法
status HeadDeleteList(LinkList* list)
{
// 判斷 next 是否指向本身，如果是表示只有一個(gè)節(jié)點(diǎn)
if((*list)->next == *list)
{
// 只有一個(gè)節(jié)點(diǎn)時(shí)，釋放后需要將指針指向 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é)點(diǎn)， pre 表示前一個(gè)節(jié)點(diǎn)
while(cur->next != *list)
{
pre = cur;
cur = cur->next;
}
free(cur);
// 當(dāng) pre == NULL，則說明鏈表只有一個(gè)節(jié)點(diǎn)
if(pre == NULL)
*list = NULL; // 只有一個(gè)節(jié)點(diǎn)，刪除后沒有節(jié)點(diǎn)，所以 *list 指向 NULL
else
pre->next = *list; // 有多個(gè)節(jié)點(diǎn), 將刪除后的最后一個(gè)節(jié)點(diǎn)，指向開頭
return EXIT_SUCCESS;
}
// 打印鏈表
status PrintList(LinkList list)
{
// list == NULL 鏈表中沒有節(jié)點(diǎn)；
LinkNode* cur = list;
do
{
printf("%d -> ", cur->data); // 打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
cur = cur->next; // cur 指向下一個(gè)節(jié)點(diǎn)
}while (cur != list); // cur == list 時(shí)表示已經(jīng)遍歷了整個(gè)鏈表，如果使用 cur->next != list 進(jìn)行判斷最后一個(gè)節(jié)點(diǎn)會(huì)無法打印
printf("NULL\n");
return EXIT_SUCCESS;
}
// 按位插入節(jié)點(diǎn)
status InsertList(LinkList* list, int pos, int data)
{
// 判斷值是否合法，大于等于 1 不代表pos有效，但小于1一定不能插入
if(pos < 1)
return EXIT_FAILURE;
// 當(dāng)要在第一位插入時(shí)，可以使用頭差法插入
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時(shí)，代表已經(jīng)到最后一個(gè)節(jié)點(diǎn)了，但是還是沒有到達(dá)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é)點(diǎn)
status DeleteList(LinkList* list, int pos)
{
// 判斷 pos 是否小于1，插入位置不能小于 1
if (pos < 1)
return EXIT_FAILURE;
// 當(dāng) pos 等于 1 時(shí)，使用頭插法
if (pos == 1)
return HeadDeleteList(list);
int curPos = 1; // 當(dāng)前節(jié)點(diǎn)的位置
LinkNode* curNode = *list; // 用于查找要?jiǎng)h除的節(jié)點(diǎn)
LinkNode* preNode = NULL; // 指向 curNode 的前一個(gè)節(jié)點(diǎn)，一開始沒有前一節(jié)點(diǎn)，所以初始化為NULL
while (curNode->next != *list && curPos < pos)
{
// 移動(dòng) curNode，直到 curNode 指向第 pos 位節(jié)點(diǎn)
preNode = curNode;
curNode = curNode->next;
curPos++;
}
// 當(dāng) curPos 小于 pos-1 時(shí)，curNode 已經(jīng)指向最后一個(gè)節(jié)點(diǎn)，故要插入的位置超出當(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é)點(diǎn)
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é)點(diǎn)
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語言實(shí)現(xiàn)循環(huán)單鏈表的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于C 循環(huán)單鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++中vector模擬實(shí)現(xiàn)中的迭代器失效問題
本文主要介紹了C++中vector插入操作導(dǎo)致迭代器失效的問題,插入后返回的迭代器位置變化,需及時(shí)更新以避免錯(cuò)誤,具有一定的參考價(jià)值,感興趣的可以了解一下2025-06-06
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)雙邊濾波算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
socketpair()創(chuàng)建已連接的匿名Unix套接字對(duì),用于高效進(jìn)程間通信,無需綁定或連接,支持雙向流式/數(shù)據(jù)報(bào)通信,適用于父子進(jìn)程和線程,相比管道,提供全雙工能力,結(jié)合了易用性與靈活性,本文給大家介紹c++中socketpair函數(shù)示例,感興趣的朋友一起看看吧2025-07-07
本文主要講解C語言 常量,這里整理了 C語言常量的基礎(chǔ)知識(shí)，并附代碼示例和示例詳細(xì)講解，希望能幫助開始學(xué)習(xí)C 語言的同學(xué)2021-09-09
共同體的定義類似結(jié)構(gòu)體，不過共同體的所有成員都在同一段內(nèi)存中存放，起始地址一樣，并且同一時(shí)刻只能使用其中的一個(gè)成員變量2013-10-10
C++數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹的實(shí)現(xiàn)
了解搜索二叉樹是為了STL中的map和set做鋪墊，我們所熟知的AVL樹和平衡搜索二叉樹也需要搜索二叉樹的基礎(chǔ)。本文將詳解如何利用C++實(shí)現(xiàn)搜索二叉樹，需要的可以參考一下2022-05-05
這篇文章主要介紹了C++ 兩個(gè)vector對(duì)象拼接方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
本篇文章介紹了，深入分析C++中deque的使用。需要的朋友參考下2013-05-05
C++11并發(fā)編程關(guān)于原子操作atomic的代碼示例
今天小編就為大家分享一篇關(guān)于C++11并發(fā)編程關(guān)于原子操作atomic的代碼示例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了C語言之如何求三次方根問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12