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

《数据结构(C语言版)第1章绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第1章绪论.ppt（59页珍藏版）》请在三一办公上搜索。

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

2、现方法，并着重从时间上进行定性或定量的分析和比较。第十二章 文件结构 介绍数据库系统中组织文件的常用方法。,内 容 安 排,绪论,1、数据结构基本概念 数据、数据元素、数据对象、数据结构 和抽象数据类型等概念。2、算法及算法分析 性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量。,教学内容,数值计算：加工处理的对象纯粹的数值。,非数值计算,计算机应用,工业检测,过程控制,管理系统,文字处理,加工处理的对象,具有一定的结构,逻辑结构,存储结构,算法,有效地组织 计算机存储,研究对象的特性及 其相互之间的关系,有效地实现对象之 间的“运算”关系,数据结构的研究内容,为什么要学数据结构

3、？,1.1 什么是数据结构,抽象数学模型,计算机解题步骤,设计算法,编程、调试、运行,分析问题,提取操作对象,找出操作对象之间的关系,用数学语言描述,数据结构,例1：计算机电话号码查询系统。,算 法：查询、插入、修改、删除,线性结构,线性表,操作对象：单位名，号码,关 系：线性关系,例2：计算机和人对弈问题。,非线性结构,树,操作对象：格局（棋盘状态）,关 系：非线性关系（由比赛规则决定）,例3、多叉路口交通灯的管理问题。,在多叉路口需设几种颜色的交通灯才能使车辆相互之间不碰 撞，又能达到最大流通量。,非线性结构,图,操作对象：通路,关 系：非线性关系（由问题的要求决定）,程序设计的实质是对实

4、际问题选择一种好的数据结构，加之设计一个好的算法。,瑞士著名的计算机科学家、Pascal 语言发明者沃思(N.Wirth)教授提出：,数据结构是一门研究非数值计算的程序设计问题中计算 机的操作对象以及它们之间的关系和运算的一门学科。,数据结构是问题的数学模型。,算法（解决问题的方法）处理的对象就是数据。算法与数据 的结构密切相关，算法无不依附于具体的数据结构，数据结构直 接关系到算法的选择和效率。,要想有效地使用计算机，就必须学习数据结构。,程序=算法+数据结构,数据结构的发展史,“数据结构”作为一门独立的课程在国外是从 1968 年才开始 设立的，由美国唐 欧 克努特教授开创其最初体系，他所

5、著的 计算机程序设计技巧第一卷基本算法是第一本较系统地 阐述数据的逻辑结构和存储结构及其操作的著作。,我国于 1978 年开设本课程。,数据结构的地位,1、数据结构在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的 一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数 值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和应用程序的重要基 础。,是对信息的一种符号表示人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及 其活动所做的描述。,数据(Data),1.2 基本概念和术语,在计算

6、机科学中是指所有能输入到计算机中并被计 算机程序处理的符号的总称包括数值型数据和 非数值型数据(包括文字、表格、图象、声音等，都称为数据)。它是计算机操作对象的总称。,数据是个集合，可用集合的表示方法来写：数据=x|x 是计算机操作的对象,数据元素(Data Element)：(也称结点),是数据(集合)中的一个“个体”，是数据的基本单位，在计算 机程序中通常作为一个整体进行考虑和处理。,数据项(data item)：是数据结构中讨论的“最小单位”。,两类数据元素,不可分割的“原子”型数据元素,如：整数“5”，字符“N”等；,由多个款项构成的数据元素，其中每个款项被 称为一个“数据项”。,如描

7、述一个学生的信息的数据元素可由 3 个 数据项组成。其中的出生日期又可以由三个 数据项：“年”、“月”和“日”组成，则称“出 生日期”为“组合项”，而其它不可分割的数 据项为“原子项”。,数据对象(Data Object)：,是性质相同的数据元素的集合。是数据的一个子集。,例：整数数据对象的集合可表示为 N=0,1,2,，字母字符数据对象的集合可表示为 C=A,B,Z。,数据结构(Data Structure)：,是相互之间存在一种或多种 特定关系的数据元素的集合。,结构：数据元素之间的相互关系。,意为 x 和 y 之间存在“x 领先于 y”的次序关系。,长整数“321465879”可用 a1

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

