数据结构动画版

1、下一章,第一章 绪言,1946年，第一台电子计算机ENIAC Shown here are two women “programming” ENIAC. U.S. Army Photo,什么是数据结构,系统功能分析,系统输入/输出数据、功能需求,设计合适的数据对象的表示结构,解决特定问题的具体步骤的描述,程序设计一般流程,程序设计：为计算机处理问题编制的一组指令集 数据结构：问题的数学模型 算 法：处理问题的策略,什么是数据结构,信息结构层次,求解策略层次,语言层次,从问题求解角度上，数据结构和高级程序设计语言（C语言）立足于不同的层面上 针对问题时，C语言一般要想该用何种控制结构（分支还是循

2、环）等细节问题； 而数据结构主要考虑的问题的描述、信息的结构等宏观问题 针对于问题的求解，算法立足于更高的层次: 与数据结构相比，它更多地考虑整个问题该用何种策略（思想）求解，而不是其中涉及信息的组织与结构 问题的一般求解过程为： 分析求解策略设计其中涉及信息的结构用语言加以具体实现,什么是数据结构,系统功能分析,程序设计一般流程,非数值计算问题,数值问题 例 已知：游泳池的长len和宽wide，求面积area 建模型：问题涉及的对象：游泳池的长len 宽wide，面积area；对象之间的关系：area=lenwide 设计 求解问题的方法 编程 main ( ) int len, wide

3、,area ;scanf (“%d %d%n”,什么是数据结构,书目文件,例1 书目自动检索系统,电话号码查询系统 学生成绩管理系统 职工信息系统 等文档管理的数学模型,例2 人机对奕问题,例2 人机对奕问题,例3 多叉路口交通灯管理问题,所有可能通行方向 AB AC AD BA BC BD DA DB DC EA EB EC ED 用AB表示AB，余类推,交叉路口的模型,算法设计： 穷举法：逐一检查所有可能组合，记录最小分组数和对应分组 贪心法：一类典型算法，其宗旨是根据当时掌握的信息，尽 可能地向得到解的方向推进,例3 多叉路口交通灯管理问题,例3 多叉路口交通灯管理问题,例3 多叉路口交

4、通灯管理问题,例3 多叉路口交通灯管理问题,例3 多叉路口交通灯管理问题,是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,数据结构定义,数据结构学科的地位 综合性的专业基础课 介于数学、计算机硬件和计算机软件之间的核心课程 不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 本课程的先修课程：离散数学、C语言(或其他程序设计语言) 本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等,数据（data)所有能输入到计算机中去的描述客观事物的符号,数据元素（data elem

5、ent）数据的基本单位，也称结点（node）或记录（record） 数据项（data item）有独立含义的数据最小单位，也称域(field,数据对象（data object)性质相同数据元素的集合,整数数据对象 N = 0, 1, 2,基本概念和术语,数据结构（data structure)数据元素和数据元素关系的集合 Data_Structure = D, R,数据的逻辑结构只抽象反映数据元素的逻辑关系,从逻辑关系上描述数据，与数据的存储无关 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关,基本概念和术语,数据的存储（物理）结构数据的逻辑结构在计

6、算机存储器中的实现,索引存储结构 散列存储结构,基本概念和术语,元素n,元素i,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(元素i)=Lo+（i-1)*m,顺序存储结构,基本概念和术语,1536,元素2,1400,元素1,1346,元素3,元素4,1345,链式存储结构,h,基本概念和术语,基本概念和术语,数据类型一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称,例 C语言中，提供int, char, float, double等基本数据类型， 数组、结构体、共用体等构造数据类型， 还有指针、空(void)类型等。 用

7、户也可用typedef 自己定义数据类型,typedef struct long num; char name30; char author20; char publisher30; float price; BOOKCARD; BOOKCARD book1,book2,*p,一些最基本数据结构可以用数据类型来实现，如数组、字符串等 另一些常用的数据结构，如栈、线性表、树、图等，不能直接用数据类型来表示,基本概念和术语,数据结构和数据类型的关系 “数据结构”是数据类型的抽象； “数据类型”是数据结构在计算机内部的具体表现,Abstract Data Type,ADT,定义：ADT是指一个数学模

8、型和定义在该模型上的一组操作的总称 由用户定义,从问题抽象出来的数据模型数据逻辑结构 还包括定义在数据模型上的一组抽象运算相关操作 不考虑其在计算机内具体存储结构与运算的具体实现算法 优点：信息隐蔽和数据封装，使用与实现相分离,使用者只要知道这些操作的用途就可以编程序了；至于这些操作是怎样实现的，以及它在内存中是如何表示的，并不影响使用者所编程序的编码形式,ADT两个重要特征： 数据抽象：用ADT描述程序处理的实体时，强调其本质特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法） 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型,AD

