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

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

1、数据结构实用教程（C/C++描述）徐孝凯编著第一章绪论§1.1基本术语§1.2算法描述§1.3算法评价§1.1基本术语数据（Data）：是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。（在计算机领域中：能被计算机输入、存储、处理、输出的一切信息）数据元素（DataElement简称元素）：数据整体中相对独立的单位。（各领域中的名称：记录、结点、节点、顶点等）数据记录（DataRecord）：数据处理领域组织数据的基本单位。数据项：记录属性的描述（字段）。关键项（KeyItem）:能唯一标识一个记录的数

2、据项。关键字（KeyWord或Key）：关键项中的每一个值。§1.1基本术语数据处理（DataProcessing）：指对数据进行检索、插入、删除、合并、拆分、排序、统计、简单计算、转换、输入、输出等操作过程。数据结构（DataStructure）：数据及其相互之间的联系。包括三个方面：1、数据的逻辑结构（数据之间的相互联系）2、数据的物理结构（数据结构在存储器中的存储方式）3、数据的运算（在数据结构上施加的各种操作）注：通常所说的数据结构是指数据的逻辑结构。数据结构的分类：1、线性结构。（唯一的开始，唯一的终点，中间任何结点有唯一的直接

3、前趋和唯一的直接后继）2、非线性结构。（树形结构、图形结构、集合）常用的四种存储方式：顺序存储：元素逻辑相邻物理存储相邻链接存储：元素逻辑关系指针关系索引存储：建立相的索引表：由索引项组成=关键字+地址。散列存储（哈希存储）：元素的存储地址=散列函数（关键字）返回§1.1基本术语数据结构的描述：二元组表示B=（K，R）K={ki

4、1≤i≤n,n≥0}R={rj

5、1≤j≤m,m≥0}说明：1、n=0，则K为空集，B无结构。2、m=0，R为空集，K中元素之间不存在任何关系，彼此独立。3、K上的关系r是序偶集合，表示：（x,y）→无向；

6、>→有向。（其中x为y的直接前趋；y为x的直接后继）例子1~5：书上P.3~6.。§1.1基本术语数据类型（DataType）：对数据的取值范围、每一数据的结构以及允许施加的操作的一种描述。数据类型分类：1、简单类型：每个数据都无法再分割。（整型、实型等）2、结构类型：结构类型中的数据可以分解为若干简单类型或结构数据。（数组、记录、结构体、串、文件等）抽象数据类型（AbstractDataType-ADT）:由一组数据结构和在该组数据结构上的一组操作所组成。§1.1基本术语有关抽象数据类型的说明：1、在定义抽象数据类型中的数据部分和操作部

7、分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。（可通过C++中的类类型来描述）2、描述抽象数据类型的一般格式：ADT<抽象数据类型名>isData:<数据描述>Operations:<操作声明>end<抽象数据类型名>§1.1基本术语例：设计一个矩形的抽象数据类型1、抽象数据类型：ADTRECtangleisData:floatlength,width;Operations:RectangleInitRectangle(floatlen,floatwid);floatCircumference(Recta

8、ngler);floatArea(Rectangler);endRECtangle2、抽象数据类型的具体实现。P.8~10.§1.1基本术语数据对象（DataObject简称对象）：属于一种数据类型（包括一般和抽象数据类型）中的特定量（又称实例），包括常量和变量。算法（Algorithm）：解决问题的方法及步骤。算法的5个特性：1、有穷性。2、确定性。3、可行性。4、输入。5、输出。§1.1基本术语描述算法的工具：文字叙述、流程图、N-S图、PAD图、伪代码、计算机语言等。算法分类：1、根据解决问题的内容分为：数值算法（数值问题）和非数值

9、算法（非数值问题）。2、根据解决问题的特点分为：递归算法（递归问题）和非递归算法（非递归问题）注：在计算机领域中，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。§1.2算法描述本书采用文字描述及C++程序对算法进行描述。下面是有关C++语言的简介：1.2.1包含文件语句格式：#include<头文件>或#include“头文件”常用头文件介绍：1、#include定义了：标准输入设备（键盘）流对象：cin标准输出设备（屏幕）流对象：cout标准错误输出设备（屏幕）流对象：c

10、err§1.2算法描述提取操作符（输入）：>>插入操作符（输出）：<<符号常量（换行）：endl空指针常量：NULL例：P.12~13.注意两个知识点：①运算符重载：<类型>operator<