本文作者:qiaoqingyi

链表查找编程(链表如何查找元素)

qiaoqingyi 02-02 142

  单链表上基本操作的实现

  5、插入结点操作

  插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第i-1个结点,再在其后插入新结点。

  算法首先调用(3)中的序号查找算法GetElem(L,i-1),查找第i-1个结点。假设返回的第i-1个结点为*p,然后令新结点*s的指针域指向*p的后继结点,再令结点*p的指针域指向新插入的结点*s。其操作过程如下图所示。

  实现插入结点的代码片段如下:

  

  

  算法中,语句2 3的顺序不能颠倒,否则,当先执行p-next=s后,指向其原后继的指针就不存在了,再执行s-next=p-next时,相当于执行了s-next=s,显然是错误的。本算法主要的时间开销在于查找第i-1个元素,时间复杂度为O(n)。若是在给定的结点后面插入新结点,则时间复杂度仅为O(1)。

  扩展:对某一结点进行前插操作

  前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反,在单链表插入算法中,通常都是采用后插操作的。

  以上面的算法为例,首先调用函数GetElem()找到第i-1个结点,即待插入结点的前驱结点后,再对其执行后插操作。由此可知,对结点的前插操作均可以转化为后插操作,前提是从单链表的头结点开始顺序查找到其前驱结点,时间复杂度为O(n)。

  此外,可以采用另一种方式将其转化为后插操作来实现,设待插入结点为*s,将*s插入到*p的前面。我们仍然将*s插入到*p的后面,然后将p-data与s-data交换即可,这样既满足了逻辑关系,又能使得时间复杂度为O(1)。算法的代码片段如下:

  

  6、删除结点操作

  删除操作是将单链表的第i个结点删除。先检查删除位置的合法性,然后查找表中第i-1个结点,即被删结点的前驱结点,再将其删除。其操作过程如下图所示。

  

  假设结点*p为找到的被删结点的前驱结点,为了实现这一操作后的逻辑关系的变换,仅需修改*p的指针域,即将*p的指针域next指向*q的下一结点。

  实现删除结点的代码片段如下:

  

  和插入算法一样,该算法的主要时间也是耗费在查找操作上,时间复杂度为O(n)。

  扩展:删除结点*p

  要实现删除某一个给定结点*p,通常的做法是先从链表的头结点开始顺序找到其前驱结点,然后再执行删除操作即可,算法的时间复杂度为O(n)。

  其实,删除结点*p的操作可以用删除*p的后继结点操作来实现,实质就是将其后继结点的值赋予其自身,然后删除后继结点,也能使得时间复杂度为O(1)。

  实现上述操作的代码片段如下:

  

  7、求表长操作

  求表长操作就是计算单链表中数据结点(不含头结点)的个数,需要从第一个结点开始顺序依次访问表中的每个结点,为此需要设置一个计数器变量,每访问一个结点,计数器加1,直到空结点为止。算法的时间复杂度为O(n)。

  需要注意的是,因为单链表的长度是不包括头结点的,因此,不带头结点和待头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表,但表为空时要单独处理。

  单链表是整个链表的基础,读者一定要熟练掌握单链表的基本操作算法,在设计算法时,建议先通过图示的方法理清算法的思路,然后再进行算法的编写。

  来自王道论坛(推荐购买正版),交流学习,每天一点点,有问题和建议在留言板留言~~

  qq群号:

链表查找编程(链表如何查找元素)

  群一:176792348

  群二:262739638

群三:274526397

  群功能:方便大家互相交流~~群文件中各种建模资料~~

  ps:数据结构

阅读
分享