数据结构-第一章绪论.ppt
数据结构,教材:数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社 计算机科学与技术学院,本课程讲述的主要内容：分别讲述数据结构的基本概念、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序等内容。学习本课程的基本方法：,上课认真听讲；仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；独立完成每个章节的练习题和作业题。,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析,第一章 绪论,1.1 什么是数据结构,著名计算机科学家、Pascal语言发明者N.沃思教授提出：程序=算法+数据结构 程序:处理问题编制一组指令集 算法:处理问题的策略数据结构:问题的数学模型也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。,数值计算的程序设计问题：例如：结构静力分析计算 线性 代数方程组 预报人口增长情况 微分方程,例1 书目自动检索系统,书目文件,算法：需要检索的书目？如何检索？用户界面？模型：？,非数值计算的程序设计问题：,例2 人机对奕问题,算法：对奕的规则 和策略模型：？,教学计划编排问题,算法：如何确定课程的次序关系?模型：？,数据结构研究的主要内容：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。,数据（data)所有能被输入到计算机中，且被计算机处理的符号的集合，是计算机操作的对象的总称。数据元素（data element）是数据的基本单位，由若干个数据项组成，也称结点、元素、顶点或记录。数据项（data item）是数据的不可分割的最小单位，有时也称为域（field），即数据表中的字段。数据对象(data object)：性质相同的数据元素的集合，是数据的一个子集。如大写字母字符数据对象是集合C=A,B,C,，Z，整数数据对象是集合 N=0,1,2,1.2 基本概念和术语,数据结构(data structure)：是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。,例：一个含12位数的十进制数可以用三个4位的十进制数表示 3214,6587,9345 a1(3214),a2(6587),a3(9345)在a1、a2和a3 之间存在“次序”关系 a1,a2、a2,a3 a1 a2 a3 a3 a2 a1,数据结构的形式定义：数据结构是一个二元组 Data-Structure=（D，S）其中：D是数据元素的有限集，S是D上关系的有限集。,例：在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex=（C，R）其中，C是含两个实数集合c1，c2；R=P，P是定义在集合C上的一种关系，其中有序偶表示c1是复数的实部，c2是复数的虚部。,数据的逻辑结构只抽象反映数据元素的逻辑关系。数据的存储（物理）结构数据的逻辑结 构在计算机存储器中的存储形式（或称映象）。元素/结点：用于表示数据元素的二进制位(bit)的位串。数据域：用于表示数据项的二进制位(bit)的位串。,例：（321）10（501）8（101000001）2 A（101）8（001000001）2,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;,1.3 抽象数据类型,抽象数据类型ADT（Abstract Data Type),定义：指一个数学模型以及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。,例：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型,数据结构+定义在此数据结构上的一组操作=抽象数据类型,描述方法形式定义：我们用一个三元组（D，S，P）来表示一个 抽象数据类型，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。格式：ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述 操作结果：操作结果描述,赋值参数引用参数，以“”打头,例：抽象数据类型三元组的定义：ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3Elemset 数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T，元素e1，e2和e3分别被赋以 参数v1,v2和v3的值。,DestroyTriplet（&T）操作结果：三元组T被销毁。Get（T,i,&e）初始条件：三元组T已存在，1=i=3.操作结果：用e返回T的第i元的值。Put(&T,i,e)初始条件：三元组T已存在，1=i=3.操作结果：改变T的第i元的值为e。IsAscending(T)初始条件：三元组T已存在。操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。,IsDescending(T)初始条件：三元组T已存在。操作结果：如果T的3个元素按降序排列，则 返回1，否则返回0。Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最小值。ADT Triplet,1.4 算法和算法分析,有穷性：对于任意一组合法输入值，在执行有穷步之后结束，即算法中的每个步骤都能在有限时间内完成；确定性：每条指令都有确切的含义，在任何条件下算法都只有一条执行路径；,算法五个重要特性：,算法：是对特定问题求解步骤的描述，是指令的有限序列。,可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；有输入：有零个或多个输入，取自特定的对象集合有输出：有一个或多个输出，是算法进行信息加工后得到的结果。,算法设计的原则正确性：在合理的数据输入下，能在有限的运算时间内得到正确结果；对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；,可读性：易于人对算法的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,高效率与低存储量需求：通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。,算法效率的衡量方法和准则 有两种衡量算法效率的方法:1.事后统计法：利用计算机内记时功能，用一组或多组相同的统计数据区分。2.事前分析估计法：求出算法的一个时间界限函数。,和算法执行时间相关的因素：算法选用的策略 问题的规模 编写程序的语言 编译程序产生机器代码质量 机器执行指令速度,时间复杂度：程序运行从开始到结束所需要的时间。设解决一个问题的规模为n，基本操作被重复执行的次数是n的一个函数 f（n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n)其中T(n)叫算法的渐进时间复杂度，简称时间复杂度。,算法控制结构+原操作（固有数据类型的操作）算法的执行时间原操作（i）的执行次数原操作（i）执行时间 从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法运行时间度衡量准则。,例1：NXN矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;,显然，被称做问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下是最深层循环内的语句中的原操作，它的执行次数和包含它的语句频度相同。,例2+x;s=0;例for(i=1;i=n;+i)+x;s+=x;例.for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;,T(n)=(1)常量阶,T(n)=O(n)线性阶,+x语句频度为：1+2+3+n-2=(n-1)(n-2)/2=(n2-3n+2)/2 T(n)=O(n2)平方阶,(1)(log2n)(n)(n2)(n3)(2n),例5：Void bubble-sort(int a，int n)for(i=n-1,change=TURE;i=1 change=TURE；,最好情况：0次最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为：O(n2),空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n)算法的存储量包括：（1）输入数据所占空间；（2）程序本身所占空间；（3）辅助变量所占空间。,注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。,算法的存储空间需求,
