鏈表的分類

鏈表的結(jié)構(gòu)?常多樣，以下情況組合起來就有8種（2 x?2?x?2）鏈表結(jié)構(gòu)：

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實際中最常?還是兩種結(jié)構(gòu)：單鏈表和雙向帶頭循環(huán)鏈表

1.?頭單向?循環(huán)鏈表：結(jié)構(gòu)簡單，?般不會單獨?來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的?結(jié)構(gòu)，如哈希表、圖的鄰接表等等。

2.帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，?般?在單獨存儲數(shù)據(jù)。實際中使?的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使?代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反?簡單了。

雙向鏈表

概念與結(jié)構(gòu)

注意：這?的“帶頭”跟前?我們說的“頭結(jié)點”是兩個概念，實際前?的在單鏈表階段稱呼不嚴(yán)謹(jǐn)，但是為了同學(xué)們更好的理解就直接稱為單鏈表的頭結(jié)點。

帶頭鏈表?的頭結(jié)點，實際為“哨兵位”，哨兵位結(jié)點不存儲任何有效元素，只是站在這?“放哨 的”

鏈表的實現(xiàn)

首先我們來看看它的具體聲明，用一個頭文件來簡述：

//定義雙向鏈表節(jié)點的結(jié)構(gòu)
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//為了保持接口的一致性，優(yōu)化接口都為一級指針
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//銷毀
void LTDesTroy(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//傳一級，需要手動將plist置為NULLvoid LTPrint(LTNode* phead);//插入
//第一個參傳一級還是二級，要看pphead指向的節(jié)點會不會發(fā)生改變
//如果發(fā)生改變，那么pphead的改變要影響實參，傳二級
//如何不發(fā)生改變，pphead不會影響實參，傳一級
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//刪除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);bool LTEmpty(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入節(jié)點
void LTInsert(LTNode* pos, LTDataType x);
//刪除指定位置節(jié)點
void LTErase(LTNode* pos);

接下來我們創(chuàng)建一個List.c文件來一一實現(xiàn)上述聲明：

新結(jié)點的創(chuàng)建：

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;//prev nextnewnode->next = newnode->prev = newnode;return newnode;
}

結(jié)點的初始化：

//初始化
//void LTInit(LTNode** pphead)
//{
//	//創(chuàng)建一個頭結(jié)點（哨兵位）
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

尾插與頭插：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode  phead->next(d1)newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

打印與置空：

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

尾刪與頭刪：

尾刪示意圖：

頭刪示意圖：

//尾刪
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead  prev(del->prev)  del(phead->prev) LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead  del(phead->next)  del->nextLTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

查找指定結(jié)點：

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

在指定結(jié)點之后插入結(jié)點：

示意圖：

//在pos位置之后插入節(jié)點
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

刪除指定位置結(jié)點：

示意圖：（本處就d2、d3兩處結(jié)點分別討論刪除后的next與prev指針指向）

//刪除指定位置節(jié)點
void LTErase(LTNode* pos)
{assert(pos);// pos->prev  pos   pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

銷毀鏈表：

示意圖：

//銷毀
void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}//銷毀哨兵位結(jié)點free(*pphead);*pphead = NULL;pcur = NULL;
}
//優(yōu)化代碼
void LTDesTroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);phead = pcur = NULL;
}

---

總結(jié)

學(xué)完了順序表與鏈表，相信大家或多或少對線性表有了自己的看法，下面我們來就順序表與鏈表做一個簡單的比較：

總的來說，順序表與鏈表沒有優(yōu)劣之分，存在即合理。它們在解決我們不同問題的過程中都有著重要的作用。以上便是本期的分享，感謝您的觀看！