链表入门

(Updated: )
面试 › 数据结构与算法

我与链表的初识

为什么要学链表？链表干嘛的？

这就是链表牛逼所在。之前我们储存数据都是通过数组，可数组开辟的是一段连续的空间，如果我们要储存一个特别大特别大的数据，计算机内极有可能找不到这么大的一块储存空间。这时候，链表闪亮登场。用链表储存数据，不需要开辟一段连续的空间。在储存数据时，只需要随机找到一个空余的空间并赋值，接下来再寻找下一个空余的空间并赋值。就像在一堆珠子中随机捡一个珠子，把它串在线上，最终形成了一个珍珠串，把它送给女朋友。所以，链表就是这样，把一个个不连续的地址串起来，用以储存庞大的数据。（说的不对直接骂）

从珍珠串开始，便引入了链表最基本的几个概念。
节点，头指针，首节点，尾节点

节点就是每个结构体中数据域和指针域构成的整体（不能理解这段中文意思的没关系，我一开始也不懂，去往下看）。简单理解节点就是珍珠串上的每一颗珍珠。
在我们储存完数据后，在读取时必须得找到第一个节点的位置，这样才能像多米诺骨牌一样一个一个寻找下一个节点的位置。因此头指针的作用就是给我们指出第一个节点位置。就好比珍珠串第一个珍珠前绳子打的结。
首节点很简单，就是第一个珍珠。相对应，尾节点就是最后一个珍珠。

现在，我们看一下链表都是怎么构造的

1
2
3
4
5
6
7
struct node
{
	int a;
	double b;
	struct node *next;
};

是不是有些不知所措，结构体中为什么又定义了一个结构体指针？
记得我之前说的数据域和指针域吗？在这段代码中，数据域就是node结构体中的int类型数据a和double类型数据b，而指针域就是结构体中的next指针，next指针指向了下一个struct node类型的地址，是不是有点递归的意思。

数据域用来储存数据，指针域指向下一个开辟的地址，以继续储存数据。

为了继续熟悉这个结构，我们来构造一个静态链表

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
# include <stdio.h>
# include <stdlib.h>
struct student  //构造链表
{
	int num;
	double score;
	struct student *next;
};
int main()
{
	struct student a,b,c,*head;

	//对结构体进行赋值
	a.num=1;
	a.score=89.5;
	b.num=2;
	b.score=98;
	c.num=3;
	c.score=85;

	//头指针指向a所在地址
	head=&a;

	//每个结构体指针指向下一个结构体
	a.next=&b;
	b.next=&c;
	c.next=NULL; //最后一个节点指针域指向空
	//打印链表
	do
	{
		printf("%d %.lf\n",head->num,head->score);
		head=head->next;
	}while(head!=NULL);
	return 0;
}

通过静态链表来理解链表非常关键，初学的朋友一定要细细品味这段代码

建立一个动态链表
相信细品过建立静态链表的同学会发现，要是我要储存未知个数个数据，静态链表明显没用了呀！还不如做个数组呢！
因此，我们来建立一个动态链表。
首先，你们需要会malloc()函数。不会的给大家推篇博客学习一下再来吧请点我q(≧▽≦q)
通过malloc()函数我们就可以开辟一段符合每段节点长度的储存空间，再上一个节点的指针域指向该空间的首地址，以新建一个节点
下面赠上代码，请细品

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
# include <stdio.h>
# include <stdlib.h>

//宏定义
# define NODE struct node  //用NODE代替struct node 减少下面每次构造一个结构体指针都要打这么多字的麻烦 
# define LEN sizeof(NODE)  //用LEN代替每个节点的长度

NODE* creatlist(void);     //建立动态链表
void printlist(NODE*);     //打印链表

NODE
{
	int num;
	NODE * next;
};

NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);    //开辟空间
	printf("\n请给每个节点赋值，以0作为结束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}

void printlist(NODE* head)
{
	NODE* p=head;
	printf("\n您建立的链表为：\n");
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}

int main()
{
	NODE* p=creatlist();     //p指向返回的head地址
	printlist(p);
	return 0;
}

看不明白请多看几次，可在纸上模拟整个程序的运作过程

学会建立动态链表后我们再来学习两个基本技能：
1.删除某个节点
字丑勿喷
函数片段如下

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
NODE* delete_node(NODE* head)
{
	NODE*p1,*p2;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想删除第几个节点呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	if(m==1)
	{
		head=head->next;
	}
	else
	{
		m--;
		while(m--)
		{
			p2=p1;
			p1=p1->next;
		}
		p2->next=p1->next;
	}
	return 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# include <stdio.h>
# include <stdlib.h>

# define NODE struct node
# define LEN sizeof(NODE)

NODE* creatlist(void);
void printlist(NODE*);
NODE* delete_node(NODE*);

NODE
{
	int num;
	NODE * next;
};


NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);
	printf("请给每个节点赋值，以0作为赋值的结束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}


void printlist(NODE* head)
{
	printf("\n该链表每个节点的值为：\n");
	NODE* p=head;
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}


NODE* delete_node(NODE* head)
{
	NODE*p1,*p2;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想删除第几个节点呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	if(m==1)
	{
		head=head->next;
	}
	else
	{
		m--;
		while(m--)
		{
			p2=p1;
			p1=p1->next;
		}
		p2->next=p1->next;
	}
	return head;
}


int main()
{
	NODE* p=creatlist();
	printlist(p);
	p=delete_node(p);
	printf("\n删除成功!\n");
	system("pause");
	printlist(p);
	return 0;
}

实现效果
在这里插入图片描述

2.插入一个节点
字丑勿喷
函数片段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
NODE* insert_node(NODE* head)
{
	NODE*p1,*p2,*p3;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想在第几个节点后插入一个节点呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	while(m--)
	{
		p2=p1;
		p1=p1->next;
	}
	p3=(NODE*)malloc(LEN);
	p2->next=p3;
	p3->next=p1;
	printf("\n您想给该节点赋值为？\n");
	scanf("%d",&p3->num);
	return 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
80
81
82
83
84
85
86
87
88
89
90
# include <stdio.h>
# include <stdlib.h>

# define NODE struct node
# define LEN sizeof(NODE)

NODE* creatlist(void);
void printlist(NODE*);
NODE* insert_node(NODE*);

NODE
{
	int num;
	NODE * next;
};


NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);
	printf("请给每个节点赋值，以0作为赋值的结束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}


void printlist(NODE* head)
{
	printf("\n该链表每个节点的值为：\n");
	NODE* p=head;
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}


NODE* insert_node(NODE* head)
{
	NODE*p1,*p2,*p3;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想在第几个节点后插入一个节点呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	while(m--)
	{
		p2=p1;
		p1=p1->next;
	}
	p3=(NODE*)malloc(LEN);
	p2->next=p3;
	p3->next=p1;
	printf("\n您想给该节点赋值为？\n");
	scanf("%d",&p3->num);
	return head;
}


int main()
{
	NODE* p=creatlist();
	printlist(p);
	p=insert_node(p);
	printf("\n插入成功！\n");
	system("pause");
	printlist(p);
	return 0;
}

实现效果
在这里插入图片描述