第1章绪论000003.ppt

《第1章绪论000003.ppt》由会员分享，可在线阅读，更多相关《第1章绪论000003.ppt（50页珍藏版）》请在三一文库上搜索。

1、第1章 绪论,1.1 什么是数据结构（定义） 1.2 数据结构的内容 1.3 算法 1.4 算法描述的工具 1.5 对算法作性能评价 1.6 关于学习数据结构,计算机的解题步骤,1.1 什么是数据结构（定义）,1、抽象出一个适当的数学模型；,2、设计解此数学模型的算法；,3、编写程序、测试、调整直到得到最终解答。,1.1 什么是数据结构（定义）,1. 数据（Data）,对客观事物的符号描述，能输入到计算机中并被计算机程序处理的符号的总称； 能被计算机识别、存储和加工处理的信息的载体。,源程序（.c or .cpp)； 目标程序(.obj)； 可执行程序(.exe)。,图1.1 编译程序示意图,

2、2. 数据元素（Data Element） 数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。,表1-1 学 籍 表,数据项,记录,数据项：具有独立含义的最小数据标识单位。,整数数据对象是集合N=0， 1， 2， ， 字母字符数据对象是集合C=A，B， Z， 表1-1所示的学籍表也可看作一个数据对象。,3. 数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子集。,综上13所述，再分析数据概念：,4. 数据结构（Data Structure） 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，,结构（Struc

3、ture） 数据元素相互之间的关系。,在形式上可用二元组表示： Data_Structure = ( D,S) D: 数据元素的有限集 S: D上关系的有限集,数据结构的内容,逻辑结构 数据元素之间的关系 。,逻辑结构可看作是从具体问题抽象出来的数学模型。,图1.3 交通流量图,图1.2 学校组织层次结构图,2. 存储结构（物理结构） 逻辑结构在计算机中的存储映象，是逻 辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。,顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构）,逻辑结构与存储结构的关系 存储结构是逻辑结构用计算机语言的实现； 如何用计算机语言表示数据元素之间的各种关系

4、。 存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。,3. 数据的运算 对数据施加的操作，通过算法描述。 算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 抽象运算定义在逻辑结构上，而实现在存储结构上。,数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做数据结构。,电话号码查询问题,田径赛的时间安排问题 5个项目：A、B、C、D、E、F。每人至多参加

5、3项。,5. 数据类型(Data Type) 数据类型是一组性质相同的值的集合以及定义在这个值集上的一组操作的总称。 该类型的取值范围， 该类型中可允许使用的一组运算。,数据类型是数据结构在程序设计语言中的实现。,原子类型 结构数据类型,6. 数据抽象与抽象数据类型,） 数据的抽象 计算机中使用的是二进制数； 汇编语言中则可给出各种数据的十进制表示； 高级语言中，更高一级的数据抽象，出现了数据类型； 进一步定义更高级的数据抽象，如各种表、队、栈、树、图、 窗口、管理器等； 可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂

6、的抽象数据类型。,） 抽象数据类型 (Abstract Data Type) 抽象数据类型（简称ADT）是指一个数学模型以及定义在该模型上的一组操作。,一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。,分解、抽象和信息隐藏。,3） ADT的表示 ADT 数据对象: 结构关系: 基本操作: ADT ,一个线性表的抽象数据类型的描述如下： ADT Linear-list 数据元素：所有ai属于同一数据对象，i=1，2，n, n0； 逻辑结构：所有数据元素ai（i=1，2，n-1）存在次序关系，ai无前趋，an无后继； 操作： Initial

7、(L): 初始化空线性表; Length(L): 求线性表的表长; Get(L, i): 取线性表的第i个元素； Insert(L, i, b): 在线性表的第i个位置插入元素b； Delete(L, i): 删除线性表的第i个元素。 ADT Linear-list;,） 抽象数据类型实现,第一种情况： 传统的面向过程的程序设计。 第二种情况： “包”、 “模型”的设计方法。 第三种情况： 面向对象的程序设计（Object Oriented Programming，简称OOP）。,用标准C语言表示和实现ADT描述时，主要包括以下两个方面: (1) 通过结构体将int、 float等固有类型组合

8、到一起, 构成一个结构类型, 再用typedef为该类型或该类型指针重新起一个名字。 (2) 用C语言函数实现各操作。,1.3 算 法,1. 算法（Algorithm）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。 ),2. 算法的特性 (1)有穷性：有限步骤之内正常结束，不能形成无穷循环。 (2)确定性： 算法中的每一个步骤必须有确定含义，无二义性。

