链表的数据域怎么使用结构体_一步一步教你从零开始写C语言链表
為什么要學習鏈表？
鏈表主要有以下幾大特性：
1、解決數組無法存儲多種數據類型的問題。
2、解決數組中，元素個數無法改變的限制(C99的變長數組，C++也有變長數組可以實現)。
3、數組移動元素的過程中，要對元素進行大范圍的移動，很耗時間，效率也不高。
先來感性的認識一下鏈表,我們先來認識下簡單的鏈表:
從這幅圖我們得出以下信息:
這個簡單鏈表的構成：
頭指針(Header)，若干個節點(節點包括了數據域和指針域)，最后一個節點要指向空。
實現原理：頭指針指向鏈表的第一個節點，然后第一個節點中的指針指向下一個節點，然后依次指到最后一個節點，這樣就構成了一條鏈表。
接下來看看鏈表的數據結構:
struct ?list_node
{
int data ; //數據域，用于存儲數據
struct list_node *next ; //指針，可以用來訪問節點數據，也可以遍歷，指向下一個節點
};
那么如何來創建一個鏈表的一個節點呢？
我們寫個程序演示一下:
#include
#include
#include
struct ?list_node
{
int data ;?
struct list_node *next ;
};
typedef struct list_node list_single ;
int main(void)
{
list_single *node = NULL ; ? ? ? ? ?//1、首先，當然是定義一個頭指針
node = (list_single *)malloc(sizeof(list_single)); //2、然后分配內存空間
if(node == NULL){
printf("malloc fair!\n");
}
memset(node,0,sizeof(list_single)); //3、清一下
node->data = 100 ; ? ? //4、給鏈表節點的數據賦值
node->next = NULL ; ? ? ? ? ? ? ? ? //5、將鏈表的指針域指向空
printf("%d\n",node->data);
free(node);
return 0 ;
}
? ? 那么，這僅僅只是創建一個鏈表中的一個節點，為了好看，我們把創建節點封裝成函數，以后想創建多少個節點，我們就可以反復調用一個函數來創建，會很方便:
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
#include
#include
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); //創建一個節點
printf("node_ptr->data=%d\n",node_ptr->data); ? //打印節點里的數據
printf("node_ptr->next=%d\n",node_ptr->next); ?
free(node_ptr);
return 0 ;
}
執行結果 ：
這樣我們就完成一個鏈表節點的創建了，那么它現在的樣子如下圖：
鏈表的結構里，數據存儲了100，因為這個鏈表只有一個節點，所以它的指針域指向了NULL。
上面只是建立一個單鏈表的基本雛形，接下來咱們再來增加一點難度。如果創建多個單鏈表節點，實現單鏈表的增刪改查？把單鏈表應用起來。
1、首先定義一個單鏈表的數據結構
創建節點函數原型可定義如下：
struct list *create_node(int data) ;
如何創建單鏈表的節點，主要分以下步驟:
(1)給當前的每個節點的數據結構配置定量的空間大小
? ?ep : struct list *node = malloc(sizeof(struct list));
(2)清節點數據(由于結構體變量在未初始化的時候，數據是臟的)
? ?ep : memset(node,0,sizeof(struct list));
(3)給節點初始化數據
? ?ep : node->id = data ;?
(4)將該節點的指針域設置為NULL
? ?ep : node->next = NULL ;
2、單鏈表的尾插：
尾插節點函數原型可定義如下：
如何將當前鏈表和新的節點相連接？只要實現：
header->next = new?
尾插流程如下：
(1)獲取當前節點的位置，也就是訪問頭節點
? ?ep : struct list *p = header ;
(2)判斷是否為最后一個節點，如果不是，移動到下一個節點，如果是，將數據插入尾部。
? ?ep : while(NULL != p->next) p = p->next ;
? ? ? ? p->next = new ;
3、單鏈表的頭插
很好理解，頭插就是把新的節點插在原來的節點和原來節點的下一個節點之間的一個節點。如圖，新的節點插在頭節點和節點1。
所以可以推出頭插流程如下：
(1)獲取當前節點的位置，也就是訪問頭節點
? ? ep : struct list *p = header ;
(2)新的節點的下一個節點設置為原來頭節點的下一個節點(第一個節點)
? ? ep : new->next = p->next ;
(3)原來的頭節點的下一個節點設置為現在新插入的頭節點
? ? ep : p->next = new ;
4、單鏈表的遍歷
如圖為一條單向鏈表的模型，看圖知道該鏈表由頭節點和若干個節點組成，最后一個節點(尾節點)為NULL 。
從圖中可以得出信息，如果我們要打印出各個節點的數據，要考慮以下問題：
(1)需要打印頭節點嗎？(頭節點肯定是不用打印的，因為這是我們為了操作方便而設置的一個節點)。
(2)這條鏈表有多少個節點我們怎么知道？(通過判斷該鏈表是否已經到達了尾節點，標志就是NULL)
那么可以得到流程如下：
(1)獲取當前節點的位置，也就是訪問頭節點
? ? ep : struct list *p = header ;
(2)由于頭節點我們不需要去打印它，這時候，初始化打印的節點需要從第一個節點開始。
? ? ep : p = p->next ; ?
(3)判斷是否為最后一個節點，如果不是，先打印第一個節點的數據(1)，然后移動到下一個節點(2),重復這兩個步驟。
? ?如果是最后一個節點，直接打印數據即可。
? ? while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
? ? printf("node:%d\n",p->data);
? ? 當然還可以一句代碼解決，這樣就達到了先偏移，后取數據。
? ? while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }
5、單鏈表的刪除
刪除節點的函數原型可定義如下：
int detele_list_node(struct list *pH , int data);
單向鏈表的刪除要考慮兩種情況，一種的普通節點的刪除(當然，頭節點不能算)
還有一種是尾節點的前一個節點的刪除情況，注意，刪除完節點還需要釋放對應節點的內存空間。
刪除節點的設計流程：
(1)先定義兩個指針，一個表示當前的節點，另一個表示當前節點的上一個節點。
? ? ep : struct list *p = header ; ?//當前節點
? ? ? ? ?struct list *prev = NULL ; //當前節點的上一個節點
(2)遍歷整個鏈表，同時保存當前節點的前一個節點
? ? ep : while(NULL != p->next)
? ? ? ? {?
? ? ? ? ? //保存了當前的節點的前一個節點
? ? ? ? ? prev = p ; ?
? ? ? ? ? //保存當前偏移的節點
? ? ? ? ? p = p->next ;?
? ? ? ? ? return 0 ;
? ? ? ? }
(3)在遍歷的過程中查找要刪除的數據
? ? ep : while(NULL != p->next)
? ? ? ? {?
? ? ? ? ? //保存了當前的節點的前一個節點
? ? ? ? ? prev = p ; ?
? ? ? ? ? //保存當前偏移的節點
? ? ? ? ? p = p->next ;?
? ? ? ? ? //查找到了數據
? ? ? ? ? if(p->id == data)
? ? ? ? ? {
? ? ? ? ? }
? ? ? ? ? return 0 ;
? ? ? ? }
(4)查找到了數據后，分兩種情況刪除
? ? ep : 普通節點的刪除
? ? ? ? if(p->id == data)
? ? ? ? {
? ? ? ? ? ? prev->next = p->next ;
? ? ? ? ? ? free(p);
? ? ? ? }
? ? ep : 考慮尾節點的下一個節點為NULL的節點刪除
? ? ? ? if(p->id == data)
? ? ? ? {
? ? ? ? ? ? if(p->next == NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? prev->next = NULL ;
? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ? }
? ? ? ? }
6、單鏈表的逆序
逆序步驟：
? ?單鏈表的基本操作流程咱們基本搞懂了，下面寫一個程序，這將會變得非常非常的簡單。
#include
#include
#include
typedef struct slist
{
int id ;
struct slist *next ;
}L;
//創建一個節點?
L *create_node(int data)
{
//給每個節點分配結構體一樣的空間大小?
L *p = malloc(sizeof(L));
if(NULL == p)
{
printf("malloc error!\n");
return NULL ;
}
//由于結構體在未初始化的時候一樣是臟數據，所以要清?
memset(p,0,sizeof(L));
//初始化第一個節點?
p->id = data ;?
//將節點的后繼指針設置為NULL?
p->next = NULL ;
}
//鏈表的尾插?
void tail_insert(L *pH , L *new)
{
//獲取當前的位置?
L *p = pH ;?
//如果當前位置的下一個節點不為空?
while(NULL != p->next)
{
//移動到下一個節點?
p = p->next ;
}
//如果跳出以上循環，所以已經到了NULL的這個位置
//此時直接把新插入的節點賦值給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)
{
//獲取當前的位置?
L *p = pH ;
//獲取第一個節點的位置?
p = p->next ;
//如果當前位置的下一個節點不為空?
while(NULL != p->next)
{
//(1)打印節點的數據?
printf("id:%d\n",p->id);
//(2)移動到下一個節點,如果條件仍為真，則重復(1)，再(2)?
p = p->next ;
}
//如果當前位置的下一個節點為空，則打印數據
//說明只有一個節點?
printf("id:%d\n",p->id);
}
//刪除鏈表中的節點?
int detele_list_node(L * pH , int data)
{
//獲取當前頭節點的位置?
L *p = pH ;
L *prev = NULL;
while(NULL != p->next)
{
//保存當前節點的前一個節點的指針?
prev = p ;
//然后讓當前的指針繼續往后移動?
p = p->next ;
//判斷，找到了要刪除的數據 ?
if(p->id == data)
{
//兩種情況，一種是普通節點，還有一種是尾節點
if(p->next != NULL) ?//普通節點的情況?
{
prev->next = p->next ;
free(p);
}
else //尾節點的情況?
{
prev->next = NULL ; //將這個尾節點的上一個節點的指針域指向空?
free(p);?
}
return 0 ?;
}
}
printf("沒有要刪除的節點\n");
return -1 ;
}
void trave_list(L * pH)
{
//保存第一個節點的位置?
L *p = pH->next;
L *pBack;
int i = 0 ;
if(p->next == NULL || p == NULL)
return ;
while(NULL != p->next) //遍歷鏈表?
{
//保存第一個節點的下一個節點?
pBack = p->next ;?
//找到第一個有效節點,其實就是頭指針的下一個節點?
if(p == pH->next)?
{
//第一個有效節點就是最后一個節點，所以要指向NULL?
p->next = NULL ;?
}?
else
{
/*
new->next = p->next ;
p->next = new ;
*/
p->next = pH->next ; //尾部連接?
}
pH->next = p ; //頭部連接?
p = pBack ; //走下一個節點?
}
top_insert(pH,p); //插入最后一個節點?
}
int main(int argc , char **argv)?
{
//創建第一個節點?
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 ;
}
運行結果：
當然，單鏈表存在一定的弊端，就是查找數據和刪除數據的時候比較麻煩，而雙鏈表的出現就是為了解決它的弊端：
雙鏈表的引入是為了解決單鏈表的不足：
(1)雙鏈表可以往前遍歷，也可以往后遍歷，具有兩個方向
雙鏈表的節點 = 有效數據 + 兩個指針(分別指向前一個節點和后一個節點)
雙向鏈表的圖形結構描述:
struct double_list ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? struct double_list
{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?{
? ? 數據域; ? ? ? ? ? ? ? ? ?ep :-------> ? ? ? ? ? ? ? ? ? int data ;
? ? 指針域(前向指針) ; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? struct double_list *prev ;
? ? 指針域(后向指針) ; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? struct double_list *next ;
}; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? };
1、雙向鏈表的創建
struct list *create_node(int data) ;
創建步驟(與單鏈表類似，就是多了一個指針):
(1)給節點申請空間：
? ?ep : struct double_list *p = malloc(sizeof(struct double_list));
(2)初始化數據域
? ?ep : p->data = data ;
(3)初始化指針域
? ?ep : p->prev = NULL ;?
? ? ? ? p->next = NULL ;
2、雙向鏈表的尾插
雙向鏈表尾插節點的函數可以定義如下：
void double_list_tail_insert(struct double_list *header , struct double_list *new) ;
尾插圖示操作：
尾插的步驟：
(1)找到鏈表的尾節點
? ?ep : 和單鏈表差不多
? ? ? ? DL *p = header ;
? ? ? ? while(NULL != p->next)
? ? ? ? ? ? p = p->next ;
(2)將新的節點連接到尾節點的后面成為新的節點
? ?1.原來的next指針指向新節點的首地址。 ? ? ? ? ? ?p->next = new ;
? ?2.新節點的prev指針指向原來的尾節點的首地址。 new->prev = p;
3、雙向鏈表的頭插
雙向鏈表頭插節點的函數可以定義如下：
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)和單鏈表一樣，先循環找到最后一個節點的地址
? ? ? ? ? (2)再依靠prev指針循環往前移動
? ? ? ? ? ? ?2.1 先打印最后一個數據 ?ep : printf("%d ",p->data);
? ? ? ? ? ? ?2.2 向前循環遍歷 ? ? ? ? ep : p = p->prev ;
? ? ? ? ? ? ?判斷條件：header->prev != p->prev,
? ? ? ? ? ? ?header保存的是頭節點的地址,
? ? ? ? ? ? ?header->prev保存的是頭節點的prev的地址,
? ? ? ? ? ? ?header->next保存的是頭節點的next的地址,
? ? ? ? ? ? ?頭節點在創建的時候:
? ? ? ? ? ? ?header->prev = NULL ;
? ? ? ? ? ? ?header->next = NULL ;
? ? ? ? ? ? ?所以這個條件這樣寫header->prev = NULL也是對的。
5、雙向鏈表節點的刪除
假設需要刪除節點1： ? ?
? ? 首先:
? ? (1)獲取當前節點的地址：?
? ? ? ? ep : p = header;
? ? (2)遍歷所有的節點，找到要刪除的節點：
? ? ? ? ep :?
? ? ? ? while(NULL != p->next)
? ? ? ? {
? ? ? ? ? ? p = p->next ;
? ? ? ? ? ? if(p->data == data)
? ? ? ? ? ? {
? ? ? ? ? ? }
? ? ? ? }
? ? (3)找到要刪除的數據以后，需要做判斷，判斷兩種情況，這和單鏈表差不多
? ? 3.1 如果找到當前節點的下一個節點不為空
? ? 3.1.1 ? ?
? ? ? ? 那就把當前節點的prev節點指向要刪除的這個節點的prev
? ? ? ? 因為當前的prev節點保存的是要刪除的上一個節點的指針?
? ? ? ? p->next->prev = p->prev ;
? ? 3.1.2 ? ?
? ? ? ? 然后將當前節點的prev指針(也就是上一個節點的指針)指向當前節點(要刪除的)的下一個節點:
? ? ? ? p->prev->next = p->next ;
? ? 3.1.3 ? ?
? ? ? ? 最后釋放刪除指針的空間：
? ? ? ? free(p);
? ? 3.2 如果找到當前節點的下一個節點為空
? ? 3.2.1 ??
? ? 直接把當前指針(要刪除的節點)的prev指針(保存著當前指針的上一個節點的地址)的下一個next指針設置為空。
? ? p->prev->next = NULL ;
? ? 3.2.2
? ? 將刪除的指針的空間釋放:
? ? free(p);
? ? 看來，雙鏈表學起來比單鏈表容易多了！確實啊，多了一個方向，操作起來就更加容易了，但是多了一個方向，一維多了一個指針，相比增加了一定的復雜度，但是，只要牢記prev指針和next指針的指向，那么，手畫一圖，代碼即可寫出！
下面給一個案例實現一下雙向鏈表：
#include
#include
#include
//創建一個雙鏈表的數據結構
typedef struct __double_list
{
int data ;
struct __double_list *prev ;
struct __double_list *next ;
}DL ;?
//創建雙向鏈表并插入一個節點?
DL *create_dl_node(int data)
{
DL *p = malloc(sizeof(DL));
if(NULL == p)
{
printf("create dl node fair!\n");
return NULL ;
}
//初始化數據?
p->data = data ;
//初始化指針?
p->next = NULL ;
p->prev = NULL ;
}
//雙向鏈表的尾插?
void double_list_tail_insert(DL *header , DL *new)
{
//取得當前節點的地址?
DL *p = header ;
//找到鏈表的尾節點?
while(NULL != p->next)
{
//找不到接著找?
p = p->next ;
}
//找到了尾節點，指向新節點的首地址?
p->next = new ;
//新節點的prev指針指向原來的尾節點的首地址。
new->prev = p;
}
//雙向鏈表的頭插(也就是插在兩個節點之間的插入方式)
void double_list_top_insert(DL *header , DL *new)
{
//新節點的next指針指向原來的節點一的地址
new->next = header->next ;?
//判斷當前節點的下一個節點的地址是否為空
if(NULL != header->next)?
header->next->prev = new ; //節點1的prev指針指向新節點的地址?
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 ;
//先找到尾節點
while(NULL != p->next)
{
p = p->next ;
}?
//已經找到了尾節點，向前遍歷，注意，遍歷到頭節點之前
//限制條件: != 頭結點?
while(NULL != p->prev)
{
printf("%d ",p->data);
p = p->prev ;
}
}
//雙向鏈表節點的刪除
int double_list_delete_node(DL *header , int data)
{
//取得當前節點?
DL *p = header;
//遍歷所有的節點?
while(NULL != p->next)
{
p = p->next ;
//找到了對應要刪除的數據了?
if(p->data == data)
{
//一樣存在兩種情況
//(1)當前節點的下一個節點不為空
if(p->next != NULL)
{
//那就把當前節點的prev節點指向要刪除的這個節點的prev
//因為當前的prev節點保存的是要刪除的上一個節點的指針?
p->next->prev = p->prev ;
//還要指定它的next節點?
p->prev->next = p->next ;
free(p);
}
//(2)當前節點的下一個節點為空?
else
{
//把?
p->prev->next = NULL ;
free(p);?
}
return 0 ;
}
}
printf("\n沒有找到對應要刪除的節點，或者節點已經被刪除！\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 ;
}
運行結果：
總結
以上是生活随笔為你收集整理的链表的数据域怎么使用结构体_一步一步教你从零开始写C语言链表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 流动性比例 什么是流动性比率
- 下一篇： 农行异地存款免费了吗