设为首页 加入收藏

TOP

[C++]LeetCode: 129 Clone Graph (图的深拷贝 BFS && DFS)(一)
2015-07-20 17:23:18 来源: 作者: 【 】 浏览:7
Tags:LeetCode: 129 Clone Graph 拷贝 BFS & DFS

题目:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

    Visually, the graph looks like the following:

           1
          / \
         /   \
        0 --- 2
             / \
             \_/

    背景知识:

    1. 深拷贝和浅拷贝

    (1) 深拷贝是指源对象与拷贝对象互相独立,其中任何一个对象的改动都不会对另外一个对象造成影响。举个例子,一个人名叫张三,后来用他克隆(假设法律允许)了另外一个人,叫李四,不管是张三缺胳膊少腿还是李四缺胳膊少腿都不会影响另外一个人。比较典型的就是Value(值)对象,如预定义类型Int32,Double,以及结构(struct),枚举(Enum)等。

    考虑以下写法

    int source = int.MaxValue;//(1)初始化源对象为整数的最大值2,147,483,647

    int dest = source;//(2)赋值,内部执行深拷贝

    dest = 1024;//(3)对拷贝对象进行赋值

    source = 2048;//(4)对源对象进行赋值

    首先(2)中将source赋给dest,执行了深拷贝动作,其时dest和source的值是一样的,都是int.MaxValue;(3)对dest进行修改,dest值变为1024,由于是深拷贝,因此不会运行source,source仍然是int.MaxValue;(4)对source进行了修改,同样道理,dest仍然是1024,同时int.MaxValue的值也不变,仍然是2,147,483,647;只有source变成了2048。

    (2)浅拷贝是指源对象与拷贝对象共用一份实体,仅仅是引用的变量不同(名称不同)。对其中任何一个对象的改动都会影响另外一个对象。举个例子,一个人一开始叫张三,后来改名叫李四了,可是还是同一个人,不管是张三缺胳膊少腿还是李四缺胳膊少腿,都是这个人倒霉。比较典型的就有Reference(引用)对象,如Class(类)。

    考虑以下写法

    class Point

    {

    public int X;

    public int Y;

    public Point(int x, int y)

    {

    X = x;

    Y = y;

    }

    }

    Point source = new Point(10, 20);

    Point dest = source;

    dest.X = 20;

    由于Point现在是引用对象,因此Point dest=source的赋值动作实际上执行的是浅拷贝,最后的结果应该是source的X字段值也变成了20。即它们引用了同一个对象,仅仅是变量明source和dest不同而已。

    2. 数据结构和结构指针

    (1)数据结构:如果结构的定义包括参数model_name (可选),该参数即成为一个与该结构等价的有效的类型名称。例如:

    struct products {
    char name [30];
    float price;
    };
    products apple;
    products orange, melon;

    我们首先定义了结构模块products,它包含两个域:name 和 price,每一个域是不同的数据类型。然后我们用这个结构类型的名称 (products) 来声明了 3个该类型的对象:apple, orange 和melon。

    在我们声明了确定结构模型的3个对象(apple, orange 和 melon)之后,我们就可以对它们的各个域(field)进行操作,这通过在对象名和域名之间插入符号点(.)来实现。例如,我们可以像使用一般的标准变量一样对下面的元素进行操作:

    apple.name
    apple.price
    orange.name
    orange.price
    melon.name
    melon.price (2)数据结构指针:

    就像其它数据类型一样,结构也可以有指针。其规则同其它基本数据类型一样:指针必须被声明为一个指向结构的指针:

    struct movies_t {
    char title [50];
    int year;
    };
    movies_t amovie;
    movies_t * pmovie;

    这里 amovie 是一个结构类型movies_t 的对象,而pmovie 是一个指向结构类型movies_t 的对象的指针。所以,同基本数据类型一样,以下表达式正确的:

    pmovie = &amovie;

    上面的代码中引入了一个重要的操作符:->。这是一个引用操作符,常与结构或类的指针一起使用,以便引用其中的成员元素,这样就避免使用很多括号。例如,我们用:

    pmovie->title

    来代替:

    (*pmovie).title

    以上两种表达式pmovie->title 和 (*pmovie).title 都是合法的,都表示取指针pmovie 所指向的结构其元素title 的值。我们要清楚将它和以下表达区分开:

    *pmovie.title

    它相当于

    *(pmovie.title)

    表示取结构pmovie 的元素title 作为指针所指向的值,这个表达式在本例中没有意义,因为title本身不是指针类型。

    下表中总结了指针和结构组成的各种可能的组合:

    表达式 描述 等价于
    pmovie.title 结构pmovie 的元素title
    pmovie->title 指针pmovie 所指向的结构其元素title 的值 (*pmovie).title
    *pmovie.title 结构pmovie 的元素title 作为指针所指向的值 *(pmovie.title)

    结构嵌套(Nesting structures)

    结构可以嵌套使用,即一个结构的元素本身又可以是另一个结构类型。例如:

    struct movies_t {
    char title [50];
    int year;
    }

    struct friends_t {
    char name [50];
    char email [50];
    movies_t favourite_movie;
    } charlie, maria;

    friends_t * pfriends = &charlie;

    因此,在有以上声明之后,我们可以使用下面的表达式:

    charlie.name
    maria.favourite_movie.title
    charlie.favourite_movie.year
    pfriends->favourite_movie.year

    (以上最后两个表

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇leetcode_6_ZigZag Conversion 下一篇Go语言实现跳表(SkipList)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·微服务 Spring Boot (2025-12-26 18:20:10)
·如何调整 Redis 内存 (2025-12-26 18:20:07)
·MySQL 数据类型:从 (2025-12-26 18:20:03)
·Linux Shell脚本教程 (2025-12-26 17:51:10)
·Qt教程,Qt5编程入门 (2025-12-26 17:51:07)