数据结构与算法分析--基础

数据结构与算法分析DataStructureandAlgorithmAnalysis数据结构与算法的基本原理基本的数据结构计算机应用中的各种常用算法计算机领域不同问题的一系列基本算法评价算法的准则和方法设计和分析算法的基本原理、方法和技巧提高分析问题、解决问题的能力主要内容一、什么是数据结构?计算机解决具体问题时，一般经过下列几个步骤：首先要对具体问题进行分析，从中进行模型抽象，然后设计算法，最后编出程序、进行测试、调整直至得到最终解答。问题分析模型抽象算法设计编程、调试得到解答SartajSahni称：“数据结构是数据对象、以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”(《数据结构、算法与应用》)CliffordA.Shaffer的定义是：“数据结构是ADT（抽象数据类型）的物理实现”(《数据结构与算法分析》)LobertL.Kruse将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现（《数据结构与程序设计》）计算机程序是用于对信息进行加工处理的。一般而言，这些信息并不是没有组织的，信息之间往往具有重要的结构关系，这就是数据结构需要研究的内容。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率NiklausWirth：Algorithm+DataStructures=Programs[例1]电话号码查询问题方法1：顺序存储，顺序查找((a1,b1),(a2,b2),(a3,b3),…,(an,bn)）姓名电话号码a1b1a2b2……anbn问题：效率低方法2：有序顺序存储，二分查找(（李1,a1),(李2,a2),…,(王1,ai),(王2,ai+1),…)姓名电话号码李1a1李2a2…………王1ai王2ai+1…………张1ak张2ak+1…………问题：修改不方便方法3：部分有序，建立索引表李1a1李2a2…………姓地址李……王张王1ai王2ai+1…………张1ak张2ak+1………………[例2]文件系统的组织（UNIX为例）[例3]计算机和人对弈⊙××⊙×⊙××⊙⊙×××⊙⊙××⊙×⊙×××⊙×⊙××⊙[例4]交叉路口的交通灯管理问题1、有连线的顶点用不同的颜色标记，表示不能同时通行；2、要求使用的颜色尽可能少，以减少等待时间；3、图论中的着色问题。ABCDABACADBDBCCBBACACD[例5]田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M1、任一选手所选中的项目之间应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。跳远100M标枪铅球200M跳远铅球跳高数据结构研究的是计算机所处理的数据元素之间的结构关系及其操作实现的算法。数据结构研究的具体内容一个具体问题的逻辑数据结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法？一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。数据结构（datastructure）具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为：（1）逻辑结构是从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向问题的。数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。不同的数据结构其操作集不同，但下列操作必不可缺：结构的生成；结构的销毁；在结构中查找满足规定条件的数据元素；在结构中插入新的数据元素；删除结构中已经存在的数据元素；遍历。集合线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（表、串、栈、队列）数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。（树、图）数据的物理结构逻辑结构在计算机存储器中的实现，故又称数据存储结构。(1)顺序（向量）所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。数据的物理结构（续）(3)索引使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。(4)散列通过构造散列函数，用函数的值来确定元素存放的地址。数据结构逻辑结构存储结构运算(操作)线性结构非线性结构集合顺序存储链接存储索引存储散列存储二、什么是算法什么是算法？顾名思义，算法就是计算的办法或法则。这里的计算不只是加减乘除，而是广义的做任何事情的计算，而办法和法则意味着使用它就可以解决需要解决的问题。算法的定义算法通常被定义为一个有穷的指令集，这些指令为解决某一特定问题规定了一个运算序列。（算法是一个定义良好的计算过程，这个过程以一组值作为输入，同时，以一组值作为输出。因此，算法可以看成是将输入转换为输出的一个计算步骤的序列。）从哲学角度看：算法是解决一个问题的抽象行为序列。从技术层面上看：算法是一个计算过程，它接受一些输入，并产生某些输出。从抽象层次上看：算法是一个将输入转化为输出的计算步骤序列。从宏观层面上看：算法是解决一个精确定义的计算问题的工具。算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性：(1)输入作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。(2)输出它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。(3)确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。(4)有穷性对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。(5)有效性（可行性）算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。算法的描述:自然语言、图形、表格、程序设计语言算法的范畴一般包含两方面内容：算法设计与算法分析。前者指根据实际问题制定出有效的算法；后者即是对算法的各种性质进行定性或定量分析从而能够择优选择某种算法。算法设计的要求(1)正确性a.程序中不含语法错误；b.对多个输入能达到满足要求的结果；c.对特定（典型、苛刻、刁难性）的输入能得到满足要求的结果；d.对一切合法的输入都能得到满足要求的结果。(2)可读性易于理解，便于调试（编程和调试、维护分开）(3)健壮性输入非法数据时，作出恰当反应或进行相应处理。(4)时间效率和空间占有量为什么学习算法？算法是计算机的灵魂算法是数学机械化的一部分，能够帮助我们解决复杂的计算问题。算法作为一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑性。算法还能帮助人们理解什么是可行的，什么是不可行的。最重要的，算法本身很有意思，很有趣味算法设计的设计过程方法自顶向下，逐步求精过程把一个具体问题的解决思路转变成一个算法[例6]选择排序问题4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’657697Scanningdirection明确问题：非递减排序解决方案：逐个选择最小数据算法框架：for(inti=0;in-1;i++){//n-1趟从a[i]检查到a[n-1];若最小的整数在a[k],交换a[i]与a[k];}细化程序：程序SelectSort通过演示观察算法执行的过程for(inti=0;in-1;i++){examinea[i]toa[n-1]andsupposethesmallestintegerinata[j];interchangea[i]anda[j];}ProgramSelectionsortalgorithmvoidsort(int*a,constintn)//sortthenintegersa[0]toa[n-1]intonondecreasingorder{for(inti=0;in-1;i++){intj=i;//findsmallestintegerina[i]toa[n-1]for(intk=i+1;kn;k++)if(a[k]a[j])j=k;inttemp=a[i];a[i]=a[j];a[j]=temp;//interchange}}ProgramSelectionsort[例7]二分查找明确问题：假定有n≥1个不同的整数已经按从小到大的顺序存放在数组元素a[0],…,a[n-1]中。我们需要做的是判断整数x是否存放在某个数组元素中，如果是，即x=a[j]，则返回j（被找到元素的下标）；否则返回－1。确定搜索区间的左右边界left和right，不断缩小搜索的区间。初始边界设定为left=0和right=n-1。令middle=(left+right)/2为搜索区间的中心位置元素。如果我们将a[middle]与x比较，其结果有三种可能：1.xa[middle]。这种情况下，如果x存放在这个数组中，则它的位置必然在0和middle-1之间。所以，我们将right设置为middle-1，继续搜索；2.x==a[middle]。找到存放x的位置，返回middle；3.xa[middle]。这种情况下，如果x存放在这个数组中，则它的位置必然在middle+1和n-1之间。所以，我们将left设置为middle+1，继续搜索。算法有两个任务：1.决定搜索区间；2.将x与中间元素a[middle]比较。解决方案：通过演示观察算法执行的过程intBinarySearch(int*a,constintx,constintn)//Searchthesortedarraya[0],…,a[n-1]forx{for(initializeleftandright;whiletherearemoreelements;){letmiddlebethemiddleelement;switch(compare(x,a[middle])){case‘’:setlefttomiddle+1;break;case‘’:setrighttomiddle–1;break;case‘=’:foundx;}//endofswitch}//endoffornotfound;}//endofBinarySearchProgramAlgorithmforbinarysearchcharcompare(intx,inty){if(xy)return‘’;e