04-图的数据结构设计ppt课件.ppt

图算法及其在通信网中的应用 虞红芳教授博导 Part04 图的数据结构设计 1 2013年春季 2 77 图的数据结构设计 1 2 3 图的存储与表达 面向对象与类 标准模板库与容器 正如前面提到的 算法与数据结构关系密切 在深入探索各类图算法之前 有必要讨论一下图的数据结构 即图在计算机中是如何存储的 以及为什么要这样存储 3 77 图的存储与表达 4 图的表达方法概述 1 2 3 5 邻接矩阵 邻接链表 关联链表 分析与讨论 2013年春季 4 77 图的表达方法 每条边都拥有一个链表 记录与之关联的节点 n行m列矩阵i行j列为1 表示第i个节点与第j条边关联 n行n列矩阵i行j列为1 表示节点i与节点j邻接 n行n列矩阵i行j列的元素值表示节点i到j的最小距离 跳数 可通过邻接矩阵得到 Kirchhoffmatrix邻接矩阵的对角线上填写节点的度数 每个节点都拥有一个链表 记录与之邻接的其它节点 2013年春季 5 77 图的存储与表达 4 图的表达方法概述 1 2 3 5 邻接矩阵 邻接链表 关联链表 分析与讨论 2013年春季 6 77 AdjacencyMatrix 有向图 无向图 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 2013年春季 7 77 邻接矩阵分析 2013年春季 8 77 图的存储与表达 4 图的表达方法概述 1 2 3 5 邻接矩阵 邻接链表 关联链表 分析与讨论 2013年春季 9 77 AdjacencyList 有关邻接点的信息 指向下一个邻接点的指针 2013年春季 10 77 邻接链表分析 2013年春季 11 77 图的存储与表达 4 图的表达方法概述 1 2 3 5 邻接矩阵 邻接链表 关联链表 分析与讨论 2013年春季 12 77 IncidenceList 关联点的信息 指向下一个关联点的指针 同样需要链表 2013年春季 13 77 图的存储与表达 4 图的表达方法概述 1 2 3 5 邻接矩阵 邻接链表 关联链表 分析与讨论 2013年春季 14 77 分析与讨论 2013年春季 15 77 图的数据结构设计 2 3 面向对象与类 标准模板库与容器 请记住 这里仅就C 中我们要用到的一些特性进行简要讨论 对于像继承 多态等许多关键特性都不作介绍 2013年春季 16 77 面向对象与类 面向对象简史 1 2 3 4 对象与类 C 中的类 CEdge 第一个类 2013年春季 17 77 面向对象简史 Early1970s Early1980s Early1990s SIMULA AlanKay svisionXeroxParc Dynabook BjornStroustrup IntegratingOOPintoC Mostsuccessful JamesGosling group asimplerversionofC forVOD RedesignedforInternet Inefficiency Smalltalk 来源 效率 面向对象编程的概念来源于对真实世界进行模拟这一愿望 实现这个愿望的代价是代码的效率 C 的成功部分来源于它在这二者之间实现了折中 C Java 2013年春季 18 77 面向对象与类 面向对象简史 1 2 3 4 对象与类 C 中的类 CEdge 第一个类 2013年春季 19 77 对象与类 Object orientedprogrammingisfirstandforemostaboutobjects 2013年春季 类与对象 20 77 2013年春季 21 77 面向对象与类 面向对象简史 1 2 3 4 对象与类 C 中的类 CEdge 第一个类 2013年春季 22 77 从一个简单的例子开始 classdate private intm day m month m year public date date date date 日期 类的定义 类定义的语法 成员变量 成员函数 这个类所定义的对象是什么 这个类的接口是什么 包括哪些属性 2013年春季 23 77 C 中的类 再次强调 这里涉及到的C 只是很少的一部分内容 仅就我们要用到的一些基本概念作一简单介绍 但求快速 不求全面 重载 Overloading C 中的类 2013年春季 24 77 引用 Reference inti 10 int inti 10 int pi 2013年春季 25 77 引用 Reference Passingobjectvoidfoo Xb can tchangeb Xx foo x Passthroughpointervoidfoo X p canchange p Xx foo Passthroughreferencevoidfoo X 2013年春季 26 77 C 中的类 再次强调 这里涉及到的C 只是很少的一部分内容 仅就我们要用到的一些基本概念作一简单介绍 但求快速 不求全面 重载 Overloading C 中的类 2013年春季 27 77 访问控制 dated intday d m day day illegal dated intday someoperationsday d get day legal 对象实例的定义和访问方法 Usercodereliesonclassinterfaceneednotchangewhenimplementationchanged 2013年春季 28 77 C 中的类 再次强调 这里涉及到的C 只是很少的一部分内容 仅就我们要用到的一些基本概念作一简单介绍 但求快速 不求全面 重载 Overloading C 中的类 2013年春季 29 77 用途 2013年春季 30 77 声明 Declaration classdate private intm day m month m year public date intd intm inty date date date Eachofthesefunctionsmustbedefinedsomewhere Ifyouforgettodoso thecompilerwillgenerateoneforyou Whichhavenoguaranteetoworkcorrectly constructor destructor copyconstructor 2013年春季 31 77 定义 Definition date date intd intm inty m month m m day d m year y date date date date date d m day d m day m month d m month m year d m year 2013年春季 32 77 使用 Usage foo dated 1 1 2000 dated1 d date pd newdate 1 1 2000 deletepd constructord copyconstructord1 constructorpd destructor pd destructord d1 Destructorofobjectonfreestore heap createdby new mustbeexplicitlycalled through delete Objectcreatedonstackwillhavetheirdestructorimplicitlycalled Whentheygoesoutofscope 2013年春季 33 77 缺省构造函数 structTables inti intvi 10 CTablet1 Tablestt defaultconstructorcalledhere IfCTablehaveadefaultconstructor itwillbecalledimplicitly Butasiandvi 10 arenotofclasstype theyarenotinitializedbydefaultconstructor Somemembers suchasReference mustbeinitializedbyconstructor Andsuchmembersmustintheinitializerlist 2013年春季 34 77 关于构造 析构函数的忠告 2013年春季 35 77 C 中的类 再次强调 这里涉及到的C 只是很少的一部分内容 仅就我们要用到的一些基本概念作一简单介绍 但求快速 不求全面 重载 Overloading C 中的类 2013年春季 36 77 函数重载 classdate private intm day m month m year public date intd intm inty date intd intm date constchar date date date Differentwaysofconstructing 2013年春季 37 77 缺省参数 classdate private intm day m month m year public date intd 1 intm 1 inty 2000 date date date 如果仅仅是希望提供多种构造对象的方法的话 缺省参数也是一个选择 但是 请记住 函数重载不仅用于这个目的 任何场合下 只要希望用同一个函数名来做不同的事情 函数重载都可以实现 2013年春季 38 77 运算符重载 X Y ZIsclearertousthanMultipleYbyZandaddtheresulttoX classcomplex complexa b complexsum a b complexmul a b classcomplex private doublere im public complexoperator complex complexcomplex operator complex 2013年春季 39 77 Initiationvs Assignment voidh Xx1 Xx2 x1 copyinitializationXx3 x3 x2 copyassignment classString private char str public String String Strings1 Strings2 s1 Strings3 s3 s2 CopyinginitializationinvokescopyconstructorCopyassignmentinvokesoperator Wehavetodelete str beforeassignment 2013年春季 40 77 面向对象与类 面向对象简史 1 2 3 4 对象与类 C 中的类 CEdge 第一个类 2013年春季 41 77 起点 head 终点 tail 权重 weight 容量 capacity 运算符重载其它算法 全参数部分参数拷贝构造 直接访问私有成员 属性 的各种接口函数 CEdge设计 2013年春季 42 77 CEdge类 classCEdge private inthead tail intweight capacity public CEdge inta intb intc intd CEdge inta intb intc CEdge CEdge returnweight returncapacity returntail returnhead head a tail b weight c capacity d head x head tail x tail weight x weight capacity x capacity if weight x weight returnTRUE elsereturnFALSE 2013年春季 43 77 图的数据结构设计 3 标准模板库与容器 我们已经有了CEdge类 现在的难题是 如何有效地表达图 记得吗 我们的第二个困难是 链表太难维护了 2013年春季 44 77 标准模板库与容器 STL简史 1 2 3 模板的概念 STL中的容器 2013年春季 45 77 STL简史 AjourneytoSTL 2013年春季 46 77 标准模板库与容器 STL简史 1 2 3 模板的概念 STL中的容器 2013年春季 47 77 函数模板 intmax intx inty if y x returnx returny floatmax floatx floaty if y x returnx returny voidmain cout max 3 7 endl cout max 3 0 7 0 endl templateT voidmain cout 3 7 0 endl 2013年春季 48 77 类模板 STL中提供了一种称为list的模板 它是用来实现双向链表的 listx listy listz 这种可以装任何类型的类模板就称为 container 2013年春季 49 77 标准模板库与容器 STL简史 1 2 3 模板的概念 STL中的容器 2013年春季 50 77 容器类型 vector list map multimap Dynamicarray Randomaccess Inserting deletingislineartime Double linkedlist Oppositeperformancefromvector Akeyisassociatedtoeachvalue Sorted Self balancingbinarysearchtree ContainersInSTL 2013年春季 51 77 STL中的容器 这部分内容主要是关于三种主要容器的使用方法和调用接口 不涉及其设计方法 vector 向量容器 map 映射容器 list 列表容器 三种容器 2013年春季 52 77 vector 向量容器 2013年春季 53 77 vector 遍历 访问 必须使用 关于namespace 迭代器的声明和使用 v size 迭代器 就像指针一样 v begin 和v end 2013年春季 54 77 vector 任意位置插入 注意迭代器加法的含义 2013年春季 55 77 vector 删除 delete的作用 erase的作用 clear的作用 2013年春季 56 77 vector 其他常用函数 2013年春季 57 77 STL中的容器 这部分内容主要是关于三种主要容器的使用方法和调用接口 不涉及其设计方法 vector 向量容器 map 映射容器 list 列表容器 三种容器 2013年春季 58 77 list 列表容器 2013年春季 59 77 list 遍历 访问 必须使用 注意迭代器的创建和使用方法 同样有begin 和end 2013年春季 60 77 list 插入 insert 要指明插入位置 push front 插入到最前面 2013年春季 61 77 list 删除 2013年春季 62 77 list 排序 sort 永远按升序排序 2013年春季 63 77 STL中的容器 这部分内容主要是关于三种主要容器的使用方法和调用接口 不涉及其设计方法 vector 向量容器 map 映射容器 list 列表容器 三种容器 2013年春季 64 77 map 映射容器 缺省情况下都是按升序对键值排序 除非指定为greater 注意 map的每个元素都是由两个对象组成的 一个是键值 key 另一个是值 value 2013年春季 65 77 map 插入 插入的元素必须是pair Insert函数返回的也是一个pair 2013年春季 66 77 map 另一种插入方法 由于map中不允许相同键值的元素 因此键值可以作为广义的数组下标来使用 显然 multimap不能这样 2013年春季 67 77 map 删除 2013年春季 68 77 map 遍历 2013年春季 69 77 map 搜索 注意find函数的返回值的含义 2013年春季 70 77 multimap 搜索 由于multimap中可以包含多个相同键值的元素 所以find函数返回的是第一个找到的位置 2013年春季 71 77 map 其他常用函数 2013年春季 讨论 容器的选择 需要大量增加新元素查找速度需要在容器中任意位置插入新元素元素排序 72 77 2013年春季 73 77 图的数据结构设计 有了STL中提供的容器 我们总算可以方便地构造一个图的数据结构了 2013年春季 74 77 顶点数目边数目边的列表 将来的任务 给定文件给定边的列表拷贝构造 直接访问私有成员 属性 的各种接口函数 CGraph设计 2013年春季 75 77 CGraph类 classCGraph private intnumVertex intnumEdge listIncidentList public CGraph char inputFile CGraph listlistEdge CG