上次有同学讲到了链表，刚好我也学了一下，总结一下自己的学习过程，方便自己以后回顾。有疑惑的地方随时可以咨询我，有错的地方也随时可以告诉我，方便我改正错误.......新手上路.
一.结构体
声明方式
1.直接声明加定义变量
Struct Node {
int value = 0;
}node;
2.先声明在定义变量
Struct Node {
int value = 0;
};
在主方法里面结构体名加变量名：struct Node node;
3.先声明在定义变量
先在代码块外部声明
typedef Struct Node {
int value = 0;
}Node;
用typedef这样可以方便以后在各类方法中定义一个新的结构体变量
如：Node node这样我们就定义了一个node结构体了。
二.指针
都知道C的灵魂是指针，也知道指针的声明就是数据类型名加变量名
如：int *p;
但是这种声明我想说的是因该杜绝的，在链表中所有非指向特定的值或不是向系统申请了内存的指针都因该初始化为NULL;
如：int *p = NULL;
那初始化与不初始化的区别是什么？
如果定义指针时未初始化，系统会为这个变量自动分配一个地址，因为这个地址是随机分配的，所以它可能是可读不可写，也有可能不可读不可写，如果在这块地方写了那么就会出现Runningtime Error，程序在窗口运行时直接崩溃。
所以定义一个指针最好初始化NULL，那么NULL的好处是什么？NULL又是什么？能不能调用或者访问这个空指针？
了解之前都知道两个符号“&”，“*”，前面是取址符，后面是取值符
先了解下NULL它就是0，那么p指针指向NULL就是指向0的地址，都知道定义一个int p再让变量以十进制的形式打印p的值得到会是一个垃圾值（随机值），指针也是一样的，不初始化它，它就会被随机分配指向一块地址，而NULL对于系统来说无害的也是无效的值，因为它的内容不可访问，所以初始话为NULL的话就可以杜绝了Runningtime Error的问题。
三.结构体指针
声明结构体指针很简单和声明结构体一样就是变量名字前多了“*”号。
四.使用结构体和指针（开始正题）
先了解四个函数：malloc,calloc,realloc,free.
很简单的四个函数，前三个都是为了向系统申请内存空间，当程序需要另外一些的内存存储数据时，它就调用这些函数，让它们从内存池中提取一块“适合”的内存（这个适合是因为提取的大小是可以自己选择的），并返回指向该内存地址的指针（说明可以进行访问读写操作）。（重点！申请得到的内存是连续，它有点类似数组下面举例的时候说明）
例如我们想要申请一个int大小的内存：
int *p = NULL;
p = (int *)malloc(sizeof( int ));
首先我们定义了一个指向整型的指针，接着为这个指针分配了一块大小为int这么大的内存，重点，分配的int大小其实是一个4个字节（操作系统不同，int大小也可能不同的啦，别纠结。）的数组，我们可以对这个数组存放int类型的变量，就是这样了。
如：*p = 8;
还有！！！他还可以这样p = (int *)malloc(n*sizeof( int ));
申请n（n可以自己定义）个int大小的内存。
calloc和realloc的原型如下：
void *calloc( size_t num_elements, size_t element_size);（！解释一下size_t就是int它们是等价关系，别问我为什么知道，问就是百度）
void *realloc(void *ptr , size_t new_size);(这个不讲，因为我见过但是一直没用过（就是我不会）)。
free就是申请到的空间回收（当你不在需要这片空间的时候记得用它，不然就会造成内存泄漏）
用法就是这样free(p);
注意！！（free只能回收上面三个函数申请分配到的内存（就是指针））
em....最好后面p在加上一条这样的语句p = NULL,因为有时候会回收失败，而NULL又是一个无害的常量，所以可以阻止内存的泄漏（也可能多此一举）。
calloc函数有两个参数分别是所需元素的数量和每个元素的字节数，它根据这些值能够计算出总共需要分配的内存，它就是相当于把前面说到的malloc里面那个n当成了一个参数传进第一个参数的位置，sizeof(int)当成第二个参数。
有时候我们只对指针进行初始化而不用malloc对他进行初始化，给它分配一个内存，那么在链表中什么时候把它初始化为：NULL,什么时候为他分配内存：int *p = ( int *)malloc(sizeof(int))，两者有什么区别？
当我们只是要一个指向地址的指针，这个指针是为了提供一个地址，而不对他进行间接访问时，就初始化为NULL,例如：链表中常常会再声明一个*head是为了指向链表的根节点，但是这个head并不进行解引。当我们需要一个指针（节点）来存储某些数据的时候就会使用到malloc申请一块可读可写的内存。
举例：
typedef struct NODE{ //首先是先声明一个结构体
int value; //图书编号
char ZuoJia[20]; //作者名字
char BookName[20]; //图书名字
NODE *next; //指向结构的指针
}Node;
void insert(Node **root, int const new_value, char new_ZuoJia[], char new_BookName[]){
Node *head = *root; //定义一个指针指向链表的头部
Node *previous = NULL; //定义一个空指针方便后续有到
Node *newstorage; //定义一个指针
newstorage = (Node *)malloc(sizeof(Node));//为指针申请一块内存存储数据
if(newstorage == NULL){
printf("分配内存失败\n");
exit(1);
}
else{
newstorage->value = new_value;
strcpy(newstorage->ZuoJia, new_ZuoJia);//对于字符串常量的赋值只 有strcpy和strcnpy两个函数
strcpy(newstorage->BookName, new_BookName);
}
｝
开始链表：
链表在java里面是容器，存储数据的一种，类似的数组也是简单的容器，所以学习链表的时候可以配合着数组来学。
数组与链表的优缺点：使用数组的话搜索一个数（值）是可以通过下标索引找到，这是数组最大的有点，但是他最致命的缺点是从中删除或者增加一个数时，后面的数都要往前或者往后移动一单位。链表与数组恰恰相反，使用链表查找一个数时候，你必须遍历整个链表，这种效率没法和数组比，但是你想从中增加或者删除一个数是很方便的，下面会说。
一. 单链表：在单链表中，每个节点包含一个指向链表下一关节点的指针。链表最后一个节点的指针字段的值为NULL，提示链表后面不再有其他节点。在你找到链表的第一个节点后，指针可以带你访问剩余的所有节点（就和数组一个，只要给了你数组名（数组的头地址）你就可以访问数组中的所有元素）。为了记住链表的起始位置，可以使用一个根指针（head）,指向链表的头结点（第一个节点）。注意下头指针就是单单指针，它的地址上不存储任何数据，只是提供链表的头地址！
下例是节点声明创建的结构方式
typedef struct NODE{
int value;
struct NODE *next;
}
从图中我们可以知道存储于每个节点的数据是一个整型值。这个链表包含三个 节点。如果你从根指针开始，跟随指针到达第一个节点，你可以访问存储于那个节点的数据（顺便说下，访问一个链表的方法和数组一样就是遍历整个链表找到你要找的key值）。随着第一个节点的指针可以到达第二个节点，你可以访问存储在那里的数据。最后第2个节点的指针带你来到最后一个节点，零值（NULL）提示它是一个空指针（记住最后一个节点一个要定义为NULL，因为他是你结束的标志），例子就不展示太多的节点了。
因为自己画的太惨不忍睹，也为了更好的理解，所以再讲一个例子吧。
#include <stdio.h>
struct student
{
long num;
float score;
struct student *next;
};
void main()
{
struct student a, b, c, *head;
a.num = 10101;
a.score = 89.5;
b.num = 10103;
b.score = 90;
c.num = 10107;
c.score = 85;
head = &a;
a.next = &b;
b.next = &c;
c.next = NULL;
do
{
printf("%ld %5.1f\n", head->num, head->score);
head = head->next;
}while( head != NULL );
}
例子很简单，我们在代码块的外部声明了一个结构体，结构体的成员有学号，分数，一个指向结构体的指针，在main函数里面我们定义了四个变量a,b,c,*head,前三个是结构体变量，作用就是存储成员的信息，后面定义是指针是为了方便我们从链表的头部开始访问，最后输出整个链表的成员信息（可以配合着图看）。
接着说明链表的增删功能如何实现
用一个新例子
1.首先是对链表节点的删除操作:从一个动态链表中删去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开来，只要撤销原来的链接关系即可，看图
就是让你要删除的节点的前一个节点的next指针指向节点的后一个节点，看代码
void deleteBook(Node **root, int delet_value){
Node *current = *root; //指向链表头的头节点
Node *previous = NULL; //定义一个空指针用来指向前一个节点的地址
if(*root == NULL) //判断是否为空链表
｛
printf("空链表!\n");
}
else{
while(current!=NULL) //遍历整个链表
{
if(current->number==delet_value) //找到要删除的节点
{
if(current->next == NULL) //如果当前节点处于链表尾部
{
current = NULL; //就把当前节点指向NULL成为新的尾节点
printf("删除成功！\n");
break;
}
else if(previous == NULL) //删除的节点为头部
｛
*root = current->next; //修改头结点，是它指向下一个节点
｝
else //如果是处于中间就把要当前节点 的一 个节点中的next指向当前节点的下一个next
{
previous->next = current->next;
printf("删除成功！\n");
break;
}
}
else
{
previous = current;
current = current->next;
}
printf("查无此值！\n");
}
}
}
再看图
删除就是使你要删除的当前节点的前一节点跳过该节点指向它的下一个节点
出现二级指针，指向结构体指针的指针，这是因为如果传入的参数是结构体指针那它头指针是不能更改的，想要更改头指针，就需要传入指向结构体指针的指针。
2.接着是对链表的插入操作: 对链表的插入是指将一个结点插入到一个已有的链表中。为了能做到正确插入，必须解决两个问题（和删除很类似）：
① 怎样找到插入的位置；
可以插入的位置有三种：
1.链表的头部
2链表的中间
3.链表的尾部.
② 怎样实现插入。
看图
头插法
插入到指定位置
尾插法
看代码
void nsert(Node **root, int const new_value)
{
Node *current = *root;
Node *previous = NULL;
Node *newstorage;
newstorage = (Node *)malloc(sizeof(Node));
if(newstorage == NULL)
{
printf("分配内存失败\n");
exit(1);
}
else
{
newstorage->value = new_value;
}
while(current!=NULL && current->value<=new_value)
{
previous = current;
current = current->next;
}
if(*root == NULL && previous == NULL)
{
*root = newstorage;
newstorage->next = NULL;
}
else
{
previous->next = newstorage;
newstorage->next = current;
}
printList(root);
}
它的实现和删除很类似，删除是从中删除一个节点那么就跳过这个节点，增加是从中增加一个节点那么就让前一个节点指向这个新节点，新节点在指向下一个节点，形成不断链的链表。上述代码配合图片和删除一起看。
二.双链表
双链表就是结构体内部存在两个结构体指针，一个指向结构的下一个节点，一个指向结构体的前一个节点，形成闭合的链条。
看图
它的声明：
typedef struct NODE{
int number;
NODE *previous //指向前一个节点
NODE *next //指向下一个节点
｝Node;
从声明上看就是多了一个NODE *previous指向当前节点的前一个节点，他的用法也和单链表一样
对比单链表的优势是他可以从链表的头和尾进行访问，加快了索引查找的效率。
最后说一下创建单链表和双链表的注意事项
创建完一个链表的头节点，要时时刻刻使它的next->NULL,这是为了保证最后一个节点（尾节点）为NULL(一般为遍历结束的标志)，如果没有使尾节点为NULL那么循环就会一直遍历这个链表通过层层递归可能打印的会是你意料之外的结果。双链表的要初始化两个节点，一个是头节点的previous->NULL,一个是尾节点的next->NULL,这也是为了方便作为循环结束的标志，如果0（NULL）是你需要存储的数据，那么就因该避免，初始化为NULL。
