本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS，因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器，本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI，请尽量通过 HTTPS 访问本站，谢谢！
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
| dsa:notes:dahua_ds:1_intro [2017/03/23 02:51] – [3.1.逻辑结构] haregy | dsa:notes:dahua_ds:1_intro [2021/11/11 08:07] (当前版本) – codinghare | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====数据结构概论==== | + | ======数据结构概论====== |
| 大话数据结构 笔记 第一章\\ | 大话数据结构 笔记 第一章\\ | ||
| <wrap em> | <wrap em> | ||
| - | ===== ===== | + | ---- |
| - | ====1.数据结构的起源==== | + | ====数据结构的起源==== |
| 数据结构是一门研究**非数值运算**的程序设计问题中的**操作对象**，以及**他们之前的关系和操作**等相关对象的学科。这意味着我们用计算机解决问题，首先要解决一些对象之前的关系与操作的问题。数据结构和算法，就是因由这些问题应用到计算机中的。总的说来，我们有一个比较概念化的公式如果下： | 数据结构是一门研究**非数值运算**的程序设计问题中的**操作对象**，以及**他们之前的关系和操作**等相关对象的学科。这意味着我们用计算机解决问题，首先要解决一些对象之前的关系与操作的问题。数据结构和算法，就是因由这些问题应用到计算机中的。总的说来，我们有一个比较概念化的公式如果下： | ||
| \\ | \\ | ||
| 行 11: | 行 11: | ||
| \\ | \\ | ||
| 1968年美国的 //Donald E. Kunth// 教授在其所写的《计算机程序与艺术》第一卷《基本算法》里首次较为系统的阐述了数据的逻辑结构、存储结构和这些数据的相关操作；这被视为数据结构课程的开端。 | 1968年美国的 //Donald E. Kunth// 教授在其所写的《计算机程序与艺术》第一卷《基本算法》里首次较为系统的阐述了数据的逻辑结构、存储结构和这些数据的相关操作；这被视为数据结构课程的开端。 | ||
| - | ====2.基本概念==== | + | ====基本概念==== |
| 数据结构作为研究数据的一门学科，我们先得知道什么数据。 简单的来说：数据可以细致的分为： | 数据结构作为研究数据的一门学科，我们先得知道什么数据。 简单的来说：数据可以细致的分为： | ||
| * 数据：计算机用于描述客观事物的符号，**可以输入计算机，并被计算机操作**。 | * 数据：计算机用于描述客观事物的符号，**可以输入计算机，并被计算机操作**。 | ||
| 行 18: | 行 18: | ||
| * 数据对象：性质相同的数据元素集合，是数据的子集。 | * 数据对象：性质相同的数据元素集合，是数据的子集。 | ||
| * 数据结构：现实世界中，不同元素之间存在特定的关系。我们用数据结构来描述< | * 数据结构：现实世界中，不同元素之间存在特定的关系。我们用数据结构来描述< | ||
| - | ====3.数据结构的分类==== | + | ====数据结构的分类==== |
| 数据结构分为**逻辑结构**和**物理结构**。 | 数据结构分为**逻辑结构**和**物理结构**。 | ||
| - | ===3.1.逻辑结构=== | + | ===逻辑结构=== |
| 逻辑结构表达了数据对象中数据元素之间的相互关系，大致分为四种类型： | 逻辑结构表达了数据对象中数据元素之间的相互关系，大致分为四种类型： | ||
| - 集合结构：集合结构中的数据元素**除了同属一个集合外，没有任何其他的关系**。他们的共同属性是“同属于一个集合”，这个概念源自于数学中集合的概念。 | - 集合结构：集合结构中的数据元素**除了同属一个集合外，没有任何其他的关系**。他们的共同属性是“同属于一个集合”，这个概念源自于数学中集合的概念。 | ||
| 行 31: | 行 31: | ||
| * 元素之间的逻辑关系用节点之间的连线表示，如果是有向的，就用箭头连线表示： | * 元素之间的逻辑关系用节点之间的连线表示，如果是有向的，就用箭头连线表示： | ||
| {{ : | {{ : | ||
| - | ===3.2.物理结构=== | + | ===物理结构=== |
| - | 物理结构（存储结构）表示了**数据的逻辑结构在计算机中的存储方式**。 | + | 物理结构（存储结构）表示了**数据的逻辑结构在计算机中的存储方式**。具体的说，就是怎么存储数据。对于不同的存储器，物理结构也有不同的描述；比如外部存储器，我们一般用文件结构来描述物理结构。 |
| + | \\ | ||
| + | \\ | ||
| + | 存储结构是从现实意义上来反映数据的逻辑结构的。因此，要实现存储结构，我们必须明白怎样将数据的逻辑结构用物理结构的方式表达出来。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 存储结构大致可以分为两种：**顺序存储结构**和**链式存储结构**。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 所谓顺序存储结构，就是把数据元素放到地址连续的内存单元里；数据间逻辑关系和物理关系是一致的。用生活中的描述来说，就是排队站位，挨个来。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 这样的存储结构很好描述；但不方便操作。比如有人如果要插队，队伍中间有人要离开，这些行为都会造成队伍结构的变化。顺序存储的应变性比较低，不足以应付这样的情况。链式存储结构可以更好的解决这一问题。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 而链式存储结构的关键点在于，**逻辑上连续，而物理上并不一定连续**；也就是说，存储结构是不能描述其逻辑结构的。为了保证逻辑上的连续，我们给数据添加指针，用指针来指向下一个逻辑连续的数据元素，就像链子一样，一环一环的来。 | ||
| + | ====抽象数据类型==== | ||
| + | ===数据类型=== | ||
| + | 数据类型分为两部分： | ||
| + | * 拥有相同性质的数据元素的结合 | ||
| + | * 操作这些数据元素的相关操作 | ||
| + | 为什么需要考虑数据类型呢？很显然是为了做好资源分配。比如商品房品种很多，因为每个人的消费水准不同，买的起的房也是不一样的。因此定义不同的商品房才能满足不同消费水平的人的需要。同理，在计算机里，资源也不是无限的；因此每个数据类型都有自己空间占用（取值）范围，对应不同的数据应用不同的数据类型，这样才能达到有效利用计算机资源的目的。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 而为什么需要抽象数据类型呢？因为不同的计算机对应不同的硬件指令，比如在不同的硬件平台上实现 '' | ||
| + | ===4.2.抽象数据类型=== | ||
| + | 抽象数据类型（// | ||
| + | \\ | ||
| + | \\ | ||
| + | 事实上，抽象数据类型体现了程序设计（也可以想象成一般解决问题）几个特性：**分解**，**抽象**，**信息隐藏**： | ||
| + | - 我们用抽象数据类型，把一个大问题分解成许多个小问题 | ||
| + | - 对于每个独立的小问题，建立一个计算机能够处理的功能模块来处理这个问题 | ||
| + | - 因为每个功能模块都是独立的，所以实现了彼此的信息隐藏（封装） | ||
| + | 来看看下面的描述： | ||
| + | < | ||
| + | ADT 抽象数据类型名 | ||
| + | Data | ||
| + | 数据元素之间关系的定义 | ||
| + | Operation | ||
| + | 操作 1 | ||
| + | 初始条件 | ||
| + | 操作结果描述 | ||
| + | 操作 2 | ||
| + | .... | ||
| + | 操作 n | ||
| + | .... | ||
| + | endADT | ||
| + | </ | ||
| + | 这就是我们用于描述抽象数据类型的标准方法。 | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | ---- | ||
| + | |||
| + | ~~DISQUS~~ | ||