第2章数据结构及应用概念及顺序表ppt课件

1、下一页上一页停止放映西安交通大学计教中心西安交通大学计教中心下一页上一页停止放映思索问题 数据构造要研讨什么问题？ 什么是线性数据构造和线性表？ 如何描画线性表？ 线性表在计算机中如何存放？有几种存储方式？它们的特点是什么？ 如何处置线性数据构造中的数据？ 下一页上一页停止放映数据构造问题的由来计算机求解问题的过程步骤： 调试程序调试程序编制编制程序程序求解求解结果结果运转运转程序程序结果输出结果输出用户用户需求需求数据类型、格式、数据类型、格式、逻辑构造逻辑构造数据数据逻辑逻辑运算运算数据的物理数据的物理操作操作分析笼统分析笼统实践实践问题

2、问题模型求解模型求解问题问题模型模型命令命令编程编程求解求解算法算法下一页上一页停止放映数据构造 数据构造是计算机的专业技术根底课。它研讨的主要问题有： 分析数据计算机加工的对象的特征 选择适当逻辑存储构造和物理存储构造 在存储构造的根底上实现对数据的操作下一页上一页停止放映2.1 数据构造根本概念1数据数据data数据是指可以输入到计算机中，并被计算数据是指可以输入到计算机中，并被计算机识别和处置的符号的集合。机识别和处置的符号的集合。 2数据元素数据元素data element数据元素是组成数据的根本单位。数据元数据元素是组成数据的根本单位。数据元素是一个数据整体中相对独立的单位。但它还素

3、是一个数据整体中相对独立的单位。但它还可以分割成假设干个具有不同属性的项字可以分割成假设干个具有不同属性的项字段，故不是组成数据的最小单位段，故不是组成数据的最小单位下一页上一页停止放映数据构造data structure是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据构造包含三个方面的内容，即数据的逻辑构造，数据的存贮构造和对数据所施加的运算。下一页上一页停止放映数据的逻辑构造 它是描画数据间的顺序逻辑关系，只是笼统地反映数据元素的构造，而不论它们在计算机中如何存放。普通用以下二元组来描画： DS=D，R 其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。与数据

4、在计算机中的存放的物理位置无关下一页上一页停止放映举例 课题组由课题组由1 1名教师、名教师、1313名研讨生、名研讨生、1616名本名本科生组成；成员关系是：教师指点研讨生、科生组成；成员关系是：教师指点研讨生、研讨生指点研讨生指点1212名本科生。名本科生。 定义定义DSDS如下：如下： Group=Group=D D，R R 其中：其中： D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2R=R1,R2R1=|1 i n , 1 n 3R2=|1in ,1 j m , 1 n 3 , 1 m 2 下一页上一页停止放映数据的存储构造 又称物理构造又称物理构造 是指数据构造在计

5、算机中的表示是指数据构造在计算机中的表示( (又称映象又称映象),),即数据在计算机中即数据在计算机中的存放。的存放。数据库中的数据存放在计算机中的物理位置下一页上一页停止放映逻辑构造和存储构造的关系v数据的逻辑构造是从逻辑关系某种顺序上察数据的逻辑构造是从逻辑关系某种顺序上察看数据，它是独立于计算机的；可以在实际上、看数据，它是独立于计算机的；可以在实际上、方式上进展研讨、推理、运算等各种操作。方式上进展研讨、推理、运算等各种操作。v数据的存储构造是逻辑构造在计算机中的实现，数据的存储构造是逻辑构造在计算机中的实现，是依赖于计算机的；分开了机器，那么无法进展是依赖于计算机的；分开了机器，那么

6、无法进展任何操作。任何操作。v任何一个算法的设计取决于选定的逻辑构造；而任何一个算法的设计取决于选定的逻辑构造；而算法的最终实现依赖于采用的存储构造。算法的最终实现依赖于采用的存储构造。下一页上一页停止放映数据存储构造分类顺序存储构造链式存储构造索引存储构造散列存储构造 下一页上一页停止放映顺序存储构造 把数据元素按某种顺序存放在一块延续的存储单元中的存储方式。数据结点构造: d1 d2 dn数据域数据域特点特点: 延续存放延续存放;逻辑上相邻逻辑上相邻,物理上也相邻。物理上也相邻。 构造简单，易实现。构造简单，易实现。 插入、删除操作不便需大量挪动元素。插入、删除操作不便需大量挪动元素。下一

7、页上一页停止放映链式存储构造 以链表方式将数据元素存放于恣意存储单元中，可延续存放，也可以不延续存放，以指针实现链表间的联络。数据结点构造: d1. d2dn 数据域数据域 指针域指针域特点特点:非延续存放非延续存放,借助指针来表示元素间的关系借助指针来表示元素间的关系;插入、删除操作简单，只需修正指针即可；插入、删除操作简单，只需修正指针即可；构造较复杂，需求额外存储空间。构造较复杂，需求额外存储空间。下一页上一页停止放映索引存储构造 数据按索引方式存放。存储时分为：数据项和索引号；经过索引表记录逻辑号记录号和物理号存储序号之间的对应关系。 数据结点构造:12 21 35 2 45 5 10

