C語言線性表之雙鏈表詳解
定義
鏈表是通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素，每一個(gè)結(jié)點(diǎn)包含兩個(gè)域：存放數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存放其后繼元素地址的域稱為指針域。因此n個(gè)元素的線性表通過每個(gè)結(jié)點(diǎn)的指針域連接成了一個(gè)“鏈條”，稱為鏈表。若此鏈表的每個(gè)結(jié)點(diǎn)中包含兩個(gè)指針域，則被稱為雙鏈表。
雙鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：
typedef struct node
{
DataType data;
struct node *llink;
struct node *rlink;
} DLinkList;像單鏈表一樣，需要一個(gè)類似于“頭結(jié)點(diǎn)”一樣的結(jié)點(diǎn)（記為rear），其數(shù)據(jù)域?yàn)榭眨羔樣虻?strong>llink指針指向表頭結(jié)點(diǎn)，rlink指針指向表尾結(jié)點(diǎn)。而表頭結(jié)點(diǎn)的llink指針指向NULL，表尾結(jié)點(diǎn)的rlink指針指向NULL。
1.刪除
假設(shè)結(jié)點(diǎn)p是待刪除結(jié)點(diǎn)，我們只需讓p的前一個(gè)結(jié)點(diǎn)的rlink指針（p->llink->rlink）指向p的后一個(gè)結(jié)點(diǎn)（p->rlink)，并讓p的后一個(gè)結(jié)點(diǎn)的llink指針（p->rlink->llink）指向p的前一個(gè)指針（p->llink），然后釋放p所占內(nèi)存空間，即可完成刪除操作。因?yàn)檫@是雙鏈表的刪除算法，因此待刪除結(jié)點(diǎn)在表頭或表尾會(huì)有略微的區(qū)別，但只要抓住核心算法：
p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p);
再對(duì)表頭表尾結(jié)點(diǎn)進(jìn)行特殊處理（改變r(jià)ear指針的指針域）即可。
雙鏈表刪除算法示例如下：
int DeleteDLinkList(DLinkList *rear, DLinkList *p)
/*在雙鏈表刪除結(jié)點(diǎn)p，成功返回1，否則返回0*/
{
DLinkList *q = p->rlink, *s = p->llink;/*q指向p的后繼，s指向p的前繼*/
if (s!=NULL && q==NULL)/*刪除的是最后一個(gè)結(jié)點(diǎn)*/
{
rear->rlink = p->llink;
p->llink->rlink = p->rlink;
free(p);
return 1;
}
if (s==NULL && q!=NULL)/*刪除的是第一個(gè)結(jié)點(diǎn)*/
{
rear->llink = p->rlink;
p->rlink->llink = p->llink;
free(p);
return 1;
}
if (s==NULL & q==NULL)/*雙鏈表只有一個(gè)結(jié)點(diǎn)*/
{
rear->rlink = rear->llink = NULL;
free(p);
return 1;
}
if (s!=NULL && q!=NULL)
{
p->llink->rlink = p->rlink;
p->rlink->llink = p->llink;
free(p);
return 1;
}
return 0;
}2.插入
假設(shè)要把結(jié)點(diǎn)q插入到結(jié)點(diǎn)p與p的后一個(gè)結(jié)點(diǎn)之間，需要①先令q的llink指針（q->llink）和rlink指針（q->rlink）分別指向p和p的后一個(gè)結(jié)點(diǎn)（p->rlink），②再令p的后一個(gè)結(jié)點(diǎn)的llink指針（p->rlink->llink）指向q，③p的rlink指針（p->rlink）指向q。稍加分析可知，若①②③三個(gè)步驟順序錯(cuò)誤，則無法完成插入。用代碼表示就是：
q->llink = p; q->rlink = p->rlink; p->rlink->llink = q; p->rlink = q;
同樣地，若要在表頭或表尾插入元素，則緊抓住核心算法稍作改變，并改變r(jià)ear的指針域即可。
雙鏈表插入算法示例如下：
int Insert(DLinkList *rear, DLinkList *p, DataType x)
{
DLinkList *q = (DLinkList *)malloc(sizeof(DLinkList));
if (q == NULL)
return 0;
q->data = x;/*數(shù)據(jù)域賦值*/
if (p->rlink == NULL)/*在表尾插入元素*/
{
rear->rlink = q;
q->llink = p;
q->rlink = p->rlink;
p->rlink = q;
return 1;
}
if (p == rear)/*若p為rear，認(rèn)為在表頭插入元素*/
{
q->llink = rear->llink->llink;
q->rlink = rear->llink;
rear->llink->llink = q;
rear->llink = q;
return 1;
}
q->llink = p;
q->rlink = p->rlink;
p->rlink->llink = q;
p->rlink = q;
return 1;
}3.建立
利用前面所講在表尾插入元素的辦法，我們可以每建立一個(gè)新結(jié)點(diǎn)就將其插入到表尾。當(dāng)剛開始建立雙鏈表時(shí)，讓rear的llink指針（rear->llink）指向表頭結(jié)點(diǎn)，并讓表頭結(jié)點(diǎn)指向NULL；當(dāng)建立結(jié)束時(shí)，讓rear的rlink指針（rear->rlink）指向最后一個(gè)結(jié)點(diǎn)，即可完成雙鏈表的建立。
DLinkList *CreateDLinkList()
{
DLinkList *rear, *p, *q;
rear = (DLinkList *)malloc(sizeof(DLinkList));
p = (DLinkList *)malloc(sizeof(DLinkList));
if (rear==NULL || p==NULL)
{
free(rear);
free(p);
return NULL;
}
DataType x;
scanf(&x);
p->data = x;
rear->llink = p;
p->llink = NULL;
p->rlink = NULL;
scanf(&x);
while (x != flag)/*flag為建立結(jié)束的標(biāo)志*/
{
q = (DLinkList *)malloc(sizeof(DLinkList));
if (q == NULL)
{
DLinkList *pr;
p = rear->llink;
while (p != NULL)
{
pr = p->rlink;
free(p);
p = pr;
}
free(rear);
return NULL;
}
q->data = x;
q->llink = p;
q->rlink = NULL;
p->rlink = q;
scanf(&x);
}
rear->rlink = q;
return rear;
}4.查找
相對(duì)于單鏈表，雙鏈表的優(yōu)勢(shì)是可以實(shí)現(xiàn)雙向的查找。假設(shè)讓指針p和指針q分別從表頭和表尾向中間遍歷雙鏈表的每一個(gè)結(jié)點(diǎn)，當(dāng)p==q或p->llink==q時(shí)認(rèn)為已遍歷結(jié)束。
DLinkList *SearchDLinkList(DLinkList *rear, DataType x)
{
DLinkList *p = rear->llink, *q = rear->rlink;
while (p->data!=x && q->data!=x)
{
p = p->rlink;
q = q->llink;
if (p==q || p->llink==q)
break;
}
if (p->data == x)
return p;
else if (q->data == x)
return q;
else
return NULL;
}總結(jié)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容
相關(guān)文章
C語言實(shí)現(xiàn)旅游資訊管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)旅游資訊管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C++解決輸出鏈表中倒數(shù)k個(gè)結(jié)點(diǎn)的問題
這篇文章主要給大家介紹了關(guān)于如何利用C++解決輸出鏈表中倒數(shù)k個(gè)結(jié)點(diǎn)的問題,文中通過實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-12-12
C++友元函數(shù)與拷貝構(gòu)造函數(shù)詳解
這篇文章主要介紹了C++友元函數(shù)與拷貝構(gòu)造函數(shù),需要的朋友可以參考下2014-07-07
在寫Qt應(yīng)用程序時(shí)，由于是采用C++語言，經(jīng)常會(huì)碰到一個(gè)令人棘手的問題，那就是內(nèi)存泄漏，本文主要介紹了Qt下監(jiān)測(cè)內(nèi)存泄漏的方法，感興趣的可以了解一下2021-12-12
C++定時(shí)器Timer在項(xiàng)目中的使用方法
