数据结构与算法、模板

1、领先源自专业领先源自专业 知识提升价值知识提升价值数据结构与算法Page 1第一章 概念介绍第二章 常用数据结构第三章 常用算法第四章 模板领先源自专业领先源自专业 知识提升价值知识提升价值n 什么是数据结构？第一章 概念介绍Page 2从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。数据元素是数据中的一个“个体”，是数据的基本单位。数据结构是指数据以及互相之间的联系，是带结构的数据元素的集合。领先源自专业领先源自专业 知识提升价值知识提升价值第一章 概念介绍n 案例分析1学生表如下图所示，其中数据元素是学生记录，每个数据元素包括4个数据项（学号、姓名、性别和班级

2、）。请用计算机语言实现上面数据的存储请用计算机语言实现上面数据的存储?Page 3学号姓名性别班级1刘丽女1115陈华男712王琦男75王萍女2领先源自专业领先源自专业 知识提升价值知识提升价值第一章 概念介绍 方法一：顺序存储struct int nNum;/学号 char name8;/名字 char sex3;/性别 int nCls;/班级Student4 = 1, “刘丽”, “女”, 11, 15, “陈华”, “男”, 7, 12, “王琦”, “男”, 7, 5, “王萍”, “女”, 2 ;Page 41刘丽女1115陈华 男712王琦 男75王萍女2领先源自专业领先源自专业

3、 知识提升价值知识提升价值第一章 概念介绍 方法二：链表存储struct StudentNode int nNum;/学号 char name8;/名字 char sex3;/性别 int nCls;/班级 struct StudentNode *pNext;Page 51刘丽女115王萍女2NULL15陈华男712王琦男7Head领先源自专业领先源自专业 知识提升价值知识提升价值n 案例分析2有一种数据结构如右图所示：第一章 概念介绍Page 6这是什么数据这是什么数据结构呢结构呢?领先源自专业领先源自专业 知识提升价值知识提升价值第一章 概念介绍n 数据类型正式开始学习之前，我们先来回顾一

4、下C/C+常用数据类型，如下：1、基本类型short/long/unsigned int, float/double/long double, char2、指针：*是指针符，&是取址符。 int n = 5; int *p = &n;3、数组int a5 = 1,2,3,4,5;4、结构体、共用体、自定义类struct、union、classPage 7领先源自专业领先源自专业 知识提升价值知识提升价值数据结构与算法Page 8第一章 概念介绍第二章 常用数据结构第三章 常用算法第四章 模板领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 常用数据结构类

5、型Page 9ListSetverctor树树栈栈数据结构map队列队列领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 顺序表：vector vector是STL中提供的一种数据结构，它是一个模板类，可以存放任意同一类型的对象； vector对象可以在运行时高效地添加元素； vector是连续存储的，可以认为这是一个直接数组功能的类； vector的元素访问需要通过iterator迭代器进行。Page 10领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 关键函数vector提供的主要函数如下：Page 11函数说明empty()如果vector

6、是空的则返回true size() 返回容器中元素个数front()返回容器中第一个元素的引用back()返回容器中最后一个元素的引用push_back()向容器末尾添加一个元素pop_back()弹出容器中最后一个元素insert()在指定节点之前插入元素 clear()清空容器领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析vector的使用实例参见：DataStructExampleDataStructExampleVectorExample.cppPage 12领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 链表：listlis

7、t是双向循环链表，每一个元素都知道前面一个元素和后面一个元素。在STL中，list和vector一样，是两个常被使用的容器。Page 13领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 关键函数list提供的主要函数如下：Page 14函数说明函数说明empty()如果list是空的则返回true pop_back()删除最后一个元素 size()返回list中的元素个数pop_front()删除第一个元素 begin() 返回指向第一个元素的迭代器 push_back()在list的末尾添加一个元素 end()返回末尾的迭代器 push_front() 在list的头

8、部添加一个元素front()返回第一个元素back()返回最后一个元素 insert()插入一个元素到list中 clear()删除所有元素 领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析list的使用实例参见：DataStructExampleDataStructExampleListExample.cppPage 15领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 list与vector的区别1）list不支持对元素的任意存取；verctor则支持任意存取。2）list提供对表首元素的操作push_front、pop_front；v

