数据结构&算法
0x00、 常见数据结构
数组（Array） 栈（Stack） 队列（Queue） 链表（Linked List） 树（Tree） 图（Graph） 堆（Heap） 散列表（Hash）
0.1、 例子 : 学生基本信息表
学号 | 姓名 | 性别 | 籍贯 | 专业 |
001 | 赵一 | 男 | 黑 | 计算机科学 |
002 | 钱二 | 女 | 吉 | 哲学 |
003 | 孙三 | 男 | 辽 | 历史学 |
0x01、 基本概念和术语
数据 / Data ： 客观事物的符号表示，所有能输入到计算机并能被计算机处理的符号的总和。
0.1小节中, 每一个字都是数据。
数据项 / Data Item : 是组成数据元素的、有独立含义的、不可分割的细小单位。
0.1小节中, 确定行的确定列，例如[0,0] 赵一的学号就是一个数据项。
数据元素 / Data Element : 有时候也称为 元素/节点/记录/… ，是数据的基本单位，在计算机中通常作为一个整体考虑和处理。
0.1小节中, 确定的行，例如第一行有关赵一的所有数据项的总和就是一个数据元素。
数据对象 / Data Object : 是性质相同的数据元素的集合。
0.1小节中, 这个表就称为一个数据对象。
0x02、 数据结构及其相关分类
数据结构 ： 是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括逻辑结构和物理结构两个层次。
2.1、 数据结构的逻辑结构
数据结构的逻辑结构的简单划分
线性结构 ： 数据元素之间存在一对一的关系。例如，将学生数据的录入按照事件顺序排列将组成一个线性结构。
集合结构 ： 数据元素之间除了“属于同一集合”的关系外，再无其他关系。例如，确定一名学生是否为班级成员只需要将班级看做一个集合结构。
树结构 ： 元素之间存在一对多的关系。
图结构/网状结构 ： 元素之间存在着多对多的关系。
数据结构的逻辑结构的再次划分
2.2、 数据的存储结构
把数据对象存储到计算机时，通常既要存储个数据元素的数据，又要存储数据元素之间的逻辑关系。
顺序存储结构 ： 在计算机内存中占用一块连续的内存空间进行数据存储
空间利用率低
执行查找和遍历时候的时间效率高
执行插入或删除数据元素的时间效率低
链式存储结构 ： 在计算机内存中占用非连续的内存空间
空间利用率高
执行查找和遍历的时间效率低
执行插入或删除数据元素的时间效率高
0x03、 算法和算法分析
3.1、 算法的定义及特性
算法 / Algorithm ： 是为了解某类问题而规定的一个有限长的操作序列。
算法的特性包括 : 1. 有穷性 : 一个算法总是在执行又穷步后结束，并且每一步必须在有穷的时间内完成。 2. 确定性 : 对于每种情况下所应执行的操作，在算法中都应该有明确的规定，不会产生二义性，是算法的执行者或阅读者都能明确其含义及如何执行。 3. 可行性 : 算法中的操作都可以通过已经实现的基本操作运算执行有限次来实现。 4. 输入 : 一个算法有 ≥0 个输入。 5. 输出 : 一个算法有 ≥1 个输出。
评价算法优劣的标准 : 1. 正确性 : 在合理的数据输入下能在有限的运行时间内得到正确的结果。 2. 可读性 : 一个好的算法首先应该便于人们理解和交流其次才考虑机器可执行性。 3. 健壮性 : 当输入非法数据时，好的算法能做出恰当的反应而不是产生无意义的结果或崩溃。 4. 高效性 : 高效性包括时间和空间两个方面。
时间高效是指算法设计合理执行效率高，可以用 时间复杂度 来度量。
空间高效是指算法占用存储容量空间合理，可以用 空间复杂度 来度量。
其他相关关键字 : 规模 : 算法求解问题的输入量称为问题的规模，一般用 n 表示，问题规模 n 对不同的问题含义不同。最自然的量度是输入中的项数。
3.2、 算法的时间复杂度计算原理
一个算法根据输入规模和输入数据的不同所需要的执行事件往往不同并且有可能有很大。 这时候对我们来说不同的数据可能有不同的意义比如 平均执行时间、最大执行时间、最小执行时间在这其中： 1. 最大执行时间 : 给出了任何输入所造成的运行时间的上界，知道了它我们就能知道这个算法最差也不过如此了，绝不会比这更差。 2. 最小执行时间 : 给出了任何输入所造成的运行时间的下界，知道了他我们能知道这个算法最最好也不过如此了，对于任何给定的输入执行时间都不可能比给此更少。 3. 平均执行时间 : 这个值应该是各种可能值与该值出现概率成绩的和。(当然这其中也包含了最大执行时间和最小执行时间与其出现概率的乘积)
对于上述三者我们： 1. 我们更多的时候关心的是最大执行时间和平均执行时间。 2. 我们也要知道平均执行事件和最大执行时间是有相同增长率的两个与输入规模 n 相关的函数。他们的差别仅仅是系数不同，而这一点在输入规模无限增长的时候是可以忽略的。
例如一个算法的最大执行时间是一个三次函数(knn*n)我们知道无论这种情况出现的概率是多么小最终计算得到的平局执行时间也回事输入规模 n 的三次函数。
最小执行时间我们暂时不考虑。
参考
《数据结构(C语言版)》ISBN 978-7-115-23490
《算法导论》第三版
END
3.*、 关于排序算法的选择
考虑的因素包括 ： 将被排序的项数、这些项已被稍微排序的程度、关于项值的可能限制、计算机的体系结构 以及 将要使用的存储设备(主存、磁盘 或 磁带)。
问题
对于已知的数据结构他们的优势和局限都是什么？
Last updated
