数据结构入门VIP免费

数据结构入门IntroductiontoDataStructure主讲何宣编剧廖洪舒Hs趣闻？1.第一次校赛2.08年北京喝了红牛，抬头看见天大mm喷鼻血3.UESTC_floyd雅加达259816min重要的事实：当代计算机1s内可做10^7左右次计算配置好的机器可到k*10^7~10^8在这个限制下时间复杂度一定的算法存在能处理的规模上限复杂度数量级最大规模O(logN)>>10^20很大O(N^1/2)10^1210^14O(N)10^610^7O(NlogN)10^510^6O(N^2)10002500O(N^3)100500O(N^4)5050O(2^N)2020O(3^N)1415O(N!)910什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。理解：数据结构是一种特别的储存和组织数据的方式，以便于我们更高效地维护和使用数据。数据结构的含义：数据、关系、操作例子：一维数组数据：a[1],a[2],…,a[n]关系：前驱/后继操作：随机存取，插入，删除…程序＝数据结构＋算法（数据结构为算法服务）根据算法对数据的操作要求，设计合适的数据结构实现同一套操作，可以用多种数据结构如何降低时空复杂度，又方便实现？维护一个电话薄，方便进行插入删除和查找操作：插入，删除，查找逻辑结构：无序线性表储存结构：数组•插入：插到尾部比较方便，O(1)•删除：“合并两半”导致元素移动，最坏O(n)•查找：最坏O(n)储存结构：链表•插入：插到头部比较方便，O(1)•删除：（找到被删除元素后）O(1)•查找：最坏O(n)维护一个电话薄，方便进行插入删除和查找操作：插入，删除，查找逻辑结构：有序线性表储存结构：数组•插入：最坏O(n)•删除：最坏O(n)•查找：二分查找，最坏O(logn)储存结构：链表•插入：（找到后）最坏O(1)•删除：（找到后）最坏O(1)•查找：最坏O(n)数据结构即是研究数据的各种逻辑结构和储存结构，以及在此基础之上对数据的各种操作。今天学什么？栈(Stack)队列(Queue)并查集(Disjoint-set)二叉堆(BinaryHeap)平衡二叉搜索树(Self-balancingBinarySearchTree)线段树(SegmentTree)树状数组(BinaryIndexedTree)外特性：后进先出(LIFO)交卷子逻辑结构：只在一端操作的线性表数组实现：元素stack[maxn];栈顶指针top;•入栈(push)：stack[top++]=element;•出栈(pop)：element=stack[--top];•空栈条件：top==0栈(Stack)PushPoptopSTL(StandardTemplateLibrary)#includeusingnamespacestd;stacks;intx=s.top();s.push(x);s.pop();s.empty();s.size();栈的应用•保护现场(系统栈)•括号匹配•表达式求值•深度优先搜索（Depth-firstSearch）栈(Stack)外特性：先进先出(FIFO)食堂排队吸管里的饮料数组实现：元素queue[maxn]，队首head，队尾tail•入队：queue[tail++]=element;•出队：element=queue[head++];•队空条件：head>=tail•问题：出队的元素还在数组里，不是很浪费吗？队列(Queue)poppushheadtailSTL(StandardTemplateLibrary)#includeusingnamespacestd;queueq;intx=q.front();q.push(x);q.pop();q.empty();q.size();队列的应用•广度优先搜索（Breadth-firstSearch）•……扩展•循环队列（CircularQueue）•最短路的SPFA算法(ShortestPathFasterAlgorithm)•双端队列（DoubleEndedQueue）•例：SlidingWindow•对某些动态规划（DynamicProgramming）算法进行优化队列(Queue)例：SlidingWindowWindowpositionMaximumvalue[13-1]-3536731[3-1-3]5367313[-1-35]367513-1[-353]67513-1-3[536]7613-1-35[367]7并查集(Disjoint-set)引例两种操作：•合并(Union)两个集合•查找(Find)某元素属于哪个集合所以叫做并查集。集合如何表示？并查集(Disjoint-set)每个集合用一棵“有根树”表示，根节点就是这个集合的代表元•定义数组set[1…n]•set[i]=i，则i表示本集合，且是集合对应树的根•set[i]=j，j<>i，则j是i的父节点.并查集(Disjoint-set)123456789101232134334iSet(i)15247103689并查集(Disjoint-set)intfindSet(intx){if(x==set[x])returnx;elsereturnfindSet(set[x]);}voidunionSet(intx,inty){intfx=findSet(x);intfy=findSet(y);set[fy]=fx;}并...