caroline's world - 数据结构与算法
type: channel
link: https://blog.carolineworld.cn/index.php/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/
items: 数据结构与算法

数据结构与算法
type: item
date: 2024-01-13T12:00:00+08:00
description: 数据结构与算法课程笔记1 绪论1.1 基本概念和术语1.1.1 数据数据(data)：对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素（data element）：数据的基本单位。在计算机中通常作为一个整体进行考虑喝处理。数据项（data item）：是组成数据元素、有独立含义的、不可分割的最小单位。数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集。1.1.2 数据结构数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合。结构（structure）：数据元素相互之间的关系。逻辑结构数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构 可以看作是 从具体问题抽象出来的数学模型。四类基本结构：集合 set：数据元素之间就是“属于同一个集合”线性结构 list：数据元素之间存在着一对一的线性关系树形结构 tree：数据元素之间存在者一对多的层次关系图状结构 或 网状结构 graph：数据元素之间存在着多对多的任意关系存储结构存储结构：数据结构在计算机中的表示（又称映像），数据的物理结构。包括数据元素的表示和关系的表示。在计算机中，表示信息的最小单位是二进制数的一位，叫做 位（bit）。计算机中，用一个由若干位组合起来形成的一个位串表示一个数据元素。通常称这个位串为元素（element）或结点（node）。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域（data field）。元素 或 结点 可以看成是数据元素在计算机中的映像。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像 和 非顺序映像，并由此得到两种不同的存储结构：顺序存储结构 和 链式存储结构。（其实还有两种存储方式：索引存储（索引项：关键词、地址）、散列存储（结点地址 = F(关键字) ））顺序映像 的特点是：借助元素在存储器中的相对关系来表示数据元素之间的逻辑关系非顺序映像 的特点是：借助指示元素存储地址的 指针（pointer）来表示 数据元素之间的逻辑关系数据存储原则：不仅要存储数据本身的值，还要保存数据间的关系。存储数据的目的是为了对它们进行处理。数据的 逻辑结构 属于用户视图，是面向问题的，反映了数据内部的构成方式，数据的逻辑结构独立于计算机数据的 物理存储结构 的实现要用计算机语言中的 数据类型 来描述，因而是依赖于具体的计算机语言而言的，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据存储的效率往往是不同的1.1.3 数据的运算数据的运算有两方面的含义：运算的定义与算法的实现运算的定义：取决于数据的逻辑结构。根据问题中的数据及数据间的关系，设计相应的数据处理方法。常见的运算操作：初始化：对存储结构设置初始值，或者申请存储空间。判空：判断存储空间是否为未存放有效值的状态查找：判断是否包含指定元素遍历：按某种次序访问所有元素，每个元素只被访问一次插入：增加指定元素删除：移去指定元素……1.1.3 数据类型和抽象数据类型数据类型数据类型（data type）是 一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型抽象数据类型（Abstract Data Type，简称 ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型，不仅包括各处理器已经定义及实现的数据类型，还包括用户自己定义的数据类型。抽象数据类型具体包括三部分：数据对象、数据对象上关系的集合以及对抽象对象的基本操作抽象数据类型的定义格式：ADT 抽象数据类型名{ 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> }ADT 抽象数据类型名基本操作的定义格式：基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述>1.2 算法和算法分析1.2.1 算法算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的 5 个重要特性：有穷性：一个算法总是在执行有穷步之后结束，且每一步都可在 有穷时间 内完成。确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。而且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。可行性：算法中所描述的操作都是可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有零个或多个输入，这些输入来自某个特定的对象的集合输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量1.2.…