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

《第2章数据结构及应用.ppt》由会员分享，可在线阅读，更多相关《第2章数据结构及应用.ppt（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、下一页上一页停止放映第2章数据结构及应用概念及顺序表西安交通大学计教中心西安交通大学计教中心下一页上一页停止放映思考问题数据结构要研究什么问题？什么是线性数据结构和线性表？如何描述线性表？线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？如何处理线性数据结构中的数据？2 2下一页上一页停止放映数据结构问题的由来计算机求解问题的过程步骤：调试程序调试程序编制编制程序程序求解求解结果结果运行运行程序程序结果输出结果输出用户用户需求需求数据类型、格式、数据类型、格式、逻辑结构逻辑结构数据数据逻辑逻辑运算运算数据的物理数据的物理操作操作分析抽象分析抽象实际实际问题问题模型求解模型求解问题问题

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

3、立的的单单位位。但但它它还还可可以以分分割割成成若若干干个个具具有有不不同同属属性性的的项项（字字段段），故故不不是是组成数据的最小单位组成数据的最小单位5 5下一页上一页停止放映数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。6 6下一页上一页停止放映数据的逻辑结构 它是描述数据间的顺序（逻辑）关它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存构，而不管它们在计算机中如何存放。一般用下列二元

4、组来描述：放。一般用下列二元组来描述：DS=DS=（D D，R R）其中：其中：D D：是数据元素的有限集合；是数据元素的有限集合；R R：是数据元素之间关系的集合。是数据元素之间关系的集合。与数据在计算机中的存放的物理位置无关7 7下一页上一页停止放映举例课题组由课题组由1 1名教师、名教师、1313名研究生、名研究生、1616名本名本科生组成；成员关系是：教师指导研究生、科生组成；成员关系是：教师指导研究生、研究生指导研究生指导1212名本科生。名本科生。定义定义DSDS如下：如下：Group=Group=（D D，R R）其中：其中：D=T，G1，,Gn,S11,Snm 1 n 3,1

5、m 2R=R1,R2R1=|1 i n,1 n 3R2=|1in,1 j m,1 n 3,1 m 2 8 8下一页上一页停止放映数据的存储结构又称物理结构又称物理结构是是指指数数据据结结构构在在计计算算机机中中的的表表示示(又又称称映映象象),),即即数数据据在在计计算算机机中中的的存放。存放。数据库中的数据存放在计算机中的物理位置9 9下一页上一页停止放映逻辑结构和存储结构的关系v数据的数据的逻辑结构逻辑结构是从逻辑关系（某种顺序）上观是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。形式上进

6、行研究、推理、运算等各种操作。v数据的数据的存储结构存储结构是逻辑结构在计算机中的实现，是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任是依赖于计算机的；离开了机器，则无法进行任何操作。何操作。v任何一个任何一个算法的设计算法的设计取决于选定的逻辑结构；而取决于选定的逻辑结构；而算法的最终实现算法的最终实现依赖于采用的存储结构。依赖于采用的存储结构。1010下一页上一页停止放映数据存储结构分类v顺序存储结构顺序存储结构v链式存储结构链式存储结构v索引存储结构索引存储结构v散列存储结构散列存储结构 1111下一页上一页停止放映顺序存储结构 把数据元素按某种顺序存放在一块连续

7、的存储单元中的存储形式。数据结点结构:d1 d2 dn数据域数据域特点特点:连续存放连续存放;逻辑上相邻逻辑上相邻,物理上也相邻。物理上也相邻。结构简单，易实现。结构简单，易实现。插入、删除操作不便（需大量移动元素）。插入、删除操作不便（需大量移动元素）。1212下一页上一页停止放映链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:d1.d2dn 数据域数据域 指针域指针域特点特点:非连续存放非连续存放,借助指针来表示元素间的关系借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；插入、删除操作简单，只要修

8、改指针即可；结构较复杂，需要额外存储空间。结构较复杂，需要额外存储空间。1313下一页上一页停止放映索引存储结构 数据按索引形式存放。存储时分为：数据项和索引数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。（存储序号）之间的对应关系。数据结点结构数据结点结构:12 21 35 2 45 5 10 4 3 2 7 1 6 5 数据域数据域 索引顺序号索引顺序号特点：特点：非连续存放；非连续存放；检索速度快；检索速度快；增、删操作简单。增、删操作简单。序 号：1 2 3 4 5 6 7 数据

