混子数据结构学习之第二章线性表顺序表示之查找、插入、删除

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

前言

继续之前的学习梳理，已经停了一段时间了，这段时间主要是中途去做一个项目被耽搁了，现在将继续学习整理，好记性不如烂笔头，还是得写写记记，东西太多，记忆总是有限的。上一篇主要梳理了线性表的顺序存储的基本的概念和代码的实现，本文将接着前面的梳理，主要涉及顺序表的按值查找元素的位置、在线性表中任意位置插入元素、在线性表中任意位置删除元素的相关操作。

顺序表的按值查找位置

思路：

从线性表L中查找与指定值e相同的数据元素的位置。从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0。
这里是查找指定元素的位置，和前面查找指定位置的元素区分开

代码实现

说明：

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

//线性表中查找指定元素的位置信息
//法一
unsigned int LocatingEleme1(SqList L,ElemType e)
{
    unsigned int i;
    
    for(i = 0; i< L.length; i++)
    {
        if(L.elem[i] == e)
        {
            return (i+1);
        }
    }

    return FALSE;
}
//法二
unsigned int LocatingEleme2(SqList L,ElemType e)
{
    unsigned int i=0;
    while(i< L.length && L.elem[i] != e)//如果在线性表长度范围内，未扫描到指定元素，则一直循环
    {
        i++;
        //return i;
    }
    if(i < L.length)// 查询成功，如果上面没有查询成功，i = L.length,不会进入这里，如果查询成功，i需要加1输出实际的位置
    {
        return i + 1;
    }
   
    return FALSE;
}

运行结果：

从算法复杂度简要分析上述操作：

查找的基本操作为：将记录的关键字同给定值进行比较，然后输出位置。
（固定值在表中的位置不确定下，可能是第一个一下子就找出来，可能是最后一个或者不存在那就要把表中的元素全部轮询一遍）

下面引入：

平均查找长度ASL（Average Search Length）：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。

对含有n个记录的表，查找成功时：

Pi 是第i个记录被查找的概率，Ci 是找到第i个记录需比较的次数。

顺序查找的平均查找长度：

假设每个记录的查找概率相等：Pi = 1/n 。

则：

顺序表插入新元素

思路：

插入新元素是在顺序表的第i（1<=i+1<length+1）位置上，新增一个结点e,使长度为n的线性表变成长度为n+1的线性表。
和前面那些操作一样，我们需要去考虑操作位置的合理性。

image.png

算法步骤

• 判断插入位置i是否合法。
• 判断顺序表的存储空间是否已满，若已满返回ERROR。
• 将第n至第i位的元素依次向后移动一个位置，空出第i个位置。
• 将要插入的新元素e放入第i个位置。
• 表长加1，插入成功返回OK。
  注：就是需要处理的是插入位置后面的元素要一一往后跑的操作！

代码实现：

说明：

• 使用的平台：VC++2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）
• 主要是学习方法思路，代码设计上其实还存在一些瑕疵，可以优化完善的

//线性表中指定位置插入新结点元素
unsigned int InsertElement(SqList *L, int i,ElemType e)
{
     int j;
    //判断指定位置是否合法
    if(i < 1 || i > L->length+1)
    {
        return FALSE;
    }
    //如果线性表的空间已经存满
    if(L->length == MAXSIZE)
    {
        return FALSE;
    }

    //插入位置及以后的元素后移(从最后一个开始依次移动)
    for(j = L->length - 1; j >= i - 1; j--)//注意j=0的情况，j=0会执行循环，执行后j会减1
    { 
        L->elem[j + 1] = L->elem[j];
        printf("j = %d;i = %d\n",j,i);
    }
    L->elem[i - 1] = e;//将新元素e放入第i个位置 
    L->length++;//表长增1 

    return OK;
}

代码运行结果：

注意

在上面这个代码调试书写中，需要注意程序中的i和j的类型，最开始两个值我写了无符号数类型，在1号位置插值发生错误，原因就在我之前分享的有无符号数大小比较问题里面，那里j=0执行循环后，会减1再和表达式2比较判断，如果是无符号数，减1 后变成了最大值，然后又会满足条件，具体可以实操试试看看..............
调试出现错误的结果：

从算法复杂度简要分析上述操作：

上述中，插入位置不同，for循环执行的次数不一样，在最后一个位置插入时，不用执行循环即可插入，依次往前，次数会增加；插在第一个位置时需要将所有元素都往后移动，耗时最多。算法时间主要用于移动元素去了。
分析出现的情况有n+1种，复杂度计算：

平均时间复杂度为：O（n）;

删除顺序表指定元素

思路：

删除和插入类似，删除元素是在顺序表的第i（1<=i+1<length+1）位置上，删除一个结点e,使长度为n的线性表变成长度为n-1的线性表。

算法步骤

• 判断删除位置i是否合法
• 将欲删除的元素保留在e中。
• 将第i+1至第n位的元素依次向前移动一个位置。
• 表长减1，删除成功返回OK。

代码实现

• 使用的平台：VC++2010
• 这里代码沿袭了上一章的代码，在原来基础上增加函数。（不能直接复制下述代码运行）
• 主要是学习方法思路，代码设计上其实还存在一些瑕疵，可以优化完善的

//线性表中指定位置删除元素
unsigned int DeleteElement(SqList *L, int i)
{
     int j;
    //判断指定位置是否合法
    if(i < 1 || i > L->length+1)
    {
        return FALSE;
    }

    //被删除的元素依次往前移动占位(从靠近删除元素的位置开始依次移动)
    for(j = i; j <= L->length+1; j++)//注意j=0的情况，j=0会执行循环，执行后j会减1
    { 
        L->elem[j - 1] = L->elem[j];
        printf("j = %d;i = %d\n",j,i);//调试使用
    }
    L->length--;//表长减1 

    return OK;
}

运行结果

从算法复杂度简要分析上述操作：

算法时间主要耗费在移动元素的操作上。
若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中n-1个元素全部前移（特别慢）；

顺序表插入算法的平均时间复杂度为O(n)。

小结

本节主要记录了线性表的按值查找元素的位置、表中增加新结点、删除结点的三个操作。后两个思路都差不多，都是要去移动操作位置后面的元素。根据思路可以自行写代码实现。总结几个小点：

• 传入的顺序表参数，需要传入地址，不能直接传入L（SqList L）。
• 在循环语句中作比较时需要考虑数据类型不同
• 减减操作一定要特别注意变量0减1后将会什么值
• 在插入结点设计时需要判断储存表的长度，存储的空间是否还有空位存
• 上述的代码主要学习思路，处理的方法，部分细节还有待优化！

写到这里，线性表的顺序存储方式差不多记录完毕了，下一章将开始进行链式存储的学习记录了，也是很重要的知识点。

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

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

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

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