C語(yǔ)言實(shí)現(xiàn)循環(huán)單鏈表的示例代碼
一、定義
與單鏈表相似,只不過(guò)單鏈表最后一個(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)就可以訪問(wè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 沒(méi)有成功分配內(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; // 鏈表中沒(méi)有節(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,是為了避免鏈表中沒(méi)有節(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) // 鏈表中沒(méi)有節(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)了,但是還是沒(méi)有到達(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,則說(shuō)明鏈表只有一個(gè)節(jié)點(diǎn) if(pre == NULL) *list = NULL; // 只有一個(gè)節(jié)點(diǎn),刪除后沒(méi)有節(jié)點(diǎn),所以 *list 指向 NULL else pre->next = *list; // 有多個(gè)節(jié)點(diǎn), 將刪除后的最后一個(gè)節(jié)點(diǎn),指向開(kāi)頭 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),一開(kāi)始沒(méi)有前一節(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ù)打印出來(lái),使用do ... while
是為了更好的判斷最后一個(gè)節(jié)點(diǎn),當(dāng)?shù)谝淮闻袛?cur != list
時(shí),cur已經(jīng)不是指向開(kāi)頭了,而是指向第二個(gè)節(jié)點(diǎn)的位置,使用 cur != list
判斷是否完全遍歷整個(gè)鏈表是沒(méi)有問(wèn)題的,而要使用其他循環(huán)打印會(huì)變得麻煩
status PrintList(LinkList list) { // list == NULL 鏈表中沒(méi)有節(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ì)無(wú)法打印 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)用頭刪法,直到鏈表中沒(méi)有節(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 沒(méi)有成功分配內(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; // 鏈表中沒(méi)有節(jié)點(diǎn),將 node->next 指向自己 (*list) = node; // 修改頭指針指向 node } return EXIT_SUCCESS; } // 尾插法 status TailInsertList(LinkList* list, int e) { LinkNode* cur = (*list); // 判斷 cur != NULL,是為了避免鏈表中沒(méi)有節(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) // 鏈表中沒(méi)有節(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,則說(shuō)明鏈表只有一個(gè)節(jié)點(diǎn) if(pre == NULL) *list = NULL; // 只有一個(gè)節(jié)點(diǎn),刪除后沒(méi)有節(jié)點(diǎn),所以 *list 指向 NULL else pre->next = *list; // 有多個(gè)節(jié)點(diǎn), 將刪除后的最后一個(gè)節(jié)點(diǎn),指向開(kāi)頭 return EXIT_SUCCESS; } // 打印鏈表 status PrintList(LinkList list) { // list == NULL 鏈表中沒(méi)有節(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ì)無(wú)法打印 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)了,但是還是沒(méi)有到達(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),一開(kāi)始沒(méi)有前一節(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++入門(mén)指南之貪吃蛇游戲的實(shí)現(xiàn)
這篇文章主要給大家介紹了關(guān)于C++入門(mén)指南之貪吃蛇游戲?qū)崿F(xiàn)的相關(guān)資料,文章通過(guò)示例代碼介紹的非常詳細(xì),可以讓大家能短時(shí)間內(nèi)寫(xiě)出一個(gè)貪吃蛇,需要的朋友可以參考下2021-10-10C語(yǔ)言之整數(shù)劃分問(wèn)題(遞歸法)實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言之整數(shù)劃分問(wèn)題(遞歸法)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-02-02C語(yǔ)言數(shù)組元素循環(huán)右移問(wèn)題及解決方法
這篇文章主要介紹了C語(yǔ)言數(shù)組元素循環(huán)右移問(wèn)題,本文通過(guò)多種方法給大家分享解決方案,通過(guò)實(shí)例代碼講解,對(duì)大家的工作或?qū)W習(xí)具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲,附有詳細(xì)代碼,需要的小伙伴可以參考一下,希望對(duì)你的遼西有所幫助2021-10-10VS2019+MPI配置過(guò)程的實(shí)現(xiàn)步驟
本文介紹了在VS2019上配置MPI,包括下載和安裝MPI、創(chuàng)建項(xiàng)目、配置屬性、導(dǎo)入頭文件和庫(kù)文件、添加依賴項(xiàng)等步驟,具有一定的參考價(jià)值,感興趣的可以了解一下2024-12-12