数据结构第1章-绪论

第1章绪论

1.1数据结构概述

1.2算法描述与实现1.3算法的评价与分析1.1.1.引言多年来，人类对所有出现过的数据和信息进行了分类处理，从而形成了几种十分重要的数据形式。1.1数据结构概述编号姓名性别民族出生日期工作时间文化程度专业28011李立男汉19641988.9大学图书管理29121张媛媛女汉19702002.8大学机械制造……………………23579王云坤男满族19601981.9硕士数学表1.1某单位的人员情况表1.1.1.引言多年来，人类对所有出现过的数据和信息进行了分类处理，从而形成了几种十分重要的数据形式。1.1数据结构概述1.1.1.引言多年来，人类对所有出现过的数据和信息进行了分类处理，从而形成了几种十分重要的数据形式。1.1数据结构概述1.1.1.引言多年来，人类对所有出现过的数据和信息进行了分类处理，从而形成了几种十分重要的数据形式。1.1数据结构概述1.1.1.引言综上所述，客观世界出现了形形色色的现象和对象，它们不再是数学方程所能描述的形态，而是用表、树、图等来描述的另一类数据结构，当我们用计算机进行处理时，总要寻找一些有效的方法来处理它们，数据结构就是这样的一门综合研究此类非数值计算问题的方法和理论的课程。1.1数据结构概述1.1.2.数据结构有关概念及术语（1）信息（information）：信息（information）是人类为了生存，对各种有用的知识、技能、劳作的记录的总结。它们或使用有形的形式，如图形、文字；或使用无形的东西，如音乐、语言等。（2）数据（data）：数据(data)是对信息的一种符号表示，是指所有能输入到计算机中并被计算机程序处理的符号的总称。它们包括文字、数字、声音、图像等。1.1数据结构概述1.1.2.数据结构有关概念及术语（3）数据元素(dataelement)：是数据的基本单位。（4）数据对象(dataobject)：是相同性质的数据元素的集合，是数据的一个子集；或是某种数据类型元素的集合。（5）数据结构（datastructure）：是相互之间存在一种或多种特定关系的数据元素的集合。或定义为：按照一定逻辑关系组织，并按照一定存储方法存储在计算机中的，且需要定义一系列运算的数据的集合。数据的逻辑结构、存储结构和运算合称数据结构的三要素。1.1数据结构概述1.1.2.数据结构有关概念及术语1.1数据结构概述1.1.2.数据结构有关概念及术语（6）逻辑结构：规定了数据元素之间的逻辑关系，形式如（1）式。Data_Structure=(D,R)（1）（1）式是数据结构的数学表示，它描述了数据元素之间的逻辑关系，所以又称为数据的逻辑结构。数据的逻辑结构由四种结构构成，它们是集合结构、线性结构、树形结构、图形结构。1.1数据结构概述1.1.2.数据结构有关概念及术语（7）存储结构：指数据结构在计算机存储器中的存储映像，又叫做数据的物理结构。存储结构既要反映数据元素本身，还要反映数据元素之间的关系。数据在计算机存储器中一般有两种存储结构，一种是顺序存储结构，一种是链表存储结构。顺序(sequence)结构中每个单元存储数据的值，单元之间的相对位置反映了数据元素之间的关系。链表(linklist)存储结构中，用数据域表示数据元素的值，另外设置一个或多个指针域来表示数据元素之间的关系。1.1数据结构概述1.1.2.数据结构有关概念及术语除了顺序存储和链表存储结构外，还有索引存储结构和散列存储结构。索引(index)存储结构中，在存储所有数据元素的同时，建立附加的关键字索引表，来表示数据元素之间的逻辑关系。散列(hash)存储结构是指根据数据元素的关键字，通过散列函数计算各个数据元素相应的存储地址，存和取都是根据散列函数值来进行。1.1数据结构概述1.1.2.数据结构有关概念及术语（8）运算：运算(operation)是对定义在数据结构之上的数据进行操作的总称。不同的数据结构可能有不同的运算。定义在数据结构上的基本运算有：1）建立：建立某种指定的数据结构。2）清除：把某个指定的数据结构置为空（不存在）。3）插入：在数据结构指定位置上插入一个新的数据元素。1.1数据结构概述1.1.2.数据结构有关概念及术语（8）运算：运算(operation)是对定义在数据结构之上的数据进行操作的总称。不同的数据结构可能有不同的运算。定义在数据结构上的基本运算有：4）删除：在数据结构指定位置上删除一个数据元素。5）更新：修改数据结构中某个数据元素的值。6）查找：在数据结构中查找满足某种条件的数据元素。1.1数据结构概述1.1.2.数据结构有关概念及术语（8）运算：运算(operation)是对定义在数据结构之上的数据进行操作的总称。不同的数据结构可能有不同的运算。定义在数据结构上的基本运算有：7）排序：使数据元素按某种指定的次序重新排列。8）判空和判满：判定某个数据结构是否为空和判定该数据结构是否已达到逻辑上或存储上的最大容量。9）求长：求指定的数据结构中数据元素的个数。1.1数据结构概述1.1.3.数据类型用计算机来处理自然界的具体数据对象时，为了方便处理，需要把不同性质的数据加以分类，在各类数据上定义特定的运算，并规定在该类数据上的运算产生的数据也具有该类数据的性质（相同的类型），并根据数据类型来决定在存储器中划分多大的空间来存储该类型的数据。因此说，数据类型是一个值的集合和定义在该值集上操作的总称。1.1数据结构概述1.1.3.数据类型数据类型分为基本类型和构造类型。基本类型主要有：整型、浮点型、字符型。构造类型主要有：数组、表、集合、自定义。如Python语言中的int、float、bool是基本类型，list、set、dict是构造类型。构造类型可以由不同的基本数据类型复合定义。所以基本类型又叫作原子类型（不可再分割），构造类型又叫作结构类型。1.1数据结构概述1.1.3.数据类型除了数据类型外，还有一种称为抽象数据类型（abstractdatatype，ADT），它只定义基于逻辑类型的数据类型，以及定义在该数据类型上的一组操作，只考虑逻辑结构和运算，而不考虑其存储结构。抽象数据类型与计算机存储器内部的表示和实现无关。1.1数据结构概述第1章绪论

