• 顺序表
    • 数组
  • 链表
    • 单链表
    • 双链表
    • 循环链表

      线性表

      线性表（List）：全名为线性存储结构，由零个或多个数据元素组成的有限序列。

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。另外链表、队列、栈等也是线性表结构。

image.png

而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性 表中，数据之间并不是简单的前后关系。
image.png

线性表的特征：

  • 序列：元素间有顺序
  • 有限：元素个数有限

线性表元素的个数 n（n>0）定义为线性表的长度，当 n=0 时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如 a 是第一个数据元素， a 是最后一个数据元素，a 是第 i个数据元素，称 i 为数据元素 a 在线性表中的位序。

前驱和后继

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。

  • 公司组织架构
  • 班级同学关系
  • 情侣爱情关系
  • 班级点名册
  • 星座列表

抽象数据类型

抽象：抽取事物具有的普遍性的本质。

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。

  • ADT 线性表
  • Data
  • Operation
    • InitList(*L)：初始化操作。建立一个空的线性表
    • ListEmpty(L)：若线性表为空，返回 true，否则返回 false
    • ClearList(*L)：将线性表清空
    • GetElem(L, i, *e)：将线性表 L 中的第 i 个位置元素值返回给 e
    • LocateElem(L, e)：在线性表 L 中查找与给定值 e 相等的元素，如果查找成功，返回该元素在表中序号，表示成功；否则，返回 0，表示失败。
    • ListInsert(*L, i, e)：在线性表 L 中第 i 个位置插入新元素 e
    • ListDelete（L, i, e）：删除线性表 L 中第 i 个位置元素，并用 e 返回其值
    • ListLength（L）：返回线性表 L 的元素个数
  1. void union(List *La, list Lb)
  2. {
  3.     int La_len, Lb_len, i;
  5.     ElemType e;
  6.     La_len = ListLength(*La);
  7.     La_len = ListLength(Lb);
  9.     for(i = 1; i <= Lb_len; i++)
  10.     {
  11.         GetElem(Lb, i, &e);
  12.         if( !LocateElem(*La, e) )
  13.         {
  14.             ListInsert(La, ++La_len, e);
  15.         }
  16.     }
  17. }