9、ector不具备。3）list的迭代器不会存在失效的情况；vector的迭代器可能会失效。4）list允许快速的插入和删除；verctor不允许。5）list不存在重新申请内存的情况，成本是恒定的；vector存在构造成本。另外，在销毁旧内存的时候， vector会调用析构函数，存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！Page 16领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 集合：setset的含义是集合。 它是一个有序的容器，能够将插入的元素按照键值自动排序； 它能保证集合中的元素不重复； 它的检索效率高于list和队

10、列。 应用场景构造set集合主要目的是为了快速检索，不可直接去修改键值。Page 17领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 关键函数set提供的主要函数如下：Page 18函数说明pair insert(value)插入value，返回pair配对对象iterator insert(&pos, value)在pos位置之前插入value，返回新元素位置size_type erase(value) 移除set容器内元素值为value的所有元素，返回移除的元素个数void erase(&pos) 移除pos位置上的元素void clear()移除s

11、et容器内所有元素领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析set的使用实例参见：DataStructExampleDataStructExampleSetExample.cppPage 19领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 特点1）不能直接改变元素值，因为那样会打乱原本正确的顺序；2）不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取；3）元素比较动作只能用于类型相同的容器。Page 20领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 集合：mapmap是c+的一个键值对容器，它提

12、供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果。 关键函数map提供的主要函数如下：Page 21函数说明根据key获取valueinsert()插入键值对 find()查找元素，函数返回一个迭代器，指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。 领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析map的使用实例参见：DataStructExampleDataStructExampleMapExample.cppPage 22领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 树树是由n(n0)个结点

13、组成的有限集合。其中：树的定义是递归的，一颗树是由若干个子树构成的，每一个子树由更小的若干子树构成。 结点25、64是48的孩子结点25是36的父亲结点25、64是兄弟结点 特点每一个节点都可以有不止一个后继，都有且只有一个前驱。Page 23领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析树的使用实例参见：DataStructExampleDataStructExampleTreeExample.cppPage 24领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 栈栈是最常用、最重要的数据结构之一。它是一种特殊的线性表，只能在表的一端

14、进行插入和删除操作。通常称插入删除这一端为栈顶，另一端称为栈底。数据从栈顶插入，从栈顶取出。 栈遵循后进先出的原则：Page 25领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析用S表示进栈操作，用P表示出栈操作，如果元素进栈顺序是1234，为了得到1342出栈顺序，请给出相应的S和P操作串？解：其操作过程如下图所示：可知，操作串是SPSSPSPP。Page 26领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 栈的应用栈结构比较常用的场景有：1）表达式求值，例如(69-9)/(4+6) 2）二叉树的各种算法3）递归、非递归转换Page 2

15、7领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 stack栈stack是STL中的很有用的容器适配器之一，默认基于Deque容器（双向链表）实现。使用stack 只需要包含头文件。关键函数Page 28函数说明stack构造栈对象push()入栈pop()出栈empty()判断栈是否为空，当栈空时返回truesize()获取栈中的元素个数领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析栈的使用实例参见：DataStructExampleDataStructExampleStackExample.cppPage 29 PS:需要注意的是，

16、出栈操作只是删除栈顶的元素，并不返回该元素。领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 队列队列也是是一种特殊的线性表，队列允许在表的一端进行插入，在表的另外一端进行删除。通常把进行插入的一端称作队尾(rear)，进行删除的一端称作队首或队头(front)。 队列遵循先进先出的原则：Page 30领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析设有4个人站成一排，从左向右编号分别为1n，现在从左往右报数“1，2，1，2”，报数为1的人出列，数2的人不动。反复报数，直到所有人都出列为止，请给出出列顺序？解：方法是构造一个队列，队列元素

17、有4个，出列一个结点，下一个节点出列再入列，直到队列为空。出列顺序是：1324。Page 31领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 队列的应用队列也应用广泛，比较常用的场景有：1）操作系统资源分配2）操作系统消息队列Page 32领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 queue队列queue用于模拟队列这种数据结构(先进先出 FIFO)。queue在头文件中定义。关键函数Page 33函数说明queue构造队列对象push()将x元素接到队列的末端pop()弹出队列的第一个元素，并不会返回元素的值empty()判断栈是否为空，