1.1数据结构概述 1.2算法描述与实现1.3算法的评价与分析1.2.1算法的概念与特性1.算法的定义算法（Algorithm）是建立在数据结构基础之上的，求解问题的一系列规则的有限步骤。换句话说，算法就是计算机解题的过程。这个过程中首先要有解题思路，然后才是编写程序，前者叫“推理”的算法，后者叫“操作”的算法。1.2算法的描述与实现算法1.1欧几里德算法给定两个正整数m和n，寻找它们的最大公约数，即，可以同时整除m和n的最大正整数。算法描述如下：①输入两个正整数m，n，且m>n；②令r等于m除以n的余数；③令m←n，n←r，如果r≠0则返回②；否则，运算结束，返回m。1.2算法的描述与实现算法1.1欧几里德算法此算法用伪语言描述如下：算法1.1欧几里德算法1.2算法的描述与实现AlgorithmEuclid(m,n)#计算m,n的最大公约数,m,n由调用函数赋值，且m>n。

r←mmodnwhile(r≠0)m←nn←rr←mmodn输出m1.2.1算法的概念与特性2.算法的特性（1）有穷性：一个算法必须总是在执行有穷步骤之后结束，且每一步都在有穷时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法只有唯一的一条执行路径（相同的输入只能有相同的输出）。1.2算法的描述与实现1.2.1算法的概念与特性2.算法的特性（3）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。（4）输入：一个算法有至少1个或多个输入，这些输入取自某个特定的对象的集合。算法1.1中输入了两个整数m，n。1.2算法的描述与实现1.2.1算法的概念与特性2.算法的特性（5）输出：一个算法有零个或多个输出，这些输出是与输入有某种特定关系的量。算法1.1输出正整数m和n的最大公约数d。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程（1）分析待求解的问题。（2）通过程序流程图或者伪代码表达算法步骤。（3）将算法编写成可运行的程序。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程为了对算法的设计有一个大概的理解，我们讨论一个实例来说明算法的设计过程。在算法设计中，有时需要流程图。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程例1.2对一批正整数（N0,N1,……Nm）进行分类，要求如下：①当Ni≤20时，归类为第一类；②当20<Ni≤50时，为第二类；③当50<Ni≤100时，为第三类；④当100<Ni时，为第四类。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程例1.2对一批正整数（N0,N1,……Nm）进行分类。解：（1）分析这是一个简单的分类问题，可以用条件语句进行判断，算法描述为：①输入Ni；②如果Ni<=20，x1++；1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程例1.2对一批正整数（N0,N1,……Nm）进行分类。解：（1）分析③如果Ni>20并且Ni<=50，x2++；④如果Ni>50并且Ni<=100，x3++；⑤如果Ni>100，x4++；⑥如果i<m转①，否则结束。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程例1.2对一批正整数（N0,N1,……Nm）进行分类。解：（2）画出程序流程图把上面分析中的描述转化为流程图，如图1.7所示。1.2算法的描述与实现1.2.2算法的设计与实现1.算法的设计过程例1.2对一批正整数（N0,N1,……Nm）进行分类。解：（3）算法设计本书中采用Python语言作为描述语言，则此问题的算法为：1.2算法的描述与实现defsort(m):#对m个正整数进行分类

