C语言之链表以及单链表的实现
一：链表的引入
1：从数组的缺陷说起
（1）数组有两个缺陷。一个是数组中所有元素类型必须一致，第二是数组的元素个数必须事先指定并且一旦指定后不能更改
（2）如何解决数组的两个缺陷：数组的第一个缺陷结构体可以解决，结构体运行结构体内部元素不相同，因此解决了第一个缺陷
（3）解决数组的第二个缺陷：使用链表来实现数组大小的实时扩展
总结：几乎可以这样理解：链表就是一个大小可以实时变化的一个数组
2：链表是什么样的
(1)顾名思义，链表就是用锁链连接起来的表。这里的表指的是一个一个的节点(一个节点就是
一个校区)，节点中有一些内存可以用来存储数据(所以叫表，表就是数据表);这里的锁链指
的是链接各个表的方法，C语言中用来连接2个表(其实就是2块内存)的方法就是指针。
(2)链表是由若干个节点组成的(链表的各个节点结构是完全类似的)，节点是由有效数据和指
针组成的。有效数据区域用来存储信息完成任务的，指针区域用于指向链表的下一个节点从而构
成链表。
3：要时刻记住链表是用来干嘛的
(1)时刻谨记:链表就是用来解决数组的大小不能动态扩展的问题，所以链表其实就是当数组用
的。直白点:链表能完成的任务用数组也能完成,数组能完成的任务用链表也能完成。但是灵活
性不一样。
(2)简单说:链表就是用来存储数据的。链表用来存数据相对于数组来说优点就是灵活性，需要
多少个动态分配多少个，不占用额外的内存。
二：单链表的实现ji
1：单链表的节点的构成
（1）链表是由节点构成的，节点中包含：有效数据和指针
#include <stdio.h>//构建一个链表的节点
struct node
{int datas; //有效数据struct node *pNEXT; //指向下一个节点的指针};（2）定义的struct node只是一个结构体，，本身并没有变量生成，也不占用内存。结构体定义相当于为链表节点构建了一个模版，但是还没有一个节点，将来在实际创建链表时需要一个节点时用这个模版来复制一个即可
2：堆内存的申请和使用
（1）链表的内存要求比较灵活，不能用栈（当需要插入或删除中间节点时会出现问题），也不能用data数据段（因为数据段是在程序加载时就已经确定好的，占用多少的内存已经定好了，这样就丧失了灵活性），只能用堆内存。
（2）使用堆内存来创建一个链表节点的步骤：1：申请堆内存，大小为一个节点大小（检查申请结果是否正确） -> 2：清理申请到的堆内存 -> 3：把申请到的堆内存当做一个新节点 -> 4：填充新节点的有效数据和指针区域
#include <stdio.h>
#include <string.h>
#include <stdlib.h> //构建一个链表的节点
struct node
{int datas; //有效数据struct node *pNEXT; //指向下一个节点的指针};int main(void)
{//创建一个链表节点struct node *p = (struct node *)malloc(sizeof(struct node)); if(NULL == p) //检查申请结果是否正确{printf("malloc error!\n"); return -1;}//memset(p,0,sizeof(struct node)); bzero(p,sizeof(struct node)); //清理申请到的堆内存//填充节点p->datas = 1; //填充数据区p->pNEXT = NULL; //将来要执行下一个节点的首地址return 0;}3：链表的头指针
（1）头指针并不是一个节点，而是一个普通指针，只占4个字节。头指针的类型是struct node * 类型的，所以它才能指向指向链表的节点
（2）一个典型的莲表示实现就是：头指针指向链表的第一个节点，然后第一个节点中的指针指向下一个节点，然后依次类推到最后一个节点，这样就构成了一个链
4：构建一个简单的单链表
#include <stdio.h>
#include <string.h>
#include <stdlib.h> //构建一个链表的节点
struct node
{int datas; //有效数据struct node *pNEXT; //指向下一个节点的指针};int main(void)
{//定义头指针struct node *phead = NULL;//创建一个链表节点struct node *p = (struct node *)malloc(sizeof(struct node)); if(NULL == p) //检查申请结果是否正确{printf("malloc error!\n"); return -1;}//memset(p,0,sizeof(struct node)); bzero(p,sizeof(struct node)); //清理申请到的堆内存//填充节点p->datas = 1; //填充数据区p->pNEXT = NULL; //将来要执行下一个节点的首地址phead = p; //将本节点和前面的头指针关联起来//创建一个链表节点并和上一个节点关联起来struct node *p1 = (struct node *)malloc(sizeof(struct node)); if(NULL == p1) //检查申请结果是否正确{printf("malloc error!\n"); return -1;}//memset(p,0,sizeof(struct node)); bzero(p1,sizeof(struct node)); //清理申请到的堆内存//填充节点p1->datas = 1; //填充数据区p1->pNEXT = NULL; //将来要执行下一个节点的首地址p-pNEXT>= p1; //将本节点和前面的节点关联起来//再创建一个链表节点并和上一个节点关联起来struct node *p2 = (struct node *)malloc(sizeof(struct node)); if(NULL == p2) //检查申请结果是否正确{printf("malloc error!\n"); return -1;}//memset(p2,0,sizeof(struct node)); bzero(p2,sizeof(struct node)); //清理申请到的堆内存//填充节点p2->datas = 1; //填充数据区p2->pNEXT = NULL; //将来要执行下一个节点的首地址p1-pNEXT>= p2; //将本节点和前面的节点关联起来return 0;}