数据结构章.ppt

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

1、数据结构章现在学习的是第1页，共57页上机时间地点安排上机：周五（双周）晚上第11-13节;地点为：浙大紫金港校区计算中心 联系老师：裘雯联系电话：88206072，13858091198现在学习的是第2页，共57页 随着个人计算机和Internet的迅猛发展，以计算机科学技术为核心的信息技术正在深刻地改变着人们的工作方式、生活方式和思维方式。有人预计21世纪的计算机软件业将成为全球高科技产业发展的最主要的推动力。因此，作为软件设计技术的理论基础，“数据结构与数据库技术”就不仅仅是计算机科学技术学科的核心课程，也是所有应用计算机的其它理工学科需要掌握的课程。现在学习的是第3页，共57页智慧城市

2、关键技术取得的新进展智慧城市关键技术取得的新进展 （1）云计算从概念走向实施IBM“蓝云计划”可以对企业现有的基础架构进行整合，实现企业硬件资源和软件资源的统一管理、统一分配、统一部署、统一监控和统一备份，帮助中小企业实现云计算“Google Computer Engine”云计算服务用户可快速、廉价（免费使用限定的流量和存储）地部署自己开发的互联网应用，如网站、游戏等现在学习的是第4页，共57页Amazon Web Services 依靠亚马逊的计算和存储服务，用户能够建立可靠、强大、低成本的互联网应用Apple的“iCloud”适用于 Mac（Macintosh,苹果电脑)、iPhone、