i=0x1=0;x2=0;x3=0;x4=0whilei<m:n=int(input("请输入一个正整数："))ifn<=20:x1+=1elifn<=50:x2+=1elifn<=100:x3+=1else:x4+=1i+=1print(x1,x2,x3,x4)1.2.2算法的设计与实现2.算法与程序算法一般分为两个层面，一个是“推理”的算法，一个是“操作”的算法。“推理”的算法实际上就是解题思路，美其名曰“解题的数学模型”。推理的算法可以用自然语言、流程图来、伪语言来描述。但是只有“推理”的算法，还不能让计算机解题，所以，要把“推理”算法转变成“操作”算法。要实现操作算法，就需要程序设计语言的支持，因此，我们讲的算法的实现是把“推理”算法转化成“操作”算法的过程。1.2算法的描述与实现1.2.3算法的设计与实现2.算法与程序为了说清楚算法和程序的区别，我们用算法1.1为例进行简单对比。算法1.1可以用Python语言来描述如下:算法1.1a欧几里德算法1.2算法的描述与实现defEuclid(m,n):#计算m,n的最大公约数,m>n。

whiler:r=m%nm=nn=rreturnn这个算法在计算机上调试时，不能通过（请思考原因），因此只能称为算法。算法1.1b欧几里德算法defEuclid(m,n):#计算m,n的最大公约数,m,n由调用函数赋值。

ifm<n:m,n=n,mr=1whiler:r=m%nm=nn=rreturn

n算法1.1b可以在计算机上直接调试通过，因此称为程序。1.2.3算法的设计与实现2.算法与程序因此，对于一个要求用计算机处理的实际问题，我们可以得出其解题过程的“三步曲”：首先分析问题得出其“推理”算法；继而形式化地给出“操作”算法；最后根据算法转化为程序设计语言编写的程序以获得答案，这叫作算法的实现。我们自始至终都把主要注意力放在这“三步曲”的前两步，最后一步主要由读者通过上机实训的办法验证性地完成。1.2算法的描述与实现第1章绪论

