欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)線性動態(tài)(單向)鏈表的示例代碼

 更新時間:2022年05月16日 10:31:05   作者:非線性光學(xué)元件  
本文主要介紹了C語言實現(xiàn)線性動態(tài)(單向)鏈表的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

什么是鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)里面的一種,線性鏈表是鏈表的一種,線性鏈表的延伸有雙向鏈表和環(huán)形鏈表。在編程語言中優(yōu)化數(shù)據(jù)結(jié)構(gòu)可以在處理大數(shù)據(jù)時大大降低程序的空間復(fù)雜性和時間復(fù)雜性。這里我只用一個簡單的例子——線性單向鏈表為例,說明C語言是如何實現(xiàn)該結(jié)構(gòu)的。

鏈表的元素是由結(jié)構(gòu)體來實現(xiàn)struct table *p。結(jié)構(gòu)體中有一個成員是結(jié)構(gòu)體指針struct table *next,而這個結(jié)構(gòu)體指針的類型和此結(jié)構(gòu)體類型相同。除鏈表最后一個元素外,每一個結(jié)構(gòu)體的指針都指向鏈表中下一個元素的結(jié)構(gòu)體,最后一個元素的結(jié)構(gòu)體指針為空(NULL)。保存鏈表時,只需要記錄下鏈表的頭指針,即鏈表中第一個結(jié)構(gòu)體的地址即可。添加一個鏈表元素時,都需要單獨申請一段內(nèi)存;刪除時則將其釋放掉。在查找鏈表時,只需要順著結(jié)構(gòu)體指針的順序一個一個往下查找,直到查找的結(jié)構(gòu)體中的成員指針。以下是一個鏈表結(jié)構(gòu)的示意:

struct Student{
int ID;//學(xué)號
char[20];//姓名
int marks[5];//5門考試的成績
struct Student *next;//指向下一個結(jié)構(gòu)體的結(jié)構(gòu)體指針
}

為什么不用結(jié)構(gòu)體數(shù)組

有人會有問為什么不直接用一個結(jié)構(gòu)體數(shù)組代替鏈表,結(jié)構(gòu)體數(shù)組占據(jù)的內(nèi)存空間是連續(xù)的,如果使用malloc指令一樣可以動態(tài)存儲,而且連續(xù)的內(nèi)存空間肯定比不確定的內(nèi)存空間效果要好。但是如果對一個動態(tài)數(shù)組插入或者刪除元素的話,它后面的所有元素都需要變動位置,因此修改數(shù)組會比鏈表要難的多。但它的優(yōu)點在于查找方式很靈活,每一個元素相對于數(shù)組首元素地址都有一個偏移量i,因此對于數(shù)組來說既可以順向查找也可以反向查找,還可以二分法查找。

由于鏈表的每一個元素都有一段內(nèi)存,這些內(nèi)存未必是連續(xù)的,加上鏈表本身會比結(jié)構(gòu)體數(shù)組多一個指向下一個元素的結(jié)構(gòu)體指針,因此從節(jié)省內(nèi)存的角度看鏈表是不如數(shù)組的。但是鏈表刪除元素的時候(假設(shè)這個元素是a[k])只需要a[k-1]的next指針指向a[k+1],再把a[k]的內(nèi)存釋放即可,非常方便;插入元素的時候(假設(shè)這個元素是a[n]),只需要a[n-1]的next指針指向a[n]再將a[n]的指針指向a[n+1]即可,相比于數(shù)組來說只修改了兩個元素,速度快而且非常方便。

鏈表的操作

鏈表的操作分為——創(chuàng)建表、插入元素、刪除元素、清空表、查找表、打印表。其中插入/刪除的元素可以是一個也可以說多個。鏈表從存儲類型上來分可以分為靜態(tài)鏈表和動態(tài)鏈表,靜態(tài)鏈表是事先編寫好的鏈表,占用的內(nèi)存是靜態(tài)存儲區(qū)的內(nèi)存,使用時不可以對其中的元素進行刪減,只能查找;動態(tài)鏈表是按照程序要求生成的鏈表,存放于動態(tài)存儲區(qū),結(jié)構(gòu)比較靈活,每一個元素都占據(jù)一部分存儲空間,如果要刪除元素,則釋放該位置的內(nèi)存;如果要添加元素,則申請一個結(jié)構(gòu)體內(nèi)存區(qū)的內(nèi)存。