9、项：索引号：1414下一页上一页停止放映散列存储结构在数据元素与存储位置之间建立一种在数据元素与存储位置之间建立一种存储关系存储关系F F，根据这种关系根据这种关系F F，已知元已知元素素E E，就可以得到它的存储地址，即就可以得到它的存储地址，即D=FD=F（E E）。）。哈希查找中的哈希表就是这样一种存哈希查找中的哈希表就是这样一种存储结构。储结构。特点：特点：数据元素间无内在联系；数据元素间无内在联系；存储形式不定。存储形式不定。1515下一页上一页停止放映数据运算数据运算是指对存放在物理结构上的数据数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。按定义的逻辑结构进

10、行的各种操作。常见操作有：常见操作有：输入、检索、插入、删除、修改、排序输入、检索、插入、删除、修改、排序等。等。1616下一页上一页停止放映数据结构分类 线性表线性表堆栈堆栈队列队列串串数组数组树树二叉树二叉树图图线性结构线性结构非线性结构非线性结构数据结构数据结构DSDS1717下一页上一页停止放映数据结构基本类型 线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路交通线路、通信网络通信网络1818下一页上一页停止放映算法（algorithm）通通通通俗俗俗俗地地地地讲讲讲讲，算算算算法法法法就

11、就就就是是是是一一一一种种种种解解解解题题题题的的的的方方方方法法法法。更更更更严严严严格格格格地地地地说说说说，算算算算法法法法是是是是由由由由若若若若干干干干条条条条指指指指令令令令组组组组成成成成的的的的有有有有穷穷穷穷序序序序列列列列，它它它它必必必必须须须须满满满满足足足足下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：下述条件（也称为算法的五大特性）：输输入入：具具有有0 0个个或或多多个个输输入入的的外外界界量量（算算法法开开始始前前的的初始量）初始量）输出输出：至少有一个输出，是算法执行完后的结果。至少有一个输出，是算法执行

12、完后的结果。有穷性有穷性：每条指令的执行次数必须是有限的。每条指令的执行次数必须是有限的。确定性确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。可行性可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。1919下一页上一页停止放映1 1时间复杂度时间复杂度 一个算法花费的时间与算法中语句的执行次一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费数成正比，哪个算法中语句执行次数多，它花费时间就多。时间就多。数据结构中数据元素个数数据结构中数据元素个数n n称为问题的规模，称为问题的规模，当当n n不断变化时，语句的执行

13、次数也会变化。一不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数个算法中的时间复杂度一般用语句执行次数的数量级来衡量。量级来衡量。例如：例如：for(i=1;i=n;i+)for(j=1;j=i;j+)dij=dataij+1;算法分析O(n2)2020下一页上一页停止放映算法的评价算法评价的标准：算法评价的标准：时间复杂度时间复杂度 指在计算机上运行该算法所花费的时间。用指在计算机上运行该算法所花费的时间。用“O O（数量级）数量级）”来表示，称为来表示，称为“阶阶”。常见。常见的时间复杂度有：的时间复杂度有：O O（1 1）O O（lognlogn）O O（

14、n n）O O（n n2 2 ）常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶空间复杂度空间复杂度 指算法在计算机上运行所占用的存储空间。指算法在计算机上运行所占用的存储空间。度量同时间复杂度。度量同时间复杂度。2121下一页上一页停止放映时间复杂度举例（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=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

15、）O O（n n2 2 ）2222下一页上一页停止放映2 2、空间复杂度、空间复杂度与时间复杂度类似，空间复杂度是指算法与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。似，不再赘述。2323下一页上一页停止放映2.2 线性数据结构 线性表是由有限个同类型的数据元素组成的有线性表是由有限个同类型的数据元素组成的有序序列，一般记作序序列，一般记作（a a1 1

16、,a,a2 2,a,an n）。除了除了a a1 1和和a an n之之外，任意元素外，任意元素a ai i都有一个直接前趋都有一个直接前趋a ai-1i-1和一个直接和一个直接后继后继a ai+1i+1。a a1 1无前趋，无前趋，a an n无后继。无后继。例如，一星期七天的英文缩写表示：例如，一星期七天的英文缩写表示：（SunSun，MonMon，TheThe，wedwed，ThuThu，FriFri，SatSat）是一个线性表，其中的元素是字符串，表的长度是一个线性表，其中的元素是字符串，表的长度为为7 7。2424下一页上一页停止放映线性表的逻辑结构定义：定义：线性表是线性表是n n

