《数据结构》PPT课件.ppt

数据结构,严蔚敏 吴伟民 编著,课程内容： 计算机软件的基础知识数据结构 课时安排： 周二晚上上机锡昌科技楼402 周四1、2节（单周）锡昌科技楼505 周五下午锡昌科技楼505,第1章 绪言, 1.1 什么是数据结构 1.程序=数据结构+算法 2 .例子：例1 图书馆的书目检索自动化系统,书目文件,例2 计算机和人对奕问题,例3 多叉路口交通灯管理问题,（a）五叉路口,（b）表示通路的图,3 .数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,4.数据结构所处的地位： 它是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 在计算机科学中，它不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它程序和大型应用程序的重要基础。, 1.2 基本概念和术语 1 .数据元素和数据项： 1)数据（data)是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2)数据元素（data element）数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素又为元素、结点、顶点或记录。 3)数据项（data item）是数据不可分割的最小单位。通常作为数据元素的分量，数据项又称为字段或域。 2 .数据的数据结构（data structure）相互之间存在一种或多种特定关系的数据元素的集合。,2）数据结构的形式定义：一个二元组Data_Structure(D,S) 其中：D是数据元素的有限集，S是D上关系的有限集。,3.数据的逻辑结构: 1)逻辑关系-数据元素间的关联方式或称邻接关系。 2)逻辑结构-数据元素间逻辑关系的整体。它只抽象反映数据元素的逻辑关系。,4.数据的存储（物理）结构数据的逻辑结构在计算机 存储器中的实现。,5.数据类型一个值的集合和定义在这个值集上的一组操作的总称。(操作是指数据结构上需要或能够进行的处理。) 原子类型非结构。例如C语言中的整型等基本类型 数据类型 结构类型可以分解，成分可以是结构、非结构。例如数组,6.抽象数据类型一个数学模型以及定义在该模型上的一组操作。 1）抽象数据类型 :原子类型不可分解。 固定聚和类型其值由确定数目的成分按某种结构组成。例如复数 可变聚和类型“值”的成分的数目不确定。例如可定义“有序整数序列”的抽象数据类型，其中序列的长度是可变的。 2）抽象数据类型的形式定义：一个三元组Data_Structure(D,S，P)其中：D是数据对象，S是D上关系集，P是对D的基本操作集。,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,例 C语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,13 抽象数据类型的表示与实现（略）,14 算法和算法分析 1.4.1算法的概念 ：算法是特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。 算法具有以下重要特性：,算法的描述采用C语言算法的评价 1.4.2.算法设计的要求衡量算法优劣的标准 1)正确性(correctness)应满足具体问题的需求。 2)可读性(readability)为了人的阅读和交流。 3)健壮性(robustness)输入非法数据也能适当地作出反应或进行处理。 4)效率与低存储量高效率低存储,1.4.3.算法效率的度量：算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适,估算时间复杂度的方法 ：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 。,3.渐近时间复杂度（时间复杂度）：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度，简称时间复杂度。,例1：NXN矩阵相乘，计算以下算法的时间复杂性。 procedure matri(var A,B,C:ARRAY1.N,1.NOF integer); /求n阶方阵A、B的乘积C / begin 1.for i:=1 to n do 2.for j:=1 to n do 3. Ci,j:=0； 4.for k:=1 to n do Ci,j:=Ci,j+Ai,k*bk,i end 计算方法1：由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3 故时间复杂度为T(n)=O(n3)。 计算方法2：由于“乘法”运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，故时间复杂度为T(n)=O(n3)。,4.频度：是指该语句重复执行的次数。频度与问题的基本操作执行次数相同，故时间复杂度可通过频度来计算。 例 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1) 即常量阶。 例、for(I=1;I=n;+I) +x;s+=x; 将x自增看成是基本操作，则语句频度为：n其时间复杂度为：O(n) 即时间复杂度为线性阶。,例、for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x; 将x自增看成是基本操作，则语句频度为：n2,其时间复杂度为：O(n2) 即时间复杂度为平方阶。 (补充)定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)（证略）。 例for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x;ai，j=x; 语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 时间复杂度为O(n2) 即此算法的时间复杂度为平方阶。,一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a ，int n) /将a中整数序列重新排列成自小到大有序的整数序列。 for(I=n-1;change=TURE;I1 change=TURE 当a中初始序列为自小到大有序时，基本操作的执行次数为0，故最好情况：0次。 当a中初始序列为自大到小有序时，基本操作的执行次数为1+2+3+n-1 =n(n-1)/20，故最坏情况的时间复杂度为:O(n2),1.4.4算法的存储空间需求 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小),作业：一、书面作业：1.1,1.8 二、上机作业：P10 1.16 上机作业要求：P83 三、交书面和上机作业时间：第二周星期五下午,