本篇主要记载链表如何初始化和C++的指针、引用相关的内容。着重点在代码本身，毕竟链表的思想很简单。

链表

学过数据结构的人应该对其有所了解，网上的资料很多，这里就不上图了（哈哈，不想浪费我的云存储空间）。链表其实就是把节点串起来，每一个节点一般是由一个指针域和值域组成。指针域用来指向下一个节点，值域代表本节点的值。
说了这么多，还是上代码吧: 

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
#include <iostream>
using namespace std;
typedef struct list_node ListNode;
//节点
struct list_node
{
	//这里大多数人看到的是：
    //struct list_node* next
	ListNode* next;
	int value;
};
//用一个数组初始化链表
void InitList(ListNode*& head,int* array,int n)
{
	head=NULL;
	ListNode* tmp;
	ListNode* record;
	for (int i = 0; i < n; i++)
	{
		tmp=new ListNode;
		tmp->value=array[i];
		tmp->next=NULL;
		if(head==NULL)
		{
			head=tmp;
			record=head;
		}
		else
		{
			record->next=tmp;
			record=tmp;
		}
	}
}
//打印构建好的链表
void print_list(ListNode* list)
{
//这里有一个中间变量，可不是多此一举，为了保证链表的头指针始终指向表头
	ListNode* tmp=list;
	while(tmp!=NULL)
	{
		cout<<tmp->value<<" ";
		tmp=tmp->next;
	}
	cout<<endl;
}
int main()
{
	int array[]={1,2,3,4,5,6,7,8,9,10};
	ListNode* list;
	InitList(list,array,10);
	print_list(list);
	return 0;
}

接下来主要说一下各个节点怎么连接起来。假设，有一个只有一个节点的链表，在链表尾部加入一个节点。显然需要两个指针才能完成任务，一个指针（tmp）指向新开辟的节点，另一个指针（record）节点指向当前链表的这个节点,那么我们只要令 

1
2
record->next=tmp;
record=tmp;

就可以把两个节点连起来，而且让record指向链表尾部。不过初始化链表这个过程，最开始应该是不存在链表的，那该怎么办了？其实我们只要把最开始的这个节点想象成空节点就好了。初始化第一个节点使用下面代码就可以了： 

1
2
head=tmp;
record=head;

链表连接过程的大概思路就是这样子的，不过这并不代表你就能写出完整的代码了。

C++指针和引用

这里还是先分析一下每一行代码吧，毕竟C++指针和引用的东西也太多了。 

1
typedef struct list_node ListNode;

这行代码只要是认真学了c语言的人应该能明白吧，要是还不明白我在举一个例子 

1
typedef int my_int

这不就是把数据类型重新换了一个名字啦，以后就可以用它来代替原来的数据类型了，那么struct list_node又是说明数据类型了？
其实它就是下面我们自己定义的数据类型： 

1
2
3
4
5
6
7
struct list_node
{
	//这里大多数人看到的是这种表示方法：
    //struct list_node* next
	ListNode* next;//有没有明白这里为什么是ListNode?
	int value;
};

说白了就是定义了一个表示链表节点的数据类型。
InitList函数的主体思想我前面已经讲解了，这里就不再累赘了。不过有没有觉得参数 

1
ListNode*& head

很奇怪，这里怎么有一个地址符号（&）了？接下来就来揭晓奥秘吧。
第一眼是不是觉得应该去掉地址符号，直接传一个链表的首地址就好了。如果去掉&符号那么将得到如下的错误：Segmentation Faults（完整的错误我没有写出来），通过google，发现这是新手C+ + 程序员会遇到的问题（你要是没有一眼看出其中的门道，欢迎你加入C++程序员的行列）。 还是先上一下的测试程序吧： 

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
#include <iostream>
using namespace std;
typedef struct list_node ListNode;
struct list_node
{
	ListNode* next;
	int value;
};
void InitList(ListNode* head,int* array,int n)
{
	cout<<"在InitList函数内，链表初始化之前，head的值："<<head<<endl;
	cout<<"在InitList函数内，链表初始化之前，head的地址："<<&head<<endl;
	cout<<endl;
	head=NULL;
	ListNode* tmp;
	ListNode* record;
	for (int i = 0; i < n; i++)
	{
		/* code */
		tmp=new ListNode;
		tmp->value=array[i];
		tmp->next=NULL;
		if(head==NULL)
		{
			head=tmp;
			record=head;
		}
		else
		{
			record->next=tmp;
			record=tmp;
		}
	}
	cout<<"在InitList函数内，链表初始化之后，head的值："<<head<<endl;
	cout<<"在InitList函数内，链表初始化之后，head的地址："<<&head<<endl;
	cout<<endl;
}
void print_list(ListNode* list)
{
	ListNode* tmp=list;
	while(tmp!=NULL)
	{
		cout<<tmp->value<<" ";
		tmp=tmp->next;
	}
	cout<<endl;
}
int main()
{
	int array[]={1,2,3,4,5,6,7,8,9,10};
	ListNode* list;
	cout<<"在初始化链表之前，list的值："<<list<<endl;
	cout<<"在初始化链表之前，list的地址："<<&list<<endl;
	cout<<endl;
	InitList(list,array,10);
	cout<<"在初始化链表之后，list的值："<<list<<endl;
	cout<<"在初始化链表之后，list的地址："<<&list<<endl;
	// print_list(list);
	return 0;
}

运行的结果:
在初始化链表之前，list的值：0x400c7a
在初始化链表之前，list的地址：0x7fffa8805708

在InitList函数内，链表初始化之前，head的值：0x400c7a
在InitList函数内，链表初始化之前，head的地址：0x7fffa88056b8

在InitList函数内，链表初始化之后，head的值：0x12bd780
在InitList函数内，链表初始化之后，head的地址：0x7fffa88056b8

在初始化链表之后，list的值：0x400c7a
在初始化链表之后，list的地址：0x7fffa8805708
居然发现，list的值在初始化前后既然没有变化。在初始化过程中首地址开辟新地址空间，应该变了才对啊。接着，发现head的值在初始化前后是变化了的，这是为什么了？难道是在InitList中开辟的是临时变量，让人不经想起这段代码： 

1
2
3
4
5
6
7
8
9
10
11
12
void fun(int a)
{
	a+=1;
	cout<<a<<endl;
}
int main()
{
	int a=1;
	fun(a);
	cout<<a<<endl;
	return 0;
}

不过真的就是同一个原因，就是因为在函数中开辟了临时变量。值得注意的是list和head指针指向的地址的值同样也是一个地址,而不是一个数值。
首先来看一下list的变化过程：
listimg
接着来看一下head的变化过程：
headimg
通过比较head和list最后指向的地址不一样，就是因为临时变量作用的结果（方框顶上的地址是不一样的哦，表示list传到head地址是变了的，也就是有临时变量）。如果我们加上&符号，地址就不会变了（其中的原因看一下下面推荐的博客吧）.
总结一下，所有的问题都是因为被表面现象所迷惑，以为传一个指针进去就是把地址传进去了，归根到底是对指针和引用理解不深，因此我也找了一篇博客C++指针和引用的详解