第2章数据结构及应用.ppt

1、第2章数据结构及应用概念及顺序表,西安交通大学计教中心 ,第2/42页,思考问题,数据结构要研究什么问题？ 什么是线性数据结构和线性表？ 如何描述线性表？ 线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？ 如何处理线性数据结构中的数据？ ,第3/42页,数据结构问题的由来,计算机求解问题的过程步骤：,求解 结果,用户 需求,第4/42页,数据结构,数据结构是计算机的专业技术基础课。它研究的主要问题有： 分析数据（计算机加工的对象）的特征 选择适当逻辑存储结构和物理存储结构 在存储结构的基础上实现对数据的操作,第5/42页,2.1 数据结构基本概念,1数据（data） 数据是指能够输

2、入到计算机中，并被计算机识别和处理的符号的集合。 2数据元素（data element） 数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位,第6/42页,数据结构（data structure） 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。,第7/42页,数据的逻辑结构,它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述： DS=（D，R）

3、其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。,与数据在计算机中的存放的 物理位置无关,第8/42页,举例,课题组由1名教师、13名研究生、16名本科生组成；成员关系是：教师指导研究生、研究生指导12名本科生。 定义DS如下： Group=（D，R） 其中：,D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2,R=R1,R2 R1=|1 i n , 1 n 3 R2=|1in ,1 j m , 1 n 3 , 1 m 2 ,第9/42页,数据的存储结构,又称物理结构 是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放。,数据库中的数据存放在计算机

4、中的物理位置,第10/42页,逻辑结构和存储结构的关系,数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。 数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。,第11/42页,数据存储结构分类,顺序存储结构 链式存储结构 索引存储结构 散列存储结构,第12/42页,顺序存储结构,把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构:,d1 d2 dn,数据域,特点: 连续存放;逻辑上相

5、邻,物理上也相邻。 结构简单，易实现。 插入、删除操作不便（需大量移动元素）。,第13/42页,链式存储结构,以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:,d1,.,d2,dn ,数据域 指针域,特点: 非连续存放,借助指针来表示元素间的关系; 插入、删除操作简单，只要修改指针即可； 结构较复杂，需要额外存储空间。,第14/42页,索引存储结构,数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。 数据结点结构:,12 21 35 2 45 5 10,4 3 2 7

6、1 6 5,特点： 非连续存放； 检索速度快； 增、删操作简单。,序 号： 1 2 3 4 5 6 7,数据项： 索引号：,第15/42页,散列存储结构,在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。 哈希查找中的哈希表就是这样一种存储结构。 特点： 数据元素间无内在联系； 存储形式不定。,第16/42页,数据运算,数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。 常见操作有： 输入、检索、插入、删除、修改、排序等。,第17/42页,数据结构分类,第18/42页,数据结构基本类型,线性结构 通迅录、成绩单、

7、花名册 树形结构 电子字典、家谱、目录 图状结构 交通线路、通信网络,第19/42页,算法（algorithm）,通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）： 输入：具有0个或多个输入的外界量（算法开始前的初始量） 输出：至少有一个输出，是算法执行完后的结果。 有穷性：每条指令的执行次数必须是有限的。 确定性：每条指令的含义都必须明确，无二义性。 可行性：每条指令的执行时间都是有限的。,第20/42页,1时间复杂度 一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。 数据结构

8、中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。 例如： for(i=1; i=n; i+) for(j =1; j=i; j+) dij=dataij+1;,算法分析,第21/42页,算法的评价,算法评价的标准： 时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1） O（logn） O（ n ） O（ n2 ） 常数阶 对数阶 线性阶 平方阶 空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。,第22/42页,时间复杂度举例,（a）

9、 X：=X+1 ；,（b） FOR I：=1 TO n DO X：= X+1；,（c） FOR I：= 1 TO n DO FOR J：= 1 TO n DO X：= X+1；,O（ 1 ）,O（ n ）,O（ n2 ）,第23/42页,2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。,第24/42页,2.2 线性数据结构,线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和

10、一个直接后继ai+1。 a1无前趋，an无后继。 例如，一星期七天的英文缩写表示： （Sun，Mon，The，wed，Thu，Fri，Sat） 是一个线性表，其中的元素是字符串，表的长度为7。,第25/42页,线性表的逻辑结构,定义： 线性表是n（n0）个元素a1,a2,an 的有限序列；表中每个数据元素，除了第1个和最后1个外，有且仅有一个前趋元素和后继元素。 形式定义： 含有n个数据元素的线性表是一种数据结构，表示为： Linear_list=( D , R ) 其中: D=ai | aiD0,i=1,2,3,n,n 0 R=N, N=|ai-1,ai D0 ,i=1,n D是数据元素的有

