数据结构-软件基础概述.ppt

1、计算机软件技术基础 主讲：张 静 二系二教,学习内容及要求,数据结构 掌握数据结构的类型、算法及编程技巧，能用形式语言描述算法和简单评估算法性能，并且能用自己熟悉的语言(推荐：C语言)编程实现算法。 操作系统 掌握操作系统的基本功能、主要组成部分，多道程序环境下出现的问题及解决方法，以及并行程序设计的有关概念和方法。 课堂教学、思考题、上机实践、考试,数据结构C唐策善等 高等教育出版社 数据结构严蔚敏 清华大学出版社 操作系统精髓与设计原理William Stallings 著，清华大学出版社 操作系统设计与实现(第二版) Andrew S.Tanenbarm 清华大学出版社,参考书,是设计和

2、实现编译程序、操作系统、数据库系统以及其他系统程序和应用程序的基础。 它不仅仅是计算机专业的核心课程，也是其他非计算机专业的主要选修课程之一。 课程抽象，内容丰富，学习难度较大。,数据结构课程的地位和特点,CHAP. 2 数据结构,(1) 把具体问题抽象成相应模型，选择适当的数据结构(逻辑结构)； (2) 选择合适的存储结构，即如何将问题中所用到的数据存储到计算机中去； (3) 根据具体的问题在相应的存储结构上进行操作或运算，并得出结果； (4) 检查算法的正确性，进行效率分析。,解决具体问题的基本步骤：,CHAP. 2 数据结构,2.1.2 概念、术语,数据(Data)：是信息的载体，是描述

3、客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据(整数、定点数、浮点数) 非数值性数据(图像、声音、文字数据),信息与数据的关系： 信息是具有一定含义的数据 信息是经过加工(处理)后的数据 信息是对决策有价值的数据,2.1.2 概念、术语,数据元素(Data Element)：数据的基本单位，即数据集合中的一个个体，又称为元素、结点、顶点、记录。 数据元素可由若干数据项(Data Item)组成：数据项是数据的最小单位。,关键字(key)：唯一能识别一个数据元素的数据项。,数据项(Data Item),数据元素 Data Element,数据项 D

4、ata Item,数据字段 Data Field,2.1.2 概念、术语,数据对象(data object)：性质相同的数据元素集合。 如： 整数的数据对象N=0,1,2, 字母字符的数据对象C=A,B,Z。,2.1.2 概念、术语,数据类型(data type)：是变量可能取的值和能做的运算的集合。即： 数据对象+操作(运算) 如：矩阵(求转置、加、乘、求逆、求特征值) 构成一个矩阵的数据类型,2.1.2 概念、术语,1) 基本数据类型(原子数据类型) 如：C语言中的基本数据类型 int char float double void 整型 字符型 浮点型 双精度型 无值 2) 结构数据类型

5、如：数组、结构、联合、枚举 struct student char name; int sex; float achievement; ,数据结构(Data Structure) ： 是指同一数据对象的所有数据成员之间的关系。记为： Data_Structure = D, R 其中，D 是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 如：n维向量 x=(x1,x2,xn) D=x1,x2,xn R=,2.1.2 概念、术语,1) 逻辑结构 描述数据元素间的逻辑关系，与存储无关，独立于计算机，为具体问题抽象出来的数学模型。 数据的逻辑结构有： 线性结构：有且仅有一个开始结点和一个

6、终端结点，所有结点最多只有一个直接前趋和一个直接后继(线性表)。 非线性结构：一个结点可能有多个直接前趋和直接后继(树、图(网络)。,2.1.2 概念、术语,user,线性结构,树形结构 树 二叉树 二叉排序树,堆结构,12,3,5,4,8,7,11,10,2,9,1,6,图结构 网络结构,2) 物理结构(存储结构) 数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言。 数据元素及其关系在计算机存储器内的表示(映象)。 数据元素表示：位串,2.1.2 概念、术语,数据的存储结构可采用四种基本存储方法： 顺序存储表示：把逻辑相邻的结点存储在物理位置相邻的存储单元。(数组) 链接存储表示

7、：不要求逻辑相邻的结点在物理位置上相邻。(指针) 索引存储表示：存储结点同时，建立附加的索引表。索引项(关键字、地址) 散列存储表示：根据结点的关键字直接计算出该结点的存储地址，以实现对结点的存储和访问。,2.1.2 概念、术语,3) 运算对数据施加的操作。,2.1.2 概念、术语,每种逻辑结构都涉及到一些基本运算，这些基本运算实际上是定义在抽象的数据上的一系列操作。 最常用的运算有： 检索、插入、删除、更新、排序等。,数据结构概念说明：,2.1.2 概念、术语,同一批数据可以抽象出不同的逻辑结构 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构，并冠以不同的名称； 给定数据的逻辑结构和