17、（n n 0 0）个元素个元素a a1 1,a,a2 2,a,an n 的的有限序列；表中每个数据元素，除了第有限序列；表中每个数据元素，除了第1 1个和最个和最后后1 1个外，有且仅有一个前趋元素和后继元素。个外，有且仅有一个前趋元素和后继元素。形式定义：形式定义：含有含有n n个数据元素的线性表是一种数据结构，表个数据元素的线性表是一种数据结构，表示为：示为：Linear_list=(D,R)Linear_list=(D,R)其中其中:D=D=a ai i|a|ai i D D0 0,i=1,2,3,n,n,i=1,2,3,n,n 00 R=N,N=a R=N,N=|a|ai-1i-1,a

18、,ai i D D0 0 ,i=1,n ,i=1,n D D是数据元素的有限集合，是数据元素的有限集合，R R是是D D上逻辑关系的有上逻辑关系的有限集合。关系限集合。关系N N是一个有序偶对的集合。是一个有序偶对的集合。2525下一页上一页停止放映顺序表 采用顺序存储结构的线性表称为顺序表，它的数采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素假定元素a1的物理地址是的物理地址是Loc(aLoc(a1 1

19、)，每个元素占每个元素占d个存储单元，则第个存储单元，则第i个元素的存储位置为个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*d length=n maxsize 0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an2626下一页上一页停止放映线性表元素存储示意图 a1a2.ai.元素序号元素序号 内存状态内存状态 存储地址存储地址12.i.LOC(a1)LOC(a1)+1.LOC(a1)+(i-1).2727下一页上一页停止放映顺序表类型描述 struct SeqList ElemType*data;/顺序表存储数组的地址顺序表存储数组的地址 int maxs

20、ize;/顺序表最大允许长度顺序表最大允许长度 int length;/顺序表当前长度顺序表当前长度 ；SeqList list;/定义一个线性表定义一个线性表list（1）ElemType代表数组的类型。代表数组的类型。（2）数组数组data需要在初始化函数中利用需要在初始化函数中利用new操作动态操作动态申请，申请，maxsize为其长度。数组的下标从为其长度。数组的下标从0开始。开始。（3）length表示线性表当前长度，初始长度为表示线性表当前长度，初始长度为0（空表）（空表），最大不超过，最大不超过maxsize。2828下一页上一页停止放映线性表的基本操作SetnullSetnul

21、l（L L）置空表置空表LengthLength（L L）求表长度；求表中元素个数求表长度；求表中元素个数GetGet（L L，i i）取表中第取表中第i i个元素（个元素（1 1 i i n n）PriorPrior（L L，i i）取取i i的前趋元素的前趋元素NextNext（L L，i i）取取i i的后继元素的后继元素LocateLocate（L L，x x）返回指定元素在表中的位置返回指定元素在表中的位置InsertInsert（L L，i i，x x）插入元素插入元素DeleteDelete（L L，x x）删除元素删除元素EmptyEmpty（L L）判别表是否为空判别表是否为

22、空2929下一页上一页停止放映顺序表的主要算法（1 1）顺序表的初始化）顺序表的初始化 顺序表的初始化主要是为顺序表的初始化主要是为ElemType类型的数组申类型的数组申请空间，下面的初始化函数为顺序表申请了长度请空间，下面的初始化函数为顺序表申请了长度为为size的空间。的空间。void Init(SeqList*L,int size)if(size 0)L-maxsize=size;L-length=0;L-data=new ElemTypesize;/申请空间申请空间else coutlength-1;j=i-1;j-)/length 是元素个数(8)L-dataj+1=L-dataj

23、;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 3333下一页上一页停止放映void Insert(SeqList*L,int i,ElemType x)if(iL-length+1|L-length=L-maxsize)coutlength-1;j=i-1;j-)L-dataj+1=L-dataj;/元素依次右移元素依次右移 L-datai-1=x;/向第向第 i 个位置