8、 4 3 2 7 1 6 5 数据域数据域 索引顺序号索引顺序号特点：特点：非延续存放；非延续存放；检索速度快；检索速度快；增、删操作简单。增、删操作简单。 序 号： 1 2 3 4 5 6 7 数据项：索引号：下一页上一页停止放映散列存储构造 在数据元素与存储位置之间建立一种在数据元素与存储位置之间建立一种存储关系存储关系F F，根据这种关系，根据这种关系F F，知元素，知元素E E，就可以得到它的存储地址，即就可以得到它的存储地址，即D=FD=FE E。 哈希查找中的哈希表就是这样一种存哈希查找中的哈希表就是这样一种存储构造。储构造。 特点：特点： 数据元素间无内在联络；数据元素间无内在联

9、络； 存储方式不定。存储方式不定。下一页上一页停止放映数据运算数据运算是指对存放在物理构造上的数据,按定义的逻辑构造进展的各种操作。 常见操作有：输入、检索、插入、删除、修正、排序等。下一页上一页停止放映数据构造分类 线性表线性表堆栈堆栈队列队列串串数组数组树树二叉树二叉树图图线性构造线性构造非线性构造非线性构造数据构造数据构造DSDS下一页上一页停止放映数据构造根本类型 线性构造线性构造 通迅录、成果单、花名册通迅录、成果单、花名册 树形构造树形构造 电子字典、家谱、目录电子字典、家谱、目录 图状构造图状构造 交通线路、通讯网络交通线路、通讯网络下一页上一页停止放映算法algorithm 通

10、俗地讲，算法就是一种解题的方法。更严厉地说，算法是由假设干条指令组成的有穷序列，它必需满足下述条件也称为算法的五大特性：输入：具有0个或多个输入的外界量算法开场前的初始量输出：至少有一个输出，是算法执行完后的结果。有穷性：每条指令的执行次数必需是有限的。确定性：每条指令的含义都必需明确，无二义性。可行性：每条指令的执行时间都是有限的。下一页上一页停止放映1 1时间复杂度时间复杂度 一个算法破费的时间与算法中语句的一个算法破费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次执行次数成正比，哪个算法中语句执行次数 多 ， 它 破 费 时 间 就 多 。数 多 ， 它 破 费 时 间 就 多

11、 。 数据构造中数据元素个数数据构造中数据元素个数n n称为问题称为问题的规模，当的规模，当n n不断变化时，语句的执行次不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度普数也会变化。一个算法中的时间复杂度普通用语句执行次数的数量级来衡量。通用语句执行次数的数量级来衡量。例如：例如： for(i=1; i=n; i+) for(i=1; i=n; i+) for(j =1; j=i; for(j =1; j=i; j+)j+) dij=dataij+1;dij=dataij+1;算法分析O(n2)下一页上一页停止放映算法的评价算法评价的规范：算法评价的规范：时间复杂度时间复杂度 指在

12、计算机上运转该算法所破费的时间。用指在计算机上运转该算法所破费的时间。用“O O数量级来表示，称为数量级来表示，称为“阶。常见的阶。常见的时间复杂度有：时间复杂度有： O O1 1 O Olognlogn O O n n O O n2 n2 常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶空间复杂度空间复杂度 指算法在计算机上运转所占用的存储空间。指算法在计算机上运转所占用的存储空间。度量同时间复杂度。度量同时间复杂度。 下一页上一页停止放映时间复杂度举例a a X X：=X+1 =X+1 ；b b FOR I FOR I：=1 TO n DO =1 TO n DO X X：= X+1=

13、 X+1；c c FOR I FOR I：= 1 TO n DO= 1 TO n DO FOR J FOR J：= 1 TO n DO= 1 TO n DO X X：= X+1= X+1；O O 1 1 O O n n O O n2 n2 下一页上一页停止放映2 2、空间复杂度、空间复杂度与时间复杂度类似，空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用是指算法在计算机内执行时所占用的内存开销规模。但我们普通所讨的内存开销规模。但我们普通所讨论的是除正常占用内存开销外的辅论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间助存储单元规模。讨论方法与时间复杂度类似，不

14、再赘述。复杂度类似，不再赘述。下一页上一页停止放映2.2 线性数据构造 下一页上一页停止放映线性表的逻辑构造定义：定义： 线性表是线性表是n nn n0 0个元素个元素a1,a2,an a1,a2,an 的有限序列；表中每个数据的有限序列；表中每个数据元素，除了第元素，除了第1 1个和最后个和最后1 1个外，有且仅有个外，有且仅有一个前趋元素和后继元素。一个前趋元素和后继元素。方式定义：方式定义： 含有含有n n个数据元素的线性表是一种数据构个数据元素的线性表是一种数据构造，表示为：造，表示为： Linear_list=( D , R ) Linear_list=( D , R ) 其中其中:

