混子数据结构学习之第二章线性表链式表示之基本操作查询、取值

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

前言

本篇将补充几个操作，主要涉及到链表的按地址取值、查询地址、删除、插入某一个结点这些操作，有了前面那些操作的学习，理解这些其实相对很简单了。

链表的基本操作的补充

取值操作

概念：就是取出第i个结点的数据。

算法步骤

• 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
• j做计数器，累计当前扫描过的结点数，j初值为1。
• 当p指向扫描到的下一结点时，计数器j加1。
• 当j == i时，p所指的结点就是要找的第i个结点。

代码实现

说明：

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

 //--------取值：取单链表中第i个元素的内容
ElemType GetElem_L(LinkList L, int i)
{
    LinkList p; //定义一个结点地址，用于存储
    unsigned int k = 1;

    p = L->next; 
    while(p && k < i) //向后扫描，直到p指向第i个元素或p为空 
    {
        p = p->next;
        ++k;//记录位置（不能和前面的写反）
    }
    //printf("测试检查：%d\n",p->date);

    if(!p || k > i)//第i个元素不存在
    { 
        return FALSE;
    }
    return p->date;//取第i个元素 
}

按值查找地址

概念：就是给定一个数值，看这个值在链表的哪个位置（地址），当然这个位置可以是对应的存储地址也可以是从链表顺序上看的第几个的位置。
下面就说查找实际地址一种，另外的也类似，加个计数的变量即可得出位置！
算法步骤：

• 从第一个结点起，依次和e相比较。
• 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址。
• 如果普遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。

代码实现

说明：

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

//----取地址：查找指定元素的地址
Node* Get_Address(LinkList L, ElemType e)
{
    LinkList p; //定义一个结点地址，用于存储
    p = L->next;

    while((p->date != e) && (p != NULL))
    {
        p = p->next;
    }
    if(p->date == e)
    {
       return p;
    }
    else
    {
         return NULL;
    }
}

删除第i个结点元素

概念：
删除指定的第i个结点，销毁结点的空间。

算法步骤：

• 首先找到ai-1结点的指针域P，保存要删除的ai结点。
• 使P->next保存ai+1的结点的地址域。
• 释放结点ai的空间。

代码实现

//----删除第i个结点，释放结点的空间
unsigned char  NodetDelete_L(LinkList *L,  int i, ElemType *e)//需要操作链表的结点，故传入二级指针，等同于Node **L
{
    LinkList p,q; //定义一个结点地址，用于存储
     int k = 1;

    p = *L; //临时储存要处理的链表 注意不要少*

    while( p->next && k < i )//寻找第i个结点，并令p指向其前驱
    { 
        p = p->next;//遍历移动链表中的各个结点
        ++k;
    }

    if(!(p->next) || k > i )//删除位置不合理，出错
    {
        return FALSE;
    }

    q =  p->next;//临时保存被删结点的地址以备释放 
    p->next = q->next;//改变删除结点前驱结点的指针域 
    *e = q->date;//保存删除结点的数据域 
    free(q);//释放删除结点的空间 

    return OK;
}

在第i个位置插入结点

概念：
在指定的位置插入新的结点。

算法步骤：

• 首先找到ai结点的指针域P；
• 生成一个结点S；
• 插入新结点：新结点的指针域指向结点ai+1;结点ai-1的指针域指向新结点。

代码实现

//---在第i个位置（ai）插入结点，开辟空间 
// s->next = p->next; p->next = s;
unsigned char  NodeInsert_L(LinkList *L,  int i, ElemType e)//需要操作链表的结点，故传入二级指针，等同于Node **L
{
    LinkList p,s; //定义一个结点地址，用于存储
     int k = 1;

    p = *L; //临时储存要处理的链表 注意不要少*

    while( p && k < i )//寻找第i个结点
    { 
        p = p->next;//遍历移动链表中的各个结点
        ++k;
    }

    if(!p || k > i )//插入位置不合理，出错
    {
        return FALSE;
    }
    s = (LinkList)malloc((sizeof(Node)));//生成新的结点，开启结点空间
    s->date = e;//新结点数据域
    s->next = p->next;//新结点指针域指向p的后继
    p->next = s; //s成为p的后继

    return OK;
}

过程记录注意点

• 在写删除结点的程序时，写p = *L;这句临时存储头结点的语句时，少写了指针号，导致出错，得不到对应的结果，调试了好久才发现这个问题。这里传入的L是地址，而p相当于是一个链表的类型，故加取出对应的值。

小结

这部分代码还是比较有共性的，特别是删除和插入结点的操作，可以类比学习。对比线性结构的插入删除操作，链表是相对方便的，效率也直观感受到很高，线性表中需要每一个结点都进行依次移动，但是链表并不需要，只要找出上一个结点就可以对其操作。
记住核心操作基本就可以掌握了这些算法了。

• p = p->next;
• q = p->next; p->next = q->next;//删除操作核心逻辑
• s->next = p->next; p->next = s;//插入操作核心逻辑

好了，就到这里了，睡觉了，最近也没时间学习写，疫情来了............

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

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

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

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

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