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