C语言链表详解附实例

什么是链表

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。链表和数组比较，不用事先确定存储空间，而是根据需要开辟内存单元。
下图1是最简单的一种链表（单向链表）的结构

第 0 个结点称为头结点，它存放有第一个结点的首地址，它没有数据，只是一个指针变量。以下的每个结点都分为两个域，一个是数据域，存放各种实际的数据，如学号 num，姓名 name，性别 sex 和成绩 score 等。另一个域为指针域，存放下一结点的首地址。链表中的每一个结点都是同一种结构类型。

环境构建

用的Visual Studio 2019软件

在源文件中添加C文件

建立静态链表

包含所需要的头文件

#include<stdio.h> //标准输入输出头文件
#include<stdlib.h>//包含了C、C++语言的最常用的系统函数

宏定义相关变量

#define LEN sizeof(struct Student)//宏定义节点长度得命名
#define TYPE struct Student//宏定义结构体变量命名

创建一个结构体

struct Student//定义一个学生类型结构体，包括学号，分数
{
	long num;
	float score;
	struct Student* next;//next是指针变量，指向结构体变量
};
//指向结构体对象得指针变量既可以指向结构体变量，也可以指向结构体数组中得元素

主函数

int main()
{
	TYPE* head,*p;//定义头指针
	struct Student a,b,c;//定义三个结构体变量
	a.num = 101; a.score = 20;//分别对三个结点赋值
	b.num = 102; b.score = 20;
	c.num = 103; c.score = 20;
	/*1、A.B则A为对象或者结构体
      2、A->B则A为指针，->是成员提取，A->B是提取A中的成员B，A只能是指向类、结构、联合的指针；*/
	head = &a;
	a.next = &b;
	b.next = &c;
	c.next = NULL;
	p = head;//把首地址给变量
	do
	{
		printf("%ld %5.1f\n",p->num,p->score);//输出每个结点信息
		p = p->next;//使P指向下一个结点
	} while (p != NULL);//直到指针域指向空值
	return 0;
}

结果展示

说明

将第一个结点的起始地址赋值给头指针head,将第二个结点的起始地址赋值给第一个结点的next成员，将第二个结点的起始地址赋给第一个结点的next…第三个结点的next赋值为NULL，这就形成了简单的链表。

建立动态链表

所谓建立动态链表是指在程序执行过程中从无到有地建立起一个 链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相连的关系。

包含所需要的头文件

#include<stdio.h> //标准输入输出头文件
#include<stdlib.h>//包含了C、C++语言的最常用的系统函数
#include<malloc.h>//动态存储分配函数头文件

宏定义相关变量

#define LEN sizeof(struct Student)//宏定义节点长度得命名
#define TYPE struct Student//宏定义结构体变量命名

创建一个结构体

struct Student//定义一个学生类型结构体，包括学号，分数
{
	long num;
	float score;
	struct Student* next;//next是指针变量，指向结构体变量
};
//指向结构体对象得指针变量既可以指向结构体变量，也可以指向结构体数组中得元素

建立链表函数

TYPE* Creat(void)//定义函数，此函数返回一个指向链表头的指针
{
	TYPE* head;//定义头指针
	TYPE* p1,*p2;//定义两个 指针变量用来相互保存
	number = 0;//开始时，结点清零
	p1 = p2 = (TYPE*)malloc(LEN);//创建存储空间
	printf("请按格式输入学生学号，分数\n");//输出提示信息
	printf("例如101,1 并以0,0结束\n");
	scanf("%ld,%f", &p1->num, &p1->score);//按格式输入第一个结点的信息
	head = NULL;//第一个结点头指针赋空值
	while (p1->num!=0)//循环直到输入学生学号为0，就结束
	{
		number++;//结点自增
		if (number == 1)//如果只有一个结点，那么头指针指向第一个输入的结点
			head = p1;
		else
			p2->next = p1;//如果大于1个，那么要用next保存前一个结点的信息
		p2 = p1;//保存前一个结点信息
		p1 = (TYPE*)malloc(LEN);//开辟新的结点
		scanf("%ld,%f", &p1->num, &p1->score);//输入下一个结点信息
	}
	p2->next = NULL;//循环结束，将指向信息赋空值
	return (head);//返回首地址
}

