数据结构与算法、模板总结

领先源自专业知识提升价值数据结构与算法Page1第一章概念介绍第二章常用数据结构第三章常用算法第四章模板领先源自专业知识提升价值什么是数据结构？第一章概念介绍Page2从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。数据元素是数据中的一个“个体”，是数据的基本单位。数据结构是指数据以及互相之间的联系，是带结构的数据元素的集合。领先源自专业知识提升价值第一章概念介绍案例分析1学生表如下图所示，其中数据元素是学生记录，每个数据元素包括4个数据项（学号、姓名、性别和班级）。请用计算机语言实现上面数据的存储???Page3学号姓名性别班级1刘丽女1115陈华男712王琦男75王萍女2领先源自专业知识提升价值第一章概念介绍方法一：顺序存储struct{intnNum;//学号charname[8];//名字charsex[3];//性别intnCls;//班级}Student[4]={{1,“刘丽”,“女”,11},{15,“陈华”,“男”,7},{12,“王琦”,“男”,7},{5,“王萍”,“女”,2}};Page4……1刘丽女1115陈华男712王琦男75王萍女2……领先源自专业知识提升价值第一章概念介绍方法二：链表存储structStudentNode{intnNum;//学号charname[8];//名字charsex[3];//性别intnCls;//班级structStudentNode*pNext;};Page5……1刘丽女11…………5王萍女2NULL…………15陈华男7…………12王琦男7……Head领先源自专业知识提升价值案例分析2有一种数据结构如右图所示：第一章概念介绍Page6这是什么数据结构呢???领先源自专业知识提升价值第一章概念介绍数据类型正式开始学习之前，我们先来回顾一下C/C++常用数据类型，如下：1、基本类型short/long/unsignedint,float/double/longdouble,char2、指针：*是指针符，&是取址符。intn=5;int*p=&n;3、数组inta[5]={1,2,3,4,5};4、结构体、共用体、自定义类struct、union、classPage7领先源自专业知识提升价值数据结构与算法Page8第一章概念介绍第二章常用数据结构第三章常用算法第四章模板领先源自专业知识提升价值第二章常用数据结构常用数据结构类型Page9ListSetverctor树栈数据结构map队列领先源自专业知识提升价值第二章常用数据结构顺序表：vectorvector是STL中提供的一种数据结构，它是一个模板类，可以存放任意同一类型的对象；vector对象可以在运行时高效地添加元素；vector是连续存储的，可以认为这是一个直接数组功能的类；vector的元素访问需要通过iterator迭代器进行。Page10领先源自专业知识提升价值第二章常用数据结构关键函数vector提供的主要函数如下：Page11函数说明empty()如果vector是空的则返回truesize()返回容器中元素个数front()返回容器中第一个元素的引用back()返回容器中最后一个元素的引用push_back()向容器末尾添加一个元素pop_back()弹出容器中最后一个元素insert()在指定节点之前插入元素clear()清空容器领先源自专业知识提升价值第二章常用数据结构实例分析vector的使用实例参见：DataStructExample\DataStructExample\VectorExample.cppPage12领先源自专业知识提升价值第二章常用数据结构链表：listlist是双向循环链表，每一个元素都知道前面一个元素和后面一个元素。在STL中，list和vector一样，是两个常被使用的容器。Page13领先源自专业知识提升价值第二章常用数据结构关键函数list提供的主要函数如下：Page14函数说明函数说明empty()如果list是空的则返回truepop_back()删除最后一个元素size()返回list中的元素个数pop_front()删除第一个元素begin()返回指向第一个元素的迭代器push_back()在list的末尾添加一个元素end()返回末尾的迭代器push_front()在list的头部添加一个元素front()返回第一个元素back()返回最后一个元素insert()插入一个元素到list中clear()删除所有元素领先源自专业知识提升价值第二章常用数据结构实例分析list的使用实例参见：DataStructExample\DataStructExample\ListExample.cppPage15领先源自专业知识提升价值第二章常用数据结构list与vector的区别1）list不支持对元素的任意存取；verctor则支持任意存取。2）list提供对表首元素的操作push_front、pop_front；vector不具备。3）list的迭代器不会存在失效的情况；vector的迭代器可能会失效。4）list允许快速的插入和删除；verctor不允许。5）list不存在重新申请内存的情况，成本是恒定的；vector存在构造成本。另外，在销毁旧内存的时候，vector会调用析构函数，存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！Page16领先源自专业知识提升价值第二章常用数据结构集合：setset的含义是集合。它是一个有序的容器，能够将插入的元素按照键值自动排序；它能保证集合中的元素不重复；它的检索效率高于list和队列。应用场景构造set集合主要目的是为了快速检索，不可直接去修改键值。Page17领先源自专业知识提升价值第二章常用数据结构关键函数set提供的主要函数如下：Page18函数说明pairiterator,boolinsert(value)插入value，返回pair配对对象iteratorinsert(&pos,value)在pos位置之前插入value，返回新元素位置size_typeerase(value)移除set容器内元素值为value的所有元素，返回移除的元素个数voiderase(&pos)移除pos位置上的元素voidclear()移除set容器内所有元素领先源自专业知识提升价值第二章常用数据结构实例分析set的使用实例参见：DataStructExample\DataStructExample\SetExample.cppPage19领先源自专业知识提升价值第二章常用数据结构特点1）不能直接改变元素值，因为那样会打乱原本正确的顺序；2）不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取；3）元素比较动作只能用于类型相同的容器。Page20领先源自专业知识提升价值第二章常用数据结构集合：mapmap是c++的一个键值对容器，它提供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果。关键函数map提供的主要函数如下：Page21函数说明[]根据key获取valueinsert()插入键值对find()查找元素，函数返回一个迭代器，指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。领先源自专业知识提升价值第二章常用数据结构实例分析map的使用实例参见：DataStructExample\DataStructExample\MapExample.cppPage22领先源自专业知识提升价值第二章常用数据结构树树是由n(n≥0)个结点组成的有限集合。其中：树的定义是递归的，一颗树是由若干个子树构成的，每一个子树由更小的若干子树构成。结点•25、64是48的孩子结点•25是36的父亲结点•25、64是兄弟结点特点每一个节点都可以有不止一个后继，都有且只有一个前驱。Page23领先源自专业知识提升价值第二章常用数据结构实例分析树的使用实例参见：DataStructExample\DataStructExample\TreeExample.cppPage24领先源自专业知识提升价值第二章常用数据结构栈栈是最常用、最重要的数据结构之一。它是一种特殊的线性表，只能在表的一端进行插入和删除操作。通常称插入删除这一端为栈顶，另一端称为栈底。数据从栈顶插入，从栈顶取出。栈遵循后进先出的原则：Page25领先源自专业知识提升价值第二章常用数据结构实例分析用S表示进栈操作，用P表示出栈操作，如果元素进栈顺序是1234，为了得到1342出栈顺序，请给出相应的S和P操作串？解：其操作过程如下图所示：可知，操作串是SPSSPSPP。Page26领先源自专业知识提升价值第二章常用数据结构栈的应用栈结构比较常用的场景有：1）表达式求值，例如(69-9)/(4+6)2）二叉树的各种算法3）递归、非递归转换Page27领先源自专业知识提升价值第二章常用数据结构stack栈stack是STL中的很有用的容器适配器之一，默认基于Deque容器（双向链表）实现。使用stack只需要包含头文件stack。•关键函数Page28函数说明stackT构造栈对象push()入栈pop()出栈empty()判断栈是否为空，当栈空时返回truesize()获取栈中的元素个数领先源自专业知识提升价值第二章常用数据结构实例分析栈的使用实例参见：DataStructExample\DataStructExample\StackExample.cppPage29PS:需要注意的是，出栈操作只是删除栈顶的元素，并不返回该元素。领先源自专业知识提升价值第二章常用数据结构队列队列也是是一种特殊的线性表，队列允许在表的一端进行插入，在表的另外一端进行删除。通常把进行插入的一端称作队尾(rear)，进行删除的一端称作队首或队头(front)。队列遵循先进先出的原则：Page30领先源自专业知识提升价值第二章常用数据结构实例分析设有4个人站成一排，从左向右编号分别为1~n，现在从左往右报数“1，2，1，2…”，报数为1的人出列，数2的人不动。反复报数，直到所有人都出列为止，请给出出列顺序？解：方法是构造一个队列，队列元素有4个，出列一个结点，下一个节点出列再入列，直到队列为空。出列顺序是：1324。Page31领先源自专业知识提升价值第二章常用数据结构队列的应用队列也应用广泛，比较常用的场景有：1）操作系统资源分配2）操作系统消息队列Page32领先源自专业知识提升价值第二章常用数据结构queue队列queue用于模拟队列这种数据结构(先进先出FIFO)。queue在头文件queue中定义。•关键函数Page33函数说明queueT构造队列对象push()将x元素接到队列的末端pop()弹出队列的第一个元素，并不会返回元素的值empty()判断栈是否为空，当栈空时返回truefront()访问队首元素back()访问队尾元素size()访问队中的元素个数领先源自专业知识提升价值第二章常用数据结构实例分析队列的使用实例参见：DataStructExample\DataStructExample\QueueExample.cppPage34领先源自专业知识提升价值第二章常用数据结构小结数据结构是软件开发的基础，著名的类库皆是在这些规则的基础上经过封装而来。掌握数据逻辑结构，了解各种存储结构，并在此基础上熟练使用各种类库，才能写出优秀代码。Page35领先源自专业知识提升价值数据结构与算法Page36第一章概念介绍第二章常用数据结构第三章常用算法第四章模板领先源自专业知识提升价值第三章常用算法算法是什么？数据元素之间的关系有逻辑关系和物理关系，对应操作有逻辑结构上的操作功能。把具体存储结构上的操作实现方法称为算法。Page37领先源自专业知识提升价值第三章常用算法算法的特性Page