数据结构和算法--基础

数据结构和算法--基础

数据的逻辑结构(4种)
集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里(例如数组)。

线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来,地址可以不连续。

树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。
1)顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

2)非顺序存储结构(链式存储):是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

算法

数据结构和算法的关系:

两者基友联系又有区别。联系是程序=算法+数据结构。
数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。
区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想,数据结构则是这些思想的基础。

算法的五大特性:

有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

输入,是指算法具有零个或多个输入。

输出,是指算法至少有一个或多个输出。

复杂度

算法复杂度包括时间复杂度和空间复杂度,两者中又以时间复杂度相对重要,我们常见的性能优化策略都是以空间换时间。

算法的时间复杂度就是算法的时间度量,记作T(n) = O(f(n))

称作大 O记法,我们在分析时间复杂度的时候往往遵循以下原则:1、只关注循环执行次数最多的一段代码;2、加法法则:总复杂度等于量级最大的那段代码的复杂度;3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
时间复杂度

常见的时间复杂度按数量级递增排列依次为

undefined

因此,如果分析某个算法的时间复杂度是 T(n) = O(2n+2)
/ T(n) = O(2n^2 +2n+3),则公式中的低阶、常量、系数三部分都可以忽略,即:T(n) = O(n) / T(n) = O(n^2)

时间复杂度里细分起来又有最好、最坏、平均情况时间复杂度之分

1、最好情况时间复杂度就是在最理想的情况下,执行这段代码的时间复杂度;

2、最坏情况时间复杂度就是在最糟糕的情况下,执行这段代码的时间复杂度;

3、平均情况时间复杂度顾名思义就是结合概率论分析从最好到最坏每种情况平均下来的加权平均时间复杂度

一般而言,我们关注复杂度就够了,只有特别严苛条件下或者复杂度相同的情况下,我们才会进一步区分最好、最坏、平均复杂度

数据结构(数组)

数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。
c或java中当创建数组时会在内存中划分出一块连续的内存,然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时,需要提供数组中的索引,然后数组根据索引将内存中的数据取出来,返回给读取程序。

数组的优点是可以通过下标值随机访问数组内的任何元素,算法复杂度是 O(1),非常高效,但是缺点是删除/插入元素比较费劲,以删除为例,需要在删除某个元素后,将后续元素都往前移一位,如果是插入,则需要将插入位置之后的元素都往后移,所以对数组的插入/删除而言,算法复杂度是 O(n).
段常规的数组定义在 PHP 中并不成立,PHP 的数组可以存储任何类型数据.

链表

链表是线性表

链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。

链表是属于非顺序存储结构的数据.因为链表中的数据并不是连续的,所以创建链表的过程中不用事先划出一块连续的内存.

链表在存储数据的内存中有两块区域,一块区域用来存储数据,一块区域用来记录下一个数据保存在哪里(指向下一个数据的指针)。当有数据进入链表时候,会根据指针找到下一个存储数据的位置,然后把数据保存起来,然后再指向下一个存储数据的位置。

链表种类

单链表:
单链表中有两个节点比较特殊,分别是第一个结点和最后一个结点。
我们通常把第一个结点叫作头结点,把最后一个结点叫作尾结点。
其中,头结点用来记录链表的基地址,有了它,我们就可以遍历得到整条链表。
而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。
对单链表而言,理论上来说,插入和删除节点的时间复杂度是 O(1),查询节点的时间复杂度是 O(n)

单向循环链表:
循环链表和单链表的区别是尾节点指向了头结点,从而首尾相连,有点像贪吃蛇,可用于解决「约瑟夫环」问题

双向链表:
顾名思义,与单链表的区别是双向链表除了有一个指向下一个节点的指针外,还有一个用于指向上一个节点的指针,从而实现通过 O(1) 复杂度找到上一个节点。
正是因为这个节点,使得双向链表在插入、删除节点时比单链表更高效,虽然我们前面已经提到单链表插入、删除时间复杂度已经是 O(1) 了,但是这没有考虑还只是针对插入、删除操作本身而言,以删除为例,删除某个节点后,需要将其前驱节点的指针指向被删除节点的下一个节点.
这样,我们还需要获取其前驱节点,在单链表中获取前驱节点的时间复杂度是 O(n),所以综合来看单链表的删除、插入操作时间复杂度也是 O(n),而双向链表则不然,它有一个指针指向上一个节点,所以其插入和删除时间复杂度才是真正的 O(1).

双向循环链表:
就是将双向链表的首尾通过指针连接起来.

(堆栈),队列,堆

栈又叫堆栈(Stack):先进后出(后进先出),往桶里面放放东西.
"队列":先进先出.
“堆”:是指二叉树.

(堆栈)

栈(stack)又名堆栈,它是一种运算受限的线性表。

其限制是仅允许在表的一端进行插入和删除运算。

这一端被称为栈顶,相对地,把另一端称为栈底。

栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来(先进后出),这个特性通常称为后进先出(LIFO)队列。

(Stack)是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域,该区域具有FIFO的特性,在编译的时候可以指定需要的Stack的大小。

(堆栈的特性):

最后一个放入堆栈中的物体总是被最先拿出来, 这个特性通常称为后进先出(LIFO)队列。
堆栈中定义了一些操作。
两个最重要的是PUSH和POP。
PUSH操作在堆栈的顶部加入一 个元素。
POP操作相反, 在堆栈顶部移去一个元素, 并将堆栈的大小减一。

队列

1.队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

2.队列中没有元素时,称为空队列。

3.建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置。

4.队列采用的FIFO(first in first out),新元素(等待进入队列的元素)总是被插入到链表的尾部,而读取的时候总是从链表的头部开始读取。每次读取一个元素,释放一个元素。所谓的动态创建,动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成,遍历也方便。(先进先出)

5.队列也可以通过数组和链表实现,通过数组实现的叫顺序队列,通过链表实现的叫做链式队列

6. 通过数组实现的顺序队列有一个问题,就是随着队列元素的插入和删除,队尾指针和队头指针不断后移,而导致队尾指针指向末尾无法插入数据,这时候有可能队列头部还是有剩余空间的.
我们当然可以通过数据搬移的方式把所有队列数据往前移,但这会增加额外的时间复杂度,如果频繁操作数据量很大的队列,显然对性能有严重损耗,对此问题的解决方案是循环队列,即把队列头尾连起来.通过链表来实现队列的话,显然没有这类问题,因为链表没有空间限制。

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质

1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。
3.将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
4.堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。
5.堆是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。
6.堆是指程序运行时申请的动态内存,而栈只是指一种使用堆的方法(即先进后出)

数组

数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数组元素,按照数据元素的类型,数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。  

是典型的非线性结构,它是包括,2个结点的有穷集合K。在树结构中,有且仅有一个根结点,该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点,而且可以有聊个后继结点,m≥0。  

是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。  

散列表(Hash)

散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。