9、，S 是 D 上关系的有限集。,例 1-4：复数的数据结构：Complex=(C,R)其中：C 是含两个实数的集合 c1,c2，分别表示复数的实部和 虚部。R=P，P 是定义在集合 C 上的一种关系。,例 1-5：科研课题小组的数据结构：,Group=(D,R),其中：D=T,G1,Gn,S11,Snm 1 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,操作对象的数学模型,逻辑结构(logical structure),指数据元素之间抽象化的相互关系。独立于计算机，是数据本身所固有的。,物理结构：数据的逻辑结构在计算

10、机中的存储形式(映象)。存储结构(Storage Structure)必须依赖于计算机。,位串：n 位的组合。,位(bit)：二进制数的一位。计算机中表示信息的最小单位。,元素(element)：计算机中用来存储数据元素的一个位串，结点(node)即数据元素在计算机中的映象。,数据域(data field)：当数据元素由若干数据项组成时，位串 中对应于各个数据项的子位串。,例：十进制数值 321 可用位串 101000001 表示，字母“A”可用位串 01000001 表示。,数据结构在计算机中的表示方法,顺序映象,非顺序映象,顺序存储结构,链式存储结构,用元素在存储器中的相对位置来表示数据元

11、素之间的逻辑关系。,在每一个数据元素中增加一个存放地址的指针(pointer)，用此指 针来表示数据元素之间的逻辑关系。,作业：,1.1,选择题部分 1、组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2、数据结构研究数据的（）以及它们之间的相互关系。（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3、在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构,填空题 1.数据逻辑结构包括（）、（）和（）三种类型，树形结构和图形结构

12、合称为（）。2.线性结构中元素之间存在（）关系，树形结构中元素之间 存在（）关系，图形结构中元素之间存在（）关系。,数据类型：(data type),数据类型是一组性质相同的值的集合以及定义于这个值集合 上的一组操作的总称。值的集合+值集合上的一组操作,例如，C 语言中的 int 型变量，是指由-32768 到 32767 范围 中的值构成的集合及一组操作（加、减、乘、除、乘方等）的总 称。而 Unsigned int 型变量，则是指由 0 到 65535 范围中的值构 成的集合及一组操作（加、减、乘、除、乘方等）的总称。,约束变量或常量的取值范围，约束变量或常量的操作。,在用高级程序设计语言

13、编写的程序中，必须对程序 中出现的每个变量、常量或表达式，明确说明它们 所属的数据类型。例如，C 语言中的基本数据类型 有：整型、字符型、实型（包括单精度型和双精度 型）及枚举型。,数据类型的作用,数据类型的作用,是解释计算机内存中信息含义的一种手段。,实现了信息的隐蔽，将用户不 必了解的细节封装在类型中。,抽象特性,强调的是其所能完成的功能以及它和外部用 户的接口(即外界使用它的方法)。,所有高级语言中都有“整型”数据类型，它们的实现方法可 以各自不同，但对程序员而言，它们是“相同”的。程序员使用 它们时仅需了解它们的数学特性，而不需要了解它们在语言中 是如何实现的。换句话说，各种语言中实现

14、的是同一个“整数 类型”，而这个“整数类型”的定义仅对“整数的数学特性”有明 确规定。,01000001,int：65（十进制数）char：A,抽象数据类型(Abstract Data Type，简称ADT)：,数学模型+定义在该模型上的一组操作。,数据结构+定义在此结构上的一组操作。,ADT 抽象数据类型名 数据对象:数据对象的定义数据关系:数据关系的定义基本操作:基本操作的定义 ADT 抽象数据类型名,抽象数据类型(Abstract Data Type)的描述方法：,抽象数据类型可用(D,S,P)三元组表示，其中，D 是数据对 象，S 是 D 上的关系集，P 是对 D 的基本操作集。,用伪

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

16、stroyComplex(&Z)初始条件：复数 Z 已存在。操作结果：复数 Z 被销毁。GetReal(Z,&realPart)初始条件：复数 Z 已存在。操作结果：用realPart 返回 Z 的实部值。GetImag(Z,&ImagPart)初始条件：复数 Z 已存在。操作结果：用ImagPart 返回 Z 的虚部值。Add(Z1,Z2,&sum)初始条件：Z1,Z2 是复数。操作结果：用sum 返回 z1,z2 的和值。ADT Complex,数据关系：R1=|e1是复数的实部，e2是复数的虚部,用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。,例 1-

17、6：抽象数据类型三元组的定义：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。,IsAscendi

