数据结构与算法：第1章 绪论

数据结构与算法DataStructures

andAlgorithm讲课学时：42，实验学时：12，课程设计：18+1周教学安排：期末考试占60%，实验成绩占30%，平时作业占10%考核要求：本学期上课时间：3-14周,周二5-6节，周四5-6节.致知23考试时间：18周课程设计：12-16周计算机导论数字逻辑计算机组成技术操作系统数据库系统课程设计计算机网络编译原理数据结构与算法数据结构与算法课程设计多核程序设计数据库系统Linux操作系统*程序设计语言用户界面设计面向对象技术与UMLJava语言程序设计实践面向服务的计算技术.NetC++语言J2EE软件开发实践软件外包开发技术*英语限选军训大学外语体育政治大学外语体育马哲英语限选体育英语限选体育英语口语英语限选英语口语工科数析Ⅰ代数与几何概率论与数理统计离散数学运筹学算法设计与分析工科数析Ⅱ理论系列系统系列工具系列工程系列管理系列其他课程第一学期第二学期第三学期第四学期第五学期第六学期第七学期第八学期系统分析与设计软件工程概论软件项目管理软件开发过程管理软件质量保证与测试软件工程综合课程设计计算机职业道德市场营销知识产权法交流技巧财务管理商务谈判IT企业管理合同法IT企业创业管理方向课计算机安全概论服务学概论中文信息处理嵌入式操作系统方向1)网络通信与信息安全2)服务学与企业信息化3)多媒体与信息处理4)嵌入式系统与软件毕业设计物联网专业教材数据结构与算法（第4版）编著廖明宏郭福顺张岩李秀坤高等教育出版社参考资料数据结构严尉敏吴伟民编著清华大学出版社引进教材DataStructuresandProgramDesigninC++数据结构与程序设计——C++语言描述（影印版）RobertL.Kurse,AlexandeerJ.RybaISBN7-04-010039-8/TP.691P736教材比较1.1数据结构研究对象1.2数据结构发展概况1.3抽象数据型(ADT)1.4数据结构与程序设计1.5算法描述与算法分析主要内容1.1数据结构研究对象◆计算机科学：信息在计算机内使用数据来表示,

研究信息表示和信息处理。◆数据：是用以描述客观事物的数值、字符，以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合。数据的基本单位称为数据元素数据的最小单位称为数据项◆数据对象：性质相同的数据元素的集合◆数据特征：数值、文本、多媒体、超媒体、实时、海量◆数据类型?高级语言中变量的取值范围和允许的操作

什么是数据？大数据(bigdata)大数据可分成：大数据技术大数据工程：大数据工程指大数据的规划建设运营管理的系统工程；大数据科学：大数据科学关注大数据网络发展和运营过程中发现和验证大数据

的规律及其与自然和社会活动之间的关系大数据应用大数据的4个“V”：—Volume：数据体量巨大。从TB级别，跃升到PB级别；—Variety：数据类型繁多。网络日志、视频、图片、地理位置信息等—Value：价值密度低。以视频为例，连续不间断监控过程中，可能有用的数据

仅仅有一两秒。—Velocity：处理速度快，1秒定律。第一，大数据的基本概念第二，大数据计算机其挑战第三，研究问题与部分解大数据无处不在：因特网有很多的大数据，在科学研究领域、医疗领域、商业领域、制造业、智慧城市都有大量的数据。全世界的感知数据增长率是每年58%全世界拥有的存储能力或者是存储总量的增长率是每年只有40%2007年，全世界的感知数据已经超过了全世界所拥有的存储器的容量2010年，全世界的感知数据是1.25千万PB2011年产生的感知数据已经二倍于我们人类所拥有的存储器的容量结论：大数据无处不在，数据量远远超出了现有的存储能力大数据的输入是大数据D，问题的解是f（D）。李建中教授谈大数据◆数据结构：数据对象中的数据元素彼此之间抽象的相互关系，并不涉及数据元素的具体内容◆数据结构分类：线性表：(a1,a2,a3,……ai-1,ai,ai+1……an-1,an)→线性结构线性表的一般概念、字符串、数组，广义表等树：

→层次结构二叉树，树等图：

→网状结构有向图、无向图等①②③⑤

二叉树①②③④有向图◆结构：关系

国际象棋：每次需要考虑的合乎规则的着法平均只有35

步“回合”，计算机预先分析7至8个回合的着

法。若设为7个回合，则有超过1亿亿亿个不

