《Data Structures》 Notes
Bilibili，Mosh 《Data Structures》 Notes 1 1 What is Big O 1 O(1) 2 O(n) 2 O(n^2) 3 O(log n) 4 O(2^n) 4 Space Complexity 5 2 Arrays 6 Understanding Arrays 6 Working in Code 7 Creating the Class 8
第1章 数据结构绪论
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合
1.1 开场白
If you give someone a program, you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime. (如果你交给某人一个程序，你将折磨他一整天; 如果你教某人如何编写程序，你将折磨他一辈子)
1.2 你数据结构怎么学的？
“我在工作中发现，我所需要的如栈、队列、链表、散列表等结构，以及查找、排序等算法，在编程语言的开发工具框中都有完美的实现，我只需要掌握如何使用它们就可以了，为什么还要去弄懂这里面的算法原理呢?”
1.3 数据结构起源
数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。 程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。 程序设计= 数据结构+算法
1.4 基本概念和术语
正所谓“巧妇难为无米之炊”，再强大的计算机，也是要有"米'下锅才可以干活的，否则就是一堆破铜烂铁。这个"米"就是数据。
1.4.1 数据
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型 这里说的数据，其实就是符号，而且这些符号必须具备两个前提: - 可以输入到计算机中。 - 能被计算机程序处理。
1.4.2 数据元素
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
1.4.3 数据项
数据项:一个数据元素可以自若干个数据项组成。 数据项是数据不可分割的最小单位
1.4.4 数据对象
数据对象:是性质相同的数据元素的集合，是数据的子集。
1.4.5 数据结构
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合
1.5 逻辑结构和物理结构
1.5.1 逻辑结构
逻辑结构:是指数据对象中数据元素之间的相互关系。 1.集合结构:集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。 2.线性结构:统性结构中的数据元素之间是一对一的关系 3.树形结构:树形结构中的数据元素之间存在一种一对多的层次关系 4.图形结构:图形结构的数据元素是多对多的关系
1.5.2 物理结构
物理结构：是指数据的逻辑结构在计算机中的存储形式。 数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的，如何 存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。 数据元素的存储结构形式有两种:顺序存储和链式存储。 1.顺序存储结构(排队占位)—>数组 顺序存储结构:是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。 2.链式存储结构:是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的 逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。
1.6 抽象数据类型
1.6.1 数据类型
数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 比如，大家都需要住房子，也都希望房子越大越好。但显然，没有钱，考虑房子是没啥意义的。于是商品房就出现了各种各样的房型，有别墅的，有错层的，有单间的;有一百多平米的，也有几十平米的，甚至在北京还出现了胶囊公寓——只有两平米的房间……这样就满足了不同人的需要。 在C 语言中，按照取值的不同，数据类型可以分为两类： - 原子类型:是不可以再分解的基本类型，包括整型、实型、字符型等。 - 结构类型:自若干个类型组合而戚，是可以再分解的。例如，整型数组是由若干整型数据组成的。 抽象是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。
1.6.2 抽象数据类型
抽象数据类型(Abstract Data Type，ADT ) : 是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 “抽象”的意义在于数据类型的数学抽象特性。 抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题， 然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。
第2章 算法
算法:算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
2.1 开场白
难度有上升
2.2 数据结构与算法关系
梁山伯与祝英台 罗密欧与朱丽叶 现在好多大学里，通常都是把《算法》分出一门课单独讲的，也就是说，在《数据结构》课程中，就算谈到算法，也是为了帮助理解好数据结构，并不会详细谈及算法的方方面面。
2.3 两种算法的比较
1+2+3+……+100 高斯算法 人脑比电脑算得快，似乎成为了现实。
2.4 算法定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 那我就要问问你们，有没有通用的算法呀?这个问题其实很弱智，就像问有没有可以包治百病的药呀! 现实世界中的问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决所有的问题。甚至解决一个小问题，很优秀的算法却不一定适合它。
2.5 算法的特性
算法具有五个基本特性: 输入、输出、有穷性、确定性和可行性。
2.5.1 输入输出
算法具有零个或多个输入 算法至少有一个或多个输出
2.5.2 有穷性
有穷性:指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
2.5.3 确定性
确定性:算法的每一步骤都具有确定的含义，不会出现二义性。
2.5.4 可行性
可行性:算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
2.6 算法设计的要求
2.6.1 正确性
正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 但是算法的"正确"通常在用法上有很大的差别，大体分为以下四个层次。 1. 算法程序没有语法错误。 2. 算法程序对于合法的输入数据能够产生满足要求的输出结果。 3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。 4 . 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
2.6.2 可读性
可读性: 算法设计的另一目的是为了便于阅读、理解和交流。 可读性高有助于人们理解算法，晦涩难愤的算法往往醋、合错误，不易被发现，并且难于调试和修改。 追求的是"最少代码" 这样的极致，使得代码真的不好理解。
2.6.3 健壮性
健壮性:当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
2.6.4 时间效率高和存储量低
设计算法应该尽量满足时间效率高和存储量低的需求
2.7 算法效率的度量方法
2.7.1 事后统计方法
事后统计方法:这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
2.7.2 事前分析估算方法
事前分析估算方法:在计算机程序编制前，依据统计方法对算法进行估算。 经过分析，我们发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素: 1. 算法采用的策略、方法。 2 . 编译产生的代码质量。 3 . 问题的输入规模。 4. 机器执行指令的速度。
2.8 函数的渐近增长
函数的渐近增长:给定两个函数f(n)和g(n)， 如果存在一个整数N，使得对于所有的n > N, f(n)总是比g(n)大，那么， 我们说f(n)的增长渐近快于g(n)。 与最高次项相乘的常数并不重要。最高次项的指数大的，函数随着n 的增长，结果也会变得增长特别快。判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)的阶数。
2.9 算法时间复杂度
2.9.1 定义
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。 一般情况下，随着n 的增大， T(n)增长最慢的算法为最优算法。 显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为O(1)，O(n)，O(n^2)。我们分别给它们取了非官方的名称，O(1)叫常数阶、O(n) 叫线性阶、O(n 2) 叫平方阶，当然，还有其他的一些阶。
2.9.2 推导大O 阶方法
推导大O 阶: 1.用常数1取代运行时间中的所有加法常数。 2 .在修改后的运行次数函数时，只保留最高阶项。 3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。 得到的结果就是大O 阶。
2.9.3 常数阶
这种与问题的大小无关( n 的多少) ，执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。 注意: 不管这个常数是多少，我们都记作O(1)，而不能是O(3)、O(12)等其他任何数字，这是初学者常常犯的错误。 对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着n 的变大而发生变化，所以单纯的分支结构(不包含在循环结构中) ，其时间复杂度也是O(1)。 2.9.4 线性阶 要分析算法的复杂度，关键就是要分析循环结构的运行情况。