18、ng(T)初始条件：三元组 T 已存在。操作结果：如果 T 的三个元素按升序排列，则返回 1，否则返回 0。IsDescending(T)初始条件：三元组 T 已存在。操作结果：如果 T 的三个元素按降序排列，则返回 1，否则返回 0。,Max(T,&e)初始条件：三元组 T 已存在。操作结果：用 e 返回 T 的三个元素中的最大值。Min(T,&e)初始条件：三元组 T 已存在。操作结果：用 e 返回 T 的三个元素中的最小值。ADT Triplet,1.3 抽象数据类型的表示与实现,抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之为固有数据类型）来表示和实现。,抽象数据类型的

19、实现包括数据结构的实现和操作的实现，因 此不仅要借用高级语言中的数据类型来描述它的存储结构，也要 利用高级语言中已经实现的固有数据类型的操作来实现抽象数据 类型的操作。,例：利用 C 语言实现的“复数”类型如下描述：,数据对象：D=e1,e2|e1,e2RealSet 数据关系：R1=|e1 是复数的实部，e2 是复数的虚部,/存储结构的定义 typedef struct float realpart;float imagpart;complex;,基本操作：InitComplex(&Z,v1,v2)DestroyComplex(&Z)GetReal(Z,&realPart)GetImag(Z

20、,&ImagPart)Add(Z1,Z2,&sum),/基本操作的函数原型说明void add(complex z1,complex z2,complex,本书采用类 C 语言作为抽象数据类型的描述工具。,1.4 算法和算法分析,1.4.1 算法,通俗地讲，算法就是一种解题的方法。,严格地讲算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多 个操作。,(5)输 出:一个算法有一个或多个输出，这些输出是同输入有着 某些特定关系的量。,(4)输 入:一个算法有零个或多个输入，这些输入取自于某个特 定的对象集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法

21、内给定。,算法的五个特性：,(1)有穷性:一个算法必须总是在执行有穷步之后结束，且每一步 都在有穷时间内完成。,(2)确定性:算法中每一条指令必须有确切的含义，无二义性。并 且，在任何条件下，算法同时只有唯一的一条执行路 径，即对于相同的输入只能得出相同的输出。,(3)可行性:算法描述的所有操作都必须足够基本，都是可以通过 已经实现的基本运算执行有限次来实现的。,序列中的每个操作都是可以简单完 成的，其本身不存在算法问题，例 如，“求 x 和 y 的和”就不够基本。,算法的含义与程序十分相似，但二者是有区别的。,注,1、一个程序不一定满足有穷性（如一个操作系统在用户未使用 前一直处于“等待”的

22、循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。）；,2、程序中的指令必须是机器可执行的，而算法中的指令则无此 限制。算法若用计算机语言来书写，则它就可以是程序。,一个算法可以用自然语言、数学语言或约定的符号来描述，也可以用流程图、计算机高级程序语言（如 C 语言）或伪代码等 来描述。,1.4.2 算法设计的要求,设计一个“好”的算法应考虑以下几个方面（评价标准）：,(1)正确性：算法应满足具体问题的需求。,“正确”的含义在通常的用法中有很大的差别，大体可分为以 下四个层次：1)、程序不含语法错误；2)、程序对于几组输入数 据能够得出满足规格说明要求的结果；3)、程

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

24、两者与问题的规模有关。,(2)可读性：算法在正确的前提下，可读性是摆在第一位的，这 在当今大型软件需要多人合作完成的环境下是至关重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。,1.4.3 算法效率的度量,一个算法执行时间，从理论上是不能算出来的，必须通过依 据该算法编制的程序上机运行测试才能知道。,度量一个程序的执行时间通常有两种方法：,(1)、事后统计的方法,此方法有两个缺陷：一是必须先运行程序；二是所得时间的 统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算 法本身的优劣。,(2)、事前分析估算的方法,事后统计容易陷入盲目境地，例如，当程序执行很长时间仍 未结束时，不易判

25、别是程序错了还是确实需要那么长的时间。,显然，后三条受着计算机硬件和软件的制约，既然是“估算”仅需考虑前两条。,与算法执行时间相关的因素有：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=s x+b;s=s x+c;s=s x+d;(3次乘法，3次加法)计算量小 方法2 的原理：a x x x+b x x+c

