循環(huán)雙鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種址儒，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)衅疙。所以莲趣，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)饱溢。一般我們都構(gòu)造雙向循環(huán)鏈表喧伞。
結(jié)點(diǎn)結(jié)構(gòu)
空鏈
0.數(shù)據(jù)結(jié)構(gòu)聲明
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElementType;/* ElementType類型根據(jù)實(shí)際情況而定绩郎，這里假設(shè)為int */
//定義結(jié)點(diǎn)
typedef struct Node{
ElementType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * DoublyCycleLinkedList;
1.初始化
Status InitLinkList(DoublyCycleLinkedList *list){
*list = (DoublyCycleLinkedList)malloc(sizeof(Node));
if (*list == NULL) {
return ERROR;
}
(*list)->next = (*list);
(*list)->prior = (*list);
//新增數(shù)據(jù)
DoublyCycleLinkedList p = *list;
for(int i=0; i < 10;i++){
//1.創(chuàng)建1個(gè)臨時(shí)的結(jié)點(diǎn)
DoublyCycleLinkedList temp = (DoublyCycleLinkedList)malloc(sizeof(Node));
temp->data = i;
//2.為新增的結(jié)點(diǎn)建立雙向鏈表關(guān)系
//① temp 是p的后繼
p->next = temp;
//② temp 的前驅(qū)是p
temp->prior = p;
//③ temp的后繼是*list
temp->next = (*list);
//④ 頭結(jié)點(diǎn)的前驅(qū)指向新建的temp
(*list)->prior = temp;
//⑤ p 要記錄最后的結(jié)點(diǎn)的位置,方便下一次插入
p = p->next;
}
return OK;
}
DoublyCycleLinkedList list;
ElementType temp,item;
InitLinkList(&list);
2.遍歷
Status Description(DoublyCycleLinkedList list){
if (list == NULL) {
printf("打印的雙向循環(huán)鏈表為空!\n\n");
return ERROR;
}
printf("雙向循環(huán)鏈表內(nèi)容: ");
DoublyCycleLinkedList p = list->next;
while (p != list) {
printf("%d ",p->data);
p = p->next;
}
printf("\n\n");
return OK;
}
Description(list);
3.插入結(jié)點(diǎn)
約定：當(dāng)插入位置超過(guò)鏈表長(zhǎng)度則插入到鏈表末尾
Status LinkListInsert(DoublyCycleLinkedList *list, int index, ElementType data){
//1. 創(chuàng)建指針p,指向雙向鏈表頭
DoublyCycleLinkedList p = (*list);
int i = 1;
//2.雙向循環(huán)鏈表為空,則返回error
if(*list == NULL) return ERROR;
//3.找到插入前一個(gè)位置上的結(jié)點(diǎn)p
while (i < index && p->next != *list) {
p = p->next;
i++;
}
//4.如果i>index 則返回error
if (i > index) return ERROR;
//5.創(chuàng)建新結(jié)點(diǎn)temp
DoublyCycleLinkedList temp = (DoublyCycleLinkedList)malloc(sizeof(Node));
//6.temp 結(jié)點(diǎn)為空,則返回error
if (temp == NULL) return ERROR;
//7.將生成的新結(jié)點(diǎn)temp數(shù)據(jù)域賦值e.
temp->data = data;
//8.將結(jié)點(diǎn)temp 的前驅(qū)結(jié)點(diǎn)為p;
temp->prior = p;
//9.temp的后繼結(jié)點(diǎn)指向p->next;
temp->next = p->next;
//10.p的后繼結(jié)點(diǎn)為新結(jié)點(diǎn)temp;
p->next = temp;
//如果temp 結(jié)點(diǎn)不是最后一個(gè)結(jié)點(diǎn)
if (*list != temp->next) {
//11.temp節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的前驅(qū)為temp 結(jié)點(diǎn)
temp->next->prior = temp;
}else{
(*list)->prior = temp;
}
return OK;
}
printf("輸入要插入的位置和數(shù)據(jù)用空格隔開(kāi)：");
scanf("%d %d",&temp,&item);
LinkListInsert(&list,temp,item);
Description(list);
4.刪除結(jié)點(diǎn)
/**
循環(huán)雙鏈表刪除結(jié)點(diǎn)
@param list 實(shí)例
@param index 位置
@param data 數(shù)據(jù)
@return 狀態(tài)
*/
Status LinkListRemove(DoublyCycleLinkedList *list,int index,ElementType *data){
int i = 1;
DoublyCycleLinkedList temp = (*list)->next;
if (*list == NULL) {
return ERROR;
}
//①.如果刪除到只剩下首元結(jié)點(diǎn)了,則直接將*list置空;
if(temp->next == *list){
free(*list);
(*list) = NULL;
return OK;
}
//1.找到要?jiǎng)h除的結(jié)點(diǎn)
while (i < index) {
temp = temp->next;
if (temp != *list){
i++;
}
}
//2.給e賦值要?jiǎng)h除結(jié)點(diǎn)的數(shù)據(jù)域
*data = temp->data;
//3.修改被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼指針
temp->prior->next = temp->next;
//4.修改被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)指針
temp->next->prior = temp->prior;
//5. 刪除結(jié)點(diǎn)temp
free(temp);
return OK;
}
printf("輸入要?jiǎng)h除位置：");
scanf("%d",&temp);
LinkListRemove(&list, temp, &item);
printf("刪除鏈表位置為%d,結(jié)點(diǎn)數(shù)據(jù)域?yàn)?%d\n",temp,item);
Description(list);