【文档说明】计算机软件技术基础--数据结构课件.ppt，共(41)页，267.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76546.html

以下为本文档部分文字说明：

计算机软件技术基础——数据结构东北大学网络学院计算机软件技术基础课程组教师：高克宁E-mail：c_gkn@necmail.neu.edu.cn数据结构——概述2007东北大学网络学院计算机软件技术基础课程组

2主要内容数据结构讨论的范畴基本概念抽象数据类型算法的特性、分类及度量数据结构的选择和评价数据结构——概述2007东北大学网络学院计算机软件技术基础课程组3数据结构讨论的范畴程序=数据结构+算法数据结构：问题的数据模型数据的逻辑结构数据的物理结构数据的运

算算法：求解问题的策略查找排序数据结构——概述2007东北大学网络学院计算机软件技术基础课程组4数据结构讨论的范畴数值计算的程序设计问题圆的面积（函数）结构静力分析计算（线性代数方程组）人口增长预报（微分方程）数据结构——概述2007东北大学网络学院计算机软件技术基

础课程组5数据结构讨论的范畴非数值计算问题的程序设计问题学生信息管理系统（表）算法：需要检索的项目如何检索、用户界面模型：各种表格人机对弈（树）算法：对弈的规则和策略模型：棋盘及棋盘的格局教学计划编排问题（图）算法：课表编排的规则模型：课程以及课程间关

系数据结构——概述2007东北大学网络学院计算机软件技术基础课程组6数据结构——概述2007东北大学网络学院计算机软件技术基础课程组7数据结构——概述2007东北大学网络学院计算机软件技术基础课程组8数据结构——概述2007东北大学网络学院计算

机软件技术基础课程组9数据结构讨论的范畴数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理通过算法训练来提高学

生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高数据结构——概述2007东北大学网络学院计算机软件技术基础课程组10数据结构基本概念数据（data)所有能输入到计算机中去的描述客观事物的符号是计算机操作的对象的总称是计算机处理的信息的某种特定的符号

表示形式数据元素（dataelement）数据结构中讨论的基本单位，也称结点（node）或记录（record）是数据（集合）中的一个“个体”例如：学生信息检索系统中学生信息表中的一个记录、对弈问题中状态树的一个状态、排课问题中的一个顶点等，都被称为一个数据元素数据结构——概述200

7东北大学网络学院计算机软件技术基础课程组11数据结构基本概念数据项（dataitem）有独立含义的数据最小单位，也称域(field)数据元素可以是数据项的集合数据对象是性质相同的数据元素的集合，是数据的一个子集。数据元素是数据对象的一个实例例如整数数据对象是集合N

