您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C語言怎么實(shí)現(xiàn)線性動(dòng)態(tài)單向鏈表”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“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ú)申請一段內(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)體指針 }
有人會(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)存空間效果要好。但是如果對一個(gè)動(dòng)態(tài)數(shù)組插入或者刪除元素的話,它后面的所有元素都需要變動(dòng)位置,因此修改數(shù)組會(huì)比鏈表要難的多。但它的優(yōu)點(diǎn)在于查找方式很靈活,每一個(gè)元素相對于數(shù)組首元素地址都有一個(gè)偏移量i,因此對于數(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í)不可以對其中的元素進(jìn)行刪減,只能查找;動(dòng)態(tài)鏈表是按照程序要求生成的鏈表,存放于動(dòng)態(tài)存儲(chǔ)區(qū),結(jié)構(gòu)比較靈活,每一個(gè)元素都占據(jù)一部分存儲(chǔ)空間,如果要?jiǎng)h除元素,則釋放該位置的內(nèi)存;如果要添加元素,則申請一個(gè)結(jié)構(gòu)體內(nèi)存區(qū)的內(nèi)存。
創(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("請依次輸入學(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; }
完整代碼及注釋如下:
代碼窗口可以通過鍵盤的"←"和"→"查看。
#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("請選擇:\n|1:插入元素(子表)\n|2:刪除元素\n|3:續(xù)表\n|4:查找表\n"); scanf("%d",&choice); switch(choice) { case 1: printf("請輸入插入地點(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("請輸入刪除元素的學(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("請依次輸入學(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; }
輸出效果如下圖:
到此,相信大家對“C語言怎么實(shí)現(xiàn)線性動(dòng)態(tài)單向鏈表”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。