数据结构——Chapter1基础概念

数据结构——Chapter1基础概念

• 数据结构
• • 数据的基本概念
  • 关系
  • • 逻辑结构
    • 存储结构
  • 抽象数据类型
  • 算法
  • • 算法时间效率的度量
• 小结

\quad 现在，计算机主要用于非数值计算，包括处理字符、表格和图像等具有一定结构的数据。这些数据内容存在着某种联系，只有分清楚数据的内在联系，合理地组织数据，才能对它们进行有效的处理，设计出高效的算法。如何合理地组织数据、高效地处理数据，这就是 “数据结构” 主要研究的问题。
\quad 数据结构 (Data Structure) 是相互之间存在一种或多种特定关系的数据元素的集合。换句话
说，数据结构是带 ”结构＂ 的数据元素的集合， “结构” 就是指数据元素之间存在的关系。
数据结构包括逻辑结构和存储结构两个层次。

数据结构

数据的基本概念

数据（Data）：能输入计算机且能被计算机处理的各种符号的集合。分数值型和非数值型
数据元素（Data element）:数据的基本单位，是整体性概念，也可称结点、记录、顶点。
数据项：构成数据元素不可分割的最小单位
数据>数据元素>数据项
数据对象：性质相同的数据元素的集合，是数据的子集
数据元素不是孤立的，它们之间存在某种关系，数据元素相互之间的关系称为结构
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
数据结构包括三方面的内容：

1. 逻辑结构：数据元素间的逻辑关系
2. 存储结构（物理结构）：数据元素及其逻辑关系在计算机内存中的表示（映像）
3. 数据元素的运算和实现：对数据元素的操作和这些操作在相应的存储结构上的实现

关系

逻辑结构

划分方法一
1.线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和直接后继（线性表，栈，队列，串）
2.非线性结构：一个结点可以有多个前驱和后继（树，图，集合）

划分方法二
1 .集合结构
2. 线性结构：数据元素间存在一对一的线性关系
3. 树形结构：数据元素间存在一对多的层次关系
4. 图形结构：数据元素间存在多对多的任意关系

存储结构

四种基本存储结构
1.顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助
程序设计语言的数组类型来描述。
2.链式存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用千存放后继
元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
3.索引存储结构
4.散列存储结构

数据类型（Data Type):一组性质相同的值的集合以及定义在这个集合上的一组操作的总称。
作用：约束变量或常量的取值范围和操作

抽象数据类型

（ADT）：一个数学模型（逻辑结构）及定义在此模型上的一组操作（运算），而不考虑具体的数据存储表示和操作实现。
形式定义
（D,R,P）三元组表示：D——数据对象，R——关系集，P——基本操作集
基本格式： //定义用伪代码描述
ADT 抽象数据类型名{
数据对象：<数据对象的定义> (用伪代码描述）
//数据元素 间的关系集合
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类项名

算法

定义： 解决问题的方法步骤（解决某类问题而规定的一个有限长的操作序列）
算法的描述方法：1.自然语言 2.流程图3.伪代码 4.程序代码

算法的特性

要求


鲁棒性：

算法时间效率的度量

算法时间效率可以用依据该算法所编制的程序在计算机上执行所消耗的时间来度量。
两种度量方法：
事后统计：将算法实现，测量其时间和空间开销
事前分析：对算法所消耗资源的一种估计方法 。

算法中基本语句重复执行的次数是问题规模$n$的某个函数$f(n)$，算法的时间度量记作：$T(n)=O(f(n))$
一般考虑最坏的时间复杂度

小结

参考资料 ：
数据结构（C语言版）严蔚敏
青岛大学，王卓 教学视频

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！