同的变化，经简化后，仍有500亿至600亿个

变化。多分析一步，增加18亿个变化资料：下棋程序围棋：分析7个回合的着法，则需要考虑超过200的

14次方个变化，经简化后，仍有1000亿亿个

变化。多分析一步，增加64万亿个变化根据计算机“深蓝”的速度，平均5分钟走一步根据计算机“深蓝”的速度，平均1.5年走一步BlueGene,共装有32个并行处理器，速度：2亿步棋/秒深蓝vs

卡斯帕罗夫:第一次1996年：2月10日—17日，比分2:4第二次1997年：5月3日—11日，比分3.5:2.5双方先后共进行6局对弈第一局，卡斯帕罗夫执白先行，经过3个多小时的苦战击败“深蓝”，力拔头筹；第二局，“深蓝”却以凌厉的攻势和明显的优势战胜卡氏，扳回一局；第三、第四和第五局，双方下得异常激烈，鏖战数小时，平局；第六局，“深蓝”执白先行，一路强攻，仅用一个多小时，双方仅走19步，就让卡氏俯首称臣，取得了决定性的胜利。IBM：“深蓝”与棋王卡斯帕罗夫的对比:身高：卡斯帕罗夫5英尺10英寸，“深蓝”6英尺5英寸；体重：卡斯帕罗夫176磅，“深蓝”1.4吨；年龄：卡斯帕罗夫34岁，“深蓝”4岁；每秒行棋速度：卡斯帕罗夫2步，“深蓝”2亿步。“神来之手”1.1数据结构研究对象◆数据结构研究方法：逻辑结构：对操作对象的一种数学描述，或从操作对象中抽象出的数学模型，用以描述数据元素之间的逻辑关系物理结构：数据结构在计算机中的表示或映象，

物理结构又称存储结构，分为顺序映象和

非顺序映象，或称顺序存储结构和链式存储结构计算机解题过程：问题→数学模型→算法→程序→测试→计算分析数据并确定存储结构输入到计算机中1.2数据结构发展概况●数据结构侧重解决非数值问题■FORTRAN,ALGOL等高级语言是以程序为中心侧重于解决数值问题■LISP,SONBOL表或串处理语言是以数据为中心侧重于解决非数值问题●1968年以前，数据结构的内容大多包含在形如表、树、图论、集合代数论、格、关系等方面。1968年开始，“数据结构”逐渐开始成为独立的一门课程。●作为一门专业基础课，“数据结构”是计算机专业的核心课程之一，是其他专业课的基础。是数学、硬件和软件三者的交叉，很受重视。■从PASCAL语言开始逐渐形成二者结合知识结构1.3抽象数据型AbstractDataTypes（ADT）

●软件系统由数据结构、操作过程和控制机能三者组成，软件设计是对三者的抽象过程，即数据抽象、过程抽象和控制抽象。[定义]：抽象数据型是一个数学模型和在该模型上定义

