数据结构和算法-线性表

简介

线性表:数据与数据之间只存在简单的前后关系的数据结构,例如数组、链表、栈、队列;

非线性表:数据与数据之间存在多种关系,例如图、堆、二叉树。

数组

数组:一组内存连续的数据结构,用于存储一组同一类型的数据

数组的访问速度快,因为使用了下标(偏移量),所以访问效率高,能够进行随机(任意)访问。

访问原理为:数组首地址+偏移量*数据大小;

时间复杂度:使用随机访问的时间复杂度为O(1);

新增和删除操作:需要调整其他元素,例如要新增一个元素n到下标i的位置,则需要调整i以后的元素,最好情况是新增到最后一位,此时时间复杂度是O(1),最差情况是添加到第一位,则需要调整整个数组所有元素,此时时间复杂度是O(n),那么平均时间复杂度是(1+…+n)/n=O(n),删除操作也与之类似。

优化方案:可以不用每一次删除都调整其他所有元素位置,将每次需要删除的元素记录(标记)起来,当数据空间不足以存储新数据时,再清除所有记录的元素(类似于jvm的标记清除算法)。

二维数组:例如m*n,则a[i][j]的内存地址为:数组首地址+(i*n+j)*数据大小。

关于数组下标从0开始的原因,通常认为有两个原因:由于C语言是从0开始,其他语言为了减少程序员学习成本,都模仿的C语言;还有就是偏移量如果从1开始,那么找地址时就是:首地址+(偏移量-1)* 数据大小,会多一次减法操作,影响性能。

Java中,数组和ArrayList的应用场合:

容器:业务操作,对性能没有极端要求的场景;

数组:对性能有要求,或者需要存储基本数据类型的场景。

链表

链表不需要连续的内存空间,数据之间的内存可以是零散的。

链表包含单链表,循环链表,双向链表。

单链表:链表中每一个节点包含两个部分,数据和下一节点指针(next),头节点包含基地址,尾节点指向一个空地址NULL;

循环链表:在单链表的基础上,尾节点的下一节点指针指向了头节点;

双向链表:链表中每一个节点包含三个部分,数据、上一节点指针(prev)和下一节点指针;

访问操作:需要从头节点开始查找,复杂度为O(n);

删除和插入操作:找到需要删除的节点,将该节点的上一节点的next指向该节点的下一节点,删除操作本身的时间复杂度是O(1),主要的时间耗费是在查找节点上。

对于双向链表,虽然花费的空间大一些,但是在删除或者插入节点的时候,能够直接获取到判断操作位置的前一个节点(空间换时间)。例如,删除一个节点分为两种情况:

  1. 删除与给定节点数据相等的节点q,此时需要从链表第一个节点开始找并比较数据是否相等,直到找到p->next=q为止,然后将上一节点指针指向被删除节点的下一个节点;

  2. 删除给定的指针所指向的节点q,此时已知需要删除的数据,如果直接删除该节点,那么还需要遍历找到该节点的上一节点,但是使用双向链表的时候,就无需遍历,根据被删除节点的前置指针就能找到上一节点,即通过q->prev的到p,然后将p->next指向r,并将r->prev指向p。

链表不能像数组一样充分利用CPU缓存,因为CPU在内存中读取数组数据时,读取的并不是某一个数据,而是一个数据块,即读取下标为i的数据会一起读取i+n的数据块,下次查找数据时就能够首先查询缓存,弥补了读取内存带来的速度差的缺陷。实际项目中需要根据场合来使用对应的数据结构。

操作受限的线性表,一种先入后出的数据结构,只支持入栈(push)和出栈(pop)。

时间复杂度:由于入栈和出栈操作的都是栈顶元素,所以为O(1);

空间复杂度:由于入栈操作和出栈操作时只需要一个额外的空间存储操作的元素,所以是O(1);

栈是一种抽象的数据结构,链表和数组是一种实际存在于内存中的数据结构。所以栈的实现可以是数组和链表,如果是数组实现的就叫顺序栈,链表实现的叫链式栈。

入栈操作分析:对于动态可扩容的顺序栈,入栈时需要判断空间是否可以存储入栈元素,最好时间复杂度就是O(1),如果需要扩容,那么就需要移动原来的n个元素,最坏时间复杂度就是O(n),如果均摊到每一次入栈,就是每一次入栈只需要一次O(1)的push到栈顶的操作加上一次数据移动操作,所以摊还时间复杂度也是O(1)。

应用场景:

1.浏览器的前进后退

定义两个栈,一个保存后退页面back stack ,另一个保存前进页面forward stack。从a页面进入到b页面时,将a放到back stack,从b到c页面,就将c放入back stack,如果需要点击后退按钮,则将c放入forward stack,从back stack取出b渲染页面,然后再点击前进按钮,则将b再次放入back stack,将c从forward stack中取出来。

2.简单运算

定义两个栈,一个保存操作数,一个保存操作符。从左到右遍历2+3*4-5/5,遇到数字就压入操作数栈,遇到操作符就与操作符栈顶元素比较,当遇到的操作符优先级小于操作符栈顶的操作符时,从操作数栈取出两个数字执行操作,将算得的结果压入操作数栈,继续比较,算的结果以后清空栈。

3.函数调用栈

每一个函数都是一个栈帧,当调用函数时则将被调用函数压进栈里,处于栈顶。

4.括号匹配

扫到左括号时放入栈里,扫到右括号则从栈里取出栈顶元素判断是否是一对,直到栈中元素匹配完成,如果能够恰好匹配上,栈中最后会没有元素。

函数调用采用栈这种数据结构,是因为函数调用时很符合前后函数先入后出德思想。

队列

操作受限的线性表,一种先入先出的数据结构,只支持入队(enqueue)和出队(dequeue)操作,同样是一种抽象数据结构,如果通过数组实现称之为顺序队列,如果通过链表实现,则称之为链式队列。

时间复杂度:链式队列入队和出队的时间复杂度都是O(1),顺序队列入队时,可能会触发数据搬移(队列头有元素出队),所以最好时间复杂度时O(1),最坏时间复杂度度时O(n),由于入队时触发一次数据搬移后剩下的入队时间复杂度都是O(1),所以摊还时间复杂度也是O(1);

空间时间复杂度:O(1);

1.循环队列

循环顺序队列的首(head)和尾(tail)是相连的,成一个环状,因此入队时不需要进行数据搬移,直接将tail往后移一位即可,直到数组空间满;

2.阻塞队列

阻塞队列同样有head和tail两个位置标记首尾,如果队列为空时,会阻塞出队操作,直到队列中有元素放入;

3.并发队列

在入队和出队操作上加上同步关键字,或者使用顺序队列,通过cas操作实现;

循环队列最重要和最难的部分就是在于判断队列的空和满的条件。

参考

本节相关的学习代码参考github:

https://github.com/liuhuijun11832/algorithm

坚持原创、技术分享。请作者喝杯茶吧!