数据结构与算法-2014年2月21日课堂introfeb

数据结构与算法主讲教员:段凌宇2014年2月21日

北京大学信息科学与技术学院，转载或翻印必究北京大学信息学院，转载或翻印必究Page22月19日课程回顾数据的逻辑结构（结点+关系）线性结构（linearstructure）树型结构（treestructure）图结构（graphstructure）数据的存储结构(结点+关系->存储器的映射）顺序(sequential)链接(linked)索引(indexing)散列(hashing)数据的运算(算法->程序->解决问题）北京大学信息学院，转载或翻印必究Page3数据的存储结构用数学上的映射来表示，数据的存储结构是建立一种映射，对于数据逻辑结构（K,r）,其中r∈R对它的结点集合K建立一个从K到存储器M的单元的映射：K→M，对于每一个结点j∈K都对应一个唯一的连续存储区域c∈M。每一个关系元组（j1,j2）∈r（其中j1,j2∈K是结点），亦即j1,j2的逻辑后继关系应映射为存储单元的地址顺序关系（或指针的地址指向关系）。四种基本存储映射方法：顺序、链接、索引、散列北京大学信息学院，转载或翻印必究Page4索引（indexing）的方法索引法是顺序存储法的一种推广，它也使用整数编码来访问数据结点位置索引方法是要建造一个由整数域Z映射到存储地址域D的函数Y：ZD，把结点的整数索引值

z∈Z映射到结点的存储地址

d∈D。它称为索引函数，一般而言它并不象数组那样，是简单的线性函数。当数据结点长度不等的情况下，索引函数就无法用线性表达式给出北京大学信息学院，转载或翻印必究Page5索引（indexing）的方法为了构造任意的索引函数，可以为索引函数提供附加的存储空间，称为索引表S索引表中每一元素是指向数据结点的指针。因为索引表S由等长元素（指针）组成，所以可以进行线性的索引计算： 始址(元素S[i])＝ 始址(元素S[0])＋i（指针尺寸）通过上述公式，由索引号i可以计算出索引表中的单元S[i]的始址，再通过读出S[i]元素的内容（是指针），访问真正需要访问的数据结点北京大学信息学院，转载或翻印必究Page6索引（indexing）的方法索引方法也付出了存储开销，其数据结点要附加用于指针的存储空间。索引方法在程序设计中是一种经常使用的方法，其主要原因是对于非顺序的存储结构来说，使用索引表是快速地由整数索引值找到其对应数据结点的唯一方法北京大学信息学院，转载或翻印必究Page7散列（hashing）的方法散列方法是索引方法的一种延伸和扩展利用一种称为散列函数(hashfunctions)

进行索引值的计算，然后通过索引表求出结点的指针地址散列函数是将字符串s映射到非负整数z的一类函数h:SZ，对任意的s∈S，散列函数h(s)=z，z∈Z北京大学信息学院，转载或翻印必究Page8散列（hashing）的方法telephonenumbers,carlicenseplates,invoicenumbers,etc.Ahashfunctionisanywell-definedprocedureormathematicalfunctionthatconvertsalarge,possiblyvariable-sizedamountofdataintoasmalldatum,usuallyasingleintegerthatmayserveasanindextoanarray.Thevaluesreturnedbyahashfunctionarecalledhashvalues,hashcodes,hashsums,orsimplyhashes.Hashfunctionsaremostlyusedtospeeduptablelookupordatacomparisontasks—suchasfindingitemsinadatabase,detectingduplicatedorsimilarrecordsinalargefile,findingsimilarstretchesinDNAsequences,andsoon.北京大学信息学院，转载或翻印必究Page9第一章概论1.1为什么要学习数据结构1.2什么是数据结构1.3

抽象数据类型1.3.1什么是抽象数据类型1.3.2示例1.3.3类1.3.4类模板附：1.3.5动态内存分配;1.3.6C与C++语言的输入输出语句1.4算法的特性及分类1.5算法的效率度量1.6数据结构的选择和评价北京大学信息学院，转载或翻印必究Page101.4算法及其特性算法(algorithms)是为了求解问题而给出的清晰指令序列程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解一个求解问题通常用该问题的输入数据类型和该问题所要求解的结果（算法的输出数据）所应遵循的性质来描述例子：

基于“模拟退火”算法和“遗传”算法，求解旅行商问题(travelingsalesmanproblem)的源程序北京大学信息学院，转载或翻印必究Page111.4.1算法及其特性一定的通用性(Universality)对于那些符合输入类型的任意输入数据，都能根据算法进行问题求解，并保证计算结果的正确性。算法的有效性(Effectiveness)算法是有限条指令组成的指令序列，其中每一条指令都必须是能够被确切执行的，被人或机器所执行。指令的类型应该明确规定，仅限于若干明确无误的指令动作，是一个有限的指令集。其结果应具有确定的数据类型，是能够预期的。北京大学信息学院，转载或翻印必究Page121.4.1算法及其特性算法的确定性(Definiteness)算法每执行一步之后，关于它的下一步，应该有明确的指示。下一步动作可以是条件判断、分支指令、或顺序执行一条指令、或者指示整个算法的结束等。算法的确定性要保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令（被锁住）或仅仅含有模糊不清的指令。算法的有穷性(Finiteness)算法的执行必须在有限步内结束。换句话说，算法不能含有死循环。北京大学信息学院，转载或翻印必究Page13递推法递归穷举搜索法贪婪法分治法动态规划法迭代法算法设计与分析的基本方法北京大学信息学院，转载或翻印必究Page141.4.2 计算复杂性和算法的效率根据计算理论(theoryofcomputation)，存在着一类问题虽然能够被准确定义，但却不存在能够解决该问题的算法。称为不可解问题(UndecidableDecisionProblem)比如:停机问题(Haltingproblem)；图灵在1936年（那时还没电脑，是在没有设备支持的纯理论基础上提出来的）输入一段程序代码和一个针对此程序的输入，能否编程判断运行这个程序后程序是否会终止计算复杂性理论(computationalcomplexitytheory)指出，理论上存在一大类难解问题，它们虽然存在着求解算法，但是在算法的计算时间上，都是组合爆炸型的求解算法。北京大学信息学院，转载或翻印必究Page15组合爆炸型的旅行商（TSP）问题：旅行商按一定的顺序访问N个城市的每个城市，使得每个城市都能被访问且仅能被访问一次，最后回到起点，而使花费的代价最小。目前的方法接近一个一个的排着试，还沒有找到更好可以寻得最短路径的方法。对七个城而言，共有6!=720个排法，尚不算难，但若有20个城，则排法就有19!种。

依据斯特灵公式：，有19!≈1.21x1017若每秒钟排一次，要排3.84x109

年（一年约为3.15x107

秒）。即使使用计算机，每秒排一百万次（不容易做到），也得三千年才能找到答案。区区二十个城，要三十个世纪才能找到答案。NP-Hardproblem,i.e.,nondeterministicpolynomial-timehard组合爆炸型问题（示例）北京大学信息学院，转载或翻印必究Page161.4.2 计算复杂性和算法的效率所谓组合爆炸型，是指随着问题的规模n的增大，算法的时间开销不能约束在n的k阶多项式数量范围内。（其中k是任意不依赖于n的常数）特別注意n2

与2n

中之差异，一般称2n

为计算量呈指数上升，而n2

或nk

的计算量呈n

的方次上升，对目前及未来的计算机而言，一个呈方次上升的计算量应可以应付，但对一个呈指数上升的计算量在n

相当大时则毫无希望。因此，计算机学家致力解决，如何将一个呈指数上升的计算量问題，简化成一个方次上升的计算量问題。北京大学信息学院，转载或翻印必究Page171.4.2 计算复杂性和算法的效率根据计算复杂性理论，难解问题的定义就是它的求解算法均无法在多项式时间nk数量级内解决（其中k是任意正整数）。比较常见的难解问题有：图论中的求最优巡游路径（TSP）问题等若以计算机每秒做一百万次的运算速度，完成各层次计算量所约需的时间（若无单位，均以秒为单位）

北京大学信息学院，转载或翻印必究Page18第一章概论1.1为什么要学习数据结构1.2什么是数据结构1.3抽象数据类型1.3.1什么是抽象数据类型1.3.2示例1.3.3类1.3.4类模板附：1.3.5动态内存分配;1.3.6C与C++语言的输入输出语句1.4算法的特性及分类1.5算法的效率度量1.6数据结构的选择和评价北京大学信息学院，转载或翻印必究Page191.5算法的执行效率及其度量解决同一个问题总是存在着多种算法，而算法设计者往往要在所花费的时间和所使用的空间资源之间采取折中，采用某种以空间资源换取时间资源的策略。算法设计者可以通过算法分析，判断所提出的算法是否现实，设计出更好的算法时间空间北京大学信息学院，转载或翻印必究Page20时间空间1.5算法的执行效率及其度量北京大学信息学院，转载或翻印必究Page211.5.1算法的渐进分析(asymptoticanalysis)算法的渐进分析，简称算法分析。算法在计算机上实际执行时，消耗的时间资源（归结为CPU执行指令的总数）；使用的空间资源（所需占用的存储单元数量，字节数）。由于算法分析和它所求解的问题规模直接有关，因此通常将问题规模n作为一个参照量，

求算法的时空开销和n的关系。北京大学信息学院，转载或翻印必究Page221.5.1算法的渐进分析(asymptoticanalysis)算法的渐进分析数据规模n逐步增大时，资源开销T(n)的增长趋势。从数量级大小的比较来考虑当n增大到一定值以后，资源开销的计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都是可以忽略的。北京大学信息学院，转载或翻印必究Page231.5.1算法的渐进分析(asymptoticanalysis)算法的渐进分析就是要得到一个大O渐进表达式，简写为：

ratenT(n)＝O(F(n))其中O是数学分析常用符号“大O”，而F(n)是自变量为n的某个具体的整函数表达式，例如：F(n)＝n2如果存在正的常数c和n0

，当问题的规模n≥n0后，某算法的时间（空间）代价T(n)≤c·F(n)，则说该算法的时间（空间）代价为O(F(n))。北京大学信息学院，转载或翻印必究Page241.5.1算法的渐进分析(asymptoticanalysis)算法的执行时间等于它所有基本操作执行时间之和，而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积，

如下：

算法的执行时间

＝

操作1

＋

操作2

＋

...+操作n

操作的执行时间

＝

基本操作执行次数

X

基本操作执行一次的时间

不同的编程语言，不同的编译器，或不同的CPU等因素将导致执行一次基本操作的时间各不相同，这样的结果会使算法的比较产生歧义，

于是我们假定所有计算机执行相同的一次基本操作所需时间相同，而把算法中基本操作所执行的最大次数作为量度。就是说我们把算法的执行时间简单地用基本操作的执行次数来代替了。基本操作是什么？

它可以是基本运算，赋值，比较，交换等，比如在排序中，基本操作指的是元素的比较及交换；在线性查找中，它是数据的比较。北京大学信息学院，转载或翻印必究Page25算法的渐进分析示例

冒泡排序、数组的线性查找比如一个冒泡排序的算法，假如有10个数，第一次循环比较9次，第二次循环比较8次，以此类推，一共循环9次，那么总比较次数为

9＋8＋7＋6＋5＋4＋3＋2＋1

等于45次，

则对于N个数来说，总比较次数为

N(N-1)/2

次，

比较次数的数量级已达到N的平方，即T=N(N-1)/2

，

则我们说它的比较操作的时间复杂度为

O(n2)(n的平方）。

对于一个数组的线性查找，在最坏的情况下，10个数要比较10次，那么对于N个数来说，要比较N次，平均

N/2

次，

即T=N/2，它的数量级是一次的，

则我们说这个线性查找的比较操作的时间复杂度是线性，即

O(n)。北京大学信息学院，转载或翻印必究Page26算法的渐进分析示例

矩阵求和（matrix_addition）voidmatrix_addition(double**M1,double**M2,intk){

//矩阵M1,M2求和，即两两元素求和，结果存回M1

//k×k是矩阵的规模

for(inti=0;i<k;i++) for(intj=0;j<k;j++)//对应位置的矩阵元素相加

M1[i][j]=M1[i][j]+M2[i][j];}北京大学信息学院，转载或翻印必究Page27此问题的规模由输入数据规模决定，主要是浮点矩阵M1,M2的尺寸n＝k2

在渐进分析时，通常我们把浮点运算和数组元素的读写操作的执行时间都看作在同一个数量级内，忽略其执行时间的细微差别为了求出一个渐进估计的代数公式，若令r是单个指令执行时间，那么对于矩阵加法程序，由于循环体每执行一次，需要pr时间，其中p是一个常数倍数算法的渐进分析示例

矩阵求和（matrix_addition）北京大学信息学院，转载或翻印必究Page28考虑到两重嵌套的for循环，一共执行k×k遍，因此，这个程序的时间开销的渐进估计式可以写为T(n)＝prn＋C。其中C是一个不随n而变化的常数，代表进入循环体前后计算机所作的辅助操作时间由此看出，矩阵加法的时间开销是和问题规模n成正比的，且该算法的时间开销是线性增长的，

简写为ratenT(n)＝O(n)，即F(n)=n算法的渐进分析示例

矩阵求和（matrix_addition）北京大学信息学院，转载或翻印必究Page29用于渐进分析的常见的F(n)还有以下若干种：F(n)=1,常数函数，不依赖于nF(n)=logn,对数函数，它比线性函数n增长慢F(n)=n，线性增长，随着问题规模n而增长

例如，raten（n个a相加）

=raten

（na）

=O(n)F(n)=n2，二阶增长 例如，raten∑i=1..n∑j=i..n(a)=O(n2)， 因为∑i=1..n（a(n－i+1)）＝（a(n(n+1)/2)北京大学信息学院，转载或翻印必究Page30用于渐进分析的常见的F(n)还有以下若干种：F(n)=nlog(n)，其增长率的阶数低于二阶，但高于一阶线性。例如，

raten∑i=1..logn∑j=i..n(a)＝O(nlog(n))F(n)=an

指数增长，随问题规模n而增长极快 这种指数型的渐进函数往往由递归定义的函数产生。北京大学信息学院，转载或翻印必究Page311.5.2最坏、最好、

和平均情况在具体进行算法增长率估计时，往往会由于算法中的条件分支而遇到困难。由于算法实际执行的操作往往依赖于分支条件的走向，而输入数据的取值又影响这些分支走向，因此很多算法都无法得出独立于输入数据的渐进估计。针对这一情况，提出了最坏情况估计、平均情况估计、和Theta（希塔）估计等三种方法北京大学信息学院，转载或翻印必究Page32算法分析示例

—求矩阵M中绝对值最大的元素doubleabs_biggest(double**M,intk)

{//求矩阵M中绝对值最大的元素，k×k是矩阵的规模

doublecurrent_big=0;//临时存储单元，初始化为0for(inti=0;i<k;i++) for(intj=0;j<k;j++){//对每一个矩阵元素进行大小比较

doubletemp=fabs(M[i][j]);//fabs是浮点数求绝对值函数 if(temp>current_big) current_big=temp;//current_big存储当前最大者

returncurrent_big;//函数值返回}北京大学信息学院，转载或翻印必究Page33输入参数为浮点矩阵M，它的大小是影响算法时空开销的主要因素。令n＝k×k为这个问题的规模在最坏的情况下，每一次判断(temp>current_big)都为真，赋值语句执行n次在最好的情况下（第一次current_big赋值后，程序没再有赋值操作），则基本没有赋值时间开销平均而言，在假定浮点矩阵的主元素（绝对值最大）位置随机分布的情况下，可以说，其平均时间（关于赋值操作）开销正比于n/2；关于比较操作正比于n。算法分析示例

—求矩阵M中绝对值最大的元素北京大学信息学院，转载或翻印必究Page34对于时间开销，一般不关注算法的‘最好估计’

特别是处理应急事件，计算机系统必须在规定的响应时间内做完紧急事件处理。这时，最坏估计是唯一的选择。对于多数算法而言，最坏情况和平均情况估计两者，它们的时间开销的公式虽然不同，但是往往只是常数因子大小的区别，或者常数项的大小区别。因此不会影响渐进分析的增长率函数估计。1.5.2最坏、最好、

和平均情况北京大学信息学院，转载或翻印必究Page351.5.3空间资源开销空间开销，也可以采取类似的渐进分析方法静态存储结构存储空间在算法执行过程中并不发生变化。空间开销，或者与所涉及的问题规模成正比（空间开销为线性增长），或者不随问题的规模而增大（空间开销为常数）。动态数据结构北京大学信息学院，转载或翻印必究Page361.5.3空间资源开销静态的存储结构动态数据结构算法的存储空间在算法运行过程中会发生变化，有时会有数量级的增大或缩小空间开销的分析和估计是十分必要的北京大学信息学院，转载或翻印必究Page37时空资源的折中原理求解同一个问题，一般会存在多种算法。这些算法的优劣往往表现出‘时空折中’的性质为了改善一个算法的时间开销，往往可以通过增大空间开销为代价，而设计出一个新算法来为了缩小算法的空间开销，而牺牲计算机的运行时间，通过增大时间开销来换取存储空间的节省北京大学信息学院，转载或翻印必究Page381.5.4大表示法及其分析规则大（希塔）表示法是算法分析的一种渐进估计，简称希塔估计。它是前面讨论的大O表示的扩展对于任意的资源开销函数T(n)，以及对T(n)的一个渐进估计式F(n)，称F(n)为T(n)的一个渐进希塔估计，当且仅当满足如下数学性质：

存在正常数C1,

C2，以及正整数n0，使得对于任意的正整数n>n0，有下列两不等式同时成立：

|T(n)|>C1

F(n)和|T(n)|<C2

F(n)北京大学信息学院，转载或翻印必究Page391.5.4大表示法及其分析规则如果一个算法存在一个渐进估计式F(n)，可以同时充当它的上界和下界的渐进估计，那么就把这个F(n)称作算法开销T(n)的希塔估计，或称估计对于算法的资源开销，估计可以同时给出它的下界估计和上界估计。北京大学信息学院，转载或翻印必究Page401.5.4大表示法示例

假定资源开销函数T(n)＝100n2＋5n＋500， 令F(n)=n2，存在正常数C1=100,C2=105，以及n0=10

使得当n>n0时，|T(n)|>C1F(n)和|T(n)|<C2F(n)

同时成立。（上述不等式可以用算术计算验证）

由此说明T(n)的希塔估计式等于F(n)=n2

北京大学信息学院，转载或翻印必究Page41第一章概论1.1为什么要学习数据结构1.2什么是数据结构1.3抽象数据类型1.3.1什么是抽象数据类型1.3.2示例1.3.3类1.3.4类模板附：1.3.5动态内存分配;1.3.6C与C++语言的输入输出语句1.4算法的特性及分类1.5算法的效率度量1.6数据结构的选择和评价北京大学信息学院，转载或翻印必究Page421.6数据结构的选择和评价仔细分析所要解决的问题，特别是求解问题所涉及的数据类型和数据间逻辑关系数据结构的初步设计往往在算法设计之先注意数据结构的可扩展性。包括考虑当输入数据的规模发生改变时，数据结构是否能够适应。同时，数据结构应该适应求解问题的演变和扩展数据结构的设计和选择要比较算法的时空开销优劣北京大学信息学院，转载或翻印必究Page43算法的度量算法设计的两个目标：充分利用计算机资源（算法和数据结构）易读、易编码和调试（软件工程）评估方法实验（运行程序）渐进分析关键资源影响运行时间的因素（与问题的输入规模n有关）北京大学信息学院，转载或翻印必究Page44“C语言复习”中若干知识点

结构体类型的定义

指针与结构体

函数调用北京大学信息学院，转载或翻印必究Page45结构体类型的定义

结构体━━可以含有不同类型数据的整体。

(structure)

学生信息

{整型学号；

字符串姓名；字符性别；整型年龄；实型成绩；字符串地址；

}数组━━相同类型数据的序列北京大学信息学院，转载或翻印必究Page46给类型定义命名

typedef类型定义名字；

typedefintatype[8];

typedefstructstudent

{intno;charname[16];

charsex;intage;floatscore;charaddr[16];}stype;北京大学信息学院，转载或翻印必究Page47typedefstruct{intno;charname[16];

charsex;intage;floatscore;charaddr[16];}stype;stypes;s.sexs.ages.scores.addr结构体变量名·成员名北京大学信息学院，转载或翻印必究Page48关于指针一个指针变量只能指向事先声明的类型的变量。

inta,b,*pointer_1;

floatr,*pointer_2;

pointer_1=&a;pointer_1=&b;