《DS数据结构概述》由会员分享，可在线阅读，更多相关《DS数据结构概述（38页珍藏版）》请在金锄头文库上搜索。
1、DS-DS-数据结构概述数据结构概述软件学院软件学院 李媛媛李媛媛本章重点难点重点重点: 数据结构的逻辑结构、存储结构以及基本操数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系；作的概念及相互关系；抽象数据类型抽象数据类型(ADT)的概念和实现方法，算的概念和实现方法，算法的时间复杂性和空间复杂性分析。法的时间复杂性和空间复杂性分析。难点难点: 抽象数据类型抽象数据类型(ADT)的概念和实现方法；的概念和实现方法；算法的时间复杂性和空间复杂性分析算法的时间复杂性和空间复杂性分析。软件学院软件学院 李媛媛李媛媛1.1 为什么要学习数据结构为什么要学习数据结构算法+数据结构=程序设计处理问
2、题的策略给出问题的数学模型编制出用计算机处理问题的指令问题问题构建数学模型构建数学模型算法实现算法实现软件学院软件学院 李媛媛李媛媛p计算机的发展p数据处理的种类p数据数值数据数值数据非数值数据非数值数据数(整数,实数)字符字符串文字图形图象声音对客观对象的符号表示程序程序原始数据原始数据结果数据结果数据软件硬件应用领域软件学院软件学院 李媛媛李媛媛学习数据结构的原因：学习数据结构的原因：计算机处理的数据量越来越大。计算机处理的数据量越来越大。数据类型越来越多。数据类型越来越多。数据的结构越来越复杂。数据的结构越来越复杂。数据结构是一门研究数据结构是一门研究“非数值计算程序设计问题非数值计算程
3、序设计问题中计算机的操作对象以及它们之间的关系和操作中计算机的操作对象以及它们之间的关系和操作的学科。的学科。1.1 为什么要学习数据结构为什么要学习数据结构软件学院软件学院 李媛媛李媛媛 已知数据如下：已知数据如下：结论结论1：杂乱无章的数据不能表达和交流。：杂乱无章的数据不能表达和交流。例例119850700163172978233000340304195902261011工号：工号：1985070016电话号码：电话号码：3172978邮编：邮编：233000身份证号码：身份证号码：340304195902261011软件学院软件学院 李媛媛李媛媛 例例2电话号码簿（电话号码簿（a1,b
4、1）（）（ a2,b2 ）（ ）（ an,bn ）,其中，其中，ai为某人姓名，为某人姓名，bi为该人的电话号码。为该人的电话号码。结论结论2：数据之间是有联系的。：数据之间是有联系的。软件学院软件学院 李媛媛李媛媛 例例3家族的族谱家族的族谱: 假设某家族有假设某家族有10个成员个成员A, B,C,D,E,F,G,H,I,J，他们之间的血缘关系可以用如下图表示。，他们之间的血缘关系可以用如下图表示。JIACBDHGFE结论结论3：数据之间是有结构的。：数据之间是有结构的。软件学院软件学院 李媛媛李媛媛学号学号 姓名姓名 性别性别 出生日期出生日期 入学成绩入学成绩 所在班级所在班级 0020
5、1 杨润生杨润生 男男 82/06/01 561 00计算机计算机200102 石磊石磊 男男 83/12/21 512 00计算机计算机100202 李梅李梅 女女 83/02/23 532 00计算机计算机200301 马耀先马耀先 男男 82/07/12 509 00计算机计算机3 已知某级学生情况已知某级学生情况, ,要求分班按入学成绩排列顺序。要求分班按入学成绩排列顺序。说明：在此类文档管理中说明：在此类文档管理中,可以有查找、修改、插入、删可以有查找、修改、插入、删除等操作。除等操作。例例4结论结论4：在某种数据结构上可以定义一组运算。：在某种数据结构上可以定义一组运算。软件学院软
6、件学院 李媛媛李媛媛1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语1 1、数据数据：对客观事物的符号表示，信息的载体，能被计算机识别、存：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。储和加工处理。如整数，实数，字符串、图象、声音等都是数据。2 2、数据元素数据元素：数据的基本单位，又可称为元素、结点、顶点、记录等。：数据的基本单位，又可称为元素、结点、顶点、记录等。3 3、数据项数据项: : 是数据不可分割的最小单位。如学号、姓名等。是数据不可分割的最小单位。如学号、姓名等。 一个数据元素可以由若干个数据项构成
7、。一个数据元素可以由若干个数据项构成。4 4、数据对象数据对象：性质相同的数据元素的集合。如所有班名相同的记录集：性质相同的数据元素的集合。如所有班名相同的记录集合。合。5 5、数据类型数据类型：是指一个类型和定义在这个类型上的操作集合。：是指一个类型和定义在这个类型上的操作集合。分为：分为：原子类型原子类型和和结构类型结构类型6 6、抽象数据类型抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集：是指一个逻辑概念上的类型和这个类型上的操作集合合。优点：优点：将数据和操作封装在一起实现了信息隐藏。将数据和操作封装在一起实现了信息隐藏。软件学院软件学院 李媛媛李媛媛 抽抽象象数数据据类类
8、型型的的定定义义可可以以由由元元素素、元元素素之之间间的的关关系系及及操操作作三三部部分分构构成。成。 抽象数据类型的定义格式抽象数据类型的定义格式ADT 抽象数据类型名抽象数据类型名数据对象数据对象： 数据关系数据关系： 基本操作基本操作： ADT 抽象数据类型名抽象数据类型名例如：例如：P4 例例1-41.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语数据结构：数据结构：相互之间存在一种或多种特定关相互之间存在一种或多种特定关系的数据元素的集合。系的数据元素的集合。 形式定义为：形式
9、定义为：Data_Structure(D, R R) 例如：例如：P5 例例1-5软件学院软件学院 李媛媛李媛媛数据结构包括以下内容：数据结构包括以下内容：（1）数数据据的的逻逻辑辑结结构构。从从逻逻辑辑关关系系上上描描述述数数据据，与与数数据据存存储储无无关关，独独立立于于计计算算机机。它它包包括括以以下下四类基本结构：四类基本结构：集合：集合：同属一个集合同属一个集合线性结构：线性结构：一对一一对一树形结构：树形结构：一对多一对多图状结构或网状结构：图状结构或网状结构：多对多多对多1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛数据结构类型数据
10、结构类型树图线性表栈队列串数组广义表数据结构线性结构非线性结构软件学院软件学院 李媛媛李媛媛（2）数数据据的的物物理理结结构构，数数据据结结构构在在计计算算机机存存储储器中的表示，又称存储结构。它包括：器中的表示，又称存储结构。它包括：顺顺序序存存储储结结构构：借借助助数数据据元元素素在在存存储储器器中中相相对对位置表示逻辑关系位置表示逻辑关系链链式式存存储储结结构构：依依靠靠数数据据元元素素中中的的指指针针表表示示元元素之间的逻辑关系素之间的逻辑关系索引索引散列散列1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛对每种数据结构，主要讨论如下三方面
11、的问题：对每种数据结构，主要讨论如下三方面的问题：数据的逻辑结构数据的逻辑结构数据元素之间的逻辑关系，是具体关系的抽象。数据元素之间的逻辑关系，是具体关系的抽象。数据的存储结构数据的存储结构(物理结构物理结构)：数据元素及其关系在计算机内存中的表示；数据元素及其关系在计算机内存中的表示；数据的运算（或算法）数据的运算（或算法）即对数据施加的操作。定义在数据的逻辑结构上的抽即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。象的操作。软件学院软件学院 李媛媛李媛媛1.3 1.3 算法和算法描述算法和算法描述1、算法、算法算算法法是是对对特特定定问问题题求求解解步步骤骤的的一一种种描描述述，是
12、是指令的集合。指令的集合。算算法法的的特特性性：有有穷穷性性、确确定定性性、可可行行性性、输输入、输出入、输出软件学院软件学院 李媛媛李媛媛 算法的基本特征算法的基本特征有穷性：有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。间内完成。确定性：确定性：组成算法的操作必须清晰无二义性。组成算法的操作必须清晰无二义性。可行性：可行性：算法中的所有操作都必须足够基本，都可以通过已经实算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。现的基本操作运算有限次实现之。输入：输入：作为算法加工对象的量值，通常体现为
13、算法中的一组变量。作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：输出：它是一组与输入有确定关系的量值，是算法进行信息加工它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。后得到的结果，这种确定关系即为算法的功能。软件学院软件学院 李媛媛李媛媛2、算法设计的要求、算法设计的要求正确性正确性可读性可读性健壮性健壮性高高效效性性1.3 1.3 算法和算法描述算法和算法描述软件学院软件学院 李媛媛李媛媛算法必须是算法必须是“正确的正确的”l所谓算
14、法是正确的，除了应该满足算法说明中写明的所谓算法是正确的，除了应该满足算法说明中写明的“功能功能”之外，应对之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。易于隐藏错误而难以调试。应有很好的应有很好的“可读性可读性”l一个一个算法算法应当思路清晰、层次分明、简单明了
15、、易读易懂。应当思路清晰、层次分明、简单明了、易读易懂。算法的设计要求算法的设计要求软件学院软件学院 李媛媛李媛媛必须具有必须具有“健壮性健壮性”l算法的健壮性指的是，算法应对非法输入的数据作出恰当反映算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。示错误或错误性质的值。算法的效率算法的效率l应考虑所设计的算法具有应考虑所设计的算法具有“高效率与低存储量高效率与低存储量”。高效率与低。高效率与低存储量是矛盾的，要视具体问题而定。存储量是矛盾的，要视具体问题而定
16、。算法的设计要求算法的设计要求软件学院软件学院 李媛媛李媛媛算法描述：算法描述：1.文字形式文字形式 :用中文或英文这样的文字来描述算法。用中文或英文这样的文字来描述算法。2.伪伪码码形形式式 :用用一一种种仿仿程程序序设设计计语语言言的的语语言言来来描描述述算算法。比如法。比如类类C语言语言。3.程程序序设设计计语语言言形形式式 :用用某某种种程程序序设设计计语语言言描描述述算算法法。其其优优点点是是算算法法不不用用修修改改，直直接接作作为为程程序序语语句句键键入入计计算机，计算机能调用和运行算机，计算机能调用和运行。1.3 1.3 算法和算法描述算法和算法描述软件学院软件学院 李媛媛李媛媛
17、算法描述：算法描述：类类C语言语言比比程序设计语言程序设计语言更容易描述和被理解，比文更容易描述和被理解，比文字描述的自然语言更接近程序设计语言，容易转换成高字描述的自然语言更接近程序设计语言，容易转换成高级语言。级语言。 例如：例如：P7 例例1-61.3 1.3 算法和算法描述算法和算法描述软件学院软件学院 李媛媛李媛媛1.算法是对特定问题求解步骤的一种描述，是指令的集算法是对特定问题求解步骤的一种描述，是指令的集合。一个问题可以有多种算法。合。一个问题可以有多种算法。2.程序是用某种程序设计语言对算法的具体实现。程序是用某种程序设计语言对算法的具体实现。软件开发生命周期：软件开发生命周期
18、：需求分析需求分析概要设计概要设计算法算法设计设计程序编码程序编码运行维护运行维护算法和程序的区别算法和程序的区别软件学院软件学院 李媛媛李媛媛1.程序可以是无穷的，例如：程序可以是无穷的，例如：OS；算法必须是有穷的。算法必须是有穷的。2.程序可以是错误的，算法必须是正确的。程序可以是错误的，算法必须是正确的。3.程序是用程序设计语言描述，在机器上可以运程序是用程序设计语言描述，在机器上可以运行；算法也可以用框图，自然语言等方式描述。行；算法也可以用框图，自然语言等方式描述。算法和程序的区别算法和程序的区别软件学院软件学院 李媛媛李媛媛1.4 1.4 算法时空效率分析方法算法时空效率分析方法
19、算算法法分分析析就就是是对对算算法法质质量量优优劣劣的的评评价价，通通常常分为分为事后统计事后统计和和事前分析事前分析两种方法。两种方法。算法分析应从两个角度：算法分析应从两个角度：依依据据算算法法编编写写的的程程序序在在计计算算机机中中运运行行时时间的多少的度量，即间的多少的度量，即时间复杂度时间复杂度。依依据据算算法法编编写写的的程程序序在在计计算算机机中中占占存存储储空间的多少的度量，即空间的多少的度量，即空间复杂度空间复杂度。注注：时时间间复复杂杂度度和和空空间间复复杂杂度度合合称称算算法法的的复杂度复杂度。软件学院软件学院 李媛媛李媛媛1.4 1.4 算法时空效率分析方法算法时空效率
20、分析方法1.算法的时间复杂度算法的时间复杂度 程序运行所需要的时间取决于以下因素：程序运行所需要的时间取决于以下因素： (1)机器执行指令的速度机器执行指令的速度 (2)书写算法的程序设计语言书写算法的程序设计语言 (3)编译产生的机器语言代码质量编译产生的机器语言代码质量 (4)算法所选用的策略算法所选用的策略(5 5)问题的规模问题的规模，即算法的时间效率与算法所处理的数据个数，即算法的时间效率与算法所处理的数据个数n的的函数关系。函数关系。软件学院软件学院 李媛媛李媛媛算法的时间复杂度算法的时间复杂度是是算算法法执执行行的的时时间间耗耗费费，是是求求解解问问题题规模规模n的函数。记为：的
21、函数。记为：T(n)=O(f(n)。(1)时间复杂度的计算方法时间复杂度的计算方法频度统计法频度统计法 例例1：语语句句 x=x+1;执执行行频频度度为为1，时时间间复复杂度记为：杂度记为： T(n)=O(1)1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛 (1)时间复杂度的计算方法时间复杂度的计算方法频度统计法频度统计法例例2： for(i=1; i=n; i+) x=x+1; 算法的频度算法的频度=n+1 则算法的时间复杂度为则算法的时间复杂度为O(n)1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛(1)时间复
22、复杂度的度的计算方法算方法频度度统计法法例例3： for(i=1; i=n; +i) for(j=1; j=n; +j) x=x+1; 算法的算法的频度度=n(n+1) 则算法的算法的时间复复杂度度为O(n2)1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛(1)时间复复杂度的度的计算方法算方法频度度统计法法例例4： for(i=1; i=n; +i) for(j=1; j=n; +j) cij = 0; for(k=1; k=n; +k) cij += aik * bkj; 算法的算法的频度度=n+1 + n(n+1) + n2 + n2(n+1) +
23、n3 = 2n3 + 3n2 + 2n + 1 则算法的算法的时间复复杂度度为O(n3)1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛(2)有有的的情情况况下下，算算法法中中基基本本操操作作重重复复执执行行的的次次数数还还随随问问题题的的输输入入数数据据集集不不同同而而不不同同。此此时时，一一种种办办法法是是讨讨论论平平均均时时间复杂度间复杂度，一种办法是讨论，一种办法是讨论最坏的情况下的时间复杂度最坏的情况下的时间复杂度。(3)常见的常见的时间复杂度按数量级递增排列依次为：时间复杂度按数量级递增排列依次为：常常数数阶阶O(1)对对数数阶阶O(log2n
24、)线线性性阶阶O(n)线线性性对对数数阶阶O(nlog2n)平平方方阶阶O(n2)立立方方阶阶O(n3)k次次方方阶阶O(nk)指指数阶数阶O(2n)。 1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛讨论：讨论： “不不必必最最求求高高效效算算法法，低低效效算算法法可可以以在在高高速速计计算机上得到补偿。算机上得到补偿。”这一说法正确吗？这一说法正确吗？1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛设设A1,A2,A3是是求求解解同同一一问问题题的的不不同同算算法法，其其时时间间复复杂杂度度分分别别是是： O(n)
25、,O(nlgn), O(N!)。C1和和C2为为计计算算机机，且且C2的的计算速度是计算速度是C1的的10倍。倍。复杂度复杂度C1可解规模可解规模C2可解规模可解规模可解规模的关系可解规模的关系 O(n) N11 N21 N21=10N11O(nlgn) N12 N22 N22=10N12O(N!) N13 N23 N23=N13+小常数小常数1.4 1.4 算法时空效率分析方法算法时空效率分析方法结论：结论：“不必最求高效算法，低效算法可以在高速计算机不必最求高效算法，低效算法可以在高速计算机上得到补偿。上得到补偿。”这一说法是错误的这一说法是错误的!软件学院软件学院 李媛媛李媛媛2.算法的
26、空间复杂度算法的空间复杂度是是算算法法的的空空间间耗耗费费，也也是是求求解解问问题题规规模模n的的函数。记为：函数。记为：S(n)=O(f(n)。算法执行期间所需要的存储量包括：算法执行期间所需要的存储量包括：输入数据所占空间（固定，与算法无关）输入数据所占空间（固定，与算法无关）程序本身所占空间（固定，与算法无关）程序本身所占空间（固定，与算法无关）辅助变量辅助变量所占空间所占空间1.4 1.4 算法时空效率分析方法算法时空效率分析方法软件学院软件学院 李媛媛李媛媛本章小结l数据结构研究的是数据的数据结构研究的是数据的逻辑结构逻辑结构和和存储结构存储结构以及其算以及其算法；法；l本课程从本课
27、程从抽象数据类型抽象数据类型角度讨论各种类型的数据结构及角度讨论各种类型的数据结构及其应用；其应用；l本课程使用本课程使用类类C语言语言作为算法的描述工具；作为算法的描述工具；l算法的五大特性：算法的五大特性：有穷性、确定性、可行性、输入、输有穷性、确定性、可行性、输入、输出出；l一个一个“好好”的算法应满足的算法应满足正确性、可读性、健壮性正确性、可读性、健壮性以及以及效率与低存储量的需求效率与低存储量的需求；l算法的分析主要考察算法的算法的分析主要考察算法的时间复杂度时间复杂度和和空间复杂度空间复杂度。软件学院软件学院 李媛媛李媛媛课堂练习1. 算法的时间复杂度取决于（算法的时间复杂度取决于（ ） A问题的规模问题的规模 B. 待处理数据的初态待处理数据的初态 C. A和和B2.计算机算法指的是（计算机算法指的是（1），它必须具备（），它必须具备（2） 这三个特性。这三个特性。(1) A计算方法计算方法 B. 排序方法排序方法 C. 解决问题的步骤序列解决问题的步骤序列 D. 调度方法调度方法(2) A可执行性、可移植性、可扩充性可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性确定性、有穷性、稳定性 D. 易读性、稳定性、安全性易读性、稳定性、安全性 结束结束
