概述:
? ? ? 鏈表作為 C 語言中一種基礎的數據結構,在平時寫程序的時候用的并不多,但在操作系統里面使用的非常多。不管是RTOS還是Linux等使用非常廣泛,所以必須要搞懂鏈表,鏈表分為單向鏈表和雙向鏈表,單向鏈表很少用,使用最多的還是雙向鏈表。單向鏈表懂了雙向鏈表自然就會了。
文章目錄
一、鏈表的概念
?鏈表的構成:
鏈表的操作:
?雙向鏈表
鏈表與數組的對比
二、鏈表的創建
?三、鏈表的遍歷
四、鏈表的釋放
?五、鏈表節點的查找
六、鏈表節點的刪除
七、鏈表中插入一個節點
八、鏈表排序
九、雙向鏈表的創建和遍歷
?十、雙向鏈表插入節點
一、鏈表的概念
定義:
? ? ? 鏈表是一種物理存儲上非連續,數據元素的邏輯順序通過鏈表中的指針鏈接次序,實現的一種線性存儲結構。
特點:
? ? ? 鏈表由一系列節點(鏈表中每一個元素稱為節點)組成,節點在運行時動態生成 (malloc),每個節點包括兩個部分:
? ? ?一個是存儲數據元素的數據域
? ? ?另一個是存儲下一個節點地址的指針域
圖1?單向鏈表
?鏈表的構成:
? ? ? 鏈表由一個個節點構成,每個節點一般采用結構體的形式組織,例如:
typedef struct student{int num;char name[20];struct student *next;}STU;
? ? ? 鏈表節點分為兩個域
? ? ? 數據域:存放各種實際的數據,如:num、score等
? ? ? 指針域:存放下一節點的首地址,如:next等.
圖2 節點內嵌在一個數據結構中
鏈表的操作:
? ? ? 鏈表最大的作用是通過節點把離散的數據鏈接在一起,組成一個表,這大概就是鏈表 的字面解釋了吧。 鏈表常規的操作就是節點的插入和刪除,為了順利的插入,通常一條鏈 表我們會人為地規定一個根節點,這個根節點稱為生產者。通常根節點還會有一個節點計 數器,用于統計整條鏈表的節點個數,具體見圖3中的 root_node。
圖3帶根節點的鏈表
?雙向鏈表
? ? ? 雙向鏈表與單向鏈表的區別就是節點中有兩個節點指針,分別指向前后兩個節點,其 它完全一樣。有關雙向鏈表的文字描述參考單向鏈表小節即可,有關雙向鏈表的示意圖具體見圖4
圖4雙向鏈表
鏈表與數組的對比
? ? ? 在很多公司的嵌入式面試中,通常會問到鏈表和數組的區別。在 C 語言中,鏈表與數 組確實很像,兩者的示意圖具體見圖5,這里以雙向鏈表為例。
圖5 鏈表與數組的對比
? ? ? 鏈表是通過節點把離散的數據鏈接成一個表,通過對節點的插入和刪除操作從而實現 對數據的存取。而數組是通過開辟一段連續的內存來存儲數據,這是數組和鏈表最大的區 別。數組的每個成員對應鏈表的節點,成員和節點的數據類型可以是標準的 C 類型或者是 用戶自定義的結構體。數組有起始地址和結束地址,而鏈表是一個圈,沒有頭和尾之分, 但是為了方便節點的插入和刪除操作會人為的規定一個根節點。
二、鏈表的創建
第一步:創建一個節點
?第二步:創建第二個節點,將其放在第一個節點的后面(第一的節點的指針域保存第二個節點的地址)
第三步:再次創建節點,找到原本鏈表中的最后一個節點,接著講最后一個節點的指針域保存新節點的地址,以此內推。
#include <stdio.h>
#include <stdlib.h>
//定義結點結構體
typedef struct student
{//數據域int num; //學號int score; //分數char name[20]; //姓名//指針域struct student *next;
}STU;void link_creat_head(STU **p_head,STU *p_new)
{STU *p_mov = *p_head;if(*p_head == NULL) //當第一次加入鏈表為空時,head執行p_new{*p_head = p_new;p_new->next=NULL;}else //第二次及以后加入鏈表{while(p_mov->next!=NULL){p_mov=p_mov->next; //找到原有鏈表的最后一個節點}p_mov->next = p_new; //將新申請的節點加入鏈表p_new->next = NULL;}
}int main()
{STU *head = NULL,*p_new = NULL;int num,i;printf("請輸入鏈表初始個數:\n");scanf("%d",&num);for(i = 0; i < num;i++){p_new = (STU*)malloc(sizeof(STU));//申請一個新節點printf("請輸入學號、分數、名字:\n"); //給新節點賦值scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);link_creat_head(&head,p_new); //將新節點加入鏈表}
}
?三、鏈表的遍歷
第一步:輸出第一個節點的數據域,輸出完畢后,讓指針保存后一個節點的地址
?第二步:輸出移動地址對應的節點的數據域,輸出完畢后,指針繼續后移?
?
?第三步:以此類推,直到節點的指針域為NULL
//鏈表的遍歷
void link_print(STU *head)
{STU *p_mov;//定義新的指針保存鏈表的首地址,防止使用head改變原本鏈表p_mov = head;//當指針保存最后一個結點的指針域為NULL時,循環結束while(p_mov!=NULL){//先打印當前指針保存結點的指針域printf("num=%d score=%d name:%s\n",p_mov->num,\p_mov->score,p_mov->name);//指針后移,保存下一個結點的地址p_mov = p_mov->next;}
}
四、鏈表的釋放
重新定義一個指針q,保存p指向節點的地址,然后p后移保存下一個節點的地址,然后釋放q對應的節點,以此類推,直到p為NULL為止
//鏈表的釋放void link_free(STU **p_head){//定義一個指針變量保存頭結點的地址STU *pb=*p_head;while(*p_head!=NULL){//先保存p_head指向的結點的地址pb=*p_head;//p_head保存下一個結點地址*p_head=(*p_head)‐>next;//釋放結點并防止野指針free(pb);pb = NULL;}}
?五、鏈表節點的查找
? ? ? 先對比第一個結點的數據域是否是想要的數據,如果是就直接返回,如果不是則繼續查找下 一個結點,如果到達最后一個結點的時候都沒有匹配的數據,說明要查找數據不存在
//鏈表的查找
//按照學號查找
STU * link_search_num(STU *head,int num)
{STU *p_mov;//定義的指針變量保存第一個結點的地址p_mov=head;//當沒有到達最后一個結點的指針域時循環繼續while(p_mov!=NULL){//如果找到是當前結點的數據,則返回當前結點的地址if(p_mov->num == num)//找到了{return p_mov;}//如果沒有找到,則繼續對比下一個結點的指針域p_mov=p_mov->next;}//當循環結束的時候還沒有找到,說明要查找的數據不存在,返回NULL進行標識return NULL;//沒有找到
}//按照姓名查找
STU * link_search_name(STU *head,char *name)
{STU *p_mov;p_mov=head;while(p_mov!=NULL){if(strcmp(p_mov->name,name)==0)//找到了{return p_mov;}p_mov=p_mov->next;}return NULL;//沒有找到
}
六、鏈表節點的刪除
? ? ? 如果鏈表為空,不需要刪除 如果刪除的是第一個結點,則需要將保存鏈表首地址的指針保存第一個結點的下一個結點的 地址 如果刪除的是中間結點,則找到中間結點的前一個結點,讓前一個結點的指針域保存這個結 點的后一個結點的地址即可
//鏈表結點的刪除
void link_delete_num(STU **p_head,int num)
{STU *pb,*pf;pb=pf=*p_head;if(*p_head == NULL)//鏈表為空,不用刪{printf("鏈表為空,沒有您要刪的節點");\return ;}while(pb->num != num && pb->next !=NULL)//循環找,要刪除的節點{pf=pb;pb=pb->next;}if(pb->num == num)//找到了一個節點的num和num相同{if(pb == *p_head)//要刪除的節點是頭節點{//讓保存頭結點的指針保存后一個結點的地址*p_head = pb->next;}else{//前一個結點的指針域保存要刪除的后一個結點的地址pf->next = pb->next;}//釋放空間free(pb);pb = NULL;}else//沒有找到{printf("沒有您要刪除的節點\n");}
}
七、鏈表中插入一個節點
鏈表中插入一個結點,按照原本鏈表的順序插入,找到合適的位置
?情況(按照從小到大):
? ? ? 如果鏈表沒有結點,則新插入的就是第一個結點。
? ? ? 如果新插入的結點的數值最小,則作為頭結點。
? ? ? 如果新插入的結點的數值在中間位置,則找到前一個,然后插入到他們中間。
? ? ? 如果新插入的結點的數值最大,則插入到最后。
//鏈表的插入:按照學號的順序插入
void link_insert_num(STU **p_head,STU *p_new)
{STU *pb,*pf;pb=pf=*p_head;if(*p_head ==NULL)// 鏈表為空鏈表{*p_head = p_new;p_new->next=NULL;return ;}while((p_new->num >= pb->num) && (pb->next !=NULL) ){pf=pb;pb=pb->next;}if(p_new->num < pb->num)//找到一個節點的num比新來的節點num大,插在pb的前面{if(pb== *p_head)//找到的節點是頭節點,插在最前面{p_new->next= *p_head;*p_head =p_new;}else{pf->next=p_new;p_new->next = pb;}}else//沒有找到pb的num比p_new->num大的節點,插在最后{pb->next =p_new;p_new->next =NULL;}
}
八、鏈表排序
? ? ? 如果鏈表為空,不需要排序。
? ? ? 如果鏈表只有一個結點,不需要排序。
? ? ? 先將第一個結點與后面所有的結點依次對比數據域,只要有比第一個結點數據域小的,則交 換位置。
? ? ? ?交換之后,拿新的第一個結點的數據域與下一個結點再次對比,如果比他小,再次交換,依 次類推。
? ? ? 第一個結點確定完畢之后,接下來再將第二個結點與后面所有的結點對比,直到最后一個結 點也對比完畢為止。
//鏈表的排序
void link_order(STU *head)
{STU *pb,*pf,temp;pf=head;if(head==NULL){printf("鏈表為空,不用排序\n");return ;}if(head->next ==NULL){printf("只有一個節點,不用排序\n");return ;}while(pf->next !=NULL)//以pf指向的節點為基準節點,{pb=pf->next;//pb從基準元素的下個元素開始while(pb!=NULL){if(pf->num > pb->num){temp=*pb;*pb=*pf;*pf=temp;temp.next=pb->next;pb->next=pf->next;pf->next=temp.next;}pb=pb->next;}pf=pf->next;}
}
九、雙向鏈表的創建和遍歷
第一步:創建一個節點作為頭節點,將兩個指針域都保存NULL
第二步:先找到鏈表中的最后一個節點,然后讓最后一個節點的指針域保存新插入節點的地址,新插入節點的兩個指針域,一個保存上一個節點的地址,一個保存NULL
#include <stdio.h>
#include <stdlib.h>//定義結點結構體
typedef struct student
{//數據域int num; //學號int score; //分數char name[20]; //姓名//指針域struct student *front; //保存上一個結點的地址struct student *next; //保存下一個結點的地址
}STU;void double_link_creat_head(STU **p_head,STU *p_new)
{STU *p_mov=*p_head;if(*p_head==NULL) //當第一次加入鏈表為空時,head執行p_new{*p_head = p_new;p_new->front = NULL;p_new->next = NULL;}else //第二次及以后加入鏈表{while(p_mov->next!=NULL){p_mov=p_mov->next; //找到原有鏈表的最后一個節點}p_mov->next = p_new; //將新申請的節點加入鏈表p_new->front = p_mov;p_new->next = NULL;}
}void double_link_print(STU *head)
{STU *pb;pb=head;while(pb->next!=NULL){printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);pb=pb->next;}printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);printf("***********************\n");while(pb!=NULL){printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);pb=pb->front;}
}int main()
{STU *head=NULL,*p_new=NULL;int num,i;printf("請輸入鏈表初始個數:\n");scanf("%d",&num);for(i=0;i<num;i++){p_new=(STU*)malloc(sizeof(STU));//申請一個新節點printf("請輸入學號、分數、名字:\n"); //給新節點賦值scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);double_link_creat_head(&head,p_new); //將新節點加入鏈表}double_link_print(head);
}
?十、雙向鏈表插入節點
按照順序插入結點
#include <stdio.h>
#include <stdlib.h>//定義結點結構體
typedef struct student
{//數據域int num; //學號int score; //分數char name[20]; //姓名//指針域struct student *front; //保存上一個結點的地址struct student *next; //保存下一個結點的地址
}STU;void double_link_creat_head(STU **p_head,STU *p_new)
{STU *p_mov=*p_head;if(*p_head==NULL) //當第一次加入鏈表為空時,head執行p_new{*p_head = p_new;p_new->front = NULL;p_new->next = NULL;}else //第二次及以后加入鏈表{while(p_mov->next!=NULL){p_mov=p_mov->next; //找到原有鏈表的最后一個節點}p_mov->next = p_new; //將新申請的節點加入鏈表p_new->front = p_mov;p_new->next = NULL;}
}void double_link_print(STU *head)
{STU *pb;pb=head;while(pb->next!=NULL){printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);pb=pb->next;}printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);printf("***********************\n");while(pb!=NULL){printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);pb=pb->front;}
}//雙向鏈表的刪除
void double_link_delete_num(STU **p_head,int num)
{STU *pb,*pf;pb=*p_head;if(*p_head==NULL)//鏈表為空,不需要刪除{printf("鏈表為空,沒有您要刪除的節點\n");return ;}while((pb->num != num) && (pb->next != NULL) ){pb=pb->next;}if(pb->num == num)//找到了一個節點的num和num相同,刪除pb指向的節點{if(pb == *p_head)//找到的節點是頭節點{if((*p_head)->next==NULL)//只有一個節點的情況{*p_head=pb->next;}else//有多個節點的情況{*p_head = pb->next;//main函數中的head指向下個節點(*p_head)->front=NULL;}}else//要刪的節點是其他節點{if(pb->next!=NULL)//刪除中間節點{pf=pb->front;//讓pf指向找到的節點的前一個節點pf->next=pb->next; //前一個結點的next保存后一個結點的地址(pb->next)->front=pf; //后一個結點的front保存前一個結點的地址}else//刪除尾節點{pf=pb->front;pf->next=NULL;}}free(pb);//釋放找到的節點}else//沒找到{printf("沒有您要刪除的節點\n");}
}int main()
{STU *head=NULL,*p_new=NULL;int num,i;printf("請輸入鏈表初始個數:\n");scanf("%d",&num);for(i=0;i<num;i++){p_new=(STU*)malloc(sizeof(STU));//申請一個新節點printf("請輸入學號、分數、名字:\n"); //給新節點賦值scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);double_link_creat_head(&head,p_new); //將新節點加入鏈表}double_link_print(head);printf("請輸入您要刪除的節點的num\n");scanf("%d",&num);double_link_delete_num(&head,num);double_link_print(head);}