C语言数据结构C语言当中的链表，什么是链表，链表的三要素，创建一个链表，查找链表当中的元素，删除指定的结点的链表，链表的插入（向链表当中插入元素）_c语言链表结构体定义

链表：

一、什么是链表：

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

在这里要注意：

首先看一下定义：
-> ：->是C语言和C++语言的一个运算符，叫做指向结构体成员运算符，用处是使用一个指向结构体或对象的指针访问其内成员。

. 并不是一个运算符，它只是一个断点符号，它指向的是结构体或者对象。

-> 是通过一个结构体或对象指针来访问他们的内部成员变量；
.是直接通过结构体或对象来访问他们的内部成员变量。
a->b读作a指向结构体的b
a.b读作a的b

二、链表的三要素：

头指针（head）:头指针是用来说明链表的开始了，头指针就代表了链表本身，所以要访问链表，就要访问头指针。
头指针就代表公司老板。老板就代表头指针。
结点（node）：链表当中每一个变量被称为结点
尾指针：用来说明链表结束（它是一个空指针，NULL）

注意：在定义结构体的时候有没有该结构类型的指针

三、如果来创建一个链表

1、用函数来创建一个链表（返回值为创建的那个链表，也就是要返回头指针 ）
举例：返回指针的函数
函数返回指针就必须在该函数名称之前

int *sum(int a,int b){//这个函数返回的是int类型指针
}
1
2

案例一、

创建一个链表模拟图如下

