哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).

1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析本章重点难点重点:①数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系；②抽象数据类型(ADT)的概念和实现方法，算法的时间复杂性和空间复杂性分析。难点:①抽象数据类型(ADT)的概念和实现方法；②算法的时间复杂性和空间复杂性分析。1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1数据结构及其讨论范畴算法+数据结构=程序设计处理问题的策略给出问题的数学模型编制出用计算机处理问题的指令问题构建数学模型算法实现①在解决问题时可能遇到的典型的逻辑结构（数据结构）②逻辑结构的存储映象（存储实现）③数据结构的相关操作及其实现。数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。第1章绪论1.1数据结构及其讨论范畴例1求n个整数中的最大值。例2交叉路口的红绿灯管理。例3煤气管道的铺设问题。……说明：例子中的数学模型正是数据结构要讨论的问题。第1章绪论1.1数据结构及其讨论范畴例计算机的发展数据处理的种类数据数值数据非数值数据数(整数,实数)字符字符串文字图形图象声音对客观对象的符号表示程序原始数据结果数据第1章绪论1.1数据结构及其讨论范畴软件硬件应用领域数值问题与非数值问题①数值问题例1已知：游泳池的长len和宽wide，求面积area设计求解问题的方法编程建模型：问题涉及的对象：游泳池的长len宽wide，面积area；对象之间的关系：area=lenwide第1章绪论1.1数据结构及其讨论范畴学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机100202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机3②非数值问题已知某级学生情况,要求分班按入学成绩排列顺序。说明：在此类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,该数学模型称为线性模型。第1章绪论1.1数据结构及其讨论范畴例②非数值问题第1章绪论1.1数据结构及其讨论范畴下棋程序--国际象棋：每次需要考虑的合乎规则的着法平均只有35步回合，计算机预先分析7至8个回合的着法。若设为7个回合，则有超过1亿亿亿个不同的变化，经简化后，仍有500亿至600亿个变化。多分析一步，增加18亿个变化。根据计算机“深蓝”的速度，平均5分钟走一步。算法：对弈的规则和策略棋盘及棋盘的格局模型：根据计算机“深蓝”的速度例迷宫问题：在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”。入口出口第1章绪论1.1数据结构及其讨论范畴例第1章绪论1.1数据结构及其讨论范畴对每种数据结构，主要讨论如下三方面的问题：①数据的逻辑结构数据元素之间的逻辑关系，是具体关系的抽象。②数据的存储结构(物理结构)：数据元素及其关系在计算机内存中的表示；③数据的运算即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。1.1数据结构及其讨论范畴1.2基本概念和术语1.3数据结构的分类及表示1.4抽象数据类型的表示与实现1.5算法和算法分析数据：是信息的载体，能够被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。数据项:相当于记录的“域”或字段,是数据不可分割的最小单位。如学号。数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。第1章绪论1.2基本概念和术语数据结构类型树图第1章绪论1.2基本概念和术语数据结构是数据之间的相互关系，即数据的组织形式。线性表栈队列串数组广义表数据结构线性结构非线性结构①线性结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继；②非线性结构：其逻辑特征是一个结点可能有多个直接前驱和直接后继；第1章绪论1.2基本概念和术语数据的逻辑结构学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员001003002004006005008007学生间学号顺序关系是一种线性结构关系第1章绪论学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治、面貌，表中的记录是按学生的学号顺序排列的。1.2基本概念和术语例家族的族谱:假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE第1章绪论1.2基本概念和术语例①顺序存储方法：数组②链接存储方法：指针③索引存储方法④散列存储方法说明：•同一逻辑结构的不同存储结构，冠以不同的数据结构名称。如顺序表、链表、散列表。•运算不同，数据结构也不同。如栈和队列。更进一步，顺序栈、链栈、顺序队列、链队列。第1章绪论1.2基本概念和术语数据的存储结构算法：数据运算的描述数据结构：数据的逻辑结构和存储结构算法+数据结构=程序第1章绪论1.2基本概念和术语1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析抽象数据型AbstractDataTypes（ADT）[定义]：抽象数据型是一个数学模型和在该模型上定义的操作的集合ADT特点：•降低了软件设计的复杂性；•提高了程序的可读性和可维护性；•程序的正确性容易保证第1章绪论1.3抽象数据类型的表示与实现在软件设计中，可以对哪三种不同的对象进行抽象？第1章绪论1.3抽象数据类型的表示与实现第1章绪论1.3抽象数据类型的表示与实现软件系统数据结构控制机能操作过程软件设计抽象软件设计是对数据抽象、过程抽象和控制抽象。抽象数据型的规格描述完整性：反映所定义的抽象数据型的全部特征；统一性：前后协调，不自相矛盾；通用性：适用于尽量广泛的对象；不依赖性：不依赖于程序设计语言。语法：给出操作的名称、I/O参数的数目和类型；语义：由一组等式组成，定义各种操作的功能及相互之间的关系；规格描述的两个方面:语法和语义第1章绪论1.3抽象数据类型的表示与实现抽象描述→（高级语言）编写的程序三条原则：①符合规格描述的定义；②有尽可能好的通用性；③尽可能独立于程序的其它部分自底向上与自顶向下相结合、由简单到复杂第1章绪论1.3抽象数据类型的表示与实现抽象数据型的实现多层次抽象技术抽象数据类型的形式描述ADT=(D，S，P),其中：D是数据对象;S是D上的关系集;P是D的基本操作集。第1章绪论1.3抽象数据类型的表示与实现数据类型和抽象数据类型①抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现；②抽象数据类型的实现包括数据结构的实现和操作的实现。第1章绪论1.3抽象数据类型的表示与实现抽象数据类型“复数”的定义为：ADTComplex{数据对象：D={e1,e2|e1,e2属于RealSet}数据关系：R1={e1,e2|e1是复数的实部，e2是复数的虚部}其中用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。例设计函数DELEVAL（LIST&L,elementtyped)，其功能为删除L中所有值为d的元素。VoidDELEVAL(LIST&L,elementtyped){positionp;p=FIRST(L);while(P!=END(L)){if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);}}第1章绪论1.3抽象数据类型的表示与实现例1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.4算法与算法分析算法（algorithm）的概念算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性关于本书采用的类语言描述：C或C++自然语言；程序设计语言；类语言。算法描述第1章绪论1.4算法与算法分析算法的基本特征有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定性：组成算法的操作必须清晰无二义性。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。输入：作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。在设计算法时通常应考虑以下原则算法必须是“正确的”所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。应有很好的“可读性”第1章绪论1.4算法与算法分析在设计算法时通常应考虑以下原则必须具有“健壮性”算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。算法的效率应考虑所设计的算法具有“高效率与低存储量”。高效率与低存储量是矛盾的，要视具体问题而定。第1章绪论1.4算法与算法分析影响时间特性的四个因素[定义]语句频度：语句重复执行的次数第1章绪论1.4算法与算法分析①程序运行时输入数据的总量;②对源程序编译所需的时间;③计算机执行每条指令所需的时间;④程序中指令重复执行的次数。所有算法均以函数形式给出,算法的输入数据来自参数表；参数表的参数在算法之前均进行类型说明；有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明描述算法的书写规则第1章绪论1.4算法与算法分析评价算法标准本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。O(n3)称为矩阵相乘算法时间复杂度；O(n3)表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；n阶矩阵相乘的算法For(i=1;i=n;i++)For(j=1;j=n;j++){c[i][j]=0;For(k=1;k=n;k++)c[i][j]+=a[i][k]*b[k][j]}乘法加法执行次数均为n3例第1章绪论1.4算法与算法分析说明：有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑①算法平均时间复杂度②算法在最坏情况下的时间复杂度算法的时间复杂度T(n)第1章绪论1.4算法与算法分析一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i=N;i++)for(j=0;j=N;j++)for(k=0;k=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;if(count==N&&money==N)printf(“%d,%d,%d\n%”,i,j,k);}}算法的时间复杂度为O(n3)100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支，各种组合方案的算法如下，计算时间复杂度。例第1章绪论1.4算法与算法分析本章小结数据结构和算法等基