第一章 绪 论(数据结构word版课件).doc
《第一章 绪 论(数据结构word版课件).doc》由会员分享,可在线阅读,更多相关《第一章 绪 论(数据结构word版课件).doc(20页珍藏版)》请在三一文库上搜索。
1、第一章 绪 论1.1 为什么要学习数据结构1.2 数据结构概念历史定义1.1数据是指对象的表示,即按照适合于通信、解释或处理(借助人或自动装置)的方式所形成的关于事实、概念或指令的表示;数据只是表示,而无含义3。数据是计算机科学与技术中最基本的概念,它是计算机程序要处理的“原料”,是所有被计算机识别、存储和加工处理的符号的总称4,5。元素、结点或顶点,数据项(也称为域或字段) 数据元素(或曰数据成分)还可被称为元素、结点或顶点等。数据元素可大可小,大到可以是一篇文稿、一本书,小到可以是一个字符,甚至是计算机二进制数中的一位。数据元素可由若干个数据项(也称为域或字段)组成。例1.1 如表1.1所
2、示的通讯录表,行表示一个结点(数据元素),每个结点由姓名、区号、办公电话和手机四个域(数据项)组成。表1.1 通讯录表姓名区号办公电话手机赵一0105364458713911001234钱二0208963415913809771333孙三0214597652813916586666李四0246342754113804076111 定义1.2 数据结构由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。数据成分及其间的数据约束关系合称为数据结构的逻辑结构。数据结构从数学上可用适当的数学结构以及其上的函数变换统一地定义。但迄今为止,关于数据结构之定义在计算机科学技术界还未取得完全认
3、同。有些学者认为数据结构应由数据的逻辑结构、数据的存储结构及其运算三部分组成。一个逻辑结构可形式定义为一个二元组5:L = (N, R),其中,N是结点的有限集合,R 是定义在集合N上的二元关系r的集合。设 L=(N, R) 是一个逻辑结构. r1R是与线性结构、树结构和二叉树结构对应的一种关系,若a,bN,且 (a,b) r1,则称 a是b的前驱结点,b是a的后继结点,a和b是相邻结点;若不存在aN使得 (a,b) r1,则称 b 为始结点;若不存在 bN 使得(a,b) r1,则称 a 为终结点. r2R是与图结构对应的一种关系,若a,bN,且关系 (a,b) r2,则称a和b是相邻结点;
4、对于有向图结构,若存在(a,b) r2,则称a是b的前驱结点,b是a的后继结点。数据的存储结构(或曰物理结构)1.2.3 对数据结构的操作插入、删除、修改、排序、查找1.3 算 法定义1.49 一个算法就是给出求解特定类型问题之运算序列的一个有穷规则集合,一个算法应具有5个重要特征:1) 有限性:一个算法在执行有限步骤后必然终止;2) 确定性:对一个算法的每个步骤都必须给出精确的定义;对要执行的动作都必须给出针对每种情况的严格、无歧义的描述;3) 输入:一个算法有0个或多个输入;4) 输出:算法有1个或多个输出;5) 可行性:算法中的所有操作都必须是充分基本的,因而原则上人们用纸和笔都可在有限
5、时间内精确地完成它们。1.3.2 算法的描述ADL语言例1.3 欧几里得算法E9-10 算法E ( m , n . n )/* 给定两个正整数m和n,算法E求它们的最大公因子(即能同时整除m和n的最大正整数),输出结果在n中 */E1. 求余数 r m - m/n n . / 有0 r N . 与 N 是最大整数矛盾。(3) 肯定原来的结论:因此,没有最大的整数。证毕。2. 数学归纳法证明算法正确性的一般方法是数学归纳法。设THM是一个定理, n是THM中的正参数. 数学归纳法表明,如果下面两个条件为真,则对于参数n的任何值,THM都是正确的:(1) 基础归纳:n = c 时,THM成立。(2
6、) 归纳步骤:如果n = k - 1 时THM 成立,则n = k 时THM也成立。其中,c是一个较小的常量,n c . 通常,证明初始归纳很容易,而证明归纳步骤很难。以上是一般意义下的数学归纳法,而强归纳法在归纳步骤上有所变化: (2) 归纳步骤:如果对于所有的k ( c k 1 .证明:(1) 基础归纳:n =1 时,T ( 1 ) = 1 - 1 = 0,结论成立。(2) 归纳步骤:假设 T ( n - 1 ) = n - 2 成立 (归纳假设)要证明T ( n ) = n - 1 成立。由递归定义可知:n 1 时,有T ( n ) = T ( n - 1 ) + 1 由归纳假设:T (
7、 n ) = T ( n - 1 ) + 1 = n - 2 + 1 = n - 1所以,由数学归纳法推出T ( n ) = n - 1成立。证毕。对于一个算法,证明其正确性是必要的。如果算法比较复杂,至少应该给出其关键步骤的正确性证明。目前,算法或程序的正确性证明仍然是计算机科学领域中具有挑战性的重要研究课题。1.5 算法分析基础1.5.1 算法时间复杂性的分析方法分析算法的时间复杂性需要分析算法的基本运算次数。基本运算是指算法运行过程中起主要作用且花费最多时间的运算。例1.7 A是一个含有n个不同元素的实数数组,给出求A之最大和最小元素的算法。算法SM( A , n . max , min
8、 )/ 求实数数组An的最大和最小元素( max和min ) .SM1. 初始化maxminA1. SM2. 比较FOR i = 2 to n DO(IF Ai max THEN maxAi. IF Ai min THEN minAi)对算法SM 进行分析,容易看出算法SM 对大小为的 n 的数组 A 需要 2(n -1) 次元素比较,如果规定算法SM的基本运算是元素比较,那么算法SM 的基本运算的次数,即时间复杂性为2(n-1) .一般情况下,计算一个算法的基本运算次数是相当困难的,甚至是不可能的(因为一个算法的不同输入往往产生不同的运算次数,而一个算法的所有不同输入的数目可能十分庞大)。一
9、种可行的方法是计算算法的平均运算次数。这样的结果在实际中可能不是特别有用,因为某些输入较之其它的输入可能更经常出现,所以对数目足够的不同输入的加权平均将会给出更有意义的结果。通常在最好、最坏和平均三种情况下,讨论算法的时间复杂性。定义1.5 设一个领域问题的输入规模为n,Dn是该领域问题的所有输入的集合,任一输入IDn,T(I)是(解决该领域问题的)算法在输入I下所执行的基本运算次数,P(I)是I出现的频率,该算法的最好情况下的复杂性为:该算法的最坏情况下的复杂性为:该算法的平均情况下的复杂性,或期望复杂性为:例1.8 实数数组R由 n 个元素组成,给定一个实数K,试确定K是否是R的元素。算法
10、F(R , n , K . i)/*给定一具有n 个元素的实数数组R,判断实数K是否在R中出现,若是,1 i n;否则,i= n+1 .*/F1. 初始化i1.F2. 比较WHILE i n DO( IF Ri = K THEN RETURN. i i+1) 算法F的运行结果:如果1 i n,则表示 K 是 R 的元素;反之,K 不是 R 的元素。规定算法F 的基本运算为 R 中元素与 K 的比较,假定 q 表示 K 是 R 中元素的概率,又假定 K 等于 R 的每个元素有相同的概率。令 Dn = I1, I2, In, In+1,其中 Ii (1 i n) 表示 K等于 Ri 的任一输入,I
11、n+1 表示 K 不是 R 中元素的任一输入。由上述说明我们有:当1 i n时, P(Ii) = q/n, T(Ii) = i, P(In+1) = 1-q, T(In+1) = n . 算法F的期望复杂性为:如果已知K在R中,即q = 1,则我们有由算法F我们很容易看出,该算法的最坏情况下的时间复杂性为算法F的最好情况下的时间复杂性为Flash动画课件115网盘用户名:2010datastructu密码:forsuccess2010例1.9 算法SM的改进算法BS .算法BS( A, i, j . fmax, fmin )/ 在数组A的第i个元素到第j个元素之间寻找最大和最小元素,已知i j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 论数据结构word版课件 数据结构 word 课件
链接地址:https://www.31doc.com/p-4660829.html