26、 x+d=(a x+b)x2+c x+d=(a x+b)x+c)x+d,问题的规模一般根据问题本身的性质合理地确定：例1：对 n 个电话号码进行排序，这里 n 即可作为问题的规模。显然对 1000 个电话号码进行排序比对 10 个电话号码进行排 序规模要大。例2：求 n 阶矩阵的转置，这里 n 即可作为问题的规模。,(2)、事前分析估算的方法,如何估算算法的时间效率？,填空题 1.算法的五个重要特性是（）、（）、（）、（）、（）。2.算法的四个衡量标准是（）、（）、（）、（）。,作 业,分析：任何一个算法都是由一个控制结构和若干原操作组成的。,控制结构：顺序、分支和循环 3 种。,原操作：指对

27、固有数据类型（高级语言中的数据类型）的操 作（如赋值操作、转向操作、比较操作等等），显然每个原操作 的执行时间和算法无关，相对于问题的规模是常量。,结论：算法的执行时间可看成是所有原操作的执行时间之和：,既然执行一种原操作所需的时间与算法无关，那么我们只讨 论影响运行时间的另一个因素算法中进行原操作的次数。,算法中包含原操作次数的多少叫做算法的时间复杂度，用它 来衡量一个算法的运行时间性能。,算法的执行时间如何计算？,算法的时间复杂度通常是问题的规模 n 的某个函数 T(n)。,例：累加求和 int Sum(int bn,int n)int i,s=0;for(i=0;in;i+)s+=bi;

28、return s;,各执行 1 次原 操作。,for 循环语句所包含的原操作：i=0;/1 次m1:if(i=n)goto m2;/n+1次 s+=bi;/n次 i+;/n次 goto m1;/n次m2:return s;,时间复杂度为：T(n)=4n+4,例：矩阵相加 void MA(int amsms,int bmsms,int cmsms,int n)/实现矩阵 an,n 和 bn,n 的加法，其和存入 cn,n 中/ms 为大于等于 n 的常量 int i,j;for(i=0;in;i+)for(j=0;jn;j+)cij=aij+bij;,双重 for 循环语句所包含的原操作：i=0

29、;/1 次m1:if(i=n)goto m4;/n+1次 j=0;/n次m2:if(j=n)goto m3;/n(n+1)次 cij=aij+bij;/nn次,时间复杂度为：T(n)=4n2+5n+2,j+;/nn次 goto m2;/nn次 m3:i+;/n次 goto m1;/n次 m4:,从上述分析可知，一个算法的时间复杂度的计算相当烦琐。实际上，一般没必要精确地计算出算法的时间复杂度，只要大 致计算出相应的数量级(Order)即可。,时间复杂度 T(n)的数量级表示：,定义,如果存在两个正常数 c 和 n0，对于所有的 n n0，有|f(n)|c|T(n)|则称 f(n)是 T(n)的

30、同数量级函数。,把 T(n)表示成数量级的形式为：T(n)=O(f(n)。称(f(n)为算法 的渐近时间复杂度，简称时间复杂度。,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)cij+=aik*bkj;,由于是一个三重循环，每个循环从 1 到 n，则原操作重复执 行的总次数为：nnn=n3，时间复杂度为 T(n)=O(n3)。,在“累加求和”例中，当n 1（即n0=1）时，|n|c|4n+4|均 成立，则f(n)=n，T(n)=O

31、(n)；在“矩阵相加”例子中，当 n2（即 n0=2）时，|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)

32、for(j=1;j=n;+j)+x;s+=x;包含“x 增 1”基本操作的语句的频度为：n2，其时间复杂度 为：O(n2)，即：平方阶。,例：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;a i,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(log n)O(n)O(nlog n)O(n2)O(2n)O(n!)O(nn),算法的时间 复杂度常见的有：常数阶 O(1)，对数阶 O(log n)，线性阶 O

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

34、ort最好情况：0次最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为：O(n2),在本课程中讨论的时间复杂度，均指最坏的时间复杂度。,1.4.4 算法的存储空间需求,一个算法所需存储空间,算法本身的存储空间 输入数据的存储空间 算法在运行过程中临时占用的存储空间,若所需临时空间不随问题规模的大小而改变，则称此算法为 原地工作。,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n)其中 n 为问题的规模。,程序代码本身所占空间对不同算法通常不会有数量级之差 别，因此在比较算法时可以不加考虑；算法的输入数据量和问 题规

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