@
目錄- 1.雙向鏈表的定義
- 2.雙向鏈表的創建
- 3.雙向鏈表的插入
- 4.雙向鏈表的洗掉
- 5.雙向鏈表更改節點資料
- 6.雙向鏈表的查找
- 7.雙向鏈表的列印
- 8.測驗函式及結果
1.雙向鏈表的定義
上一節學習了單向鏈表單鏈表詳解，今天學習雙鏈表，學習之前先對單向鏈表和雙向鏈表做個回顧，
單向鏈表特點：
??1.我們可以輕松的到達下一個節點, 但是回到前一個節點是很難的.
??2.只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)
雙向鏈表特點
??1.每次在插入或洗掉某個節點時, 需要處理四個節點的參考, 而不是兩個. 實作起來要困難一些
??2.相對于單向鏈表, 必然占用記憶體空間更大一些.
??3.既可以從頭遍歷到尾, 又可以從尾遍歷到頭
雙向鏈表的定義:
??雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個資料結點中都有兩個指標，分別指向直接后繼和直接前驅，所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，下圖為雙向鏈表的結構圖，
??從上中可以看到，雙向鏈表中各節點包含以下 3 部分資訊：
??指標域：用于指向當前節點的直接前驅節點；
??資料域：用于存盤資料元素，
??指標域：用于指向當前節點的直接后繼節點；
雙向回圈鏈表的定義:
??雙向鏈表也可以進行首尾連接，構成雙向回圈鏈表,如下圖所示
在創建鏈表時，只需要在最后將收尾相連即可（創建鏈表代碼中已經標出），其他代碼稍加改動即可，
雙鏈表的節點結構用 C 語言實作為：
/*亂數的范圍*/
#define MAX 100
/*節點結構*/
typedef struct Node{
struct Node *pre;
int data;
struct Node *next;
}Node;
2.雙向鏈表的創建
??同單鏈表相比，雙鏈表僅是各節點多了一個用于指向直接前驅的指標域，因此，我們可以在單鏈表的基礎輕松實作對雙鏈表的創建，
??需要注意的是，與單鏈表不同，雙鏈表創建程序中，每創建一個新節點，都要與其前驅節點建立兩次聯系，分別是：
??將新節點的 prior 指標指向直接前驅節點；
??將直接前驅節點的 next 指標指向新節點；
??這里給出創建雙向鏈表的 C 語言實作代碼：
Node* CreatList(Node * head,int length)
{
if (length == 1)
{
return( head = CreatNode(head));
}
else
{
head = CreatNode(head);
Node * list=head;
for (int i=1; i<length; i++)
/*創建并初始化一個新結點*/
{
Node * body=(Node*)malloc(sizeof(Node));
body->pre=NULL;
body->next=NULL;
body->data=https://www.cnblogs.com/dongxb/archive/2020/12/16/rand()%MAX;
/*直接前趨結點的next指標指向新結點*/
list->next=body;
/*新結點指向直接前趨結點*/
body->pre=list;
/*把body指標給list回傳*/
list=list->next;
}
}
/*加上以下兩句就是雙向回圈鏈表*/
// list->next=head;
// head->prior=list;
return head;
}
3.雙向鏈表的插入
??根據資料添加到雙向鏈表中的位置不同，可細分為以下 3 種情況：
1.添加至表頭
??將新資料元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關系即可，
??換句話說，假設新元素節點為 temp，表頭節點為 head，則需要做以下 2 步操作即可：
??temp->next=head; head->prior=temp;
??將 head 移至 temp，重新指向新的表頭；
??將新元素 7 添加至雙鏈表的表頭，則實作程序如下圖所示：
2.添加至表的中間位置
??同單鏈表添加資料類似，雙向鏈表中間位置添加資料需要經過以下 2 個步驟，如下圖所示：
??新節點先與其直接后繼節點建立雙層邏輯關系；
??新節點的直接前驅節點與之建立雙層邏輯關系；
3.添加至表尾
??與添加到表頭是一個道理，實作程序如下：
??找到雙鏈表中最后一個節點；
??讓新節點與最后一個節點進行雙層邏輯關系；
/*在第add位置的前面插入data節點*/
Node * InsertListHead(Node * head,int add,int data)
{
/*新建資料域為data的結點*/
Node * temp=(Node*)malloc(sizeof(Node));
if(head == NULL)
{
printf("malloc error!\r\n");
return NULL;
}
else
{
temp->data=https://www.cnblogs.com/dongxb/archive/2020/12/16/data;
temp->pre=NULL;
temp->next=NULL;
}
/*插入到鏈表頭，要特殊考慮*/
if (add==1)
{
temp->next=head;
head->pre=temp;
head=temp;
}
else
{
Node * body=head;
/*找到要插入位置的前一個結點*/
for (int i=1; inext;
}
/*判斷條件為真，說明插入位置為鏈表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
}
else
{
body->next->pre=temp;
temp->next=body->next;
body->next=temp;
temp->pre=body;
}
}
return head;
}
```c
/*在第add位置的后面插入data節點*/
Node * InsertListEnd(Node * head,int add,int data)
{
int i = 1;
/*新建資料域為data的結點*/
Node * temp=(Node*)malloc(sizeof(Node));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
Node * body=head;
while ((body->next)&&(inext;
i++;
}
/*判斷條件為真，說明插入位置為鏈表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
temp->next=NULL;
}
else
{
temp->next=body->pre->next;
temp->pre=body->pre;
temp->pre=body->pre;
body->pre->next=temp;
}
return head;
}
4.雙向鏈表的洗掉
??雙鏈表洗掉結點時，只需遍歷鏈表找到要洗掉的結點，然后將該節點從表中摘除即可，
??例如，洗掉元素 2 的操作程序如圖 所示：
Node * DeleteList(Node * head,int data)
{
Node * temp=head;
/*遍歷鏈表*/
while (temp)
{
/*判斷當前結點中資料域和data是否相等，若相等，摘除該結點*/
if (temp->data=https://www.cnblogs.com/dongxb/archive/2020/12/16/=data)
{
/*判斷是否是頭結點*/
if(temp->pre == NULL)
{
head=temp->next;
temp->next = NULL;
free(temp);
return head;
}
/*判斷是否是尾節點*/
else if(temp->next == NULL)
{
temp->pre->next=NULL;
free(temp);
return head;
}
else
{
temp->pre->next=temp->next;
temp->next->pre=temp->pre;
free(temp);
return head;
}
}
temp=temp->next;
}
printf("Can not find %d!\r\n",data);
return head;
}
5.雙向鏈表更改節點資料
??更改雙鏈表中指定結點資料域的操作是在查找的基礎上完成的，實作程序是：通過遍歷找到存盤有該資料元素的結點，直接更改其資料域即可，
/*更新函式，其中，add 表示更改結點在雙鏈表中的位置，newElem 為新資料的值*/
Node *ModifyList(Node * p,int add,int newElem)
{
Node * temp=p;
/*遍歷到被洗掉結點*/
for (int i=1; i<add; i++)
{
temp=temp->next;
}
temp->data=https://www.cnblogs.com/dongxb/archive/2020/12/16/newElem;
return p;
}
6.雙向鏈表的查找
??通常，雙向鏈表同單鏈表一樣，都僅有一個頭指標，因此，雙鏈表查找指定元素的實作同單鏈表類似，都是從表頭依次遍歷表中元素，
/*head為原雙鏈表，elem表示被查找元素*/
int FindList(Node * head,int elem)
{
/*新建一個指標t，初始化為頭指標 head*/
Node * temp=head;
int i=1;
while (temp)
{
if (temp->data=https://www.cnblogs.com/dongxb/archive/2020/12/16/=elem)
{
return i;
}
i++;
temp=temp->next;
}
/*程式執行至此處，表示查找失敗*/
return -1;
}
7.雙向鏈表的列印
/*輸出鏈表的功能函式*/
void PrintList(Node * head)
{
Node * temp=head;
while (temp)
{
/*如果該節點無后繼節點，說明此節點是鏈表的最后一個節點*/
if (temp->next==NULL)
{
printf("%d\n",temp->data);
}
else
{
printf("%d->",temp->data);
}
temp=temp->next;
}
}
8.測驗函式及結果
int main()
{
Node * head=NULL;
//創建雙鏈表
head=CreatList(head,5);
printf("新創建雙鏈表為\t");
PrintList(head);
//在表中第 5 的位置插入元素 1
head=InsertListHead(head, 5,1);
printf("在表中第 5 的位置插入元素 1\t");
PrintList(head);
//在表中第 3 的位置插入元素 7
head=InsertListEnd(head, 3, 7);
printf("在表中第 3 的位置插入元素 7\t");
PrintList(head);
// //表中洗掉元素 7
head=DeleteList(head, 7);
printf("表中洗掉元素 7\t\t\t");
PrintList(head);
printf("元素 1 的位置是\t：%d\n",FindList(head,1));
//表中第 3 個節點中的資料改為存盤 6
head = ModifyList(head,3,6);
printf("表中第 3 個節點中的資料改為存盤6\t");
PrintList(head);
return 0;
}
??大家的鼓勵是我繼續創作的動力，如果覺得寫的不錯，歡迎關注，點贊，收藏，轉發，謝謝！
以上代碼均為測驗后的代碼，如有錯誤和不妥的地方，歡迎指出，
部分內容參考網路，如有侵權，請聯系洗掉，
如遇到排版錯亂的問題，可以通過以下鏈接訪問我的CSDN，
CSDN:CSDN搜索“嵌入式與Linux那些事”
歡迎歡迎關注我的公眾號：嵌入式與Linux那些事，領取秋招筆試面試大禮包（華為小米等大廠面經，嵌入式知識點總結，筆試題目，簡歷模版等）和2000G學習資料，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/235622.html
標籤：其他
下一篇：我已經在Ubuntu的docker上部署好了Nextcloud，用ip可以進入Nextcloud上。但是我想讓外網也可以登錄網盤，這個應該怎么實作呀？