数据结构(C语言版)第1章绪论.ppt

《数据结构(C语言版)第1章绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第1章绪论.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第一章绪论数据结构(C语言版)Data Structure主讲教师鄂寒梅E-mail:数据结构第一章绪论学分：3 总学时：64 教材：数据结构（C语言版）严蔚敏、吴伟民-清华大学出版社 数据结构题集（C语言版）严蔚敏、吴伟民-清华大学出版社数据结构第一章绪论v编程基础v考研课程v计算机等级考试课程v程序员考试课程课程重要性数据结构第一章绪论本课程的体系结构 第一章绪论 介绍数据、数据结构和抽象数据类型的概念。第二章第七章基本数据结构 从抽象数据类型的角度，分别讨论线性表、栈和队列、串、数组和广义表、树、图等基本数据结构及其应用。第八章动态存储管理 介绍操作系统和编译程序中涉及的 动态存

2、储管理的基本技术。数据结构第一章绪论 第九章第十一章查找和排序 介绍了各种实现方法，并着重从时间上进行定性或定量的分析和比较。第十二章文件结构 介绍数据库系统中组织文件的常用方法。数据结构第一章绪论内容安排章 内容 学时 章 内容 学时1序论2 7图82线性表8 8动态存储管理略3栈和队列8 9查找84串8 10内部排序85数组和广义表8 11外部排序略6树和二叉树8 12文件略数据结构第一章绪论 总评成绩（100分）期末考试（60%）平时成绩（40%）课堂考勤上机演示作业课堂测验数据结构第一章绪论数据结构第一章绪论1、数据结构基本概念数据、数据元素、数据对象、数据结构和抽象数据类型等概念。2

3、、算法及算法分析性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量。教学内容数据结构第一章绪论占据了当今计算机应用的绝大多数。数值计算：加工处理的对象纯粹的数值。非数值计算计算机应用工业检测过程控制管理系统文字处理加工处理的对象字符表格图象声音具有一定的结构 逻辑结构存储结构算法有效地组织计算机存储研究对象的特性及其相互之间的关系有效地实现对象之间的“运算”关系 数据结构的研究内容 为什么要学数据结构？数据结构第一章绪论1.1什么是数据结构抽象数学模型 计算机解题步骤设计算法 编程、调试、运行 分析问题 提取操作对象 操作对象 找出操作对象之间的关系 操作对象之间的关系 用数学语言

4、描述 数据结构 数据结构第一章绪论例1：计算机电话号码查询系统。法学系8523101国贸系8522105工商系8523150计算机系8521088会计系8525789统计系85281368521088计算机系8522105国贸系8523101法学系8523150工商系8525789会计系8528136统计系算法：查询、插入、修改、删除 线性结构 线性表 操作对象：单位名，号码关系：线性关系数据结构第一章绪论例2：计算机和人对弈问题。非线性结构 树 操作对象：格局（棋盘状态）关系：非线性关系（由比赛规则决定）数据结构第一章绪论例3、多叉路口交通灯的管理问题。在多叉路口需设几种颜色的交通灯才能使车

5、辆相互之间不碰 相互之间不碰撞 撞，又能达到最大流通量 达到最大流通量。ABCDE非线性结构 图 操作对象：通路关系：非线性关系（由问题的要求决定）ABACADBADCEDBC BDDADBEAEBEC数据结构第一章绪论程序设计的实质 实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。瑞士著名的计算机科学家、Pascal语言发明者沃思(N.Wirth)教授提出：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 操作对象以及它们之间的关系 关系和运算 运算的一门学科。数据结构是问题的数学模型。算法（解决问题的方法）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于

6、具体的数据结构，数据结构直接关系到算法的选择和效率。要想有效地使用计算机，就必须学习数据结构。要想有效地使用计算机，就必须学习数据结构。程序=算法+数据结构数据结构第一章绪论数据结构的发展史“数据结构”作为一门独立的课程在国外是从1968 1968年才开始设立的，由美国唐欧克努特教授开创其最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。我国于1978 1978年开设本课程。数据结构第一章绪论数据结构的地位 1、数据结构在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数