1.1数据结构概述 1.2算法描述与实现1.3算法的评价与分析1.3.1.评价标准1.算法设计的要求（1）正确性：能够确保对于某种相对程度的随机输入有正确的输出。（2）可读性：算法描述清晰易懂，便于修改和移植，有利于阅读者对程序的理解。（3）健壮性：算法应该具有容错处理，当输入非法数据时，算法能适当做出反应或执行处理，而不会产生莫名其妙的输出结果。1.3算法的评价与分析1.3.1评价标准（4）效率：效率指的是算法的执行时间。算法的执行效率可以用算法的时间复杂度度量。（5）存储量需求：指算法执行过程中所需要的最大存储空间。算法的存储需求用算法空间复杂度来度量。1.3算法的评价与分析1.3.1评价标准2.算法分析的目的衡量一个算法的优劣主要看算法的执行效率，算法的时间复杂度和空间复杂度分析叫算法分析，其目的是考察算法的运行时间和空间占有情况，以求改进算法或对不同算法的效率进行比较。1.3算法的评价与分析1.3.2算法的时间复杂性1.大O符号设函数f(n)和g(n)是正整数n的实函数，如果存在实常数c>0和整常数n0≥1,对于每个n≥n0的整数,满足f(n)≤cg(n)，则称f(n)是O(cg(n))。这个定义称为大O符号。有时又称函数f(n)的阶至多是O(g(n))，换句话说，O(g(n))是函数f(n)的一个上界。读作“f(n)是g(n)的大O”。1.3算法的评价与分析1.3.2算法的时间复杂性2.时间复杂度一般情况下，算法的执行时间随输入大小的增加而增大。如果，算法中所有语句的频度（指该语句在算法中被重复执行的次数）之和记为T(n)，它也是该算法所求解问题规模n的函数，称为该算法的时间复杂度。当问题规模n趋向无穷大时，T(n)的数量级称为该算法的渐进时间复杂度（asymptotictimecomplexity），记为T(n)=O(f(n))，我们使用大O符号来描述渐进时间复杂度，称“T(n)是f(n)的大O”。1.3算法的评价与分析1.3.2算法的时间复杂性3.算法的时间复杂度分析1)典型语句度量法：典型语句度量法是用算法中的支配性语句来估算它的运行时间。例1.5分析下面冒泡排序算法的时间复杂度。

defbubble_sort(a):foriinrange(len(a)-1,-1,-1):forjinrange(i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]returna1.3算法的评价与分析解：if条件句是关键语句，若a[i]已经从大到小排好序，则只需一趟比较就结束，此时T(n)=O(n)。对于任意情况，if条件的执行次数分析如下：当i=1时，进行n-1次比较和交换；当i=2时，进行n-2次比较和交换；……当i=n-1时，进行1次比较和交换。共执行1+2+3+….(n-1)=n(n-1)/2次，所以T(n)=O(n2)。因为它抓住if条件句，根据这个典型语句的执行次数进行分析。1.3.2算法的时间复杂性3.算法的时间复杂度分析1.3算法的评价与分析1.3.2算法的时间复杂性3.算法的时间复杂度分析2)分段估算法：把算法分成不同的段，每个段有一个f(n)，算法的运行时间是各个段的f(n)的和，这叫做分段估算法。1.3算法的评价与分析1.3.2算法的时间复杂性3.算法的时间复杂度分析分段估算法是一种常见的时间复杂性计算方法。例1.6分析下面程序段的时间复杂度。

foriinrange(1,n+1): #①s+=1 #②forjinrange(1,2*n+1): #③t+=1 #④1.3算法的评价与分析1.3.2算法的时间复杂性3.算法的时间复杂度分析解：给每个语句标上标号，每个标号为一段。语句①的频度：n+1②的频度：n③的频度：n*(2n+1)④的频度：n*2n所以，语句频度T(n)=n+1+n+n*(2n+1)+n*2n=4n2+3n+1

即:T(n)=O(n2)。1.3算法的评价与分析1.3.2算法的时间复杂度3.算法的时间复杂度分析3)分层估算法：当算法中出现多层结构时，如出现了多重循环结构，外层与内层的关系是相乘的关系，此时分别计算各层的时间复杂性，然后相乘，即为该算法的时间复杂度。例1.7分析下面程序段的时间复杂度。foriinrange(1,n+1):forjinrange(1,i+1):forkinrange(1,j+1):s+=11.3算法的评价与分析1.3.2算法的时间复杂度