雙向循環(huán)鏈表的創(chuàng)建

雙向循環(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("已初始化鏈表~ ");

return OK;

}

2、遍歷雙向循環(huán)鏈表

注意它的尾節(jié)點(diǎn)的next不再是Null，而是頭節(jié)點(diǎn)

//2、遍歷雙向循環(huán)鏈表

void printfLinkLisk(LinkList list){

printf("遍歷鏈表： ");

if (list == NULL || list->next == list) {

printf("這是一個(gè)空鏈表 ");

return;

}

LinkList p = list;

//判斷next是否全部正確

printf("根據(jù)next從前往后遍歷：");

while (p->next != list) {

printf("%d ",p->next->data);

p = p->next;

}

printf(" ");

//判斷prior是否全部正確

printf("根據(jù)prior從后往前遍歷：");

while (p != list) {

printf("%d ",p->data);

p = p->prior;

}

printf(" ");

}

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) ");

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) ");

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) ");

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(" ");

return 0;

}

輸出結(jié)果：

—END—

審核編輯 ：李倩