1、抽象数据类型

1.1 相关定义

  • 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
  • 例如：整型、浮点型、字符型这些指的就是数据类型。

例如在C语言中，按照取值的不同，数据类型可以分为两类：

  • 原子类型：不可以再分解的基本类型，例如：整形、浮点型、字符型等。
  • 结构类型：由若干个类型组合而成，可以再分解，例如整型数组是由若干个整型数据组成的。

1.2 抽象数据类型

  • 抽象：是指抽出事物具有的普遍性的本质；
  • 抽象数据类型类型(Abstract Data Type，ADT)：是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。例如我们定义一个坐标point由x、y、z三个整型数据组合，那么point就是一个抽象数据类型。

1.3 抽象数据类型标准格式

  1. ADT 抽象数据类型名
  2. Data
  3.     数据元素之间逻辑关系的定义
  4. Opreration
  5.     操作
  6. endADT

2、线性表

1.1 线性表定义

  • 线性表：由零个或多个数据元素组成的有限序列。

    • 首先，它是一个序列，元素之间是有顺序的，元素之间有一个先来后到。
    • 若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。
    • 另外，线性表强调是有限的，事实上无论计算机发展到多强大，它所处理的数据都是有限的。

  • 数学语言定义线性表

    • 若将线性表记为（a,…a,a,a,…a），则a是a的前驱元素，a是a的后继元素；
    • 线性表的元素个数为n(n>=0)，定义为线性表的长度；
    • 当n=0时，称为空表；

1.2 线性表抽象数据类型的定义

  1. ADT 线性表(List)
  2. Data
  3.     数据对象集合和为{a1, a2,...,an}
  4.     数据类型为：DataType
  5.     当线性表有多个元素时，第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继
  7. Operation
  8.         InitList(*L)：初始化，建立一个空的线性表L
  9.     ListEmpty(L)：判断线性表L是否为空表
  10.     ListLength(L)：返回线性表L的长度
  11.     GetElem(L, i, *e)：获取线性表L中第i个位置的元素值并返回
  12.     LocateElem(L, e)：在线性表L中查找给定值e，如果查找成功则返回该元素在表中的序号(索引)，否则返回0表示失败
  13.     ListInsert(*L, i, e)：在线性表L中第i个位置，插入新元素e
  14.     ListDelete(*L, i, *e)：删除线性表L中的第i个位置的元素，并用e返回
  15.     ListClear(*L)：清空线性表L
  16. endADT

**
原文链接：https://blog.csdn.net/weruse/article/details/104592352