鏈表基礎知識詳解(非常詳細簡單易懂)

概述:

? ? ? 鏈表作為 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);}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/716011.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/716011.shtml
英文地址,請注明出處:http://en.pswp.cn/news/716011.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

【Vue3】解鎖Vue3黑科技:探索接口、泛型和自定義類型的前端奇跡

&#x1f497;&#x1f497;&#x1f497;歡迎來到我的博客&#xff0c;你將找到有關如何使用技術解決問題的文章&#xff0c;也會找到某個技術的學習路線。無論你是何種職業&#xff0c;我都希望我的博客對你有所幫助。最后不要忘記訂閱我的博客以獲取最新文章&#xff0c;也歡…

Android Compose - PlainTooltipBox(已廢棄)的替代方案

Android Compose - PlainTooltipBox 的替代方案 TooltipBox(positionProvider TooltipDefaults.rememberPlainTooltipPositionProvider(),tooltip {PlainTooltip {Text(/* tooltip content */)}},state rememberTooltipState(), ) {// tooltip anchorIconButton(onClick {…

跨站腳本攻擊xss-labs(1-20)靶機練手

目錄 一、跨站腳本攻擊&#xff08;XSS&#xff09; 1.1 漏洞簡介 1.2:類型 1.3 XSS危害 1.4XSS防御規則 二、環境搭建 三、xsst通關記錄 Level 1&#xff1a;文本解析為 HTML Level 2&#xff1a;htmlspecialchars;input 標簽 value 注入 定義和用法 字符過濾繞過 …

從零自制docker-1-【環境配置 docker go介紹與安裝】

文章目錄 docker簡介舉例docker安裝go語言go安裝go 配置 docker簡介 Docker可以看作是一種極其輕巧的“虛擬機”&#xff0c;它允許你將一個或多個程序及其運行環境打包在一起&#xff0c;形成一個標準化的單元&#xff0c;這個單元可以在任何支持Docker的系統上運行&#xff…

實用!IntelliJ IDEA離線開發使用要點(一)

如果IntelliJ IDEA在本地網絡之外沒有HTTP訪問&#xff0c;它將無法檢查更新和應用補丁。在這種情況下&#xff0c;您必須下載新版本的IDE并按照離線安裝中的描述手動安裝它們。 IDEA v2023.3正式版下載 注意&#xff1a;沒有互聯網接入&#xff0c;您不能安裝IntelliJ IDEA使…

SaaS 電商設計 (九) 動態化且易擴展的實現購物車底部彈層(附:一套普適的線上功能切量的發布方案)

目錄 一.背景1.1 業務背景1.2 技術負債 二.技術目標三.方案設計3.1 解決移動端頻繁發版3.1.1 場景分析3.1.2 技術方案 3.2 減少后端壞味道代碼&無法靈活擴展問題3.2.1 通過抽象接口完成各自單獨樓層渲染邏輯3.2.2 通過配置能力做到部分字段可配 四.升級上線(普適于高并發大…

2314576

? 通用計算機啟動過程 1??一個基礎固件&#xff1a;BIOS 一個基礎固件&#xff1a;BIOS→基本IO系統&#xff0c;它提供以下功能&#xff1a; 上電后自檢功能 Power-On Self-Test&#xff0c;即POST&#xff1a;上電后&#xff0c;識別硬件配置并對其進行自檢&#xff0c…

學習JAVA的第十二天(基礎)

算法 算法&#xff08;Algorithm&#xff09;是指解題方案的準確而完整的描述&#xff0c;是一系列解決問題的清晰指令&#xff0c;算法代表著用系統的方法描述 解決問題的策略 機制。 查找算法 基本查找&#xff08;順序查找&#xff09; 關鍵&#xff1a; 從0索引開始依次向…

學習:吳恩達:什么是神經元?神經網絡如何工作?

學習-吳恩達《AI for everyone》2019 深度學習非技術解釋 第2部分 可選.zh_嗶哩嗶哩_bilibili 深度學習Deep learning 人工神經網絡Artificial Neural network 什么是神經網絡&#xff1f; 只有一個神經元 4個神經元的神經網絡 神經網路的絕妙之處 神經網路的絕妙之處就在…

ctf_show筆記篇(web入門---信息收集)

目錄 信息收集 1-2&#xff1a;查看源代碼 3&#xff1a;bp抓包 4&#xff1a;robots.txt&#xff08;這個文件里會寫有網站管理者不想讓爬蟲的頁面或其他&#xff09; 5&#xff1a;網站源代碼泄露index.phps 6&#xff1a;同樣也是源碼泄露&#xff0c;&#xff08;拿到…

Java快讀

java的快讀 (1)BufferedReader BufferedReader br new BufferedReader(new InputStreamReader(System.in));//定義對象String[] strings br.readLine().split(" ");//讀取一行字符串&#xff0c;以空格為分隔轉化為字符串數組int n Integer.parseInt(strings[0])…

k8s分布式圖床(k8s,metricsapi,vue3+ts)

image-manage 圖像管理應用 圖像管理應用提供了一個方便管理圖片的平臺&#xff0c;支持單機和Kubernetes集群部署。請確保您至少擁有一個MySQL數據庫和一個Redis數據庫&#xff0c;以及一個至少為Kubernetes 1.29版本的集群&#xff08;如果選擇集群部署&#xff09;。 文檔…

PCL1.14.0安裝、使用教程

寫在前面 本文內容 本文是PCL1.14.0在Windows下的安裝、使用教程&#xff1b; PCL、Open3D其他版本的編譯和使用相關教程見 各個版本的Open3D、PCL的編譯、使用教程平臺/環境 windows11(windows10): visual studio 2022&#xff1b;cmake 3.22; VsCode轉載請注明出處&#xff…

http和https的區別是什么?

–前言 傳輸信息安全性不同、連接方式不同、端口不同、證書申請方式不同 一、傳輸信息安全性不同 1、http協議&#xff1a;是超文本傳輸協議&#xff0c;信息是明文傳輸。如果攻擊者截取了Web瀏覽器和網站服務器之間的傳輸報文&#xff0c;就可以直接讀懂其中的信息。 2、h…

關于django makemigrations/migrate在生成數據表上遇到的一些問題

當你刪除了生成的 migration 文件夾&#xff0c;將數據庫從 SQLite 切換到 MySQL&#xff0c;并且在執行 makemigrations 命令時顯示沒有變化&#xff0c;同時 MySQL 中沒有生成表&#xff0c;可能是由于以下原因造成的&#xff1a; Django遷移系統的工作方式&#xff1a;Djang…

排序(3)——直接選擇排序

目錄 直接選擇排序 基本思想 整體思路&#xff08;升序&#xff09; 單趟 多趟 代碼實現 特性總結 直接選擇排序 基本思想 每一次從待排序的數據元素中選出最小&#xff08;或最大&#xff09;的一個元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部待排序的…

軟考 系統分析師系列知識點之詳細調查(3)

接前一篇文章&#xff1a;軟考 系統分析師系列知識點之詳細調查&#xff08;2&#xff09; 所屬章節&#xff1a; 第10章. 系統分析 第2節. 詳細調查 在系統規劃階段&#xff0c;通過初步調查&#xff0c;系統分析師已經對企業的組織結構、系統功能等有了大致的了解。但是&…

力扣203移除鏈表元素

題目&#xff1a; 203. 移除鏈表元素 給你一個鏈表的頭節點 head 和一個整數 val &#xff0c;請你刪除鏈表中所有滿足 Node.val val 的節點&#xff0c;并返回 新的頭節點 。 1&#xff0c;設置一個頭節點&#xff0c;統一操作。 2&#xff0c;這里是用p查找&#xff0c;但是…

BUUCTF---數據包中的線索1

1.題目描述 2.下載附件&#xff0c;是一個.pcap文件 3.放在wireshark中&#xff0c;仔細觀察數據流&#xff0c;會發現有個叫fenxi.php的數據流 4.這條數據流是http,且使用GET方式&#xff0c;接下來我們使用http.request,methodGET 命令來過濾數據流 5.在分析欄中我們追蹤htt…

查看端口占用命令

fuser 8080/tcp netstat -tuln | grep 8080 lsof -i:8080 ss -tuln | grep 8080