創(chuàng)建表

創(chuàng)建鏈表需要兩個指針,一個作為先行指針(*p1),開辟內(nèi)存并保存結(jié)構(gòu)體的值;一個作為緩存指針(*p2),保留先行指針的所有值并且將它的next指向先行指針。構(gòu)建鏈表時,先行指針賦一個值,后行指針保存一個值并且后行指針的next指向先行指針。賦值終止時,先行指針的next指向NULL,同時將先行指針賦值給后行指針,鏈表即構(gòu)建完畢
代碼窗口可以通過鍵盤的"←"和"→"查看。

struct Student * input()
{
	struct Student *p1,*p2,*head=NULL; 
	printf("************************動態(tài)鏈表實驗***********************\n【輸入動態(tài)鏈表】\n");
	printf("請依次輸入學(xué)號	姓名  身高(cm)  體重(kg)(用空格間隔,學(xué)號輸入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個元素只需要將第n-1個元素的next指針指向第n+1個元素,再將第n個元素的內(nèi)存釋放即可,我這里是寫的其中一個例子,根據(jù)關(guān)鍵字學(xué)號(int stdID)刪除表中的某個元素,同時返回刪除后的鏈表首地址(如果刪的是第一個元素,則鏈表首地址會變)
代碼窗口可以通過鍵盤的"←"和"→"查看。

struct Student *delate(struct Student *head,int stdID)
{
	struct Student *p1,*p2;
	if(head->ID==stdID)
	{
		p1=head->next;
		free(head);
		return p1;
	}//如果刪除的是第一個元素,比較特殊,需要修改頭指針,其余不動
	//剩余幾種情況都是修改next結(jié)構(gòu)體指針 
	for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指針和p2指針同時查找,p1指向當(dāng)前的學(xué)生,p2保指向了上一個學(xué)生 
	{
		if(p1->ID==stdID)
		{
		 	p2->next=p1->next;//假設(shè)找到了需要刪除的學(xué)生的學(xué)號,則讓它上一個學(xué)生的指針指向跳過他的下一個學(xué)生 
		 	free(p1);
		 	return head; 
		}
	}
	return NULL;//返回NULL代表沒找到 
}

插入元素

插入元素的原理是,假設(shè)要在第n個元素前插入一個元素。首先判斷它是不是首元素,如果是,則修改頭指針指向該元素,并將該元素的next指向原來的頭指針。如果不是首元素,是第k個元素之前插入一個元素,則將第k-1個元素的next指針指向插入元素(或者子表)的地址(或者頭指針),將插入元素的next指針(或尾指針)指向第k個元素。本示例代碼是根據(jù)一個學(xué)號(主要關(guān)鍵字)插入一個元素(或者子表)的函數(shù),返回鏈表的首地址(因為如果在第一個元素前面插入,可能改變鏈表的首地址)。
代碼窗口可以通過鍵盤的"←"和"→"查看。

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鏈表的最后一個元素 
	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; 
}

代碼及運行結(jié)果

完整代碼及注釋如下:
代碼窗口可以通過鍵盤的"←"和"→"查看。

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define LEN sizeof(struct Student)//定義結(jié)構(gòu)體變量的大小為符號常量LEN 
struct Student{
	int ID;//學(xué)號 
	char name[20];//姓名 
	float height;//身高 
	float weight;//體重
	float BMI;//BMI指數(shù),錄入時不需要計算 
	struct Student *next;//指向下一個結(jié)構(gòu)體 
};
struct Student *input();//輸入函數(shù) 
void output(struct Student * head);//輸出函數(shù) 
struct Student *delate(struct Student *head,int stdID);//刪除一個元素,返回刪除后表的頭指針 
struct Student *insert(struct Student *head,int stdID,struct Student *insertstd);//返回插入元素(子表)后的頭指針 
int append(struct Student *head);//插入一個鏈表,從input函數(shù)輸入 
struct Student *isexist(struct Student *head,int stdID);
int main()
{
	struct Student *present;//當(dāng)前鏈表的頭指針 
	int choice;
	bool next;
	int stdID;
	/* 
	1:插入一個元素
	2:刪除一個元素
	3:續(xù)表 
	4:查找表 
	*/ 
	printf("**********動態(tài)鏈表實驗**********\n初始化一個鏈表:\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("請輸入插入地點的后一個同學(xué)的學(xué)號: ");
				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é)號:  ");
				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("************************動態(tài)鏈表實驗***********************\n【輸入動態(tài)鏈表】\n");
	printf("請依次輸入學(xué)號	姓名  身高(cm)  體重(kg)(用空格間隔,學(xué)號輸入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("【輸出動態(tài)鏈表】\n");
	printf("|學(xué)號\t\t|姓名\t|身高\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;
	}//如果刪除的是第一個元素,比較特殊,需要修改頭指針,其余不動
	//剩余幾種情況都是修改next結(jié)構(gòu)體指針 
	for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指針和p2指針同時查找,p1指向當(dāng)前的學(xué)生,p2保指向了上一個學(xué)生 
	{
		if(p1->ID==stdID)
		{
		 	p2->next=p1->next;//假設(shè)找到了需要刪除的學(xué)生的學(xué)號,則讓它上一個學(xué)生的指針指向跳過他的下一個學(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鏈表的最后一個元素 
	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)//插入一個鏈表,從input函數(shù)輸入 
{
	struct Student *p;
	for(p=head;p->next!=NULL;p=p->next);//找到head鏈表的最后一個元素 
	p->next=input();//從input輸入需要添加的元素,可以是1個或者多個
	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語言輸出動態(tài)鏈表結(jié)果1

C語言輸出動態(tài)鏈表結(jié)果2

到此這篇關(guān)于C語言實現(xiàn)線性動態(tài)(單向)鏈表的示例代碼的文章就介紹到這了,更多相關(guān)C語言 線性動態(tài)(單向)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

  • C++深入探究哈希表如何封裝出unordered_set和unordered_map

    C++深入探究哈希表如何封裝出unordered_set和unordered_map

    哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu),該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方,說起來可能感覺有點復(fù)雜,我想我舉個例子你就會明白了,最典型的的例子就是字典
    2022-06-06
  • 通過C++程序示例理解設(shè)計模式中的外觀模式

    通過C++程序示例理解設(shè)計模式中的外觀模式

    這篇文章主要介紹了通過設(shè)計模式中的外觀模式及相關(guān)的C++程序示例,外觀模式在高層提供了一個統(tǒng)一的接口實現(xiàn)一定程度上的解耦,需要的朋友可以參考下
    2016-03-03
  • 詳解C++?OpenCV實現(xiàn)圖像拼接的原理及方法

    詳解C++?OpenCV實現(xiàn)圖像拼接的原理及方法

    本文以實現(xiàn)圖像拼接為目標(biāo),把分割開的圖像進行拼接還原,核心的內(nèi)容包括:OpenCV圖像拼接相關(guān)原理以及OpenCV圖像拼接案例的實現(xiàn),感興趣的可以了解一下
    2022-07-07
  • C++實現(xiàn)Date類各種運算符重載的示例代碼

    C++實現(xiàn)Date類各種運算符重載的示例代碼

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)Date類各種運算符重載的相關(guān)知識,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-02-02
  • C++中不得不說的map容器

    C++中不得不說的map容器

    大家好,本篇文章主要講的是C++中不得不說的map容器,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-02-02
  • C語言中遞歸和排列組合詳解

    C語言中遞歸和排列組合詳解

    大家好,本篇文章主要講的是C語言中遞歸和排列組合詳解,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2022-01-01
  • C語言修煉之路初識指針陰陽竅?地址還歸大道真下篇

    C語言修煉之路初識指針陰陽竅?地址還歸大道真下篇

    指針是指向另一個變量的變量。意思是一個指針保存的是另一個變量的內(nèi)存地址。換句話說,指針保存的并不是普通意義上的數(shù)值,而是另一個變量的地址值。一個指針保存了另一個變量的地址值,就說這個指針“指向”了那個變量
    2022-02-02
  • 人臉檢測中AdaBoost算法詳解

    人臉檢測中AdaBoost算法詳解

    這篇文章主要為大家詳細(xì)介紹了人臉檢測中AdaBoost算法的相關(guān)資料,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • 淺析string類字符串和C風(fēng)格字符串之間的區(qū)別

    淺析string類字符串和C風(fēng)格字符串之間的區(qū)別

    string類是標(biāo)準(zhǔn)庫的類,并不是內(nèi)置類型,標(biāo)準(zhǔn)庫就像是我們自己定義的類差不多的,string類型對象沒有標(biāo)配'\0'結(jié)尾的
    2013-09-09
  • 最新評論