动态链表 头插法

作为单链表知识点而言，本节使用C语言讲解。

在介绍单链表之前，很有必要把C语言的几个知识点捋清楚：

1、C语言预备知识

1.1 指针与指针变量

int a = 32; 定义整形变量int *p = &a; 定义指针变量二者类比看待这里存在2对概念	1、整形与整型变量	2、指针与指针变量本质上而言的话：整形与指针都属于常量范畴，整型变量与指针变量都属于变量范畴赋值运算的本质就是将相对应的正确类型的常量赋值给对应变量的内存单元中	就上面两个赋值语句而言的话：第一个是将整型常量32赋值给整形变量a当中，第二就是将变量a的地址常量赋值给指针变量p当中。 作者：快乐的小log  出处：bilibili

1.2 图示讲解

指针变量

1.3 结构体

typedef int ElementType;  给数据类型起别名  扩展性很强struct Node{  ElementType data;  struct Node* next;}typedef struct Node* LK;我们都知道单链表是由节点构成的，节点当中包括两部分信息：	数据域：节点存储的信息，比如学生管理系统的学生信息	指针域：与当前节点相连接的下一个节点地址信息，这样才能形成一个链条的逻辑结构 内存开辟的两种方式： 	静态开辟内存：int a = 32; 编译的时候就开辟好了，上来就占坑。	动态开辟内存：通过指针的方式开辟一段连续大小的内存空间，用的时候才开辟内存空间。灵活一些，提升内存使用效率。

2.1 静态创建

静态创建三个节点的单链表

代码如下：

#include "stdio.h"#include "stdlib.h"// 上述两处我替换为双引号  应该为尖括号，小破站现在对代码块这一块支持不是很友好// 给单链表数据域数据类型起别名  拓展数据域类型功能typedef char ElementType;// 定义单链表struct Node{	ElementType data;	struct Node* next;};typedef struct Node* LK;// 打印单链表void displayLinkList(LK L){	LK p = L;	while(p){		printf("%c\n",p->data);		p = p->next;	}}//主函数int main(int argc, char const *argv[]){	struct Node A,B,C;	A.data = 'A';	B.data = 'B';	C.data = 'C';	A.next = &B;	B.next = &C;	C.next = NULL;	displayLinkList(&A);	return 0;}

链表遍历图示：

链表遍历流程

2.2 动态创建

//主函数int main(int argc, char const *argv[]){	// 静态创建单链表	// struct Node A,B,C;	// A.data = 'A';	// B.data = 'B';	// C.data = 'C';	// A.next = &B;	// B.next = &C;	// C.next = NULL;	// malloc方式动态创建单链表：尾插法同时包括头尾指针，方便链表操作	LK p,tail,head;	for (int i = 0; i < 3; ++i)	{		p = (LK)malloc(sizeof(struct Node));		p->data = 65+i; //'A'的ascll码数值：65		if(i==0){			head = p;			tail = p;		}		tail->next = p;		tail = p;	}	tail->next = NULL;	displayLinkList(head);	return 0;}

动态链表尾插法图示：

动态链表头插法

2.3 C vs C++ &不同之处

/** * C++有一个玩意儿叫引用 长得和C语言地址符号一样 & * 下面的例子就很清楚说明问题，你在main函数传入实际参数。 * 如果你在函数当中想操作实际参数比如++，--操作，我们在C语言的时候只能通过指针操作 * C++当中的引用就不用指针方式，只需要你在函数参数前面加&符号，在main函数中传入实际参数即可。 * 这个在链表操作过程中比如说某个函数会有返回值，但我们希望定义函数为void类型，这样我们就可以在函数参数中添加一个返回值参数了。以引用的方式操作,比如： *  void getMaxElem(LK L,int &res) * */int getVar(int a,int &b){	a++;	b++;	return b;}int main() {	int a = 5;	int r = getVar(a,a);	printf("%d,%d",r,a);   // 打印结果 ： 6 6	return 0;}