一、帶頭結(jié)點的循環(huán)雙向鏈表
二、結(jié)點與接口定義
結(jié)點定義：
typedef int ListDataType;
typedef struct LinkedListNode
{
struct LinkedListNode* next;
struct LinkedListNode* prev;
ListDataType data;
}LinkedListNode;
接口定義：
LinkedListNode* LinkedListInit();
void LinkedListPrint(LinkedListNode* phead);
bool LinkedListEmpty(LinkedListNode* phead);
void LinkedListPushBack(LinkedListNode* phead, ListDataType x);
void LinkedListPushFront(LinkedListNode* phead, ListDataType x);
void LinkedListPopBack(LinkedListNode* phead);
void LinkedListPopFront(LinkedListNode* phead);
LinkedListNode* LinkedListFind(LinkedListNode* phead, ListDataType x);
// 在pos之前插入
void LinkedListInsert(LinkedListNode* pos, ListDataType x);
// 刪除pos位置的值
void LinkedListErase(LinkedListNode* pos);
void LinkedListDestroy(LinkedListNode* phead);
三、實現(xiàn)
3.1 申請節(jié)點
我們將申請結(jié)點的代碼封裝成函數(shù)，方便后續(xù)使用
LinkedListNode* CreateLinkedListNode(ListDataType x)
{
LinkedListNode* newnode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
3.2 初始化
由于是帶頭結(jié)點的雙向鏈表，因此在使用鏈表前，我們需要對鏈表進行初始化。
LinkedListNode* LinkedListInit()
{
LinkedListNode* phead = CreateLinkedListNode(230510);
phead->next = phead;
phead->prev = phead;
return phead;
}
3.3 打印
遍歷鏈表，值得說的是，帶頭結(jié)點的雙向鏈表的循環(huán)結(jié)束條件是 cur != phead
void LinkedListPrint(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* cur = phead->next;
printf("guard<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
3.4 尾插
尾插時，需要先找到尾結(jié)點，然后將新結(jié)點插入到尾結(jié)點后面。
void LinkedListPushBack(LinkedListNode* phead, ListDataType x)
{
assert(phead);
// 1.找到尾結(jié)點
LinkedListNode* tail = phead->prev;
// 2.插入到尾結(jié)點后面
LinkedListNode* newnode = CreateLinkedListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
3.5 頭插
第一種寫法，要注意現(xiàn)將newnode后面的結(jié)點進行鏈接，然后再講newnode鏈接到phead后面。
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* newnode = CreateLinkedListNode(x);
// 與原來的第一個數(shù)據(jù)結(jié)點鏈接
newnode->next = phead->next;
phead->next->prev = newnode; // newnode->next->prev = newnode;
// newnode變?yōu)樾碌牡谝粋€數(shù)據(jù)結(jié)點
phead->next = newnode;
newnode->prev = phead;
}
第二種寫法（推薦寫法），我們使用變量記錄phead的next，記為first，這樣newnode插入到phead和first之間，這樣邏輯比較清楚。
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* newnode = CreateLinkedListNode(x);
// 用變量記錄第一個結(jié)點
LinkedListNode* first = phead->next;
// 與原來的第一個數(shù)據(jù)結(jié)點鏈接
newnode->next = first;
first->prev = newnode;
// newnode變?yōu)樾碌牡谝粋€數(shù)據(jù)結(jié)點
phead->next = newnode;
newnode->prev = phead;
}
3.6 尾刪
phead的prev是尾tail，tail的prev是tailPrev。
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* tail = phead->prev;
LinkedListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
上面代碼的問題是鏈表為空的情況報錯，于是我們在該函數(shù)內(nèi)部對空鏈表進行斷言：
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 刪除時鏈表不能為空
LinkedListNode* tail = phead->prev;
LinkedListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
3.7 判斷鏈表為空斷言
判斷鏈表為空邏輯：
bool LinkedListEmpty(LinkedListNode* phead)
{
assert(phead);
return phead->next == phead;
}
使用鏈表為空的斷言：
assert(!LinkedListEmpty(phead)); // 鏈表為空時error
3.8 頭刪
頭刪時需要將第一個結(jié)點刪除，很容易便想到以下代碼：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 刪除時鏈表不能為空
LinkedListNode* next = phead->next;
phead->next = next->next;
phead->next->prev = phead; // next->next->prev = phead;
free(next);
}
為了提高可讀性，推薦使用以下代碼，定義first和second兩個變量指向第一個和第二個：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 刪除時鏈表不能為空
LinkedListNode* first = phead->next;
LinkedListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}
3.9 查找find
查找的本質(zhì)就是遍歷鏈表
LinkedListNode* LinkedListFind(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
3.10 插入insert-在pos之前插入
pos的來源一般是find的結(jié)果
void LinkedListInsert(LinkedListNode* pos, ListDataType x)
{
assert(pos);
LinkedListNode* prev = pos->prev;
LinkedListNode* newnode = CreateLinkedListNode(x);
// prev newnode pos
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
3.11 頭插尾插復(fù)用insert
有了上面的insert在任意位置插入，我們可以修改尾插代碼：
void LinkedListPushBack(LinkedListNode* phead, ListDataType x)
{
assert(phead);
// 在phead之前插入，也就是尾插
LinkedListInsert(phead, x);
}
同理也可以修改頭插代碼：
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListInsert(phead->next, x);
}
3.12 刪除erase-刪除pos位置
同insert一樣，pos也應(yīng)該是調(diào)用者通過find返回的結(jié)果。
void LinkedListErase(LinkedListNode* pos)
{
assert(pos);
LinkedListNode* posPrev = pos->prev;
LinkedListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
3.13 頭刪尾刪復(fù)用erase
有了上面的erase在任意位置刪除，我們可以修改尾刪的代碼：
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead));
LinkedListErase(phead->prev);
}
同理也可以修改頭刪的代碼：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead));
LinkedListErase(phead->next);
}
3.14 銷毀destroy
記得釋放頭結(jié)點phead：
void LinkedListDestroy(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* cur = phead->next;
while (cur != phead)
{
LinkedListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
源碼
gitee-LinkedList
總結(jié)
帶頭結(jié)點、雙向、循環(huán)鏈表的實現(xiàn)都非常的簡單，需要注意判空條件與遍歷終止的條件。文章來源：http://www.zghlxwxcb.cn/news/detail-438544.html
在代碼寫法上，對于某個節(jié)點的前一個或后一個的問題，我們最好分別使用變量去記錄，這樣代碼的邏輯更清晰，可讀性更高。例如尾插時的tail，尾刪時的tail和tailPrev，以及頭刪時的first與second，erase中的posPrev與posNext，這些變量的使用，提高了代碼的可讀性。文章來源地址http://www.zghlxwxcb.cn/news/detail-438544.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】C語言實現(xiàn)雙向鏈表（帶頭結(jié)點、循環(huán)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
