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

(C语言详细版)第一章什么是数据结构第一页，共52页。第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求作业第二页，共52页。1.1什么是数据结构众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。在电子计算机发展的初期阶段，人们用计算机主要处理数值计算问题，用以解决人们用手工或机械计算机难以胜任的数值计算。当时涉及的数据对象还比较简单，不外乎是整型、实型、布尔型等。——数学软件。随着计算机使用领域的扩大和深入，解决“非数值性问题”越来越引起人们的重视和关注。例如：第三页，共52页。1.1什么是数据结构

金融和工商企业领域的信息管理系统支持多媒体的文献资料查询 神经元和模式识别网络与通信图形化用户界面等等第四页，共52页。1.1什么是数据结构解决此类问题使用的数学工具已不是分析数学和计算方法，而更多地用到离散数学和计算机的有关知识，所涉及的对象也更为复杂，其突出的特点是：数据元素之间所具有的特定联系已不能用分析数学的方程式来简单描述。

现代计算机科学的观点，计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：第五页，共52页。1.1什么是数据结构信息的表示和信息的处理 信息的表示直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。第六页，共52页。1.1什么是数据结构重要性历史沿革1968年D·E·Knuth发表：“Artofcomputerprogramming”IEEE68教程1983IEEE83教程1991IEEE91教程2000IEEE2000教程国内在78年开设、相应地有93教程等。计算机科技的两大支柱Algorithm+Data

Structures=Programs——NiklausWirthAlgorithm:求解问题的策略DS: 问题的数学模型Programs:为计算机处理问题编制的一组指令第七页，共52页。1.1什么是数据结构实例：银行帐号共100000个如图所示，组成一个顺序存储的结构，存于计算机之中。插入新帐号45怎样进行呢？插入新帐号45：1、查找位置2、移表3、插入合适位置移动一个结点，需100us,移动100000个结点需100us×100000＝10秒。每天处理10000个帐号，需30小时，无法接受。如何快速地进行插入?节省访问外存的时间，是一个很重要的问题。第八页，共52页。1.1什么是数据结构地位：1、“数据结构”在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。第九页，共52页。1.1什么是数据结构事实证明，要想有效地使用计算机，仅掌握计算机语言而缺乏数据结构和算法的有关知识，难以应付众多复杂的应用课题。

第十页，共52页。1.1什么是数据结构一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：

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

structstudent{ charsNo[8]; charsName[9]; intnScore; }astStudent[200];2)基本运算的实现第十三页，共52页。1.1什么是数据结构例2：图书馆书目检索系统自动化问题例3：计算机和人对弈问题例4：多叉路口交通灯的管理问题例5：附设煤气管道的最小费用问题例6：酒店管理系统中的客房分配问题第十四页，共52页。1.1什么是数据结构结论描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现目前，多数高级语言尚不能直接操作这些带结构的数据。我们将在高级语言（C语言）的层次上讨论如何表示这些数据和如何对它们进行操作。第十五页，共52页。1.2基本概念和术语数据(Data)信息的载体能输入到计算机中被计算机程序处理的符号集数据元素(DataElement)数据的基本单位在计算机程序中作为一个整体进行考虑和处理一个数据元素可以由若干数据项(DataItem)组成数据项是具有独立含义的最小标识单位数据对象(DataObject)性质相同的数据元素的集合e.g.C={‘A’,‘B’,…,‘Z’}第十六页，共52页。1.2基本概念和术语-数据结构数据结构(DataStructure)是相互之间存在一种或多种特定关系的数据元素的集合。即带结构的数据对象，它有两层含义：第一，它包括一个具有共同特性的数据元素的集合，即数据对象。第二，它还包括一个定义在这个集合上的一组关系，即数据元素之间的“结构”。第十七页，共52页。1.2基本概念和术语-数据结构数据结构(DataStructure)形式定义Data_Structure=（D,S）D--数据对象S—该对象中各数据元素之间的关系的有限集四个基本的数据结构集合结构：关系集合是空集

顶点元素间无任何关系，R={}空集第十八页，共52页。1.2基本概念和术语-线性结构/树线性结构：元素间的关系是1:1

一个结点（除尾结点外）有且仅有一个直接前驱

一个结点（除头结点外）有且仅有一个直接后继树型结构：一般树、二叉树、森林

一个结点可以有多个直接后继（除叶子结点外），

但只有一个直接前驱（除根结点外）第十九页，共52页。1.2基本概念和术语-图状结构图状结构：元素间的关系是m:n

一个结点可以有多个直接后继，也可以有多个直接前驱注：由于“集合”是数据元素之间关系极为松散的一种结构，因此可用其他结构来表示第二十页，共52页。1.2基本概念和术语-逻辑结构数据结构包括逻辑结构和物理结构数据的逻辑结构研究的是数据元素及其关系的数学特性。特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关与数据元素的相对位置无关分类线性结构：线性表非线性结构：树、图第二十一页，共52页。1.2基本概念和术语-存储结构数据的物理结构（存储结构）研究的是它们在计算机内的实现方法（映象）。（OR）数据结构在计算机中的表示对机器语言：这种实现是具体的对高级语言：在高级语言的层次上来讨论这种实现，用高级语言中的数据类型来描述这种实现细节，不妨称其为虚拟存储结构。依赖于计算机程序设计语言说明：为简明起见，以后我们简称数据结构的逻辑结构——数据结构数据结构的物理结构——存储结构第二十二页，共52页。1.2基本概念和术语-存储结构数据元素之间的关系的表示顺序映像（顺序存储结构）：借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

向量（表格存储结构）非顺序映像（链式存储结构）：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。

