基本概念
在之前的學(xué)習(xí)中，已經(jīng)學(xué)習(xí)了單向鏈表及其實(shí)現(xiàn)原杂，在單向鏈表中抽减，查找一個(gè)數(shù)據(jù)郁竟，只能從某個(gè)結(jié)點(diǎn)出發(fā)，順著指針往后查找其他結(jié)點(diǎn)狡逢，若需要查找結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)宁舰，只能從表頭指針重新出發(fā)。在單向鏈表中奢浑，查找一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)明吩，其時(shí)間復(fù)雜度為O(1)，而查找其直接前驅(qū)結(jié)點(diǎn)殷费，需要的時(shí)間復(fù)雜度為O(n)印荔，為了克服這種缺點(diǎn)，特地引入了雙向鏈表详羡。
雙向鏈表與單向鏈表相比仍律，雙向鏈表有兩個(gè)指針域，一個(gè)指向其直接后繼实柠，另一個(gè)指向其直接前驅(qū)水泉，其結(jié)構(gòu)如下圖所示：
雙向鏈表的結(jié)點(diǎn)可以用以下結(jié)構(gòu)體定義
typedef struct dulNode {
int pData; //數(shù)據(jù)域
struct dulNode *next; //后繼結(jié)點(diǎn)
struct dulNode *pre; //前驅(qū)結(jié)點(diǎn)
}dulNode, *dulList;
雙向鏈表的接口及其實(shí)現(xiàn)
接口定義
接口定義如下代碼所示：
#pragma once
#ifndef DOUBLELINKLIST_H
#define DOUBLELINKLIST_H
typedef struct dulNode {
int pData; //數(shù)據(jù)域
struct dulNode *next; //后繼結(jié)點(diǎn)
struct dulNode *pre; //前驅(qū)結(jié)點(diǎn)
}dulNode, *dulList;
dulList initDulList(); //初始化
dulList insertDulList(dulList list, int i, int elem); //位置i處插入元素elem
dulList deleteDulList(dulList list, int i);//刪除i處的結(jié)點(diǎn)
int locateDulList(dulList list, int elem); //查找元素elem的位置‘
void dulList_trave(dulList list); //遍歷鏈表
void freeDulList(dulList list); //銷毀鏈表
dulList updateDulList(dulList list, int i, int elem); //修改i處的元素
int getLength(dulList list);
#endif // !DOUBLELINKLIST_H
接口實(shí)現(xiàn)
- 初始化
初始化的過程就是給鏈表頭結(jié)點(diǎn)分配一塊固定大小的內(nèi)存，并將它的后繼結(jié)點(diǎn)與前驅(qū)結(jié)點(diǎn)置空，當(dāng)然也可以將前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)設(shè)置為頭結(jié)點(diǎn)本身草则。具體實(shí)現(xiàn)代碼如下所示;
dulList initDulList()
{
dulList list = (dulList)malloc(sizeof(dulNode));
if (list)
{
list->next = list->pre = NULL;
list->pData = NULL;
return list;
}
else
return NULL;
}
-
插入結(jié)點(diǎn)
雙向鏈表中插入一個(gè)結(jié)點(diǎn)與單向鏈表相比钢拧，要多考慮其前驅(qū)指針的變化，當(dāng)插入位置是頭結(jié)點(diǎn)之前時(shí)炕横，直接將插入結(jié)點(diǎn)的后繼指針指向原來(lái)的鏈表頭結(jié)點(diǎn)源内，并將其前驅(qū)指針指向其結(jié)點(diǎn)本身。而當(dāng)插入位置是尾結(jié)點(diǎn)是份殿，需要將原來(lái)鏈表的后繼指針指向要插入的結(jié)點(diǎn)膜钓，將要插入結(jié)點(diǎn)的前驅(qū)指針指向原來(lái)鏈表的尾結(jié)點(diǎn)。當(dāng)插入位置是中間位置時(shí)卿嘲，實(shí)現(xiàn)過程可有下圖動(dòng)態(tài)表示;
插入元素
以上過程可以由以下代碼實(shí)現(xiàn)
dulList insertDulList(dulList list, int i, int elem)
{
dulList temp = (dulList)malloc(sizeof(dulNode));
temp->pData = elem;
temp->next = NULL;
temp->pre = NULL;
if (i<1||i>getLength(list)+1)
{
printf("位置無(wú)效颂斜！");
exit(0);
}
else if (i == 1)
{
temp->next = list;
list->pre = temp;
list = temp;
}
else
{
//找到插入位置的前一個(gè)結(jié)點(diǎn)
dulList p = list;
for (int j = 1; j < i-1; j++)
{
p = p->next;
}
//判斷是否是尾
if (p->next == NULL)
{
p->next = temp;
temp->pre = p;
}
else
{
p->next->pre = temp;
temp->next = p->next;
p->next = temp;
temp->pre = p;
}
}
return list;
}
- 刪除元素
在雙向鏈表中刪除一個(gè)元素，需要處理好被刪除結(jié)點(diǎn)直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針域拾枣，具體實(shí)現(xiàn)可以簡(jiǎn)單描述為以下兩步:
- 將被刪除結(jié)點(diǎn)的后繼指針賦值給其直接前驅(qū)結(jié)點(diǎn)的后繼指針;
-
將被刪除結(jié)點(diǎn)的前驅(qū)指針賦值給其直接后繼結(jié)點(diǎn)的前驅(qū)指針沃疮。
具體過程可由以下動(dòng)態(tài)圖所示：
刪除一個(gè)結(jié)點(diǎn)
以上過程的具體實(shí)現(xiàn)代碼如下所示：
dulList deleteDulList(dulList list, int i)
{
if (i<1 || i>getLength(list))
{
printf("位置錯(cuò)誤！");
exit(0);
}
dulList p = list;
for (int j = 0; j <i-1; j++)
{
p = p->next;
}
if (p!=NULL)
{
p->pre->next = p->next;
p->next->pre = p->pre;
free(p);
}
return list;
}
-
查找指定元素
雙向鏈表查找指定元素的代碼如下所示梅肤，若找到指定元素司蔬，返回其位置，否則返回-1.
動(dòng)態(tài)圖演示如下：
查找指定元素
int locateDulList(dulList list, int elem)
{
int index = 0;
dulList p = list;
while (p!=NULL)
{
if (p->pData == elem)
{
return index;
}
index++;
p = p->next;
}
return -1;
}
- 修改數(shù)據(jù)
雙向鏈表要修改一個(gè)數(shù)據(jù)凭语，首先通過遍歷找到要修改結(jié)點(diǎn)的位置葱她，然后將其數(shù)據(jù)域更改為指定的元素即可撩扒。如下代碼所示：
dulList updateDulList(dulList list, int i, int elem)
{
if (i < 1 || i>getLength(list))
{
printf("無(wú)效位置似扔！");
exit(0);
}
dulList p = list;
if (p != NULL)
{
for (int j = 1; j < i; j++)
{
p = p->next;
}
p->pData = elem;
return list;
}
}
- 獲取鏈表長(zhǎng)度
要獲得鏈表長(zhǎng)度，設(shè)置計(jì)數(shù)器初始值為0搓谆，需要遍歷整個(gè)鏈表炒辉，計(jì)數(shù)器累加即可，具體代碼如下所示：
int getLength(dulList list)
{
int i = 0;
dulList p = list->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
- 遍歷鏈表
遍歷整個(gè)鏈表的實(shí)現(xiàn)代碼如下所示：
void dulList_trave(dulList list)
{
dulList p = list;
if (p->next == NULL)
{
exit(0);
}
while (p->next)
{
if (p->next == NULL)
{
printf("%d", p->pData);
}
else
{
printf("%d->", p->pData);
}
p = p->next;
}
}
- 銷毀鏈表
對(duì)鏈表銷毀泉手，就是銷毀鏈表的每一個(gè)結(jié)點(diǎn)黔寇，通過遍歷鏈表，銷毀每個(gè)結(jié)點(diǎn)斩萌，具體實(shí)現(xiàn)代碼如下所示:
void freeDulList(dulList list)
{
dulList p = list;
if (list)
{
exit(0);
}
while (list)
{
p = list;
list = list->next;
free(p);
}
}
對(duì)雙向鏈表的測(cè)試代碼如下所示：
int main()
{
struct dulList* list = initDulList();
list = insertDulList(list, 1, 1);
list = insertDulList(list, 2, 2);
list = insertDulList(list, 3, 3);
list = insertDulList(list, 4, 4);
int index = locateDulList(list, 4);
list = updateDulList(list, 4, 6);
//printf("%d\n", index);
freeDulList(list);
//dulList_trave(list);
system("pause");
return 0;
}
教材：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）清華大學(xué)出版社
輔助學(xué)習(xí)網(wǎng)站：https://visualgo.net
