混子数据结构学习之第二章线性表链式表示之基本操作插入

"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“

前言

继续接着上一章的学习，本文主要还是记录链表的一些基本操作，主要是链表的清空、求链表长度、两种插入链表结点等一些操作，一方面是回顾这个链表的定义和使用，一方面需要去体会这些操作处理的逻辑思路。

链表的基本操作的补充

清空链表

理解：链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）。
注意的是和销毁的区别，清空链表还存在，销毁链表是不存在了。
算法思路：依次释放所有结点，保留头结点，并将头结点指针域设置为空。

代码实现

说明：

• 使用的平台：VC2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）

//-------单链表的清空：链表还存在
unsigned char ClearList(LinkList *L)//需要传入二级指针，等同于Node **L
{
    Node *p, *q;//或LinkList p, q;
    p = (Node*)(*L)->next;//存下首元结点的地址，当前的地址
    while(p)   
    {
        q =(Node*)p->next;//先保存当前的后面一个结点的地址
        free(p);//释放当前的结点
        p = q;//将后一个的结点地址赋值给p
    }
    (*L)->next = NULL;//头结点指针域为空 
    return OK;
}

求取链表的长度

概念：求取链表的有效结点个数。
算法：从首元结点开始进行依次判断计算，直道下一个结点为空即可；

代码实现

说明：

• 使用的平台：VC2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）

//------求单链表的长度
unsigned int ListLength(LinkList L)//这里不对链表进行值和地址的修改，传入一级指针即可！
{
    unsigned int i = 0;
    LinkList p =(LinkList) L->next; //读取首元结点

    while(p)//判断结点是否存在
    {
        i++;//计数
        p = (LinkList) p->next;//读取下一个结点
        //printf("第 %d 个结点\n",i);//测试使用的
    }

    //printf("统计结束\n");//测试使用的
    return i;
}

链表的创建（输入）

前面说了这种多操作，我们好像都没有学一下如何往链表中输入结点，这也就是创建各个结点。
有两种方法：头插法和尾插法；

头插法

概念：
字面意思理解，就是从头部开始插入结点，这种方法是当前插入的结点永远是首元结点，也就是最先插入的结点在链表的最后位置。

实现步骤

• 1、初始化构造一个带头结点的单链表（前面笔记里有写）
• 2、创建一个临时结点P,数据域进行赋值 p->date = date;

• 3、通过地址域将结点进行连接起来，将p插到头结点与第一个结点之间

  
  

代码实现

说明：

• 使用的平台：VC2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）

//------单链表的输入 法一（头插法）
unsigned char CreateListHead( LinkList* L, int n )
{
    LinkList p; //定义一个结点地址，用于存储
    int i,date;
    
    for(i=0; i<n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));//创建新结点

        printf("输入结点的数据：");
        scanf("%d",&date);
        p->date = date;

        p->next = (*L)->next;//这两句实现将结点P插入到L和L->next结点之间
        (*L)->next = p;

        printf("已完成插入第 %d 个结点\n",i+1);

    }
    return OK;
}

运行结果：

注意点

• 函数未增加初始化链表L的处理，需要先调用函数InitList_L(&L)进行初始化L
• 最核心的两句代码为：
  p->next = (*L)->next;//这两句实现将结点P插入到L和L->next结点之间
(*L)->next = p;

尾插法

概念：
类比头插法，尾插就是把新结点插到链表的尾端，当前插入的结点永远在尾端，先插入的都在表尾。把新加入的节点插入到上一个节点的尾部。
实现步骤：

• 1、定义两个结点的元素变量，一个用于储存临时创建的结点，一个用来存储链表的尾端结点
• 2、对临时结点进行分配空间，分配数据
• 3、将新结点插入到尾端结点和上一个结点之间，更新尾端结点
  end->next = p;//将新结点挂到上一个尾结点的后面

end = p;//end读取当前的尾结点
  

代码实现

说明：

• 使用的平台：VC2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）

//------单链表的输入 法二（尾插法）
unsigned char CreateListTail( LinkList* L, int n )
{
    LinkList p; //定义一个结点地址，用于存储
    LinkList end;//定义一个结点，用来存储尾结点
    int i=0,date=0;

    end = (*L) ;//尾部结点(最开始没得结点，头结点可以认为是尾结点)
    
    for(i=0; i<n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));//创建新结点

        printf("输入结点的数据：");
        scanf("%d",&date);
        p->date = date;//数据域赋值

        end->next = p;//将新结点挂到上一个尾结点的后面
        end = p;//end读取当前的尾结点

        printf("已完成插入第 %d 个结点\n",i+1);
    }

    end->next = NULL;//尾端结点的地址域清零

    return OK;
}

运行结果

过程问题点：

• 1、在写插入结点函数进行测试时，未调用初始化L，就直接插入报错
• 2、在写输出结点数据函数测试时，函数中的局部变量未初始化导致运行不了（具体问题暂不作分析）
  局部变量处于堆栈区，其数值是随机的，即当时内存中的值。
  后续专门研究一下给出解释！
  需要养成习惯，变量定义后要进行初始化赋值！
• 3、在书写尾插法的时候，函数最后未对尾端的结点的地址域进行赋空地址！导致在调用查询长度和输出的时候出问题，代码运行异常！

小结

今天这个就暂时记录到这里，后面查询删除这些后续重新开篇记录，不然篇幅有点大！
上述主要需要理解两种插入方式的思想，可能理解起来尾插法不太好理解，我自己学习理解就是自己画图，代入理解的，心里面想一下插入2个或者3个结点两种方法他是如何实现的，也很容易想明白！

参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
《大话数据结构》.程杰

若上述描述有问题或者歧义的，欢迎与我反馈交流，共同进步学习！

欢迎关注本人微信公众号：那个混子

记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！

单片机类嵌入式交流学习可加企鹅群：120653336