C語(yǔ)言實(shí)現(xiàn)循環(huán)單鏈表的示例代碼
一、定義
與單鏈表相似,只不過單鏈表最后一個(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)前鏈表長(zhǎ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);
// 求表長(zhǎng)
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)前鏈表長(zhǎng)度
if(curPos < pos - 1)
return EXIT_FAILURE;
preNode->next = curNode->next;
free(curNode);
}
// 求表長(zhǎng)
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語(yǔ)言實(shí)現(xiàn)循環(huán)單鏈表的示例代碼的詳細(xì)內(nèi)容,更多關(guān)于C 循環(huán)單鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語(yǔ)言之整數(shù)劃分問題(遞歸法)實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言之整數(shù)劃分問題(遞歸法)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-02-02
C語(yǔ)言數(shù)組元素循環(huán)右移問題及解決方法
這篇文章主要介紹了C語(yǔ)言數(shù)組元素循環(huán)右移問題,本文通過多種方法給大家分享解決方案,通過實(shí)例代碼講解,對(duì)大家的工作或?qū)W習(xí)具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲,附有詳細(xì)代碼,需要的小伙伴可以參考一下,希望對(duì)你的遼西有所幫助2021-10-10
VS2019+MPI配置過程的實(shí)現(xiàn)步驟
本文介紹了在VS2019上配置MPI,包括下載和安裝MPI、創(chuàng)建項(xiàng)目、配置屬性、導(dǎo)入頭文件和庫(kù)文件、添加依賴項(xiàng)等步驟,具有一定的參考價(jià)值,感興趣的可以了解一下2024-12-12

