浙江工商大学数据结构课件

主讲教师：吴海燕[e-mail]数据结构第一课课程内容：–计算机软件的基础知识———数据结构课时安排：–课堂——16*4=64学时–上机——单开数据结构实验课教材：–数据结构(C语言版）浙江大学出版社第一章绪言•1.1什么是数据结构程序=数据+算法–例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表–例2人机对奕问题树……..……..…...…...…...…...–多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图–数据结构定义:是一门研究程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科•1.2基本概念和术语–数据（data)—所有能输入到计算机中去的描述客观事物的符号–数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）–数据项（dataitem）—有独立含义的数据最小单位，也称域(field)–数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图–数据的逻辑结构—只抽象反映数据元素的逻辑关系–数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：中国科大《数据结构》1-121.3数据类型和抽象数据类型数据类型：是一个值的集合和定义在这个值集上一组操作总称。分类：(按值的不同特性)原子类型：每一个对象仅由单值构成的类型；结构类型：每一个对象可由若干成分按某种结构构成的类型。中国科大《数据结构》1-13抽象数据类型ADT（AbstractDataType）作用：抽象数据类型可以使我们更容易描述实际问题。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。好处：可提高软件的复用程度。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。抽象数据类型中国科大《数据结构》1-14抽象数据类型表示法表示方法：三元组表示：（D，S，P）其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。标准定义格式：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名中国科大《数据结构》1-15名称线性表解释数据对象D={ai|ai(-ElemSet,i=1,2,...,n,n=0}任意数据元素的集合数据关系R1={ai-1,ai|ai-1,ai(-D,i=2,...,n}除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(L,i,e)L为线性表，i为位置，e为数据元素。ListDelete(L,i,e)...例：线性表的表示中国科大《数据结构》1-16算法的概念建立在数据结构基础上的、求解问题的一系列确切的步骤。算法的五个特性有穷性：对任何合法输入执行有穷步后能结束。确定性：每条指令必须有确切的含义。可行性：算法的每一条指令均能执行。输入：有零个或多个输入。输出：有一个或多个输出。算法和程序的关系两者相似而又有区别。程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。1.4算法和算法分析中国科大《数据结构》1-17正确性(Correctness)算法应满足具体问题的需求对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。健壮性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果。高效性(Efficiency)效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。时间复杂度和空间复杂度都与问题的规模有关。评价算法优劣的基本标准中国科大《数据结构》1-18算法效率的度量事后统计的方法：求出该算法的一个时间界限函数；事前分析估算的方法；要考虑以下的因素：问题的规模；编写程序时所用的程序设计语言；机器的速度；算法所用的策略。渐近时间复杂度（时间复杂度）：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作T(n)=O(f(n))称作算法的渐近时间复杂度，简称时间复杂度。频度：是指该语句重复执行的次数。频度与问题的基本操作执行次数相同，故时间复杂度可通过频度来计算。估算时间复杂度的方法：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。中国科大《数据结构》1-19时间复杂度n问题规模，一般为数据的输入量f(n)算法中基本操作重复执行的次数—频度是问题规模n的某个函数算法的时间量度、时间复杂度算法中各语句的频度之和T(n)T(n)=O(f(n))随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同O的含义存在正的常数c和n0，使得当nn0时，0T(n)c*f(n)中国科大《数据结构》1-20渐近复杂度的数学定义定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳，则称函数f(n)当n充分大时有上界，且g(n)是它的一个上界，记为f(n)=O(g(n))此时，可以说f(n)的阶不高于g(n)。大O标记法的几个性质：（1）O(f(n))+O(g(n))=O(max(f(n),g(n)))(2)O(f(n))+O(g(n))=O(f(n)+g(n))(3)O(f(n))O(g(n))=O(f(n)g(n))(4)O(cf(n))=O(f(n))(5)f(n)=O(f(n))中国科大《数据结构》1-21时间复杂度计算例1：x++;s=0;用频度法分析：将x++看成是基本操作，语句频度为１T(n)=2算法的时间复杂度：O(1)---常量阶例2:for(i=0;in;i++){//执行n+1次x++;//语句频度为：ns+=x;//语句频度为：n}T(n)=2n+n+1=3n+1，则时间复杂度为：O(n)也可以这样考虑：将x自增看成是基本操作，则语句频度为：n其时间复杂度为：O(n)，即时间复杂度为线性阶。中国科大《数据结构》1-22例3:矩阵相乘C=AxBfor(i=0;in;i++)//n+1for(j=0;jn;j++){//n*(n+1)c[i][j]=0;//n2for(k=0;kn;k++)//n2*(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}T(n)=2n3+3n2+2n+1算法的时间复杂度：O(n3)计算方法1：由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3故时间复杂度为T(n)=O(n3)。计算方法2：由于“乘法”运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，故时间复杂度为T(n)=O(n3)。时间复杂度计算中国科大《数据结构》1-23例4:分析以下程序段的时间复杂度i=1;//语句频度为：１while(i=n)i=i*2//语句频度为：f(n)因为：２f(n)≤n，即：f(n)≤log2n，取最大值f(n)=log2n，则该程序的时间复杂度为：T(n)=1+f(n)=1+log2n=O(log2n)时间复杂度计算中国科大《数据结构》1-24时间复杂度计算补充)定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)（证略）。例５for(i=2;i=n;++i)for(j=2;j=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=(n2-3n+2)/2∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。中国科大《数据结构》1-25时间复杂度计算算法中基本操作重复执行的次数随问题的输入数据集不同而不同例6：在数组A[n]查找给定值K(1)i=n-1;(2)while(i=0&&A[i]!=K)(3)i=i-1;(4)RETURN(i);最好情况的时间复杂度T(n)=O(1)最坏情况的时间复杂度T(n)=O(n)平均时间复杂度：所有可能的输入实例以等概率出现的情况T(n)=(1+2+...+n)/n算法的时间复杂度：O(n)中国科大《数据结构》1-26时间复杂度按数量递增排列及增长率一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)指数时间的关系为：O(nk)O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。*Figure1.8:Plotoffunctionvalues(p.39)nlognnlogn*Figure1.9:Timesona1billioninstructionpersecondcomputer(p.40)中国科大《数据结构》1-29空间复杂度(TimeComplexity)类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作：S(n)=O(f(n))其中n为问题规模的大小。主要包括三个部分：（1）输入数据所占用的空间。（2）程序本身所占用的空间。（3）辅助变量所占用的空间。存储密度d=数据本身存储量/实际所占存储量MoreExamples•Example:sum1=0;for(k=1;kn;k*=2)for(j=1;j=n;j++)sum1++:sum2=0;for(k=1;k=n;k*=2)for(j=1;j=k;j++)sum2++;课后练习•什么是算法？•什么是时间复杂度，空间复杂度？•什么线性问题，非线性问题•如何理解树，图结构•认真回顾书上例子