本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS，因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器，本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI，请尽量通过 HTTPS 访问本站，谢谢！
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
| dsa:notes:dahua_ds:1_intro [2017/03/23 03:56] – [4.2.抽象数据类型] 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.物理结构=== | + | ===物理结构=== |
| 物理结构（存储结构）表示了**数据的逻辑结构在计算机中的存储方式**。具体的说，就是怎么存储数据。对于不同的存储器，物理结构也有不同的描述；比如外部存储器，我们一般用文件结构来描述物理结构。 | 物理结构（存储结构）表示了**数据的逻辑结构在计算机中的存储方式**。具体的说，就是怎么存储数据。对于不同的存储器，物理结构也有不同的描述；比如外部存储器，我们一般用文件结构来描述物理结构。 | ||
| \\ | \\ | ||
| 行 39: | 行 39: | ||
| \\ | \\ | ||
| 存储结构大致可以分为两种：**顺序存储结构**和**链式存储结构**。 | 存储结构大致可以分为两种：**顺序存储结构**和**链式存储结构**。 | ||
| + | \\ | ||
| \\ | \\ | ||
| 所谓顺序存储结构，就是把数据元素放到地址连续的内存单元里；数据间逻辑关系和物理关系是一致的。用生活中的描述来说，就是排队站位，挨个来。 | 所谓顺序存储结构，就是把数据元素放到地址连续的内存单元里；数据间逻辑关系和物理关系是一致的。用生活中的描述来说，就是排队站位，挨个来。 | ||
| + | \\ | ||
| \\ | \\ | ||
| 这样的存储结构很好描述；但不方便操作。比如有人如果要插队，队伍中间有人要离开，这些行为都会造成队伍结构的变化。顺序存储的应变性比较低，不足以应付这样的情况。链式存储结构可以更好的解决这一问题。 | 这样的存储结构很好描述；但不方便操作。比如有人如果要插队，队伍中间有人要离开，这些行为都会造成队伍结构的变化。顺序存储的应变性比较低，不足以应付这样的情况。链式存储结构可以更好的解决这一问题。 | ||
| + | \\ | ||
| \\ | \\ | ||
| 而链式存储结构的关键点在于，**逻辑上连续，而物理上并不一定连续**；也就是说，存储结构是不能描述其逻辑结构的。为了保证逻辑上的连续，我们给数据添加指针，用指针来指向下一个逻辑连续的数据元素，就像链子一样，一环一环的来。 | 而链式存储结构的关键点在于，**逻辑上连续，而物理上并不一定连续**；也就是说，存储结构是不能描述其逻辑结构的。为了保证逻辑上的连续，我们给数据添加指针，用指针来指向下一个逻辑连续的数据元素，就像链子一样，一环一环的来。 | ||
| - | ====4.抽象数据类型==== | + | ====抽象数据类型==== |
| - | ===4.1.数据类型=== | + | ===数据类型=== |
| 数据类型分为两部分： | 数据类型分为两部分： | ||
| * 拥有相同性质的数据元素的结合 | * 拥有相同性质的数据元素的结合 | ||
| 行 62: | 行 65: | ||
| - 对于每个独立的小问题，建立一个计算机能够处理的功能模块来处理这个问题 | - 对于每个独立的小问题，建立一个计算机能够处理的功能模块来处理这个问题 | ||
| - 因为每个功能模块都是独立的，所以实现了彼此的信息隐藏（封装） | - 因为每个功能模块都是独立的，所以实现了彼此的信息隐藏（封装） | ||
| - | 我们用这样的格式来描述抽象数据类型： | + | 来看看下面的描述： |
| < | < | ||
| ADT 抽象数据类型名 | ADT 抽象数据类型名 | ||
| 行 77: | 行 80: | ||
| endADT | endADT | ||
| </ | </ | ||
| - | ===Comments=== | + | 这就是我们用于描述抽象数据类型的标准方法。 |
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | ---- | ||
| ~~DISQUS~~ | ~~DISQUS~~ | ||