(mooc)第11章数据结构与算法

1、第第11章章 数据结构与算法西安交通大学计教中心仇国巍数据结构数据结构n要解决实际问题，首先对问题进行抽象，转化为适合编程处理的数据形式。n经过研究，人们总结出了少数常见的数据组织形式，并研究其存储方式、算法等等。这门学问就是数据结构n标准模板库(STL)将数据结构中常见结构、算法抽象为一种通用的形式。它的出现使得代码的可重用性、健壮性得到大幅提高。数据结构基本概念n数据处理的基本单位在就称为数据元素数据元素。 例如，在一张员工信息表中的个人信息。n线性结构、树形结构和图状结构 算法的某些基本概念 n在数据结构的每种结构中，都有一些通用的算法，他们在解决实际问题时作用很大n算法是指解题方案的准

2、确而完整的描述，是一系列解决问题的清晰指令。n具有五个主要特征：有穷性，确定性，可行性，输入，输出。 时间复杂度时间复杂度n表示一个算法对时间的消耗情况n时间复杂度的分析主要是考察关键指令重复执行的次数。n 例如下面是O(n2)复杂度复杂度for(i=1; in; i+) for(j=1; jn; j+) cij = aij + bij; 类似的还有空间复杂度线性数据结构： 顺序表元素按照逻辑顺序依次存放在一组连续的存储单元中主要算法是插入元素、删除元素以及查找元素线性数据结构：线性链表n形式有：单链表、双向链表、单循环链表以及双向循环链表n单链表用一组地址任意的存储单元存放线性表中的元素。逻

3、辑上相邻的元素其物理位置不一定相邻，为了建立元素间的逻辑关系，需要在线性表的每个元素中附加其后继元素的地址信息。单链表结构 data next 单链表的结点 单链表结构删除、插入堆栈队列 A B C front rear front rear (a) A 、B 、C 入队列 (b) 队列假溢出 图 11-10 一般队列示意图 循环队列 0 1 2 3 4 5 6 7 front rear 0 1 2 3 4 5 6 7 front rear A B C D 0 1 2 3 4 5 6 7 front rear A B C F G E D 非线性数据结构：树，二叉树A B C D E 排序二叉树

4、图的基本概念n在图中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 (a)无向图 (b)有向图 (c)网络 0 1 3 2 5 2 8 1 3 0 1 2 3 4 1 0 2 3 4 图的遍历 A D F C G B E 函数模板函数模板是用类型做参数，设计出的通用的函数。其定义形式为：template 函数返回类型 函数名(函数参数表)/函数模板定义其中template表示定义的是模板，里是模板的类型参数，可以是一个或多个。例如：template T Max(T a,T b) return ab? a:b; 在这个max函数里，返回值和参数都是类型T。使用时直接采用下面的

5、语句即可。int iRet = Max(i1,i2); /调用Max(int , int)char cRet=Max(c1,c2); /调用Max(char , char)类模板template class 类模板名/类模板定义简化的顺序表。简化的顺序表。template class LinearList T data100; /最大元素为100个 public: bool IsEmpty(); /判断表是否为空 int Length(); /求表长度 int Search(T x); /查找 bool Insert(int i, T x); /插入 bool Delete(int i); /

6、删除 protected: int n; /线性表的长度;使用：使用：LinearList aList;标准模板库n有三类：容器(container)、算法(algorithm)、和迭代器（iterator），几乎所有的代码都采用了类模板和函数模版的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。容器容器n序列型容器：该类容器中的元素不会自动排序。这类容器主要有vector（向量）、deque（双向队列）、list（线性表）n关联型容器：关联型容器中的元素一定是按照某种特征有序排列的。这类容器主要有四个：map(映射)、set(集合)等n容器适配器：是对前面提到的某些容器（

7、如vector）进行再包装，使其变为另一种容器。典型的有栈(stack)、队列(queue)等。算法n由一大堆模版函数组成的，实现了大量通用算法，用于操控各种容器。n其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。n比如：find用于在容器中查找等于某个特定值的元素，for_each用于将某个函数应用到容器中的各个元素上，sort用于对容器中的元素排序。迭代器n迭代器提供对一个容器中的对象的访问方法n迭代器就象是容器中指向对象的指针。事实上，C+的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此不能认为他们一定具有地址值。例如，一个数组索引，也可

8、认为是一种迭代器。迭代器有五种类型迭代器有五种类型：Input iterators提供对数据的只读访问，只能向前移动提供对数据的只读访问，只能向前移动Output iterators 提供对数据的只写访问，只能向前移动提供对数据的只写访问，只能向前移动Forward iterators提供读写操作，并只能向前移动提供读写操作，并只能向前移动Bidirectional iterators 提供读写操作，能向前和向后移动提供读写操作，能向前和向后移动Random access iterators 提供读写操作，并能在数据中提供读写操作，并能在数据中随机移动随机移动应用举例: vectorn(1)

