《数据结构：绪论、算法》由会员分享，可在线阅读，更多相关《数据结构：绪论、算法（38页珍藏版）》请在金锄头文库上搜索。
1、数据结构第一章 绪论数据结构研究的内容l 数据结构的研究内容： 数据元素之间的相互关系(逻辑结构)l数据结构 数据元素在计算机中的存储(存储结构) 算法实现l l数据元素之间的相互关系：数据元素之间的相互关系： 线性结构（一对一）l 逻辑结构 树形结构（一对多）：层次 图形结构（多对多）：网状 顺序存储l 存储结构 链式存储基本概念-数据l数据 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序加工处理的符号的总称，它是计算机加工的原料的集合。 如图像、声音等都可以通过编码而归之于数据的范畴。基本概念-数据元素l数据元素 是数据的基本单位，在计算机中通常作为一个整体进行
2、考虑和处理。每一个数据元素可以只有一个数据项（内存中称为域），也可以由若干数据项组成。 数据元素的同义语有：数据元素的同义语有：结点结点、顶点顶点和和记录记录等。等。基本概念-数据项l数据项是数据的不可分割的最小单位 。基本概念-数据对象l数据对象 是性质相同的数据元素的集合，它是数据的一个子集。数据对象可以是有限的，也可以是无限的比较和总结l数据l数据元素l数据项l数据对象基本概念-数据结构l数据结构数据之间的相互关系，即数据的组织形式。数据之间的相互关系，即数据的组织形式。说明：说明： 研究数据结构，就是指研究数据的逻辑结构和物理结构 。l数据的逻辑结构：数据元素之间的逻辑关系l数据的物理
3、结构：数据元素在计算机存储器中是如何存储的数据的逻辑结构l集合集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。l线性关系线性关系 结构中的数据元素之间存在一个对一个的关系。集合集合线性结构线性结构数据的逻辑结构l树形结构树形结构 结构中的数据元素之间存在一个对多个的关系。l图状结构图状结构或网状结构网状结构 结构中的数据元素之间存在多个对多个的关系。对比和总结l一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。l二、线性结构 结构中的数据元素之间存在一对一的关系。l三、树型结构 结构中的数据元素之间存在一对多的关系。l四、图状结构或网状结构 结构中的数据元素
4、之间存在多对多的关系。数据的存储结构l数据元素及其关系在计算机存储器中的表示数据的存储可以用以下四种基本的存储方法得到：1.顺序存储方法2.链接存储方法3.索引存储方法4.散列存储方法 总结l数据的逻辑结构和存储结构是数据结构的两个密切相关的的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于设计的逻辑结构，而算法的实现依赖于指定的存储结构。补充一些概念l数据的运算数据的运算对数据施加的操作。l数据类型数据类型1.原子类型（不可分解）2.结构类型l抽象数据类型抽象数据类型一个数学模型以及定义在该模型上的一组操作。算 法一个重要的公式程序=算法+数据结构l瑞典计算机科学家沃斯（N.Wir
5、th） PASCAL之父及结构化程序设计的首创者。基本概念l算法算法 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法的五个重要特性l有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。l确定性确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。l可行性可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。算法的五个重要特性l输入输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。l输出输出 一个算法有一个或多个输出，这些输出是同输入有着
6、某些特定关系的量。算法设计的要求l正确性正确性 算法应满足具体问题的需求。l可读性可读性 算法应该好读。以有利于阅读者对程序的理解。便于纠正和扩充 。l健状性健状性 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。算法设计的要求l效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。总结评价算法的一般原则l正确性正确性l可读性可读性l健状性健状性l效率与存储量需求效率与存储量需求算法效率的度量l事后统计的方法 因为很多计算机内部都有计时功能，有的甚至可以精确到毫秒级，不同
7、算法的程序可以通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两种缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。l事前分析估算的方法 用数学方法直接对算法的效率进行分析。时间复杂度1.一个算法所需的运算时间通常与所解决问题的规模大小有关。2.用n 表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。3.不同的T(n)算法，当n增长时，运算时间增长的快慢往往差别很大。时间复杂度l一个算法所需的执行时间就是该算法中所有语句执行次数之和。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个
8、函数，算法的时间量度记作： T(n)=O(f(n) 其中，大写字母O为Order(数量级)的首字母，f(n)为函数形式，如T(n)=O(n2)。时间复杂度 T(n)=O(f(n)的含义是随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。说明： 时间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是问题规模n的增大，算法执行时间的变化趋势。补充定理l定理：定理： 若A(n)=a m n m +a m-1 n m-1 +a1n+a0 是一个m次多项式，则A(n)=O(n m)例1l计算下面交换i和j内容程序段的时间复杂性。 te
9、mp=i; i=j; j=temp; 解答：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1). 例21.for(i=1; i=n;+i) （n次 ）2. +x; s+=x; （n次 ）解答：其时间复杂度为：O(n) 即时间复杂度为线性阶。 例3l计算下面求累加和程序段的时间复杂性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ）解答： T(n)=2n2+n+1 =O(n2) 即时间复杂度为平方阶。
10、例41. for( i=2; i=n; +i )2. for( j=2; j=i-1; +j )3. +x ; aij=x; 解答： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2l时间复杂度为O(n2)六种最常用的计算算法时间的多项式O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)补充：l指数时间的关系为：O(2n)O(n!)1 & change;-i) change=false; for(j=0;jaj+1) aj aj+1; change=TURE 分析l当数据初始序列已经自小到大有序，最好情况：0次。l当数据初始序列已
11、经自大到小有序，最坏情况：1+2+3+n-1=n(n-1)/2。l平均时间复杂度为:O(n2)分析下列算法的时间复杂性lsum=0; for (i=1;i=n;i+) sum=sum+i; lsum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij; 空间复杂度l以空间复杂度作为算法所需存储空间的度量，记作： S(n)=O(f(n)l其中n为问题的规模(或大小)。一个程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无
12、关，则只需分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。如果所占空间量依赖于特定的输入，则除特别注明外，均按最坏情况分析。习题与练习l名词解释1.数据2.数据项3.数据元素4.数据结构5.数据逻辑结构6.数据物理结构7.算法8.算法的时间复杂性算法分析硬件厂商AMD公司宣称他们最新研制的CPU运行速度为Intel公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n！的各算法，若用Intel公司的计算机在1小时内能求解输入规模为n的问题，那么用AMD公司的计算机一小时内分别能解输入规模为多大的问题？
