西安交通大学计教中心 ctec.xjtu.edu.cn 数据结构概念及顺序表 西安交通大学计教中心 ctec.xjtu.edu.cn

2.1 数据结构基本概念 1．数据（data） 2．数据元素（data element） 2.1 数据结构基本概念 1．数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。 2．数据元素（data element） 数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位

数据结构（data structure） 数据的逻辑结构独立于计算机，是数据本身所固有的 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。 这三个方面的关系为： 数据的逻辑结构独立于计算机，是数据本身所固有的 存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。

数据结构基本类型 线性结构 —— 通迅录、成绩单、花名册 树形结构 —— 电子字典、家谱、目录 图状结构 —— 交通线路、通信网络

数据结构中常用的存贮结构 (1) 顺序存贮 (2) 链式存贮 (3) 索引存贮（略） (4) 散列存贮（略） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存贮 所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。 (3) 索引存贮（略） (4) 散列存贮（略）

算法（algorithm） 通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）： （1）输入：具有0个或多个输入的外界量（算法开始前的初始量） （2）输出：至少产生一个输出，它们是算法执行完后的结果。 （3）有穷性：每条指令的执行次数必须是有限的。 （4）确定性：每条指令的含义都必须明确，无二义性。 （5）可行性：每条指令的执行时间都是有限的。

算法分析 1． 时间复杂度 一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。 数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。 例如： for(i=1; i<=n; i++) for(j =1; j<=i; j++) d[i][j]=data[i][j]+1; O(n2)

2． 空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。

2.2 线性数据结构 线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。 a1无前趋，an无后继。 线性表的存储结构主要有顺序存储结构和链式存储结构两种。

Loc(ai) = Loc(a1) + (i-1) * d 顺序表 采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。 假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为： Loc(ai) = Loc(a1) + (i-1) * d length=n maxsize 0 1 i-2 i-1 i n-1 a2 … ai-1 ai ai+1 a1 an

顺序表类型描述 struct SeqList { ElemType *data; // 顺序表存储数组的地址 int maxsize; // 顺序表最大允许长度 int length; // 顺序表当前长度 }； SeqList list; // 定义一个线性表list （1）ElemType代表数组的类型。 （2）数组data需要在初始化函数中利用new操作动态申请，maxsize为其长度。数组的下标从0开始。 （3）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。

顺序表的主要算法 （1）顺序表的初始化 顺序表的初始化主要是为ElemType类型的数组申请空间，下面的初始化函数为顺序表申请了长度为size的空间。 void Init( SeqList *L, int size ) { if( size > 0 ) L->maxsize = size; L->length = 0; L->data = new ElemType[size]; //申请空间 } else cout<<"线性表初始化长度错误";

（2）在表中第 i 个位置插入新元素x 算法实现的主要步骤是： ① 判断插入位置的合理性以及表是否已满。 ② 从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第i个元素为止。 ③ 向空出的第i个位置存入新元素x。 ④ 最后还要将线性表长度加一。

void Insert( SeqList *L, int i, ElemType x ) { if( i<1 || i>L->length+1 || L->length==L->maxsize ) cout<<"插入位置错误或表满"; else { for( int j=L->length-1; j>=i-1; j-- ) L->data[j+1] = L->data[j]; //元素依次后移 L->data[i-1] = x; // 向第 i 个位置存入新元素 x L->length++; // 表长度加一 }

（3）在表中删除第i个元素 算法实现的主要步骤是： ① 判断删除位置的合理性。 ② 从第i+1个元素开始，依次向后直到最后一个元素为止，将每个元素向前移动一个位置。这时第i个元素已经被覆盖删除。 ③ 最后还要将线性表长度减一。

void Delete( SeqList *L, int i ) { if(i<1 || i>L->length ) cout<<"表中没有第"<<i<<"个元素"; else { for ( int j=i; j<=L->length-1; j++ ) L->data[j-1] = L->data[j]; L->length--; }

下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，算法返回元素的实际位置。 （4）在表中查找某个元素 下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，算法返回元素的实际位置。 int Find( SeqList *L, ElemType x ) { for( int i = 0; i<L->length; i++ ) { //查找成功，返回元素位置 if( L->data[i]==x ) return i+1; } return 0; //查找失败，返回 0

顺序表应用举例 【例2-1】利用顺序表表示多项式，实现两个一元多项式L1(x)和L2(x)相加，将结果存于多项式L3(x)中。并计算当L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3时，L3(x)的结果是什么。 一元多项式P(x)可以表示为((a0, 0), (a1, 1), … , (a n, n))。例如线性表((6, 1), (-5, 4), (8, 10))表示多项式: P(x) = 6x - 5x4 + 8x10。

用顺序表L1和L2存放需要相加的两个多项式L1(x)和L2(x)，用顺序表L3来存放结果。多项式相加算法可按照下列步骤实现： ① 设定两个位置变量i和j指向顺序表L1和L2的第一个元素，设定位置变量k表示L3的插入位置，插入位置从1开始。本例中i、j和k初值均为1。 ② 比较i和j两个位置数据元素的指数项，如果L1中第i项指数较小，则将此项数据元素复制到L3的位置k中，并将位置变量i和k后移；如果L2中第j项指数较小，则同样是将此项复制到L3中，并将位置变量j和k后移；如果两项指数项相等，则合并同类项后再将结果复制到L3中，并将位置变量i、j和k同时后移。 ③ 当L1或L2中的一个顺序表已经处理完毕，则将另一个顺序表的剩余部分复制到L3中。

参照程序[例2-1]