图的数据结构设计.pptx

图算法及其在通信网中的应用,虞红芳 教授 博导,Part 04: 图的数据结构设计,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的最小距离（跳数）。 可通过邻接矩阵自乘得到。,Kirchhoff matrix 邻接矩阵的对角线上填写节点的度数。,每个节点都拥有一个链表，记录与之邻接的其它节点。,2013年春季,5 / 77,图的存储与表达,4,图的表达方法概述,1,2,3,5,邻接矩阵,邻接链表,关联链表,分析与讨论,2013年春季,6 / 77,Adjacency Matrix,有向图,无向图,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,Adjacency List,有关邻接点的信息,指向下一个邻接点的指针,2013年春季,10 / 77,邻接链表分析,2013年春季,11 / 77,图的存储与表达,4,图的表达方法概述,1,2,3,5,邻接矩阵,邻接链表,关联链表,分析与讨论,2013年春季,12 / 77,Incidence List,关联点的信息,指向下一个关联点的指针,同样需要链表,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,面向对象简史,Early 1970s,Early 1980s,Early 1990s,SIMULA & Alan Kays vision Xerox Parc & Dynabook,Bjorn Stroustrup: Integrating OOP into C. Most successful.,James Gosling group: a simpler version of C+ for VOD. Redesigned for Internet. Inefficiency,Smalltalk,来源,效率,面向对象编程的概念来源于对真实世界进行模拟这一愿望。,实现这个愿望的代价是代码的效率。C+的成功部分来源于它在这二者之间实现了折中。,C+,Java,2013年春季,18 / 77,面向对象与类,面向对象简史,1,2,3,4,对象与类,C+中的类,CEdge: 第一个类,2013年春季,19 / 77,对象与类,Object-oriented programming is first and foremost about objects.,2013年春季,类与对象,20 / 77,2013年春季,21 / 77,面向对象与类,面向对象简史,1,2,3,4,对象与类,C+中的类,CEdge: 第一个类,2013年春季,22 / 77,从一个简单的例子开始,class date private: int m_day, m_month, m_year; public: date(); date(); date(date,“日期”类的定义,类定义的语法,成员变量,成员函数,这个类所定义的对象是什么？,这个对象的接口是什么？包括哪些属性？,2013年春季,23 / 77,C+中的类,再次强调：这里涉及到的C+只是很少的一部分内容。仅就我们要用到的一些基本概念作一简单介绍。但求快速，不求全面。,重载(Overloading),C+中的类,2013年春季,24 / 77,引用(Reference),int i = 10; int,int i = 10; int* pi = ,2013年春季,25 / 77,引用(Reference),Passing object void foo(X b) /cant change b; X x; foo(x),Pass through pointer void foo(X* p) /can change *p X x; foo(,Pass through reference void foo(X,2013年春季,26 / 77,C+中的类,再次强调：这里涉及到的C+只是很少的一部分内容。仅就我们要用到的一些基本概念作一简单介绍。但求快速，不求全面。,重载(Overloading),C+中的类,2013年春季,27 / 77,访问控制,date d; int day; /. d.m_day = day; / illegal,date d; int day; /. some operations day = d.get_day() / legal,对象实例的声明和访问方法,User code relies on class interface need not change when implementation changed.,2013年春季,28 / 77,C+中的类,再次强调：这里涉及到的C+只是很少的一部分内容。仅就我们要用到的一些基本概念作一简单介绍。但求快速，不求全面。,重载(Overloading),C+中的类,2013年春季,29 / 77,用途,2013年春季,30 / 77,声明(Declaration),class date private: int m_day, m_month, m_year; public: date( int d, int m, int y); date(); date(date,Each of these functions must be defined some where. If you forget to do so, the compiler will generate one for you. Which have no guarantee to work correctly.,/ constructor,/ destructor,/ copy constructor,2013年春季,31 / 77,定义(Definition),date:date(int d, int m, int y): 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() date d(1, 1, 2000); date d1 = d; date* pd = new date(1,1,2000); /. delete pd; ,/ constructor d,/ copy constructor d1,/ constructor pd,/ destructor *pd,/ destructor d, d1,Destructor of object on free store/heap( created by “new”), must be explicitly called( through “delete”),Object created on stack will have their destructor implicitly called. When they goes out of scope.,2013年春季,33 / 77,缺省构造函数,struct Tables int i; int vi10; CTable t1; ; Tables tt;,/ default constructor called here. If CTable have a default constructor, it will be called implicitly. But as i and vi10 are not of class type, they are not initialized by default constructor.,Some members (such as Reference) must be initialized by constructor. And such members must in the initializer list.,2013年春季,34 / 77,关于构造/析构函数的忠告,2013年春季,35 / 77,C+中的类,再次强调：这里涉及到的C+只是很少的一部分内容。仅就我们要用到的一些基本概念作一简单介绍。但求快速，不求全面。,重载(Overloading),C+中的类,2013年春季,36 / 77,函数重载,class date private: int m_day, m_month, m_year; public: date(int d, int m, int y); date(int d, int m); date(const char*); date(); date(date,Different ways of constructing,2013年春季,37 / 77,缺省参数,class date private: int m_day, m_month, m_year; public: date(int d = 1, int m = 1, int y = 2000); date(); date(date,如果仅仅是希望提供多种构造对象的方法的话，缺省参数也是一个选择。,但是，请记住：函数重载不仅用于这个目的。任何场合下，只要希望用同一个函数名来做不同的事情，函数重载都可以实现。,2013年春季,38 / 77,运算符重载,X + Y * Z Is clearer to us than Multiple Y by Z and add the result to X,class complex; complex a, b; complex sum = a + b; complex mul = a * b;,class complex private: double re, im; public: /. complex operator+(complex,complex complex:operator+(complex ,2013年春季,39 / 77,Initiation vs. Assignment,void h() X x1; X x2 = x1; / copy initialization X x3; x3 = x2; / copy assignment ,class String private: char* str; /. public: /. String(String,String s1(/*/); String s2 = s1; String s3(/*/); s3 = s2;,Copying initialization invokes copy constructor Copy assignment invokes operator=.,We have to delete “str” before assignment.,2013年春季,40 / 77,面向对象与类,面向对象简史,1,2,3,4,对象与类,C+中的类,CEdge: 第一个类,2013年春季,41 / 77,起点(head) 终点(tail) 权重(weight) 容量(capacity),运算符重载 其它算法,全参数 部分参数 拷贝构造,直接访问私有成员（属性）的各种接口函数,CEdge设计,2013年春季,42 / 77,CEdge类,class CEdge private: int head, tail; int weight, capacity; public: CEdge(int a, int b, int c, int d); CEdge(int a, int b, int c); CEdge(CEdge ,return weight;,return capacity;,return tail;,return head;, head = a; tail = b; weight = c; capacity = d; , head = x.head; tail = x.tail; weight = x.weight; capacity = x.capacity; , if(weight x.weight) return TRUE; else return FALSE; ,2013年春季,43 / 77,图的数据结构设计,3,标准模板库与容器,我们已经有了CEdge类，现在的难题是，如何有效地表达图。记得吗？我们的第二个困难是：链表太难维护了。,2013年春季,44 / 77,标准模板库与容器,STL简史,1,2,3,模板的概念,STL中的容器,2013年春季,45 / 77,STL简史,A journey to STL,2013年春季,46 / 77,标准模板库与容器,STL简史,1,2,3,模板的概念,STL中的容器,2013年春季,47 / 77,函数模板,int max(int x, int y) if (y x) return x; return y; ,float max(float x, float y) if (y x) return x; return y; ,void main() cout max(3,7) endl; cout max(3.0,7.0) endl; ,template T ,void main() cout (3,7.0) endl; ,2013年春季,48 / 77,类模板,STL中提供了一种称为list的模板，它是用来实现双向链表的。,list x;,list y;,list z;,这种可以装任何类型的类模板就称为“container”。,2013年春季,49 / 77,标准模板库与容器,STL简史,1,2,3,模板的概念,STL中的容器,2013年春季,50 / 77,容器类型,vector,list,map / multimap,Dynamic array; Random access; Inserting/deleting is linear time.,Double-linked list; Opposite performance from vector.,A key is associated to each value; Sorted; Self-balancing binary search tree.,Containers In STL,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年春季,讨论容器的选择,不同容器提供不同的复杂度平衡，应权衡使用。 vector 是序列式容器，作为缺省使用。 List应当用于频繁在序列中部进行插入和删除操作的情况。 仅仅处于可动态改变大小的原因，应选择vector 需要在容器中任意位置插入新元素的能力吗？ 如果是，你需要的是顺序容器，关联容器没有这种功能。,72 / 77,2013年春季,73 / 77,图的数据结构设计,有了STL中提供的容器，我们总算可以方便地构造一个图的数据结构了。,2013年春季,74 / 77,顶点数目 边数目 边的列表,将来的任务,给定文件 给定边的列表 拷贝构造,直接访问私有成员（属性）的各种接口函数,CGraph设计,2013年春季,75 / 77,CGraph类,class CGraph private: int numVertex; int numEdge; list IncidentList; public: CGraph(char* inputFile); CGraph(list li