数据结构学习笔记 第一章

一、为什么要写博客？

　　前段时间听过一个在学术界卓有成就的学长谈他的学习、科研经验，他讲到“很多学生往往只重视学习或者科研的成果，却忽视了学习的过程······对于学习和科研，我们应该具有归档和整理的能力。”我很赞同他的观点，认为在学习过程中，归档和总结是必不可少的。因为它带给你的不仅仅是知识的重温和复习，还是对知识的结构化、系统化整理。可能将来你很少再去翻看这样一些资料，但是如果你在未来涉及到或者再次用到这些知识时，这样的一份笔记或许可以迅速带你回忆起你看书时的所思所想，将整本书的知识脉络重新呈现在你的头脑之中。

　　在正式决定写博客之前，我也是有尝试过用word文档或是写纸质笔记去学习，但却是无疾而终。因为纸质笔记容易弄丢，而我也不想因为这个去买notebook，但是用word文档又觉得有点麻烦（当然归根结底可能还是我比较懒吧哈哈哈）。同时我个人感觉自己是一个比较注重仪式感的人，在开始学习一个新东西之前总爱给自己整一点什么。所以这次打算正式地用博客来记录我学习的过程，一则因为转了专业学习任务加重，日益繁杂的知识急需系统的归档整理，二则也是利用网络博客去督促自己，激励自己，一旦开始一件事就尽量不要让它中途停下。

二、正文

　　第一章因为是绪论，没有什么难以理解的内容，概念性的知识和辅助理解的文字会多一些。这一章是对数据结构所涉及的若干概念包括算法的解释，以及定义一个数据结构的（伪）代码实现。主要把这一章涉及的几个关键概念以及我的理解在这里列出来。

　　1.1 什么是数据结构

　　这一节用三个例子（三个数据结构）说明了三种计算机领域的问题，并在后文简单介绍了数据结构在计算机领域的发展历史和地位（定位）。

　　主要涉及到的例子有：

　　① 图书馆书目检索   线性数据结构

　　② 计算机和人对弈问题   利用“树”这一结构预测棋局（文中称为“格局”）的发展变化，是非数值计算问题的数学模型

　　③ 多叉路口交通灯的管理问题   利用图的知识来解决五岔路口红绿灯的设计问题（如何设置红绿灯才能使车辆之间相互不碰撞，且达到车辆的最大流通）

　　综合上述三个例子，可以看到数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

　　1.2 基本概念和术语

　　主要介绍了数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型等等的几个概念。

　　数据的含义极为广泛，用数据元素去定义其基本单位，而数据元素（例如，书目）又可以用若干个数据项（作者名、书名等）去表示。数据对象则是性质相同的数据元素的集合，数据结构反映的是不同数据元素之间的关系。数据结构有逻辑结构和存储结构。任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。数据类型用以刻画操作对象的特性（如int型，char型或是自己定义的类型），分为原子类型和结构类型。结构类型是原子类型的复合，而原子类型不可分解。抽象数据类型顾名思义是对数据类型的抽象，它不依托于计算机的内部逻辑实现，例如我们所理解的“整数型”。抽象数据类型也可以分类，分别是原子类型，固定聚合类型和可变聚合类型。抽象数据类型可以利用<数据对象（通常是其他数据类型）、数据关系、基本操作（函数）>这样的三元组表示。

　　1.3 抽象数据类型的表示与实现

　　本小节主要给出的是定义一个抽象数据类型的语法，并给出了一个实例：定义一个三元组（包括初始化、删除、排序、修改等等）。其语法与C++常规语法基本类似，故不详细列出。

　　1.4 算法和算法分析

　　本节讲的是算法的相关特性以及算法效率的度量。

　　其中，算法有五个重要特性：有穷性、确定性、可行性、输入、输出。有四条应该达到的目标：（1）正确性（对于精心选择的典型，苛刻而带有刁难性的几组输入数据都能够有合理性的结果，一般以它作为程序是否合格的衡量）（2）可读性（算法主要是给人看的！）（3）健壮性（当输入的数据非法时，也不会产生离谱的结果）（4）效率与低存储量（实际上就是时空复杂度要尽量小）

　　算法的时间复杂度的比较可以分为两种方法：（1）事后统计 （2）事前分析估算，对于（2），就引出了一个重要的概念——时间复杂度的计算。本书后来又给出了几个计算时间复杂度的实例，因在算法课有详细介绍，故不列出。最后简单介绍了算法的空间复杂度。从篇幅来看，空间复杂度显然不能成为本书论述的重点（但不代表它不重要！）