《绪论数据结构》PPT课件.ppt

1,数据结构与应用,马石安 魏文平 编著,2,内容简介,本教材采用面向对象的观点讨论数据结构技术，并以C+类模板作为算法描述工具。教材在简要回顾C+程序设计概念的基础上，全面系统地介绍了线性表、栈和队列、串、数组和广义表、树和二叉树及图等数据结构，讨论了常用的查找和排序技术，对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，还对所有算法进行了C+语言实现和评价，并给出了应用实例。教材附录给出了上机实验内容。,3,教材目录,第0章 C+程序设计语言预备知识0.1 一个简单C+语言程序0.2 指针与引用0.3 动态存贮分配0.4 函数0.5 类与对象0.6 运算符重载0.7 模板,4,第1章 绪论1.1 数据结构的产生和发展1.2 数据结构研究的内容1.3 基本概念和术语1.4 算法第2章线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构2.3 线性表的链式存储结构2.4 顺序表和链表的比较2.5 线性表的应用,5,第章栈和队列3.1 栈3.2 队列3.3 栈的应用第4章 串4.1 串的逻辑结构4.2 串的顺序存储结构4.3 串的链式存储结构4.4 串的应用,6,第5章 数组和广义表5.1 数组5.2 矩阵的压缩存储5.3 广义表5.4 多维数组的应用,7,第6章 树和二叉树6.1 树的逻辑结构6.2 树的顺序存储结构6.3 二叉树的逻辑结构6.4 二叉树的存储结构6.5 线索二叉树6.6 树、森林与二叉树的转换6.7 树的应用,8,第7章 图7.1 图的逻辑结构7.2 图的存储结构7.3 图的遍历7.4 生成树和最小生成树7.5 最短路径7.6 DAG图及其应用,9,第8章 排序8.1 概述8.2 插入排序8.3 交换排序8.4 选择排序8.5 归并排序8.6 基数排序8.7 各种内排序方法的比较和选择,10,第9章 查找9.1 概述9.2 线性表的查找9.3 树表的查找9.4 散列表的查找附录 实验内容,11,第1章 绪论,12,本章主要内容,13,1968年美国人Donald E.Knuth开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作著作。1968年，数据结构作为一门独立的课程在国外开始出现。,1.1数据结构的产生和发展,14,从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构,数据结构问题起源于程序设计,15,从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。,数据结构的发展并未终结,16,无结构阶段 结构化阶段数据结构算法程序 面向对象阶段(数据结构算法)程序,数据结构的发展阶段：,17,计算机处理问题的一般过程:,1.2数据结构研究内容,18,计算机科学是对信息进行表示和处理的科学 计算机中表示和处理的信息以数据的形式体现 数据的表示和组织直接关系到计算机程序能否处理这些数据以及处理的效率,数据结构问题起源于程序设计,19,设计高效率、高可靠性的程序需要 研究数据的特性、数据间的相互关系；数据在计算机内部的存储表示。利用这些特性和关系设计出相应的算法和程序,两大类问题：数值计算、非数值计算,20,数据结构研究内容,建立数据模型,逻辑结构,计算机中的表示,物理/存储结构,操作在计算机中的实现,算法,21,结构静力分析计算,-线性代数方程组,-环流模式方程(球面坐标系),全球天气预报,数值计算的程序设计问题,22,数据计算问题：百鸡问题,公元5世纪末，我国古代数据家张丘建在他所撰写的算经中，提出了这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？,23,公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。,24,非数值计算问题：通讯录管理问题,25,非数值计算问题：学籍管理问题,26,构成家庭成员名的集合，如父亲，儿子，女儿，孙子，孙女，这些数据有一个共同特征，即他们都是家庭的成员名。,非数值计算问题：家庭成员的关系,27,如何实现对弈?各格局之间是什么关系？,非数值计算问题：人机对弈问题,28,如何表示课程之间的先修关系？,非数值计算问题：教学计划编排问题,29,非数值计算问题：天然气管道的铺设,如下图需为城市的各小区之间铺设天然气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境等不同因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？,30,1.3 基本概念和术语,数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数值数据：整数、实数等非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。,31,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。,数据的逻辑结构是从具体问题抽象出来的数据模型,存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。,实质上是内存分配，在具体实现时，依赖于计算机语言。,32,典型逻辑结构,线性表：数据元素之间存在着一对一的线性关系,33,集合：数据元素之间就是“属于同一个集合”,34,树：数据元素之间存在着一对多的层次关系,35,图：数据元素之间存在着多对多的任意关系。,36,存储结构,数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。,顺序存储,链式存储,散列存储,索引存储,37,顺序存储,顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。,38,链式存储,链式存储：对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。链式存储结构通常借助于程序设计语言中的指针类型来实现。,39,根据关键字keyH(key)，来确定存储地址,散列存储,索引存储,40,逻辑结构和存储结构之间的关系,数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。,41,算法（Algorithm）：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。,1.4 算法,42,例：求整型数组元素中的最大值,求解思路：采用类似“打擂”的方法,Step 1：设擂主。最初把数组首元素A0设为擂主，即A0最小数，以min表示，min=A0；Step 2：从次元素A1直至An-1依次与min相比，如果比min小，则该数组元素为新擂主，Step 3：输出最小数min,操作步骤：,43,算法特性,有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着相同的输入仅有唯一的一条路径。可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。输入。一个算法具有零个或多个输入，这些输入取自特 定的数据对象集合。输出。一个算法具有一个或多个输出，这些输出同输入 之间存在某种特定的关系。,44,算法与程序,算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。,45,算法描述,自然语言,流程图,程序设计语言,类程序设计语言,伪代码,46,算法设计要求,正确性。算法的执行结果应当满足预先规定的功能和性能要求。可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性。当输入不合法数据时，应能作适当处理，不至于引起严重后果。高效性。有较高的时间效率并能有效使用存储空间。,47,算法分析,算法分析（Algorithm Analysis）：对算法所需要的计算机资源时间和空间进行估算。时间复杂性（Time Complexity）空间复杂性（Space Complexity）,48,与时间相关因素,算法选用策略问题的规模选用的程序设计语言编译程序所产生的机器代码的质量机器执行的速度,49,算法的执行时间,int Algo1(int n)if(n0)return 0;sum=0;for(i=0;i=n;i+)sum=sum+i;return sum;,算法=控制结构+原操作,50,算法执行时间=(基本操作(i)的执行次数基本操作(i)的执行时间),算法的执行时间 与 原操作执行次数之和 成正比,51,定义:若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n),算法分析:大O符号,52,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,定理：大O符号运算,(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!),(1)常量阶,(n)线性阶,(n2)平方阶,(log2n)对数阶,(2n)指数阶,53,【例1.2】分析以下算法的时间复杂度。temp=i；i=j；j=temp；,算法分析举例,54,【例1.3】分析以下算法的时间复杂度。for(i=1;i=n;+i)+x;,55,【例1.4】分析以下算法的时间复杂度。for(i=1;i=n;+i)for(i=1;i=n;+i)+x;,56,【例1.5】分析以下算法的时间复杂度。for(i=1;i=n;+i)for(j=1;j=i-1;+j)+x;,57,【例1.6】分析以下算法的时间复杂度。i=n-1;while(i=0),58,算法空间性能分析,程序本身所占空间；,输入数据所占空间;,辅助变量所占空间。,定义：算法执行所需空间的增长率，为算法的渐近空间复杂度，简称“算法空间复杂度”。记为：S(n),S(n)=O(g(n),若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。,59,本章要点,数据结构的基本概念和术语：数据、数据元素、数据项、数据结构、数据类型、逻辑结构、物理结构等。典型的逻辑结构有：集合、线性有、树、图等。典型的物理结构有：顺序存储、链式存储、散列存储、索引存储等。算法的概念、特性、设计要求以及算法效率的度量的时间复杂度和空间复杂度的概念和求法。,60,本章结束,