有時(shí)在解決具體問題時(shí)吠式，需要我們對(duì)鏈表的結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如抽米，可以把鏈表的兩頭連接特占，使其成為了一個(gè)環(huán)狀鏈表，通常稱為循環(huán)鏈表云茸。
和它名字的表意一樣是目，只需要將表中最后一個(gè)節(jié)點(diǎn)的指針指向首元節(jié)點(diǎn)，鏈表就能成環(huán)兒标捺，如圖所示懊纳。
單向循環(huán)鏈表.png
需要注意的是，雖然循環(huán)鏈表成環(huán)狀亡容，但本質(zhì)上還是鏈表嗤疯，因此在循環(huán)鏈表中，依然能夠找到頭指針和首元節(jié)點(diǎn)等闺兢。循環(huán)鏈表和普通鏈表相比茂缚，唯一的不同就是循環(huán)鏈表首尾相連，其他都完全一樣。
以下是自己手敲的C語言單向循環(huán)鏈表
如果有不對(duì)的地方脚囊，歡迎指正帖汞，謝謝～
1、初始化鏈表方法
/*
1凑术、初始化單向循環(huán)鏈表
判斷是否第一次創(chuàng)建鏈表翩蘸，分2種情況:
① YES->創(chuàng)建一個(gè)新節(jié)點(diǎn),并使得新節(jié)點(diǎn)的next 指向自身; (*L)->next = (*L);
② NO-> 找鏈表尾節(jié)點(diǎn),將尾節(jié)點(diǎn)的next = 新節(jié)點(diǎn). 新節(jié)點(diǎn)的next = (*L);
注意：這里需要每次記錄尾節(jié)點(diǎn)，方便插入數(shù)據(jù)
*/
Status InitList(LinkList *list){
LinkList tempNode,lastNode = NULL;
int scanfData;
printf("請(qǐng)輸入要插入的數(shù)據(jù)(輸入比1小的數(shù)退出輸入)：");
while (1) {
scanf("%d",&scanfData);
if (scanfData < 1) {
break;
}
//創(chuàng)建一個(gè)節(jié)點(diǎn)
tempNode = malloc(sizeof(Node));
if (tempNode == NULL) {
return ERROR;
}
tempNode->data = scanfData;
if (*list == NULL) {
//首元節(jié)點(diǎn)插入
*list = tempNode;
tempNode->next = tempNode;
}
else {
//尾節(jié)點(diǎn)插入
tempNode->next = lastNode->next;
lastNode->next = tempNode;
}
//記錄尾節(jié)點(diǎn)
lastNode = tempNode;
}
return OK;
}
2淮逊、遍歷鏈表方法
/*
2催首、遍歷鏈表
循環(huán)鏈表的遍歷最好用do while語句，因?yàn)樾枰茸鲆淮蝡 = p->next泄鹏，判斷p->next等于首元節(jié)點(diǎn)的時(shí)候就是找到尾節(jié)點(diǎn)了
*/
void ListTraverse(LinkList list){
printf("遍歷鏈表：");
LinkList p = list;
if (!p) {
printf("這是一個(gè)空鏈表");
}
else {
do {
printf("%d ",p->data);
p = p->next;
} while (p != list);
}
printf("\n");
}
3郎任、鏈表插入節(jié)點(diǎn)方法
插入數(shù)據(jù)分兩種情況：
-
1、插入位置在首元節(jié)點(diǎn)
插入在首元節(jié)點(diǎn).png -
2备籽、插入位置不在首元節(jié)點(diǎn)舶治，這按普通鏈表插入方式操作即可
插入非首元節(jié)點(diǎn).png
/*
3、鏈表插入數(shù)據(jù)
初始條件:鏈表表List已存在,0≤i≤ListLength(List);
操作結(jié)果：在List中第i個(gè)位置之后插入新的數(shù)據(jù)元素data（i以0開始）
1.插入位置在首元節(jié)點(diǎn)
(1) 創(chuàng)建新節(jié)點(diǎn),并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
(2) 判斷是否空鏈表车猬，是則直接插入霉猛，并賦值*list。不是則找到鏈表的尾節(jié)點(diǎn);
(3) 讓新節(jié)點(diǎn)的next 指向首元節(jié)點(diǎn);
(4) 尾節(jié)點(diǎn)的next 指向新節(jié)點(diǎn);
(5) 讓頭指針指向新節(jié)點(diǎn).
2.如果插入的位置在其他位置;
(1) 創(chuàng)建新節(jié)點(diǎn),并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
(2) 先找到插入的位置,如果超過鏈表長(zhǎng)度,則自動(dòng)插入隊(duì)尾;
(3) 通過locaNode找到要插入位置的前一個(gè)節(jié)點(diǎn);
(4) 新節(jié)點(diǎn)的next 指向locaNode原來的next位置, 然后讓locaNode->next = 新節(jié)點(diǎn).
*/
Status ListInsert(LinkList *list, int index, ElemType data){
LinkList p = malloc(sizeof(Node));
if (p == NULL) {
return ERROR;
}
p->data = data;
if (index == 0) {
//插入的是首元節(jié)點(diǎn)
if (*list == NULL) {
p->next = p;
}
else {
//找到尾節(jié)點(diǎn)
LinkList lastNode = *list;
while (lastNode->next != *list) {
lastNode = lastNode->next;
}
p->next = lastNode->next;
lastNode->next = p;
}
*list = p;
}
else {
LinkList locaNode = *list;
for (int i = 1; i < index && locaNode->next != *list; i++) {
locaNode = locaNode->next;
}
//插入數(shù)據(jù)
p->next = locaNode->next;
locaNode->next = p;
}
return OK;
}
4珠闰、鏈表刪除節(jié)點(diǎn)方法
刪除數(shù)據(jù)分兩種情況：
- 1惜浅、刪除首元節(jié)點(diǎn)
- 2、刪除非首元節(jié)點(diǎn)
/*
4伏嗜、循環(huán)鏈表刪除元素
初始條件：鏈表L已存在坛悉，1≤i≤ListLength(List)
操作結(jié)果：刪除List的第i個(gè)數(shù)據(jù)元素（i以0為起始位置）
1.刪除首元節(jié)點(diǎn)
(1) 判斷是否只有一個(gè)節(jié)點(diǎn)，是則直接刪除;
(2) 找到鏈表的尾節(jié)點(diǎn)承绸，使得尾節(jié)點(diǎn)next 指首元節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn);
(3) 把新節(jié)點(diǎn)做為首元節(jié)點(diǎn),然后釋放原來的首元節(jié)點(diǎn);
2.刪除非首元節(jié)點(diǎn)
(1) 找到刪除節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)previousNode裸影，和當(dāng)前節(jié)點(diǎn)locaNode
(2) 使得previousNode->next 指向locaNode->next
(3) 釋放需要?jiǎng)h除的節(jié)點(diǎn)locaNode
*/
Status ListDelete(LinkList *list, int index){
if (*list == NULL) {
return ERROR;
}
if (index == 0) {
//刪除首元節(jié)點(diǎn)
if ((*list)->next == *list) {
(*list)->next = NULL;
free(*list);
*list = NULL;
}
//1、找到尾節(jié)點(diǎn)
LinkList lastNode;
for (lastNode = *list; lastNode->next != *list; lastNode = lastNode->next);
LinkList p = *list;
lastNode->next = p->next;
*list = p->next;
free(p);
}
else {
LinkList previousNode = *list;
int I;
for (i = 1; i < index && previousNode->next != *list; i++) {
previousNode = previousNode->next;
}
if (i == index) {
LinkList locaNode = previousNode->next;
previousNode->next = locaNode->next;
free(locaNode);
}
else {
return ERROR;
}
}
return OK;
}
5军熏、鏈表取值方法
//5轩猩、單鏈表取值
/*
初始條件: 順序線性表List已存在,1≤i≤ListLength(List);
操作結(jié)果：用data返回List中第i個(gè)數(shù)據(jù)元素的值
*/
Status GetElem(LinkList list, int index, ElemType *data){
LinkList p = list;
int i = 0;
//當(dāng)尾節(jié)點(diǎn)指向首元節(jié)點(diǎn)就會(huì)直接跳出循環(huán)
while (p && i < index && p->next != list) {
p = p->next;
I++;
}
if (i != index || !p) {
return ERROR;
}
*data = p->data;
return OK;
}
6、清空單向循環(huán)鏈表方法
//6羞迷、清空鏈表
/* 初始條件：順序線性表List已存在界轩。操作結(jié)果：將List重置為空表 */
void ClearList(LinkList *list){
LinkList p,q;
for (p = *list; p->next != *list; p = p->next);
p->next = NULL;
p = *list;
while (p) {
q = p->next;
free(p);
p = q;
}
*list = NULL;
}
7画饥、類定義和main方法
#define OK 1
#define ERROR 0
#define S_TRUE 1
#define S_FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
int main(int argc, const char * argv[]) {
//初始化
LinkList list;
printf("初始化鏈表\n");
InitList(&list);
//遍歷數(shù)據(jù)
ListTraverse(list);
//插入數(shù)據(jù)
int insertIndex;
ElemType insertData;
while (1) {
printf("輸入要插入的位置和數(shù)據(jù)用空格隔開(數(shù)據(jù)小于1則結(jié)束輸入)：");
scanf("%d %d",&insertIndex,&insertData);
if (insertData < 1) {
break;
}
ListInsert(&list, insertIndex, insertData);
printf("插入數(shù)據(jù)后 ");
ListTraverse(list);
}
//刪除數(shù)據(jù)
ListDelete(&list, 3);
printf("刪除第3個(gè)元素：\n");
ListTraverse(list);
//取出數(shù)據(jù)
ElemType data;
GetElem(list, 3, &data);
printf("取出第3個(gè)數(shù)：%d\n",data);
// //清空鏈表
ClearList(&list);
printf("清空鏈表\n");
ListTraverse(list);
printf("\n");
return 0;
}
根據(jù)此代碼實(shí)現(xiàn)的約瑟夫環(huán)地址：http://www.reibang.com/p/d8b65de0ef1f