18、当栈空时返回truefront()访问队首元素back()访问队尾元素size()访问队中的元素个数领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构 实例分析队列的使用实例参见：DataStructExampleDataStructExampleQueueExample.cppPage 34领先源自专业领先源自专业 知识提升价值知识提升价值第二章 常用数据结构n 小结数据结构是软件开发的基础，著名的类库皆是在这些规则的基础上经过封装而来。掌握数据逻辑结构，了解各种存储结构，并在此基础上熟练使用各种类库，才能写出优秀代码。Page 35领先源自专业领先源自专业 知识提升价值

19、知识提升价值数据结构与算法Page 36第一章 概念介绍第二章 常用数据结构第三章 常用算法第四章 模板领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 算法是什么？ 数据元素之间的关系有逻辑关系和物理关系，对应操作有逻辑结构上的操作功能。把具体存储结构上的操作实现方法称为算法。Page 37领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 算法的特性Page 38领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 案例分析设计算法，求aX2+bX+c=0的根。Page 39算法步骤：1、计算d=b*b-4*a*c2、如果d0,转53、

20、如果d=5,转94、如果d0,转125、计算x1 = (-b+sqrt(d)/(2*a)6、计算x2 = (-b-sqrt(d)/(2*a)7、显示两个实根x1和x28、转139、计算x=(-b)/(2*a)10、显示一个实根x11、转1312、显示没有实根13、算法结束 领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 算法设计的目标Page 40领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 递归在定义一个过程或函数时出现调用本身的情况，称为递归。 直接递归： P调用P自身； 间接递归：函数P调用q，q调用P。Page 41领先源自专业领先源自专业

21、 知识提升价值知识提升价值第三章 常用算法 应用场景1）定义是递归的，例如求和n!和斐波那契数列2）数据结构是递归的，例如单链表3）问题求解方法是递归的 实例分析递归函数算法的实例参见：DataStructExampleDataStructExampleRecursiveExample.cppPage 42领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 查找算法 顺序查找法在给定的数据结构中找出某个指定的元素是指在给定的数据结构中找出某个指定的元素。最好情况下只做一次比较，最差情况下要与所有的元素进行比较。在平均情况下大约要与表中的一般元素进行比较。对于较大的线性表，顺序

22、查找效率低下。应用场景1）线性表是无序表2）链式存储结构的表Page 43领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 实例分析（顺序查找）顺序查找算法的实例参见：DataStructExampleDataStructExampleSearchInOrderExample.cppPage 44领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 二分查找法（折半查找）查找过程：每次将待查记录所在区间缩小一半使用条件：采用顺序存储结构的有序静态查找表时间复杂度：O(log2n)Page 45领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 实

23、例分析（二分查找）顺序查找算法的实例参见：DataStructExampleDataStructExampleSearchInHalfExample.cppPage 46领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 排序算法Page 47排序算法直接插入排序冒泡排序归并排序基数排序直接选择排序希尔排序堆排序快速排序领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 冒泡排序Page 48领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板实例分析冒泡排序的实例参见：DataStructExampleDataStructExampleBubble

24、SortExample.cppPage 49领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 快速排序Page 50领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板实例分析快速排序的实例参见：DataStructExampleDataStructExampleQuickSortExample.cppPage 51领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 应用场景1）若n较小(如n50)，可采用直接插入或直接选择排序。当记录规模较小时，选用直接插入排序、直接选择排序为宜，最简单。2）若文件初始状态基本有序(指正序)，选用直接插人、冒泡或随

25、机的快速排序为宜；3）若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。Page 52领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 排序算法总结Page 53排序方法时间复杂度空间复杂度稳定性复杂性直接插入排序O(n2)O(1)稳定简单希尔排序O(nlog2n)O(1)不稳定复杂直接选择排序O(nlog2n)O(1)不稳定简单堆排序O(nlog2n)O(1)不稳定复杂冒泡排序O(n2)O(1)稳定简单快速排序O(nlog2n)O(n

26、log2n)不稳定复杂归并排序O(nlog2n)O(n)稳定复杂基数排序O(d(n+r)O(n+r)稳定复杂领先源自专业领先源自专业 知识提升价值知识提升价值n 时间复杂度和空间复杂度 时间复杂度算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作 T(n)=O(f(n)，称作算法的渐近时间复杂度，简称时间复杂度。 空间复杂度是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(f(n) 其中：n为问题的规模(或大小)。第三章 常用算法Page 54领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n STL算法STL算法部分主要由头文

27、件,组成，算法大致分为四类：Page 55可变序列算法非可变序列算法数值算法排序算法领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 STL非可变序列算法这是一组不破坏操作数据的模板函数，用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配,具有极为广泛的适用性。l 关键函数Page 56类型函数说明循环for_each()对序列中的每个元素执行某操作。查找find()在序列中找出某个值的第一次出现的位置。find_if()在序列中找出符合某谓词的第一个元素。find_end()在序列中找出一子序列的最后一次出现的位置。find_first_of()在序列中找出第一次

28、出现指定值集中之值的位置。计数count()在序列中统计某个值出现的次数。count_if()在序列中统计与某谓词匹配的次数。搜索search()找出两个序列相异的第一个元素。领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 STL可变序列算法这是一组能够修改容器元素数据的模板函数。l 关键函数Page 57类型函数说明复制copy()从序列的第一个元素起进行复制。交换swap()交换两个元素。transform将某操作应用于指定范围的每个元素变换replace()用一个给定值替换一些值。replace_if()替换满足谓词的一些元素填充fill_n()用一给定值取代前n个元

29、素。生成generate()用一操作的结果取代所有元素删除remove_if()删除满足谓词的元素。唯一unique()删除相邻的重复元素。领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 STL排序算法提供元素排序策略。l 关键函数Page 58类型函数说明排序sort()以很好的平均效率排序二分检索lower_bound()找到大于等于某值的第一次出现。binary_search()在有序序列中确定给定元素是否存在归并merge()归并两个有序序列。includes()一序列为另一序列的子序列时为真。堆操作sort_heap()给堆排序。最大和最小max()取得两个值中较

30、大的。min()取得两个值中较小的。领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 STL数值算法对容器内容进行数值计算。此种算法不多，涉及到专业领域中有用的算术操作，独立包涵于头文件中。l 关键函数Page 59函数说明Accumulate对标识的序列段元素之和，加到一个由val指定的初始值上。partial_sum创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。 inner_product对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。 adjacent_difference创建一个新序列，新序列中每个新值代表当前元素与上一个元

31、素的差。领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法 STL算法实例STL算法的部分实例参见：DataStructExampleDataStructExampleSTLAlgorithmExample.cppPage 60领先源自专业领先源自专业 知识提升价值知识提升价值第三章 常用算法n 小结我们的日常工作中一定会接触到各种算法，因而掌握一些基础的数据结构及算法是十分必要的。在本章的所有算法中，基础的查找和排序算法是一定要掌握的，请大家在课后注意多加练习。Page 61领先源自专业领先源自专业 知识提升价值知识提升价值数据结构与算法Page 62第一章 概念介绍第二章

32、常用数据结构第三章 常用算法第四章 模板领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板n 什么是模板？模板（Template），是根据参数类型生成函数和类的机制（有时称为“参数决定类型”），通过使用模板，可以只设计一个类来处理多种类型的数据，而不必为每一种类型分别创建类。Page 63领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板n 案例分析针对int、long、char三种类型创建函数来返回两个参数中较小的一个，如果不使用template，必须要编写一系列如下的函数：然而，使用template，可以减少重复部分，形成一个函数：Page 64领先源自专业领先源自

33、专业 知识提升价值知识提升价值第四章 模板n 模板的优点模板具有以下几个优势：Page 65领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板n 应用场景模板经常被用来实现如下功能： 创建一个类型安全的集合类（例如，堆栈）用来处理各种类型的数据； 为函数添加额外的类型检查以避免获得空指针； 合并操作符重载组来修改类型行为（例如智能指针）； 实际上，大多数以上应用可以不用模板实现。Page 66领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板n 模板的应用模板通常有两种使用方式，也就是函数模板和类模板。下面，我们就针对函数模板和类模板的使用进行学习。Page 67函数模板类模板领先源自专业领先源自专业 知识提升价值知识提升价值第四章 模板n 函数模板 概念使用函数模板，你可以指定一组基于相同代码但是处理不同类型或类的函数。 定义模板关键自字为template，定义如图所示：这段代码定义了一个函数家族来交换函数的参数值。从这个函数模板你可以产生一系列函数，不仅可以交换int、long，而且可以交换用户定义类型。同样，前面案例中