数据结构与算法 - 线性表

数据类型

    一组性质相同的值的集合及定义在此集合上的一些操作的总称。如很多编程语言中的整型，浮点型之类

抽象数据类型

    是指一个数据模型，及定义在该模型上的一组操作，不仅仅指那些已经定义并实现的数据类型，也可以是编程人员自己设计软件程序时定义的数据类型。他的定义只取决于他的逻辑特性，而与其在计算机类如何表示实现无关。

线性表

    list:由零个或多个数据元素组成的有限序列，第一个元素无前驱，最后一个元素无后继，无限的概念只存在数学的理论中。

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

   ADT   线性表(List)

   DATA

      线性表的数据集合为｛a1,a2,a3...,an｝，每个元素类型均为DataType，其中，除第一元素a1，每个元素有且只有一个直接前驱元素，除最后一个元素an，每个元素有且只有一个直接后继元素，数据元素之间的关系是一对一关系。

  Operation

      initList();初始化操作，建立一个空的，指定长度的线性表。

      listEmpty();判断线性表是否为空，是返回true，否返回false

      clearList();清空线性表

      getElem(index);将线性表中第index个元素返回，这里是从下标是从1开始，抽象给人看，具体实现时从0开始。

      listInsert(i,e);在线性表中第i个位置，插入元素e

      listDelete(i);删除对应位置的元素

      listLength();返回线性表元素个数

   ENDADT

    对不同的应用，线性表的操作是不一样的，上述是最基本的操作，对于实际问题中复杂的操作，可以用上述操作的组合来实现。

线性表存储结构

 线性表有两种存储结构，顺序存储和链式存储！