数据结构（续）

第三章链表和list一链表的概念1.列表的定义2.列表的定义二链表的模拟实现1.单链表的模拟实现动态申请链表节点和链表构建动态申请节点Node节点将动态申请一个节点的这个动作封装成一个函数打印链表的所有元素printlist:打印链表三动态链表—list在算法⽐赛中⼀般不会使⽤ new 和 delete 去模拟实现⼀个链表。⽽ STL ⾥⾯的 list 的底层就是动态实现的双向循环链表增删会涉及 new 和 delete效率不⾼竞赛中⼀般不会使⽤这⾥了解⼀下即可。1push_front / push_back1.push_front头插2.push_back尾插。2pop_front / pop_back1.pop_front头删2.pop_back尾删四算法题1排队顺序2单向链表第四章 栈的概念1.栈的概念栈是⼀种只允许在⼀端进通常是尾端⾏数据插⼊和删除操作的线性表。也就是栈是一种访问受限的线性表。• 进⾏数据插⼊或删除的⼀端称为栈顶另⼀端称为栈底。不含元素的栈称为空栈。•进栈就是往栈中放⼊元素出栈就是将元素弹出栈顶。2.栈的模拟实现3.stack1创建与list和vector相似stackT st; T 可以是任意类型的数据。2size/emptysize返回栈⾥实际元素的个数empty返回栈是否为空。时间复杂度O(1)3toptop返回栈顶元素但是不会删除栈顶元素。时间复杂度O(1)。代码测试第五章 队列和queue1.队列的概念相关术语空队入队队头与队尾出队2.队列的模拟实现1创建•⼀个⾜够⼤的数组充当队列•⼀个变量 h标记队头元素的前⼀个位置•⼀个变量 t标记队尾元素的位置。两个变量(h, t]是⼀种左开右闭的形式这样设定纯属个⼈喜好因为后续的代码写着⽐较舒服。当然也可以h标记队头元素的位置。只要能控制住代码不出现bug想怎么实现就怎么实现。第七章 二叉数三二叉树的遍历1.深度优先遍历代码演示2.宽度优先遍历四算法题1.新二叉数2.二叉树的遍历3.二叉数的深度4.先序排列5.美国血统6.二叉树问题第八章 堆和priority_queue一.堆的定义和存储1.定义2.存储二.核心操作1.向上调整算法2.向下调整算法3.priority_queue的创建列less和greater都只针对内置类型如果数据类型为结构体那么需要在结构体中重载比较运算符从而创建大根堆和小根堆。4.算法题12