2.2顺序表

​​​一、顺序表的定义​​

• ​​逻辑结构​​：线性表是具有​​相同数据类型​​的n（n≥0）个数据元素的​​有限序列​​。
• ​​存储结构​​：顺序表采用​​顺序存储​​，即逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素关系由存储单元的邻接关系体现。

​​二、顺序表的实现方式​​

​​1. 静态分配​​

• 使用静态数组，长度固定。
• 定义示例：

  #define MaxSize 10
  typedef struct {
      ElemType data[MaxSize];  // 存放数据元素的数组
      int length;              // 当前长度
  } SqList;

• ​​缺点​​：表长固定，无法扩展。

​​2. 动态分配​​

• 使用指针动态申请内存，更灵活。
• 定义示例：

  #define InitSize 10
  typedef struct {
      ElemType *data;     // 指向动态数组的指针
      int MaxSize;        // 最大容量
      int length;         // 当前长度
  } SeqList;

• ​​初始化操作​​：

  void InitList(SeqList &L) {
      L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
      L.length = 0;
      L.MaxSize = InitSize;
  }

• ​​优点​​：可扩展（但扩展时间复杂度较高）。

​​三、基本操作实现与分析​​

​​1. 插入操作：ListInsert(&L, i, e)​​

• 在位置i插入元素e。
• ​​代码实现​​：

  bool ListInsert(SqList &L, int i, ElemType e) {
      if (i < 1 || i > L.length + 1) return false;   // 判断i的有效性
      if (L.length >= MaxSize) return false;         // 判断是否已满
      for (int j = L.length; j >= i; j--)            // 后续元素后移
          L.data[j] = L.data[j - 1];
      L.data[i - 1] = e;
      L.length++;
      return true;
  }

• ​​时间复杂度​​：
  • 最好（插入表尾）：O(1)
  • 最坏（插入表头）：O(n)
  • 平均：O(n)

​​2. 删除操作：ListDelete(&L, i, &e)​​

• 删除位置i的元素，并通过e返回。
• ​​代码实现​​：

  bool ListDelete(SqList &L, int i, ElemType &e) {
      if (i < 1 || i > L.length) return false;       // 判断i的有效性
      e = L.data[i - 1];
      for (int j = i; j < L.length; j++)             // 后续元素前移
          L.data[j - 1] = L.data[j];
      L.length--;
      return true;
  }

• ​​时间复杂度​​：
  • 最好（删除表尾）：O(1)
  • 最坏（删除表头）：O(n)
  • 平均：O(n)

​​3. 按位查找：GetElem(L, i)​​

• 获取位置i的元素。
• ​​代码实现​​：

  ElemType GetElem(SqList L, int i) {
      return L.data[i - 1];
  }

• ​​时间复杂度​​：O(1)
  （利用“随机存取”特性）

​​4. 按值查找：LocateElem(L, e)​​

• 查找第一个值为e的元素并返回其位序。
• ​​代码实现​​：

  int LocateElem(SeqList L, ElemType e) {
      for (int i = 0; i < L.length; i++)
          if (L.data[i] == e)
              return i + 1;
      return 0;
  }

• ​​注意​​：结构体类型需自定义比较函数。
• ​​时间复杂度​​：
  • 最好（在表头）：O(1)
  • 最坏（在表尾或无）：O(n)
  • 平均：O(n)

​​四、顺序表的特点总结​​

​​五、重要考点回顾​​

• 区分​​静态分配​​与​​动态分配​​的优缺点。
• 掌握​​插入、删除、查找​​操作的代码实现。
• 熟练计算​​时间复杂度​​，理解最坏、平均情况。
• 注意​​结构体元素的比较​​需自定义函数。
• 理解​​顺序表的随机存取特性​​及其实现原理。