2099-12-12

数据结构与算法

数据结构与算法笔记。

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

函数的渐近增长

给定两个函数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,开辟一段连续的空间,于是第一个数组数据就放在第一个位置,第二个数据放在第二个,这样依次摆放。
链式存储结构

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

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

同名

物理结构、存储结构

最

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

基本数据类型

基本数据类型一览。
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-树、散列表
排序算法：插入排序、气泡排序、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序和基数排序