《数据结构教程》2.1-2.2 顺序表

定义

线性表 是由 n 个属于 同一数据对象 的数据元素组成的有限序列。除序列的第一个数据元素与最后一个数据元素之外，其他任何一个数据元素有且仅有一个直接前驱元素，有且仅有一个直接后继元素。

线性表的存储结构可以采用 顺序存储结构 和 链式存储结构，采用顺序存储结构的线性表又称为 顺序表。

顺序表

特点：逻辑位置相邻的数据元素在物理位置上也一定相邻。

只要确定了首地址，线性表中任意一个数据元素可以随机存取。因此，可以称线性表的存储结构为一种随机存取的存储结构。

优点：简单、易理解，存储密度大，实际占用最少的存储空间。
缺点：需要占用一片地址连续的整块空间，可能造成空间浪费。并且存储分配要事先进行，插入、删除效率低。

C 语言实现

书中介绍了顺序表的几种常见操作，本文尝试用完整 C 语言实现。

头文件与宏定义

编写 util.h 头文件，定义 ERRORMESSAGE，需要抛出异常时打印 log 并退出。在顺序表的实现中，ElemType 为 int。

#include <stdio.h>
#include <stdlib.h>

#define ERRORMESSAGE(msg) \
{  \
  printf(msg);  \
  exit(1); \
}

typedef int ElemType;

顺序表实现

编写 02-list.c 文件，是顺序表的实现文件。

// 引入 util 头文件
#include "util.h"
// 假设顺序表最多存放 100 个数据元素
#define MaxSize 100

// 声明顺序表（使用数组实现）
ElemType A[MaxSize];
// 顺序表实际存储元素数量
int n = 0;

插入元素

书中的定义是第 i 个位置，下同，也就是说参数是从 1 开始的。顺序表的插入操作时间复杂度为 O(n)。

/**
 * 在长度为 n 的线性表 A 的第 i 个位置插入一个新数据元素 item
 */
void insertList(ElemType A[], int *n, int i, ElemType item) {
  if (*n == MaxSize || i < 1 || i > *n + 1) {
    ERRORMESSAGE("表满或插入位置不正确！");
  }

  for (int j = *n - 1; j >= i - 1; j--) {
    A[j + 1] = A[j];
  }

  A[i - 1] = item;

  (*n)++;
}

删除指定位置的元素

时间复杂度为 O(n)。

/**
 * 删除长度为 n 的线性表 A 的第 i 个数据元素
 */
void deleteList(ElemType A[], int *n, int i) {
  int j;
  if (i < 1 || i > *n) {
    ERRORMESSAGE("表满或删除位置不正确！");
  }

  for (j = i; j < *n; j++) {
    A[j - 1] = A[j];
  }

  (*n)--;
}

查找元素的位置

时间复杂度为 O(n)。

/**
 * 确定元素 item 在长度为 n 的线性表 A 中的位置
 */
int locate(ElemType A[], int n, ElemType item) {
  for (int i = 0; i < n; i++) {
    if (A[i] == item) {
      return i + 1;
    }
  }

  return -1;
}

删除表中重复的元素

时间复杂度为 O(n^2)。

/**
 * 删除表中重复出现的元素
 */
void purge(ElemType A[], int *n) {
  int i = 0, j;
  while (i < *n) {
    j = i + 1;

    while (j < *n) {
      if (A[j] == A[i]) {
        deleteList(A, n, j + 1);
      } else {
        j++;
      }
    }

    i++;
  }
}

查找并删除元素

一般的实现方式是先遍历查找，如果找到了进行删除操作，时间复杂度为 O(n^2)。

优化版的时间复杂度为 O(n)，因为只需要记录符合条件（需要被删除）的个数，一遍遍历即可完成操作。

/**
* 基础版
*/
void deleteItem(ElemType A[], int *n, ElemType item) {
  int i = 0;
  while (i < *n) {
    if (A[i] == item) {
      deleteList(A, n, i + 1);
    } else {
      i++;
    }
  }
}

/**
* 优化版
*/
void deleteItem2(ElemType A[], int *n, ElemType item) {
  int k = 0;
  for (int i = 0; i < *n; i++) {
    if (A[i] == item) {
      k++;
    } else {
      A[i - k] = A[i];
    }
  }

  *n = *n - k;
}

打印数组

void printList(ElemType A[], int *n) {
  for (int i = 0; i < *n; i++) {
    printf("%d", A[i]);
  }

  printf("\n");
}