={…-2,-1,0,1,2…..}数据结构——概述2007东北大学网络学院计算机软件技术基础课程组12数据结构基本概念数据结构（datastructure)数据结构是相互之间存在着某种逻辑关系的数据元素的集合例如：在一维数组{a1,

a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系{<ai,ai+1>|i=1,2,3,4,5}数据结构——概述2007东北大学网络学院计算机软件技术基础课程组13什么是数据结构？数据结构的三个方面数据的

逻辑结构从具体问题抽象出来的数学模型，它与数据的存储无关线性结构：线性表、栈、队列非线性结构：树、图数据的存储结构数据结构在计算机中的标识（又称映像）称为数据的物理结构，数据的逻辑结构在计算机存储器中的实现顺序存储链式存储数据的运算检索、排序、插入、

删除、修改等数据结构——概述2007东北大学网络学院计算机软件技术基础课程组14什么是数据结构？(1)数据的逻辑结构数据的逻辑结构可以用一组数据（表示为结点集合D），以及这些数据之间的一组二元关系（关系集合S）来表示

：(D，S)其中D是数据元素的有限集，是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据S是D上关系的有限集，是定义在集合D上的一组关系，用它描述结点数据之间的逻辑关系Data_St

ructures=(D,S)数据结构——概述2007东北大学网络学院计算机软件技术基础课程组15什么是数据结构？(2)数据的逻辑结构结点的数据类型高级语言中指数据的取值范围及其上可进行的操作的

总称例C语言中基本数据类型：int,char,float,double等构造数据类型：数组、结构体、共用体、枚举指针、空(void)类型用户也可用typedef自己定义数据类型结点的类型可以是基本数据类型，也可以根据应

用的需要来灵活定义typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu,*pstu;数据结构——概述2007东北大学网络学院计算机软件技术

基础课程组16什么是数据结构？(3)数据的逻辑结构关系S阐明数据结构的特性线性结构（linearstructure）一个对一个树型结构（treestructure）一个对多个图状结构（gr

aphstructure）多个对多个数据结构——概述2007东北大学网络学院计算机软件技术基础课程组17什么是数据结构？(4)数据的逻辑结构线性结构关系S是一种线性关系，或称为‘前后关系’，有时也称为‘大小关系’。关系S是有向的，且满足全序性和单索性等约束条件全序性线性结构的全

部结点两两皆可以比较前后（关系S）单索性每一个结点a都存在唯一的一个直接后继结点b数据结构——概述2007东北大学网络学院计算机软件技术基础课程组18什么是数据结构？(5)数据的逻辑结构树型结构树型结构又称为层次结构，其关系S称为层次关系树型结构的最高层次的结点称为根

（root）结点只有它没有父结点每一个结点可以有多于一个的‘子结点’，但是它只能有唯一的‘父结点’图状结构也称为结点互联的网络结构，允许结点具有多个‘父结点’图结构的关系S没有任何约束，无法利用关系S的约束来设计图结构的存储结构因特网

的web网页链接关系是一个非常复杂的图结构数据结构——概述2007东北大学网络学院计算机软件技术基础课程组19什么是数据结构？(6)数据的逻辑结构三种结构的区别树结构和图结构的基本区别就是“每个结点是否仅仅从属一个父结点”线性结构和树结构的基本区别是“每个结点是否仅仅有一个直接后

继”数据结构——概述2007东北大学网络学院计算机软件技术基础课程组20什么是数据结构？(7)数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现（逻辑结构在存储器中的映象）计算机的主存储器的特性存储空间提供了一种具有非负整数

地址编码的，相邻单元的集合其基本的存储单元是字节计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同数据结构——概述2007东北大学网络学院计算机软件技术基础课程组21什么是数据结构？(8)数据

的存储（物理）结构数据的存储结构是建立一种映象，对于数据逻辑结构（D,s）,其中s∈S“数据元素”的映象对它的结点集合D建立一个从D到存储器的单元的映射：对于每一个结点d∈D都对应一个唯一的连续存储区域。“关系”的映象每一个关系元组（d1,d2）

∈s（其中d1,d2∈D是结点），d1,d2的逻辑后继关系应映射为存储单元的地址顺序关系（或链接关系）数据结构——概述2007东北大学网络学院计算机软件技术基础课程组22什么是数据结构？(9)数据的存

储（物理）结构顺序存储结构用一块无空隙的存储区域存储数据称为顺序存储借助元素在存储器中的相对位置来表示数据元素间的逻辑关系结点间的逻辑后继关系用存储单元的自然顺序关系来表达链式存储结构借助指示元

素存储地址的指针表示数据元素间的逻辑关系两个结点的逻辑后继关系可以用指针的指向来表达数据结构——概述2007东北大学网络学院计算机软件技术基础课程组23什么是数据结构？(10)数据的存储（物理）结构LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容

Loc(元素i)=Lo+（i-1)*m顺序存储元素1元素2元素i元素nhead^数据结构——概述2007东北大学网络学院计算机软件技术基础课程组24什么是数据结构？(11)数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构数据结构——概述2007东北大学

网络学院计算机软件技术基础课程组25抽象数据类型（AbstractDataType简称ADT）抽象数据类型是描述数据结构的一种理论工具特点是把数据结构作为独立于应用程序的一种抽象代数结构来描述抽象数据类型

不同于具体的数据结构目的是使人们能够独立于程序的实现细节来理解数据结构的特性数据结构——概述2007东北大学网络学院计算机软件技术基础课程组26抽象数据类型（1）抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实

现无关即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用数据结构——概述2007东北大学网络学院计算机软件技术基础课程组27抽象数据类型(2)是指一个数学模型以及定义在此数学模型上的

一组操作。“抽象”的定义在于数据类型的数学抽象特性抽象数据类型的形式定义：ADT=（D，S，P）其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操

