线性表

一、逻辑结构和基本操作

1. 逻辑结构

  • 具有相同数据类型的n个数据元素的有限序列，表长n，n=0为空表
  • 表头：第一个元素
  • 表尾：最后一个元素
  • 除第一个元素外，每个元素有且仅有一个直接前驱
  • 除最后一个元素外，每个元素有且仅有一个直接后继

    2. 基本操作

    initList(&L);
len(L);
locateElem(L, i);
getElem(L, i);
listInsert(&L, i, e);
listDelete(&L, i, &e);
printList(L);
isEmptyList(L);
destroyList(&L);

二、顺序存储结构

1. 定义：又称顺序表，使用一组地址连续的存储单元，依次存储线性表的数据元素，使逻辑上相邻的两个元素物理位置也相邻

  • 存储空间的起始位置data[ ]
  • 顺序表最大存储容量MaxSize
  • 顺序表当前最大长度len 特点
  • 随机访存，O(1)时间复杂度访问
  • 存储密度高，每个结点只存储数据元素
  • 无需花费空间建立数据之间的逻辑关系，由物理位置相邻特性决定
  • 逻辑上物理上均相邻，插入删除操作需要移动大量元素

    2. 基本操作

    （1）插入元素

    //插入元素
boolean listInsert(SqList &L, int i, Elemtype e){
  if(i < 1 || i  L.len + 1)
      return -1;
  if(L.len = MaxSize)
      return -1;
  for(int j = L.len; j  i; j--)
      L.data[j] = L.data[j - 1];
  L.data[i - 1] = e;
  L.len++;
}

    分析

  • 最好情况：在表尾插入 (i=n+1)，不需要移动元素，时间复杂度为O(1)
  • 最坏情况：在表头插入 (i=1)，元素后移n次，时间复杂度O(n)
  • 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n+1}\))，是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n}{2}\)，其时间复杂度为O(n)
    （2）删除元素 
    //删除元素
boolean listDelete(SqList &L, int i, Elemtype e){
  if(i < 1 || i  L.len + 1)
      return -1;
  e = L.data[i-1];
  for(int j = i; j < L.len; j++)
      L.data[j-1] = L.data[j];
  L.len--;
  return true;
}

    分析

  • 最好情况：在表尾插入 (i=n)，不需要移动元素，时间复杂度为O(1)
  • 最坏情况：在表头插入 (i=1)，元素后移n次，时间复杂度O(n)
  • 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n+1}\))，是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n-1}{2}\)，其时间复杂度为O(n)
    （3）查找元素 
      int locateElem(SqList &L, Elemtype e){
      int i;
      for(i = 0; i < L.len; i++)
          if(e == L.data[i])
              return i+1;
  }

    分析

  • 最好情况：查找的元素在表头，仅需比较1次，时间复杂度O(1)
  • 最坏情况：查找的元素在表尾或不存在，需要比较n次，时间复杂度O(n)
  • 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n}\))是在第i个位置上结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n+1}{2}\)，其时间复杂度为O(n)

    链式存储结构

    1.创建单链表

    （1）头插法

  • 为新插入的结点分配内存空间
  • 每次都是把插入的新结点放入表头(头结点位置)
  • 链表结点的次序与输入的顺序相反

    （2）尾插法

  • 为新插入的结点分配内存空间
  • 每次都是把插入的新结点放入表尾(尾结点位置)
  • 链表中的结点顺序与输入顺序一致

    2.按值查找结点

  • 在链表中从第一个结点出发，顺指针next逐个向下搜索，直到找到第i个结点，否则返回最后一个结点的指针域NULL

    3.按序号查找结点

  • 从链表第一个结点开始，由前往后按照序号递增定位到相应结点的位置，返回该值，需检查序号是否越界

    4.插入

  • 插入操作是将值为x的新结点插入到单链表的第i个位置
  • 先检查插入位置是否合法
  • 找到待插入位置的前驱结点
  • 在其后将结点插入 
      p = getElem(L, i-1)
  s-next = p-next;
  p-next = s;

    5.删除

  • 将单链表的第i个结点删除
  • 先检查插入位置是否合法
  • 找到待删除位置的前驱结点
  • 删除其后结点 
      p = getElem(L, i-1)
  q = p-next;
  q-next = p-next;
  free(q);

    双链表

  • 双链表有两个指针prior和next，分别指向前驱和后继结点
  • 插入操作 
      s-next = p-next;
  p-next-prior = s;
  s-prior = p;
  p-next = s;
  • 删除操作 
      p-next = q-next;
  q-next-prior = p;
  free(q);

    循环链表

  • 循环双链表和循环单链表
  • 静态链表使用数组来描述线性表的链式存储结构