数据结构第一章绪论

《数据结构第一章绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构2009年春DataStructure一、数据结构课程的地位二、学习数据结构课程的方法三、考核办法1.计算机及相关专业的专业基础课。2.程序设计的核心技术。3.一些后继课的基础。1.多思考2.多阅读程序3.多动手(实践)闭卷:平时30分，期末试卷70分。1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学

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

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

4、),a2(6587),a3(9345)“次序”关系a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}数据结构：带结构的数据元素的集合a1a3a5a2a4a6a1a2a3a4a5a6在一维数组{a1,a2,a3,

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

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

7、数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型。typedefintLong_int[3]定义长整数为:C+

8、+语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool双精度型double实型（C++语言）二、数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。ADT抽象数据类型名{数据对象：

9、〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名基本操作的定义格式为:基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉抽象数据类型矩形的定义：数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{

10、e1是矩形长部分

11、e2是矩形的宽部分}ADTRectangle{基本操