数据结构：绪论、算法

1、数据结构第一章 绪论数据结构研究的内容 数据结构的研究内容： 数据元素之间的相互关系(逻辑结构)数据结构 数据元素在计算机中的存储(存储结构) 算法实现数据元素之间的相互关系： 线性结构（一对一） 逻辑结构 树形结构（一对多）：层次 图形结构（多对多）：网状 顺序存储 存储结构 链式存储基本概念-数据数据 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序加工处理的符号的总称，它是计算机加工的原料的集合。 如图像、声音等都可以通过编码而归之于数据的范畴。基本概念-数据元素数据元素 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。每一个数据元素可以只有一个数据

2、项（内存中称为域），也可以由若干数据项组成。 数据元素的同义语有：结点、顶点和记录等。基本概念-数据项数据项是数据的不可分割的最小单位 。基本概念-数据对象数据对象 是性质相同的数据元素的集合，它是数据的一个子集。数据对象可以是有限的，也可以是无限的比较和总结数据数据元素数据项数据对象基本概念-数据结构数据结构数据之间的相互关系，即数据的组织形式。说明： 研究数据结构，就是指研究数据的逻辑结构和物理结构 。数据的逻辑结构：数据元素之间的逻辑关系数据的物理结构：数据元素在计算机存储器中是如何存储的数据的逻辑结构集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性关系 结构

3、中的数据元素之间存在一个对一个的关系。集合线性结构数据的逻辑结构树形结构 结构中的数据元素之间存在一个对多个的关系。图状结构或网状结构 结构中的数据元素之间存在多个对多个的关系。对比和总结一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。数据的存储结构数据元素及其关系在计算机存储器中的表示数据的存储可以用以下四种基本的存储方法得到：顺序存储方法链接存储方法索引存储方法散列存储方法 总结数据的逻辑结构和存储结构是数据结构

4、的两个密切相关的的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于设计的逻辑结构，而算法的实现依赖于指定的存储结构。补充一些概念数据的运算对数据施加的操作。数据类型原子类型（不可分解）结构类型抽象数据类型一个数学模型以及定义在该模型上的一组操作。算 法一个重要的公式程序=算法+数据结构瑞典计算机科学家沃斯（N.Wirth） PASCAL之父及结构化程序设计的首创者。基本概念算法 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法的五个重要特性有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性 算法中每一条指令必须

5、有确切的含义。不存在二义性。且算法只有一个入口和一个出口。可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。算法的五个重要特性输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法设计的要求正确性 算法应满足具体问题的需求。可读性 算法应该好读。以有利于阅读者对程序的理解。便于纠正和扩充 。健状性 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。算法设计的要求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中

6、所需要的最大存储空间。一般，这两者与问题的规模有关。总结评价算法的一般原则正确性可读性健状性效率与存储量需求算法效率的度量事后统计的方法 因为很多计算机内部都有计时功能，有的甚至可以精确到毫秒级，不同算法的程序可以通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两种缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。事前分析估算的方法 用数学方法直接对算法的效率进行分析。时间复杂度一个算法所需的运算时间通常与所解决问题的规模大小有关。用n 表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的

7、T(n)算法，当n增长时，运算时间增长的快慢往往差别很大。时间复杂度一个算法所需的执行时间就是该算法中所有语句执行次数之和。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作： T(n)=O(f(n) 其中，大写字母O为Order(数量级)的首字母，f(n)为函数形式，如T(n)=O(n2)。时间复杂度 T(n)=O(f(n)的含义是随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。说明： 时间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是问题规模n的增大，算法执行时间的变化趋势。补充定

8、理定理： 若A(n)=a m n m +a m-1 n m-1 +a1n+a0 是一个m次多项式，则A(n)=O(n m)例1计算下面交换i和j内容程序段的时间复杂性。 temp=i; i=j; j=temp; 解答：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1). 例2for(i=1; i=n;+i) （n次 ） +x; s+=x; （n次 ）解答：其时间复杂度为：O(n) 即时间复杂度为线性阶。 例3计算下面求累加和程序段的时间复杂性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n

9、次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ）解答： T(n)=2n2+n+1 =O(n2) 即时间复杂度为平方阶。例4 for( i=2; i=n; +i ) for( j=2; j=i-1; +j ) +x ; aij=x; 解答： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2时间复杂度为O(n2)六种最常用的计算算法时间的多项式O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)补充：指数时间的关系为：O(2n)O(n!)1 & change;-i) change=false

10、; for(j=0;jaj+1) aj aj+1; change=TURE 分析当数据初始序列已经自小到大有序，最好情况：0次。当数据初始序列已经自大到小有序，最坏情况：1+2+3+n-1=n(n-1)/2。平均时间复杂度为:O(n2)分析下列算法的时间复杂性sum=0; for (i=1;i=n;i+) sum=sum+i; sum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij; 空间复杂度以空间复杂度作为算法所需存储空间的度量，记作： S(n)=O(f(n)其中n为问题的规模(或大小)。一个程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。如果所占空间量依赖于特定的输入，则除特别注明外，均按最坏情况分析。习题与练习名词解释数据