C语言线性动态(单向)链表

时间:2022-06-02 非线性光学元件人气:2

什么是链表

链表是数据结构里面的一种，线性链表是链表的一种，线性链表的延伸有双向链表和环形链表。在编程语言中优化数据结构可以在处理大数据时大大降低程序的空间复杂性和时间复杂性。这里我只用一个简单的例子——线性单向链表为例，说明C语言是如何实现该结构的。

链表的元素是由结构体来实现struct table *p。结构体中有一个成员是结构体指针struct table *next，而这个结构体指针的类型和此结构体类型相同。除链表最后一个元素外，每一个结构体的指针都指向链表中下一个元素的结构体，最后一个元素的结构体指针为空(NULL)。保存链表时，只需要记录下链表的头指针，即链表中第一个结构体的地址即可。添加一个链表元素时，都需要单独申请一段内存；删除时则将其释放掉。在查找链表时，只需要顺着结构体指针的顺序一个一个往下查找，直到查找的结构体中的成员指针。以下是一个链表结构的示意：

struct Student{
int ID;//学号
char[20];//姓名
int marks[5];//5门考试的成绩
struct Student *next;//指向下一个结构体的结构体指针
}

为什么不用结构体数组

有人会有问为什么不直接用一个结构体数组代替链表，结构体数组占据的内存空间是连续的，如果使用malloc指令一样可以动态存储，而且连续的内存空间肯定比不确定的内存空间效果要好。但是如果对一个动态数组插入或者删除元素的话，它后面的所有元素都需要变动位置，因此修改数组会比链表要难的多。但它的优点在于查找方式很灵活，每一个元素相对于数组首元素地址都有一个偏移量i，因此对于数组来说既可以顺向查找也可以反向查找，还可以二分法查找。

由于链表的每一个元素都有一段内存，这些内存未必是连续的，加上链表本身会比结构体数组多一个指向下一个元素的结构体指针，因此从节省内存的角度看链表是不如数组的。但是链表删除元素的时候(假设这个元素是a[k])只需要a[k-1]的next指针指向a[k+1]，再把a[k]的内存释放即可，非常方便；插入元素的时候(假设这个元素是a[n])，只需要a[n-1]的next指针指向a[n]再将a[n]的指针指向a[n+1]即可，相比于数组来说只修改了两个元素，速度快而且非常方便。

链表的操作

链表的操作分为——创建表、插入元素、删除元素、清空表、查找表、打印表。其中插入/删除的元素可以是一个也可以说多个。链表从存储类型上来分可以分为静态链表和动态链表，静态链表是事先编写好的链表，占用的内存是静态存储区的内存，使用时不可以对其中的元素进行删减，只能查找；动态链表是按照程序要求生成的链表，存放于动态存储区，结构比较灵活，每一个元素都占据一部分存储空间，如果要删除元素，则释放该位置的内存；如果要添加元素，则申请一个结构体内存区的内存。

创建表

创建链表需要两个指针，一个作为先行指针(*p1)，开辟内存并保存结构体的值;一个作为缓存指针(*p2)，保留先行指针的所有值并且将它的next指向先行指针。构建链表时，先行指针赋一个值，后行指针保存一个值并且后行指针的next指向先行指针。赋值终止时，先行指针的next指向NULL，同时将先行指针赋值给后行指针，链表即构建完毕
代码窗口可以通过键盘的"←"和"→"查看。

struct Student * input()
{
	struct Student *p1,*p2,*head=NULL; 
	printf("************************动态链表实验***********************\n【输入动态链表】\n");
	printf("请依次输入学号	姓名  身高(cm)  体重(kg)（用空格间隔，学号输入0结束）:\n");
	p2=p1=(struct Student *)malloc(LEN);//开辟内存 
	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指数 
		p1=(struct Student *)malloc(LEN);//开辟内存 
		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个元素的内存释放即可,我这里是写的其中一个例子，根据关键字学号（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结构体指针 
	for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指针和p2指针同时查找,p1指向当前的学生，p2保指向了上一个学生 
	{
		if(p1->ID==stdID)
		{
		 	p2->next=p1->next;//假设找到了需要删除的学生的学号，则让它上一个学生的指针指向跳过他的下一个学生 
		 	free(p1);
		 	return head; 
		}
	}
	return NULL;//返回NULL代表没找到 
}

