《数据结构概念及顺序表》由会员分享，可在线阅读，更多相关《数据结构概念及顺序表（22页珍藏版）》请在金锄头文库上搜索。
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; ilength+1 | length=MAXSIZE )cout=i-1;j- ) dataj+1 = dataj; / 元素依次向后移动 datai-1 = x;/ 向第i个位置存入新元素 length+; / 表长度加1 （2）在表中删除第i个元素 算法实现
5、的主要步骤是： 判断删除位置的合理性。 从第i+1个元素开始，依次向后 直到最后一个元素为止，将每个元 素向前移动一个位置。这时第i个元 素已经被覆盖删除。 最后还要将线性表长度减一。void SeqList:Delete( int i ) if(iL-length ) cout“表中没有第“i“个元素“;else for ( int j=i; j=length-1; j+ ) dataj-1 = dataj; /元素依次向前移动 length-; （3）在表中查找某个元素 下面是根据数据元素本身的值进行查询的 算法，x为需要查找的元素，算法返回元素的 实际位置。 int SeqList:Fi
6、nd(ElemType x ) for( int i = 0; ilength; i+ ) /查找成功，返回元素位置 if( datai=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,
7、 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