3、iPad 和 iPod touch等设备，不仅可存储 Mac 和所有iOS(由苹果公司开发的手持设备操作系统）设备上的内容，还可以在所有设备上访问你的照片、日历、通讯录、文档以及更多内容，并随时随地保持更新。现在学习的是第5页，共57页大数据：正在到来的数据革命涂子培爆发：大数据时代预见未来的新思维（美）艾伯特-拉斯洛巴拉巴西（2）大数据受到高度关注大数据时代：生活、工作与思维的大变革（英）维克托迈尔-舍恩伯格现在学习的是第6页，共57页全球技术研究和咨询公司Gartner表示，2013年是企业大规模采用大数据技术的一年。根据Gartner针对全球IT主管进行的调查，42%的受访者表示已投资于

4、大数据技术，或将于未来一年内进行相关投资大数据的产生现在学习的是第7页，共57页大数据的重要性大数据的未来现在学习的是第8页，共57页大数据的应用 奥巴马总统连任之路 定位“多金族”通过大数据库，竞选团队发现参与了“快速捐献”计划(允许在网上或者通过短信重复捐钱，而无须重新输入信用卡信息)的人，捐出的资金是其他的捐献者4倍。该计划被迅速推广，并成为竞选重要组成部分。最终竞选资金达到了10亿美元 搞定“摇摆州”利用大数据库，通过计算机模拟竞选，来推算出奥巴马在每个“摇摆州”的胜算，从而确定可以赢得这些州的机会，再进行资源分配 广告精准投放不再依赖于外部媒体顾问来决定广告应该在哪里出现，将广告的购

5、买决策建立在内部大数据库上来精准定位可劝服的选民，使电视广告效率提高了14%现在学习的是第9页，共57页大数据正在对竞选、商业、犯罪预防等涉及政治、经济、大数据正在对竞选、商业、犯罪预防等涉及政治、经济、社会等领域的运作和管理模式产生深刻的影响。社会等领域的运作和管理模式产生深刻的影响。现在学习的是第10页，共57页“大数据”是智慧城市建设的核心问题之一5Vs:量大(Volume）：对海量数据进行处理 种类多(Variety)：对多部门、多行业同构或异构的数据进行处理速度快(Velocity)：对即时数据进行处理真实性要求高(Veracity)：需要对获取的数据进行清洗 价值高(Value)：

6、基于人工智能的数据分析和知识管理大数据的核心：基于海量、复杂（同构或异构）、即时、真实数据的 智能分析预测能力现在学习的是第11页，共57页 数据结构与数据库技术主要内容包括两大部分：第一部分为数据结构，包括线性表、栈和队、串、数组、树、图等，以及排序和查找等操作；第二部分为数据库技术，包括数据库概论、数据库技术基础、关系数据库基本理论、数据库设计、关系数据库标准语言SQL等。现在学习的是第12页，共57页第一部分数 据 结 构现在学习的是第13页，共57页1.1 数据结构的概念数据结构的概念 1.1.1 研究内容研究内容 1.1.2 有关概念和术语有关概念和术语1.2 算法和算法分析算法和算

7、法分析 1.2.1 算法特性算法特性 1.2.2 算法描述算法描述 1.2.3 算法性能分析与度量算法性能分析与度量第一章 绪论现在学习的是第14页，共57页 在用计算机解决实际问题时，一般要经过以下几个步骤：首先，对具体问题抽象出数学模型；然后针对数学模型设计出求解算法；选择或设计合适的数据结构存储相关数据；最后编出程序上机调试，直至得到最终的解答。下面简述各环节的有关内容。1.1.1 研究内容现在学习的是第15页，共57页问题求解之一：问题建模n 一般情况下，实际应用问题可能会各式各样，例如：我们所熟悉的工资表的处理问题，学生成绩管理问题，电话号码查询，数据加密、压缩问题等。n 这些问题中

8、，无论是所涉及到的数据，还是其操作要求，都可能存在一定的差异，但许多问题还是具有一定的相似之处的。例如：现在学习的是第16页，共57页虽然工资表和学生成绩表的具体信息（栏目）不同，但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体，则这两个表结构之间就有了某些共性。从操作方面来看，虽然对这两种表的操作存在差异，但也存在一些相同或相似的基本操作。例如，查询一个人的工资信息和成绩信息，修改有关信息等。现在学习的是第17页，共57页n 正因为许多不同的问题之间存在着的某些共性，可以将一个具体问题用这些共性的形式描述出来问题建模。n 问题建模通常包括：所描述问题中的数据对象的集合；对象间关系

9、及其描述；问题求解的要求及方法等。现在学习的是第18页，共57页n 建立问题模型的好处：通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后借助于这一模型来实现。数据结构、离散数学及许多数学课程中就介绍了许多模型。现在学习的是第19页，共57页问题求解之二：构造求解算法n 通过问题建模，将一个具体的问题转换成一个用模型所描述的抽象的问题。n 借助于这一模型以及已有的知识（例如数据结构中有关图结构的基本知识），可以相对容易地描述出原问题的求解方法，即算法。n 该算法不仅能实现原问题的求解，而且还可能实现许多类似的具体问题的求解。现在学习的是第20页，共57页问题求解之三：选择或设计存储结

10、构n 在构造出求解算法之后，需要考虑在计算机上实现求解了。为此，需要做两方面的工作：选择或设计合适的存储结构，以便将问题所涉及到的数据存储到计算机中。设计程序，实现问题求解。存储形式和问题要求决定了程序设计的方法。现在学习的是第21页，共57页问题求解之四：测试 如何实现预定的功能和目标？n 理论证明：这是计算机科学领域曾经开展过的工作。由于算法和程序的复杂性急剧增长，因而难以实用。n测试：通过对所开发的系统或模块，运行给定的测试数据，以发现存在的错误，而不是证明其正确。现在学习的是第22页，共57页这是当前软件开发领域普遍采用的方法，通常要占系统开发40%以上的工作量。详细描述可参考“软件工

11、程”相关的描述。所设计的算法和程序，需要经过充分的测试才能交付使用。对程序的测试态度反映出学生的治学态度：如果是认真负责的态度，就会认识到，任何设计都难免有疏漏，或者受环境的影响，因而需要高度重视。对程序的测试设计也反映出学生的治学能力：如何设计测试用例？需要依据多种方法、策略和实践。现在学习的是第23页，共57页现在学习的是第24页，共57页1.1.2 有关概念和术语 数据数据(Data)：是能够被计算机识别、存储和加工处理的信息的载体。例如：工资表（编号，姓名，基本工资，奖金），学生成绩表（学号，姓名，考试成绩），电话号码簿；一个家族关系的表示形式；一个群体之间关系的图形描述等。虽然数据的

12、形式及运算存在较大的差异，但存在共性：由若干具有独立意义的个体所组成，个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如，在家族关系数据中，组成数据的基本个体是个人信息，其中各人之间存在着多种关系，如父子关系、兄弟关系等。现在学习的是第25页，共57页 从工资表、学生成绩表这些示例数据可见，数据可以分解为元素的集合。数据元素数据元素(Data Element)：是数据的基本单位（具有完整的独立意义）。也称为元素、结点、顶点、记录。例如：工资表中的个人工资信息；成绩表中的学生成绩信息；家族关系中的个人等。编号姓名基本工资奖金0001张三300020000002李四31002100杭州科

13、力特公司工资表学号姓名考试成绩6001张三956002李四841301班 数学课程学生成绩表现在学习的是第26页，共57页 数据项数据项(Data Item):有独立含义的数据最小单位，也称域有独立含义的数据最小单位，也称域(Field)或字段。它是元素的具体描述信息。或字段。它是元素的具体描述信息。学号姓名考试成绩6001张三956002李四846003王五76表中一行对应一个元素表中一行对应一个元素表中一列对应一个字段表中一列对应一个字段 数据对象数据对象(Data Object)：是具有相同特性的数据元素的集合：是具有相同特性的数据元素的集合，是数据的一个子集。，是数据的一个子集。现在学

14、习的是第27页，共57页 数据结构数据结构(Data Structure)：是指构成数据的元素之间的结构关系：是指构成数据的元素之间的结构关系，即数据的组织形式。，即数据的组织形式。数据元素之间存在以下几类内在的关系：线性结构线性结构：元素之间具有次序关系。树形结构树形结构（树型结构）：元素之间的关系类似于现实中的树。图结构图结构（网状结构）：元素间的关系较复杂。集合集合：元素之间没有关系。逻辑结构现在学习的是第28页，共57页更一般地，数据结构包括以下三个方面的内容：更一般地，数据结构包括以下三个方面的内容：(1)数据元素之间的内在结构关系（逻辑关系），也称为数据的逻辑结构(Logical

15、Structure)。(2)数据元素及其关系在计算机存储器内的实现形式，称为数据的存储结构(Storage Structure)。(3)数据的运算，即对数据施加的操作。现在学习的是第29页，共57页逻辑结构逻辑结构运算定义运算定义抽象数据类型（ADT)存储结构存储结构运算实现（算法）运算实现（算法）分析分析数据结构的组成有关数据结构几个方面的联系图：ADT:是指一个数学模型以及定义在该模型上的一组操作。现在学习的是第30页，共57页 数据类型数据类型高级语言中指数据的取值范围及其上可进行的操作的总称。例 C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用

16、体、枚举等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型。typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;现在学习的是第31页，共57页例例1 1 学生成绩表如下：学号 姓名 数学分析 普通物理 高等代数 平均成绩 880001 丁一 90 85 95 90 880002 马二 80 85 90 85 880003 张三 95 91 99 95 880004 李四 70 84 86 80 880003 王五 91 84 92 89 我们把上表称为一

17、个数据结构（线性表），表中的每一行是一个结点（或记录），它由学号、姓名、各科成绩及平均成绩等数据项组成。现在学习的是第32页，共57页 该表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点，也只有最后一个结点没有直接后继，故称为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。现在学习的是第33页，共57页 该表的存储结构则是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用

18、指针将这些结点链接在一起？对这张表怎样进行查找、删除、插入，这就是数据的运算问题。现在学习的是第34页，共57页例2 人机对奕问题树.现在学习的是第35页，共57页 综上所述，我们可以将数据结构定义为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。现在学习的是第36页，共57页 在不会产生混淆的前提下，我们常将数据的逻辑结构简称为数据结构。线性结构 非线性结构 线性结构的逻辑特征：有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和直接后继。非线性结构的逻辑特征：一个结点可能有多个直接

19、前趋和直接后继。数据的逻辑结构现在学习的是第37页，共57页数据的存储结构可用以下四种基本的存储方法得到：(1)顺序存储方法顺序存储方法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。(2)链接存储方法链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示。(3)索引存储方法索引存储方法：在存储结点信息的同时，还建立附加的索引表。(4)散列存储方法散列存储方法：根据结点的关键字直接计算出该结点的存储地址。现在学习的是第38页，共57页顺序存储结构借助元素在存储器中的相对位置 来表示数据元素间的逻辑关系

20、链式存储结构借助指示元素存储地址的指针表 示数据元素间的逻辑关系现在学习的是第39页，共57页元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储现在学习的是第40页，共57页1536元素元素2 21346元素元素3 3 元素元素4 4存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536

21、元素元素3 3 1346 1346 链式存储链式存储 1400元素元素1 1h1345h现在学习的是第41页，共57页 同一逻辑结构可有不同的存储结构；同理在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。例如，线性表是一种逻辑结构，若采用顺序方法的存储表示，则为顺序表；若采用链接方法的存储表示，则为链表；若采用散列方法的存储表示，则为散列表；若对线性表上的插入、删除运算限制在表的一端进行，则为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则为队列。现在学习的是第42页，共57页 数据的逻辑结构数据的逻辑结构 数据的存储结构数

22、据的存储结构 数据的运算：插入、删除、修改、检索、排序等数据的运算：插入、删除、修改、检索、排序等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：散列存储散列存储 索引存储索引存储现在学习的是第43页，共57页1.2 算法和算法分析 算法：算法：解决某一特定问题的具体步骤的描述，是指令的有限序列。算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及实现一定功能的算法。下面就从算法特性、算法描述、算法性能分析与度量等三个方面对算法

23、进行介绍。现在学习的是第44页，共57页1.2.1 1.2.1 算法特性算法特性 （1）有限性：每一条指令的执行次数必须是有限的。（2）确定性：每条指令的含义都必须明确，无二义性。（3）可行性：每条指令的执行时间都是有限的。（4）输入：具有零个或多个输入的外界量。（5）输出：至少产生一个输出。现在学习的是第45页，共57页要设计一个好的算法通常要考虑以下的要求：正确正确：算法的执行结果应当满足预先规定的功能和性能要求。可读可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果。高效高效：有效使用存储空间和有较高的时间效率。现在学

24、习的是第46页，共57页1.2.2 1.2.2 算法描述算法描述 (1)使用自然语言；(2)使用程序流程图、N-S图等算法描述工具；(3)直接使用某种程序设计语言；(4)使用一种称为伪码语言的描述方法。本书用C+语言来描述算法。现在学习的是第47页，共57页1.2.3 1.2.3 算法性能分析与度量算法性能分析与度量算法的衡量指标：在正确性正确性的前提下，重点关注以下指标：（1）时间性能时间性能：执行算法所耗费的时间；（3）空间性能空间性能：执行算法所耗费的存储空间；（4）其它性能其它性能：是指算法的易读性、可移植性等。现在学习的是第48页，共57页 当然我们希望选用一个所占存储空间小、运行时

25、间短、其它性能也好的算法。然而，实际上很难做到十全十美。原因是上述要求有时相互抵触。要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间又可能要以更多的时间作代价。因此我们只能根据具体情况有所侧重。我们可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。现在学习的是第49页，共57页1.时间复杂度时间复杂度 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数（也称为频度频度）与该语句执行一次所需时间的乘积。但是，当算法转换为程序之后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量，这是很难确定的。我们

26、假设执行每条语句所需的时间均是单位时间，则：一个算法的时间耗费就是该算法中所有语句的频度之和。现在学习的是第50页，共57页时间性能（时间复杂度）的描述方法讨论：（1）以运行算法d的机器时间开销来度量 问题是：与具体机器相关，难以比较（2）以算法中语句的执行次数来衡量 问题是：计算麻烦，可以简化为（3）以算法中语句的执行次数的数量级来替代。现在学习的是第51页，共57页数量级数量级：如果变量 n 的函数f(n)和g(n)满足：lim f(n)/g(n)=常数k（k，0），n则称f(n)和g(n)是同一数量级的，并用f(n)=O(g(n)的形式来表示。现在学习的是第52页，共57页#define

27、 n 自然数 MATRIXMLT(A，B，C)float A n，B n，C n；int i，j，k；(1)for(i=0；in；i+)(2)for(j=0；jn；j+)(3)C ij=0；(4)for(k=0；kn；k+)(5)C ij=C ij+A ik*B kj；/*MATRIXMLT*/例：求两个 n 阶方阵的乘积 C=AB，其算法如下：n+1n(n+1)n2n2(n+1)n3现在学习的是第53页，共57页 该算法中所有语句的频度之和（即算法的时间耗费）为：T(n)=n+1+n(n+1)+n2+n2(n+1)+n3 =2 n3+3 n2+2n+1 我们将算法求解问题的输入量（或初始数据

28、量）称为问题的规模（Size，大小），并用一个整数表示。例如，矩阵乘积问题的规模是矩阵的阶数n。现在学习的是第54页，共57页 算法的时间复杂度时间复杂度(也称也称时间复杂性时间复杂性)：是该算法的时间耗费，它是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度渐近时间复杂度。例如，算法MATRIXMLT的时间复杂度 T(n)=2 n3+3 n2+2n+1 lim T(n)/n3=lim(2 n3+3 n2+2n+1)/n3=2 n n 这表明，当n充分大时，T(n)和n3的数量级相同，可记作T(n)=O(n3)。我们称 T(n)=O(n3)是算法MATRIXMLT的渐近时间复杂度。现在学习的是第55页，共57页 其中“O”是数学符号，其严格的数学定义是：定义定义（大O记号）：如果存在三个正常数c、c1、c2和n0，使得对所有的nn0，有：c1 g(n)f(n)c2g(n)则有：f(n)O(g(n)现在学习的是第56页，共57页 在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。现在学习的是第57页，共57页