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