婴儿做核磁共振的危害 婴儿做核磁共振危害大吗

数据结构主讲人刘英“数据结构”作为一门独立的课程在国外是从1968年才开始设立的，由美国唐·欧·克努特教授开创其最初体系，他所著的《计算机程序技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。我国于1978年开设本课程。数据结构的发展史1、数据结构在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和应用程序的重要基础。数据结构的地位教学内容1.1数据结构讨论的范畴1.2基本概念1.3算法及量度瑞士著名的计算机科学家、Pascal语言发明者沃思(N.Wirth)教授提出：程序=算法+数据结构程序设计:算　　法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型1.1数据结构的讨论范畴算法（解决问题的）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。分情况讨论：①a=0，不是二次方程。②b2-4ac=0，有两个相等实根。③b2-4ac＞0，有两个不等实根。④b2-4ac＜0，有两个共轭复根。【例5.6】求ax2＋bx＋c=0方程的解。算法（解决问题的方法）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。猴子吃桃问题猴子第一天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。例1：计算机电话号码查询系统算法：基本操作“比较两条记录是否相等”模型：电话号码记录的表示 学院和电话号码的次序无规律，则只能逐一比较学院名字进行查找。2.如果学院名按字典次序组织，则查找就快捷多了。数据之间的排列关系直接影响到算法的好坏，也就是说数据之间是有联系的。（需要）这种联系是内在的，它表现的是一种可见的结构。联系是：一对一人与电脑下象棋1996年2月17日，国际象棋世界冠军加里·卡斯帕罗夫以4∶2的优势击败了电脑对手“深蓝”。1997年，卡斯帕罗夫与有着更深“功力”的“深蓝II”再次对决，卡斯帕罗夫在6局较量中败下阵来。IBM例2：计算机和人对弈问题算法：对弈的和策略模型：棋盘和棋子的表示井字棋由两人对弈，期盘为3x3的方格，当一方的3个棋子占同一行，或同一列，或同一对角线便为胜方。设每个书目含：书名，作者，登陆号，分类，出版年月对图书目录常有如下操作：☆查找-某书在书库中是否存在？☆插入-购进新书时登陆☆删除-报废或丢失的书，需从目录中去掉例3：图书目录管理图书书目还是一种线性结构，之所以考虑结构是为了进行一定的操作。有了数据，数据之间进行了一定的排列，那我们就可以定义相应的运算。 数据的各种逻辑结构和物理结构，以及它们之间的关系 为每种结构定义相应的运算 设计相应的算法 分析算法的效率综上所述：《数据结构》研究的内容是数据(Data)它是计算机操作对象的总称。数据是个集合，可用集合的表示方法来写：　　　　数据={x|x是计算机操作的对象}1.2基本概念及术语文字图像声音数据凡是能够通过键盘、扫描仪、数字化仪录入到计算机的数据列举法是将其中的数据元素一一列举出来，在数据元素有限的情况下可采用。课件中的方法属于描述法。数据元素(DataElement)：是数据(集合)中的一个“个体”，是数据的“基本单位”，在计算机程序中通常作为一个整体进行考虑和处理。两类数据元素不可分割的“原子”型数据元素如：整数“5”，字符“N”等；由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。 姓名 出生日期 成绩 年 月 日 洪伟 1986.11.2 68 陈键 1987.4.08 85数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。例：整数数据对象的集合可表示为N={0,±1,±2,…}，字母字符数据对象的集合可表示为C={‘A’,’B’,…,’Z’}。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。结构：数据元素之间的相互关系。321465879345 假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345a1(3214),a2(6578),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a1a2a3≠6587，3214，9345a2a1a3四类基本结构集合：数据元素除了同属于一种类型外，别无其它关系。线性结构：一对一。树型结构：一对多。图状结构或网状结构：多对多。对这些基本结构进行举例说明数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集S是D上关系的有限集。例：复数的数据结构：Complex=(C,R)其中：C是含两个实数的集合{c1,c2}，R={P}，P是定义在集合C上的一种关系{<c1,c2>}，分别表示复数的实部和虚部。逻辑结构(logicalstructure)逻辑结构是数据之间关系的描述独立于计算机，是数据本身所固有的。物理结构：数据的逻辑结构在计算机中的存储形式(映象)。存储结构(StorageStructure)必须依赖于计算机。数据结构描述的是数据的逻辑结构，同一逻辑结构可以采用不同的存储结构。数据结构在计算机中的表示方法顺序映象非顺序映象——顺序存储结构——链式存储结构用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。在每一个数据元素中增加一个存放地址的指针(pointer)，用此指针来表示数据元素之间的逻辑关系。数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。值的集合+值集合上的一组操作例如，C语言中的short型变量，是指由-32768到32767范围中的值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。约束变量或常量的取值范围，约束变量或常量的操作。数据类型的作用在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。所有高级语言中都有“整型”数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是“相同”的。程序员使用它们时仅需了解它们的数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个“整数类型”，而这个“整数类型”的定义仅对“整数的数学特性”有明确规定。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型(AbstractDataType，简称ADT)：ADT抽象数据类型名{数据对象:〈数据对象的定义〉数据关系:〈数据关系的定义〉基本操作:〈基本操作的定义〉}ADT抽象数据类型名抽象数据类型(AbstractDataType)的描述方法：可用(D,S,P)三元组表示，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。基本操作的定义格式：赋值参数：只为操作提供输入值；引用参数：以&打头，既可提供输入值，还可返回结果。描述操作执行前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。说明操作正常完成之后，数据结构的变化状况和应返回的结果。基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉例：抽象数据类型“复数”的定义ADTComplex{　数据对象：D={e1,e2|e1,e2∈RealSet}基本操作：　　InitComplex(&Z,v1,v2)　　　操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。　　DestroyComplex(&Z)　　　初始条件：复数Z已存在。操作结果：复数Z被销毁。　　　数据关系：R1={<e1,e2>|e1是复数的实部，e2是复数的虚部}用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。　　GetReal(Z,&realPart)　　　初始条件：复数Z已存在。操作结果：用realPart返回Z的实部值。　GetImag(Z,&ImagPart)　　　初始条件：复数Z已存在。操作结果：用ImagPart返回Z的虚部值。　　Add(Z1,Z2,&sum)　　　初始条件：Z1,Z2是复数。操作结果：用sum返回z1,z2的和值。}ADTComplex1.3抽象数据类型的实现例：利用C++语言实现的“复数”类型如下描述：classComplex{private:doublerealpart;//实部　　doubleimagpart;//虚部public:Complex(doublerp=0,doubleip=0);//构造函数~Complex(){}//析造函数doubleGetReal()const;……};抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之为固有数据类型）来表示和实现。1.4.1算法一个有限的指令集，遵循指令流可以完成特定的功能。1.4算法和算法分析一个算法可以用自然语言来描述，也可以用流程图、计算机高级程序语言（如C语言）或伪代码等来描述。如何衡量一个正确算法的好坏？运行所花费的时间（时间特性）所占用存储空间的大小（空间特性）其他（可读性，易读性，健壮性等）算法分析时间和空间特性的巨大改进源自于更好的数据结构和算法随着软件系统的规模越来越大，这些非功能特性显得越来越重要软件工程这么课中，将介绍其他特性等相关内容一个算法的执行时间通常有两种计算方法：(1)、事后统计的方法此方法有两个缺陷：一是必须先运行程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。如何估算算法的时间效率？(2)、事前分析估算的方法一个算法执行时间，从理论上是不能算出来的，必须通过依据该算法编制的程序上机运行测试才能知道。事后统计容易陷入盲目境地，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。显然，后三条受着计算机硬件和软件的制约，既然是“估算”仅需考虑前两条。与算法执行时间相关的因素有：1)算法选用的策略2)问题的规模3)编写程序的语言4)编译程序产生的机器代码的质量5)计算机执行指令的速度一般认为算法的效率只依赖于问题的规模。问题的规模如何计算？例：考虑计算三次多项式ax3+bx2+cx+d方法1：s=axxx+bxx+cx+d(6次乘法，3次加法)计算量大方法2：s=a;s=sx+b;s=sx+c;s=sx+d;(3次乘法，3次加法)计算量小方法2的原理：axxx+bxx+cx+d=(ax+b)x2+cx+d=((ax+b)x+c)x+d问题的规模一般根据问题本身的性质合理地确定：例1：对n个电话号码进行排序，这里n即可作为问题的规模。显然对1000个电话号码进行排序比对10个电话号码进行排序规模要大。例2：求n阶矩阵的转置，这里n即可作为问题的规模。分析：任一算法都是由一个控制结构和若干原操作组成的。控制结构：顺序、分支和循环3种。原操作：指对固有数据类型的操作（如赋值操作、比较操作等等），显然每个原操作的执行时间和算法无关，相对于问题的规模是常量。结论：算法的执行时间可看成是所有原操作的执行时间之和：算法中包含原操作次数的多少叫做算法的时间复杂度，用它来衡量一个算法的运行时间性能。既然执行一种原操作所需的时间与算法无关，那么我们只讨论影响运行时间的另一个因素——算法中进行原操作的次数。算法的时间复杂度通常是问题的规模n的某个函数T(n)。例：累加求和intSum(intb[n],intn){inti,s=0;for(i=0;i<n;i++)s+=b[i];returns;}各执行1次原操作。for循环语句所包含的原操作：i=0;//1次m1:if(i>=n)gotom2;//n+1次s+=b[i];//n次i++;//n次gotom1;//n次m2:returns;时间复杂度为：T(n)=4n+4从上述分析可知，一个算法的时间复杂度的计算相当烦琐。实际上，一般没必要精确地计算出算法的时间复杂度，只要大致计算出相应的数量级(Order)即可。时间复杂度T(n)的数量级表示：定义如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|T(n)|则称f(n)是T(n)的同数量级函数。　把T(n)表示成数量级的形式为：T(n)=O(f(n))。称Ｏ(f(n))为算法的渐近时间复杂度，简称时间复杂度。O是Order的首字母，意为f(n)与T(n)只差一个常数倍。算法效率的度量：采用渐进时间复杂度例：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];}由于是一个三重循环，每个循环从1到n，则原操作重复执行的总次数为：n×n×n=n3，时间复杂度为T(n)=O(n3)。在“累加求和”例中，当n1（即n0=1）时，|n|c|4n+4|均成立，则f(n)=n，T(n)=O(n)。f(n)一般是算法中频度最大的语句的频度。语句频度：语句被重复执行的次数。例：{++x;s=0;}包含“x增1”基本操作的语句的频度为１，即时间复杂度为O(1)。O(1)表示算法的运行时间为常量。例：for(i=1;i<=n;++i){++x;s+=x;}包含“x增1”基本操作的语句的频度为n，其时间复杂度为：O(n)。常量阶线性阶例：for(i=1;i<=n;++i)　　　　for(j=1;j<=n;++j){++x;s+=x;}包含“x增1”基本操作的语句的频度为：n2，其时间复杂度为：O(n2)。平方阶时间复杂度：O(n2)平方阶常见的算法的时间复杂度之间的关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)<O(nn)算法的时间复杂度常见的有：常数阶O(1)，对数阶O(logn)，线性阶O(n)，线性对数阶O(nlogn)，平方阶O(n2)，立方阶O(n3)，…，k次方阶O(nk)，指数阶O(2n)，阶乘阶O(n!)。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：起泡排序Voidbubble-sort(inta[]，intn){//将a中整数序列重新排列成自小至大有序的整数序列for(i=n-1;i>=1;--i)for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];}}最好情况：0次最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为：O(n2)一个算法所需存储空间算法本身的存储空间输入数据的存储空间算法在运行过程中临时占用的存储空间若所需临时空间不随问题规模的大小而改变，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n))其中n为问题的规模。本章是为以后各章讨论的内容作基本知识的准备。本章小结：数据数据元素数据对象加上数据元素之间的关系数据结构集合结构线性结构树形结构图状结构抽象数据类型数据对象数据关系基本操作存储结构顺序结构链式结构算法特性：有穷性、确定性、可行性、输入、输出衡量：正确性、可读性、健壮性、效率、存储量需求时间复杂度空间复杂度1、理解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念。2、理解并掌握抽象数据类型定义、表示和实现方法。3、掌握计算语句频度和估算算法时间复杂度的方法。教学要求算法（解决问题的方法）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。算法（解决问题的方法）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。数据之间的排列关系直接影响到算法的好坏，也就是说数据之间是有联系的。（需要分析）这种联系是内在的，它表现的是一种可见的结构。联系是：一对一IBM井字棋由两人对弈，期盘为3x3的方格，当一方的3个棋子占同一行，或同一列，或同一对角线便为胜方。图书书目还是一种线性结构，之所以考虑结构是为了进行一定的操作。有了数据，数据之间进行了一定的排列，那我们就可以定义相应的运算。凡是能够通过键盘、扫描仪、数字化仪录入到计算机的数据列举法是将其中的数据元素一一列举出来，在数据元素有限的情况下可采用。课件中的方法属于描述法。对这些基本结构进行举例说明数据结构描述的是数据的逻辑结构，同一逻辑结构可以采用不同的存储结构。在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。所有高级语言中都有“整型”数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是“相同”的。程序员使用它们时仅需了解它们的数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个“整数类型”，而这个“整数类型”的定义仅对“整数的数学特性”有明确规定。抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之为固有数据类型）来表示和实现。随着软件系统的规模越来越大，这些非功能特性显得越来越重要软件工程这么课中，将介绍其他特性等相关内容一个算法执行时间，从理论上是不能算出来的，必须通过依据该算法编制的程序上机运行测试才能知道。事后统计容易陷入盲目境地，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。既然执行一种原操作所需的时间与算法无关，那么我们只讨论影响运行时间的另一个因素——算法中进行原操作的次数。