本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
这是本文档旧的修订版!
大话数据结构 笔记 第一章
我的笔记均包含大量个人理解内容,存在一定偏差。如果您发现错误,请留言提出,谢谢!
数据结构是一门研究非数值运算的程序设计问题中的操作对象,以及他们之前的关系和操作等相关对象的学科。这意味着我们用计算机解决问题,首先要解决一些对象之前的关系与操作的问题。数据结构和算法,就是因由这些问题应用到计算机中的。总的说来,我们有一个比较概念化的公式如果下:
$$程序结构 = 数据 + 算法$$
1968年美国的 Donald E. Kunth 教授在其所写的《计算机程序与艺术》第一卷《基本算法》里首次较为系统的阐述了数据的逻辑结构、存储结构和这些数据的相关操作;这被视为数据结构课程的开端。
数据结构作为研究数据的一门学科,我们先得知道什么数据。 简单的来说:数据可以细致的分为:
数据结构分为逻辑结构和物理结构。
逻辑结构表达了数据对象中数据元素之间的相互关系,大致分为四种类型:
我们可以形象的用示意图来表示数据的逻辑结构:
物理结构(存储结构)表示了数据的逻辑结构在计算机中的存储方式。具体的说,就是怎么存储数据。对于不同的存储器,物理结构也有不同的描述;比如外部存储器,我们一般用文件结构来描述物理结构。
存储结构是从现实意义上来反映数据的逻辑结构的。因此,要实现存储结构,我们必须明白怎样将数据的逻辑结构用物理结构的方式表达出来。
存储结构大致可以分为两种:顺序存储结构和链式存储结构。
所谓顺序存储结构,就是把数据元素放到地址连续的内存单元里;数据间逻辑关系和物理关系是一致的。用生活中的描述来说,就是排队站位,挨个来。
这样的存储结构很好描述;但不方便操作。比如有人如果要插队,队伍中间有人要离开,这些行为都会造成队伍结构的变化。顺序存储的应变性比较低,不足以应付这样的情况。链式存储结构可以更好的解决这一问题。
而链式存储结构的关键点在于,逻辑上连续,而物理上并不一定连续;也就是说,存储结构是不能描述其逻辑结构的。为了保证逻辑上的连续,我们给数据添加指针,用指针来指向下一个逻辑连续的数据元素,就像链子一样,一环一环的来。
数据类型分为两部分:
为什么需要考虑数据类型呢?很显然是为了做好资源分配。比如商品房品种很多,因为每个人的消费水准不同,买的起的房也是不一样的。因此定义不同的商品房才能满足不同消费水平的人的需要。同理,在计算机里,资源也不是无限的;因此每个数据类型都有自己空间占用(取值)范围,对应不同的数据应用不同的数据类型,这样才能达到有效利用计算机资源的目的。
而为什么需要抽象数据类型呢?因为不同的计算机对应不同的硬件指令,比如在不同的硬件平台上实现 1 + 1
的命令都不一样。现实生活中我们要计算 1 + 1
不会去考虑什么平台用什么的。这就是抽象:抽取事物具有的普遍性。同理,如果我们要研究数据,必须要摆脱平台的困扰,把数据抽象为一系列的普遍操作;而数学则是抽象数据的最有效的工具。
抽象数据类型(Abstract Data Type, ADT),其本质就是一个数学模型(集合),和一系列应用到这个数学模型上的操作。因为类型是抽象的,所以我们只探讨抽象数据类型的逻辑性,而不会去讨论它在计算机内部如何实现。
事实上,抽象数据类型体现了程序设计(也可以想象成一般解决问题)几个特性:分解,抽象,信息隐藏:
来看看下面的描述:
ADT 抽象数据类型名
Data
数据元素之间关系的定义
Operation
操作 1
初始条件
操作结果描述
操作 2
....
操作 n
....
endADT
这就是我们用于描述抽象数据类型的标准方法。
~~DISQUS~~