(C语言详细版)第一章-什么是数据结构

1、第一章 绪论重点：数据结构的基本概念难点：ADT、算法复杂度-1-第一章 绪论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求作业-2-1.1 什么是数据结构众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。在电子计算机发展的初期阶段，人们用计算机主要处理数值计算问题，用以解决人们用手工或机械计算机难以胜任的数值计算。 当时涉及的数据对象还比较简单，不外乎是整型、实型、布尔型等。数学软件 。随着计算机使用领域

2、的扩大和深入，解决“非数值性问题”越来越引起人们的重视和关注。例如：-3-1.1 什么是数据结构 金融和工商企业领域的信息管理系统 支持多媒体的文献资料查询 神经元和模式识别 网络与通信 图形化用户界面 等等-4-1.1 什么是数据结构解决此类问题使用的数学工具已不是分析数学和计算方法，而更多地用到离散数学和计算机的有关知识，所涉及的对象也更为复杂，其突出的特点是：数据元素之间所具有的特定联系已不能用分析数学的方程式来简单描述。 现代计算机科学的观点，计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：-5-1.1 什么是数据结构信息的表示和信息的处理信息的表示直接关系

3、到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。-6-1.1 什么是数据结构重要性历史沿革1968年DEKnuth 发表：“Art of computer programming”IEEE 68 教程1983 IEEE 83 教程1991 IEEE 91 教程2000 IEEE 2000 教程国内在78 年开设、相应地有93 教程等。计算机科技的两大支柱Algorithm + Data Structu

4、res = Programs Niklaus WirthAlgorithm: 求解问题的策略DS: 问题的数学模型Programs: 为计算机处理问题编制的一组指令-7-1.1 什么是数据结构实例：银行帐号共100000 个如图所示，组成一个顺序存储的结构，存于计算机之中。插入新帐号45怎样进行呢？插入新帐号45：1、查找位置2、移表3、插入合适位置移动一个结点，需100us, 移动100000 个结点需100us 100000 10 秒。每天处理10000 个帐号，需30 小时，无法接受。如何快速地进行插入?节省访问外存的时间，是一个很重要的问题。-8-1.1 什么是数据结构地位：1、“数据

5、结构”在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。-9-1.1 什么是数据结构事实证明，要想有效地使用计算机，仅掌握计算机语言而缺乏数据结构和算法的有关知识，难以应付众多复杂的应用课题。 -10-1.1 什么是数据结构一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤： 1）首先要从具体问题抽象出一个适当的数学模型； 2）然后设计一个解此数学模型的算法； 3）最后编出程

6、序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。下面请看几个例子。-11-1.1 什么是数据结构为了帮助同学们建立对数据结构的感性认识，下面举几个简单的例子例1：学生成绩单-12-1.1 什么是数据结构例1：学生成绩单要求：给定学生的学号或姓名，要求打印出其成绩；若学生不存在，则报告没有该学生的信息。计算机处理该问题时，应考虑：1) 数据及其存储：学生(学号,姓名

7、,成绩) struct student char sNo8;char sName9;int nScore; astStudent200;2) 基本运算的实现-13-1.1 什么是数据结构例2：图书馆书目检索系统自动化问题例3：计算机和人对弈问题例4：多叉路口交通灯的管理问题例5：附设煤气管道的最小费用问题例6：酒店管理系统中的客房分配问题-14-1.1 什么是数据结构结论描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现目前，多数高级语言尚不能直接操作这些带结构的数据。我们将在高级语言（C语言）的层次上

8、讨论如何表示这些数据和如何对它们进行操作。-15-1.2 基本概念和术语数据(Data)信息的载体能输入到计算机中被计算机程序处理的符号集数据元素(Data Element)数据的基本单位在计算机程序中作为一个整体进行考虑和处理一个数据元素可以由若干数据项(Data Item)组成数据项是具有独立含义的最小标识单位数据对象(Data Object)性质相同的数据元素的集合 e.g. C= A, B, , Z -16-1.2 基本概念和术语-数据结构数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。即带结构的数据对象，它有两层含义： 第一，它包括一个具有共