9、不指定元素个数nvector v; n(2) 指定容器大小nvector v(10); /元素下标09，初始值0n(3) 指定容器大小及初始值nvector v(10, 3.1); /10个元素初值都是3.1【例11-1】用向量容器装入整数110，用accumulate算法统计和#include#include /使用vector需要#include /使用算法accumulate需要using namespace std;int main() vector v; /定义向量v int i; for(i=0;i10;i+) v.push_back(i); /在尾部加入一个数据 vector:i

10、terator it;/定义迭代器（续） for(it=v.begin(); it!=v.end(); it+) cout*it ; /利用迭代器输出数据coutendl; /调用accumulate算法coutaccumulate(v.begin(),v.end(),0)endl;return 0;【运行结果】0 1 2 3 4 5 6 7 8 945【程序说明】nvector容器有很多方法，本程序用到以下几个方法：npush_back(elem) 在尾部加入一个数据。nbegin() 返回首元素位置的迭代器。nend() 返回最后一个元素的下一元素位置的迭代器。【例11-2】向vector

11、中插入元素#include#include /使用vector需要using namespace std;int main()vector v(3); /定义向量v v0=1;/像数组一样使用vectorv1=3;v2=4;v.insert(v.begin(),0); /将 0 插入到最前面v.insert(v.begin()+2,2);/在第二个元素前插入v.insert(v.end(),5); /在末尾插入vector:iterator it; /定义迭代器变量for(it=v.begin();it!=v.end();it+) cout*it ; return 0;【运行结果】0 1 2

12、3 4 5 vector的，insert有三种形式：insert(pos,elem) 在pos位置插入一个elem拷贝insert(pos,n,elem)在pos位置插入n个elem数据insert(pos,beg,end) 在pos位置插入在beg,end)区间的数据【例11-4】测试vector中的reverse（反序）和sort（排序）算法#include#include /使用vector需要#include /使用sort, reverse算法需要using namespace std;int main()vector v(10);/定义向量v int i; for(i=0;i10;

