c語言鏈表詳解(C語言中鏈表的示例分析)

C語言鏈表詳解附實例

什么是鏈表

鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。鏈表和數組比較,不用事先確定存儲空間,而是根據需要開辟內存單元。
下圖1是最簡單的一種鏈表(單向鏈表)的結構

第 0 個結點稱為頭結點,它存放有第一個結點的首地址,它沒有數據,只是一個指針變量。以下的每個結點都分為兩個域,一個是數據域,存放各種實際的數據,如學號 num,姓名 name,性別 sex 和成績 score 等。另一個域為指針域,存放下一結點的首地址。鏈表中的每一個結點都是同一種結構類型。

環境構建

用的Visual Studio 2019軟件

在源文件中添加C文件

建立靜態鏈表

包含所需要的頭文件

#include<stdio.h>//標準輸入輸出頭文件#include<stdlib.h>//包含了C、C++語言的最常用的系統函數

宏定義相關變量

#defineLENsizeof(structStudent)//宏定義節點長度得命名#defineTYPEstructStudent//宏定義結構體變量命名

創建一個結構體

structStudent//定義一個學生類型結構體,包括學號,分數{longnum;floatscore;structStudent*next;//next是指針變量,指向結構體變量};//指向結構體對象得指針變量既可以指向結構體變量,也可以指向結構體數組中得元素

主函數

