数据结构-软件基础概述

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机软件技术基础,主讲：张 静,二系二教,学习内容及要求,数据结构,掌握数据结构的,类型、算法,及编程技巧，能用,形式语言,描述算法和简单评估算法性能，并且能用自己熟悉的,语言,(推荐：C语言)编程实现算法。,操作系统,掌握操作系统的,基本功能、主要组成部分,，,多道程序,环境下出现的问题及解决方法，以及并,行程序设计,的有关概念和方法。,课堂教学、思考题、上机实践、考试,数据结构C,唐策善等 高等教育出版社,数据结构,严蔚敏 清华大学出版社,操作系统精髓与设计原理,William Stallings 著，清华大学出版社,操作系统设计与实现,(第二版)Andrew S.Tanenbarm 清华大学出版社,参考书,是设计和实现编译程序、操作系统、数据库系统以及其他,系统程序和应用程序,的基础。,它不仅仅是计算机专业的,核心课程,，也是其他非计算机专业的,主要选修课程,之一。,课程抽象，内容丰富，学习,难度较大,。,数据结构课程的地位和特点,CHAP.2,数据结构,(1)把具体问题抽象成相应模型，选择适当的数据结构(,逻辑结构,)；,(2)选择合适的,存储结构,，即如何将问题中所用到的数据存储到计算机中去；,(3)根据具体的问题在相应的存储结构上进行,操作或运算,，并得出结果；,(4)检查算法的正确性，进行,效率分析,。,解决具体问题的基本步骤：,CHAP.2,数据结构,2.1.2,概念、术语,数据,(Data),：,是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的,集合,。,数值性数据,(,整数、定点数、浮点数,),非数值性数据,(,图像、声音、文字数据,),信息与数据的关系：,信息是具有一定含义的数据,信息是经过加工,(,处理,),后的数据,信息是对决策有价值的数据,概念、术语,数据元素(Data Element)：,数据的基本单位，即数据集合中的一个个体，又称为,元素、结点、顶点、记录。,数据元素可由若干,数据项(Data Item),组成：数据项是数据的最小单位。,关键字(key)：,唯一能识别一个数据元素的数据项,。,数据项(Data Item),姓,名,俱乐部名称,出生日期,年 月 日,入队 日期,职,位,业,绩,数据元素,Data Element,数据项,Data Item,数据字段,Data Field,概念、术语,数据对象(data object)：,性质相同的数据元素集合。,如：,整数的数据对象,N=0,1,2,字母字符的数据对象,C=A,B,Z。,概念、术语,数据类型(data type)：,是变量可能取的值和能做的运算的集合。即：,数据对象+操作(运算),如：矩阵(求转置、加、乘、求逆、求特征值),构成一个,矩阵的数据类型,概念、术语,1)基本数据类型(原子数据类型),如：,C,语言中的基本数据类型,int char float double void,整型 字符型 浮点型 双精度型 无值,2)结构数据类型,如：数组、结构、联合、枚举,struct student,char name;,int sex;,float achievement;,数据结构(Data Structure)：,是指同一数据对象的所有数据成员之间的,关系,。记为：,Data_Structure=D,R,其中，D 是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。,如：,n,维向量,x,=(,x,1,x,2,x,n,),D=,x,1,x,2,x,n,R=,概念、术语,1)逻辑结构,描述数据元素间的逻辑关系，与存储无关，独立于计算机，为具体问题抽象出来的数学模型。,数据的逻辑结构有：,线性结构：,有且仅有一个开始结点和一个终端结点，所有结点最多只有一个直接前趋和一个直接后继,(线性表),。,非线性结构：,一个结点可能有多个直接前趋和直接后继,(树、图(网络),。,概念、术语,bin,dev,etc,lib,user,2,1,14,13,12,11,2,3,4,6,7,8,9,10,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,5,5,线性结构,树形结构,树,二叉树,二叉排序树,堆结构,12,3,5,4,8,7,11,10,2,9,1,6,1,2,5,6,4,3,1,2,5,4,3,6,11,33,18,14,6,6,5,19,21,图结构,网络结构,2)物理结构(存储结构),数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言。,数据元素及其关系在计算机存储器内的表示(映象)。,数据元素表示：,位串,概念、术语,数据的存储结构可采用四种基本存储方法：,顺序存储表示：,把逻辑相邻的结点存储在物理位置相邻的存储单元。,(数组),链接存储表示：,不要求逻辑相邻的结点在物理位置上相邻。,(指针),索引存储表示：,存储结点同时，建立附加的索引表。索引项(关键字、地址),散列存储表示：,根据结点的关键字直接计算出该结点的存储地址，以实现对结点的存储和访问。,概念、术语,3)运算,对数据施加的操作。,概念、术语,每种逻辑结构都涉及到一些基本运算，这些基本运算实际上是定义在抽象的数据上的一系列,操作,。,最常用的运算有：,检索、插入、删除、更新、排序等。,数据结构概念说明：,概念、术语,同一批数据可以抽象出不同的逻辑结构,同一逻辑结构采用不同的存储方法，可以得到不同的存储结构，并冠以不同的名称；,给定数据的逻辑结构和存储结构，运算不同，导致不同数据结构。,存储方法可以单独使用，也可以结合起来使用；,数据结构的逻辑结构、存储结构、运算三个方面是一个整体；,运算是数据结构的重要方面,如：顺序表、链表、散列表,如：顺序栈、顺序队列、链栈、链队列,数值的计算,数据的处理,数据结构的发展,数据结构在计算机科学中的地位,算法数据结构程序,程序设计的,实质,是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。,2.1.1,概 述,例一：电话号码查询问题,电话号码查询问题的索引存储,2.1.1,概 述,A,B,C,D,F,D,E,安排竞赛项目的数据结构模型,参赛选手比赛项目表,例二：田竞赛的时间安排问题,A,C,F,B,D,E,2.1.1,概 述,算法描述,逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。,算法定义,算法,是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作,。,算法需满足下述准则：,1),输入：,具有0个或多个输入的外界量，是算法开始前对算法给出的最初量。,2),输出：,至少产生一个输出，是同输入有某种关系的量。,3),有穷性：,每一条指令的执行次数必须是有限的。,4),确定性：,每条指令的含义明确，无二义性。,5),可行性：,每条指令的执行时间是有限的。,算法描述,算法概念说明：,算法,对任何输入，执行有限条指令一定终止，在有限时间内必须完成，即不会陷入无限循环。,程序,不一定满足有穷性，,如：OS,程序指令,是机器可执行的，,算法指令,无此限制。,算法描述,联系：,算法用机器可执行的语言来书写，就变成一个程序。,算法语言,：自然语言、数学语言、符号语言等。,本书采用：高级语言,+,自然语言,评价算法优劣标准：,正确性：,不含语法错误,对几组数据运行正确,对典型、苛刻的数据运行正确；,对所有数据运行正确,效率：,高效、低存储需要。,健壮性：,当输入非法数据时，算法也能作出适当反应，而不会出现莫名其妙的输出结果。,可读性,算法分析,算法运行时间要素,（1）对源程序进行编译所需的时间,（2）程序运行时所需数据输入的时间,（3）机器执行每条指令所需时间,（4）程序中的每条指令重复执行的次数,说明：,1、,前三条取决运行程序的机器的软、硬件系统，不能作为评价算法时间性能的标准，仅第四条反映了算法的计算量。,2、,假设每条指令执行所需时间为,单位时间,。因此算法的时间耗费可以用指令重复执行的次数(也称,频度,T(n)进行度量。,算法分析,时间复杂度：,算法时间=,每条语句执行时间,之和,(该语句执行次数(频度)*,该语句执行一次所需时间),=所有语句的频度之和,算法分析,语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为,单位时间,int i,j,k;(1)for(i=0;in;i+),n+1,(2)for(j=0;jn;j+),n(n+1),(3)cij=0;,n,2,(4)for(k=0;kn;k+),n,2,(n+1),(5)cij=cij+aik*bkj;,n,3,T(n)=(n+1)+n(n+1)+n,2,+n,2,(n+1)+n,3,=2n,3,+3n,2,+2n+1,为方阵的阶n的函数。,当n趋于无穷大时，T(n)/n,3,2 即T(n)与n,3,是同阶的，可记为T(n)=O(n,3,)，称为该算法的,(渐进)时间复杂度,(time complexity)。,#define n,自然数,float ann,bnn,cnn;,例1.4 求两个n阶方阵的乘积 C=AB,其算法描述如下：,算法分析,表示方法：,T(,n,)=O(F(,n,),F(n),表示基本操作重复执行的次数，是,n,的某个函数，随问题规模,n,的增大，算法执行时间的增长率和F(,n,)的增长率属于同一数量级；,O,表示F(,n,)和T(,n,)只相差一个常数倍。,T(,n,),称做渐进时间复杂度，简称时间复杂度。,算法分析,时间复杂度分析技巧：,时间复杂度以算法中,频度最大,的语句度量。,由嵌套层数最多的循环语句中最内层语句的频度,F(n)决定,时间复杂度是,n,的函数,问题,规模,n,：求解问题的输入量,(如：数据元素个数),。,时间增长趋势：问题规模,n,趋向无穷大。,算法分析,例一：交换a和b的内容,temp=a;a=b;b=temp;,T(n)=O(1),例二：变量记数之一,(1)x=0;y=0;,(2)for(k=1;k=n;k+),(3)x+;,(4)for(i=1;i=n;i+),(5)for(j=1;j=n;j+),(6)y+;,频度最大的语句是(6)，且f(n)=n,2,，所以该程序段的时间复杂度为,T(n)=O(n,2,),算法分析,常见时间复杂度：,常数阶 O(1),对数阶 O(log,2,n),线性阶 O(n),线性对数阶 O(nlog,2,n),平方阶 O(n,2,),立方阶 O(n,3,),k次方阶 O(n,k,),指数阶 O(2,n,),时间复杂度递增,算法分析,递增,最坏时间复杂度和平均时间复杂度,很多算法的时间复杂度不仅仅是问题规模的函数，还与它所处理的数据集的状态有关，在这种情况下，通常是根据数据集中可能出现的最坏情况，估计出算法的,最坏时间复杂度,。,有时对数据集的分布作出某种假设(如等概率)，讨论算法的,平均时间复杂度,。,算法分析,在数组An中查找值为K的元素，若找到，则返回位置I(0=I=0)&(Ai!=K),(3)i-;,(4)return i;,最坏事件时间复杂度T(n)=n,例：,算法分析,空间复杂度,(Space Complexity)S(n)：,算法分析,算法所耗费的存储空间，仍是问题规模n的函数。,记作：,S(n)=O(f(n),存储空间的固定部分,程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间,可变部分,尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,空间复杂度：所需,辅助,空间。,时间与空间是矛盾。,算法分析,