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;}