9、 (3) 输入： 有多个或0个输入。 (4) 输出： 至少有一个或多个输出。 (5) 可行性： 原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成。 在算法的五大特性中， 最基本的是有限性、 确定性和可行性。,3. 算法设计的要求,正确性 可读性 健壮性 高效率和低存储量,1.4 算法描述的工具,1. 算法、 语言和程序的关系 (1) 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。 自然语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构， 而高级程序语言则较为准确但又比较严谨。 (2) 程序是算法在计算机中的实现（与所用计算机及所用语言有关）。,2. 设计

10、实现算法的步骤 找出与求解有关的数据元素之间的关系（建立结构关系）。 确定在某一数据对象上所施加的运算。 考虑数据元素的存储表示。 选择描述算法的语言。 设计实现求解的算法， 并用程序语言加以描述。,3. 描述算法的语言选择 类C语言,(1) 预定义常量和类型。 本书中用到以下常量符号，如True、 False、MAXSIZE等，约定用如下宏定义预先定义： define TRUE 1 define FALSE 0 define MAXSIZE 100 define OK 1 define ERROR 0,1.5 对算法作性能评价,1. 性能评价 问题规模N 、所占空间S、所耗费时间T,2. 有

11、关数量关系的计算 1） 关于算法执行时间 所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 ,2） 语句频度 语句频度是指该语句在一个算法中重复执行的次数。,2个N*N矩阵相乘,for (i= 1; i=n; +i) for (j= 1; j=n; +j) cij = 0; for (k= 1; k=n; +k) cij += aik * bkj; ,n n2 n2 n3 n3,3） 算法的时间复杂度 算法中基本操作重复执行的次数是问题规模n的函数f(n)。 算法的时间度量记作T(n)。 分析T(n)随n的变化情况并确定T(n)的数量级 （Order

12、of Magnitude）。 用“O”来表示数量级，所谓算法的时间复杂度， 即是算法的时间量度，记作： T(n)=O(f(n), （1） x=x+1 ； 其时间复杂度为O(1)， 我们称之为常量阶； （2） for (i=1; i= n; i+) x=x+1; 其时间复杂度为O(n)， 我们称之为线性阶； （3） for (i=1; i= n; i+) for (j=1; j= n; j+) x=x+1; 其时间复杂度为O(n2), 我们称之为平方阶。 此外算法还能呈现的时间复杂度有对数阶O(log2n), 指数阶O(2n)等。,4） 数据结构中常用的时间复杂度频率计数 O(1) 常数阶 O(

13、n)线性阶 O(n2)平方阶 O(n3)立方阶 O(2n)指数阶 O(log2n)对数阶 O(nlog2n)线性对数阶,图1.6 多种数量级的时间复杂度图示,例如： 下列程序段： for (i=1; i n; i+) for (j=i; j= n; j+) x+; 语句x+的执行频度为 n+(n-1)+(n-2)+3+2+1 =n(n+1)/2 而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。,5） 最坏时间复杂度 算法中基本操作重复执行的次数还随所处理的数据集的状态有关。,6） 算法的空间复杂度 关于算法的存储空间需求，类似于算法的时间复杂度， 我们采用空间复杂度作为算法所

14、需存储空间的量度，记作： S(n)=O(f(n),1.6 关于学习数据结构,1. 数据结构课程的地位,图1.7 数据结构与其它课程的关系,2. “数据结构”课程的学习特点,“数据结构”课程的教学目标是要求学生学会分析数据对象特征， 掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。,3. 关于本书内容编写的说明 本书的基本结构分为三个部分： 第一部分： 数据结构的基本概念（第1章）。 第二部分： 基本的数据结构，包括：线性结构线性表、栈和队列、 串、 数组（第25章）；非线性结构树、 图（第

15、6、 7章）。 第三部分： 基本技术，包括：查找技术与排序技术（第8、9、 10章）。,数据结构,逻辑结构,存储结构,数据运算 （算法）,线性结构 （线性表、栈和队列、串）,非线性结构 （广义表、树、图、文件）,链式存储结构,顺序存储结构,练习 例1：设逻辑结构图如下，试给出其数据结构表示。,数据结构定义为： Data_Structure = (D,S) 其中 D=a,b,c,d,e,f S=R R=(a,b),(a,c),(c,d),(c,e), (c,f),(d,f),例2：设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数，写出其时间复杂度。 x=0; for( i=1

16、; in ; i+) for( j=1; j=n-i ; j+) x+;,例3：计算机执行下面的语句时，语句S的执行次数为多少？ for( i=1; i=i ; j-) S;,例4：试说明下列计算过程是否是一个算法？ （1）开始； （2）n = 0; （3）n+； （4）重复（3）； （5）结束； 不具备算法的有穷性，不是一个算法。,void exam1() n=2; while(n%2=0) n=n+2; printf(“%dn”,n); ,void exam2() y=0; x=3/y; printf(“%d,%dn” ,x,y); ,违反了有穷性。,违反了可行性。,作业 P7 ：（3、8、9、17）,