资源预览内容
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
第9页 / 共22页
第10页 / 共22页
亲,该文档总共22页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构概念及顺序表,西安交通大学计教中心 ,2.1 数据结构基本概念,1数据(data) 数据是指能够输入到计算机中,并被计算机识别和处理的符号的集合。 2数据元素(data element) 数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项(字段),故不是组成数据的最小单位,数据结构(data structure) 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容,即数据的逻辑结构,数据的存贮结构和对数据所施加的运算。 这三个方面的关系为: 数据的逻辑结构独立于计算机,是数据本身所固有的 存贮结构是逻辑结构在计算机存贮器中的映像,必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构,但运算的实现必依赖于存贮结构。,数据结构基本类型,线性结构 通迅录、成绩单、花名册 树形结构 电子字典、家谱、目录 图状结构 交通线路、通信网络,数据结构中常用的存贮结构,(1) 顺序存贮 所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内存仍然相邻。 (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+) dij=dataij+1;,算法分析,2 空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。,2.2 线性数据结构,线性表是由有限个同类型的数据元素组成的有序序列,一般记作(a1,a2,an)。除了a1和an之外,任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。 a1无前趋,an无后继。 线性表的存储结构主要有顺序存储结构和链式存储结构两种。,顺序表,采用顺序存储结构的线性表称为顺序表,它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素,其存储位置也彼此相邻。 假定元素a1的物理地址是Loc(a1),每个元素占d个存储单元,则第i个元素的存储位置为: Loc(ai) = Loc(a1) + (i-1) * d,顺序表类描述,const int MAXSIZE=100; /顺序表最大允许长度 class SeqList public: ElemType dataMAXSIZE; / 存储数据的数组 int length; / 顺序表当前长度 SeqList() length=0; /构造函数 void ClearList() length=0; /将顺序表置为空表 /判断顺序表是否为空表 bool IsListEmpty() return length=0; ( 下页continue . ),( 接上页 ) /判断顺序表是否为满 bool IsListFull() return length=MAXSIZE; /在表中删除第i个元素 void ListDelete( int i ); /在表中第 i 个位置插入新元素x void ListInsert( int i, ElemType x ); int Find( ElemType x ); /在表中查找元素 ; (1)ElemType代表数组的某种类型。 (2)length表示线性表当前长度,初始长度为0(空表),最大不超过maxsize。,顺序表的主要算法,(1)在表中第 i 个位置插入新元素x 算法实现的主要步骤是: 判断插入位置的合理性以及表是否已满。 从最后一个元素开始依次向前,将每个元素向后移动一个位置,直到第i个元素为止。 向空出的第i个位置存入新元素x。 最后还要将线性表长度加一。,void SeqList:ListInsert( int i, ElemType x ) if( ilength+1 | length=MAXSIZE ) cout=i-1;j- ) dataj+1 = dataj; / 元素依次向后移动 datai-1 = x;/ 向第i个位置存入新元素 length+; / 表长度加1 ,(2)在表中删除第i个元素 算法实现的主要步骤是: 判断删除位置的合理性。 从第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:Find(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, 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,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号