1、数据结构概念及顺序表数据结构概念及顺序表西安交通大学计教中心2.1 数据结构基本概念1数据（ data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合 。 2数据元素（ data element）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位数据结构（ data structure）是指相互之间存在一种或多种特定关系的是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结面的内容，即数
2、据的逻辑结构，数据的存贮结构和对数据所施加的运算构和对数据所施加的运算 。这三个方面的关系为 ： 数据的逻辑结构独立于计算机，是数据本身所固有的 存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。数据结构基本类型 线性结构 通迅录、成绩单、花名册 树形结构 电子字典、家谱、目录 图状结构 交通线路 、 通信网络数据结构中常用的存贮结构(1) 顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2) 链式存贮所有元素存放在可以不连续的存贮单元中，元素之间的关系
3、通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3) 索引存贮（略） (4) 散列存贮（略）算法（ algorithm）通俗地讲，算法就是一种解题的方法。更严格地说，通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：条件（也称为算法的五大特性）：（ 1）输入： 具有 0个或多个输入的外界量（算法开始前的初始量）（ 2）输出： 至少产生一个输出，它们是算法执行完后的结果。（ 3）有穷性： 每条指令的执行次数必须是有限的。（ 4）确定性： 每条指令的含义都必须
4、明确，无二义性。（ 5）可行性： 每条指令的执行时间都是有限的。1 时间复杂度一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。数据结构中数据元素个数 n称为问题的规模，当 n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。例如： for(i=1; i=n; i+) for(j =1; j=i; j+)dij=dataij+1;算法分析O(n2)2 空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度
5、类似，不再赘述。2.2 线性数据结构 线性表是由有限个同类型的数据元素组线性表是由有限个同类型的数据元素组成的有序序列，一般记作（成的有序序列，一般记作（ a1,a2,a n）。）。除了除了 a1和和 an之外，任意元素之外，任意元素 ai都有一个直接都有一个直接前趋前趋 ai-1和一个直接后继和一个直接后继 ai+1。 a1无前趋，无前趋， an无后继。无后继。线性表的存储结构主要有顺序存储结构和链式存储结构两种。 顺序表 采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素 a1的物理地址是 Loc(a1)， 每个元素占 d个存储单元，则第 i个元素的存储位置为 ：Loc(ai) = Loc(a1) + (i-1) * d length=n maxsize0 1 i-2 i-1 i n-1 a2 ai-1 ai ai+1a1 an
