本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
dsa:notes:dahua_ds:1_intro [2017/03/23 03:57] – [Comments] 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~~ | ||