数据结构与算法

数据结构与算法笔记。

数据结构与算法的关系:相互依赖不可分割的.
算法的定义:算法是解决特定问题求解步骤的描述,在计算机中为指令的有限序列,并且每条指令表示一个或多个操作。
算法的特性:有穷性、确定性、可行性、输入、输出。
算法的设计的要求:正确性、可读性、健壮性、高效率和低存储量需求。
算法特性与算法设计容易混,需要对比记忆。
算法的度量方法:事后统计方法(不科学、不准确)、事前分析估算方法。
在讲解如何用事前分析估算方法之前,我们先给出了函数渐近增长的定义。

函数的渐近增长

给定两个函数f(n)和g(n),
如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说fn)的增长渐近快于g(n)。
于是我们可以得出一个结论,判断一个算法好不好,我们只迪过少量的数据是不能做出准确判断的
对比算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的变大,它会越来越优于另一算法,或者越来越差于另一算法。
算法时间复杂度的定义

#推导大O阶的步骤

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中,只保留最高阶项。
如果最高阶项存在且不是1,则去除与这个项相乘的常数。

得到的结果就是大0阶。
在得到算法的运行次数表达式后,很快得到它的时间复杂度,即大0阶。
推导大0阶很容易,但如何得到运行次数的表达式却是需要数学功底的。

常见的时间复杂度所耗时间的大小排列

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2”)<O(n!)<O(n”)
算法最坏情况和平均情况
空间复杂度
弄明白算法的时间复杂度的估算
深究自己写的代码是否效率低下,是不是可以通过优化让计算机更加快速高效。

CPU与算法

现在CPU越来越快,根本不用考虑算法的优劣,实现功能即可,用户感觉不到算法好坏造成的快慢？

假设CPU在短短几年间,速度提高了100倍,这其实已经很夸张了。
而我们的某个算法本可以写出时间复杂度是O(n)的程序,却写出了0(n2)的程序,仅仅因为容易想到,也容易写。
即在O(n2)的时间复杂度算法程序下,速度其实只提高了10(√100=10),而对于0(n)时间复杂度的算法来说,那才是真的100倍。
也就是说,一台老式CPU的计算机运行O(n)的程序和一台速度提高100倍新式CPU运行O(n2)的程序。

最终效率高的胜利方却是老式CPU的计算机,原因就在于算法的优劣直接决定了程序运行的效率。

起源

早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出个解此数据模型的算法,然后再编写程序,得到一个实际的软件。
可现实中,我们更多的不是解决数值计算的问题,而是需要一些更科学有效的手段(比如表、树和图等数据结构)的帮助,才能更好地处理问题。所以数据结构是门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科
1968年,美国的高德纳( Donald E. Knuth)教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统地阐述了数据的逻辑结构和存储结构及其操作,开创了数据结构的课程体系。同年,数据结构作为一门独立的课程,在计算机科学的学位课程中开始出现。也就是说,那之后计算机相关专业的学生开始接受《数据结构》的“折磨”—其实应该是享受才对。
之后,70年代初,出现了大型程序,软件也开始相对独立,结构程序设计成为程序设计方法学的主要内容,人们越来越重视“数据结构”,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。可见,数据结构在程序设计当中占据了重要的地位。

概念

数据

定义

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。

条件

这里说的数据,其实就是符号,而且这些符号必须具备两个前提：可以输入到计算机中。能被计算机程序处理。

处理

对于整型、实型等数值类型,可以进行数值计算。
对于字符数据类型,就需要进行非数值的处理。
而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

数据类型

数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
数据类型是按照值的不同进行划分的。
在高级语言中,每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

类型

数据类型：整型、实型等数值类型,字符（文字数据）及声音、图像、视频等非数值类型。

为什么有不同的数据类型

当年那些设计计算机语言的人,为什么会考虑到数据类型呢?

内存

在计算机中,内存也不是无限大的。
计算整型数字的加减乘除运算,不需要开辟很大的内存空间。
于是计算机的研究者们就考虑,要对数据进行分类,分出来多种数据类型。
比如,在C语言中变量声明inta,b,这就意味着,在给变量a和b赋值时不能超出int的取值范围,变量a和b之间的运算只能是int类型所允许的运算。

底层语言与高级语言

因为不同的计算机有不同的硬件系统,这就要求程序语言最终通过编译器或解释器转换成底层语言,如汇编语言甚至是通过机器语言的数据类型来实现的。
实现1+2进行几次开关操作,这些操作是如何实现的。

抽象

无论什么计算机、什么计算机语言,大都会面临着如整数运算、实数运算、字符运算等操作,我们可以考虑把它们都抽象出来。

抽象与抽象特性
抽象：是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。
    抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标所必需的信息。
    一个抽象数据类型到底需要哪些操作,这就只能由设计者根据实际需要（情况）来定。
抽象数据类型( Abstract Data Type,ADT):是指一个数学模型及定义在该模型上的一组操作。
    一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
    我们对已有的数据类型进行抽象,就有了抽象数据类型。
    抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型。
抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。
    把实际生活中的问题分解为多个规模小且容易处理的问题,
    然后建立一个计算机能处理的数据模型,
    并把每个功能模块的实现细节作为一个独立的单元,
    从而使具体实现过程隐藏起来。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。

数据对象

数据对象:是性质相同的数据元素的集合,是数据的子集。
实际应用中,在不产生混淆的情况下,我们都将数据对象简称为数据。
性质相同
指数据元素具有相同的数据项：数量和类型。
比如,还是刚才的例子,人都有姓名、生日、性别等相同的数据项。

数据元素（记录）

数据元素：是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。
讨论问题时,数据元素才是数据结构中建立数据模型的着眼点。

数据项

数据项:一个数据元素可以由若干个数据项组成。姓名、年龄、性别等数据项,具体有哪些数据项,要视你做的系统来决定。
数据项是数据不可分割的最小单位。
数据项是数据的最小单位。
把数据项定义为最小单位,是有助于更好地解决问题。

数据结构

结构

结构是指各个组成部分相互搭配和排列的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。

数据结构

关系、结构、集合、组织形式。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
在计算机中,数据元素并不是孤立、杂乱无序的,而是具有内在联系的数据集合。
数据元素之间存在的一种或多种特定关系,也就是数据的组织形式。
为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系。

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。

• 集合结构：集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是“平等”的,它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合。
• 线性结构：数据元素之间是一对一的关系。如不转车的地铁站。
• 树形结构：数据元素之间是一对多的关系。
• 图形结构：数据元素之间是多对多的关系。

  物理结构

  物理结构：是指数据的逻辑结构在计算机中的存储形式数据是数据元素的集合。如何把数据元素存储到计算机的存储器中。如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点。
  存储器主要是针对内存而言的,像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
• 顺序存储结构

  顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
  说白了,就是排队占位。大家都按顺序排好,每个人占一小段空间,大家谁也别插谁的队。数组就是这样的顺序存储结构。
  当你告诉计算机,你要建立一个有9个整型数据的数组时,计算机就在内存中找了片空地,按照一个整型所占位置的大小乘以9,开辟一段连续的空间,于是第一个数组数据就放在第一个位置,第二个数据放在第二个,这样依次摆放。

• 链式存储结构

  插队，添加，去掉，整个结构时刻都处于变化中。顺序存储是不科学的。
  链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
  数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
  链式存储就灵活多了,数据存在哪里不重要,只要有一个指针存放了相应的地址就能找到它了。

  示意图

  我们在用示意图表示数据的逻辑结构时,要注意两点：
  节点：将每一个数据元素看做一个结点,用圆圈表示。
  连线：元素之间的逻辑关系用结点之间的连线表示,如果这个关系是有方向的,那么用带箭头的连线表示。

分类

各个计算机,不管是大型机、小型机、PC、平板电脑、PDA,甚至智能手机

数据结构

按照视点的不同,我们把数据结构分为：逻辑结构和物理结构。
逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

逻辑结构

逻辑结构分为：集合结构、线性结构、树形结构、图形结构。
逻辑结构是针对具体问题的,是为了解决某个问题，在对问题理解的基础上,选择一个合适的数据结构表示数据元素之间的逻辑关系。

物理结构（存储结构）

数据元素的存储结构形式有两种:顺序存储和链式存储。

数据类型

在C语言中,按照取值的不同,数据类型可以分为两类。
原子类型:是不可以再分解的基本类型,包括整型、实型、字符型等。
结构类型:由若干个类型组合而成,是可以再分解的。例如,整型数组是由若干整型数据组成的。

同名

物理结构、存储结构

最

最需要关注的问题是逻辑结构。
数据的存储结构应正确反映数据元素之间的逻辑关系,这才是最为关键的。

基本数据类型

基本数据类型一览。
int()、float()、str()
整数
浮点数
字符
字符串
布尔变量
枚举
具名常量
数组
自定义变量

类型转换

int: 浮点型或合适的字符串(只能是整数字符串)
float: 整型或合适的字符串(只能是纯数字字符串)
str:

int('2') #2
int(2.14) #2 
int('2.14') #SyntaxError: invalid character in identifier
int(a) #SyntaxError: invalid character in identifier

float(2) #2.0
float('2.14') #2.14

str(2.14) #'2.14'

数据结构导图

完整性、系统性、针对性
掌握问题的本质
解题：思路、方法、技巧、能力
分析、理解、领会

数据结构、计算机组成原理、操作系统和计算机网络

线性表、栈和队列、树、图
线性表：顺序存储结构、链式存储结构
特殊矩阵的压缩存储
二叉树、线索二叉树、二叉排序树、平衡二叉树、森林
定义和概念、基本操作、存储结构和实现、特殊、遍历方法、构造、应用、复杂度分析
算法：概念、比较、分析和应用
查找算法：顺序查找、折半查找法、B-树、散列表
排序算法：插入排序、气泡排序、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序和基数排序

数据结构之线性表

线性表的定义

线性表的基本操作

线性表两种存储结构各自的特点及比较

线性表的实现：存储结构及应用

顺序存储结构

