雙向循環(huán)鏈表
定義
雙向循環(huán)鏈表和它名字的表意一樣，就是把雙向鏈表的兩頭連接，使其成為了一個(gè)環(huán)狀鏈表。只需要將表中最后一個(gè)節(jié)點(diǎn)的next指針指向頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的prior指針指向尾節(jié)點(diǎn)，鏈表就能成環(huán)兒，如圖所示：
需要注意的是，雖然雙向循環(huán)鏈表成環(huán)狀，但本質(zhì)上還是雙向鏈表，因此在雙向循環(huán)鏈表中，依然能夠找到頭指針和頭節(jié)點(diǎn)等。雙向循環(huán)鏈表和雙向鏈表相比，唯一的不同就是雙向循環(huán)鏈表首尾相連，其他都完全一樣。
注意：因?yàn)槲疑厦嬉呀?jīng)講了雙向鏈表，所以這里只注重講他們的實(shí)現(xiàn)差異。另因?yàn)閹ь^節(jié)點(diǎn)會(huì)更好操作，所以我的代碼都有頭節(jié)點(diǎn)。
1、雙向循環(huán)鏈表的創(chuàng)建
初始化時(shí)需要將頭節(jié)點(diǎn)的next和prior都指向自己。
//1、初始化雙向循環(huán)鏈表（帶頭節(jié)點(diǎn)）
Status initLinkList(LinkList *list){
? ? //創(chuàng)建頭節(jié)點(diǎn)
? ? *list = malloc(sizeof(Node));
? ? if (*list == NULL) {
? ? ? ? return ERROR;
? ? }
? ? //前驅(qū)和后繼都指向自己
? ? (*list)->prior = *list;
? ? (*list)->data = -1;
? ? (*list)->next = *list;
? ? printf("已初始化鏈表~\n");
? ? return OK;
}
2、遍歷雙向循環(huán)鏈表
注意它的尾節(jié)點(diǎn)的next不再是Null，而是頭節(jié)點(diǎn)
//2、遍歷雙向循環(huán)鏈表
void printfLinkLisk(LinkList list){
? ? printf("遍歷鏈表：\n");
? ? if (list == NULL || list->next == list) {
? ? ? ? printf("這是一個(gè)空鏈表\n");
? ? ? ? return;
? ? }
? ? LinkList p = list;
? ? //判斷next是否全部正確
? ? printf("根據(jù)next從前往后遍歷：");
? ? while (p->next != list) {
? ? ? ? printf("%d ",p->next->data);
? ? ? ? p = p->next;
? ? }
? ? printf("\n");
? ? //判斷prior是否全部正確
? ? printf("根據(jù)prior從后往前遍歷：");
? ? while (p != list) {
? ? ? ? printf("%d ",p->data);
? ? ? ? p = p->prior;
? ? }
? ? printf("\n");
}
3、根據(jù)索引位置添加節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)。
//3、根據(jù)索引位置插入數(shù)據(jù)至鏈表中
Status insertLinkList(LinkList *list, int index, ElemType data){
? ? if (list == NULL || index < 0) {
? ? ? ? return ERROR;
? ? }
? ? int i = 0;
? ? LinkList priorNode = *list;
? ? //判斷插入的位置，這里開始位置是0，index超過鏈表長(zhǎng)度則插入末尾
? ? while (i < index && priorNode->next != *list) {
? ? ? ? priorNode = priorNode->next;
? ? ? ? i++;
? ? }
? ? LinkList newNode = malloc(sizeof(Node));
? ? if (newNode == NULL) {
? ? ? ? return ERROR;
? ? }
? ? newNode->data = data;
? ? //插入操作共四步，看好了，別眨眼
? ? //1.將priorNode->next節(jié)點(diǎn)的前驅(qū)指向新節(jié)點(diǎn)
? ? priorNode->next->prior = newNode;
? ? //2.將新節(jié)點(diǎn)->next指向原來的priorNode->next
? ? newNode->next = priorNode->next;
? ? //3.將priorNode->next指向新節(jié)點(diǎn)
? ? priorNode->next = newNode;
? ? //4.新節(jié)點(diǎn)的前驅(qū)指向priorNode
? ? newNode->prior = priorNode;
? ? return OK;
}
4、根據(jù)索引位置刪除節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)。
//4、根據(jù)索引位置刪除節(jié)點(diǎn)
Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){
? ? if (*list == NULL || index < 0) {
? ? ? ? return ERROR;
? ? }
? ? LinkList locaNode = *list;
? ? int i = 0;
? ? //注意別刪了頭節(jié)點(diǎn)
? ? while (i <= index) {
? ? ? ? locaNode = locaNode->next;
? ? ? ? if (locaNode == *list) {
? ? ? ? ? ? printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
? ? ? ? ? ? return ERROR;
? ? ? ? }
? ? ? ? i++;
? ? }
? ? //開始刪除，只需要做兩步
? ? locaNode->prior->next = locaNode->next;
? ? locaNode->next->prior = locaNode->prior;
? ? *data = locaNode->data;
? ? free(locaNode);
? ? return OK;
}
5、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)。
//5、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
Status deleteLinkListByData(LinkList *list, ElemType data){
? ? if (*list == NULL) {
? ? ? ? return ERROR;
? ? }
? ? LinkList locaNode = (*list)->next;
? ? while (locaNode != *list) {
? ? ? ? if (locaNode->data == data) {
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? locaNode = locaNode->next;
? ? }
? ? if (locaNode == *list) {
? ? ? ? printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
? ? ? ? return ERROR;
? ? }
? ? //開始刪除，只需要做兩步
? ? locaNode->prior->next = locaNode->next;
? ? locaNode->next->prior = locaNode->prior;
? ? free(locaNode);
? ? return OK;
}
6、根據(jù)值查找節(jié)點(diǎn)
尾節(jié)點(diǎn)的next可是頭節(jié)點(diǎn)哦，找到它就是最后一個(gè)了。
//6、查找元素
Status selectNode(LinkList list, ElemType data, LinkList *locaNode){
? ? if (list == NULL) {
? ? ? ? return ERROR;
? ? }
? ? LinkList p = list->next;
? ? while (p != list) {
? ? ? ? if (p->data == data) {
? ? ? ? ? ? *locaNode = p;
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? p = p->next;
? ? }
? ? if (*locaNode == NULL) {
? ? ? ? printf("沒有這個(gè)你想要的節(jié)點(diǎn)\n");
? ? ? ? return ERROR;
? ? }
? ? else {
? ? ? ? return OK;
? ? }
}
其它輔助代碼
#include "stdlib.h"
#define OK? ? 1
#define ERROR 0
//元素類型
typedef int ElemType;
//狀態(tài)類型
typedef int Status;
//定義節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node {
? ? struct Node *prior;
? ? ElemType data;
? ? struct Node *next;
} Node;
typedef Node *LinkList;
int main(int argc, const char * argv[]) {
? ? LinkList list;
? ? initLinkList(&list);
? ? for (int i = 0; i < 10; i ++) {
? ? ? ? insertLinkList(&list, i, i);
? ? }
? ? printfLinkLisk(list);
? ? int index, data;
? ? printf("輸入你想插入的位置（從0開始）和存儲(chǔ)的值:");
? ? scanf("%d %d",&index,&data);
? ? insertLinkList(&list, index, data);
? ? printfLinkLisk(list);
? ? printf("輸入你想刪除的位置（從0開始）:");
? ? scanf("%d",&index);
? ? deleteLinkListByIndex(&list, index, &data);
? ? printfLinkLisk(list);
? ? printf("輸入你想刪除的節(jié)點(diǎn)的值（只刪最前的那個(gè)）:");
? ? scanf("%d",&data);
? ? deleteLinkListByData(&list, data);
? ? printfLinkLisk(list);
? ? printf("\n");
? ? return 0;
}
輸出結(jié)果：
—END—
看到這里是不是又學(xué)到了很多新知識(shí)呢~
如果你很想學(xué)編程，小編推薦我專欄的C語(yǔ)言/C++編程學(xué)習(xí)基地【點(diǎn)擊進(jìn)入】！
都是學(xué)編程小伙伴們，帶你入個(gè)門還是簡(jiǎn)簡(jiǎn)單單啦，一起學(xué)習(xí)，一起加油~
還有許多學(xué)習(xí)資料和視頻，相信你會(huì)喜歡的！
涉及：游戲開發(fā)、常用軟件開發(fā)、編程基礎(chǔ)知識(shí)、課程設(shè)計(jì)、黑客等等......
