第一章整理ppt.ppt

数 据 结 构,福建工程学院计算机与信息系 刘建华 jhliufjnu.edu.cn 博士 副教授,本课程的介绍及要求,本课程意义、重要性及特点 难点：基础问题（C要求）、教材问题（错误多） 掌握要求（层次）：思想方法、数据结构类型表达、算法代码 本课程要求： 平时要求 (上课、作业、实验及重视性) 考试要求： 平时（30%+70%）,第一章 概 论,本章知识点： 什么是数据结构 数据结构的重要性 基本概念和基本术语 什么是算法 算法性能的度量,本章学习要求： (1) 了解数据结构在计算机学科中的地位和重要性。 (2) 掌握数据结构的概念及其与数据类型的区别。 (3) 掌握算法的概念和算法的复杂度分析方法。,1.1 什么是数据结构,什么是信息？ 什么是数据？ 什么是程序？ 什么是算法？,不要是死记概念， 主要是意会，从计算机学科理解,重点：理解什么数据?,1.1 什么是数据结构,基本概念和术语 数据(Data):是对信息的一种符号表示。 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 在有些情况下，数据元素也称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项组成。 数据项是数据的不可分割的最小单位。,1.1.1 基本概念和术语,数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 例如， 整数数据对象是集合N=0，±1，±2，±3， 但计算机中的整数数据对象集合N1应该是上述集合N的一个子集，N1=0，±1，±2，±maxint，其中maxint是依赖于所使用的计算机和语言的最大整数。,什么是数据结构 程序 =数据结构+算法,程序处理的对象及其它们之间的关系,两个元素、一个问题,例1 书目自动检索系统,书目文件,对象之间的关系：线性关系,例2 人机对奕问题,对象是什么？棋局,对象关系是什么？,多叉路口交通灯管理问题,对象是什么？通路,对象关系是什么？,着色：颜色尽可能少,数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,按某种逻辑关系组织起来的数据集合， 按一定存储表示方式存储在计算机存储器中， 并在这些数据上定义一个运算的集合， -数据结构内容。,数据,结构,数据结构,信息是人们对现实世界中各种事物的描述，计算机是一门研究如何用计算机对信息进行表示和处理的学科。信息在计算机中的表示及其组织结构又直接影响甚至决定了计算机对信息的处理。随着计算机应用技术的发展，需要计算机表示和处理各种各样的多媒体数据，许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须研究分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课程所要研究的问题。通过学习它，也将为计算机专业后续课程（如软件工程、编译原理和操作系统等）的学习打下坚实的基础。,数据结构看成是带结构的数据元素的集合，其一般包括以下三个方面内容： （1）数据元素之间的逻辑关系，即数据的逻辑结构。 （2）数据元素及其关系在计算机存储器中的存储实现 （3）施加在该数据上的操作，即数据的运算。,1.1.1 基本概念和术语,对于数据元素互相之间的逻辑关系，我们称为数据的逻辑结构。 数据的逻辑结构主要有以下4类（参见图1.1）：,根据数据元素间关系的基本特性，有四种基本数据结构 1.（集合）数据元素间除“同属于一个集合”外，无其它关系 2.线性结构一个对一个，如线性表、栈、队列 3.树形结构一个对多个，如树 4.图状结构多个对多个，如图,四种基本数据结构,数据的存储结构,什么是存储结构 数据结构在计算机中的存储表示（又称映射）称为数据的物理结构，即数据的存储结构。 其包含数据元素的表示和关系的表示。,存储结构,种基本的存储映射方法。 1顺序存储方法:顺序存储主要应用于线性的数据结构的物理存储。对于非线性的数据结构，则要通过某种线性化的方法来实现其顺序存储。 其优缺点 2链式存储方法：物理上不相邻，采用指针来指向 3索引存储方法 4哈希（或散列）存储方法 与前三种存储方法不同的是，哈希存储方法不存储结点之间的逻辑关系,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,1.1.3 数据结构与数据类型,数据结构 不仅要描述数据类型的数据对象， 而且要描述数据对象各元素之间的相互关系。 数据结构的形式定义为： 数据结构是一个二元组 Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 举例说明 【例1.2】 复数的数据结构定义 (见书),1.1.3 数据结构与数据类型,存储结构是数据结构不可缺少的一个方面： 同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 （理解两个概念） 例如 线性表是一种逻辑结构， 若采用顺序存储方法的存储表示，称为顺序表； 若采用链式存储方法，称为链表；,1.1.3 数据结构与数据类型,数据的运算也是数据结构不可分割的一个方面。 按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。 例如 对线性表（顺序表或链表）限定插入、删除操作只在表的一端进行，则该线性表称之为栈； 若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。,1.1.3 数据结构与数据类型,所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。 例如 C语言中的整型数据，其值为某个区间内的整数（和机器有关），定义在其上的操作为加、减、乘、除等算术运算。 意会： 分为：系统定义，自定义？（原子类型、结构类型）,1.1.3 数据结构与数据类型,数据类型可分为 原子类型（如C语言中的实型、字符型等） 结构类型（如C语言中的数组、结构体等）两种。 数据结构是指计算机处理的数据元素及其组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。,1.2 为什么要学习数据结构,1.2.1 数据结构的重要性 “数据结构”在计算机科学中是一门综合性的专业基础课。 “数据结构”与解决现实世界中的“非数值计算问题” 拥有良好数据结构和算法的功能函数或函数块也是整个软件质量的根本保证。,1.2 为什么要学习数据结构,1.2.2数据结构的一个应用例子 编写一个查询某个城市或单位的私人电话号码的程序。程序功能要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码信息；否则指出该人没有电话号码。 分析 要解决此问题首先构造一张电话号码登记表（如表1-1所示的某市电话号码表）。,1.2.2数据结构的一个应用例子,表1-1 某市电话号码表,图1-2 采用索引存储的电话号码表,通过对比表1-1和图1.2可知，实现高效的电话号码表检索功能是 建立在有序（或部分有序）的电话号码表和附加的姓氏索引表基础上的。,1.3算法和算法分析,1. 什么是算法 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它以零个或多个值作为输入，并产生一个或多个值作为输出。,2. 算法具有以下五个明显的特性： （1）有穷性 （2）确定性 （3）可行性 （4）输入 （5）输出 算法设计的要求:正确性 ,可读性 ,健状性 ,效率与存储量需求,3. 算法与程序 : 首先，一个程序不一定满足有穷性，因此它不一定是算法。 其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限制。,1.3算法和算法分析,1.3.2 算法的度量 算法首先应该是“正确”的。其次，主要考虑如下三点： （1）执行算法所耗费的时间； （2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间； （3）算法应当易于理解，易于编码，易于调试等等,设计算法时只能根据具体情况有所侧重。 对一个算法要作出全面的分析可分成两个阶段进行，即事先分析和事后测试 。 事先分析：求出该算法的一个时间界限函数。 事后测试：收集此算法的执行时间和实际占用空间的统计资料。,算法的时间复杂度分析,所以算法的时间复杂性是输入数据量n的函数，这时就称该算法的时间代价为T（n）。,算法的时间复杂度分析,一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度记作： T(n)=O(f(n)，称作算法的渐近时间复杂度，简称算法的时间复杂度。,选取算法一种基本操作, 时间复杂度：基本操作重复执行的次数的阶数 问题规模的某个函数f(n). 算法的时间量度为:T(n)=o(f(n),例1：N阶方阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; /乘法运算是基本操作,最深层循环内的语句的原操作 语句重复执行的次数-频度 例 (a)+x;s=0; O(1) (b) for(i=1;i=n;+i) +x;s+=x; O(n) (c) for(j=1;j=n;+j) O(n2) for(k=1;k=n;+k) +x; s+=x; ,数据结构中常用的时间复杂度频率计数,时间复杂度频率计数有7个： O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型,按时间复杂度由小到大递增排列成表1-3（当n充分大时）。,算法的空间复杂度分析,与算法的时间复杂度类似，可以定义算法的空间复杂度如下：如果存在正的常数M和n0，当问题的规模nn0后，算法的空间量度S（n）M·f(n)，那么就称该算法的空间复杂度为O（f(n)）。 一个执行程序，除了需要存储空间来寄存本身所用的指令、常数、变量和输入数据以外，也需要一些对数据进行处理的工作单元和存储一些为实现计算机所需信息的辅助空间。,