8、存储结构，运算不同，导致不同数据结构。 存储方法可以单独使用，也可以结合起来使用； 数据结构的逻辑结构、存储结构、运算三个方面是一个整体； 运算是数据结构的重要方面,如：顺序表、链表、散列表,如：顺序栈、顺序队列、链栈、链队列,数值的计算 数据的处理,数据结构的发展,数据结构在计算机科学中的地位,算法数据结构程序,程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。,2.1.1 概 述,例一：电话号码查询问题,电话号码查询问题的索引存储,2.1.1 概 述,安排竞赛项目的数据结构模型,参赛选手比赛项目表,例二：田竞赛的时间安

9、排问题,2.1.1 概 述,2.1.3 算法描述,逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。,算法定义,算法是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。,算法需满足下述准则： 1) 输入：具有0个或多个输入的外界量，是算法开始前对算法给出的最初量。 2) 输出：至少产生一个输出，是同输入有某种关系的量。 3) 有穷性：每一条指令的执行次数必须是有限的。 4) 确定性：每条指令的含义明确，无二义性。 5) 可行性：每条指令的执行时间是有限的。,2.1.3 算法描述,算法概念说明： 算法对任何输入，执行有限条指令一定终止，在有限时间内

10、必须完成，即不会陷入无限循环。 程序不一定满足有穷性，如：OS 程序指令是机器可执行的，算法指令无此限制。,2.1.3 算法描述,联系：算法用机器可执行的语言来书写，就变成一个程序。,算法语言：自然语言、数学语言、符号语言等。 本书采用：高级语言+自然语言,评价算法优劣标准： 正确性： 不含语法错误 对几组数据运行正确 对典型、苛刻的数据运行正确； 对所有数据运行正确 效率： 高效、低存储需要。 健壮性： 当输入非法数据时，算法也能作出适当反应，而不会出现莫名其妙的输出结果。 可读性,2.1.4 算法分析,算法运行时间要素,（1）对源程序进行编译所需的时间 （2）程序运行时所需数据输入的时间

11、（3）机器执行每条指令所需时间 （4）程序中的每条指令重复执行的次数,说明： 1、前三条取决运行程序的机器的软、硬件系统，不能作为评价算法时间性能的标准，仅第四条反映了算法的计算量。 2、假设每条指令执行所需时间为单位时间。因此算法的时间耗费可以用指令重复执行的次数(也称频度T(n)进行度量。,2.1.4 算法分析,时间复杂度： 算法时间=每条语句执行时间之和 (该语句执行次数(频度)* 该语句执行一次所需时间) =所有语句的频度之和,2.1.4 算法分析,语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间, int i,j,k

12、; (1) for (i=0;in;i+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) cij=0; n2 (4) for(k=0;kn;k+) n2(n+1) (5) cij=cij+aik*bkj; n3 ,T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1为方阵的阶n的函数。 当n趋于无穷大时，T(n)/n 32 即T(n)与n3是同阶的，可记为T(n)=O(n3)，称为该算法的(渐进)时间复杂度(time complexity) 。,# define n 自然数 float ann, bnn, cnn;,例1.4 求两个n

13、阶方阵的乘积 C=AB,其算法描述如下：,2.1.4 算法分析,表示方法： T(n)=O(F(n) F(n) 表示基本操作重复执行的次数，是n的某个函数，随问题规模n的增大，算法执行时间的增长率和F(n)的增长率属于同一数量级； O 表示F(n)和T(n)只相差一个常数倍。 T(n) 称做渐进时间复杂度，简称时间复杂度。,2.1.4 算法分析,时间复杂度分析技巧： 时间复杂度以算法中频度最大的语句度量。 由嵌套层数最多的循环语句中最内层语句的频度F(n)决定 时间复杂度是n的函数 问题规模n：求解问题的输入量(如：数据元素个数)。 时间增长趋势：问题规模n趋向无穷大。,2.1.4 算法分析,例

14、一：交换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)=n2，所以该程序段的时间复杂度为T(n)=O(n2),2.1.4 算法分析,常见时间复杂度： 常数阶 O(1) 对数阶 O(log2n) 线性阶 O(n) 线性对数阶 O(nlog2n) 平方阶 O(n2) 立方阶 O(n3) k次方阶 O(nk) 指数阶 O(2n),时间复杂度递增,2.1.4 算法分析,递增,最坏时间复杂度和平均时间复杂度,很多算法的时间复杂度不仅仅是问题规模的函数，还与它所处理的数据集的状态有关，在这种情况下，通常是根据数据集中可能出现的最坏情况，估计出算法的最坏时间复杂度。 有时对数据集的分布作出某种假设(如等概率)，讨论算法的平均时间复杂度。,2.1.4 算法分析,在数组An中查找值为K的元素，若找到，则返回位置I(0=I=n-1)；否则返回-1，算法如下：,(1)i=n-1 (2)while(I=0),最坏事件时间复杂度T(n)=n,例：,2.1.4 算法分析,空间