数据类型——链表的简单实现（C语言实现链表）

目录

一.链表是什么

二.以一个例子来引入链表

1.元素存储方式

2.显示全部电影

3.创建链表

4.释放链表

三.整体代码：

一.链表是什么

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

简单来说，链表中的每个项在内存中并不是连续存储的，在链表中的每一项中都保存着下一项的地址，用来找到下一项的位置，那么，为了找到第一个项的位置，就得有一个头指针，他用来找到链表第一个项数的位置，链表就是由头指针和项数组成的，那么，根据这一简要介绍，我们就应该能够知道，链表中的每一项都要包含内容和下一项的地址，也就是说，链表的每一项是一个结构体，其中包含这两个东西，下面用一张图来让大家对链表有更加深入的了解。

二.以一个例子来引入链表

现在我们来试试用链表来存储电影名字，并且存储对应的评分。

首先如果有不认识malloc函数以及free函数的话建议先进行了解，这是一个前提。

malloc和free函数认识——菜鸟教程https://www.runoob.com/?s=malloc有一定编程基础的同学建议先观看整体代码自行分析一下然后再看详细解答，效果更好！

跳转链接(点击跳转）：> 三.整体代码：

1.元素存储方式

首先，这种存储电影名字和评分肯定需要用到结构体，另外，为了实现链表，每个结构体中必须要有能够找到下一个结构体的地址，所以在定义结构体类型时结构体中也要含有一个相同结构体类型的指针变量，因此，结构题定义如下:

typedef struct film
{
	char name[20];
	float score;
	struct film* next;
}Film;//运用struct使得类型名更简洁

我们需要用该程序完成两个任务，将用户输入的数据存到链表中，然后显示其中的内容。对比将用户输入的数据存入链表，显示链表更加简单。

2.显示全部电影

既然要显示全部内容，那么肯定要从头指针开始通过地址逐渐往下找链表，知道找到最下面的结构体其中的指针成员是NULL，那么就意味着已经到达了链表的最后一项，将其打印出来之后显示功能就完成了，具体实现如下：

film * current = head;
//current指的是当前程序正在处理的链表项
//第一个需要处理的项通过头指针来找到
if(current == NULL)
    printf("this chain table has not elements"\n)
    //如果头指针为空，那么就意味着链表没有项
else
{
    while(current !=NULL)
    {
        printf("%s %.2lf\n",current->name,current->score);
        current = current -> next;
    }
}

这里有一个问题：为什么这里要新建一个current指针来遍历整个链表呢？为什么不直接用头指针来遍历呢？

原因很简单，由于创建链表的时候用malloc来动态分配内存，所以在程序的最后需要用free来释放已分配的内存，如果在显示链表阶段就改变了头指针，那么在后期释放链表时就无法找到链表的首项，也就无法完成释放内存的过程，所以这里用current指针来遍历数组。

3.创建链表

创建链表有3个步骤：

使用malloc动态分配内存空间
将新分配的结构放入到链表中(也就是存储结构的地址)
拷贝当前的信息

没有必要每次都创建结构(由于该程序用输入空行来模拟结束，如果每次都创建结构，那么最后的空行也会被一个新的结构存储起来，这样就浪费了空间，所以我们用临时处理区（input数组）来存储信息），获取用户输入的信息。

这里获取电影信息使用了一个gets和fgets的结合版s_gets()，这个函数结合了fgets和gets的优点，代码如下：

char* s_gets(char * s,int n)
{
    char * rel;
    char * find;
    rel = fgets(s,n,stdin);
    if(rel)
    {
        find = strchr(s,'\n);
        if(find)
            *find = '\0';
        else
            while(getchar()!='\n')
                continue;
    }
    return rel;
}

当用户输入EOF或者输入一段空行时，通过以下判断跳出循环：

while(s_gets(input,SIZE)!=NULL&&input[0]=='\0')
//s_gets(input,SIZE) == NULL 代表用户输入EOF
//input[0]=='\0' 代表用户输入空行

如果用户输入了内容，那么就分配一个电影结构的内存空间，将其地址赋给current，然后再对current进行操作。

current = (Film *)malloc(sizeof(Film));

然后我们需要判断头指针是否为空，如果为空，那么这个结构的地址就最为头指针存在，如果不为空，就将其放到链表的下一项，并且将标识链表最后一项的指针指向该项。

完整代码如下：

puts("please enter the first movie:>");
	while (s_gets(input, size) != EOF && input[0] != '\0')
	{
		current = (Film*)malloc(sizeof(Film));
		if (head == NULL)
			head = current;
		else
		{
			pre->next = current;
		}
		current->next = NULL;
		strcpy(current->name, input);
		puts("please enter your score:>");
		scanf("%lf", &current->score );
		while (getchar() != '\n')
			continue;
		pre = current;
		puts("please enter the next movie : >");
	}

4.释放链表

在显示链表模块已经提到了链表需要释放的问题，这里进行详细操作的演示。

首先，由于释放之后就不需要再使用链表，所以可以直接对头指针进行操作，另外，由于释放后当前指针会被设置为空，所以还需要一个指针在链表该项被释放之前指向链表的下一项，然后将用来释放的指针索引指向该项，如此循环直至指针索引为空为止。

代码如下：

current = head;
	while (current != NULL)
	{
        //先找到链表的下一项
		current = head->next;
        //释放该项
		free(head);
        //用于释放的指针索引移动到下一项
		head = current;
	}
		return 0;

到此，链表制作任务就全部完成了，下面附上全部代码：

三.整体代码：

#define _CRT_SECURE_NO_WARNINGS 1
#define size 20

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct film
{
	char name[20];
	double score;
	struct film* next;
}Film;

char* s_gets(char* s, int n)
{
	char* rel;
	char* find;
	rel = fgets(s, n, stdin);
	if (rel != NULL)
	{
		if (find = strchr(rel, '\n'))
			*find = '\0';
		else
			while (getchar() != '\n')
				continue;
	}
	return rel;
}

int main(void)
{
	Film* head = NULL;
	Film* current;
	Film* pre = NULL;
	char input[size];

	//储存电影信息
	puts("please enter the first movie:>");
	while (s_gets(input, size) != EOF && input[0] != '\0')
	{
		current = (Film*)malloc(sizeof(Film));
		if (head == NULL)
			head = current;
		else
		{
			pre->next = current;
		}
		current->next = NULL;
		strcpy(current->name, input);
		puts("please enter your score:>");
		scanf("%lf", &current->score );
		while (getchar() != '\n')
			continue;
		pre = current;
		puts("please enter the next movie : >");
	}


//显示电影列表
	if (head == NULL)
		printf("No film in list");
	else
	{
		current = head;
		while (current != NULL)
		{
			printf("%s %.2lf\n", current->name, current->score);
			current = current->next;
		}
	}

	//因为用了malloc,所以需要释放所用的内存
	current = head;
	while (current != NULL)
	{
		current = head->next;
		free(head);
		head = current;
	}
		return 0;
}

以上就是链表方面的基本内容啦，当然只是小部分内容，之后作者还会用一篇文章来讲述链表ADT（抽象数据类型）的实现，敬请期待！！！