summary
type
status
date
slug
tags
category
文件和媒体
文本
icon
password
程序=数据结构+算法
线性代数
概率论
离散数学（集合论与图论）
绪论
操作对象之间的关系：非线性关系、树
典型的树形结构问题：文件系统的系统结构图
磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及
文件，但每个子目录只有一个父目录，依此类推
数据与数据成一对多的关系，是一种典型的非线性关系结构——树形结构
例子2：地图导航——求最短路径（最快路径）网状结构（图）
综上所述，这些问题的共性是都无法用数学的公式或方程来描述，是一些“非数值计算”的程序设计问题
描述非数值计算问题的数学模型不是数学方程，而是诸如表、树和图之类的具有逻辑关系的数据
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系的操作的学科
基本概念和术语1
数据
数据元素
数据项
数据对象
逻辑结构：
描述数据元素之间的逻辑关系
与数据的存储无关，独立于计算机
是从具体问题抽象出来的的数学模型
物理结构（存储结构）：
数据元素及其关系在计算机存储器中的结构（存储方式）
逻辑结构与存储结构的关系：
存储结构是逻辑关系的映像与元素本身的映像
逻辑结构是数据结构的抽象，存储结构是数据结构的实现
两者综合起来建立了数据元素之间的结构关系
逻辑结构的种类
线性结构：
有且仅有一个开始和一个终端结点，并且所有结点都是最多只有一个人直接前趋和一个直接后继
例如：线性表、栈、队列、串
非线性结构：
一个结点可能有多个直接前趋和直接后继
例如：树、图
四类基本逻辑结构
集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系
线性结构：结构中的数据元素之间存在着一对一的线性关系
树形结构：结构中的数据元素之间存在着一对多的层次关系
图形结构或网状结构：结构中的数据元素之间存在着多对多的任意关系
四类基本的存储结构：
顺序存储结构：
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
C语言中用数组来实现顺序存储结构
链式存储结构：
用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
C语言中用指针来实现链式存储结构
索引存储结构：
在存储结点信息的同时，还建立附加的索引表
索引表中的每一项称为一个索引项
索引项的一般形式是：（关键字，地址）
关键字是唯一标识一个结点的那些数据项
若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应体格索引项，则该索引表称之为稀疏索引
散列存储结构：
根据结点的关键字直接计算出该结点的存储地址
基本概念和术语2
一些最基本数据结构可以用数据类型来实现，如数组、字符串等
而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示
数据类型的作用：约束变量或常量的取值范围or约束变量或常量的操作
数据类型定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称
数据类型=值的集合+值集合上的一组操作
抽象数据类型：
是指一个数学模型以及定义在此数学模型上的一组操作
由用户定义，从问题抽象出数据类型（逻辑结构）
还包括定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内的具体存储结构与运算的具体实现算法
抽象数据类型的形式定义：
抽象数据类型可用（D，S，P）三元组表示
其中：D是数据对象
S是D上的关系集
P是对D的基本操作集
一个抽象数据类型的定义格式如下：
其中：
数据对象、数据关系的定义用伪代码描述
基本操作的定义格式为：
基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>
基本操作定义格式说明：
参数表：赋值参数，只为操作提供输入值
引用参数以&打头，除可提供输入值外，还将返回操作结果
初始条件条件：描述操作执行之前数据结构和参数应曼珠的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之
操作结构：说明操作整除完成之后u，数据结构的变化状况和应返回的结果
抽象数据类类型定义举例：
Circle的定义
复数的定义
抽象数据类型的表示与实现
一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要实现这个目标，就要把抽象的变为具体的，即抽象数据类型在计算机上实现，变为一个能用的具体的数据类型
抽象数据类型可以通过固有的数据类型（如整形、实性、字符型等）
即iyon处理器中已存在的数据类型来说明新的结构，用以及实现的操作来组合新的操作
算法与算法分析1
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序是用某种程序设计语言对算法的具体实现
程序=数据结构+算法
数据结构通过算法实现操作
算法根据数据结构设计程序
- Author:Anten
- URL:https://www.anten.ysepan.com/article/example-7
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