主函数

int main()
{
	TYPE* pt;//定义一个结构体指针变量
	pt = Creat();//函数返回链表第一个结点的地址
	printf("\nnum:%ld\nscore:%5.lf\n", pt->num,pt->score);//输出第一个结点的成员值
	return 0;
}

结果展示

== 文中最后结果显示的是第一个结点的内容，作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。==

链表的输出

用循环直接可以输出链表

输出函数

void print(TYPE * head)
{
	TYPE * p;//定义指针
	printf("\nNOW These %d records are:\n");//输出显示信息
	p = head;//使p指向第一个结点
	if(head!=NULL)//输出第一个结点后的信息
		do {
			printf("%ld %5.1f\n",p->num,p->score);
			p = p->next;//指向下个结点
		} while (p != NULL);
}

主函数

int main()
{
	TYPE * pt;//定义一个结构体指针变量
	pt = Creat();//函数返回链表第一个结点的地址
	print(pt);//输出调用
	return 0;
}

链表的修改

修改函数

修改链表节点值很简单。下面是一个传入链表和要修改的节点，来修改值的函数.

void change(TYPE* head, int n) //修改指定位置的结点的信息
{
	TYPE* p = head;//传入首地址
	int i = 0;
	while (i < n && p != NULL) {
		p = p->next;
		i++;
	}//找到相应的位置结点
	if (p != NULL) {
		printf("输入要修改的值\n");
		scanf("%ld,%f", &p->num, &p->score);//输入下一个结点信息
	}
	else 
		printf("节点不存在\n");
	}

主函数

int main()
{
	TYPE* pt;//定义一个结构体指针变量
	pt = Creat();//函数返回链表第一个结点的地址
	change(pt,2);//修改相关结点的信息,假设修改第2+1个
	print(pt);//输出调用
	return 0;
}

##链表的删除
删除链表的元素也就是把前节点的指针域越过要删除的节点指向下下个节点。即：p->next = q->next;然后放出q节点的空间，即free(q);

删除函数

void delet(TYPE* head, int n) {
	TYPE* p = head, * in;//定义两边指针
	int i = 0;
	while (i < n && p != NULL) {
		in = p;//找到左边的
		p = p->next;//找到右边的
		i++;
	}
	if (p != NULL) {
		in->next = p->next;//将左右链接
		free(p);//释放中间结点
	}
	else {
		printf("节点不存在\n");
	}

}

主函数

int main()
{
	TYPE* pt;//定义一个结构体指针变量
	pt = Creat();//函数返回链表第一个结点的地址
	delet(pt,1);//删除第1+1个结点
	print(pt);//输出调用
	return 0;
}

输出结果

##链表的插入
我们可以看出来，插入节点就是用插入前节点的指针域链接上插入节点的数据域，再把插入节点的指针域链接上插入后节点的数据域。根据图，插入节点也就是：e->next = head->next; head->next = e;
增加链表节点用到了两个结构体指针和一个int数据。

插入函数

void insert(TYPE* head, int n) {//链表的插入
	TYPE* p = head, * in;
	int i = 0;
	while (i < n && p != NULL) {
		p = p->next;
		i++;//找到相应结点
	}
	if (p != NULL) {
		in = (TYPE*)malloc(sizeof(TYPE));//开辟新的空间
		printf("输入要插入的值\n");
		scanf("%ld,%f", &in->num, &in->score);//输入新的结点信息
		in->next = p->next;//填充in节点的指针域，也就是说把in的指针域指向p的下一个节点
		p->next = in;//填充p节点的指针域，把p的指针域重新指向in
	}
	else {
		printf("节点不存在\n");
	}

}

主函数

int main()
{
	TYPE* pt;//定义一个结构体指针变量
	pt = Creat();//函数返回链表第一个结点的地址
	insert(pt, 1);//从1+1后插入
	print(pt);//输出调用
	return 0;
}

结果显示

出现的问题

1、出现scanf 和printf 在VS2019中使用时会出错，解决办法如下

最后是测试的所有源程序

链接: https://download.csdn.net/download/xiaoxiaodawei/12242402.