[讲义]高级程序设计3_数据结构ppt课件.ppt

《[讲义]高级程序设计3_数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构1数据结构简介数据结构的基本概念抽象数据类型和软件构造方法算法和算法的时间复杂度2数据结构:数据元素的组织形式和相互之间的关系。(1)数据的逻辑结构：数据元素之间的相互联系方式。(2)数据的存储结构：数据元素在计算机中的存储方式。(3)数据的操作：对一种数据类型的数据进行的某种处理。(4)数据的操作集合：对一种数据类型的数据进行的所有操作。1.1数据结构简介3数据的逻辑结构线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。树结构：除根结点外，每个数据元素只有一个前驱数据元素，可

2、有０个或若干个后继数据元素。图结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。4线性结构树结构图结构5数据的存储结构顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结

3、点的链接关系上。6顺序存储结构链式存储结构7数据的操作从抽象角度，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论；具体来说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。数据结构主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。81.2抽象数据类型和软件构造方法类型是一组值的集合。数据类型是指一个类型和定义在

4、这个类型上的操作集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。数据类型和抽象数据类型的不同之处仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。9抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以安全、

5、快速、方便的完成该应用软件系统的设计。软件的设计采用模块化方法，抽象数据类型就是构造大型软件的最基本模块。101.3算法及其时间复杂度算法是描述求解问题方法的操作步骤集合。描述算法的语言形式1.文字形式:用中文或英文这样的文字来描述算法。2.伪码形式:用一种仿程序设计语言的语言来描述算法。3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。11算法满足以下性质:(1)输入性(2)输出性(3)有限性(4)确定性(5)可执行性算法设计满足以下目标:(1)正

6、确性(2)可读性(3)健壮性(4)高时间效率(5)高空间效率算法时间效率的度量算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种:(1)事后统计方法(2)事前分析方法12程序运行消耗时间的有关因素:(1)书写算法的程序设计语言(2)编译产生的机器语言代码质量(3)机器执行指令的速度(4)问题的规模，即算法的时间效率与算法所处理的数据个数n的函数关系。算法的时间效率是算法所处理的数据个数n的函数，算法的时间效率也称作算法的时间复杂度。定义:T(n)=O(f(n)),当且仅当存在正常数c

7、和n0，对所有的n(n≥n0)满足T(n)≤c×f(n)。13例1-3设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。for(y=0;y

8、时间复杂度为T(n)=O(n3)14例1-4设n为如下算法处理的数据个数，求如下算法的时间复杂度。for(i=1;i<=n;i=2*i)cout<<"i="<