intmain(){TYPE*head,*p;//定義頭指針structStudenta,b,c;//定義三個結構體變量a.num=101;a.score=20;//分別對三個結點賦值b.num=102;b.score=20;c.num=103;c.score=20;/*1、A.B則A為對象或者結構體2、A->B則A為指針,->是成員提取,A->B是提取A中的成員B,A只能是指向類、結構、聯合的指針;*/head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;//把首地址給變量do{printf("%ld%5.1f\n",p->num,p->score);//輸出每個結點信息p=p->next;//使P指向下一個結點}while(p!=NULL);//直到指針域指向空值return0;}

結果展示

說明

將第一個結點的起始地址賦值給頭指針head,將第二個結點的起始地址賦值給第一個結點的next成員,將第二個結點的起始地址賦給第一個結點的next…第三個結點的next賦值為NULL,這就形成了簡單的鏈表。

建立動態鏈表

所謂建立動態鏈表是指在程序執行過程中從無到有地建立起一個 鏈表,即一個一個地開辟結點和輸入各結點數據,并建立起前后相連的關系。

包含所需要的頭文件

#include<stdio.h>//標準輸入輸出頭文件#include<stdlib.h>//包含了C、C++語言的最常用的系統函數#include<malloc.h>//動態存儲分配函數頭文件

宏定義相關變量

#defineLENsizeof(structStudent)//宏定義節點長度得命名#defineTYPEstructStudent//宏定義結構體變量命名

創建一個結構體

structStudent//定義一個學生類型結構體,包括學號,分數{longnum;floatscore;structStudent*next;//next是指針變量,指向結構體變量};//指向結構體對象得指針變量既可以指向結構體變量,也可以指向結構體數組中得元素

建立鏈表函數

TYPE*Creat(void)//定義函數,此函數返回一個指向鏈表頭的指針{TYPE*head;//定義頭指針TYPE*p1,*p2;//定義兩個指針變量用來相互保存number=0;//開始時,結點清零p1=p2=(TYPE*)malloc(LEN);//創建存儲空間printf("請按格式輸入學生學號,分數\n");//輸出提示信息printf("例如101,1并以0,0結束\n");scanf("%ld,%f",&p1->num,&p1->score);//按格式輸入第一個結點的信息head=NULL;//第一個結點頭指針賦空值while(p1->num!=0)//循環直到輸入學生學號為0,就結束{number++;//結點自增if(number==1)//如果只有一個結點,那么頭指針指向第一個輸入的結點head=p1;elsep2->next=p1;//如果大于1個,那么要用next保存前一個結點的信息p2=p1;//保存前一個結點信息p1=(TYPE*)malloc(LEN);//開辟新的結點scanf("%ld,%f",&p1->num,&p1->score);//輸入下一個結點信息}p2->next=NULL;//循環結束,將指向信息賦空值return(head);//返回首地址}

主函數

intmain(){TYPE*pt;//定義一個結構體指針變量pt=Creat();//函數返回鏈表第一個結點的地址printf("\nnum:%ld\nscore:%5.lf\n",pt->num,pt->score);//輸出第一個結點的成員值return0;}

結果展示

== 文中最后結果顯示的是第一個結點的內容,作為有強大功能的鏈表,對他的操作當然有許多,比如:鏈表的創建,修改,刪除,插入,輸出,排序,反序,清空鏈表的元素,求鏈表的長度等等。==

鏈表的輸出

用循環直接可以輸出鏈表

輸出函數

voidprint(TYPE*head){TYPE*p;//定義指針printf("\nNOWThese%drecordsare:\n");//輸出顯示信息p=head;//使p指向第一個結點if(head!=NULL)//輸出第一個結點后的信息do{printf("%ld%5.1f\n",p->num,p->score);p=p->next;//指向下個結點}while(p!=NULL);}

主函數

intmain(){TYPE*pt;//定義一個結構體指針變量pt=Creat();//函數返回鏈表第一個結點的地址print(pt);//輸出調用return0;}

鏈表的修改

修改函數

修改鏈表節點值很簡單。下面是一個傳入鏈表和要修改的節點,來修改值的函數.

voidchange(TYPE*head,intn)//修改指定位置的結點的信息{TYPE*p=head;//傳入首地址inti=0;while(i<n&&p!=NULL){p=p->next;i++;}//找到相應的位置結點if(p!=NULL){printf("輸入要修改的值\n");scanf("%ld,%f",&p->num,&p->score);//輸入下一個結點信息}elseprintf("節點不存在\n");}

主函數

intmain(){TYPE*pt;//定義一個結構體指針變量pt=Creat();//函數返回鏈表第一個結點的地址change(pt,2);//修改相關結點的信息,假設修改第2+1個print(pt);//輸出調用return0;}

##鏈表的刪除

刪除鏈表的元素也就是把前節點的指針域越過要刪除的節點指向下下個節點。即:p->next = q->next;然后放出q節點的空間,即free(q);

刪除函數

voiddelet(TYPE*head,intn){TYPE*p=head,*in;//定義兩邊指針inti=0;while(i<n&&p!=NULL){in=p;//找到左邊的p=p->next;//找到右邊的i++;}if(p!=NULL){in->next=p->next;//將左右鏈接free(p);//釋放中間結點}else{printf("節點不存在\n");}}

主函數

intmain(){TYPE*pt;//定義一個結構體指針變量pt=Creat();//函數返回鏈表第一個結點的地址delet(pt,1);//刪除第1+1個結點print(pt);//輸出調用return0;}

輸出結果

##鏈表的插入
我們可以看出來,插入節點就是用插入前節點的指針域鏈接上插入節點的數據域,再把插入節點的指針域鏈接上插入后節點的數據域。根據圖,插入節點也就是:e->next = head->next; head->next = e;
增加鏈表節點用到了兩個結構體指針和一個int數據。

插入函數

voidinsert(TYPE*head,intn){//鏈表的插入TYPE*p=head,*in;inti=0;while(i<n&&p!=NULL){p=p->next;i++;//找到相應結點}if(p!=NULL){in=(TYPE*)malloc(sizeof(TYPE));//開辟新的空間printf("輸入要插入的值\n");scanf("%ld,%f",&in->num,&in->score);//輸入新的結點信息in->next=p->next;//填充in節點的指針域,也就是說把in的指針域指向p的下一個節點p->next=in;//填充p節點的指針域,把p的指針域重新指向in}else{printf("節點不存在\n");}}

主函數

intmain(){TYPE*pt;//定義一個結構體指針變量pt=Creat();//函數返回鏈表第一個結點的地址insert(pt,1);//從1+1后插入print(pt);//輸出調用return0;}

結果顯示

出現的問題

1、出現scanf 和printf 在VS2019中使用時會出錯,解決辦法如下

最后是測試的所有源程序