7、据结构这一门课的内容不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和应用程序的重要基础。数据结构第一章绪论是对信息的一种符号表示人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。数据 数据(Data)(Data)1.2基本概念和术语在计算机科学中是指所有能输入到计算机中并被计 算机程序处理的符号的总称包括 数值型数据 数值型数据和非数值型数据 非数值型数据(包括文字、表格、图象、声音等，都称为 数据 数据)。它是计算机操作对象的总称。数据是个集合，可用集合的表示方法来写：数据=x|x 是计算机操

8、作的对象数据结构第一章绪论数据元素 数据元素(DataElement)(DataElement)：(也称结点 也称结点)是数据(集合)中的一个“个体”，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项 数据项(dataitem)(dataitem)：是数据结构中讨论的“最小单位”。两类数据元素 不可分割的“原子 原子”型数据元素如：整数“5”，字符“N”等；由多个款项构成的数据元素，其中每个款项被称为一个“数据项 数据项”。如描述一个学生的信息的数据元素可由3个数据项 数据项组成。其中的出生日期又可以由三个数据项：“年”、“月”和“日”组成，则称“出生日期”为“组合项”，

9、而其它不可分割的数据项为“原子项”。姓名出生日期 成绩年 月 日数据结构第一章绪论数据对象 数据对象(DataObject)(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。例：整数数据对象的集合可表示为N=0,1,2,，字母字符数据对象的集合可表示为C=A,B,Z。数据结构 数据结构(DataStructure)(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。结构：结构：数据元素之间的相互关系。数据结构第一章绪论 意为x和y之间存在“x 领先于y”的次序关系。长整数“321465879”可用a1=321，a2=465和a3=879的集合

10、表示，且三者之间的次序关系必须是，a1表示最高3位，a3表示最低的3位，a2则是中间3位。例：假设以三个3位的十进制数表示一个含9位十进制数的“长整数”，则可用如下描述的数学模型表示：它是一个含三个数据元素a1,a2,a3的集合，且在集合上存在下列次序关系：，。数据结构第一章绪论四类基本结构集合：数据元素除了 同属于一种类型 同属于一种类型 外，别无其它关系。线性结构：一对一 一对一。树型结构：一对多 一对多。图状结构或网状结构：多对多 多对多。数据结构第一章绪论数据结构的形式定义：数据结构是一个二元组：Data-Structure=(Data-Structure=(DD,SS)其中：D是数据

11、元素的有限集，S是D上关系的有限集。数据结构第一章绪论例1-4：复数的数据结构：Complex=(Complex=(C C,R R)其中：C是含两个实数的集合c1,c2，分别表示复数的实部和虚部。R=P，P是定义在集合C 上的一种关系。例 1-5：科研课题小组的数据结构：Group=(Group=(D D,R R)其中：D=T,G1,Gn,S11,Snm1 n 3,1 m 2,R=R1,R2，R1=|1 i n,1 n 3 R2=|1 i n,1 j m,1 n 3,1 m 2操作对象的数学模型 逻辑结构(logicalstructure)指数据元素之间抽象化的相互关系。独立于计算机，是数据本

12、身所固有的。独立于计算机，是数据本身所固有的。TG1G2G3S11S12S21S22S31S32数据结构第一章绪论物理结构：物理结构：数据的逻辑结构在计算机中的存储形式(映象)。存储结构 存储结构(StorageStructure)StorageStructure)必须依赖于计算机。位串 位串：n位的组合。位 位(bit)(bit)：二进制数的一位。计算机中表示信息的最小单位。元素 元素(element)(element)：计算机中用来存储数据元素的一个位串，结点 结点(node)(node)即数据元素在计算机中的映象。数据域 数据域(datafield)(datafield)：当数据元素由若

13、干数据项组成时，位串中对应于各个数据项的子位串。例：十进制数值321可用位串101000001表示，字母“A”可用位串01000001表示。数据结构第一章绪论数据结构在计算机中的表示方法 顺序映象 非顺序映象 顺序存储结构链式存储结构用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。在每一个数据元素中增加一个存放地址的指针(pointer)，用此指针来表示数据元素之间的逻辑关系。03003.00302-2.30632-0.706344.8复数顺序存储结构0415-2.306113.006130415复数链式存储结构 数据结构第一章绪论作业：1.1选择题部分1、组成数据的基本单位是（）（A

14、）数据项（B）数据类型（C）数据元素（D）数据变量2、数据结构研究数据的（）以及它们之间的相互关系。（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3、在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构填空题 1.数据逻辑结构包括（）、（）和（）三种类型，树形结构和图形结构合称为（）。2.线性结构中元素之间存在（）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在（）关系。数据结构第一章绪论数据类型：(datatype)数据类型是一组性质相同的

15、值的集合以及定义于这个值集合 上的一组操作的总称。值的集合 值的集合+值集合上的一组操作 值集合上的一组操作 例如，C语言中的int型变量，是指由-32768到32767范围中的值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。而Unsignedint型变量，则是指由0到65535范围中的值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。约束变量或常量的取值范围 取值范围，约束变量或常量的操作 操作。在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C 语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及

16、枚举型。数据类型的作用数据结构第一章绪论数据类型的作用是解释计算机内存中信息含义的一种手段。实现了信息的 实现了信息的隐蔽，将用户不，将用户不 必了解的细节 必了解的细节封装在类型中。在类型中。抽象特性 强调的是其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。所有高级语言中都有“整型”数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是“相同”的。程序员使用它们时仅需了解它们的数学特性 数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个“整数类型”，而这个“整数类型”的定义仅对“整数的数学特性”有明确规定。01000001int：65（十进

17、制数）char：A数据结构第一章绪论抽象数据类型 抽象数据类型(AbstractDataType(AbstractDataType，简称，简称ADT)ADT)：数学模型+定义在该模型上的一组操作。数据结构+定义在此结构上的一组操作。ADT ADT抽象数据类型名 抽象数据类型名数据对象:数据对象的定义数据关系:数据关系的定义基本操作:基本操作的定义 ADT 抽象数据类型名抽象数据类型(AbstractDataType)的描述方法：抽象数据类型可用(D,S,P)三元组表示，其中，D是数据对象，S 是D上的关系集，P是对D的基本操作集。用伪码(不真正执行的符号)描述数据结构第一章绪论基本操作的定义格

18、式：赋值参数：只为操作提供输入值；引用参数：以&打头，除了可提供输入值外，还将返回操作结果。描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。说明操作正常完成之后，数据结构的变化状况和应返回的结果。基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述数据结构第一章绪论例：抽象数据类型“复数”的定义ADTComplex数据对象：D=e1,e2|e1,e2 RealSet基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)初始条件：

19、复数Z已存在。操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数Z已存在。操作结果：用realPart返回Z的实部值。GetImag(Z,&ImagPart)初始条件：复数Z已存在。操作结果：用ImagPart返回Z的虚部值。Add(Z1,Z2,&sum)初始条件：Z1,Z2是复数。操作结果：用sum返回z1,z2的和值。ADTComplex数据关系：R1=|e1是复数的实部，e2是复数的虚部用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。数据结构第一章绪论例1-6：抽象数据类型三元组的定义：ADTTriplet数据对象：D=e1,

20、e2,e3|e1,e2,e3 ElemSet数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T，元素e1，e2和e3分别被赋以参数v1，v2和v3的值。数据结构第一章绪论DestroyTriplet(&T)操作结果：三元组T被销毁。Get(T,i,&e)初始条件：三元组T已存在，1i 3。操作结果：用e返回T的第i元的值。Put(&T,i,e)初始条件：三元组T已存在，1i 3。操作结果：改变T的第i元的值为e。数据结构第一章绪论IsAscending(T)初始条件：三元组T已存在。操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。I

21、sDescending(T)初始条件：三元组T已存在。操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。数据结构第一章绪论Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最小值。ADTTriplet数据结构第一章绪论1.3抽象数据类型的表示与实现抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之为固有数据类型 固有数据类型）来表示和实现。抽象数据类型的实现包括数据结构的实现和操作的实现，因此不仅要借用高级语言中的数据类型来描述它的存储结构，也要利用高级语言中

22、已经实现的固有数据类型的操作来实现抽象数据类型的操作。数据结构第一章绪论例：利用C语言实现的“复数”类型如下描述：数据对象：D=e1,e2|e1,e2 RealSet数据关系：R1=|e1是复数的实部，e2是复数的虚部/存储结构的定义typedefstructfloatrealpart;floatimagpart;complex;数据结构第一章绪论基本操作：InitComplex(&Z,v1,v2)DestroyComplex(&Z)GetReal(Z,&realPart)GetImag(Z,&ImagPart)Add(Z1,Z2,&sum)/基本操作的函数原型说明voidadd(comple

23、xz1,complexz2,complex&sum)/以sum返回两个复数z1，z2的和/基本操作的实现sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;本书采用类C语言作为抽象数据类型的描述工具。数据结构第一章绪论1.4算法和算法分析1.4.1算法通俗地讲，算法就是一种解题的方法。严格地讲算法是对特定问题求解步骤的一种描述，它是 指令 指令的有限序列，其中每一条指令表示一个或多个操作。数据结构第一章绪论(5)输 出:一个算法有一个 一个或多个 多个输出，这些输出是同输入有着某些特定关系的量。(4

24、)输 入:一个算法有零个 零个或多个 多个输入，这些输入取自于某个特定的对象集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。算法的五个特性：(1)有穷性:一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。(2)确定性:算法中每一条指令必须有确切的含义，无二义性。并 且，在任何条件下，算法同时只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。(3)可行性:算法描述的所有操作都必须足够基本 足够基本，都是可以通过已经实现的基本运算执行有限次来实现的。序列中的每个操作都是可以简单完成的，其本身不存在算法问题，例如，“求x和y的和”就不够基本。数据结构第

25、一章绪论算法的含义与程序十分相似，但二者是有区别的。注1、一个程序不一定满足有穷性（如一个操作系统在用户未使用前一直处于“等待”的循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。）；2、程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法若用计算机语言来书写，则它就可以是程序。一个算法可以用自然语言、数学语言或约定的符号来描述，也可以用流程图、计算机高级程序语言（如C 语言）或伪代码等来描述。数据结构第一章绪论1.4.2算法设计的要求设计一个“好”的算法应考虑以下几个方面（评价标准）：(1)正确性：算法应满足具体问题的需求。“正确”的含义在通常的用法中有很

26、大的差别，大体可分为以下四个层次：1)、程序不含语法错误；2)、程序对于几组输入数据能够得出满足规格说明要求的结果；3)、程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；4)、程序对于一切合法的输入数据都能产生满足规格说明要求的结果。通常以第3)层意义的正确性作为衡量一个程序是否合格的标准。数据结构第一章绪论(3)健壮性：算法应具有容错处理功能。当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。(4)效率与低存储