24、存入新元素个位置存入新元素 xL-length+;/表长度加一表长度加一 顺序表插入算法顺序表插入算法3434下一页上一页停止放映（3）在表中删除第i个元素 算法实现的主要步骤是：算法实现的主要步骤是：判断删除位置的合理性。判断删除位置的合理性。从第从第i+1i+1个元素开始，依次向后直到个元素开始，依次向后直到最后一个元素为止，将每个元素向前移最后一个元素为止，将每个元素向前移动一个位置。这时第动一个位置。这时第i i个元素已经被覆盖个元素已经被覆盖删除。删除。最后还要将线性表长度减一。最后还要将线性表长度减一。3535下一页上一页停止放映 0 1 2 i-2 i-1 i n-1 maxsi

25、ze 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 序号序号 内容内容 序号序号 内容内容 删除前删除前 删除后删除后 顺序表中删除元素前后状态顺序表中删除元素前后状态 3636下一页上一页停止放映删除算法示意举例删除算法示意举例设有数列4,5,8,10,21,25,30,43,59，长度为9，将第6位的元素“25”删除。算法描述：从第7个元素开始(i+1)；将第7个元素“30”存入第6位，将“25”覆盖，即元素左移，移动元素个数是3（9-6）；for(int j=i;jlength-1;j

26、+)/length是元素个数(9)L-dataj-1=L-dataj;/i是删除位置(6)长度减“1”L-length-；/操作后，length 等于8最后，得到的结果数列是4,5,8,10,21,30,43,59 3737下一页上一页停止放映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-;顺序表删除算法顺序表删除算法3838下一页上一页停止放映（4）在表中查找某个元素 下下

27、面面是是根根据据数数据据元元素素本本身身的的值值进进行行查查询询的的算算法法，x为为需需要要查查找找的的元元素素，算算法法返返回回元元素素的的实实际位置。查找算法际位置。查找算法:int Find(SeqList*L,ElemType x)for(int i=0;ilength;i+)/查找成功查找成功,返回元素位置返回元素位置 if(L-datai=x)return i+1;return 0;/查找失败查找失败,返回返回 0 3939下一页上一页停止放映顺序表应用举例顺序表应用举例【例例2-1】利用顺序表表示多项式，实现两个利用顺序表表示多项式，实现两个一元多项式一元多项式L1(x)和和L2

28、(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)。例如线性表例如线性表(6,1),(-5,4),(8,10)表示多项式表示多项式:P(x)=6x-5x4+8x10。4040下一页上一页停止放映用用顺顺序序表表L1和和L2存存放放两两个个多多项项式式L1(x)和和L2(x)，用用顺序表顺序表L3来存放

29、结果。来存放结果。多项式相加算法可按照下列步骤实现：多项式相加算法可按照下列步骤实现：设设定定三三个个位位置置变变量量i、j和和k，分分别别指指向向顺顺序序表表L1、L2和和L3的第一个元素。本例中的第一个元素。本例中i、j和和k初值均为初值均为1。比比较较i和和j两两个个位位置置数数据据元元素素的的指指数数项项，如如果果L1中中第第i项项指指数数小小，则则将将此此项项数数据据元元素素复复制制到到L3的的位位置置k中中，i+和和k+；如如果果L2中中第第j项项指指数数小小，则则同同样样是是将将此此项项复复制制到到L3中中，j+和和k+；如如果果两两项项指指数数项项相相等等，则则合合并并同同类类

30、项项后后再再将将结结果果复复制制到到L3中中，并并同同时时i+、j+和和k+。当当L1或或L2中中的的数数据据元元素素处处理理完完毕毕，则则将将另另一一个个顺顺序序表的表的剩余部分剩余部分复制到复制到L3中。中。算法描述算法描述 4141下一页上一页停止放映参照程序参照程序 例例2-12-1P2-1.cppP2-1.cpp线性表操作的综合例子线性表操作的综合例子 4242下一页上一页停止放映顺序存储结构的特点数据连续存放、随机存取数据连续存放、随机存取逻辑上相邻，物理上也相邻逻辑上相邻，物理上也相邻存储结构简单、易实现存储结构简单、易实现插入、删除操作不便插入、删除操作不便存储密度大，空间利用率高存储密度大，空间利用率高结论结论：顺序存储结构适合于表中元素变动顺序存储结构适合于表中元素变动较少的情况。较少的情况。4343下一页上一页停止放映结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址：http:/课件下载地址:http:/202.117.35.160/moodle15我的E-mail地址:LZQ答疑安排：每星期五下午：4:006:00 地点：计教中心505房间4444