学习准备一：ch1+软件开发+ch2+抽象数据类-课件（PPT·精·选）.ppt

数据结构与算法分析-C++语言描述(第二版) Nyhoff 著黄达明等译Introducer:毛国红E-mail: jenniemao@; ******@:广知- 4楼数据结构与算法分析–C++语言描述(第二版)数据结构与算法分析-C++语言描述(第二版)(p1-p39 自学为主)如何进行软件开发第2章抽象数据类型入门(p40-p72 自学为主)ADT概念、C++的数据类型第3章数据结构和抽象数据类型(p73-p128 自学为主)数据结构概念、 算法效率Start to Solve them!学****准备1:数据结构初步数据结构与算法分析-C++语言描述(第二版)?数据结构课程讨论的中心问题:复杂的实际问题需要处理大量的数据,数据之间又有错综复杂的关系,在机器中如何有效的表示(存储)这些数据和数据之间的联系,使它们可以在相关的处理程序中有效的用来模拟和解决问题。图:数据结构的地位及其相关领域的联系数据结构数据结构设计方法设计方法描述语言描述语言算法理论算法理论数据模型数据模型问题求解数据结构与算法分析-C++语言描述(第二版)?本课程的讨论重点?一些典型的数据结构:?字符串?列表(基于数组/基于链)?栈/队列?树/二叉树?堆/优先队列?散列?图?一些典型的算法:?添加?删除?查找/搜索?排序?最短路径?可达/连通数据结构与算法分析-C++语言描述(第二版)?对数据结构的关注点:?结构中各元素之间的抽象(逻辑)关系—逻辑结构?结构中各元素的存储方式—存储结构?结构的行为和特性—数据的添加、删除、查找、排序等。?逻辑结构-ADT(本书中对应的内容描述)?线性?非线性?存储结构-”数据结构”?连续存储:数组?链式存储:使用指针?结构的行为和特性-算法?各类算法描述和实现?算法效率的分析数据结构与算法分析-C++语言描述(第二版)?逻辑结构?线性结构…?一个头,一个尾巴?头无前驱,尾无后继?其他元素有唯一的前驱与后继.?如:字符串、链表、堆栈/队列数据结构与算法分析-C++语言描述(第二版)?逻辑结构?非线性结构?元素的前驱后继个数不确定、?如:树/二叉树、散列、图数据结构与算法分析-C++语言描述(第二版)?算法:为实现某个计算过程而规定的基本动作的执行序列(可以被计算机执行的一个过程)?Niklaus Wirth,Pascal语言的创始人算法+数据结构=程序?算法特性:-无二义性。算法的每个步骤必须准确描述,让计算机知道每个指令要求完成什么。-简单性。计算机可以实现,通常采用类似程序的形式描述,容易实现为计算机指令。-可终止性。算法必须在有限步(合理的时间内)终止。-正确性。满足初始条件的输入,无论算法执行几次,算法得到的结果总是确定并且正确的。 -(补充)>=0个输入,>=1个输出。可以有0个或多个输入,有至少1个输出。数据结构与算法分析-C++语言描述(第二版)?算法分析( p489): 评价一个算法优劣。?时间和空间。?空间复杂度:当被解决问题的规模(以某种单位计)从1?n时,解决问题的算法所需占用的空间也以某种单位从f(1)?f(n),此时称算法的空间代价是f(n)。?时间复杂度:当被解决问题的规模(以某种单位计)从1?n时,解决问题的算法所需耗费的时间也以某种单位从g(1)?g(n),此时称算法的时间代价是g(n)。?算法复杂度(效率)的表示: 大O表示法?Big-O 定义:若存在常量c,n0,对于任意的n≥n0,有T(n) ≤c·f(n).则认为T(n)=O(f(n)).称O(f(n))为算法复杂度---当n充分大时,算法的复杂度不大于f(n)的常数倍数据结构与算法分析-C++语言描述(第二版)?Big-O 的加法规则:T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n)+f2(n)))?Big-O 的乘法规则:T(n)=T1(n)XT2(n)=O(f1(n))XO(f2(n))=O((f1(n)Xf2(n)))?Big-O 举例: 1) f(n)=(1/2) n2 <=n2,n>=1 ? f(n)=O(g(n))=O( n2 )2) f(n)=n+2<=n+n=2*n,n>=2 ? f(n)=O(n)3) f(n)= n2 + n + 16,?f(n)=O( n2 )4) f(n)= n2 + n + 1<= n2 + n2 + n2 = 3 n2 ,n>=1? f(n)=O( n2 )5) f(n)= <= ,n>=3 ?