一步一步教你從零開(kāi)始寫(xiě)C語(yǔ)言鏈表
掃描二維碼
隨時(shí)隨地手機(jī)看文章
為什么要學(xué)習(xí)鏈表？
鏈表主要有以下幾大特性：
1、解決數(shù)組無(wú)法存儲(chǔ)多種數(shù)據(jù)類型的問(wèn)題。
2、解決數(shù)組中，元素個(gè)數(shù)無(wú)法改變的限制(C99的變長(zhǎng)數(shù)組，C++也有變長(zhǎng)數(shù)組可以實(shí)現(xiàn))。
3、數(shù)組移動(dòng)元素的過(guò)程中，要對(duì)元素進(jìn)行大范圍的移動(dòng)，很耗時(shí)間，效率也不高。
先來(lái)感性的認(rèn)識(shí)一下鏈表,我們先來(lái)認(rèn)識(shí)下簡(jiǎn)單的鏈表:
從這幅圖我們得出以下信息:
這個(gè)簡(jiǎn)單鏈表的構(gòu)成：
頭指針(Header)，若干個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)包括了數(shù)據(jù)域和指針域)，最后一個(gè)節(jié)點(diǎn)要指向空。
實(shí)現(xiàn)原理：頭指針指向鏈表的第一個(gè)節(jié)點(diǎn)，然后第一個(gè)節(jié)點(diǎn)中的指針指向下一個(gè)節(jié)點(diǎn)，然后依次指到最后一個(gè)節(jié)點(diǎn)，這樣就構(gòu)成了一條鏈表。
接下來(lái)看看鏈表的數(shù)據(jù)結(jié)構(gòu):
struct list_node
{
int data ; //數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)
struct list_node *next ; //指針，可以用來(lái)訪問(wèn)節(jié)點(diǎn)數(shù)據(jù)，也可以遍歷，指向下一個(gè)節(jié)點(diǎn)
};
那么如何來(lái)創(chuàng)建一個(gè)鏈表的一個(gè)節(jié)點(diǎn)呢？
我們寫(xiě)個(gè)程序演示一下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node
{
int data ;
struct list_node *next ;
};
typedef struct list_node list_single ;
int main(void)
{
list_single *node = NULL ; //1、首先，當(dāng)然是定義一個(gè)頭指針
node = (list_single *)malloc(sizeof(list_single)); //2、然后分配內(nèi)存空間
if(node == NULL){
printf("malloc fair!\n");
}
memset(node,0,sizeof(list_single)); //3、清一下
node->data = 100 ; //4、給鏈表節(jié)點(diǎn)的數(shù)據(jù)賦值
node->next = NULL ; //5、將鏈表的指針域指向空
printf("%d\n",node->data);
free(node);
return 0 ;
}
那么，這僅僅只是創(chuàng)建一個(gè)鏈表中的一個(gè)節(jié)點(diǎn)，為了好看，我們把創(chuàng)建節(jié)點(diǎn)封裝成函數(shù)，以后想創(chuàng)建多少個(gè)節(jié)點(diǎn)，我們就可以反復(fù)調(diào)用一個(gè)函數(shù)來(lái)創(chuàng)建，會(huì)很方便:
list_single *create_list_node(int data)
{
list_single *node = NULL ;
node = (list_single *)malloc(sizeof(list_single));
if(node == NULL){
printf("malloc fair!\n");
}
memset(node,0,sizeof(list_single));
node->data = 100 ;
node->next = NULL ;
return node ;
}
接下來(lái)在程序上完成的程序:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node
{
int data ;
struct list_node *next ;
};
typedef struct list_node list_single ;
list_single *create_list_node(int data)
{
list_single *node = NULL ;
node = (list_single *)malloc(sizeof(list_single));
if(node == NULL){
printf("malloc fair!\n");
}
memset(node,0,sizeof(list_single));
node->data = data;
node->next = NULL ;
return node ;
}
int main(void)
{
int data = 100 ;
list_single *node_ptr = create_list_node(data); //創(chuàng)建一個(gè)節(jié)點(diǎn)
printf("node_ptr->data=%d\n",node_ptr->data); //打印節(jié)點(diǎn)里的數(shù)據(jù)
printf("node_ptr->next=%d\n",node_ptr->next);
free(node_ptr);
return 0 ;
}
執(zhí)行結(jié)果 ：
這樣我們就完成一個(gè)鏈表節(jié)點(diǎn)的創(chuàng)建了，那么它現(xiàn)在的樣子如下圖：
鏈表的結(jié)構(gòu)里，數(shù)據(jù)存儲(chǔ)了100，因?yàn)檫@個(gè)鏈表只有一個(gè)節(jié)點(diǎn)，所以它的指針域指向了NULL。
上面只是建立一個(gè)單鏈表的基本雛形，接下來(lái)咱們?cè)賮?lái)增加一點(diǎn)難度。如果創(chuàng)建多個(gè)單鏈表節(jié)點(diǎn)，實(shí)現(xiàn)單鏈表的增刪改查？把單鏈表應(yīng)用起來(lái)。
1、首先定義一個(gè)單鏈表的數(shù)據(jù)結(jié)構(gòu)
創(chuàng)建節(jié)點(diǎn)函數(shù)原型可定義如下：
struct list *create_node(int data) ;
如何創(chuàng)建單鏈表的節(jié)點(diǎn)，主要分以下步驟:
(1)給當(dāng)前的每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)配置定量的空間大小
ep : struct list *node = malloc(sizeof(struct list));
(2)清節(jié)點(diǎn)數(shù)據(jù)(由于結(jié)構(gòu)體變量在未初始化的時(shí)候，數(shù)據(jù)是臟的)
ep : memset(node,0,sizeof(struct list));
(3)給節(jié)點(diǎn)初始化數(shù)據(jù)
ep : node->id = data ;
(4)將該節(jié)點(diǎn)的指針域設(shè)置為NULL
ep : node->next = NULL ;
2、單鏈表的尾插：
尾插節(jié)點(diǎn)函數(shù)原型可定義如下：
如何將當(dāng)前鏈表和新的節(jié)點(diǎn)相連接？只要實(shí)現(xiàn)：
header->next = new
尾插流程如下：
(1)獲取當(dāng)前節(jié)點(diǎn)的位置，也就是訪問(wèn)頭節(jié)點(diǎn)
ep : struct list *p = header ;
(2)判斷是否為最后一個(gè)節(jié)點(diǎn)，如果不是，移動(dòng)到下一個(gè)節(jié)點(diǎn)，如果是，將數(shù)據(jù)插入尾部。
ep : while(NULL != p->next) p = p->next ;
p->next = new ;
3、單鏈表的頭插
很好理解，頭插就是把新的節(jié)點(diǎn)插在原來(lái)的節(jié)點(diǎn)和原來(lái)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)之間的一個(gè)節(jié)點(diǎn)。如圖，新的節(jié)點(diǎn)插在頭節(jié)點(diǎn)和節(jié)點(diǎn)1。
所以可以推出頭插流程如下：
(1)獲取當(dāng)前節(jié)點(diǎn)的位置，也就是訪問(wèn)頭節(jié)點(diǎn)
ep : struct list *p = header ;
(2)新的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為原來(lái)頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)(第一個(gè)節(jié)點(diǎn))
ep : new->next = p->next ;
(3)原來(lái)的頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為現(xiàn)在新插入的頭節(jié)點(diǎn)
ep : p->next = new ;
4、單鏈表的遍歷
如圖為一條單向鏈表的模型，看圖知道該鏈表由頭節(jié)點(diǎn)和若干個(gè)節(jié)點(diǎn)組成，最后一個(gè)節(jié)點(diǎn)(尾節(jié)點(diǎn))為NULL 。
從圖中可以得出信息，如果我們要打印出各個(gè)節(jié)點(diǎn)的數(shù)據(jù)，要考慮以下問(wèn)題：
(1)需要打印頭節(jié)點(diǎn)嗎？(頭節(jié)點(diǎn)肯定是不用打印的，因?yàn)檫@是我們?yōu)榱瞬僮鞣奖愣O(shè)置的一個(gè)節(jié)點(diǎn))。
(2)這條鏈表有多少個(gè)節(jié)點(diǎn)我們?cè)趺粗溃?通過(guò)判斷該鏈表是否已經(jīng)到達(dá)了尾節(jié)點(diǎn)，標(biāo)志就是NULL)
那么可以得到流程如下：
(1)獲取當(dāng)前節(jié)點(diǎn)的位置，也就是訪問(wèn)頭節(jié)點(diǎn)
ep : struct list *p = header ;
(2)由于頭節(jié)點(diǎn)我們不需要去打印它，這時(shí)候，初始化打印的節(jié)點(diǎn)需要從第一個(gè)節(jié)點(diǎn)開(kāi)始。
ep : p = p->next ;
(3)判斷是否為最后一個(gè)節(jié)點(diǎn)，如果不是，先打印第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)(1)，然后移動(dòng)到下一個(gè)節(jié)點(diǎn)(2),重復(fù)這兩個(gè)步驟。
如果是最后一個(gè)節(jié)點(diǎn)，直接打印數(shù)據(jù)即可。
while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
printf("node:%d\n",p->data);
當(dāng)然還可以一句代碼解決，這樣就達(dá)到了先偏移，后取數(shù)據(jù)。
while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }
5、單鏈表的刪除
刪除節(jié)點(diǎn)的函數(shù)原型可定義如下：
int detele_list_node(struct list *pH , int data);
單向鏈表的刪除要考慮兩種情況，一種的普通節(jié)點(diǎn)的刪除(當(dāng)然，頭節(jié)點(diǎn)不能算)
還有一種是尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的刪除情況，注意，刪除完節(jié)點(diǎn)還需要釋放對(duì)應(yīng)節(jié)點(diǎn)的內(nèi)存空間。
刪除節(jié)點(diǎn)的設(shè)計(jì)流程：
(1)先定義兩個(gè)指針，一個(gè)表示當(dāng)前的節(jié)點(diǎn)，另一個(gè)表示當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。
ep : struct list *p = header ; //當(dāng)前節(jié)點(diǎn)
struct list *prev = NULL ; //當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
(2)遍歷整個(gè)鏈表，同時(shí)保存當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
ep : while(NULL != p->next)
{
//保存了當(dāng)前的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
prev = p ;
//保存當(dāng)前偏移的節(jié)點(diǎn)
p = p->next ;
return 0 ;
}
(3)在遍歷的過(guò)程中查找要?jiǎng)h除的數(shù)據(jù)
ep : while(NULL != p->next)
{
//保存了當(dāng)前的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
prev = p ;
//保存當(dāng)前偏移的節(jié)點(diǎn)
p = p->next ;
//查找到了數(shù)據(jù)
if(p->id == data)
{
}
return 0 ;
}
(4)查找到了數(shù)據(jù)后，分兩種情況刪除
ep : 普通節(jié)點(diǎn)的刪除
if(p->id == data)
{
prev->next = p->next ;
free(p);
}
ep : 考慮尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為NULL的節(jié)點(diǎn)刪除
if(p->id == data)
{
if(p->next == NULL)
{
prev->next = NULL ;
free(p);
}
}
6、單鏈表的逆序
逆序步驟：
單鏈表的基本操作流程咱們基本搞懂了，下面寫(xiě)一個(gè)程序，這將會(huì)變得非常非常的簡(jiǎn)單。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
int id ;
struct slist *next ;
}L;
//創(chuàng)建一個(gè)節(jié)點(diǎn)
L *create_node(int data)
{
//給每個(gè)節(jié)點(diǎn)分配結(jié)構(gòu)體一樣的空間大小
L *p = malloc(sizeof(L));
if(NULL == p)
{
printf("malloc error!\n");
return NULL ;
}
//由于結(jié)構(gòu)體在未初始化的時(shí)候一樣是臟數(shù)據(jù)，所以要清
memset(p,0,sizeof(L));
//初始化第一個(gè)節(jié)點(diǎn)
p->id = data ;
//將節(jié)點(diǎn)的后繼指針設(shè)置為NULL
p->next = NULL ;
}
//鏈表的尾插
void tail_insert(L *pH , L *new)
{
//獲取當(dāng)前的位置
L *p = pH ;
//如果當(dāng)前位置的下一個(gè)節(jié)點(diǎn)不為空
while(NULL != p->next)
{
//移動(dòng)到下一個(gè)節(jié)點(diǎn)
p = p->next ;
}
//如果跳出以上循環(huán)，所以已經(jīng)到了NULL的這個(gè)位置
//此時(shí)直接把新插入的節(jié)點(diǎn)賦值給NULL這個(gè)位置
p->next = new ;
}
//鏈表的頭插
void top_insert(L *pH , L *new)
{
L *p = pH ;
new->next = p->next ;
p->next = new ;
}
//鏈表的遍歷
void Print_node(L *pH)
{
//獲取當(dāng)前的位置
L *p = pH ;
//獲取第一個(gè)節(jié)點(diǎn)的位置
p = p->next ;
//如果當(dāng)前位置的下一個(gè)節(jié)點(diǎn)不為空
while(NULL != p->next)
{
//(1)打印節(jié)點(diǎn)的數(shù)據(jù)
printf("id:%d\n",p->id);
//(2)移動(dòng)到下一個(gè)節(jié)點(diǎn),如果條件仍為真，則重復(fù)(1)，再(2)
p = p->next ;
}
//如果當(dāng)前位置的下一個(gè)節(jié)點(diǎn)為空，則打印數(shù)據(jù)
//說(shuō)明只有一個(gè)節(jié)點(diǎn)
printf("id:%d\n",p->id);
}
//刪除鏈表中的節(jié)點(diǎn)
int detele_list_node(L * pH , int data)
{
//獲取當(dāng)前頭節(jié)點(diǎn)的位置
L *p = pH ;
L *prev = NULL;
while(NULL != p->next)
{
//保存當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針
prev = p ;
//然后讓當(dāng)前的指針繼續(xù)往后移動(dòng)
p = p->next ;
//判斷，找到了要?jiǎng)h除的數(shù)據(jù)
if(p->id == data)
{
//兩種情況，一種是普通節(jié)點(diǎn)，還有一種是尾節(jié)點(diǎn)
if(p->next != NULL) //普通節(jié)點(diǎn)的情況
{
prev->next = p->next ;
free(p);
}
else //尾節(jié)點(diǎn)的情況
{
prev->next = NULL ; //將這個(gè)尾節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的指針域指向空
free(p);
}
return 0 ;
}
}
printf("沒(méi)有要?jiǎng)h除的節(jié)點(diǎn)\n");
return -1 ;
}
void trave_list(L * pH)
{
//保存第一個(gè)節(jié)點(diǎn)的位置
L *p = pH->next;
L *pBack;
int i = 0 ;
if(p->next == NULL || p == NULL)
return ;
while(NULL != p->next) //遍歷鏈表
{
//保存第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
pBack = p->next ;
//找到第一個(gè)有效節(jié)點(diǎn),其實(shí)就是頭指針的下一個(gè)節(jié)點(diǎn)
if(p == pH->next)
{
//第一個(gè)有效節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn)，所以要指向NULL
p->next = NULL ;
}
else
{
/*
new->next = p->next ;
p->next = new ;
*/
p->next = pH->next ; //尾部連接
}
pH->next = p ; //頭部連接
p = pBack ; //走下一個(gè)節(jié)點(diǎn)
}
top_insert(pH,p); //插入最后一個(gè)節(jié)點(diǎn)
}
int main(int argc , char **argv)
{
//創(chuàng)建第一個(gè)節(jié)點(diǎn)
int i ;
L *header = create_node(0);
for(i = 1 ; i < 10 ; i++)
{
tail_insert(header,create_node(i));
}
Print_node(header);
detele_list_node(header,5);
putchar('\n');
Print_node(header);
putchar('\n');
trave_list(header);
Print_node(header);
return 0 ;
}
運(yùn)行結(jié)果：
當(dāng)然，單鏈表存在一定的弊端，就是查找數(shù)據(jù)和刪除數(shù)據(jù)的時(shí)候比較麻煩，而雙鏈表的出現(xiàn)就是為了解決它的弊端：
雙鏈表的引入是為了解決單鏈表的不足：
(1)雙鏈表可以往前遍歷，也可以往后遍歷，具有兩個(gè)方向
雙鏈表的節(jié)點(diǎn) = 有效數(shù)據(jù) + 兩個(gè)指針(分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn))
雙向鏈表的圖形結(jié)構(gòu)描述:
struct double_list struct double_list
{ {
數(shù)據(jù)域; ep :-------> int data ;
指針域(前向指針) ; struct double_list *prev ;
指針域(后向指針) ; struct double_list *next ;
}; };
1、雙向鏈表的創(chuàng)建
struct list *create_node(int data) ;
創(chuàng)建步驟(與單鏈表類似，就是多了一個(gè)指針):
(1)給節(jié)點(diǎn)申請(qǐng)空間：
ep : struct double_list *p = malloc(sizeof(struct double_list));
(2)初始化數(shù)據(jù)域
ep : p->data = data ;
(3)初始化指針域
ep : p->prev = NULL ;
p->next = NULL ;
2、雙向鏈表的尾插
雙向鏈表尾插節(jié)點(diǎn)的函數(shù)可以定義如下：
void double_list_tail_insert(struct double_list *header , struct double_list *new) ;
尾插圖示操作：
尾插的步驟：
(1)找到鏈表的尾節(jié)點(diǎn)
ep : 和單鏈表差不多
DL *p = header ;
while(NULL != p->next)
p = p->next ;
(2)將新的節(jié)點(diǎn)連接到尾節(jié)點(diǎn)的后面成為新的節(jié)點(diǎn)
1.原來(lái)的next指針指向新節(jié)點(diǎn)的首地址。 p->next = new ;
2.新節(jié)點(diǎn)的prev指針指向原來(lái)的尾節(jié)點(diǎn)的首地址。 new->prev = p;
3、雙向鏈表的頭插
雙向鏈表頭插節(jié)點(diǎn)的函數(shù)可以定義如下：
void double_list_top_insert(struct double_list *header , struct double_list *new) ;
4、雙向鏈表的遍歷
4.1 正向遍歷
void double_list_for_each(DL *header)
步驟：和單鏈表完全一致，沒(méi)什么好寫(xiě)的。
4.2 反向遍歷
void double_list_for_each_nx(DL *header)
步驟：(1)和單鏈表一樣，先循環(huán)找到最后一個(gè)節(jié)點(diǎn)的地址
(2)再依靠prev指針循環(huán)往前移動(dòng)
2.1 先打印最后一個(gè)數(shù)據(jù) ep : printf("%d ",p->data);
2.2 向前循環(huán)遍歷 ep : p = p->prev ;
判斷條件：header->prev != p->prev,
header保存的是頭節(jié)點(diǎn)的地址,
header->prev保存的是頭節(jié)點(diǎn)的prev的地址,
header->next保存的是頭節(jié)點(diǎn)的next的地址,
頭節(jié)點(diǎn)在創(chuàng)建的時(shí)候:
header->prev = NULL ;
header->next = NULL ;
所以這個(gè)條件這樣寫(xiě)header->prev = NULL也是對(duì)的。
5、雙向鏈表節(jié)點(diǎn)的刪除
假設(shè)需要?jiǎng)h除節(jié)點(diǎn)1：
首先:
(1)獲取當(dāng)前節(jié)點(diǎn)的地址：
ep : p = header;
(2)遍歷所有的節(jié)點(diǎn)，找到要?jiǎng)h除的節(jié)點(diǎn)：
ep :
while(NULL != p->next)
{
p = p->next ;
if(p->data == data)
{
}
}
(3)找到要?jiǎng)h除的數(shù)據(jù)以后，需要做判斷，判斷兩種情況，這和單鏈表差不多
3.1 如果找到當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空
3.1.1
那就把當(dāng)前節(jié)點(diǎn)的prev節(jié)點(diǎn)指向要?jiǎng)h除的這個(gè)節(jié)點(diǎn)的prev
因?yàn)楫?dāng)前的prev節(jié)點(diǎn)保存的是要?jiǎng)h除的上一個(gè)節(jié)點(diǎn)的指針
p->next->prev = p->prev ;
3.1.2
然后將當(dāng)前節(jié)點(diǎn)的prev指針(也就是上一個(gè)節(jié)點(diǎn)的指針)指向當(dāng)前節(jié)點(diǎn)(要?jiǎng)h除的)的下一個(gè)節(jié)點(diǎn):
p->prev->next = p->next ;
3.1.3
最后釋放刪除指針的空間：
free(p);
3.2 如果找到當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空
3.2.1
直接把當(dāng)前指針(要?jiǎng)h除的節(jié)點(diǎn))的prev指針(保存著當(dāng)前指針的上一個(gè)節(jié)點(diǎn)的地址)的下一個(gè)next指針設(shè)置為空。
p->prev->next = NULL ;
3.2.2
將刪除的指針的空間釋放:
free(p);
看來(lái)，雙鏈表學(xué)起來(lái)比單鏈表容易多了！確實(shí)啊，多了一個(gè)方向，操作起來(lái)就更加容易了，但是多了一個(gè)方向，一維多了一個(gè)指針，相比增加了一定的復(fù)雜度，但是，只要牢記prev指針和next指針的指向，那么，手畫(huà)一圖，代碼即可寫(xiě)出！
下面給一個(gè)案例實(shí)現(xiàn)一下雙向鏈表：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//創(chuàng)建一個(gè)雙鏈表的數(shù)據(jù)結(jié)構(gòu)
typedef struct __double_list
{
int data ;
struct __double_list *prev ;
struct __double_list *next ;
}DL ;
//創(chuàng)建雙向鏈表并插入一個(gè)節(jié)點(diǎn)
DL *create_dl_node(int data)
{
DL *p = malloc(sizeof(DL));
if(NULL == p)
{
printf("create dl node fair!\n");
return NULL ;
}
//初始化數(shù)據(jù)
p->data = data ;
//初始化指針
p->next = NULL ;
p->prev = NULL ;
}
//雙向鏈表的尾插
void double_list_tail_insert(DL *header , DL *new)
{
//取得當(dāng)前節(jié)點(diǎn)的地址
DL *p = header ;
//找到鏈表的尾節(jié)點(diǎn)
while(NULL != p->next)
{
//找不到接著找
p = p->next ;
}
//找到了尾節(jié)點(diǎn)，指向新節(jié)點(diǎn)的首地址
p->next = new ;
//新節(jié)點(diǎn)的prev指針指向原來(lái)的尾節(jié)點(diǎn)的首地址。
new->prev = p;
}
//雙向鏈表的頭插(也就是插在兩個(gè)節(jié)點(diǎn)之間的插入方式)
void double_list_top_insert(DL *header , DL *new)
{
//新節(jié)點(diǎn)的next指針指向原來(lái)的節(jié)點(diǎn)一的地址
new->next = header->next ;
//判斷當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址是否為空
if(NULL != header->next)
header->next->prev = new ; //節(jié)點(diǎn)1的prev指針指向新節(jié)點(diǎn)的地址
header->next = new ;
new->prev = header ;
}
//雙向鏈表的正向遍歷
void double_list_for_each(DL *header)
{
DL *p = header ;
while(NULL != p->next)
{
p = p->next ;
printf("%d ",p->data);
}
}
//雙向鏈表的反向遍歷
void double_list_for_each_nx(DL *header)
{
DL *p = header ;
//先找到尾節(jié)點(diǎn)
while(NULL != p->next)
{
p = p->next ;
}
//已經(jīng)找到了尾節(jié)點(diǎn)，向前遍歷，注意，遍歷到頭節(jié)點(diǎn)之前
//限制條件: != 頭結(jié)點(diǎn)
while(NULL != p->prev)
{
printf("%d ",p->data);
p = p->prev ;
}
}
//雙向鏈表節(jié)點(diǎn)的刪除
int double_list_delete_node(DL *header , int data)
{
//取得當(dāng)前節(jié)點(diǎn)
DL *p = header;
//遍歷所有的節(jié)點(diǎn)
while(NULL != p->next)
{
p = p->next ;
//找到了對(duì)應(yīng)要?jiǎng)h除的數(shù)據(jù)了
if(p->data == data)
{
//一樣存在兩種情況
//(1)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空
if(p->next != NULL)
{
//那就把當(dāng)前節(jié)點(diǎn)的prev節(jié)點(diǎn)指向要?jiǎng)h除的這個(gè)節(jié)點(diǎn)的prev
//因?yàn)楫?dāng)前的prev節(jié)點(diǎn)保存的是要?jiǎng)h除的上一個(gè)節(jié)點(diǎn)的指針
p->next->prev = p->prev ;
//還要指定它的next節(jié)點(diǎn)
p->prev->next = p->next ;
free(p);
}
//(2)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空
else
{
//把
p->prev->next = NULL ;
free(p);
}
return 0 ;
}
}
printf("\n沒(méi)有找到對(duì)應(yīng)要?jiǎng)h除的節(jié)點(diǎn)，或者節(jié)點(diǎn)已經(jīng)被刪除！\n");
return -1 ;
}
int main(void)
{
int i ;
DL *header = create_dl_node(0);
for(i = 0 ; i < 10 ; i++)
{
//雙向鏈表的尾插
//double_list_tail_insert(header,create_dl_node(i));
//雙向鏈表的頭插
double_list_top_insert(header,create_dl_node(i));
}
//雙向鏈表的正向遍歷
printf("雙向鏈表的正向遍歷:");
double_list_delete_node(header,5);
double_list_for_each(header);
// double_list_delete_node(header,9);
double_list_delete_node(header,5);
putchar('\n');
printf("雙向鏈表的反向遍歷:");
double_list_for_each_nx(header);
return 0 ;
}
運(yùn)行結(jié)果：
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
