[计算机软件及应用]第1章 绪论

《[计算机软件及应用]第1章 绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1数据结构及应用算法教程(修订版)配套课件2第1章绪论本章将讲述数据结构的各种概念和定义。使用类C语言描述数据结构的算法时，引入了少量的C++语言扩展的内容，以有利于算法的表达。算法分析的方法是评估数据结构及其算法效率的重要依据，该方法将贯穿全书的始终。考虑内容的连贯，绪论课件中含抽象数据类型的介绍，有关的运用细节可参见教科书的第10章。讲授本章课程大约需4课时。31.1数据结构讨论的范畴1.2与数据结构相关的概念1.3算法及其描述和分析41.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs算法+数据结构=程序程序设计

2、:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型5结构静力分析计算例如:数值计算的程序设计问题──线性代数方程组──环流模式方程(球面坐标系)全球天气预报6非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围7例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局8例三：足协的数据库管理算法：?模型：?需要管理的项目？如何管理？用户界面？各种表格9概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。101.2与数

3、据结构相关的概念一、基本概念和术语二、数据结构三、数据类型和抽象数据类型11一、基本概念和术语所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。12是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位13数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是姓名俱乐部名称出生日期参加日期职务业绩称之为组合项年月日编号关键码14二、数据结构数据结构是带“结构”的数据元素的集合。15假设用三个4位的十进制数表示一个含12位数的十进制数。3214,658

4、7,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:示例一：16在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}a1a3a5a2a4a6a1a2a3a4a5a6示例二：17在一维数组{a1,a2,a3,a4,

5、a5,a6}的数据元素之间存在如下的次序关系:{

6、i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”示例三：18数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构19数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。20数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？21数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101

7、000001)2A=(101)8=(001000001)222关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xyC23链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx24在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。25例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型。typedefintLong_in

8、t[3]；定义长整数为:26在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。三、数据类型和抽象数据类型数据类型27例如，C语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool（C++语言）双精度型double实型（C++语言）28数据类型是一个值的集合和定义在此集合上的一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。29抽象数据类型(AbstractDataT