徐孝凯数据结构PPT第一章绪论.ppt

数据结构实用教程,（C/C+描述）徐孝凯编著,第一章绪论,1.1基本术语1.2算法描述1.3算法评价,1.1基本术语,数据（Data）：是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。（在计算机领域中：能被计算机输入、存储、处理、输出的一切信息）数据元素（DataElement简称元素）：数据整体中相对独立的单位。（各领域中的名称：记录、结点、节点、顶点等）数据记录（DataRecord）：数据处理领域组织数据的基本单位。数据项：记录属性的描述（字段）。关键项（KeyItem）:能唯一标识一个记录的数据项。关键字（KeyWord或Key）：关键项中的每一个值。,1.1基本术语,数据处理（DataProcessing）：指对数据进行检索、插入、删除、合并、拆分、排序、统计、简单计算、转换、输入、输出等操作过程。数据结构（DataStructure）：数据及其相互之间的联系。包括三个方面：1、数据的逻辑结构（数据之间的相互联系）2、数据的物理结构（数据结构在存储器中的存储方式）3、数据的运算（在数据结构上施加的各种操作）注：通常所说的数据结构是指数据的逻辑结构。数据结构的分类：1、线性结构。（唯一的开始，唯一的终点，中间任何结点有唯一的直接前趋和唯一的直接后继）2、非线性结构。（树形结构、图形结构、集合）,常用的四种存储方式：,顺序存储：元素逻辑相邻物理存储相邻链接存储：元素逻辑关系指针关系索引存储：建立相的索引表：由索引项组成=关键字+地址。散列存储（哈希存储）：元素的存储地址=散列函数（关键字）,返回,1.1基本术语,数据结构的描述：二元组表示B=（K，R）K=ki|1in,n0R=rj|1jm,m0说明：1、n=0，则K为空集，B无结构。2、m=0，R为空集，K中元素之间不存在任何关系，彼此独立。3、K上的关系r是序偶集合，表示：（x,y）无向；有向。（其中x为y的直接前趋；y为x的直接后继）例子15：书上P.36.。,1.1基本术语,数据类型（DataType）：对数据的取值范围、每一数据的结构以及允许施加的操作的一种描述。数据类型分类：1、简单类型：每个数据都无法再分割。（整型、实型等）2、结构类型：结构类型中的数据可以分解为若干简单类型或结构数据。（数组、记录、结构体、串、文件等）抽象数据类型（AbstractDataType-ADT）:由一组数据结构和在该组数据结构上的一组操作所组成。,1.1基本术语,有关抽象数据类型的说明：1、在定义抽象数据类型中的数据部分和操作部分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。（可通过C+中的类类型来描述）2、描述抽象数据类型的一般格式：ADTisData:Operations:end,1.1基本术语,例：设计一个矩形的抽象数据类型1、抽象数据类型：ADTRECtangleisData:floatlength,width;Operations:RectangleInitRectangle(floatlen,floatwid);floatCircumference(Rectangler);floatArea(Rectangler);endRECtangle2、抽象数据类型的具体实现。P.810.,1.1基本术语,数据对象（DataObject简称对象）：属于一种数据类型（包括一般和抽象数据类型）中的特定量（又称实例），包括常量和变量。算法（Algorithm）：解决问题的方法及步骤。算法的5个特性：1、有穷性。2、确定性。3、可行性。4、输入。5、输出。,1.1基本术语,描述算法的工具：文字叙述、流程图、N-S图、PAD图、伪代码、计算机语言等。算法分类：1、根据解决问题的内容分为：数值算法（数值问题）和非数值算法（非数值问题）。2、根据解决问题的特点分为：递归算法（递归问题）和非递归算法（非递归问题）注：在计算机领域中，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。,1.2算法描述,本书采用文字描述及C+程序对算法进行描述。下面是有关C+语言的简介：1.2.1包含文件语句格式：#include或#include“头文件”常用头文件介绍：1、#include定义了：标准输入设备（键盘）流对象：cin标准输出设备（屏幕）流对象：cout标准错误输出设备（屏幕）流对象：cerr,1.2算法描述,提取操作符（输入）：>>插入操作符（输出）：operator（参数表）引用参数：非正常exit(1)intrand(void):产生032767之间的随整数voidsrand(unsigned):初始化随机数发生器例：P.14.3.#include定义了：,1.2算法描述,输入文件流类：ifstream输出文件流类：ofstream输入输出文件流类：fstream注：当一个文件被打开后，有两种访问方式：按字符方式（又称ASCII码方式）访问：通过文件流对象和>>或<=,*(指针),例：P.25.,1.2算法描述,记录（结构体）struct成员表列；例：P.2627.成员访问：“.”:直接成员选择符“”:间接成员选择符,1.2算法描述,文件：是按位置有序的数据集合。（在计算机中文件被存储在外存上，其存储结构由操作系统自动实现）注：在C+中，用户使用文件是通过定义与之相对应的文件流对象来实现的。字符文件三种方法从文件中读取数据：流类对象>>变量流类对象.get(字符变量)流类对象.getline(字符指针变量，整数量)两种向文件写入数据的方法：流类对象<<数据流类对象.put(字符量),1.2算法描述,字节文件读入或写入文件信息：流类对象.read(字符指针，读出字节数)流类对象.write(字符指针，写入字节数)文件指针的相关函数：流类对象.seekg(pos,origin):在输入或输入、输出文件中指针移动。origin参考位置：ios:beg,ios:cur,ios:endpos:从参考位置移动字节数（+：向后，-：向前）,1.2算法描述,流类对象.seekp(pos,origin):输出文件中指针移动。流类对象.tellg():返回输入文件指针位置。流类对象.tellp():返回输出文件指针位置。例：P.2930.1.2.3函数定义：函数头函数体；引用：函数名（实际参数）,1.2算法描述,参数传递：值传递（单向）地址传递（双向）引用传递（双向）1.2.4运算符重载格式：operator（参数表）p.3537.,1.3算法评价,1.3.1正确性：在合理的数据输入下，能够在有限的运行时间内得出正确的结果。1.3.2健壮性：算法对不合理数据输入的反应和处理能力。1.3.3可读性：符合结构化和模块化程序设计的思想，对每个功能模块、重要数据类型或语句加以注释，建立有相应的文档。1.3.4简单性：采用的数据结构和方法简单，便于用户编写、分析和调试。1.3.5时间复杂度（又称计算复杂度）时间复杂度：算法中包含简单操作次数的多少。表示：f(n)，其中n为解决问题的规模。例：P.3941.,1.3算法评价,1.3.5时间复杂度（又称计算复杂度）算法时间复杂度f(n)相应的数量级：f(n)=O(g(n)即有：算法复杂度的不同数量级变化对照表：P.42.表1-3算法时间复杂度的分类：最好、最差、平均1.3.6空间复杂度空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度,