单链表、双链表、多重链表、循环链表索引存储结构散列存储结构第二十三页，共52页。1.2基本概念和术语-存储结构说明：四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。因此，我们至少可以得到4×4种可能的物理数据结构：

sequential(sets)

linkedlists

indexedtrees

hashgraphs并不是所有的可能组合都合理第二十四页，共52页。1.2基本概念和术语-存储结构数据的逻辑结构和存储结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构第二十五页，共52页。1.2基本概念和术语-抽象数据类型抽象数据类型数据类型一个值的集合定义在该值集上的一组操作C语言中的基本数据类型intshortcharfloatdouble…

抽象数据类型一个数学模型及定义在该模型上的一组操作如：矩阵+（求转置、加、乘、逆、特征值）

第二十六页，共52页。1.2基本概念和术语-抽象数据类型抽象数据类型定义（D,S,P）D—数据对象

S—D上的关系集

P—对D的基本操作集ADT抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉第二十七页，共52页。1.2基本概念和术语-抽象数据类型抽象数据类型的特征数据抽象

对程序处理的实体的描述强调的是其本质的特征、其所能完成的功能以及它和外部养护的接口(即外界使用它的方法)

数据封装

将实体的外部特性和其内部实现细节分离，并且对外部养护隐藏其内部实现细节

认为DT仅存在于想象之中。注意力集中在感兴趣的性质上，不关心数据的表示形式，操作的具体代码等等。给出规范或说明。第二十八页，共52页。1.2基本概念和术语-抽象数据类型第二十九页，共52页。1.2基本概念和术语数据结构的内容包括三个层次的五个“要素”，如图所示。第三十页，共52页。1.3抽象数据类型的表示与实现通过程序设计语言中的类型来实现C抽象数据类型数据对象 结构体基本操作 函数C++，Java抽象数据类型类class

数据对象数据成员基本操作成员函数(方法)

一个例子第三十一页，共52页。1.3抽象数据类型的表示与实现表示：伪语言借用程序设计语言的结构描述---简洁、严谨忽略程序设计语言的细节---简洁伪C语言与C语言的区别抽象数据类型：typedef赋值：成组赋值、交换赋值选择语句：

switch的扩展输入/输出：可以忽略格式串头文件、辅助变量定义：忽略C的扩展：引入C++的引用参数表示变参第三十二页，共52页。1.3抽象数据类型的表示与实现伪C中的引用参数——C的扩展C的虚实结合：单向的值传递问题：如何简单地表示返回多个值？

C支持的策略： 全局变量、将形参定义为指针类型、将返回值定义为指针类型

C++的另一种处理：引用参数

类型说明符&引用参数名

引用参数与实在参数共享存储单元 利用引用参数表示变参(可以将在被调用函数体中改变了的值代回主调处）第三十三页，共52页。1.4算法和算法分析-定义和特性定义

对特定问题的求解步骤的一种描述，指令的有限序列，其中每一条指令表示一个或多个操作。特性有穷性：算法在执行有穷步后能结束，且每一步都在有穷时间内完成。确定性：每一指令有确切的含义，无二义。且算法只有一个入口和一个出口。可行性：每一操作都可以通过已经实现的基本运算执行有限次来实现输入：零个或多个输入输出：一个或多个输出第三十四页，共52页。1.4算法和算法分析-算法评价标准算法评价标准正确性（Correctness）首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：程序不含语法错误；对于几组输入数据能够得出满足要求的结果；程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；

程序对于一切合法的输入数据都能得出满足要求的结果；通常以第3层意义的正确性作为衡量一个算法是否合格的标准。第三十五页，共52页。1.4算法和算法分析-算法评价标准可读性（Readability）算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序很容易隐藏较多错误而难以调试健壮性（Robustness）当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。——异常处理机制第三十六页，共52页。1.4算法和算法分析-算法评价标准高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。第三十七页，共52页。1.4算法和算法分析-事后统计算法效率的度量一个可执行的正确的算法也有优劣之分，通常以算法执行时在时间和空间资源方面消耗的多寡作为评价算法优劣的标准。事后统计利用计算机内部的计时功能 doublestart,stop;

time(&start);

mainprocess(n,…);

time(&stop);

doublerunTime=stop-start;printf(”%d%d\n",n,runTime);缺陷1、必须执行程序2、其它因素掩盖算法本质（时间统计量依赖于计算机的软硬件环境）第三十八页，共52页。1.4算法和算法分析-时间分析事前分析估算(时间)算法的策略问题规模编程语言编译器产生的机器代码质量机器执行指令的速度第三十九页，共52页。1.4算法和算法分析-时间分析时间复杂度度量定义显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。第四十页，共52页。1.4算法和算法分析-时间分析一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T(n)=O(f(n)) 称T(n)为算法的(渐近)时间复杂度

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

分析：……

由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3

时间复杂度为T(n)=O(n3)第四十三页，共52页。1.4算法和算法分析-时间分析例1-4-2{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。第四十四页，共52页。1.4算法和算法分析-时间分析例1-4-3for(i=1;i<=n;++i){++x;s+=x;}语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。第四十五页，共52页。1.4算法和算法分析-时间分析例1-4-4 for(i=1;i<=n;i=2^i)(1)

{++x;s+=x;}(2)分析：其中基本语句为(2)，设其执行次数为f(n),则2f(n)<=n

故f(n)<=log2n=O(log2n)即时间复杂度为对数阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。（证略）第四十六页，共52页。1.4算法和算法分析-时间分析例1-4-5for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}

语句频度为：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2

)

即此算法的时间复杂度为平方阶.第四十七页，共52页。1.4算法和算法分析-时间分析例1-4-6n！的递归算法intfac(intn){ if(n<=1)return1;(1) elsereturn(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)第四十八页，共52页。1.4算法和算法分析-时间分析