C語言實(shí)現(xiàn)線性動(dòng)態(tài)(單向)鏈表的示例代碼
什么是鏈表
鏈表是數(shù)據(jù)結(jié)構(gòu)里面的一種，線性鏈表是鏈表的一種，線性鏈表的延伸有雙向鏈表和環(huán)形鏈表。在編程語言中優(yōu)化數(shù)據(jù)結(jié)構(gòu)可以在處理大數(shù)據(jù)時(shí)大大降低程序的空間復(fù)雜性和時(shí)間復(fù)雜性。這里我只用一個(gè)簡單的例子——線性單向鏈表為例，說明C語言是如何實(shí)現(xiàn)該結(jié)構(gòu)的。
鏈表的元素是由結(jié)構(gòu)體來實(shí)現(xiàn)struct table *p。結(jié)構(gòu)體中有一個(gè)成員是結(jié)構(gòu)體指針struct table *next，而這個(gè)結(jié)構(gòu)體指針的類型和此結(jié)構(gòu)體類型相同。除鏈表最后一個(gè)元素外，每一個(gè)結(jié)構(gòu)體的指針都指向鏈表中下一個(gè)元素的結(jié)構(gòu)體，最后一個(gè)元素的結(jié)構(gòu)體指針為空(NULL)。保存鏈表時(shí)，只需要記錄下鏈表的頭指針，即鏈表中第一個(gè)結(jié)構(gòu)體的地址即可。添加一個(gè)鏈表元素時(shí)，都需要單獨(dú)申請(qǐng)一段內(nèi)存；刪除時(shí)則將其釋放掉。在查找鏈表時(shí)，只需要順著結(jié)構(gòu)體指針的順序一個(gè)一個(gè)往下查找，直到查找的結(jié)構(gòu)體中的成員指針。以下是一個(gè)鏈表結(jié)構(gòu)的示意：
struct Student{
int ID;//學(xué)號(hào)
char[20];//姓名
int marks[5];//5門考試的成績
struct Student *next;//指向下一個(gè)結(jié)構(gòu)體的結(jié)構(gòu)體指針
}
為什么不用結(jié)構(gòu)體數(shù)組
有人會(huì)有問為什么不直接用一個(gè)結(jié)構(gòu)體數(shù)組代替鏈表，結(jié)構(gòu)體數(shù)組占據(jù)的內(nèi)存空間是連續(xù)的，如果使用malloc指令一樣可以動(dòng)態(tài)存儲(chǔ)，而且連續(xù)的內(nèi)存空間肯定比不確定的內(nèi)存空間效果要好。但是如果對(duì)一個(gè)動(dòng)態(tài)數(shù)組插入或者刪除元素的話，它后面的所有元素都需要變動(dòng)位置，因此修改數(shù)組會(huì)比鏈表要難的多。但它的優(yōu)點(diǎn)在于查找方式很靈活，每一個(gè)元素相對(duì)于數(shù)組首元素地址都有一個(gè)偏移量i，因此對(duì)于數(shù)組來說既可以順向查找也可以反向查找，還可以二分法查找。
由于鏈表的每一個(gè)元素都有一段內(nèi)存，這些內(nèi)存未必是連續(xù)的，加上鏈表本身會(huì)比結(jié)構(gòu)體數(shù)組多一個(gè)指向下一個(gè)元素的結(jié)構(gòu)體指針，因此從節(jié)省內(nèi)存的角度看鏈表是不如數(shù)組的。但是鏈表刪除元素的時(shí)候(假設(shè)這個(gè)元素是a[k])只需要a[k-1]的next指針指向a[k+1]，再把a(bǔ)[k]的內(nèi)存釋放即可，非常方便；插入元素的時(shí)候(假設(shè)這個(gè)元素是a[n])，只需要a[n-1]的next指針指向a[n]再將a[n]的指針指向a[n+1]即可，相比于數(shù)組來說只修改了兩個(gè)元素，速度快而且非常方便。
鏈表的操作
鏈表的操作分為——創(chuàng)建表、插入元素、刪除元素、清空表、查找表、打印表。其中插入/刪除的元素可以是一個(gè)也可以說多個(gè)。鏈表從存儲(chǔ)類型上來分可以分為靜態(tài)鏈表和動(dòng)態(tài)鏈表，靜態(tài)鏈表是事先編寫好的鏈表，占用的內(nèi)存是靜態(tài)存儲(chǔ)區(qū)的內(nèi)存，使用時(shí)不可以對(duì)其中的元素進(jìn)行刪減，只能查找；動(dòng)態(tài)鏈表是按照程序要求生成的鏈表，存放于動(dòng)態(tài)存儲(chǔ)區(qū)，結(jié)構(gòu)比較靈活，每一個(gè)元素都占據(jù)一部分存儲(chǔ)空間，如果要?jiǎng)h除元素，則釋放該位置的內(nèi)存；如果要添加元素，則申請(qǐng)一個(gè)結(jié)構(gòu)體內(nèi)存區(qū)的內(nèi)存。
創(chuàng)建表
創(chuàng)建鏈表需要兩個(gè)指針，一個(gè)作為先行指針(*p1)，開辟內(nèi)存并保存結(jié)構(gòu)體的值;一個(gè)作為緩存指針(*p2)，保留先行指針的所有值并且將它的next指向先行指針。構(gòu)建鏈表時(shí)，先行指針賦一個(gè)值，后行指針保存一個(gè)值并且后行指針的next指向先行指針。賦值終止時(shí)，先行指針的next指向NULL，同時(shí)將先行指針賦值給后行指針，鏈表即構(gòu)建完畢
代碼窗口可以通過鍵盤的"←"和"→"查看。
struct Student * input()
{
struct Student *p1,*p2,*head=NULL;
printf("************************動(dòng)態(tài)鏈表實(shí)驗(yàn)***********************\n【輸入動(dòng)態(tài)鏈表】\n");
printf("請(qǐng)依次輸入學(xué)號(hào) 姓名 身高(cm) 體重(kg)（用空格間隔，學(xué)號(hào)輸入0結(jié)束）:\n");
p2=p1=(struct Student *)malloc(LEN);//開辟內(nèi)存
scanf("%d %s %f %f",&p1->ID,&p1->name,&p1->height,&p1->weight);
if(p1->ID==0)return(head);
else head=p1;
while(p1->ID!=0)
{
p2->next=p1;
p2=p1;
p2->BMI=(float)p2->weight/(p2->height/100)/(p2->height/100);//求BMI指數(shù)
p1=(struct Student *)malloc(LEN);//開辟內(nèi)存
scanf("%d %s %f %f",&p1->ID,&p1->name,&p1->height,&p1->weight);
}
p2->next=NULL;
return(head);//返回鏈表頭指針
}
刪除元素
刪除元素鏈表的第n個(gè)元素只需要將第n-1個(gè)元素的next指針指向第n+1個(gè)元素，再將第n個(gè)元素的內(nèi)存釋放即可,我這里是寫的其中一個(gè)例子，根據(jù)關(guān)鍵字學(xué)號(hào)（int stdID）刪除表中的某個(gè)元素，同時(shí)返回刪除后的鏈表首地址（如果刪的是第一個(gè)元素，則鏈表首地址會(huì)變）
代碼窗口可以通過鍵盤的"←"和"→"查看。
struct Student *delate(struct Student *head,int stdID)
{
struct Student *p1,*p2;
if(head->ID==stdID)
{
p1=head->next;
free(head);
return p1;
}//如果刪除的是第一個(gè)元素，比較特殊，需要修改頭指針，其余不動(dòng)
//剩余幾種情況都是修改next結(jié)構(gòu)體指針
for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指針和p2指針同時(shí)查找,p1指向當(dāng)前的學(xué)生，p2保指向了上一個(gè)學(xué)生
{
if(p1->ID==stdID)
{
p2->next=p1->next;//假設(shè)找到了需要?jiǎng)h除的學(xué)生的學(xué)號(hào)，則讓它上一個(gè)學(xué)生的指針指向跳過他的下一個(gè)學(xué)生
free(p1);
return head;
}
}
return NULL;//返回NULL代表沒找到
}
插入元素
插入元素的原理是，假設(shè)要在第n個(gè)元素前插入一個(gè)元素。首先判斷它是不是首元素，如果是，則修改頭指針指向該元素，并將該元素的next指向原來的頭指針。如果不是首元素，是第k個(gè)元素之前插入一個(gè)元素，則將第k-1個(gè)元素的next指針指向插入元素（或者子表）的地址（或者頭指針），將插入元素的next指針（或尾指針）指向第k個(gè)元素。本示例代碼是根據(jù)一個(gè)學(xué)號(hào)（主要關(guān)鍵字）插入一個(gè)元素（或者子表）的函數(shù)，返回鏈表的首地址（因?yàn)槿绻诘谝粋€(gè)元素前面插入，可能改變鏈表的首地址）。
代碼窗口可以通過鍵盤的"←"和"→"查看。
struct Student *insert(struct Student *head,int stdID,struct Student *insertstd)
{
struct Student *p1,*p2,*p;
for(p=insertstd;p->next!=NULL;p=p->next);//找到insert鏈表的最后一個(gè)元素
if(head->ID==stdID)
{
p->next=head;
return insertstd;
}
for(p1=head;p1!=NULL;p2=p1,p1=p1->next)
{
if(p1->ID==stdID)
{
p2->next=insertstd;
p->next=p1;
return head;
}
}
return NULL;
}
代碼及運(yùn)行結(jié)果
完整代碼及注釋如下：
代碼窗口可以通過鍵盤的"←"和"→"查看。
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define LEN sizeof(struct Student)//定義結(jié)構(gòu)體變量的大小為符號(hào)常量LEN
struct Student{
int ID;//學(xué)號(hào)
char name[20];//姓名
float height;//身高
float weight;//體重
float BMI;//BMI指數(shù)，錄入時(shí)不需要計(jì)算
struct Student *next;//指向下一個(gè)結(jié)構(gòu)體
};
struct Student *input();//輸入函數(shù)
void output(struct Student * head);//輸出函數(shù)
struct Student *delate(struct Student *head,int stdID);//刪除一個(gè)元素，返回刪除后表的頭指針
struct Student *insert(struct Student *head,int stdID,struct Student *insertstd);//返回插入元素（子表）后的頭指針
int append(struct Student *head);//插入一個(gè)鏈表，從input函數(shù)輸入
struct Student *isexist(struct Student *head,int stdID);
int main()
{
struct Student *present;//當(dāng)前鏈表的頭指針
int choice;
bool next;
int stdID;
/*
1：插入一個(gè)元素
2：刪除一個(gè)元素
3：續(xù)表
4：查找表
*/
printf("**********動(dòng)態(tài)鏈表實(shí)驗(yàn)**********\n初始化一個(gè)鏈表：\n");
present=input();//當(dāng)前的鏈表指針
do{
printf("請(qǐng)選擇:\n|1：插入元素(子表)\n|2：刪除元素\n|3：續(xù)表\n|4：查找表\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("請(qǐng)輸入插入地點(diǎn)的后一個(gè)同學(xué)的學(xué)號(hào): ");
scanf("%d",&stdID);
if(isexist(present,stdID)==NULL)
{
printf("該學(xué)生不存在!\n");
break;//退出switch語句
}
present=insert(present,stdID,input());
printf("插入元素后的鏈表為:\n");
output(present);
break;
case 2:
printf("請(qǐng)輸入刪除元素的學(xué)號(hào): ");
scanf("%d",&stdID);
if(isexist(present,stdID)==NULL)
{
printf("該學(xué)生不存在!\n");
break;//退出switch語句
}
present=delate(present,stdID);
printf("刪除后的鏈表為:\n");
output(present);
break;
case 3:
append(present);
printf("續(xù)表后的鏈表為：\n");
output(present);
break;
case 4:
printf("當(dāng)前鏈表為：\n");
output(present);
break;
}
printf("是否繼續(xù)(Yes:1,No:0): ");
scanf("%d",&next);
fflush(stdin);
}while(next);
return 0;
}
struct Student * input()
{
struct Student *p1,*p2,*head=NULL;
printf("************************動(dòng)態(tài)鏈表實(shí)驗(yàn)***********************\n【輸入動(dòng)態(tài)鏈表】\n");
printf("請(qǐng)依次輸入學(xué)號(hào) 姓名 身高(cm) 體重(kg)（用空格間隔，學(xué)號(hào)輸入0結(jié)束）:\n");
p2=p1=(struct Student *)malloc(LEN);//開辟內(nèi)存
scanf("%d %s %f %f",&p1->ID,&p1->name,&p1->height,&p1->weight);
if(p1->ID==0)return(head);
else head=p1;
while(p1->ID!=0)
{
p2->next=p1;
p2=p1;
p2->BMI=(float)p2->weight/(p2->height/100)/(p2->height/100);//求BMI指數(shù)
p1=(struct Student *)malloc(LEN);//開辟內(nèi)存
scanf("%d %s %f %f",&p1->ID,&p1->name,&p1->height,&p1->weight);
}
p2->next=NULL;
return(head);//返回鏈表頭指針
}
void output(struct Student *head)
{
struct Student *p;
int num=1;
p=head;//將頭指針地址傳給p
printf("【輸出動(dòng)態(tài)鏈表】\n");
printf("|學(xué)號(hào)\t\t|姓名\t|身高\(yùn)t|體重\t|BMI\n");
while(p!=NULL)
{
printf("%3d|%08d\t|%s\t|%5.2f\t|%5.2f\t|%lf\n",num++,p->ID,p->name,p->height,p->weight,p->BMI);
p=p->next;
}
}
struct Student *delate(struct Student *head,int stdID)
{
struct Student *p1,*p2;
if(head->ID==stdID)
{
p1=head->next;
free(head);
return p1;
}//如果刪除的是第一個(gè)元素，比較特殊，需要修改頭指針，其余不動(dòng)
//剩余幾種情況都是修改next結(jié)構(gòu)體指針
for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指針和p2指針同時(shí)查找,p1指向當(dāng)前的學(xué)生，p2保指向了上一個(gè)學(xué)生
{
if(p1->ID==stdID)
{
p2->next=p1->next;//假設(shè)找到了需要?jiǎng)h除的學(xué)生的學(xué)號(hào)，則讓它上一個(gè)學(xué)生的指針指向跳過他的下一個(gè)學(xué)生
free(p1);
return head;
}
}
return NULL;//返回NULL代表沒找到
}
struct Student *insert(struct Student *head,int stdID,struct Student *insertstd)
{
struct Student *p1,*p2,*p;
for(p=insertstd;p->next!=NULL;p=p->next);//找到insert鏈表的最后一個(gè)元素
if(head->ID==stdID)
{
p->next=head;
return insertstd;
}
for(p1=head;p1!=NULL;p2=p1,p1=p1->next)
{
if(p1->ID==stdID)
{
p2->next=insertstd;
p->next=p1;
return head;
}
}
return NULL;
}
int append(struct Student *head)//插入一個(gè)鏈表，從input函數(shù)輸入
{
struct Student *p;
for(p=head;p->next!=NULL;p=p->next);//找到head鏈表的最后一個(gè)元素
p->next=input();//從input輸入需要添加的元素，可以是1個(gè)或者多個(gè)
return 0;
}
struct Student *isexist(struct Student *head,int stdID)
{
struct Student *p;
for(p=head;p!=NULL;p=p->next)
{
if(p->ID==stdID)
{
return p;
}
}
return NULL;
}
輸出效果如下圖：
到此這篇關(guān)于C語言實(shí)現(xiàn)線性動(dòng)態(tài)(單向)鏈表的示例代碼的文章就介紹到這了,更多相關(guān)C語言 線性動(dòng)態(tài)(單向)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
c語言中字符串分割函數(shù)及實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猚語言中字符串分割函數(shù)及實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要給大家介紹了Linux中利用c語言刪除某個(gè)目錄下文件的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
本篇文章是對(duì)C++中如何用cout輸出hex,oct,dec的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語言實(shí)現(xiàn)系統(tǒng)關(guān)機(jī)注銷功能
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)系統(tǒng)關(guān)機(jī)注銷功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
詳解C語言如何實(shí)現(xiàn)雙向帶頭循環(huán)鏈表
雙向帶頭循環(huán)鏈表應(yīng)該是鏈表中非常方便的一種，可以很容易的在任意位置上進(jìn)行插入和刪除，可以很容易的對(duì)鏈表進(jìn)行管理。本文將利用C語言實(shí)現(xiàn)雙向帶頭循環(huán)鏈表，需要的可以參考一下2022-08-08
數(shù)據(jù)結(jié)構(gòu)之位圖（bitmap）詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之位圖詳解,本文講解了位圖的基本知識(shí)、位圖的實(shí)現(xiàn)方法、位圖的應(yīng)用等內(nèi)容,需要的朋友可以參考下2014-08-08
本文給大家分享的是一個(gè)個(gè)人使用C++編寫的時(shí)間函數(shù)類，主要是實(shí)現(xiàn)了類的定義和調(diào)用，相比較來說還算比較復(fù)雜的時(shí)間類了，推薦給小伙伴們，有需要的朋友可以參考下。2015-03-03
在學(xué)習(xí) C 語言內(nèi)嵌匯編的實(shí)驗(yàn)過程中，發(fā)現(xiàn)內(nèi)嵌匯編極容易造成段錯(cuò)誤。2019-02-02
深入剖析Android中init進(jìn)程實(shí)現(xiàn)的C語言源碼
這篇文章主要介紹了Android中init進(jìn)程實(shí)現(xiàn)的C語言源碼,init屬性服務(wù)在安卓中屬于系統(tǒng)的底層Linux服務(wù),需要的朋友可以參考下2015-07-07
這篇文章主要介紹了C++桶排序，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04