9、同特性的数据元素的集合，即数据对象。 第二，它还包括一个定义在这个集合上的一组关系，即数据元素之间的“结构”。-17-1.2 基本概念和术语-数据结构数据结构(Data Structure)形式定义Data_Structure = （D, S）D-数据对象 S该对象中各数据元素之间的关系的有限集四个基本的数据结构集合结构：关系集合是空集顶点元素间无任何关系，R= 空集-18-1.2 基本概念和术语-线性结构/树线性结构：元素间的关系是1 : 1一个结点（除尾结点外）有且仅有一个直接前驱一个结点（除头结点外）有且仅有一个直接后继树型结构：一般树、二叉树、森林一个结点可以有多个直接后继（除叶子结点

10、外），但只有一个直接前驱（除根结点外）-19-1.2 基本概念和术语-图状结构图状结构：元素间的关系是m : n一个结点可以有多个直接后继，也可以有多个直接前驱注：由于“集合”是数据元素之间关系极为松散的一种结构，因此可用其他结构来表示-20-1.2 基本概念和术语-逻辑结构数据结构包括逻辑结构和物理结构数据的逻辑结构研究的是数据元素及其关系的数学特性。特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关与数据元素的相对位置无关分类线性结构：线性表非线性结构：树、图-21-1.2 基本概念和术语-存储结构数据的物理结构（存储结构）研究的是它们在计

11、算机内的实现方法（映象）。（OR）数据结构在计算机中的表示对机器语言：这种实现是具体的对高级语言：在高级语言的层次上来讨论这种实现，用高级语言中的数据类型来描述这种实现细节，不妨称其为虚拟存储结构。依赖于计算机程序设计语言说明：为简明起见，以后我们简称数据结构的逻辑结构数据结构数据结构的物理结构存储结构-22-1.2 基本概念和术语-存储结构数据元素之间的关系的表示顺序映像（顺序存储结构）：借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 向量（表格存储结构）非顺序映像（链式存储结构）：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。 单链表、双链表、多重

12、链表、循环链表索引存储结构散列存储结构-23-1.2 基本概念和术语-存储结构说明：四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。因此，我们至少可以得到44种可能的物理数据结构： sequential (sets) linked lists indexed trees hash graphs并不是所有的可能组合都合理-24-1.2 基本概念和术语-存储结构数据的逻辑结构和存储结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构-25-1.2 基本概念和术语-抽象数据

13、类型抽象数据类型数据类型一个值的集合定义在该值集上的一组操作C语言中的基本数据类型int short char float double 抽象数据类型一个数学模型及定义在该模型上的一组操作如：矩阵 + （求转置、加、乘、逆、特征值） -26-1.2 基本概念和术语-抽象数据类型抽象数据类型定义（D, S, P）D数据对象SD上的关系集P对D的基本操作集ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述-27-1.2 基本概念和术语-抽象数据类型抽象数据类型的

14、特征数据抽象对程序处理的实体的描述强调的是其本质的特征、其所能完成的功能以及它和外部养护的接口(即外界使用它的方法) 数据封装将实体的外部特性和其内部实现细节分离，并且对外部养护隐藏其内部实现细节 认为DT 仅存在于想象之中。注意力集中在感兴趣的性质上，不关心数据的表示形式，操作的具体代码等等。给出规范或说明。-28-1.2 基本概念和术语-抽象数据类型-29-1.2 基本概念和术语数据结构的内容包括三个层次的五个“要素”，如图所示。-30-1.3 抽象数据类型的表示与实现通过程序设计语言中的类型来实现C抽象数据类型数据对象 结构体基本操作 函数C+，Java抽象数据类型 类 class 数据

15、对象 数据成员基本操作 成员函数(方法) 一个例子-31-1.3 抽象数据类型的表示与实现表示：伪语言借用程序设计语言的结构描述-简洁、严谨忽略程序设计语言的细节-简洁伪C语言与C语言的区别抽象数据类型：typedef赋值：成组赋值、交换赋值选择语句： switch的扩展输入/输出：可以忽略格式串头文件、辅助变量定义：忽略C的扩展：引入C+的引用参数表示变参-32-1.3 抽象数据类型的表示与实现伪C中的引用参数C的扩展C的虚实结合：单向的值传递问题：如何简单地表示返回多个值？C支持的策略：全局变量、将形参定义为指针类型、将返回值定义为指针类型C+的另一种处理：引用参数 类型说明符 &引用参数