15、 : D=ai | ai D=ai | aiD0,i=1,2,3,n,n D0,i=1,2,3,n,n 00 R=N, N=|ai-1,ai R=N, N=|ai-1,ai D0 ,i=1,nD0 ,i=1,n D D是数据元素的有限集合，是数据元素的有限集合，R R是是D D上逻辑关上逻辑关系的有限集合。关系系的有限集合。关系N N是一个有序偶对的是一个有序偶对的集合。集合。下一页上一页停止放映顺序表 采用顺序存储构造的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组延续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素a1的物理地址是Loc(a1)，每个元素占d个存

16、储单元，那么第i个元素的存储位置为：Loc(ai) = Loc(a1) + (i-1) * d length=n maxsize 0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an下一页上一页停止放映线性表元素存储表示图 a1a2.ai.元素序号元素序号 内存形状内存形状 存储地址存储地址12. i.LOC(a1)LOC(a1)+1.LOC(a1)+(i-1).下一页上一页停止放映顺序表类型描画 struct SeqList ElemType *data; / 顺序表存储数组的地址顺序表存储数组的地址 int maxsize; / 顺序表最大允许长度顺序表最大允许长度 int

17、 length; / 顺序表当前长度顺序表当前长度 ； SeqList list;/ 定义一个线性表定义一个线性表list 1ElemType代表数组的类型。代表数组的类型。2数组数组data需求在初始化函数中利用需求在初始化函数中利用new操作动态操作动态恳求，恳求，maxsize为其长度。数组的下标从为其长度。数组的下标从0开场。开场。3length表示线性表当前长度，初始长度为表示线性表当前长度，初始长度为0空空表，最大不超越表，最大不超越maxsize。下一页上一页停止放映线性表的根本操作SetnullSetnullL L 置空表置空表LengthLengthL L 求表长度；求表中元

18、素个数求表长度；求表中元素个数GetGetL L，i i 取表中第取表中第i i个元素个元素1 1i i n nPriorPriorL L，i i 取取i i的前趋元素的前趋元素NextNextL L，i i 取取i i的后继元素的后继元素LocateLocateL L，x x 前往指定元素在表中的位置前往指定元素在表中的位置InsertInsertL L，i i，x x 插入元素插入元素DeleteDeleteL L，x x 删除元素删除元素EmptyEmptyL L 判别表能否为空判别表能否为空下一页上一页停止放映顺序表的主要算法 1 1顺序表的初始化顺序表的初始化 顺序表的初始化主要是为

19、顺序表的初始化主要是为ElemTypeElemType类型的数组恳类型的数组恳求空间，下面的初始化函数为顺序表恳求了长度求空间，下面的初始化函数为顺序表恳求了长度为为sizesize的空间。的空间。void Init( SeqList void Init( SeqList * *L, int size ) L, int size ) if( size 0 ) if( size 0 ) L-maxsize = size; L-maxsize = size; L-length = 0; L-length = 0; L-data = new L-data = new ElemTypesize; /E

20、lemTypesize; /恳求空间恳求空间 else coutelse coutlength-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 下一页上一页停止放映void Insert( SeqList *L, int i, ElemType x ) if( iL-length+1 | L-le

21、ngth=L-maxsize ) coutlength-1; j=i-1; j- ) L-dataj+1 = L-dataj; /元素依次右移元素依次右移 L-datai-1 = x; / 向第向第 i 个位置存入新元素个位置存入新元素 xL-length+; / 表长度加一表长度加一 顺序表插入算法顺序表插入算法下一页上一页停止放映3在表中删除第i个元素 算法实现的主要步骤是： 判 别 删 除 位 置 的 合 理 性 。 从第i+1个元素开场，依次向后直到最后一个元素为止，将每个元素向前挪动一个位置。这时第i个元素曾经被覆盖删除。 最后还要将线性表长度减一。下一页上一页停止放映 0 1 2

22、i-2 i-1 i n-1 maxsize a1 a2 a3 ai-1 ai+1 an 0 1 2 i-2 i-1 i n-1 maxsize a1 a2 a3 ai-1 ai ai+1 an 序号序号 内容内容 序号序号 内容内容 删除前删除前 删除后删除后 顺序表中删除元素前后形状顺序表中删除元素前后形状 下一页上一页停止放映删除算法表示举例删除算法表示举例设有数列4,5,8,10,21,25,30,43,59，长度为9，将第6位的元素“25删除。算法描画：从第7个元素开场(i+1)；将第7个元素“30存入第6位，将“25覆盖，即元素左移，挪动元素个数是39-6； for ( int j=

23、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 下一页上一页停止放映void Delete( SeqList *L, int i ) if(iL-length ) cout表中没有第表中没有第i个元素个元素; else for ( int j=i; jlength-1; j+ ) L-dataj-1 = L-dataj; /数据元素左移数据元素左移 L-length-; 顺序表删

24、除算法顺序表删除算法下一页上一页停止放映4在表中查找某个元素 下面是根据数据元素本身的值进展查询的算法，x为需求查找的元素，算法前往元素的实践位置。查找算法:int Find( SeqList *L, ElemType x ) for( int i = 0; ilength; i+ ) /查找胜利, 前往元素位置 i f ( L -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)的结果是的结果是: L3(x)= 3.5 + 1.5x + 6.6