上篇文章簡(jiǎn)述講解了鏈表的基本概念并且實(shí)現(xiàn)了無(wú)頭單向不循環(huán)鏈表：鏈接未來(lái)：深入理解鏈表數(shù)據(jù)結(jié)構(gòu)（一.c語(yǔ)言實(shí)現(xiàn)無(wú)頭單向非循環(huán)鏈表）-CSDN博客
那今天接著給大家?guī)?lái)帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)：
一.項(xiàng)目文件規(guī)劃
- 頭文件DoubleList.h:用來(lái)基礎(chǔ)準(zhǔn)備（常量定義，typedef），鏈表表的基本框架，函數(shù)的聲明
- 源文件DoubleList.h:用來(lái)各種功能函數(shù)的具體實(shí)現(xiàn)
- 源文件test.c:用來(lái)測(cè)試功能是否有問(wèn)題，進(jìn)行基本功能的使用
二.基本結(jié)構(gòu)及功能一覽(DoubleList.h)
結(jié)構(gòu)體定義
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;//下一個(gè)節(jié)點(diǎn)
struct ListNode* prev;//上一個(gè)節(jié)點(diǎn)
LTDataType val;//數(shù)據(jù)
}LTNode;
接口功能一覽
LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印數(shù)據(jù)
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾刪
void LTPushFront(LTNode* phead, LTDataType x);//頭插
void LTPopFront(LTNode* phead);//頭刪
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//在pos前插入
void LTErase(LTNode* pos);//刪除pos
void LTDestroy(LTNode* phead);//銷毀
三.各功能接口具體實(shí)現(xiàn)
1.創(chuàng)建節(jié)點(diǎn)
因?yàn)楹竺嫖膊澹^插，插入，初始化都要用到創(chuàng)建新節(jié)點(diǎn)，所以抽出來(lái)作為一個(gè)函數(shù)
LTNode* CreateLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//動(dòng)態(tài)開(kāi)辟
if (newnode == NULL)
{
perror("malloc");
return -1;
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
2.初始化
1.第一種：返回動(dòng)態(tài)開(kāi)辟的地址（不會(huì)銷毀）
LTNode* LTInit()
{
LTNode* a =CreateLTNode(-1);
a->next = a;//一開(kāi)始一個(gè)節(jié)點(diǎn)時(shí)，下一個(gè)和上一個(gè)都指向自己
a->prev = a;//
return a;
}
2.第二種：傳入二級(jí)指針（要直接改變頭節(jié)點(diǎn)的值）
void LTInit(LTNode** pphead)
{
*pphead = CreateLTNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
這兩種皆可
3.打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;//頭結(jié)點(diǎn)數(shù)據(jù)無(wú)效，不需要打印
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
4.尾插
void LTPushBack(LTNode* phead, LTDataType x)//無(wú)有效節(jié)點(diǎn)也適用
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
LTNode* tail = phead->prev;
// phead tail newnode 位置展示
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
5.尾刪
void LTPopBack(LTNode* phead)//只有一個(gè)有效節(jié)點(diǎn)也適用
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* pretail = tail->prev;
// phead pretail tail 位置展示
free(tail);
tail = NULL;
phead->prev = pretail;
pretail->next = phead;
}
6.頭插
void LTPushFront(LTNode* phead, LTDataType x)//無(wú)有效節(jié)點(diǎn)也適用
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
//phead newnode firest tail 位置展示
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}
7.頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);//只有哨兵位時(shí)不能刪
LTNode* first = phead->next;
LTNode* second = first->next;
//phead first second tail 位置展示
free(first);
first = NULL;
phead->next = second;
second->prev = phead;
}
8.查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);//只有哨兵位時(shí)沒(méi)必要查
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.插入pos前
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = CreateLTNode(x);
LTNode* pre = pos->prev;
//pre newnode pos tail 位置展示
pre->next = newnode;
newnode->prev = pre;
newnode->next = pos;
pos->prev = newnode;
}
- 將前一個(gè)節(jié)點(diǎn)
pre的next指針指向新節(jié)點(diǎn)newnode- 將新節(jié)點(diǎn)
newnode的prev指針指向前一個(gè)節(jié)點(diǎn)pre- 將新節(jié)點(diǎn)
newnode的next指針指向指定節(jié)點(diǎn)pos- 將指定節(jié)點(diǎn)
pos的prev指針指向新節(jié)點(diǎn)newnode
10.刪除pos位置
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* pre = pos->prev;
LTNode* next = pos->next;
//pre pos next tail 位置展示
pre->next = next;
next->prev = pre;
free(pos);
pos = NULL;
}
11.銷毀
因?yàn)槊總€(gè)節(jié)點(diǎn)時(shí)malloc動(dòng)態(tài)開(kāi)辟出來(lái)的，要把每個(gè)節(jié)點(diǎn)都依次銷毀文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-794604.html
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur->next != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
四.利用插入和刪除改變“兩插兩刪”（快速寫(xiě)出鏈表）
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);//尾插就是在phead前插入
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);//頭插就是插入到phead的下一個(gè)
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTErase(phead->next);
}
那這次就先到這里啦！兩種常見(jiàn)的鏈表都已經(jīng)實(shí)現(xiàn)完畢，接下來(lái)大概率是棧和隊(duì)列了，感謝大家支持文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-794604.html
到了這里，關(guān)于鏈接未來(lái)：深入理解鏈表數(shù)據(jù)結(jié)構(gòu)（二.c語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