27、量需求：效率 效率指的是算法执行的时间（时间复杂性）；存储量需求 存储量需求指算法执行过程中所需要的最大存储空间（空间复杂性）。一般这两者与问题的规模有关。(2)可读性：算法在正确的前提下，可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是至关重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。数据结构第一章绪论1.4.3算法效率的度量一个算法执行时间，从理论上是不能算出来的，必须通过依据该算法编制的程序上机运行测试才能知道。度量一个程序的执行时间通常有两种方法：(1)、事后统计的方法此方法有两个缺陷：一是必须先运行程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素

28、，有时容易掩盖算法本身的优劣。(2)、事前分析估算的方法事后统计容易陷入盲目境地，例如，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。数据结构第一章绪论显然，后三条受着计算机硬件和软件的制约，既然是“估算”仅需考虑前两条。与算法执行时间相关的因素有：1)、算法选用的策略2)、问题的规模3)、编写程序的语言4)、编译程序产生的机器代码的质量5)、计算机执行指令的速度一般认为算法的效率只依赖于问题的规模。问题的规模如何计算？例：考虑计算三次多项式ax3+bx2+cx+d 方法1：s=a x x x+b x x+c x+d(6次乘法，3次加法)计算量大方法2：s=a;s=

29、sx+b;s=sx+c;s=sx+d;(3次乘法，3次加法)计算量小方法2的原理：a x x x+b x x+c x+d=(ax+b)x2+c x+d=(ax+b)x+c)x+d 问题的规模一般根据问题本身的性质合理地确定：例1：对n个电话号码进行排序，这里n即可作为问题的规模。显然对1000个电话号码进行排序比对10个电话号码进行排序规模要大。例2：求n阶矩阵的转置，这里n即可作为问题的规模。(2)、事前分析估算的方法如何估算算法的时间效率？数据结构第一章绪论填空题 1.算法的五个重要特性是（）、（）、（）、（）、（）。2.算法的四个衡量标准是（）、（）、（）、（）。作 业数据结构第一章绪论