顺序存储结构的基本操作

链式存储结构

其他常见的链式存储结构

线性表的应用
链式存储结构中指针的操作
链式存储结构中单链表的应用场合
带表头结点的单链表的应用场合
循环链表、的应用场合
双向循环链表的应用场合

一堆节点，及若干边，就构成了图。若根据线路是否有方向性，分为有向图、无向图，根据图中是否有环，分为有环图、无环图。如果任意两个节点都有线路连接，则称为强连通图。
最短路径。要求给出从某地到另外某地的最便捷走法。

• 迪杰斯特拉算法。类似普里姆的「贪婪算法」，从一个极小的「已解决」开始，逐步蚕食，直到将「未解决」吃掉。差别在这回每个节点上都有个数字，代表其到起点的距离，每次都选全部「从已解决到未解决的边」指向的「未解决」节点中，数字最小的一个。比如起点是家，家距离学校500米，家距离市场600米，学校距离公园200米，根据算法，把学校标注500，市场标注600，500小于600，把学校纳入「已解决」，学校进入「已解决」之后，公园也变成了从「已解决」可以到达的「未解决」的节点，用学校的500加200，公园标注为700，与市场的600米相比，600较小，把市场纳入「已解决」。注意，这个步骤，如果是普里姆算法，纳入的是公园而非市场，因为普里姆不存在起点，都连上就ok，只考虑哪条边最短，但迪杰斯特拉有起点，要比较的是「从起点出发直到这里的距离」。
• 贝尔曼福特算法。把每个节点赋予一个表示「距离起点有多远」的数值，除了起点外，其他起点一开始都是无穷大，然后依次考察每条边，如果这条边能让指向的节点的数值变小，就将该节点数值变小或收缩，把所有边都考察一遍之后，如果这一遍中执行了「收缩操作」，则再把所有边都考察一遍，直到某一遍完全没收缩为止。上面的例子，比如考察次序是200-500-600，则第一遍200啥用没有，500将学校的+∞变为500，600将市场的+∞变为600，这遍进行了收缩，再来一遍，这回200有用了，将公园的+∞变为700，500和600都没有，这遍也收缩了，再来一遍，200/500/600都没用，完结。
  如果从每个节点出发，都能到达任意一个节点（强连通），同时图中不存在环，即称为树。树的两个条件，连通和无环。
  分为若干层。父节点，子节点，叶子节点
  二叉树：如果树的每个父节点最多只有两个子节点，该树即称为二叉树。
  二叉排序树。即如果每个根节点数值都比其左子树任意节点数值大，比其右子树的任意节点数值小。最典型用途是二叉查找。在想寻找某个数值时，可以先将该数值与根节点比，如果比根节点大，则去与其右子树根节点比，如果比根节点小，则去与其左子树根节点比，直到找到或比到叶子节点为止。
  红黑树。《算法》中红黑树的章节，从2-3树开始讲，讲到红黑树。
  二叉树和红黑树都有着清晰的用于保持树平衡的逻辑。平衡的目的是保持最差情况下的查找程度为logN：以2为底，总节点数的对数。
  最小生成树。如果树的每条边都有个权值，要求选出总权值最小的一些边，让所有节点都能互相连通，怎么办？这就是「最小生成树」问题。
• 普里姆算法。将图划为「已解决」和「未解决」两个部分，一开始「已解决」为空，「未解决」是全集，首先，任选一个点放到「已解决」，然后考察所有从「已解决」连向「未解决」的边，哪条最短，就把该边连向的「未解决」节点纳入「已解决」集合，如此反复，直到全部节点都「已解决」，结果就是最小生成树。
• 克鲁斯卡尔算法。一开始，把每个节点视为一个「分量」，寻找全部「连接两个不同分量的边」中最短的一条，将其连接的两个分量合并为一个分量，并重复这一行为，直到全部节点都属于同一分量，结果就是最小生成树。
  散列表又叫字典。主要用途是查找，通过键(key)查找值(value)。用于查找的数据结构。
  set，多以map做底层结构。
  要把键算成一个数字，散列函数就是java里类们都要实现的hashcode方法。
  两种实现方式
  链接法。主list装键，比如123，然后1对应一个list，2对应一个list，3对应一个list，把键算出是1之后，就到1对应的list元素里去找元素。显然，1对应的list长度越短，查找时间越短，那似乎主list的键越多越好，比如1到30，那每个子list的长度将变为原长度的十分之一，但主list的键们也不能太多，比如1到30000，那大部分键对应的其实是空，里面一个元素都没有，就浪费空间了，所以要权衡。
  散列法。不存在次list，把键算成数字后，直接往主list对应的位置存，如果该位置已经被别的元素占了(碰撞)怎么办？则用某种算法，算出一个新数，再尝试往新位置放(再散列)，以此类推。显然，这种方法，主list的长度也很关键，如果太短，则碰撞太多，插入、查找都麻烦，如果太长，又浪费地方。
  对两种方法，散列函数都非常重要，如果所有元素的散列函数都计算出同一个值，散列表就毫无意义了。
  FIXME:
  SAME: