数据结构和算法--基础

数据结构和算法--基础

数据的逻辑结构类型有四种:集合结构、线性结构、树状结构和网络结构。


各类型特点:

1、集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里

2、线性结构:数据元素之间存在着“一对一”的线性关系的数据结构。始节点没有前驱但有一个后继,终端节点没有后继但有一个前驱。其余节点有且只有一个前驱和一个后继。就像a-b-c-d-e-f-g·····被一根线穿连起来,地址可以不连续。

3、树状结构:数据元素之间存在“一对多”的关系。一个或多个节点的有限集合。所有节点都可以至少一个后继。这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....

4、网络结构:数据元素之间存在“多对多”的关系。任何节点都可以有多个前驱和多个后驱。常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

存储结构

存储结构也称为物理结构,指的是数据的逻辑结构在计算机中的存储形式。
数据的存储结构一般可以反映数据元素之间的逻辑关系。
分为顺序存储结构和链式存储结构。

1,顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

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

算法复杂度


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

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

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

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


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

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

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

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

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

4、将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度等于最好时间复杂度。

线性表


数组

数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。

c或java中当创建数组时会在内存中划分出一块连续的内存,然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时,需要提供数组中的索引,然后数组根据索引将内存中的数据取出来,返回给读取程序。

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

段常规的数组定义在 PHP 中并不成立,PHP 的数组可以存储任何类型数据。

链表

链表是线性表

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

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

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

链表种类

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


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

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


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


静态链表:
逻辑结构上相邻的数据元素,存储在指定的一块内存空间中,数据元素只允许在这块内存空间中随机存放,这样的存储结构生成的链表称为静态链表。

静态链表限制了数据元素存放的位置范围;其他没有限制,是整个内存空间。

静态链表使用数组这一数据类型预先申请足够大的内存空间。

由于各数据元素在数组申请的内存空间内随机存放,为了体现逻辑上的相邻,为每一个数据元素配备一个具有指针作用的整形变量,用于记录下一元素在数组中的位置。

在数组申请的存储空间中,各数据元素虽随机存储,每一个元素都记录着下一元素在数组中的位置,通过前一个元素,可以找到下一个元素,构成了一条链表,这条被局限在特定内存空间的链表就是静态链表。

静态链表中每个结点既有自己的数据部分,还需要存储下一个结点的位置,所以静态链表的存储实现使用的是结构体数组,包含两部分: 数据域 和 游标(存放的是下一个结点在数组中的位置下标)。

例如:使用静态链表存储(1,2,3,4,5),创建数组a[7]


链表头指针指向 a[0] ,表示为第一个结点,数据域存放的是 1,通过游标确定,下一个结点的位置在 a[3] ,数据域存放的是 2 ,依次类推。若游标为 0,表示此结点为链表的最后一个结点。

栈又名堆栈,是限定在表尾进行插入和删除的操作的线性表
把允许插入和删除的一端称为栈顶,另一端称为栈底,不包含任何数据元素的栈称为空栈。栈又称为后进先出的线性表,简称LIFO结构。
栈的插入操作,叫做进栈,也称压栈、入栈。
栈的删除操作,叫做出栈,也称弹栈。
栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来。
堆栈中定义了一些操作。
两个最重要的是PUSH和POP。
PUSH操作在堆栈的顶部加入一 个元素。
POP操作相反, 在堆栈顶部移去一个元素, 并将堆栈的大小减一。

堆通常是一个可以被看做一棵树的数组对象。堆和栈(堆栈)没有关系

队列

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

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

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

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

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

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

双端队列

是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。 双端队列可以在队列任意一端入队和出队。


阻塞队列

所谓阻塞队列,是在普通队列基础上实现了阻塞线程的功能:

队列为空时,获取元素的线程阻塞,直到队列变为非空。
当队列满时,存储元素的线程阻塞,直到队列可用(非满

并发队列

多个线程或多个进程共享一个队列。发生等待的问题。

散列表


散列表也称为哈希表,
用一个与集合规模差不多大的数组来存储这个集合,将数据元素的关键字映射到数组的下标,这个映射称为“散列函数”,数组称为“散列表”。查找时,根据被查找的关键字找到存储数据元素的地址,从而获取数据元素。
哈希表是唯一的专用于集合的数据结构。可以以常量的平均时间实现插入、删除和查找。

树形结构


树形数据结构是一类重要的非线性数据结构。
树形数据结构可以表示数据表素之间一对多的关系。
其中以树与二叉树最为常用,直观看来,树是以分支关系定义的层次结构。


图状结构是结构里面最复杂的结构,图状结构存在多对多的关系。

算法基本思想


排序


搜索


查找


字符串匹配