30、分析：分析：任何一个算法都是由一个控制结构 控制结构和若干原操作 原操作组成的。控制结构 控制结构：顺序、分支和循环3种。原操作 原操作：指对固有数据类型（高级语言中的数据类型）的操作（如赋值操作、转向操作、比较操作等等），显然每个原操作的执行时间和算法无关，相对于问题的规模是常量。结论：结论：算法的执行时间可看成是所有原操作的执行时间之和：既然执行一种原操作所需的时间与算法无关，那么我们只讨论影响运行时间的另一个因素算法中进行原操作的次数。算法中包含原操作次数的多少叫做算法的时间复杂度 时间复杂度，用它来衡量一个算法的运行时间性能。算法的执行时间如何计算？数据结构第一章绪论算法的时间复杂度通

31、常是问题的规模n的某个函数T(n)。例：累加求和intSum(intbn,intn)inti,s=0;for(i=0;i=n)gotom2;/n+1次s+=bi;s+=bi;/n次i+;/n次gotom1;/n次m2:returns;时间复杂度为：T(n)=4n+4数据结构第一章绪论例：矩阵相加voidMA(intamsms,intbmsms,intcmsms,intn)/实现矩阵an,n和bn,n的加法，其和存入cn,n中/ms为大于等于n的常量inti,j;for(i=0;in;i+)for(j=0;j=n)gotom4;/n+1次j=0;/n次m2:if(j=n)gotom3;/n(n+

32、1)次cij=aij+bij cij=aij+bij;/n n次时间复杂度为：T(n)=4n2+5n+2j+;/n n次gotom2;/n n次m3:i+;/n次gotom1;/n次m4:数据结构第一章绪论从上述分析可知，一个算法的时间复杂度的计算相当烦琐。实际上，一般没必要精确地计算出算法的时间复杂度，只要大致计算出相应的数量级(Order)即可。时间复杂度T(n)的数量级表示：定义如果存在两个正常数c和n0，对于所有的n n0，有|f(n)|c|T(n)|则称f(n)是T(n)的同数量级函数。把T(n)表示成数量级的形式为：T(n)=O(f(n)。称(f(n)为算法的渐近时间复杂度，简称时

33、间复杂度 时间复杂度。O是Order的首字母，意为f(n)与T(n)只差一个常数倍。算法效率的度量：采用渐进时间复杂度数据结构第一章绪论例：for(i=1，i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)c c i i j j+=+=a a i i k k*b b k k j j;由于是一个三重循环，每个循环从1到n，则原操作 原操作重复执行的总次数为：nnn=n3，时间复杂度为T(n)=O(n3)。在“累加求和”例中，当n 1（即n0=1）时，|n|c|4n+4|均成立，则f(n)=n，T(n)=O(n)；在“矩阵相加”例子中，当n 2（即n0=2）时，

34、|n2|c|4n2+5n+2|均成立，则f(n)=n2。T(n)=O(n2)。原操作应是：重复执行次数和算法的执行时间成正比的原操作。原操作的重复执行次数和包含它的语句被执行的次数相同。数据结构第一章绪论语句频度：语句被重复执行的次数。例：+x;s=0;包含“x 增1”基本操作的语句的频度为，即时间复杂度为O(1)。O(1)表示算法的运行时间为常量。即：常量阶 常量阶。例：for(i=1;i=n;+i)+x;s+=x;包含“x 增1”基本操作的语句的频度为：n，其时间复杂度为：O(n)，即：线性阶 线性阶。数据结构第一章绪论例：for(i=1;i=n;+i)for(j=1;j=n;+j)+x;

35、s+=x;包含“x 增1”基本操作的语句的频度为：n2，其时间复杂度为：O(n2)，即：平方阶 平方阶。例：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;包含“x 增1”基本操作的语句的频度为：1+2+3+n-2=(1+n-2)(n-2)/2=(n-1)(n-2)/2其时间复杂度为：O(n2)，即：平方阶 平方阶。数据结构第一章绪论常见的算法的时间复杂度之间的关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(2n)O(n!)O(nn)算法的时间复杂度常见的有：常数阶O(1)，对数阶O(logn)，线性阶O(n)，线性对数阶O(nlogn)

36、，平方阶O(n2)，立方阶O(n3)，k 次方阶O(nk)，指数阶O(2n)，阶乘阶O(n!)。当n很大时，指数阶算法和多项式阶算法在所需时间上非常悬殊。因此，只要有人能将现有指数阶算法中的任何一个算法化简为多项式阶算法，那就取得了一个伟大的成就。数据结构第一章绪论有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：起泡排序Voidbubble-sort(inta，intn)/将a中整数序列重新排列成自小至大有序的整数序列。for(i=n-1,change=TURE;i 1&change;-i)change=false;for(j=0;j aj+1)a a j j a

37、 a j j+1;change=TURE+1;change=TURE/bubble-sort最好情况：0次最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为：O(n2)在本课程中讨论的时间复杂度，均指最坏的时间复杂度。数据结构第一章绪论1.4.4算法的存储空间需求一个算法所需存储空间算法本身的存储空间输入数据的存储空间算法在运行过程中临时占用的存储空间若所需临时空间不随问题规模的大小而改变，则称此算法为原地工作 原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n)其中n 为问题的规模。程序代码本身所占空间对不

38、同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外空间。数据结构第一章绪论性质相同的构成的集合_本章是为以后各章讨论的内容作基本知识的准备。本章小结：数据 数据数据元素 数据元素 个体_ 数据对象 数据对象 加上数据元素之间的关系数据结构 数据结构 由关系不同分类集合结构线性结构树形结构图状结构加上操作抽象数据类型 抽象数据类型 数据对象数据关系基本操作映像到内存存储结构 存储结构 顺序结构 顺序结构 链式结构 链式结构 算法 算法 特性：有穷性、确定性、可行性、输入、输出衡量标准：正确性、可读性、健壮性、效率、存储量需求时间复杂度 时间复杂度 空间复杂度 空间复杂度 数据结构第一章绪论1、理解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系。2、理解并掌握抽象数据类型定义、表示和实现方法。3、理解算法的五个特性和算法正确性的确切含义。4、理解算法的四个衡量标准。5、掌握计算语句频度和估算算法时间复杂度的方法。教学要求