Linear Tables

Linear Tables

五月 29, 2021

线性表存储结构

  1. 线性表（List）的定义：零/多个数据元素的有限序列

    1. List主要性质：

      1. 是一个有限序列
      2. 元素之间是有顺序的
      3. 存在==直接前驱元素==和==直接后继元素==
      4. 第一个元素无前驱，最后一个元素无后继

    2. 线性表长度：元素个数 n

    3. 空表：n=0

    4. 位序：（ai）中的i

  2. 线性表的抽象数据类型

    1. 传参原则：(传递一个参数给函数时，参数会不会在函数内被改动决定了使用什么传参形式)

      1. 如果需要被改，==传递==指向这个参数的==指针==
      2. 如果不需要被改，直接==传递==这个==参数==
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    ADT List
    Data
       对象集合为{a1,a2,...,an}
    Operation
       InitList(*L)
       ListEmpty(L)
       ClearList(*L)
       GetElem(L,i,*e)
       LocateElem(L,e)
       ListInsert(*L,i,e)
       ListDelete(*L,i,*e)
       ListLength(L)
       endADT

  3. 线性表的顺序存储结构

    1. 定义与性质：用一段==地址连续==的==存储单元==依次存储线表的==数据元素==

      1. 存储方式：顺序占位 O(1)

      2. 实现方式：一维数组

        1. 估算最大存储容量，建立数组

        2. （固定）数组长度==最大存储容量

          1
          2
          3
          4
          5
          6
          7
          #define MAXSIZE 20
          typedef int ElemType;
          typedef struct
          {
             ElemType data[MAXSIZE];
             int length;
          }SqList;

      3. 顺序存储结构三属性：

        data：数组data的存储空间初始位置就是存储空间的存储位置

        MAXSIZE：最大存储容量/数组(据)长度

        int length：当前线性表长度

    2. 地址的计算方法：==数据元素的序号==与存放的数组==下标==存在==对应==关系