11、限集合，R是D上逻辑关系的有限集合。关系N是一个有序偶对的集合。,第26/42页,顺序表,采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。 假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为： Loc(ai) = Loc(a1) + (i-1) * d,第27/42页,线性表元素存储示意图,a1,a2,.,ai,.,元素序号 内存状态 存储地址,1,2,.,i,.,LOC(a1),LOC(a1)+1,.,LOC(a1)+(i-1),.,第28/42页,顺序表类型描述,s

12、truct SeqList ElemType *data; / 顺序表存储数组的地址 int maxsize; / 顺序表最大允许长度 int length; / 顺序表当前长度 ； SeqList list;/ 定义一个线性表list （1）ElemType代表数组的类型。 （2）数组data需要在初始化函数中利用new操作动态申请，maxsize为其长度。数组的下标从0开始。 （3）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。,第29/42页,线性表的基本操作,Setnull（L） 置空表 Length（L） 求表长度；求表中元素个数 Get（L，i）

13、取表中第i个元素（1i n） Prior（L，i） 取i的前趋元素 Next（L，i） 取i的后继元素 Locate（L，x） 返回指定元素在表中的位置 Insert（L，i，x） 插入元素 Delete（L，x） 删除元素 Empty（L） 判别表是否为空,第30/42页,顺序表的主要算法,（1）顺序表的初始化 顺序表的初始化主要是为ElemType类型的数组申请空间，下面的初始化函数为顺序表申请了长度为size的空间。 void Init( SeqList *L, int size ) if( size 0 ) L-maxsize = size; L-length = 0; L-data

14、= new ElemTypesize; /申请空间 else cout线性表初始化长度错误; ,第31/42页,（2）在表中第 i 个位置插入新元素x 算法实现的主要步骤： 判断插入位置的合理性以及表是否已满。 从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第i个元素为止。 向空出的第i个位置存入新元素x。 最后还要将线性表长度加一。,示例,第32/42页,第33/42页,插入算法示意举例,设有数列4,5,8,10,21,30,43,59，长度为8，在“21”和“30”之间插入元素“25”。 算法描述： 从数列右边开始，即从第8个元素开始； 为在第5个元素“21”后插入“25”，

15、则要把其后的3个元素右移，移动元素个数是3（8-5）； for( int j=L-length-1; j=i-1; j- ) / length 是元素个数(8) L-dataj+1=L-dataj; / j是插入位置(5) 将空出的第6个位置，存放“25”。 L-datai-1 = x; / 将x存放在第i-1 位置 表长度加“1” L-length+; / 加“1”后，结果为“9” 最后，得到的结果数列是4,5,8,10,21,25,30,43,59,第34/42页,void Insert( SeqList *L, int i, ElemType x ) if( iL-length+1 |

16、L-length=L-maxsize ) coutlength-1; j=i-1; j- ) L-dataj+1 = L-dataj; /元素依次右移 L-datai-1 = x; / 向第 i 个位置存入新元素 x L-length+; / 表长度加一 ,顺序表插入算法,第35/42页,（3）在表中删除第i个元素 算法实现的主要步骤是： 判断删除位置的合理性。 从第i+1个元素开始，依次向后直到最后一个元素为止，将每个元素向前移动一个位置。这时第i个元素已经被覆盖删除。 最后还要将线性表长度减一。,第36/42页,第37/42页,删除算法示意举例,设有数列4,5,8,10,21,25,30,

17、43,59，长度为9，将第6位的元素“25”删除。 算法描述： 从第7个元素开始(i+1)； 将第7个元素“30”存入第6位，将“25”覆盖，即元素左移，移动元素个数是3（9-6）； for ( int j=i; jlength-1; j+ ) / length是元素个数(9) L-dataj-1 = L-dataj; / i是删除位置(6) 长度减“1” L-length-； / 操作后，length 等于8 最后，得到的结果数列是4,5,8,10,21,30,43,59,第38/42页,void Delete( SeqList *L, int i ) if(iL-length ) cout

18、length-1; j+ ) L-dataj-1 = L-dataj; /数据元素左移 L-length-; ,顺序表删除算法,第39/42页,（4）在表中查找某个元素 下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，算法返回元素的实际位置。查找算法: int Find( SeqList *L, ElemType x ) for( int i = 0; ilength; i+ ) /查找成功, 返回元素位置 if( L-datai=x ) return i+1; return 0; /查找失败, 返回 0 ,第40/42页,顺序表应用举例,【例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)的结果是: L3(x)= 3.5 + 1.5x + 6.6x2 + 1.6x3 + 2.5x4 一元多项式P(x)可表示为(a0, 0), (a1, 1), , (an, n)。 例如线性