#include<stdio.h> 
#include<string.h> 
typedef struct stud{
	char Id[10];//学号 
	char Name[10];//姓名
	//这个指针的类型是结构体类型，以后这个指针就只能够指向struct stud这种结构体类型的变量 
	struct stud *Next;
}STU;
//定义了一个返回值类型为结构体类型的函数 
//因为传入的是地址值所以可以理解成为传入的是对象，即对应地址值内存当中的东西 
STU *CreateLink(STU a[],int n)//要返回链表实际上就是要返回头指针 
{
	STU *head;//定义一个结构体类型的头指针 
	head = &a[0];//把数组a当中的第一个元素地址值赋值给头，让头指针指向第一个结点
	//用循环 把前一个结点与后一个结点通过next指针联系起来
	//结点可以是一个对象，一个结构体，一个变量，一个指针地址 
	int i;
	for(i=0;i<n;i++){
	//让每一个next结点 （结构对应的结果体指针）指向下一个结构的头结点 
		a[i].Next=&a[i+1];
	}
	a[n-1].Next=NULL;//将结构体末尾指针指向的NULL 	
	return head;//返回头指针 ，实际上就代表链表本身  
} 
//输出链表当中的所有结点的值 
void OutputLink(STU *head){//参数是一个链表，这里的链表实际上就是需要头指针  
    //将链表的头指针赋值给指针p 
	//head头指针不可以动，所以要将头指针的地址值赋值给p指针通过p指针来访问链表当中的数据
	STU *p=head; 
	printf("学号\t姓名\n");
	while(p!=NULL){//当访问的结点不到末尾的时候 
		printf("%s\t%s\n",p->Id,p->Name);
		p=p->Next;//把指针p移动到下一个结点 
	}
} 
void main(){
	STU a[8]={
	{"S1","张一军"}, 
	{"S2","张二军"}, 
	{"S3","张三军"}, 
	{"S4","张四军"}, 
	{"S5","张五军"}, 
	{"S6","张六军"}, 
	{"S7","张七军"},  
	{"S8","张八军"}
	},*head;
	//现在还是只是一个数组不是链表，所以要调用 CreateLink来创建一个链表
	head = CreateLink(a,8); 
	OutputLink(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

查找在链表当中的一个指定的值

#include<stdio.h> 
#include<string.h> 
typedef struct stud{
	char Id[10];//学号 
	char Name[10];//姓名
	//这个指针的类型是结构体类型，以后这个指针就只能够指向struct stud这种结构体类型的变量 
	struct stud *Next;
}STU;
//定义了一个返回值类型为结构体类型的函数 
//因为传入的是地址值所以可以理解成为传入的是对象，即对应地址值内存当中的东西 
STU *CreateLink(STU a[],int n)//要返回链表实际上就是要返回头指针 
{
	STU *head;//定义一个结构体类型的头指针 
	head = &a[0];//把数组a当中的第一个元素地址值赋值给头，让头指针指向第一个结点
	//用循环 把前一个结点与后一个结点通过next指针联系起来
	//结点可以是一个对象，一个结构体，一个变量，一个指针地址 
	int i;
	for(i=0;i<n;i++){
	//让每一个next结点 （结构对应的结果体指针）指向下一个结构的头结点 
		a[i].Next=&a[i+1];
	}
	a[n-1].Next=NULL;//将结构体末尾指针指向的NULL 	
	return head;//返回头指针 ，实际上就代表链表本身  
} 
//输出链表当中的所有结点的值 
void OutputLink(STU *head){//参数是一个链表，这里的链表实际上就是需要头指针  
    //将链表的头指针赋值给指针p 
	//head头指针不可以动，所以要将头指针的地址值赋值给p指针通过p指针来访问链表当中的数据
	STU *p=head; 
	printf("学号\t姓名\n");
	while(p!=NULL){//当访问的结点不到末尾的时候 
		printf("%s\t%s\n",p->Id,p->Name);
		p=p->Next;//把指针p移动到下一个结点 
	}
} 
void FindById(STU *head,char Id[]){//在一个链表当中查找指定的工号对应的值 	
	//要访问链表当中的所有结点
	STU *p = head;//把链表的头指针赋值给
	while(p!=NULL){
		//p就代表链表当中的每一个结点，如果p所指向的那个结点的id与我们要找的id相同的话，则要退出循环 
		if(strcmp(p->Id,Id)==0){
			break;//说明找到了，就退出循环，就没有必要再循环，就强制的退出循环。 
		}				
		p=p->Next;//这时指针指向的就是找到的结构体或者叫结点 
	} 
	// 退出循环之后，再来判断是否找到了
	if(p==NULL){//表示没有找到 
		printf("找不到此人");
	}else{
		//输出指针所指向那个结点的值
		printf("%s\t%s\t",p->Id,p->Name); 
	}	
}
void main(){
	STU a[8]={
	{"S1","张一军"}, 
	{"S2","张二军"}, 
	{"S3","张三军"}, 
	{"S4","张四军"}, 
	{"S5","张五军"}, 
	{"S6","张六军"}, 
	{"S7","张七军"},  
	{"S8","张八军"}
	},*head;
	char Id[100]; 
	//现在还是只是一个数组不是链表，所以要调用 CreateLink来创建一个链表
	head = CreateLink(a,8); 
	//输出链表 
	OutputLink(head);
	printf("请输入一个工号S1-S8:");	
	gets(Id);//从键盘获取对应的Id以回车为结束
	FindById(head,Id); 	 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

删除指定的结点的链表

删除结点的模拟图如下

#include<stdio.h> 
#include<string.h> 
typedef struct stud{
	char Id[10];//学号 
	char Name[10];//姓名
	//这个指针的类型是结构体类型，以后这个指针就只能够指向struct stud这种结构体类型的变量 
	struct stud *Next;
}STU;
//定义了一个返回值类型为结构体类型的函数 
//因为传入的是地址值所以可以理解成为传入的是对象，即对应地址值内存当中的东西 
STU *CreateLink(STU a[],int n)//要返回链表实际上就是要返回头指针 
{
	STU *head;//定义一个结构体类型的头指针 
	head = &a[0];//把数组a当中的第一个元素地址值赋值给头，让头指针指向第一个结点
	//用循环 把前一个结点与后一个结点通过next指针联系起来
	//结点可以是一个对象，一个结构体，一个变量，一个指针地址 
	int i;
	for(i=0;i<n;i++){
	//让每一个next结点 （结构对应的结果体指针）指向下一个结构的头结点 
		a[i].Next=&a[i+1];
	}
	a[n-1].Next=NULL;//将结构体末尾指针指向的NULL 	
	return head;//返回头指针 ，实际上就代表链表本身  
} 
//输出链表当中的所有结点的值 
void OutputLink(STU *head){//参数是一个链表，这里的链表实际上就是需要头指针  
    //将链表的头指针赋值给指针p 
	//head头指针不可以动，所以要将头指针的地址值赋值给p指针通过p指针来访问链表当中的数据
	STU *p=head; 
	printf("学号\t姓名\n");
	while(p!=NULL){//当访问的结点不到末尾的时候 
		printf("%s\t%s\n",p->Id,p->Name);
		p=p->Next;//把指针p移动到下一个结点 
	}
} 
//链表的删除
/*
1、必须要找到要删除的结点
2、删除对应的结点
3：该函数要返回删除之后的新链表，实际上是返回头指针 
*/ 
STU *DelById(STU *head,char Id[]){//根据工号删除对应链表中的一个结点 
	//必须要找到该结点
	STU *p=head,*front;
	while(p!=NULL){
		if(strcmp(p->Id,Id) == 0){//如果p所指向的结点等于Id要删除的Id的话 
			break;//就退出循环 
		}
		//在p移动之前，要保留以前的位置
		front=p; 
		p=p->Next;//p移动到下一个结点 
	} 
	if(p!=NULL){//找到了要删除的结点
		front->Next=p->Next; 
	}
	return head;
}
void main(){
	STU a[8]={
	{"S1","张一军"}, 
	{"S2","张二军"}, 
	{"S3","张三军"}, 
	{"S4","张四军"}, 
	{"S5","张五军"}, 
	{"S6","张六军"}, 
	{"S7","张七军"},  
	{"S8","张八军"}
	},*head;
	char Id[100]; 
	//现在还是只是一个数组不是链表，所以要调用 CreateLink来创建一个链表
	head = CreateLink(a,8); 
	//输出链表 
	OutputLink(head);
	printf("请输入一个工号S1-S8:");	
	gets(Id);//从键盘获取对应的Id以回车为结束
	head = DelById(head,Id);//表示在调用 DelById在删除一个结点，但是看不到效果
	//再次输出对应的链表 
	OutputLink(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

链表的插入（向链表当中插入元素）

1、找到要插入链表的位置（有两个位置）
2、执行插入操作




算法实现

#include<stdio.h> 
#include<string.h> 
typedef struct stud{
	char Id[10];//学号 
	char Name[10];//姓名
	int Age;//年龄 
	//这个指针的类型是结构体类型，以后这个指针就只能够指向struct stud这种结构体类型的变量 
	struct stud *Next;
}STU;
//定义了一个返回值类型为结构体类型的函数 
//因为传入的是地址值所以可以理解成为传入的是对象，即对应地址值内存当中的东西 
STU *CreateLink(STU a[],int n)//要返回链表实际上就是要返回头指针 
{
	STU *head;//定义一个结构体类型的头指针 
	head = &a[0];//把数组a当中的第一个元素地址值赋值给头，让头指针指向第一个结点
	//用循环 把前一个结点与后一个结点通过next指针联系起来
	//结点可以是一个对象，一个结构体，一个变量，一个指针地址 
	int i;
	for(i=0;i<n;i++){
	//让每一个next结点 （结构对应的结果体指针）指向下一个结构的头结点 
		a[i].Next=&a[i+1];
	}
	a[n-1].Next=NULL;//将结构体末尾指针指向的NULL 	
	return head;//返回头指针 ，实际上就代表链表本身  
} 
//输出链表当中的所有结点的值 
void OutputLink(STU *head){//参数是一个链表，这里的链表实际上就是需要头指针  
    //将链表的头指针赋值给指针p 
	//head头指针不可以动，所以要将头指针的地址值赋值给p指针通过p指针来访问链表当中的数据
	STU *p=head; 
	printf("学号\t姓名\t年龄\n");
	while(p!=NULL){//当访问的结点不到末尾的时候 
		printf("%s\t%s\t%d\n",p->Id,p->Name,p->Age);
		p=p->Next;//把指针p移动到下一个结点 
	}
} 
//插入一个结点，并且要返回插入之后的链表 
STU *Insert(STU *head,STU *pNewNode)
{
	STU *p,*front;
	p=head;
	while(p!=NULL && p->Age < pNewNode->Age){//如果发现p所指向的年龄比新节点的年龄要小的话，就不断循环 
		p=p->Next;
	} 
	//退出循环之后，我们要来检查p的状态
	if(p==head){//说明新的结点一个插入到开头
		//新节点的next要指向以前的head 
		pNewNode->Next=head; 
		//新的head要指向插入的节点  
		head=pNewNode;
	} else{
		if(p==NULL)//说明新的节点应该插入到末尾
		{
			front->Next=pNewNode;//把front的next指向新节点的 
			pNewNode->Next=NULL;//在把新节点的next赋值为NULL 
		} else{//在中间插入 (p前面插入)
			//把front的next指向新节点
			front->Next=pNewNode;
			//把新结点的next指向p
			pNewNode->Next=p; 
		}
		return head;//返回头指针，就是返回链表 
	}
}

void main(){
	STU a[8]={
	{"S1","张一军",23}, 
	{"S2","张二军",24}, 
	{"S3","张三军",25}, 
	{"S4","张四军",26}, 
	{"S5","张五军",27}, 
	{"S6","张六军",29}, 
	{"S7","张七军",30},  
	{"S8","张八军",31}
	},*head,NewNode={"S9","小小样",12},*pNewNode=&NewNode;
	char Id[100]; 
	//现在还是只是一个数组不是链表，所以要调用 CreateLink来创建一个链表
	head = CreateLink(a,8); 
	//输出链表 
	OutputLink(head);
	pNewNode = Insert(head,pNewNode);
	OutputLink(pNewNode);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84