第1章绪论

null数 据 结 构 课程数 据 结 构 课程教材：数据结构（国防工业出版社） 学时：讲课42(学时) 上机12(学时) 教师：夏克俭 课程目录课程目录第一章：绪论（2学时） 第二章：线性表（4学时） 第三章：栈和队列（5学时） 第四章：字符串（自学） 第五章：数组和广义表（4 学时） 第六章：树（8学时） 第七章：图（8学时） 第八章：查找（6学时） 第九章：排序（5学时） 第十章：文件（自学）第一章 绪论第一章 绪论 目前，计算机业在飞速发展，其应用领域也早不限于科学计算，而是广泛深入到社会的各个部门。从应用的角度来看，计算机在各部门的应用大致可归纳为以下几类： （1）科学计算与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 （2）计算机管理 （3）计算机实时控制 （4）计算机辅助 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 /制造（CAD/CAM）及绘图 （5）计算机通讯网络 （6）办公自动化 （7）人工智能 （8）机器仿真 （9）计算机辅助教育（CAI）和娱乐绪论（续）绪论（续） 随着计算机应用的广泛深入，计算机应用领域会越来越广，计算机要处理的数据更加多样化，而数据之间的关系和对数据处理的要求也更为复杂。这就要求我们在从事具体的计算机应用时，要用较科学的方式描述、存储和处理数据，从而使计算机高效率地去完成预期的任务。 本章主要讨论数据结构、算法及算法分析方面的一些基本概念。 1.1 数据结构研究的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 和方法1.1 数据结构研究的内容和方法1.1.1 数据结构的含义 数据结构（Data Structure）简称DS，研究的是计算机所处理数据元素间的关系及其操作实现的算法。包括数据的逻辑结构、数据的存储结构以及数据的操作。 数据结构在计算机科学中涉及到计算机硬件（特别是编码理论、存储机制等）、计算机软件的研究(无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题)。数据结构的含义数据结构的含义 因此可以认为，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，如图1.1：1.1.2 数据结构研究的内容1.1.2 数据结构研究的内容1. 数据的逻辑结构（Logical Structure） 指数据元素之间的逻辑关系。 数据（Data），客观事物的符号表示。是指输入到计算机并能被计算机程序处理的符号的总称。如方程中的整数、实数，源程序中的字符串，以及文字、图像和声音信号等等，都可作为计算机中的数据。 数据元素（Data Element），数据的基本单位。简单的数据元素可以是整数、字符等形式。一般，数据元素由若干个数据项（Data Item）组成，常称为记录（Record）。数据的逻辑结构（续）数据的逻辑结构（续） 例如表1.1的图书管理表，其中 a1，……，an对应的每一行各是一个数据元素，而编号、书名等就是数据项。在计算机存取数据时，数据项是不可分割的最小存取单位。 表1.1 图书管理表 a1 a2 . . an数据的逻辑结构（续）数据的逻辑结构（续） 上表（List）中每一行为一个数据元素（或记录），记为ai(1≤i≤n)，元素之间呈现的是一种线性关系。此表可表示为： list = (a1,a2,……,an) 显然表中每一数据元素包含的许多值是非数值性的（如文字、日期等数据），对其进行的操作（或运算）也不再是加、减、乘、除等数学运算，而是诸如： 查询（查找一本书的信息）、 插入（增加一本书的信息）、 修改（某书修订后，修改元素中某些信息）、 删除（某书不再版了，做删除标记）、 分类（按某数据项的值建立索引） 等这样的运算。数据的逻辑结构（续）数据的逻辑结构（续） 具有相同性质的数据元素组成的集合，称为数据对象（Data Object），它是数据的一个子集。 计算机要处理的数据元素不是相互孤立的，而是有着各种各样的联系，这种数据元素之间的关系就称作逻辑结构。根据数据元素之间关系的不同特性，归纳出四类基本的逻辑结构： （1）集合 结构中的数据元素除了“属于同一集合”的关系外，没有其他关系（如例1–1）。 （2）线性结构 数据元素之间存在一对一的关系（如例1–2）。 （3）层次结构 数据元素之间存在一对多的关系（如例1–3）。 （4）网状结构 数据元素之间存在若干个多对多关系（如例1–4）。例1-1 集合例1-1 集合 例1–1 学校举办了英语演讲比赛和歌曲演唱比赛，参赛者可以获得优胜奖和参与奖。问多少学生在两个竞赛中都获得了优胜奖？求解这个问题可以将在两个竞赛中获得优秀奖的人分别构成一个整体，问题便成了求两个集合的交集。例1-2 表例1-2 表例1–2 到医院看病的病人需要排队，而医院实行先来先服务的原则。每个病人都有自己的病历，病历上有病历的编号还有病人的其他具体信息。如表1.2所示。 表1.2 病人信息表 这张表中的元素存在一个顺序关系，即谁在谁前，谁在谁后的信息（即病人诊断顺序依次为张立，田方，……） 。所以，可以用线性结构来刻画这种关系。例1-3 大学系级行政机构例1-3 大学系级行政机构 大学系级行政机构，如图1.2所示： 其中系、办公室、……教师、学生可视为数据元素。元素之间呈现的是一种层次关系，即系级下层机构为办公室、教研室和班级，而办公室、教研室和班级等单位又由若干个管理人员、教师、实验员和学生组成。系例1-4 田径比赛的时间安排问题例1-4 田径比赛的时间安排问题 设田径比赛项目有：A(跳高)、 B(跳远)、C(标枪)、D(铅球)、E(100m跑)、F(200m跑)。参赛选手的项目表如下： 问如何安排比赛时间，才能使得 ： (1)每个比赛项目都能顺利进行（无冲突）； (2) 尽可能缩短比赛时间。 例1-4（续）例1-4（续） 此问题可归纳为图的“染色“问题：设项目A∽F各表示一数据元素，以○表示。若两个项目不能同时举行，则将其连线。由此得到如图1.3所示的结构。若用四种颜色表示四个时间段，一种着色方案如图所示。 图1.3 即：红色时间段(如8~10点)—A、C项目；浅蓝— B、D项目；深蓝— E项目； 紫色—F项目。数据逻辑结构（续）数据逻辑结构（续） 上面的例子中所描述的逻辑结构都是从具体问题中抽象出来的数据模型，是独立于计算机存储器的。数据元素并不是孤立存在的，它们之间存在着某种关系（或联系、结构）。对于例1-2，数据元素之间呈现的是一种线性关系，或线性(linear)结构；对于例1-3，呈现的是一种层次关系，或树(Tree)结构；对于例1-4，呈现的是一种网状关系，或图(Graph)结构。如图1.4所示。 （线性关系） （层次关系） （网状关系） 图1.42．数据的存储结构（或物理结构）（Physical Structure）2．数据的存储结构（或物理结构）（Physical Structure） 数据结构在计算机中的表示（映像）称为数据的存储结构或物理结构，它包括数据元素的表示和关系的表示。 数据元素的表示 计算机中表示信息的最小单位是比特（Bit），即二进制数中的一位。数据元素由若干位组成的位串来表示，通常称这个位串为节点（Node）或元素（Element）。当数据元素由若干数据项组成时，数据项的取值范围称为数据域（Data Field）。 关系的表示 在存储器物理位置上如何反映数据元素之间的关系。目前，对一个数据结构常用的有四种存储表示： （1）顺序存储 （Sequential Storage ）：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中（如c语言的一维数组）。如表 L=(a1,a2，……,an)的顺序结构如图1.5所示。数据的存储结构（续）数据的存储结构（续）图1.5 (存储器) （2）链式存储（Linked Storage）：将数据结构中各元素分布到存储器的不同点(称为节点)，用地址（或链指针）方式建立它们之间的联系，由此得到的存储结构为链式存储结构。如表L=(a1,a2，……,an)的链式存储结构如图1.6： 链式结构是本课程的一个重点，因为元素之间的关系在计算机内部很大程度上是通过地址或指针来建立的。 （3）索引存储（Indexed Storage）：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。 数据的存储结构（续）数据的存储结构（续）例1-5 电话号码查询问题。 为便于提高查询的速度，在存储用户数据文件的同时，建立一张姓氏索引表，如图1.7所示。这样，查找一个电话就可以先查找索引表，再查找相应的数据文件，无疑加快了查询的速度。 数据文件 索引表数据的存储结构（续）数据的存储结构（续） （4）散列存储(Hash Structure)： 根据数据元素的特殊字段(称为关键字key)，计算数据元素的存放地址，然后数据元素按地址存放，所得到的存储结构为散列存储结构(或Hash结构)。 3. 数据的操作 一般而言，必须对数据进行加工处理，才能得到问题的解。在非数值性问题中，对数据的操作（或运算）已不限于对数据进行加、减、乘、除等数学运算。数据的操作是定义在逻辑结构上的，而操作的具体实现是在存储结构上进行的。基本的数据操作主要有以下几种： （1）查找：在数据结构中寻找满足某个特定条件的数据元素的位置或值。数据的操作数据的操作（2）插入：在数据结构中添加新的数据元素。 （3）删除：删去数据结构中指定的数据元素。 （4）更新：改变数据结构中某个数据元素一个或多个数据项的值。 （5）排序：重新安排数据元素之间的逻辑顺序，使之按（某个数据项的）值由小（大）到大（小）的次序排列。 其中，查找是一种引用型操作，即它不改变现有结构，而其余四种均会改变现有结构，被称为加工型操作。 综上所述，数据结构是一门研究非数值计算的程序设计中计算机操作的对象以及它们之间关系和操作的学科。在本书中，对数据结构的详细讨论，都是从数据的逻辑结构、数据的存储结构和对数据的操作这三方面展开的，读者应掌握住这个规律，以便以后知识的学习。1.1.3 研究数据结构的方法1.1.3 研究数据结构的方法 研究数据结构是为了编写解决问题（或完成任务）的程序。用计算机求解一个实际问题的过程，一般可以用图1.8所示的模型加以描述。 图1.8 计算机求解问题的流程 即首先要从现实问题出发，抽象出一个适当的数学模型，然后设计一个求解此数学模型的算法，最后根据这个算法编出程序，经过测试、排错、运行直至得到最终的解答。现实问题、数学模型、算法和程序是问题求解过程中出现的四个重要环节。 1.2 抽象数据类型的表示与实现1.2 抽象数据类型的表示与实现 抽象数据类型（Abstract Data Type, 简称ADT）是指一个数据结构以及定义在其上的一组操作。本书采用类C语言作为描述算法，这使得数据结构的描述和讨论简明清晰，不拘泥于C语言的细节，又容易转换为C或C++程序。以下面的形式描述ADT： ADT=（D，R，P） 其中，D是数据元素的有限集；R是D上关系的有限集，（D，R）构成了一个数据结构；P是对该数据结构的基本操作集。用以下格式定义抽象的数据类型： ADT 抽象数据类型名{ 数据元素集：< 元素集的定义 > 数据关系集：< 关系集的定义 > 基本操作集：< 基本操作的定义 > } ADT 抽象数据类型名；抽象数据类型抽象数据类型 其中，基本操作的定义格式是： 基本操作名(参数表) 初始条件：< 初始条件描述 > 操作结果：< 操作结果描述 > 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&开头，除了可提供输入值外，还可返回操作结果。“初始条件”描述了操作执行之前的数据结构及参数应满足的条件，“操作结果”说明了操作正常完成之后，数据结构的变化和应返回的结果。 1.3 学习数据结构的目的1.3 学习数据结构的目的1.3.1 数据结构的发展简史及在计算机科学中的地位 数据结构的内容来源于图论、操作系统、编译系统、编码理论和检索与分类技术的相关领域。20世纪60年代末，美国一些大学把上述领域中的技术归纳为《数据结构》课程。美国人D.E.克劳特《计算机程序设计技巧》一书，对数据的逻辑结构、存储结构及算法进行了系统的阐述。我国从70年代末在各大专院校陆续开设数据结构课程，目前该课程已经是计算机专业的核心课程之一。 关于计算机科学的概念，计算机界的权威人士认为： 其一，计算机科学是信息结构转换的科学，构造有关信息结构的转换模型，对其进行研究是计算机科学中最根本性的问题。而构造出现实问题中的数据结构模型，并合理地将其映象到计算机存储装置中，是这种观点的具体体现。学习数据结构的目的学习数据结构的目的 其二，计算机科学是算法的学问，研究的是对数据处理的方法或规则。要用计算机完成具体任务，离不开对算法的研究。因而，“数据结构”+“算法”是计算机科学研究中的基础课题，其理论基础是离散数学中的图论、集合论和关系理论等等，实践基础是程序设计技术。 1.3.2 学习数据结构的目的 在分析、开发系统与应用软件中要用到的数据结构知识。 如操作系统、编译系统、数据库和人工智能中涉及到：栈和队列、存储管理表、目录树、语法树、索引树、搜索树、散列表、有向图等等。 学习数据结构是为了提高程序设计水平。 我们知道，不论计算机从事哪方面的应用，一般都是由计算机运行程序来实现的，而任何一个程序都是建立和运行在相应的数据结构基础上的。这就要求在做程序设计时，一方面要描述好对应的数据结构，另一方面要设计正确、精确和快速处理数据的算法（或程序）。做到这两点，无疑程序设计水平将会有一个大的提高。1.4 算法的定义及其特性1.4 算法的定义及其特性1.4.1 算法的定义 算法（Algorithm）是一个有穷规则（或语句、指令）的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。 例1-6 求两正整数m、n的最大公因子的算法如下： ① 输入m,n； ② m/n（整除），余数→r (0≤r≤n)； ③ 若r=0,则当前n=结果，输出n,算法停止；否则，转④； ④ n→m,r->n； 转②。 如初始输入 m=10,n=4,则m,n,r 在算法中的变化如下： m n r 10 4 2 4 2 0(停止) 即10和4 的最大公因子为2。算法特性算法特性1.4.2 算法的性质 (1)    有穷性 —— 算法执行的步骤（或规则）是有限的； (2)    确定性 —— 每个计算步骤无二义性； (3)    可行性 —— 每个计算步骤能够在有限的时间内完成； (4)    输入 —— 算法有一个或多个外部输入； (5)    输出 —— 算法有一个或多个输出。 这里要说明的是，算法与程序有联系又有区别。二者都是为完成某个任务，或解决某个问题而编制的规则（或语句）的有序集合，这是它们的共同点。区别在于：其一，算法与计算机无关，但程序依赖于具体的计算机语言。其二，算法必须是有穷尽的，但程序可能是无穷尽的。其三，算法可忽略一些语法细节问题，重点放在解决问题的思路上，但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。另外，在设计算法时，一定要考虑它的确定性，即算法的每个步骤都是无二义性的（即一条规则不能有两种以上的解释）。 例1-6 中的算法转换成C语言例1-6 中的算法转换成C语言将例1-6中的算法转换成C语言程序如下： #include “stdio.h” int maxog(); main() { int m,n, j; char flag=‘Y’; while(flag==‘y’||flag==‘Y’) { printf(“\n”); scanf(“input=%d%d”,&m,&n); //输入两个整数m,n if (m>0&&n>0 ) { j=maxog(m,n) ; //求m,n的最大公因子 printf (“output=%d\n”,j); } //输出结果 printf (“continue?(y/n)”); flag=getchar(); //输入’y’或’Y’继续，否则停止 } }算法转换成C语言算法转换成C语言 int maxog(int m, int n) //求m、n的最大公因子算法（或函数） { int r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return(n); } 以后章节中的算法均以C语言的函数形式描述，而main()和数据I/O就不描述了。另外，由于某种原因（如参数错，存储分配失败等）导致算法无法继续执行下去时，约定调用函数ERROR()进行出错处理。 讨论了数据结构与算法的基本概念后，有必要提到瑞士科学家沃思（N.Wirth）的著名公式：数据结构+算法=程序 数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来；而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都做出了具体的设计，就相当于完成了相应的程序。 1.4.3 算法的设计目标1.4.3 算法的设计目标算法的设计应满足以下五点： 正确性 算法应当满足具体问题的需求，一般包括对输入、输出、处理等的明确的无歧义性的描述。 可读性 可读性有助于对算法的理解及帮助排除算法中隐藏的错误，也有助于算法的交流和移植。 健壮性 当输入不合法的数据时，算法应能做出相应的处理，而不产生不可预料的结果。 高效率 算法的效率指算法执行时间的长短，称作算法的时间复杂度。 低存储量需求 算法的存储量需求指算法执行期间所需要的最大存储空间，称作算法的空间复杂度。 1.4.4算法效率的度量1.4.4算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。这个时耗与下面因素有关： 书写算法的程序设计语言； 编译产生的机器语言代码质量； 机器执行指令的速度； 问题的规模。 这四个因素中，前三个都与机器有关。当度量一个算法的效率抛开具体的机器、仅考虑算法本身的效率高低时，算法效率仅与问题的规模有关，也就是说，算法效率是问题规模的函数。为了详细描述这个函数，我们引入以下几个概念： 1.语句的频度(Frequency Count) 语句频度定义为可执行语句在算法（或程序）中重复执行的次数。若某语句执行一次的时间为t，执行次数为f，则该语句所耗时间的估计为 t·f。例1-7 求两个n 阶方阵乘积例1-7 求两个n 阶方阵乘积  c[0][0] c[0][1] ··········· c[0][j] ··········· c[0][n-1] c[1][0] c[1][1] ··········· c[1][j] ··········· c[1][n-1] ··········· Cn·n=An·nBn·n= ··········· c[i][0] c[i][1] ··········· c[i][j] ··········· c[i][n-1] ··········· c[n-1][0] c[n-1][1] ······· c[n-1][j] ······· c[n-1][n-1] 其中： n-1 c[i][j] = ∑A[i][k]B[k][j] k = 0 例1-7 （序）例1-7 （序） void MATRIXM(A,B,C) float A[n][n], B[n][n], c[n][n]; { int i,j,k; 语句频度 for(i=0;i∞时，lim(T(n)/n3)=2，故T(n)与n3为同阶无穷大，或说T(n)与n3成正比、T(n)的量级为n3，记为：T(n)=O(n3) 。例1-8 在数组中查找例1-8 在数组中查找 在数组（A[1],A[2],..........,A[n]）中查找最后一个与给定值k相等的元素的序号的算法。 int search(datatype A[n+1], datatype k) { int i=n; A[0]=k; while(i>0&&A[i]!=k) i--; return(i); } 本例应以平均查找次数为算法的T(n)。设查找每个元素的概率pi(1≤i≤n)均等，即pi=1/n，查找元素k时，k与A[i]的比较次数（即执行while循环语句的次数）Ci=n-(i-1)，则查找次数的平均值（或期望值）： 因n->∞时，lim(T(n)/n)=1/2 ，故T(n)=O(n)，此时又称T(n)为算法的渐进时间复杂度。 T(n) =T(n)的量级T(n)的量级T(n)的量级通常有： O(c)——常数级，不论问题规模多大，T(n)一致，因而是理想的T(n)量级； O(n)——线性级；O(n2),O(n3)——平方、立方级； O(log2n),O(n*log2n) —— 对数、线性对数级； O(2n)——指数级，时间复杂度最差。 以上几种常见的T(n)随n变化 的增长率如图1.9所示：算法分析算法分析 对较为复杂的算法，可分段分析其时间复杂度。如某算法可分为两部分，其时间复杂度分别为： T1(n)=O(f(n)) , T2(n)=O(g(n)) 此时两部分问题的体积一致，则总的T(n)=T1(n)+T2(n)=O(max(f(n),g(n)), 表示取f(n)、g(n)中最大者。 但若T1(m)=O(f(m)), T2(n)=O(g(n)),两部分的体积不一致，则： T(m,n)= T1(m)+ T2(n)=O(f(m)+g(n))。 另外，算法空间复杂度的定义： 设算法对应问题的体积（或规模）为n,执行算法所占存储空间的量级为D(n)，则D(n)为算法的空间复杂度(Space Complexity)。第一章小结第一章小结 DS第一章作业第一章作业 1.试用DS=（D，R）形式说明字符串: S=“s1, s2,……, sn”(si ∈char) 是一个数据结构，即S=（D，R）中 D=？R=？ 2.设五叉口： 其中E、C道为单行线。试构造使该路口行驶车辆不碰撞的交通管理模型。 （提示:找出路口各行车路线(AB,BC,….),若两行车路线不能对驶,则将其连线。) 3.设n为正整数，求下列算法段的时间复杂度，即T(n)=O(?) (1) i=1; k=0; (2) i=1; j=0; (3) for(i=n-1; i>=1; i--) while(ij) j++; {temp=A[j];A[j]=A[j+1]; else i++; } A[j+1]=temp;}