---
title: 数据结构与算法
date: 2099-12-12 01:23:47
tags: [计算机,算法]
---
数据结构与算法笔记。
<!-- more -->

数据结构与算法的关系:相互依赖不可分割的.
算法的定义:算法是解决特定问题求解步骤的描述,在计算机中为指令的有限序列,并且每条指令表示一个或多个操作。
算法的特性:有穷性、确定性、可行性、输入、输出。
算法的设计的要求:正确性、可读性、健壮性、高效率和低存储量需求。
算法特性与算法设计容易混,需要对比记忆。
算法的度量方法:事后统计方法(不科学、不准确)、事前分析估算方法。
在讲解如何用事前分析估算方法之前,我们先给出了函数渐近增长的定义。
# 函数的渐近增长
给定两个函数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越来越快,根本不用考虑算法的优劣,实现功能即可,用户感觉不到算法好坏造成的快慢？
<blockquote>假设CPU在短短几年间,速度提高了100倍,这其实已经很夸张了。
而我们的某个算法本可以写出时间复杂度是O(n)的程序,却写出了0(n2)的程序,仅仅因为容易想到,也容易写。
即在O(n2)的时间复杂度算法程序下,速度其实只提高了10(√100=10),而对于0(n)时间复杂度的算法来说,那才是真的100倍。
也就是说,一台老式CPU的计算机运行O(n)的程序和一台速度提高100倍新式CPU运行O(n2)的程序。</blockquote>
最终效率高的胜利方却是老式CPU的计算机,原因就在于算法的优劣直接决定了程序运行的效率。

