• 数据结构学习——第一章了解数据结构


    数据结构学习——第一章绪论

    1、数据(Data):是能输入计算机且能被计算机处理的各种符号的集合

    • 信息的载体
    • 是对客观事物符号化的标识
    • 能够被计算机识别、存储和加工

    2、数据元素和数据项

    数据元素(Data element):

    • 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理

    • 也简称为元素,或称为记录、结点或顶点

    • 一个数据元素可由若干个数据项组成(Data item)

    数据项:

    • 构成数据元素的不可分割的最小单位

    数据、数据元素、数据项三者之间的关系:数据 > 数据元素 > 数据项

    例:学生表 > 个人记录 > 学号、姓名……

    4、数据对象

    数据对象是性质相同的数据元素的集合,是数据的一个子集

    数据元素与数据对象

    数据元素——组成数据的基本单位

    • 与数据的关系:是集合的个体

    数据对象——性质相同的数据元素的集合

    • 与数据的关系:集合的子集

    数据结构

    • 数据元素不是孤立存在的,他们之间存在着某种关系,数据元素相互之间的关系称为结构
    • 是指相互之间存在一种或多种特定关系的数据元素的集合
    • 或者说,数据结构是带结构的数据元素的集合

    数据结构包含以下三个方面的内容:

    1. 数据元素之间的逻辑关系,也称为逻辑结构
    2. 数据元素及其关系在计算机内存中的表示(又称为映像),称为数据的物理结构或数据的存储结构
    3. 数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

    数据结构的两个层次

    逻辑结构:

    • 描述数据元素之间的逻辑关系
    • 与数据的存储无关,独立于计算机
    • 是从具体问题抽象出来的数学模型

    物理结构(存储结构):

    • 数据元素及其关系在计算机存储器中的结构(存储方式)
    • 是数据结构在计算机中的表示

    逻辑结构与存储结构的关系:

    • 存储结构是逻辑关系的映像和元素本身的映像
    • 逻辑结构是数据结构的抽象,存储结构是数据结构的实现
    • 两者综合起来建立了数据元素之间的结构关系

    逻辑结构的种类

    划分方法一:

    • 线性结构:有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继。
      • 例如:线性表、栈、队列、串
    • 非线性结构:一个结点可能有多个直接前驱和直接后继
      • 例如:树、图

    划分方式二——四类基本逻辑结构

    • 集合结构:结构中的数据元素之间除了同属于一个集合的关系外,无任何其他关系
    • 线性结构:结构中的数据元素之间存在着一对一的线性关系
    • 树形结构:结构中的数据元素之间存在着一对多的层次关系
    • 图状结构或网状结构:结构中的数据元素之间存在着多对多的任意关系

    存储结构的种类

    四种基本的存储结构:

    • 顺序存储结构:用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示
    • 链式存储结构:用一组任意的存储单元存储数据元素,据元素之间的逻辑关系用指针来表示
    • 索引存储结构:在存储结点信息的同时,还建立附加的索引表
    • 散列存储结构:根据结点的关键字直接计算出该结点的存储地址

    数据类型和抽象数据类型

    抽象数据类型:是指一个数学模型以及定义在此数据模型上的一组操作。

    抽象数据类型的形式定义:

    抽象数据对象可用(D,S,P)三元组表示。

    其中,D是数据对象,S是D上的关系集,P是对D的基本操作集

    一个抽象数据类型的定义格式如下:

    ADT 抽象数据类型名{
    	数据对象:<数据对象的定义>
    	数据关系:<数据关系的定义>
    	基本操作:<基本操作的定义>
    }ADT 抽象数据类型名
    
    其中数据对象,数据关系的定义用伪代码描述,基本操作的定义格式为:
    基本操作名(参数表)
    初始条件:<初始条件描述>
    操作结果:<操作结果描述>
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    基本操作定义格式说明:

    参数表:赋值参数职位操作提供输入值。引用参数用&打头,除可提供输入值外。还将返回操作结果。

    初始条件:描述操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。若初始条件为空,则省略之。

    操作结果:说明操作正常完成之后,数据结构的变化状况和应返回的结果

    抽象数据类型(ADT)定义举例:Circle的定义

    ADT Circle{
    	数据对象:D = {r, x, y | r, x, y均为实数}
    	数据关系:R = {<r, x, y>| r是半径,<x, y>是圆心坐标}
    	基本操作:
    	Circle(&C,r, x, y)
    		操作结果:构造一个圆
    	double Area(C)
    		初始条件:圆已存在
    		操作结果:计算面积
    	double Circumference(C)
    		初始条件:圆已存在
    		操作结果:计算周长
    	……
    }ADT Circle
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    算法和算法分析

    算法的定义

    对特定问题求解方法和步骤的一种描述,它是指令的有限序列,其中每个指令标识一个或多个操作

    算法的特性:

    • 有穷性 一个算法必须总是在执行有穷步之后结束,且每一步在有穷时间内完成
    • 确定性:算法的每一条指令必须有确切的含义,没有二义性,在任何条件下,只有唯一的执行路径,即对于相同的输入只能得到相同的输出
    • 可行性
    • 输入
    • 输出
  • 相关阅读:
    【Java】Object 类
    物联网入门系列(一):快速搭建一站式数据存储与实时分析平台
    睡眠质量记录64
    Symfony DBAL 教程
    【AcWing】AcWing 5180. 正方形泳池(秋季每日一题2023)(排序 + 边枚举边更新)
    weapp源码反编译步骤
    数据库范式
    [云原生 | k8s ]k8s中Pod、ReplicaSet、Deployment、Service的区别
    Google Earth Engine(GEE)——用geometry点来改变选的影像范围,并进行加载的APP
    【TypeScript】深入学习TypeScript命名空间
  • 原文地址:https://blog.csdn.net/qiangqiang103/article/details/121105457