目錄

前言

鏈表實現

1.定義節點

2.接口實現

1.開辟新節點

2.初始化

3.打印鏈表

4.添加節點

頭插

尾插

在pos位置之前增加節點

5.刪除節點

判空

頭刪

尾刪

刪除pos位置的節點

6.查找

7.釋放

---

前言

帶頭雙向循環鏈表的結構最復雜，一般用在單獨存儲數據。但是實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了。現在我們看看如何實現。

鏈表實現

1.定義節點

雙向循環鏈表每個節點有兩個指針，一個指向前一個，一個指向下一個。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;

2.接口實現

1.開辟新節點

添加數據的接口都需要開辟新節點，寫一個Buynewnode方便復用。

LTNode* Buynewnode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;}

2.初始化

初始化定義哨兵位頭結點。

LTNode* LTInit()
{LTNode* phead = Buynewnode(-1);phead->next = phead;phead->prev = phead;return phead;
}

3.打印鏈表

void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;printf("guard<==>");while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

4.添加節點

頭插

LTNode* LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = Buynewnode(x);LTNode* first = phead->next;first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead;}

尾插

LTNode* LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = Buynewnode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

在pos位置之前增加節點

//在pos位置之前插入
LTNode* LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = Buynewnode(x);newnode->next = pos;pos->prev = newnode;newnode->prev = prev;prev->next = newnode;
}

頭插和尾插可以復用這段代碼。?

5.刪除節點

判空

當鏈表只剩下頭結點就不能再刪除，所以要判空。

bool JudgeEmpty(LTNode* phead)
{return phead->next == phead;
}

頭刪

LTNode* LTPopFront(LTNode* phead)
{assert(phead);assert(!JudgeEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);
}

尾刪

LTNode* LTPopBack(LTNode* phead)
{assert(phead);assert(!JudgeEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);
}

刪除pos位置的節點

//刪除pos位置的節點
LTNode* LTErase(LTNode* pos)
{assert(pos);LTNode* posnext = pos->next;LTNode* posprev = pos->prev;posnext->prev = posprev;posprev->next = posnext;free(pos);
}

6.查找

LTNode* LTFind(LTDataType x,LTNode* phead)
{LTNode* cur = phead->next;while(cur != phead){cur = cur->next;if (cur->data == x){return cur;}}return NULL;
}

7.釋放

LTNode* LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

上面的代碼有很多指針不太好想，借助畫圖會方便許多！！！?