16、名引用参数与实在参数共享存储单元利用引用参数表示变参(可以将在被调用函数体中改变了的值代回主调处）-33-1.4 算法和算法分析-定义和特性定义对特定问题的求解步骤的一种描述，指令的有限序列，其中每一条指令表示一个或多个操作。特性有穷性：算法在执行有穷步后能结束，且每一步都在有穷时间内完成。确定性：每一指令有确切的含义，无二义。且算法只有一个入口和一个出口。可行性：每一操作都可以通过已经实现的基本运算执行有限次来实现输入：零个或多个输入输出：一个或多个输出-34-1.4 算法和算法分析-算法评价标准算法评价标准正确性（Correctness）首先，算法应当满足以特定的“规格说明”方式给出的需求

17、。其次，对算法是否“正确”的理解可以有以下四个层次： 程序不含语法错误；对于几组输入数据能够得出满足要求的结果；程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能得出满足要求的结果；通常以第3层意义的正确性作为衡量一个算法是否合格的标准。-35-1.4 算法和算法分析-算法评价标准可读性（Readability）算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序很容易隐藏较多错误而难以调试 健壮性（Robustness）当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不

18、是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。异常处理机制-36-1.4 算法和算法分析-算法评价标准高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。-37-1.4 算法和算法分析-事后统计算法效率的度量一个可执行的正确的算法也有优劣之分，通常以算法执行时在时间和空间资源方面消耗的多寡作为评价算法优劣的标准。事后统计利用计算机内部的计时功能 double start, stop; time (&start); mainprocess

19、(n, ); time (&stop); double runTime = stop - start; printf ( ”%d%dn , n, runTime );缺陷1、必须执行程序2、其它因素掩盖算法本质 （时间统计量依赖于计算机的软硬件环境）-38-1.4 算法和算法分析-时间分析事前分析估算(时间)算法的策略问题规模编程语言编译器产生的机器代码质量机器执行指令的速度-39-1.4 算法和算法分析-时间分析时间复杂度度量定义显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件

20、因素都确定下来，这样一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。-40-1.4 算法和算法分析-时间分析一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T (n) = O(f(n)称T (n) 为算法的(渐近)时间复杂度

21、-41-1.4 算法和算法分析-时间分析运行时间 = 算法中每条语句执行时间之和频度：是指该语句重复执行的次数。每条语句执行时间 = 频度 * 语句执行一次所需时间设每条语句执行一次所需时间为单位时间(渐进)时间复杂度： T(n) = O(f(n) 例子常见函数的增长率：P16-42-1.4 算法和算法分析-时间分析例1-4-1 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) -43-1.4 算法和

22、算法分析-时间分析例1-4-2 +x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。-44-1.4 算法和算法分析-时间分析例1-4-3 for(i=1;i=n;+i) +x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。-45-1.4 算法和算法分析-时间分析例1-4-4 for(i=1;i=n;i=2i) (1) +x;s+=x; (2)分析：其中基本语句为(2)，设其执行次数为f(n),则 2f(n) =n 故 f(n)=log 2 n=O(log 2 n)即时间复

23、杂度为对数阶。定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)。（证略）-46-1.4 算法和算法分析-时间分析例1-4-5 for(i=2;i=n;+I) for(j=2;j=i-1;+j) +x;ai，j=x; 语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2 -3n+2 时间复杂度为O(n2 ) 即此算法的时间复杂度为平方阶.-47-1.4 算法和算法分析-时间分析例1-4- 6 n！的递归算法int fac(int n)if (n=1) return 1; (1)el

24、se return (n*fac(n-1); (2)分析：设T(n)为fac(n)的时间开销，显然 T(1)=O(1)。语句(1)的时间开销为O(1)，递归调用fac(n-1) 的时间开销为T(n-1)，则语句(2)的时间开销为：O(1)+T(n-1)。 则： T(n)=O(1)+T(n-1)= O(1)+ O(1)+T(n-2)= =(n-1)*O(1)+T(1) =n*O(1) =O(n)-48-1.4 算法和算法分析-时间分析例1-4-7 如下为NN矩阵相乘的算法，for (i=1; i=n; +i) for (j=1; j=n; +j) cij = 0; for (k=1; k=n; +k) cij += aik*bkj; 乘法运算是“矩阵相乘问题”的基本操作。整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比，记作T(n) = O(n3 )-49-1.4 算法和算法分析-时间分析例1-4-8 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：void select_sort(int a, int n) / 将a中整数序列重新排列成自小至大 / 有序的整数序列。 for ( i = 0; i n-1; +i ) j = i; for ( k = i+1; k