data[]（下标） 0 1 … i-2 i-1 … n-1 空闲空间
a? a1 a2 … ai-1 ai … an
  • C语言：数组地址从 0 开始，对应数据元素序号为 n-1

    1. 顺序存储结构的查找、插入、删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /*
    查找获取线性表L中第i个位置（对应data[i-1]）の元素值
    时间复杂度：O(1)
    */
    #define OK 1
    #define ERROR 0
    typedef int Status;
    Status GetElem(SqList L,int i,ElemType *e)
    {
        if(L.length==0 || i<1 || i>L.length)
        {
            return ERROR;    
        }
        *e=L.data[i-1];
        return OK;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    /*
    插入算法思路：
        1.如果插入位置不合理，抛出异常
        2.如果线性表长度大于等于数组长度，抛出异常或动态扩容
        3.最后一个元素**向前遍历**到第i个位置，分别都后移一个位置
        4.插入元素到i处
        5.length+1
    关键点：
         a1.第 i 个元素 == data[i-1]
        a2. k 从表倒数第二位循环向前推进覆盖 k+1
    */
    Status ListInsert(SqList *L,int i,ElemType e)
    {
        int k;
        if(L->length==MAXSIZE)    //1
        {
            return ERROR;    
        }
        if(i<1 || i>L->length+1)    //2
         {
            return ERROR;
        }
        if(i<=L-length)        //3
        {
            for(k=L->length-1;k>=i-1;k--)
            {
                L->data[k+1]=L->data[k];
            }
        }
        L->data[i-1]=e;    //4
        L->length++;    //5
        return OK;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /*
    删除算法思路：
        1.异常检测判断：删除位置不合理，抛出异常
        2.取出/记录删除元素
        3.循环覆盖实现删除：从删除元素位置开始遍历到最后一个元素位置，分别向前移动一位
        4.length-1
    */
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int k;
        if(L->length==0)    //空表
        {
            return ERROR;
        }
        if(i<1 || i>L->length)    //1
        {
            return ERROR;
        }
        *e=L->data[i-1];    //2
        if(i<L->length)
        {
            for(k=i;k<L->length;k++)
            {
                L->data[k-1]=L->data[k];    //3
            }
            L->length--;    //4
            return OK;
        }
    }
    • 读取时间复杂度：O(1)
    • 插入、删除时间复杂度：【平均】O(n)【最坏】O(n)【最好】O(1)
    • 顺序存储优势：
      • 方便存、取
    • 顺序存储劣势：
      • 不方便增、删
      • 难以确定存储空间容量
      • 造成存储空间碎片

  1. 线性表的链式存储结构

    1. 链式存储结构的定义：n个结点链结成一个链表

      1. 数据域：存储数据元素信息（data）的域
      2. 指针域：存储直接后继（next）位置的域
        1. 指针/链：指针域中存储的信息
        2. 最后一节结点的指针域：NULL / ^
      3. 结点：数据域+指针域=数据元素ai
      4. 单链表：每个结点只包含一个指针域
      5. 头指针：（必要元素）指向链表中第一个结点的存储位置
      6. 头结点：（非必要元素，为了方便操作）人为设置，置于第一个结点前【数据域：不存储任何信息/存储如线表长度等附加信息】【指针域：指向第一个结点的指针】

    2. 链式存储结构-建立单链表

      1. （数据域）存放数据元素：ai=p->data，ai+1=p->next->data

      2. （指针域）存放一个指针：p->next

        1
        2
        3
        4
        5
        6
        typedef struct Node
        {
            ElemType data;    //数据域
            struct Node *next;    //指针域（后继）
        }Node;
        typedef struct Node *LinkList;

    3. 单链表的读取：“工作指针后移”遍历查找（GetElem）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      /*
      遍历思路：
          1.声明指针p指向链表第一个结点，初始化计数器j=1
          2.当j<i时，遍历链表，p的指针向后移动，j++
          3.若链表末尾p为空，第i个结点不存在
          4.否则查找成功，返回数据p->data
      */
      Stuatus GetElem(LinkList L,int i,ElemType *e)
      {
          int j;
          LinkLisk p;
          p=L->next;    //1
          j=1;    //1
          while(p && j<1)
          {
              p=p->next;    //2
              ++j;
          }
          if(!p || j>i)    //3.（不为非空）!p!=0 --> p==0
          {
              return ERROR;
          }
          *e=p->data;    //4.取出数据p->data
          return OK;
      }

    4. 单链表的插入、删除：O(n)【插删操作越频繁，效率优势越明显】

      1. 插入：覆盖指针域（先右后左） s->next = p->next; p->next = s;

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        /*
        插入算法思路：
            1.声明指针p指向链头，初始化计数器j=1
            2.异常判断，指针p循环遍历到第i位，j++
            3.若链表末尾p为空，说明第i个结点不存在
            4.否则查找成功，动态扩容生成一个空节点s
            5.**数据元素e赋值给s->data**
            6.**覆盖插入指针域**
            7.return OK;
        */
        Status ListInsert(LinkList *L,int i,ElemType e)
        {
            int j;
            LinkList p,s;
            p = *L;    //1.指向链头
            j = 1;    //1.计数器
            while(p && j<i)    //2
            {
                p = p->next;
                ++j;
            }
            if(!p || j>i)    //3
            {
                return ERROR;
            }
            s=(LiskList)malloc(sizeof(Node));    //4.malloc()
            s->data = e;    //5
            s->next = p->next;    //6
            p->next = s;    //6
            return OK;    //7
        }

      2. 删除：后继的后继结点覆盖后继节点 q = p->next; p-next = q->next; //p->next->next;

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        /*
        删除算法思路：
            1.声明指针p指向表头，初始化计数器j=1
            2.j<i，p指针循环遍历链表到i-1，j++
            3.异常检测：若链表末尾p为空，说明i结点不存在
            4.**否则查找成功，取出后继节点p->next赋值给q**
            5.**后继的后继q-next结点覆盖后继节点p->next**
            6.q结点中数据赋值给返回值e
            7.释放q结点【free();】
            8.return OK;
        */
        Status ListDelete(LinkList *L,int i,ElemType *e)
        {
            int j;
            LinkList p,q;
            p = *L;    //1
            j = 1;    //1
            while(p && j<i)    //2.p指针循环遍历移动到第i-1个元素
            {
                p = p->next;
                ++j;
            }
            if(!(p->next) || j>i)    //3.异常检测
            {
                return ERROR;
            }
            q = p->next;    //4
            p->next = q->next;    //5
            *e = q->data;    //6
            free(q);    //7
            return OK;    //8
        }

    5. 单链表的整表创建：动态生成链表的过程

      1. 头插法创建：（在头结点后面）循环插入，向后延伸

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        /*
        头插法创建思路：
            1.声明指针p和计数器j
            （初始化随机数发生器）
            2.创建一个只有头结点的单链表，L头结点指针指向NULL
            3.循环生成结点，接在头结点后面延伸
                a.生成新结点赋值给p
                b.随机生成数据赋值给 p的数据域->data
                c.单链表插入结点操作
        */
        void CreatListHead(LinkList *L,int n)
        {
            LinkList p;
            int i;
            srand(time(0));
            *L=(LinkList)malloc(sizeof(Node));
            (*L)->next=NULL;
            for(i=0;i<n;i++)
            {
                p=(LinkList)malloc(sizeof(Node));
                p->data=rand()%100+1;    //1~100，rand()%100:0~99
                p->next=(*L)->next;
                (*L)->next=p;
            }
        }

      2. 尾插法创建：先来后到，延长尾巴

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        /*
        尾插法创建思路：
            1.声明指针p，和指向表尾的指针r
            （初始化随机数发生器）
            2生成一个（暂时作为）尾结点
            3.循环生成结点，替代前一个尾结点作为新的尾结点
                a.生成新尾结点赋值给p，生成随机数赋值给数据域p->data
                b.p指针指向结点赋值给r->next：接在r后面
                c.p赋值给r，r指针更新尾结点
            4.生成结点结束，最终确定尾结点，指针域r->next赋空
        */
        void CreatListTail(LinkList *L,int n)
        {
            LinkList p,r;    //1
            int i;    
            srand(time(0));
            *L=(LinkList)malloc(sizeof(Node));    
            r=*L;
            for(i=0; i<n ; i++)    //3
            {
                p = (Node *)malloc(sizeof(Node));    //3.a
                p->data=rand()%100+1;    //3.a
                r->next=p;    //3.b
                r=p;    //3.c
            }
            r->next=NULL;    //4
        }

    6. 单链表的整表删除

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      /*
      删除算法思路：
          1.【皇帝->太子】声明指针p负责释放结点，【遗嘱】指针q负责索引下一个待释放的结点
          2.从第一个结点开始（头结点->next==第一个结点，赋值给p）
          3.循环释放操作
              a.先将下一个结点p->next赋值给索引指针q
              b.释放p结点【free()】
              c.q赋值给p，继续下一个循环释放
          4.只剩下头结点，循环释放结束
      */
      Status ClearList(LinkList *L)
      {
          LinkList p,q;    //1
          p=(*L)->next;    //2
          while(p)    //3.循环释放
          {
              q=p->next;    //3.a
              free(p);    //3.b
              p=q;    //3.c
          }
          (*L)->next=NULL;    //4
          return OK;
      }

    7. 静态链表【游标实现法】

      1. 建立数组描述的单链表： 每一个下标对应data（存放数据元素）、cur（存放后继的游标 == next）

        1. 备用链表：未被使用的空闲空间
        2. 特殊元素：头&尾
          1. 【≈索引指针】数组第一个元素cur存放备用链表第一个结点的下标
          2. 【≈头结点】数组最后一个元素cur存放第一个数值元素的下标（空链表：cur == 0）
        1
        2
        3
        4
        5
        6
        7
        /*创建静态链表*/
        #define MAXSIZE 1000    //定义容量
        typedef struct
        {
            ElemType data;
            int cur;
        }Component,StaticLinkList[MAXSIZE];

      2. **初始化**数组状态：生成一个空链

        1. 第i结点指针域（i->next）：space[i].cur
        2. 头指针：space[0].cur
        3. 空指针：“0”
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        Status InitList(StaticLinkList space)    //int InitList(){}
          {
            int i;
            for (i=0;i<MAXSIZE-1;i++)    //下标i == n-1
            {
                space[i].cur = i+1;    //第i个元素的cur指向i+1 (i->next = i+1;)
            }
            space[MAXSIZE-1].cur = 0;    //空链：头结点的next为空
            return OK;
          }

      3. 实现Malloc函数动态扩容：查找当前第一个新待插入空节点：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        /*
        扩容：查找当前备用链表第一个空变量：
            1.初始第一个空闲节点（第一个内存空间的cur）赋值给i
            2.循环遍历：当第一个结点的cur不为空
                a.下一个结点作为新的第一个空闲节点，实现扩容+1
            3.返回i
        */
        int Malloc_SSL(StaticLinkList space)
        {
            int i = space[0].cur;    //1
            if(space[0].cur)    //2
            {
                space[0].cur = space[i].cur;    //2.a
            }
            return i;    //3
        }

      4. 插入操作：只需改变数组两个cur值（偷天换日）

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        /*
        k：查找原i的cur
        i：待插入到的位数
        j：新产生的数据下标
        插入：交换cur
            1.声明记录变量j、k、l，k从最大容量最后一位下标开始计算
            2.异常检测
            3.新节点下标赋值给j
            4.判断j是否为空（空间剩余）
                (1)e赋值数据域
                (2)循环遍历到第i个元素（遍历到原i-1位置）
                    a.L[k].cur指向原i结点（即k为i-1结点位置）
                (3)改变cur实现插入1：新元素cur（L[j].cur）指向原i结点（L[k].cur）
                (4)改变cur实现插入2：原i-1结点的cur（L[k].cur）指向新节点（j）
        */
        Status ListInsert(StaticLinkList L,int i,ElemType e)
        {
            int j,k,l;
            k=MAXSIZE - 1;    //1
            if(i < 1 || i > ListLength(L) + 1)    //2
            {
                return ERROR;
            }
            j=Malloc_SSL(L);    //3
            if(j)    //4
            {
                L[j].data = e;    //4(1)
                for(l = 1;l <= i-1;l++)    //4(2)
                {
                    k = L[k].cur;    //4(2).a
                }
                L[i].cur=L[k].cur;    //4（3）
                L[k].cur=j;    //4（4）
                return OK;
            }
            return ERROR;
        }

      5. 实现free内存释放函数：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        /*
        已删除结点成为新的第一空闲结点（space[0].cur）
            1.已删除结点的cur指向原第一空闲结点
            2.k结点成为新的第一空闲元素，原space[0].cur成为第二空闲元素
        */
        void Free_SSL(StaticLinkList space,int k)
        {
            space[k].cur = space[0].cur;    //1
            space[0].cur = k;    //2
        }

      6. 删除操作：确定需要释放的元素i，调用Free_SSL函数进行释放

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        /*
        确定需要释放的元素i：
            1.异常判断
            2.k从最大容量最后一位下标开始计算
            3.循环遍历到i-1位置
            4.将第i位结点赋值给j（L[j].cur）
            5.j的下一个结点作为新的第一个（有数据）结点
            6.调用赋值函数Free_SSL
        */
        Status ListDelete(StaticLinkList L,int i)
        {
            int j,k;
            if(i<1 || i>ListLength(L))    //1
            {
                return ERROR;
            }
            k=MAXSIZE-1;    //2
            for(j = 1;j <= i-1;j++)    
            {
                k= L[k].cur;    //3
            }
            j = L[k].cur;    //4
            L[k].cur = L[j].cur;    //5
            Free_SSL(L,j);    //6.传递k=j
            return OK;
        }

      7. 遍历检测静态链表长度：返回数据元素个数

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        int ListLength(StaticLinkList L)
        {
            int j=0;
            int i=L[MAXSIZE-1].cur;    //最后元素的cur存放第一个（有数据）结点位置
            while(i)
            {
                i=L[i].cur;    //循环往后遍历，直到i为空
                j++;
            }
            return j;
        }

    8. 循环链表：单链表尾接上头构成一个环

      1. 空循环链：头指针head->next指向头指针head

      2. （非空）循环链：p->next != head，则未到尾结点【头O(1)；尾O(n)】

      3. 改造循环链：增加一个尾指针rear，第一个结点为rear->next->next【头O(1)；尾O(1)】

      4. 链接两个带头结点的循环链表：都有头结点，只保留一个

        1
        2
        3
        4
        5
        p = rearA->next;
        rearA->next = rearB->next->next;
        q = rearB->next;
        rearB->next = p;
        free(q);    //释放B的头结点，只保留A头

    9. 双向链表：增加一个直接前驱指针prior的单链表

      1. 双向链表存储结构：

        1
        2
        3
        4
        5
        6
        typedef struct DulNode
        {
            ElemType data;
            struct DuLNode *prior;
            struct DuLNode *next;
        }DuLNode,*DuLinkList;    //DuLNode是定义了一个双向循环链表,而*DuLinkList是定义了一个可以指向链表的指针(类型同链表)

      2. 双向空循环链：头结点空链，rear，next两个指针都指向head

      3. 双向非空循环链：前驱的后继（p->rear->next） == 后继的前驱（p->next->rear） == 自己（p）

      4. 插入操作原则：改4个数据，注意顺序

        1. ==先改新==（待插入的结点），==再改旧==（原来前后结点指针域）
        2. ==先改后==（后继next），==再改前==（前驱rear）
        1
        2
        3
        4
        s->prior = p;
        s->next = p->next;
        p->next->prior = s;
        p->next = s;

      5. 删除操作：改2个数据，顺序可交换

        1
        2
        3
        p->prior->next = p->next;    //切断p前一个结点的next
        p->next->prior = p->prior;    //切断p后一个结点的prior
        free(p);
  1. 1. 线性表存储结构
    1. 1.0.1. 线性表（List）的定义：零/多个数据元素的有限序列
      1. 1.0.1.1. List主要性质：
      2. 1.0.1.2. 线性表长度：元素个数 n
      3. 1.0.1.3. 空表：n=0
      4. 1.0.1.4. 位序：（ai）中的i
    2. 1.0.2. 线性表的抽象数据类型
      1. 1.0.2.1. 传参原则：(传递一个参数给函数时，参数会不会在函数内被改动决定了使用什么传参形式)
    3. 1.0.3. 线性表的顺序存储结构
      1. 1.0.3.1. 定义与性质：用一段==地址连续==的==存储单元==依次存储线表的==数据元素==
      2. 1.0.3.2. 地址的计算方法：==数据元素的序号==与存放的数组==下标==存在==对应==关系
      3. 1.0.3.3. 顺序存储结构的查找、插入、删除
    4. 1.0.4. 线性表的链式存储结构
      1. 1.0.4.1. 链式存储结构的定义：n个结点链结成一个链表
      2. 1.0.4.2. 链式存储结构-建立单链表
      3. 1.0.4.3. 单链表的读取：“工作指针后移”遍历查找（GetElem）
      4. 1.0.4.4. 单链表的插入、删除：O(n)【插删操作越频繁，效率优势越明显】
      5. 1.0.4.5. 单链表的整表创建：动态生成链表的过程
      6. 1.0.4.6. 单链表的整表删除
      7. 1.0.4.7. 静态链表【游标实现法】
      8. 1.0.4.8. 循环链表：单链表尾接上头构成一个环
      9. 1.0.4.9. 双向链表：增加一个直接前驱指针prior的单链表