数据结构 第一章讲稿.doc

引入我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。如1. 图书馆的书目检索自动化问题-计算机处理的对象之间存在着线性关系，称为线性的数据结构。2. 人机对奕问题-计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。3. 多岔路口交通灯的管理问题-数学模型是图的数学结构。非数值计算问题的数学模型是表、树和图之类的数据结构。数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算）概念数据，数据对象，数据结构，数据类型及抽象数据类型，算法主要内容11基本概念和术语1 .1 .1 数据的概念* 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。* 现代数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。* 数据项：有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。 1.1.2 数据对象和数据结构* 数据对象：是性质相同的数据元素的集合，是数据的一个子集。* 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构一般包括三方面的内容：逻辑结构：数据元素之间的逻辑关系。存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。数据的运算：对数据施加的操作。1.1.3 数据存储结构* 从顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里， 结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。* 链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述1.1.4 数据类型和抽象数据类型* 数据类型：是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。* 抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。象数据类型的定义由一个值域和定义在抽该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型：原子类型:变量的值是不可分解的。固定聚合类型:变量的值由确定数目的成分按某种结构组成。可变聚合类型:其值的成分数目不确定。12算法和算法分析1.2.1 算法的概念算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出。描述方法：高级语言，表格，图形，类自然语言。例：求两个正整数m和n的最大公因子(m=36，n=16)1. 取m/n的余数r; (36/16, r=4; )2. 判断r是否为0：若r=0，输出n, 结束；否则，转下一步；(r0)3. 更新被除数和除数：m=n, n=r，执行第一步；(m 16, n 4;)再转（1）执行，16/4=0, 故退出，得余数为4。算法流程图如下：(r=m%n)= =0输出n输入m和nm = n, n = r1.2.2 算法设计的步骤和方法1、算法设计步骤 描述问题 建立模型 设计算法 验证算法的正确性 算法的实现 算法的分析2、算法设计步方法1) 枚举法：从问题的所有可能答案中找出满足条件的解。例：买鸡问题：公鸡每只5元，母鸡每只3元，小鸡3只一元，100元买100只鸡，有多少种买法？ 算法实现如下：main() int x,y,z; for(x=1;x=20;x+) for(y=1;y=33;y+) z=100-x-y; /*百鸡*/ if(5*x+3*y+z/3= =100) printf(“cock=%3d, hen=%3d; Chicken=%3dn”, x,y,z);2) 归纳法：找出问题的规律 递推：逐次推求中间结果和最后结果。例： 计算Fibonacci数列：数列第1项为1，第2项为1，从第三项开始，每一项等于前两项之和。 f = (1,1,2,3,5,8,13,21,34, )实现途径：可以利用数组，也可以不用数组。递归：自己调用自己。例：计算阶乘F(n)=F(n-1)*n, F(1)=1。算法实现如下： main() int fn(); int f, n; scanf(“%d”,&n); f=fn(n); printf(“the result is %d”,f); 3) 回溯法：通过“试”找到问题的解。如在一些游戏中，找出一个解决问题的途径，然后选出一条“试走”，若此路不通，退回换路线重走。1.2.3算法效率的度量* 衡量算法的标准： 正确性、时间复杂度（Time Complexity）、空间复杂度( Space Complexity )，是否易读，易于调试，测试等。* 算法耗费时间：每条语句执行时间（该语句执行次数和单次执行时间之积）之和。* 频度(Frequency Count):语句重复执行的次数。* 问题规模n：矩阵的阶，多项式中的项数等。* 时间复杂度T(n)：是n的函数，是算法的所有语句的频度之和（即算法的时间耗费）* 算法的渐近时间复杂度：问题规模n趋向无穷大时时间复杂度T(n)的数量级（阶）。* 举例计算时间复杂度的例子 # define n 4 matrixmlt(A,B,C) float Ann,Bnn,Cnn; int i,j,k; for(i=0;in;i+) n+1 for(j=0;jn;j+) n(n+1) Cij=0; n2 for(k=0;kn;k+) n2(n+1) Cij=Cij+Aik*Bkj; n3 T(n)=2n3+3n2+2n+1当n趋于无穷时T(n)和n3同阶，数量级相同。T(n)=O(n3): 算法的渐近时间复杂度。一般都用频度最大的语句来进行度量，时间复杂度的各种情况变化。例：在一维数组An中查找等于给定值 X 的元素的算法。int search(A,n,x)int A,n,x;int i=0;while(in) return 0; /这句是否正确？else return i;此算法的时间复杂度取决于循环中条件的判别次数，判别次数则依赖于数组的具体分布情况：如果第一个元素的值=x，则时间复杂度=O(1)；如果最后一个元素的值才等于x时，时