插入元素

插入元素的原理是，假设要在第n个元素前插入一个元素。首先判断它是不是首元素，如果是，则修改头指针指向该元素，并将该元素的next指向原来的头指针。如果不是首元素，是第k个元素之前插入一个元素，则将第k-1个元素的next指针指向插入元素（或者子表）的地址（或者头指针），将插入元素的next指针（或尾指针）指向第k个元素。本示例代码是根据一个学号（主要关键字）插入一个元素（或者子表）的函数，返回链表的首地址（因为如果在第一个元素前面插入，可能改变链表的首地址）。
代码窗口可以通过键盘的"←"和"→"查看。

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; 
}

代码及运行结果

完整代码及注释如下：
代码窗口可以通过键盘的"←"和"→"查看。

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define LEN sizeof(struct Student)//定义结构体变量的大小为符号常量LEN 
struct Student{
	int ID;//学号 
	char name[20];//姓名 
	float height;//身高 
	float weight;//体重
	float BMI;//BMI指数，录入时不需要计算 
	struct Student *next;//指向下一个结构体 
};
struct Student *input();//输入函数 
void output(struct Student * head);//输出函数 
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函数输入 
struct Student *isexist(struct Student *head,int stdID);
int main()
{
	struct Student *present;//当前链表的头指针 
	int choice;
	bool next;
	int stdID;
	/* 
	1：插入一个元素
	2：删除一个元素
	3：续表 
	4：查找表 
	*/ 
	printf("**********动态链表实验**********\n初始化一个链表：\n");
	present=input();//当前的链表指针
	do{
		printf("请选择:\n|1：插入元素(子表)\n|2：删除元素\n|3：续表\n|4：查找表\n");
		scanf("%d",&choice); 
		switch(choice)	
		{
			case 1:
				printf("请输入插入地点的后一个同学的学号: ");
				scanf("%d",&stdID);
				if(isexist(present,stdID)==NULL)
				{
					printf("该学生不存在!\n");
					break;//退出switch语句 
				}
				present=insert(present,stdID,input());
				printf("插入元素后的链表为:\n");	
				output(present);
				break;
			case 2:
				printf("请输入删除元素的学号:  ");
				scanf("%d",&stdID);
				if(isexist(present,stdID)==NULL)
				{
					printf("该学生不存在!\n");
					break;//退出switch语句 
				}
				present=delate(present,stdID);
				printf("删除后的链表为:\n"); 	
				output(present);
				break;
			case 3:
				append(present);
				printf("续表后的链表为：\n");
				output(present);
				break;
			case 4:
				printf("当前链表为：\n"); 
				output(present);
				break;
		}
		printf("是否继续(Yes:1,No:0):  ");
		scanf("%d",&next);
		fflush(stdin);
	}while(next);

	 
	return 0;	
} 
struct Student * input()
{
	struct Student *p1,*p2,*head=NULL; 
	printf("************************动态链表实验***********************\n【输入动态链表】\n");
	printf("请依次输入学号	姓名  身高(cm)  体重(kg)（用空格间隔，学号输入0结束）:\n");
	p2=p1=(struct Student *)malloc(LEN);//开辟内存 
	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指数 
		p1=(struct Student *)malloc(LEN);//开辟内存 
		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("【输出动态链表】\n");
	printf("|学号\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结构体指针 
	for(p1=head;p1!=NULL;p2=p1,p1=p1->next)//p1指针和p2指针同时查找,p1指向当前的学生，p2保指向了上一个学生 
	{
		if(p1->ID==stdID)
		{
		 	p2->next=p1->next;//假设找到了需要删除的学生的学号，则让它上一个学生的指针指向跳过他的下一个学生 
		 	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函数输入 
{
	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语言输出动态链表结果1

C语言输出动态链表结果2

加载全部内容

C语言 线性动态(单向)链表