的操作的集合ADT特点：①降低了软件设计的复杂性②提高了程序的可读性和可维护性③程序的正确性容易保证抽象：从众多事物中舍弃个别的、非本质的属性，抽出共同的、本质性的特征。是形成概念的重要手段，其目的是使复杂度降低。线性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例，p为位置变量。所有操作描述为：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)数学模型1.3抽象数据型（ADT）举例㈠定义任意线性表类型为LIST，其中元素类型为Elementtype，设有线性表L，函数PURGE用以删除线性表L中所有重复出现的元素。VoidPURGE(LISTL){Positionp,q;p=FIRST(L);while(p!=END(L)){q=NEXT(p,L);while(q!=END(L))if(same(RETRIEVE(p,L),RETRIEVE(q,L)))

DELETE(q,L);elseq=NEXT(q,L);p=NEXT(p,L);}}1.3抽象数据型（ADT）举例㈡假设利用两个线性表LA和LB分别表示两个集合，设计算法求一个新的集合A=A∪B。VoidUNION(LIST&A；LISTB){positionp;

elementtypee;p=FIRST(B);while(p!=END(B);{e=RETRIEVE(p,B);if(same(LOCATE(e,A),END(A)))

INSERT(e,END(A),A);p=NEXT(p,B);}}1.3抽象数据型（ADT）抽象数据型的规格描述△完整性：反映所定义的抽象数据型的全部特征△统一性：前后协调，不自相矛盾△通用性：适用于尽量广泛的对象△不依赖性：不依赖于程序设计语言，可以用任意的语言来描述规格描述的两个方面:语法和语义△语法：给出操作的名称、I/O参数的数目和类型△语义：由一组等式组成，定义各种操作的功能及相互间的关系例如：抽象数据型——栈(Stack)定义：栈是一个后进先出（LIFO）的线性表，所有插入、删除操作是在表的一端（栈顶）进行聚集数组，链表(结构体、记录)，文件1.3抽象数据型（ADT）a1a2······an-1anInsertDeletetopbottom栈底栈顶栈示意图栈(Stack)示意图1.3抽象数据型（ADT）1.3抽象数据型（ADT）typeStack[Elementtype];NEWSTACK()→Stack,PUSH(Elementtype,Stack)→Stack,POP(Stack)→Stack∪{UNDEFINED},TOP(Stack)→Elementtype∪{UNDEFINED},EMPTY(Stack)→Boolean;抽象数据型——栈语法：declarestk:Stack,elm:Elementtype;POP(NEWSTACK)=NEWSTACK,POP(PUSH(elm,stk))=stk,TOP(NEWSTACK)=UNDEFINED,TOP(PUSH(elm,stk))=elm,EMPTY(NEWSTACK)=TRUE,EMPTY(PUSH(elm,stk))=FALSE;抽象数据型——栈语义：

规格描述给出操作的名称,I/O参数的数目和类型定义各种操作的功能及相互间的关系抽象数据型的实现抽象描述→（高级语言）编写的程序三条原则：①符合规格描述的定义

②有尽可能好的通用性

③尽可能独立于程序的其他部分多层次抽象技术自底向上与自顶向下相结合、由简单到复杂1.3抽象数据型（ADT）1.4数据结构与程序设计问题解决问题的算法实现算法的程序问题总是先于算法程序设计的四个里程碑

①子程序、②高级语言、③结构程序设计、④面向对象(OOP)结构程序设计

①限制使用GOTO语句（基于三种基本结构）

②逐步求精的设计方法

③自顶向下的设计、编码与调试

④主程序员组的组织形式N.Wirth：Programming=Algorithm+DataStructure

程序设计=算法+数据结构1.4数据结构与程序设计问题环境数据结构程序结构读和写

程序要完成的任务可执行的操作程序结构基于数据结构的根源1.4数据结构与程序设计

“我们对复杂性问题的最重要的办法是抽象，对一个复杂问题，不应马上用计算机指令、数字与逻辑字来表示，而应该用较为自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号（可能是自然语言）来表示。对抽象程序作进一步的分解，并进入下一层的抽象，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。此时的程序可能是某种高级语言或机器指令书写的。”——N.wirth基于数据结构的jackson设计方法：①研究问题环境，确定要处理的数据结构②基于数据结构，形成程序结构（骨架）③用初等操作来定义要完成的任务，并分配初等操作“从上到下，逐步求精”算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。PersianTextbook(《波斯教科书》)的作者的名字AbuJa'farMohammedibn

Mûsâal-Khowârizm

（约公元前825年）——从字面上看，这个名字的意思是“Ja'far

的父亲，Mohammed和Mûsâ

的儿子，Khowârizm

的本地人”。Khowârizm

是前苏联XИBA(基发)的小城镇。Al-Khowârizm

写了著名的书Kitabaljabr

w'al-muqabala(《复原和化简的规则》)；1.5算法描述与算法分析资料：Algorithm与Logarithm这个词一直到1957年之前在Webster'sNewWorldDictionary(《韦氏新世界词典》)中还未出现，我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的PersianTextbook(《波斯教科书》)的作者的名字AbuJa'farMohammedibn

Mûsâal-Khowârizm

（约公元前825年）——从字面上看，这个名字的意思是“Ja'far

的父亲，Mohammed和Mûsâ

的儿子，Khowârizm

的本地人”。Khowârizm

是前苏联XИBA(基发)的小城镇。Al-Khowârizm

写了著名的书Kitabaljabr

w'al-muqabala(《复原和化简的规则》)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典Vollstandiges

MathematischesLexicon(《数学大全辞典》)，给出了Algorithmus(算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus

infinitesimalis(无限小方法)，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。1950年左右，algorithm一词经常地同欧几里德算法(Euclid'salgorithm)联系在一起。这个算法就是在欧几里德的《几何原本》(Euclid'sElements,第VII卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。递归技术

——最常用的算法设计思想，体现于许多优秀算法之中分治法

——分而制之的算法思想，体现了一分为二的哲学思想模拟法

——用计算机模拟实际场景，经常用于与概率有关的问题贪心算法

——采用贪心策略的算法设计状态空间搜索法

——被称为“万能算法”的算法设计策略随机算法

——利用随机选择自适应地决定优先搜索的方向动态规划——常用的最优化问题解决方法“好”的算法的标准：

①正确性，算法能满足具体问题的需求

②可读性，首先方便阅读与交流，其次才是机器执行

③健壮性，输入错误时，能作出反应，避免异常出错

④效率与低存储量要求算法的特征：

①有穷性、②确定性、③输入、④输出、⑤能行性对算法“正确性”的要求：

①不含语法错误；

②对于几组输入数据能得到满足要求的结果；

③对精心选择苛刻并带有刁难的数据能得到满足要求的结果；

④对于一切合法的输入均得到满足要求的结果；算法描述：

①自然语言；②程序设计语言；③类语言*；关于本书采用的类语言描述：

①结构类型说明

②输入输出约定(cin>>v,cout<<v)

③new和delete

④引入引用类型

⑤其他影响算法执行的因素：

①算法实现后所消耗的时间**②算法实现后所占存储空间的大小*③算法是否易读、易移植等等其它问题影响时间特性的四个因素：

①程序运行时输入数据的总量②对源程序编译所需的时间③计算机执行每条指令所需的时间④程序中指令重复执行的次数*[定义]语句频度：语句重复执行的次数程序运行时间渐近时间复杂度（时间复杂度）T（n）

算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作：

T（n）=O（f（n））它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。渐近空间复杂度（空间复杂度）S（n）S（n）=O（g（n））运算法则：设：T1(n)=O(f(n))，T2(n)=O(g(n))

加法规则：T1(n)+T2(n)=O(max{f(n),g(n)})

乘法规则：T1(n)·T2(n)=O(f(n)·g(n))程序运行时间比较T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△

T(n)设：T(x)：取变量或常量x之值所消耗时间T(.V)：取变量V之地址所消耗的时间T(=)：赋值所消耗时间T(θ)：执行基本运算θ所耗时间T(call/return)：执行函数调用和返回所耗时间T(par)：将参数par传给函数所消耗时间～(1)表达式和赋值语句

exp::=常数|变量|F-name(e1,e2,…,em)|(expθexp)

T(v=exp)=T(.v)+T(=)+T(exp)

T(exp

θ

exp)=T(exp)+T(θ)+T(exp)

T(F-name(e1,e2,…,em))=T(call/return)+mT(par)+T(F-body)

例：

T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)

相应的汇编程序为：

loadainR1loadbinR2addR2toR1load.cinR2storeR1inR2～～通常取O(1)(2)语句序列

T(s1,s2,…,sk)=max{T(s1),T(s2),…,T(sk))(3)条件语句

T(if(B)s1elses2)=T(B)+T(else)+max{T(s1),T(s2)}

通常取T(B)+T(else)=O(1)

T(if(B)s)=O(1)+T(s)(4)Switch语句设语句sswitch(E){caseE1:S1;…caseEk:Sk;default:Sm}

T(s)=T(E)+∑T(Ei)+max{T(s1),…,T(sk),T(sm)}

O(1)ki=1(5)for语句

T(for(i=1;i<=n;i++)s)=∑(T(s)+T(i=1)+T(i<=n)+T(i++)+T(for))O(1)(6)while语句

while(B)si=0;while(B){s;i++}

设RT0表示某一次循环开始执行时的绝对时间关于循环的定时不变式RT为

RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j))

其中：T(while)代表测试循环终止条件所耗时间

T(j)代表跳回循环头所耗时间可简化成：T(j)=T(while)

T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while)(7)函数调用非递归调用：∑被调用子函数运行时间递归调用：求解递归方程(8)goto语句

goto语句破坏了程序结构一般对goto语句限制使用对有条件的goto转移可忽略不计举例：

①s=0;→f(n)=1;T1(n)=O(f(n))=O(1)常量阶

②for(i=1;i<=n;++i){++x;s+=x;}→f(n)=3n+1;T2(n)=O(f(n))=O(n)线性阶

③for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}→f(n)=3n2+2n+1;T3(n)=O(f(n))=O(n2)平方阶

④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];}→f(n)=2n3+3n2+2n+1;T4(n)=O(f(n))=O(n3)立方阶VoidBUBBLE(A)int

A[n];{int

I,j,temp;

for(i=0;i<n-1;i++)

for(j=n-1;j>=i+1;j--)O(