作：〈基本操作的定义〉}ADT抽象数据类型名数据结构——概述2007东北大学网络学院计算机软件技术基础课程组28例如，抽象数据类型复数的定义：ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分；|e2是复数的虚数

部分}基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(

Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：

用sum返回两个复数z1,z2的和值。}ADTComplex数据结构——概述2007东北大学网络学院计算机软件技术基础课程组29抽象数据类型(3)ADT重要特征数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和

外部用户的接口（即外界使用它的方法）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节数据结构——概述2007东北大学网络学院计算机软件技术基础课程组30抽象数据类型(4)ADT与数据类型的关系抽象数据类型

和数据类型实质上是一个概念“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象数据类型的范畴更广，它不再局限于各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型数

据结构——概述2007东北大学网络学院计算机软件技术基础课程组31抽象数据类型(4)数据结构——概述2007东北大学网络学院计算机软件技术基础课程组32算法的特性与度量算法（algorithm）解决某一特定问题的具体步骤的

描述，是指令的有限序列程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解数据结构——概述2007东北大学网络学院计算机软件技术基础课程组33算法的特性与度量算法的特性有穷性对于任意一组合法输入值，在执行有穷步

骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径数据结构

——概述2007东北大学网络学院计算机软件技术基础课程组34算法的特性与度量(1)算法的特性可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输

入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能数据结构——概述2007东

北大学网络学院计算机软件技术基础课程组35算法的特性与度量(2)算法设计的原则正确性(correctness)可读性(readability)健壮性(robustness)高效率与低存储量正确性：算法应当满足以特定的“规格说明”方式给出

的需求以下四个层次：无语法错误、随意数据、刻意数据、一切合法数据可读性：算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；晦涩难读的程序易于隐藏较多错误而难以调试健壮性：当输入的数据非法时，算法应当

恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。处理出错的方法也不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理高效率与低存储量：效率指的是算法执

行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关数据结构——概述2007东北大学网络学院计算机软件技术基础课程组36算法的特性与度量(3)算法的执行效率解决同一个问题总是存在着多种算法，而算法设计者在所花费的时间和所

使用的空间资源往往要两者之间采取折中，采用某种以空间资源换取时间资源的策略算法设计者可以通过算法分析，判断所提出的算法是否现实，设计出更好的算法数据结构——概述2007东北大学网络学院计算机软件技术基础课程组37算法的特性与度量(4)算法的执行效率用依据

该算法编制的程序在计算机上执行所消耗的时间来度量和算法执行时间相关的因素算法选用的策略问题的规模编写程序的语言编译程序产生的机器代码的质量计算机执行指令的速度数据结构——概述2007东北大学网络学院计算机软件技术基础课程组38算法的特性与度量(5

)算法的执行效率时间复杂度假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：称T(n)为算法的(渐近)时间复杂度算法的渐进分析就是要估计，当数据规模n逐步增大时，资源开销T(n)的增长趋势

从数量级大小的比较来考虑，当n增大到一定值以后，资源开销的计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都是可以忽略的T(n)=O(f(n))数据结构——概述2007东北大学网络学院

计算机软件技术基础课程组39算法的特性与度量(6)算法的执行效率如何估算算法的时间复杂度算法的执行时间与原操作执行次数之和成正比算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的

执行次数×原操作(i)的执行时间∑数据结构——概述2007东北大学网络学院计算机软件技术基础课程组40算法的特性与度量(7)算法的执行效率例1：NXN矩阵相乘for(i=1;i<=n;i++)n+1for(j=1;j<=n;j++)n*(n+1){c[i][j]=0;n*nfor

(k=1;k<=n;k++)n*n*(n+1)c[i][j]+=a[i][k]*b[k][j];n*n*n}T(n)=2n3+3n2+2n+1=O(n3)33)(nOnTnnf数据结构——概述2007东北大学网络学院计算机软件技术基础课程组41算法的特性与度量(7)算法的执行效率

结论随着n值的增大，增长速度各不相同，存在下列关系当f(n)为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当f(n)为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法慢O(1)常量阶O(n)线性阶O(logn)对数阶O(n2

)平方阶O(nk)多项式阶快O(2n)指数阶