# 起源
早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出个解此数据模型的算法,然后再编写程序,得到一个实际的软件。
可现实中,我们更多的不是解决数值计算的问题,而是需要一些更科学有效的手段(比如表、树和图等数据结构)的帮助,才能更好地处理问题。所以数据结构是门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科
1968年,美国的高德纳( Donald E. Knuth)教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统地阐述了数据的逻辑结构和存储结构及其操作,开创了数据结构的课程体系。同年,数据结构作为一门独立的课程,在计算机科学的学位课程中开始出现。也就是说,那之后计算机相关专业的学生开始接受《数据结构》的“折磨”—其实应该是享受才对。
之后,70年代初,出现了大型程序,软件也开始相对独立,结构程序设计成为程序设计方法学的主要内容,人们越来越重视“数据结构”,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。可见,数据结构在程序设计当中占据了重要的地位。
# 概念
## 数据
![image.png](https://upload-images.jianshu.io/upload_images/6908911-8dd32c84e607dd12.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![image.png](https://upload-images.jianshu.io/upload_images/6908911-aea8c6a097def30a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
### 定义
数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
### 条件
这里说的数据,其实就是符号,而且这些符号必须具备两个前提：可以输入到计算机中。能被计算机程序处理。
### 处理
对于整型、实型等数值类型,可以进行数值计算。
对于字符数据类型,就需要进行非数值的处理。
而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。
## 数据类型
数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
数据类型是按照值的不同进行划分的。
在高级语言中,每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。
### 类型
数据类型：整型、实型等数值类型,字符（文字数据）及声音、图像、视频等非数值类型。
### 为什么有不同的数据类型
当年那些设计计算机语言的人,为什么会考虑到数据类型呢?
#### 内存
在计算机中,内存也不是无限大的。
计算整型数字的加减乘除运算,不需要开辟很大的内存空间。
于是计算机的研究者们就考虑,要对数据进行分类,分出来多种数据类型。
比如,在C语言中变量声明inta,b,这就意味着,在给变量a和b赋值时不能超出int的取值范围,变量a和b之间的运算只能是int类型所允许的运算。
#### 底层语言与高级语言
因为不同的计算机有不同的硬件系统,这就要求程序语言最终通过编译器或解释器转换成底层语言,如汇编语言甚至是通过机器语言的数据类型来实现的。
实现1+2进行几次开关操作,这些操作是如何实现的。
#### 抽象
无论什么计算机、什么计算机语言,大都会面临着如整数运算、实数运算、字符运算等操作,我们可以考虑把它们都抽象出来。
```
抽象与抽象特性
抽象：是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。
    抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标所必需的信息。
    一个抽象数据类型到底需要哪些操作,这就只能由设计者根据实际需要（情况）来定。
抽象数据类型( Abstract Data Type,ADT):是指一个数学模型及定义在该模型上的一组操作。
    一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
    我们对已有的数据类型进行抽象,就有了抽象数据类型。
    抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型。
抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。
    把实际生活中的问题分解为多个规模小且容易处理的问题,
    然后建立一个计算机能处理的数据模型,
    并把每个功能模块的实现细节作为一个独立的单元,
    从而使具体实现过程隐藏起来。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。
```
![数据抽象标准格式](https://upload-images.jianshu.io/upload_images/6908911-4023d768ccc847ca.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/960)
## 数据对象
数据对象:是性质相同的数据元素的集合,是数据的子集。
实际应用中,在不产生混淆的情况下,我们都将数据对象简称为数据。
性质相同
指数据元素具有相同的数据项：数量和类型。
比如,还是刚才的例子,人都有姓名、生日、性别等相同的数据项。
### 数据元素（记录）
数据元素：是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。
讨论问题时,数据元素才是数据结构中建立数据模型的着眼点。
#### 数据项
数据项:一个数据元素可以由若干个数据项组成。姓名、年龄、性别等数据项,具体有哪些数据项,要视你做的系统来决定。
数据项是数据不可分割的最小单位。
数据项是数据的最小单位。
把数据项定义为最小单位,是有助于更好地解决问题。
## 数据结构
### 结构
结构是指各个组成部分相互搭配和排列的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。
### 数据结构
关系、结构、集合、组织形式。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
在计算机中,数据元素并不是孤立、杂乱无序的,而是具有内在联系的数据集合。
数据元素之间存在的一种或多种特定关系,也就是数据的组织形式。
为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系。
#### 逻辑结构
逻辑结构：是指数据对象中数据元素之间的相互关系。
* 集合结构：集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是“平等”的,它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合。
* 线性结构：数据元素之间是一对一的关系。如不转车的地铁站。
* 树形结构：数据元素之间是一对多的关系。
* 图形结构：数据元素之间是多对多的关系。
#### 物理结构
物理结构：是指数据的逻辑结构在计算机中的存储形式数据是数据元素的集合。如何把数据元素存储到计算机的存储器中。如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点。
存储器主要是针对内存而言的,像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
* 顺序存储结构
>顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。  
说白了,就是排队占位。大家都按顺序排好,每个人占一小段空间,大家谁也别插谁的队。数组就是这样的顺序存储结构。  
当你告诉计算机,你要建立一个有9个整型数据的数组时,计算机就在内存中找了片空地,按照一个整型所占位置的大小乘以9,开辟一段连续的空间,于是第一个数组数据就放在第一个位置,第二个数据放在第二个,这样依次摆放。  
* 链式存储结构
>插队，添加，去掉，整个结构时刻都处于变化中。顺序存储是不科学的。  
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。  
数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
链式存储就灵活多了,数据存在哪里不重要,只要有一个指针存放了相应的地址就能找到它了。
## 示意图
我们在用示意图表示数据的逻辑结构时,要注意两点：
节点：将每一个数据元素看做一个结点,用圆圈表示。
连线：元素之间的逻辑关系用结点之间的连线表示,如果这个关系是有方向的,那么用带箭头的连线表示。

# 分类
各个计算机,不管是大型机、小型机、PC、平板电脑、PDA,甚至智能手机
## 数据结构
按照视点的不同,我们把数据结构分为：逻辑结构和物理结构。
逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。
### 逻辑结构
逻辑结构分为：集合结构、线性结构、树形结构、图形结构。
逻辑结构是针对具体问题的,是为了解决某个问题，在对问题理解的基础上,选择一个合适的数据结构表示数据元素之间的逻辑关系。
### 物理结构（存储结构）
数据元素的存储结构形式有两种:顺序存储和链式存储。
## 数据类型
在C语言中,按照取值的不同,数据类型可以分为两类。
原子类型:是不可以再分解的基本类型,包括整型、实型、字符型等。
结构类型:由若干个类型组合而成,是可以再分解的。例如,整型数组是由若干整型数据组成的。

# 同名
物理结构、存储结构

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

# 基本数据类型

基本数据类型一览。
int()、float()、str()
<!-- more -->[整数](/基本数据类型：整数)
[浮点数](/基本数据类型：浮点数)
[字符](/基本数据类型：字符)
[字符串](/基本数据类型：字符串)
[布尔变量](/基本数据类型：布尔变量)
[枚举](/基本数据类型：枚举)
[具名常量](/基本数据类型：具名常量)
[数组](/基本数据类型：数组)
[自定义变量](/基本数据类型：自定义变量)
# 类型转换

int: 浮点型或合适的字符串(只能是整数字符串)
float: 整型或合适的字符串(只能是纯数字字符串)
str: 
```py
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-树、散列表
排序算法：插入排序、气泡排序、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序和基数排序

# 数据结构之线性表
<!-- more -->
## 线性表的定义
![线性表的定义](https://upload-images.jianshu.io/upload_images/6908911-957dd1bf3b253047.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![线性表的定义](https://upload-images.jianshu.io/upload_images/6908911-b5651d8755dc784b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![线性结构分类](https://upload-images.jianshu.io/upload_images/6908911-a32d5e37c6c288b1.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

## 线性表的基本操作
![线性表的基本操作](https://upload-images.jianshu.io/upload_images/6908911-8732b0dcfa33f8fd.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![线性表的基本操作](https://upload-images.jianshu.io/upload_images/6908911-5cf609d3da3bb9fb.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)


## 线性表两种存储结构各自的特点及比较
![两种存储结构](https://upload-images.jianshu.io/upload_images/6908911-4d945d62429f9cd0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![比较](https://upload-images.jianshu.io/upload_images/6908911-56758df782fec87f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![比较](https://upload-images.jianshu.io/upload_images/6908911-697d8320970c22df.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

![数据结构、线性结构](https://upload-images.jianshu.io/upload_images/6908911-9f2c8facfb0f1f41.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![存储结构比较：效率](https://upload-images.jianshu.io/upload_images/6908911-1e08ecb6e76d2b4e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![存储结构比较：地址连续性](https://upload-images.jianshu.io/upload_images/6908911-4a41ce148eb75fb6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 线性表的实现：存储结构及应用
![存储结构分类](https://upload-images.jianshu.io/upload_images/6908911-22431cb8b3461932.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 顺序存储结构
![顺序表结构示意图](https://upload-images.jianshu.io/upload_images/6908911-ff0261d520374613.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![顺序表结构体](https://upload-images.jianshu.io/upload_images/6908911-7b939d020770a0ab.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 顺序存储结构的基本操作
![创建清空判断更新](https://upload-images.jianshu.io/upload_images/6908911-ceea8b7b425d0c4b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![插入元素](https://upload-images.jianshu.io/upload_images/6908911-e09d194846e7ff4d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![删除元素](https://upload-images.jianshu.io/upload_images/6908911-038cdb3b411571ae.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![删除元素](https://upload-images.jianshu.io/upload_images/6908911-6cbbd209cfd493c5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![插入和删除](https://upload-images.jianshu.io/upload_images/6908911-76b50c91eff4215c.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 链式存储结构
![链式存储结构](https://upload-images.jianshu.io/upload_images/6908911-1c2d238a8c333fe5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![链式存储结构基本操作](https://upload-images.jianshu.io/upload_images/6908911-47c1b9529b3e7703.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![链式存储结构基本操作](https://upload-images.jianshu.io/upload_images/6908911-381c02ed527bc9d6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![链式存储结构基本操作](https://upload-images.jianshu.io/upload_images/6908911-080b3d00bc2cdf75.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 其他常见的链式存储结构
![其他常见的链式存储结构](https://upload-images.jianshu.io/upload_images/6908911-8e998b4aa32070d8.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![其他常见的链式存储结构](https://upload-images.jianshu.io/upload_images/6908911-561212d0e36619f3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
![其他常见的链式存储结构](https://upload-images.jianshu.io/upload_images/6908911-a16f9d12d9b8e5e1.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

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

一堆节点，及若干边，就构成了图。若根据线路是否有方向性，分为有向图、无向图，根据图中是否有环，分为有环图、无环图。如果任意两个节点都有线路连接，则称为强连通图。 
最短路径。要求给出从某地到另外某地的最便捷走法。
* 迪杰斯特拉算法。类似普里姆的「贪婪算法」，从一个极小的「已解决」开始，逐步蚕食，直到将「未解决」吃掉。差别在这回每个节点上都有个数字，代表其到起点的距离，每次都选全部「从已解决到未解决的边」指向的「未解决」节点中，数字最小的一个。比如起点是家，家距离学校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: