数据结构复盘

什么是线性表线性表是抽象的逻辑规则元素有序一对一前驱后继我感觉这些 “表” ,全是基于数组来模拟的线性表顺序表链表的区别线性表是顶层的抽象定义顺序表和链表是这个定义的具体实现方式线性表的顺序储存就是顺序表链式储存就是链表关于顺序表顺序表在任意位置p删除元素,将[p1,队尾]的元素视为整体,往前覆盖一个单位STL—vectorvector的底层是一个会自动扩容的顺序表,可以把ta当一个会自动变长的数组看待关于链表如果说数组是一排固定位置的格子,那么链表就是结点分散存储,靠指针串起来,没有固定内存位置的线性数据结构链表具有储存数据的数据域和储存逻辑关系的指针域链表进行插入,删除操作时,针对修改前驱和后继的顺序问题,我的总结是:在元素1前插入元素2,就最后改元素1的前驱;在元素1后插入元素2,就最后改元素1的后继什么是栈?栈是一种只能在一端执行数据插入和删除操作的线性表队列是两端执行,前端进行删除,后端进行插入STL—stackstack模拟了栈这种数据结构的行为什么是队列队列是一种访问受限的线性表,只能在表的一端进行插入操作,另一端进行删除操作可以形象地类比食堂打饭时排的队伍,打完饭的人从队头离开,要打饭的人从队尾加入STL—queuequeue模拟了队列这种数据结构的行为STL—dequedeque模拟了双端队列这种数据结构,核心就是两端都可以进行插入和删除操作(头插/删 , 尾插/删)什么是树?树是一种非线性数据结构,由若干个结点组成,结点之间通过父子关系连接,且整个结构中不会出现环树的存储树的存储运用孩子表示法什么是孩子表示法?孩子表示法就是把所有结点都放在一个数组里,每个结点再拉一条链表,链上存ta所有孩子的下标树的存储大体上有两种方式,一种是基于vector数组,另一种是基于链表(链式前向星).vector数组直接用下标来访问给定结点的所有孩子,链表靠h数组的下标来访问给定结点的所有孩子链式前向星的数组h是用来存储所有结点的哨兵位(数组h就像是一棵树的主干,数组的下标就好比主干的分支,每个分支里存的多个元素就好比分支上结的果实)链式向前星------建树constintN1e510;inth[N],e[N*2],ne[2*N],id;voidadd(intx,inty)// 将y头插在x的链表中{id;e[id]y;ne[id]h[x];h[x]id;}intmain(){intn;cinn;for(inti1;in;i){inta,b;cinab;add(a,b);add(b,a);}return0;}深度优先遍历与宽度优先遍历两种遍历方式的共同点就是从给定的结点出发,遍历一遍这个结点的所有孩子,找出没标记的vector存储就用范围for遍历数组,链表存储就用for循环遍历链表元素深度优先遍历深度优先遍历的具体流程:从根节点出发,依次遍历每一颗子树遍历子树的时候,重复第一步// 深度优先遍历voiddfs(intx){coutx ;boolst[x]true;for(ih[x];i;ine[i]){intte[i];if(!st[t])dfs(t);}}宽度优先遍历宽度优先遍历的具体流程:初始化一个队列根节点入队,同时标记这个结点当队列不为空时,拿出队头元素,访问,然后将队头元素的所有孩子入队,同时打上标记重复3过程,直到队列为空// 宽度优先遍历queueintq;voidbfs(){q.push(1);boolst[1]true;while(q.size()){inttq.front();q.pop();coutt ;for(ih[t];i;ine[i]){intue[i];if(!st[u]){q.push(u);st[u]true;}}}}关于vector数组的建树及其遍历,大体思路与链式前向星相同,这里不再赘述什么是二叉树?二叉树的核心规则是每个结点最多只有两个子节点,且子节点有明确的左右顺序(左右子树不能随意交换)二叉树的建树二叉树的建树就是把所有结点的左右孩子都存在对应编号的左右数组里intn;intl[N],r[N];// 存储左右孩子的左右数组intmain(){cinn;// 表示有n个结点for(inti1;in;i){// 存下 i 号结点的左右孩⼦cinl[i]r[i];}return0;}二叉树的顺序存储如果二叉树按照宽度优先遍历的顺序进行存储,那么子节点与父节点的关系可由编号计算设结点下标为i:如果父存在,父下标为i/2如果左孩子存在,左孩子下标为2i如果右孩子存在,右孩子下标为2i1二叉树的遍历先序遍历,中序遍历,后序遍历都是基于深度优先遍历的模式下实现的三种遍历方式的不同在于处理根节点的时机先序遍历可以说就是深度优先遍历的过程中序遍历就是先一条路走到黑,永远是先访问左孩子(没有左孩子也要遵循这个规则),接着回程访问根节点(输出),然后是右孩子,访问到叶子结点就直接输出- 后续遍历也是先一条路走到黑,碰到叶子结点就输出,从右子树回来时再输出根节点什么是完全二叉树?完全二叉树就是在满二叉树的基础上,在最后一层的叶子结点上,从右往左依次删除若干个结点,剩下的就是完全二叉树什么是堆?堆是一棵满足父节点与子节点大小规则的完全二叉树堆分为大根堆和小根堆大根堆(小根堆)的核心特点-----每个父节点的值都大于(小于)等于其所有孩子结点的值堆可以执行删除任意元素的操作,但是堆的设计初衷是高效操作堆顶元素,删除任意元素需要额外处理,且时间复杂度会比删除堆顶元素高堆的两个核心算法向上调整算法与⽗结点的权值作⽐较如果⽐它⼤就与⽗亲交换交换完之后重复 1 操作直到⽐⽗亲⼩或者换到根节点的位置// 向上调整算法voidup(intchild){intparentchild/2;// 父结点存在且父结点的值小于孩子结点的值时进入循环while(parent1heap[child]heap[parent]){swap(heap[child],heap[parent]);// 交换孩子结点与父结点的值childparent;// 交换孩子结点与父结点的下标parentchild/2;// 重新定义父子结点}}向下调整算法找出左右⼉⼦中权值最⼤的那个如果⽐它⼩就与其交换交换完之后重复 1 操作直到⽐⼉⼦结点的权值都⼤或者换到叶节点的位置// 向下调整算法// 核心是大的数往上冒小的数往下沉voiddown(intparent){intchildparent*2;// 从父节点的左孩子找起原代码笔误应为parent*2while(childn)// 如果左孩子存在{// 如果右孩子存在就和右孩子进行比较让child指向最大的那个孩子if(child1nheap[child]heap[child1])child;if(heap[parent]heap[child])break;// 剩下的情况都是父节点的数小于孩子结点的情况swap(heap[parent],heap[child]);// 先交换父亲和孩子的值parentchild;// 再交换父亲和孩子的下标childparent*2;// 以新的结点为父亲重新找左孩子}}STL—priority_queue(优先级队列)priority_queue 底层基于堆的实现,核心特征是队列的队首永远是优先级最高的元素.不管插入的顺序如何,都会自动实现堆的调整逻辑,保证每次取出的元素都是最大或最小的那个什么是二叉搜索树(BST)?可以把BST想象成一本按页码排序的书,左边页码更小,右边更大具体规则:对于树中的任意一个结点,其左子树的值都小于该节点的值,其右子树的值都大于该节点的值ps:只有一个结点的树也算二叉搜索树左,右子树也必须是一个二叉搜索树