数据结构学习笔记之单链表的相关操作

      用链接存储方式存储的线性表被称为链表，链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散的分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加、删除结点，动态调整。

      为了能正确表示结点之间的逻辑关系，一个存储单元（假定每个结点需要一个存储单元）除了存放结点的数据字段的值，还必须存放其逻辑相邻节点（前驱结点或后继结点）的地址信息，这个地址信息被称为指针。根据结点指针域的不同，链表主要有三种实现方式：单链表、循环链表和双向链表。本次只记录学习单链表的相关问题。

      一个单链表的结点由数据域data和指针域next构成。其中数据域data存放该结点的数据域的值，指针域next存放该结点的后继结点的地址信息。链表的第一个结点被称为头结点（也称为表头），指向头结点的指针被称为头指针（head）。

      一、存取算法

     要求将链表中的第k个结点的字段值赋给item，只需在保证算法合法的前提下，从表头开始逐一访问链表结点，直至找到第k个结点为止。

       ADL语言实现：

       算法Find（k.item）//将链表中第k个结点的字段值赋给item
       F1.[k合法？]
            IF（k<1）THEN（PRINT“存取位置不合法”.RETURN.）
       F2.[初始化]
             p<-head.i<-0.   //令指针p指向哨位结点，计数器初始值为0
       F3.[找第k个结点]
            WHILE（p≠NULL AND i<k）DO
                     （p<-next(p).i<-i+1.）  //若找到第k个结点或已达到表尾，则循环终止
            IF p=NULL THEN(PRINT"无此结点".RETURN.)

            item<-data(p).  ▎

    C++语言实现：

            

       

       二、查找算法

       要求在链表中查找字段值为item的结点并返回其在表中的位置。同存取算法类似，类似算法也需要从表头开始逐一访问链表结点，并比较每个结点的字段值是否为item，直至找到该结点或已遍历至表尾仍未找到。

       ADL语言实现：

     算法 Search（item.i）//在链表中查找字段值为item的结点并返回其在链表中的位置

       S1.[初始化]
              p<-next(head).i<-1.//令指针p指向哨位结点的后继结点，计数器初始值为1
       S2.[逐点访问]
            WHILE（p≠NULL AND data(p)≠item）DO
                     （p<-next(p).i<-i+1.）  //令指针p指向下一结点，且计数器加一
            IF p≠NULL THEN RETURN i.

            PRINT“无此结点”.RETURN -1. ▎

     C++语言实现：

     

    三、删除算法

       要求删除链表中第k个结点并将其字段值赋给item。该算法首先需要找到第k-1个结点，并存取其后继结点（第k个结点）的字段值，其实现过程与存取算法Find类似；然后修改第k-1个结点的next指针使其指向第k+1个结点。需要注意的是，在此过程中应该用一个临时指针指向被删除结点，并最终释放结点所占用的存储空间，否则该部分空间将成为存储空间中无法利用的垃圾。

       ADL语言实现：

       算法Delete（k.item）//删除链表中第k个结点并将其字段值赋给item
       D1.[k合法？]
            IF（k<1）THEN（PRINT“删除位置不合法”.RETURN.）
       D2.[初始化]
             p<-head.i<-0.   //令指针p指向哨位结点，计数器初始值为0
       D3.[找第k-1个结点]
            WHILE（next(p)≠NULL AND i<k-1）DO
                     （p<-next(p).i<-i+1.） 
            IF next(p)=NULL THEN(PRINT"无此结点".RETURN.)
       D4.[删除]
            q<- next(p). next(p) <- next(q). //修改p的next指针

            item<-data(q). AVAIL<=q. //存取q的字段值并释放存储空间  ▎

     C++语言实现：

        

    四、插入算法

       在链表中第k个结点后插入字段值为item的结点。该算法首先要找到第k个结点，其实现过程与存取算法Find类似；为新插入结点申请存储空间，并令其next指针指向第k+1个结点；修改第k个结点的next指针，令其指向新插入结点。

       ADL语言实现：

       算法Insert（k,item. head）//在链表中第k个结点后插入字段值为item的结点

       I1.[k合法？]
            IF（k<0）THEN（PRINT“插入位置不合法”.RETURN.）
       I2.[初始化]
             p<-head.i<-0.   //令指针p指向哨位结点，计数器初始值为0
       I3.[p指向第k个结点]
            WHILE（p≠NULL AND i<k）DO
                     （p<-next(p).i<-i+1.） 
            IF p=NULL THEN(PRINT"插入位置不合法".RETURN.)
       I4.[插入]
            s<=AVAIL. data(s)<-item. next(s) <- next(p). //生成新结点s，其next指针指向p的后继结点

            next(p)<-s. //修改p的next指针，令其指向新插入结点s  ▎

     C++语言实现：

       

以上算法时间复杂度最好情况下均为O（1），平均和最坏情况下均为O（n）。