13、i+) vi=i;/赋值为0,1,2,.,9for(i=0;i10;i+) coutvi ; coutendl;reverse(v.begin()+2,v.end();vector:iterator it; for(it=v.begin();it!=v.end();it+) cout*it ; coutendl;sort(v.begin(),v.end();for(it=v.begin();it!=v.end();it+) cout*it ; return 0;【运行结果】0 1 2 3 4 5 6 7 8 90 1 9 8 7 6 5 4 3 20 1 2 3 4 5 6 7 8 9stac

14、k（栈）n加入下列语句：n#includen栈的常用算法有：npush(elem)将元素elem入栈npop()栈顶元素出栈ntop()求栈顶元素nempty()判断栈是否空nsize()求栈内元素个数测试stack容器中的各种算法#include#include using namespace std;int main() stack s;/定义栈 ss.push(1); s.push(2); s.push(3); s.push(9);/入栈过程cout栈顶元素：s.top()endl; /读栈顶元素cout元素数量：s.size()endl; /返回元素个数cout出栈过程：;while(

15、s.empty()!=true)/栈非空couts.top() ; /读栈顶元素s.pop();/出栈，删除栈顶元素return 0;【运行结果】【运行结果】栈顶元素：栈顶元素：9元素数量：元素数量：4出栈过程：出栈过程：9 3 2 1queue（队列）（队列）n加入下列语句：n#includen队列的常用算法有：npush()入队npop()出队nfront()读取队首元素nback()读取队尾元素nempty() 判断队列是否空nsize()求队列长度常见算法策略常见算法策略：枚举法：枚举法 n(1)建立问题的数学模型，确定问题的可能解的集合（可能解的空间）。n(2)确定合理的筛选条件，用

16、来选出问题的解。n(3)确定搜索策略，逐一枚举可能解集合中的元素，验证是否是问题的解。设解的个数设解的个数n初始为初始为0; 循环循环(枚举每一可能解枚举每一可能解)：若若( 该解法满足约束该解法满足约束 ) ：输出这个解输出这个解; 解的数量解的数量n加加1;【例11-6】八皇后问题在88的国际象棋棋盘上放置八个皇后，求出满足下列条件的摆放方法数量：使得任意两个皇后都不在同一行，或同一列或同一对角线上。如图所示就是八皇后问题的一个正确摆法（即一个解）。算法描述：算法描述：r0;/存放解的数目循环循环(令y1从 1 到 8)： /放置第1行棋子 循环循环(令y2从 1 到 8)： /放置第2行

17、棋子 循环循环(令y3从 1 到 8)： /放置第3行棋子 循环循环(令y4从 1 到 8)： /放置第4行棋子 循环循环(令y5从 1 到 8)： /放置第5行棋子 循环循环(令y6从 1 到 8)： /放置第6行棋子 循环循环(令y7从1 到 8)： /放置第7行棋子 循环循环(令y8从1 到 8)：/放置第8行棋子 /判断有没有两个棋子在同列或同一对角线上 flag1;/先假设本方案是解 循环循环( 令i 从1 到 8 ) ： 循环循环( 令j 从 i+1 到 8 ) ：若( yiyj 或 |i-j|=|yi-yj| ) : flag0; 若若(flag=1) 则：r+; /解的数量加1

18、输出解的数量r ;分治法分治法 n分治法解题的一般步骤如下： （1）分解：将要解决的问题划分成若干规模较小、彼此独立的同类问题；（2）求解：当子问题划分得足够小时，用较简单的方法解决；（3）合并：按原问题的要求，将子问题的解逐步合并构成原问题的解。【例11-7】二分查找n如果数组L的元素按照关键字的值递增存放，如何进行查找？n比较key和L中任意一个元素Li，若key=Li，则key在L中的位置就是i；如果keyLi，同理只要在Li的后面查找即可。 如果对给定有序数列 5，6，11，17，21，23，28，30，32，40进行二分查找，查找关键字值为30的数据元素。则查找过程如下：int Bi

19、nSearch( int *L, int length, int key ) int low, high, mid; low = 0; high = length-1; /设置查找区间初值while (low = high) mid = (low + high)/2;if(key=Lmid) return mid+1; /查找成功else if( keyn)： /找到了一个解找到了一个解 处理和输出结果处理和输出结果; 否则：否则： 循环循环( 每个每个aSi )： xi a; 若若( (x1，x2，xi)满足约束条件满足约束条件 ): try(i+1); /尝试第尝试第i+1次决策次决策n其

20、中：其中：i是递归深度；是递归深度；n是解空间树的的高度；是解空间树的的高度； 八皇后问题八皇后问题n假定变量假定变量L1、L2、L8表示在棋盘第表示在棋盘第1行至第行至第8行中行中棋子的位置。显然每个变量的取值范围是棋子的位置。显然每个变量的取值范围是18，任一，任一组合（组合（L1、L2、L8）都代表一种摆法）都代表一种摆法 Try(Li的取值的取值) ： 循环循环(试探Li为18) ： 若若Li当前取值与L1L i-1有冲突，则继续试探Li下一个值 否则否则 Try(Li+1的取值的取值)在上面的框架中只考虑了不断递归前进，没有考虑当在上面的框架中只考虑了不断递归前进，没有考虑当8行棋子

21、行棋子全确定后输出解或计算解的数量的问题。因此需要循环试探前加全确定后输出解或计算解的数量的问题。因此需要循环试探前加上下面一句判断：上下面一句判断： 若若 L1L 8全部确定，则输出解或计算解的数量全部确定，则输出解或计算解的数量tryit(i)：/ 尝试在第i行放棋子若若( 行号i8 ): 产生新解(由L1L8表示), 解的个数加1, 返回；循环循环(令第i行棋子位置 j 从 1 到 8): /逐行判定棋子i与前面棋子冲突否循环循环(令行号 k 从 1 到 i-1): 若若( Lk=j 或 |k-i|=|Lk-j|): 则提前终止本层循环;若若( k=i )： /当前棋子与其他无冲突 Li

22、j; /放置棋子i到第j列 tryit(i+1); /尝试放置下一行皇后算法描述：算法描述：迷宫求解问题迷宫求解问题n有一个包含有一个包含mn个方格的长方形迷宫，其中有个方格的长方形迷宫，其中有些方格为道路，有些方格为墙壁。要求从某个些方格为道路，有些方格为墙壁。要求从某个位置位置A出发，每次可走动一格，且出发，每次可走动一格，且每次移动都每次移动都不可出边界或碰墙不可出边界或碰墙。请找到一条从。请找到一条从A走到走到B的的不不包含环路包含环路的通路。的通路。 AB2 0 0 1 0 02 1 0 0 0 02 1 1 1 1 02 2 2 2 2 11 0 1 1 2 2 每前进一步就是一次

23、决策；从每前进一步就是一次决策；从A到到B要经过多少步不确定；要经过多少步不确定； 从一个位置出发最多有从一个位置出发最多有4种决策；约束条件为种决策；约束条件为上面的红色字上面的红色字体描述体描述 算法用二维数组算法用二维数组mase1.m1.n存储迷宫，其中用存储迷宫，其中用0代表代表可行位置，用可行位置，用1代表墙壁。如果将某位置纳入路径时，设此代表墙壁。如果将某位置纳入路径时，设此位置值为位置值为2；若经过试探，通过此位置无法到达目的地，则；若经过试探，通过此位置无法到达目的地，则将此位置还原为将此位置还原为0。/变量ok为1表示已经找到了A到B的路径，ok为0表示没找到路径ok0;

24、/尚未找到路径search(x, y)： /试探位置（x,y）masexy2; /标记（x,y）为已经过 若若(x，y)为目的地)：ok1; 否则：否则： 若若(ok=0 且 (x,y+1)既未超界也未经过)： search(x,y+1); 若若(ok=0 且 (x+1,y)既未超界也未经过)： search(x+1,y); 若若(ok=0 且 (x, y-1)既未超界也未经过)： search(x,y-1); 若若(ok=0 且 (x-1, y)既未超界也未经过)： search(x-1,y); 若若(经过(x,y)无路可通,即ok仍为0): /则该点还原为0， masexy0; /从(x,y)回退，标记它为未经过贪心算法n贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。n贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。n例如在买东西时，售货员就常常计算最少需要找多少张零钱，以便简化工作流程。比如买东西需要48.5元，交给售货员100元整，按照现在的货币体系，则售货员