9、T形式化定义,ADT=（D，S，P） D=数据对象 S=D上的关系集 P=对D的基本操作集,ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,基本操作定义格式： 基本操作名(参数表) 初始条件： 操作结果,赋值参数：只为操作提供输入值 引用参数：以 float imag; Complex,基本操作的函数原型说明 void AssignComplex(Complex,基本操作的实现 void AssignComplex(Complex,ADT实现举例,ADT定义与实现的关系,预定义常量和类型： #define TURE 1 #define FALSE 0 #de

10、fine OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status,ADT实现中几个问题,引用运算符： /*a为普通的整型变量*/ int /*b是a的引用变量*/ b变量是变量a的引用,b也等于4,这两个变量同步改变,注意：C语言不支持引用类型,ADT实现中几个问题,关于引用,引用常用于函数形参中,采用引用型形参时,实现数据双向传递,例如,ADT实现中几个问题,关于引用,void swap(int x, int y) int temp; temp=x; x=y; y=temp;,当用执行

11、语句swap(a,b)时： a 和b的值没有发生交换,值传递,引用常用于函数形参中,采用引用型形参时,实现数据双向传递,例如,ADT实现中几个问题,关于引用,void swap(int *x, int *y) int temp; temp = *x; *x= *y; *y=temp;,当用执行语句swap( while(n%2=0) n=n+2; printf(“%dn”,n);,void exam2() int y=0; int x=3/y; printf(“%d,%dn”,x,y);,违反了有穷性,违反了可行性,这两段描述均不能满足算法的特征,试问它们违反了哪些特征,算法特性,In nat

12、ural languages, like English or Chinese Flow charts Pseudo-code Programming languages, like C or Java,Recipe: CHOCOLATE CAKE 4 oz. chocolate 3 eggs 1 cup butter 1 tsp. vanilla cups sugar 1 cup flour Melt chocolate and butter. Stir sugar into melted chocolate. Stir eggs and vanilla Mix in flour Sprea

13、d mix in greased pan Baked at 350 for 40 minutes or until inserted fork comes out almost clean Cool in pan before eating,Program Code Declare variables Chocolate eggs mix butter vanilla sugar flour mix=melted (4*chocolate) +butter) mix=stir(mix+(2*sugar) mix=stir(mix+(3*eggs)+vanilla) mix=mix+flour

14、spread(mix) while( not clean(fork) bake(mix, 350,算法描述,Descriptions,衡量算法优劣的标准 正确性(Correctness) 可读性(Readability) 健壮性(Robustness) 效率(Efficiency,灵活性（Flexibility） 可重用性(Reuseable) 自适应性(Adaptability)等,健壮性: 1、指当输入数据 非法时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。 2、处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理

15、,可读性： 1、算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解； 2、另一方面，晦涩难读的算法易于隐藏较多错误而难以调试,正确性：有四个层次 1、程序中不含语法错误； 2、程序对于几组输入数据能够得出满足要求的结果； 3、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 4、程序对于一切合法的输入数据都能得出满足要求的结果。 通常以第三层意义上的正确性作为衡量一个算法是否合格的标准,算法评价,Evaluation,例1：在有序表中查找给定值,例2：百钱买百鸡问题,自顶向下，逐步求精,算法设计重要性,举例：数组a中存放从小到大排好序的

16、n个整数，查找给定值k在数组中下标；若查找失败，返回-1,方法一：顺序查找,int Search(int a,int n,int k) int i=0; while( ) i+; if(i=n) return(-1); else return(i);,找64,最多比较 次,查找成功,n,ai!=k, in,方法二：折半查找,找37,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,查找成功,方法二：折半查找,找90,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,查找失败,7,最多比较log2n 1 次,in

17、t BiSearch(int a,int n,int k) int low,high,mid,found; low=0; high=n-1; found=0; while( ) if(kamid) else if(k=amid) else if(found=1) return(mid); else return(-1);,low=high) i=100; i+) for(j=0; j=100; j+) for(k=0; k=100;k+) if(k%3 = = 0,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需

18、要解出本方程就可以得到答案,循环次数=101*101*101 即约一百万次,方法2用二重循环：k=100-i-j for(i=0; i=100; i+) for(j=0; j=100; j+) k=100 i j ; if(k%3 = = 0,循环次数=101*101 即约一万次,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案,方法3用二重循环：钱100元，母

19、鸡5元1只，所以i=20， 同样，j=33 for(i=0; i=20; i+) for(j=0; j=33; j+) k=100 i j ; if(k%3 = = 0,循环次数=21*34=714,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案,方法4用一重循环：合并方程得到:14*i+8*j = 200 简化为: 7*i+4*j=100 所以有：i=14

20、又： j=25-7*i/4 ，故i必为4的倍数 for(i=0; i=14; i+4) j = (100 7*i)/4; k=100 i j ; if(k%3 = = 0,循环次数=4,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案,1.事后统计利用计算机内记时功能，用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、

21、软件等环 境因素，掩盖算法本身的优劣,2.事前分析估计程序在计算机上运行所消耗 的时间取决于： 算法策略 问题规模 程序语言 编译质量 计算机速度,算法时间效率度量方法,渐近）时间复杂度：算法耗用时间相对问题规 模的增长率 定义：设n是问题规模,T(n)和f(n)是n的函数，当且仅当存在正整数c和n0,使得对所有n n0 ，满足T(n)cf(n),则T(n)称作 大O表示法：T(n)=O(f(n,加法规则(顺序连接)与乘法规则(嵌套连接,1、O(f(n)+O(g(n) = O( max(f(n),g(n) 2、O(cf(n) = O(f(n), c是正整数 3、O(f(n)*O(g(n) =

22、O( f(n)*g(n,Asymptotic time complexity,算法时间效率度量方法,T1(n) = O(1,T2(n) = O(n,T3(n) = O(n2,T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2,频度最大语句重复执行次数的阶数,算法时间效率度量方法,例：两个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;,算法时间效率度量方法,渐近）时间复杂度：基本操作重复执行的次数的阶数（算法耗用时间的增长率 ） 大O表示法：T(n)=O(f(n,渐近）空间复杂度：S(n)=O(f(n,加法规则与乘法规则,最坏情况 最好情况 平均情况,常用时间复杂度： O(1)-常量型 O(n)、 O(n2)、 O(n3)-多项式型 O(log2n)、 O(nlog2n)-对数型 O(2n) 、O(en)-指数型,Asymptotic space complexity,辅助存储空间增长率,算法存储量包括： 输入数据所占空间 程序本身所占空间 辅助变量所占空间,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查