顺序表

1. 线性表

1.1 基本概念

1. 定义：一种逻辑结构，表示 N 个相同类型元素的有限序列
2. 常见的线性表：顺序表，栈和队列，链表，字符串等
3. 线性表的数据集合可以写作 $\{a_1,a_2,a_3,...,a_n\}$，其中 $n$ 为线性表的 长度 (length)，$1,2,3,...,n$ 称为线性表中各个元素的 逻辑下标
4. 在线性表中，除最后一个元素（这个元素称为 终端节点 之外，每一个元素 $a_i$ 都有一个元素作为他的 后继 ，记作 $\mathrm{next}(a_i)$
5. 在线性表中，除第一个元素（这个元素称为 开始节点）之外，每一个元素 $a_i$ 都有一个元素作为他的 前驱 ，记作 $\mathrm{prev}(a_i)$

1.2 基本操作

1. 置空 (clear())
2. 判空 (isEmpty())
3. 长度 (length())
4. 取元素 (get(i))
5. 插入 (insert(i,x))
6. 删除 (remove(i))
7. 查找 (indexOf(x))

2. 顺序表 (SeqList) 示例代码

2.1 基本概念

1. 元素存储在一段 逻辑地址连续 的存储单元上, 连续保证了可以用指针偏移的方式访问
2. 通常使用数组实现
3. 因为数组下标从 0 开始，所以 逻辑下标 为 1 的元素存储在数组下标为 0 的位置上，这个下标称为此元素的 * 物理下标*
4. 在顺序表中，通常情况下，物理下标 = 逻辑下标-1
   此二级标题包裹的内容中，下标 默认指 物理下标
5. 顺序表可以用一个定长数组实现，但容易造成“不够用”和“过剩”，所以一般动态开辟和扩容数组

2.2 实现

1. 构建结构体

   typedef int ElementType;
   typedef struct {
       ElementType* arr;
       size_t size; // length of the sequence list
       size_t capacity; // size of the array
   } SeqList;

2. 初始化

   1. 初始化空顺序表

      void initSeqList(SeqList* l) {
          l->arr = (ElementType*)malloc(sizeof(ElementType) * g_initCap);
          if (!(l->arr)) {
              printf("Intitalization failed!\n");
              exit(-1);
          }
          l->size = 0;
          l->capacity = g_initCap;
      }

   2. 以数组初始化顺序表

      void initSeqListFromArray(SeqList* l, ElementType* a, int length) {
          l->arr = (ElementType*)malloc(sizeof(ElementType) * length);
          if (!(l->arr)) {
              printf("Intitalization failed!\n");
              exit(-1);
          }
          for (size_t n = 0; n < length; ++n)
              l->arr[n] = a[n];
          l->size = length;
          l->capacity = length;
      }

3. 清空

   void clearSeqList(SeqList* l) {
       free(l->arr);
       initSeqList(l);
   }

4. 判空

   bool isSeqListEmpty(SeqList* l) { return l->size == 0; }

5. 长度

   size_t lengthOfSeqList(SeqList* l) { return l->size; }

6. 取元素

   ElementType getFromSeqList(SeqList* l, int i) {
       if (i >= l->size) {
           printf("Index out of bound!\n");
           return 0;
       }
       return l->arr[i];
   }

7. 插入
   除上文所说在指定位置插入外，还可以实现在表尾插入的功能
   在插入时，如当前线性表大小已经和容量一样大，则需要进行扩容

   1. 扩容

      void expandSeqList(SeqList* l) {
          printf("Expansion\n");
          ElementType* newArr =
              (ElementType*)realloc(l->arr, sizeof(ElementType) * 2 * l->capacity);
          if (!(newArr)) {
              printf("Expansion failed!\n");
              exit(-1);
          }
          l->capacity *= 2;
          l->arr = newArr;
      }

   2. 在末尾插入

      void insertBack2SeqList(SeqList* l, ElementType x) {
          if (l->size == l->capacity) {
              expandSeqList(l);
          }
          l->arr[l->size] = x;
          l->size += 1;
      }

   3. 指定位置插入

      void insert2SeqList(SeqList* l, int i, ElementType x) {
          if (l->size == l->capacity) {
              expandSeqList(l);
          }
          for (size_t n = l->size; n > i; --n) {
              l->arr[n] = l->arr[n - 1];
          }
          l->arr[i] = x;
          l->size += 1;
      }

8. 删除元素

   void removeFromSeqList(SeqList* l, int i) {
       if (i >= l->size)
           printf("Index out of bound!\n");
       for (size_t n = i; n < l->size - 1; ++n) {
           l->arr[n] = l->arr[n + 1];
       }
       l->size -= 1;
   }

9. 查找元素

   int indexOfSeqList(SeqList* l, ElementType x) {
       for (int n = 0; n < l->size; ++n)
           if (l->arr[n] == x)
               return n;
       return -1;
   }

10. 打印链表

    void printSeqList(SeqList* l) {
        printf("cap: %zu  size: %zu ==>", l->capacity,  l->size);
        for (size_t i = 0; i < l->size; ++i) {
            printf(" [%zu]=%d", i, l->arr[i]);
        }
        printf("\n");
    }

11. 额外功能：“反”扩容（？
    当 size < capacity/4 的时候，可以缩小数组，减小对内存的占用

    void curtailSeqList(SeqList* l) {
        printf("Curtailment\n");
        ElementType* newArr =
            (ElementType*)realloc(l->arr, sizeof(ElementType) * l->capacity / 2);
        if (!(newArr)) {
            printf("Curtailment failed!\n");
            exit(-1);
        }
        l->capacity /= 2;
        l->arr = newArr;
    }

    在 removeFromSeqList 中添加如下代码：

    if ((l->size + 1) * 4 < l->capacity)
        curtailSeqList(l);

3. 链表 (Linked List)

3.1 基本概念

1. 顺序存储的不足 上一节中，我们实现了一个简易的顺序表
   但是某些操作很麻烦，比如 删除 元素和 插入 元素，需要将后面所有元素左移或右移

3.2 实现

3.2.1 单链表 示例代码

1. 创建结构体

3.2.2 双链表

3.2.3 循环链表

3.3 顺序表和链表的对比

1. 占用空间
2. 随机访问
3. 插入/删除操作

4. 栈 (Stack)

4.1 基本概念

1. 栈是一种 只允许在表尾进行插入和删除操作 的线性表
2. 上一条的“表尾”（即允许进行插入和进行删除操作的一端）一般称作 栈顶
3. 另一端称作 栈底
4. 在栈顶位置插入元素的操作叫做 压栈（入栈，进栈）
5. 删除栈顶元素的操作叫做 出栈（弹栈，退栈）
6. 可以用数组和链表实现栈

4.2 实现

4.2.1 用数组实现

4.2.2 用链表实现

5. 队列 (Queue)