C++备忘录模式实践:轻松实现撤销与恢复功能

简介: C++备忘录模式实践:轻松实现撤销与恢复功能

引言(Introduction)

备忘录模式(Memento Pattern)是一种行为型设计模式,它的主要目的是在不违反对象封装性的前提下,捕捉和保存对象的内部状态,以便将来可以将对象恢复到先前的状态。它通常用于实现撤销(Undo)和重做(Redo)操作,同时也适用于保存和恢复应用程序的状态。

备忘录模式通过在三个主要角色之间建立关系来实现这些功能:发起人(Originator)、备忘录(Memento)和管理者(Caretaker)。

  1. 发起人(Originator):负责创建一个备忘录,用于保存其当前状态,同时还负责从备忘录中恢复状态。
  2. 备忘录(Memento):存储发起人的内部状态,但不应该直接暴露给其他对象。备忘录应该保持不变,并且只能由发起人访问和修改。
  3. 管理者(Caretaker):负责管理和维护备忘录对象,但不应该修改或访问备忘录中存储的状态。管理者可以根据需要存储多个备忘录,并在需要时将发起人恢复到相应的状态。

备忘录模式的应用场景包括实现撤销和重做操作、状态存储与恢复等。使用备忘录模式可以简化撤销和重做操作的实现,同时保持代码的可读性和可维护性。

备忘录模式定义及核心概念(Memento Pattern Definition and Core Concepts)

备忘录模式的定义(Definition of Memento pattern)

备忘录模式(Memento Pattern)是一种行为型设计模式,它提供了一种在不破坏对象封装性的前提下捕捉和保存对象的内部状态,以便后续可以将对象恢复到先前的状态。备忘录模式通过将发起人(Originator)的内部状态存储在一个名为备忘录(Memento)的对象中,并由管理者(Caretaker)负责管理和维护备忘录,从而实现撤销和重做操作,以及状态存储与恢复等功能。

备忘录模式的主要角色(Key roles in Memento pattern)

备忘录模式的主要角色(Key roles in Memento pattern)

  1. 发起人(Originator): 发起人是一个具有内部状态的对象,负责创建备忘录以保存其当前状态,并从备忘录中恢复状态。发起人可以创建一个备忘录对象,用于存储其内部状态,同时也可以通过备忘录对象恢复到某个之前的状态。发起人不应该与管理者直接交互,而应该通过备忘录来实现状态的保存和恢复。
  2. 备忘录(Memento): 备忘录是一个用于存储发起人内部状态的对象,它应该保持对发起人状态的封装,不向其他对象暴露发起人的内部状态。备忘录应该保持不变,并且只能由发起人访问和修改。通常,备忘录类设计为嵌套类,以确保只有发起人能够访问和操作备忘录。
  3. 管理者(Caretaker): 管理者负责管理和维护备忘录对象,但不应该修改或访问备忘录中存储的状态。管理者可以根据需要存储多个备忘录,并在需要时将发起人恢复到相应的状态。管理者通常会为发起人提供保存和恢复状态的功能,如撤销(Undo)和重做(Redo)操作。

这三个角色之间的关系使得备忘录模式能够在不破坏对象封装性的前提下实现状态的保存和恢复。这样的设计提高了代码的可读性和可维护性,并降低了发起人与管理者之间的耦合度。

备忘录模式的UML图

备忘录模式的UML图包含以下三个类:

  1. Originator(发起人)
  2. Memento(备忘录)
  3. Caretaker(管理者)

下面是备忘录模式的UML图:

+----------------+        +------------+      +------------+
|   Originator   |<------>|  Memento   |      | Caretaker  |
+----------------+        +------------+      +------------+
|                |        |            |      |            |
| +createMemento()|       |+getState() |      | +addMemento()|
| +restore(memento: Memento)|  |+setState(state: State) | |+getMemento(index: int)|
|                |        |            |      |            |
+----------------+        +------------+      +------------+

在这个UML图中:

  • Originator(发起人)类具有createMemento()方法,用于创建一个备忘录对象以存储其内部状态;restore(memento: Memento)方法用于通过备忘录对象恢复到先前的状态。
  • Memento(备忘录)类具有getState()setState(state: State)方法,用于存储和获取发起人的内部状态。这两个方法通常只能被发起人访问和使用。
  • Caretaker(管理者)类具有addMemento()方法,用于存储备忘录对象;getMemento(index: int)方法用于根据索引获取备忘录对象,以便将发起人恢复到相应的状态。

这个UML图展示了备忘录模式的结构和关键组件。通过这种设计,备忘录模式可以实现在不破坏对象封装性的前提下保存和恢复对象的内部状态。

备忘录模式的使用场景(When to Use Memento Pattern)

撤销操作(Undo functionality)

在许多应用程序中,用户可能希望取消先前执行的操作,将应用程序恢复到以前的状态。例如,在文本编辑器中,用户可能希望撤销键入的字符或删除的文本。在这种情况下,备忘录模式是一种理想的解决方案,它允许在不违反对象封装性的前提下捕捉和保存对象的内部状态。

当使用备忘录模式实现撤销操作时,发起人(Originator)负责创建备忘录以保存其当前状态,并从备忘录中恢复状态。管理者(Caretaker)负责存储备忘录并提供撤销功能。当用户执行撤销操作时,管理者从备忘录中获取先前的状态,并将发起人恢复到该状态。

使用备忘录模式实现撤销操作的优势包括:

  1. 易于实现:备忘录模式提供了一种简单的方法来捕捉和存储对象的状态,从而简化了撤销操作的实现。
  2. 封装性:备忘录模式不会破坏对象的封装性,因为它将状态存储在备忘录对象中,而不是直接访问或修改发起人的内部状态。
  3. 可扩展性:备忘录模式可以轻松地扩展以支持重做操作和其他状态恢复功能。

恢复操作(Redo functionality)

恢复操作(Redo)是在应用程序中允许用户重做先前撤销的操作。这在很多场景中都是有用的,例如文本编辑器、绘图软件或游戏中。在这些情况下,备忘录模式同样可以作为实现重做功能的理想解决方案。

当使用备忘录模式实现重做操作时,管理者(Caretaker)负责存储备忘录并提供重做功能。在执行撤销操作后,管理者将保留一个指向撤销前的备忘录的引用。当用户执行重做操作时,管理者使用该引用将发起人(Originator)恢复到撤销前的状态。

使用备忘录模式实现重做操作的优势包括:

  1. 易于实现:与实现撤销操作类似,备忘录模式提供了一种简单的方法来捕捉和存储对象的状态,从而简化了重做操作的实现。
  2. 封装性:备忘录模式保持了对象的封装性,因为它将状态存储在备忘录对象中,而不是直接访问或修改发起人的内部状态。
  3. 可扩展性:备忘录模式可以轻松地扩展以支持多步撤销和重做操作,以及其他状态恢复功能。

状态存储与恢复(State storage and restoration)

在某些应用程序中,可能需要保存和恢复对象的状态。这种情况下,备忘录模式可以作为一种有效的解决方案。状态存储与恢复功能可以应用于多种场景,如游戏存档、软件设置恢复等。

使用备忘录模式实现状态存储与恢复的优势包括:

  1. 封装性:备忘录模式通过将状态保存在备忘录对象中,而不是直接访问或修改发起人的内部状态,从而保持了对象的封装性。
  2. 易于实现:备忘录模式提供了一种简单的方法来捕捉和存储对象的状态,从而简化了状态存储与恢复功能的实现。
  3. 可扩展性:备忘录模式可以轻松地扩展,以支持跨越多个状态变化的状态存储与恢复功能,同时也适用于不同类型的发起人对象。

当使用备忘录模式实现状态存储与恢复时,发起人(Originator)负责创建备忘录以保存其当前状态,并从备忘录中恢复状态。管理者(Caretaker)负责存储备忘录并提供保存和恢复状态的功能。在需要保存状态时,管理者通过发起人创建一个备忘录对象;在需要恢复状态时,管理者将发起人恢复到相应的备忘录状态。

用C++实现备忘录模式(Implementing Memento Pattern in C++)

代码示例(Code example)

#include <iostream>
#include <string>
#include <vector>
class Memento {
    friend class Originator;
private:
    std::string state;
    Memento(const std::string& state) : state(state) {}
    std::string getState() const {
        return state;
    }
    void setState(const std::string& newState) {
        state = newState;
    }
};
class Originator {
public:
    Originator(const std::string& state) : state(state) {}
    Memento createMemento() {
        return Memento(state);
    }
    void restore(const Memento& memento) {
        state = memento.getState();
    }
    std::string getState() const {
        return state;
    }
    void setState(const std::string& newState) {
        state = newState;
    }
private:
    std::string state;
};
class Caretaker {
public:
    void addMemento(const Memento& memento) {
        mementos.push_back(memento);
    }
    Memento getMemento(size_t index) const {
        if (index < mementos.size()) {
            return mementos[index];
        }
        return Memento("");
    }
private:
    std::vector<Memento> mementos;
};
int main() {
    Originator originator("Initial State");
    Caretaker caretaker;
    caretaker.addMemento(originator.createMemento());
    originator.setState("State 1");
    caretaker.addMemento(originator.createMemento());
    originator.setState("State 2");
    caretaker.addMemento(originator.createMemento());
    // Restore state to "State 1"
    originator.restore(caretaker.getMemento(1));
    std::cout << "Restored state: " << originator.getState() << std::endl;
    return 0;
}

代码解析(Code explanation):

在这个代码示例中,我们实现了三个类:MementoOriginatorCaretaker

  1. Memento 类用于存储发起人的内部状态。它具有私有的构造函数、getState()setState() 方法,这些方法只能由 Originator 类访问。这样,我们确保了对象的封装性得以维护。
  2. Originator 类包含一个内部状态,并具有 createMemento() 方法和 restore() 方法。createMemento() 方法用于创建一个备忘录对象以保存当前状态;restore() 方法用于通过备忘录对象恢复到先前的状态。
  3. Caretaker 类负责存储和管理备忘录对象。它具有 addMemento() 方法,用于添加备忘录对象;getMemento() 方法用于根据索引获取备忘录对象。

main() 函数中,我们创建了一个 Originator 对象,并修改了它的状态。随后,我们使用 Caretaker 对象来存储和恢复 Originator 的状态。通过运行这个程序,我们可以看到备忘录模式如何实现状态的保存和恢复,同时保持对象的封装性。

备忘录模式的优缺点(Pros and Cons of Memento Pattern)

备忘录模式的优点(Pros of Memento Pattern)

  1. 封装性:备忘录模式确保了发起人(Originator)对象的内部状态不会直接暴露给外部。状态的保存和恢复通过备忘录(Memento)对象进行,而不需要访问或修改发起人的内部状态。这样,备忘录模式可以保持对象的封装性。
  2. 易于实现:备忘录模式提供了一种简单且易于实现的方法来保存和恢复对象状态。通过将状态保存在备忘录对象中,我们可以实现撤销、重做等操作,而无需复杂的实现方式。
  3. 可扩展性:备忘录模式可以很容易地扩展以支持多种状态恢复功能,如多步撤销、重做操作等。此外,它还适用于不同类型的发起人对象,提供了一种通用的状态管理方法。
  4. 能够支持事务:备忘录模式能够支持事务,即一系列操作可以作为一个整体来执行。如果在执行事务过程中发生错误,可以利用备忘录模式将系统恢复到事务开始之前的状态。这使得应用程序更加健壮和可靠。

备忘录模式的缺点(Cons of Memento Pattern)

  1. 内存消耗:由于备忘录模式需要为每个保存的状态创建一个备忘录对象,这可能导致较高的内存消耗,尤其是在需要保存大量状态或频繁进行状态保存的场景中。
  2. 性能开销:当发起人(Originator)对象的状态较大或复杂时,创建备忘录对象和恢复状态的过程可能会导致性能开销。此外,管理者(Caretaker)需要维护备忘录对象的列表,这也可能在一定程度上影响性能。
  3. 维护难度:当发起人对象的内部状态发生更改时,可能需要相应地更新备忘录类。这可能会增加系统的维护难度和复杂性。

尽管备忘录模式存在这些缺点,但在需要实现状态保存和恢复的场景中,它仍然是一种有效且广泛使用的设计模式。在实际应用中,开发者需要根据具体需求权衡优缺点,以决定是否使用备忘录模式。

备忘录模式与其他设计模式的关联(Relationship with Other Design Patterns)

备忘录模式与命令模式(Memento pattern and Command pattern)

备忘录模式和命令模式之间有一定的关联,它们都可以用于实现撤销(Undo)和重做(Redo)功能。然而,两者在实现这些功能时的方法和重点有所不同。

  1. 实现方式:命令模式通过将操作封装成对象来实现撤销和重做功能。每个命令对象具有执行(execute)和撤销(undo)方法,用于执行操作或撤销操作。而备忘录模式通过保存和恢复对象的状态来实现撤销和重做功能。
  2. 状态保存:在命令模式中,可以在命令对象中保存足够的信息以便在需要时撤销操作。而在备忘录模式中,状态保存在备忘录对象中,而不是命令对象中。
  3. 封装性:备忘录模式保持了对象的封装性,因为它将状态存储在备忘录对象中,而不是直接访问或修改发起人的内部状态。而在命令模式中,封装性可能会受到一定程度的影响,因为命令对象可能需要访问和修改接收者对象的状态以执行和撤销操作。
  4. 适用场景:命令模式更适用于需要将操作封装为对象、实现宏命令(一组命令的组合)或者需要将命令放入队列中以便稍后执行的场景。而备忘录模式更适用于需要保存和恢复对象状态的场景,尤其是在需要保持对象封装性的情况下。

在实际应用中,备忘录模式和命令模式可以独立使用,也可以结合使用。例如,在实现一个文本编辑器时,可以使用命令模式来封装文本操作(如插入、删除等),同时使用备忘录模式来保存和恢复文本状态,实现撤销和重做功能。这样,我们可以充分利用两种设计模式的优势,实现一个更加灵活和高效的系统。

备忘录模式与状态模式(Memento pattern and State pattern)

备忘录模式和状态模式在一定程度上有关联,但它们的目的和实现方式有所不同。

  1. 目的:备忘录模式主要关注保存和恢复对象的内部状态,通常用于实现撤销(Undo)和重做(Redo)操作。而状态模式主要关注对象状态的变化以及根据状态改变对象的行为。状态模式通过将状态封装为独立的对象,并在运行时切换这些状态对象来改变对象的行为。
  2. 状态管理:在备忘录模式中,对象的状态保存在备忘录(Memento)对象中,而不直接暴露给外部。发起人(Originator)对象通过创建备忘录对象和恢复备忘录对象的状态来实现状态的保存和恢复。而在状态模式中,状态以独立的状态对象形式存在,这些状态对象定义了对象在特定状态下的行为。当对象的状态发生变化时,会切换到相应的状态对象。
  3. 封装性:备忘录模式保持了发起人对象的封装性,因为状态的保存和恢复通过备忘录对象进行,而不需要访问或修改发起人的内部状态。而在状态模式中,封装性体现在将状态相关的行为封装在各自的状态对象中,从而遵循单一职责原则。
  4. 适用场景:备忘录模式适用于需要保存和恢复对象状态的场景,尤其是在需要保持对象封装性的情况下。而状态模式适用于对象状态的变化会导致对象行为发生变化的场景,以便在运行时灵活地切换行为。

尽管备忘录模式和状态模式有一定的关联,但它们解决的问题和实现方式有所不同。在实际开发中,根据具体需求和场景选择合适的设计模式是至关重要的。有时,这两种模式甚至可以结合使用,以实现更加灵活和高效的系统。

实际案例:C++应用中的备忘录模式(Real-life Case: Memento Pattern in C++ Application)

案例描述(Case description):

假设我们正在开发一个简单的文本编辑器,允许用户对文本进行插入、删除、修改等操作。为了提供更好的用户体验,我们希望添加撤销(Undo)和重做(Redo)功能,以便用户可以撤销或重做他们的操作。在这个案例中,我们可以使用备忘录模式来保存和恢复文本编辑器的状态。

案例实现(Case implementation):

首先,我们需要定义三个类:Editor(发起人),EditorMemento(备忘录),和EditorCaretaker(管理者)。

#include <iostream>
#include <string>
#include <stack>
class EditorMemento {
public:
    EditorMemento(const std::string& content) : content_(content) {}
    std::string getContent() const { return content_; }
private:
    std::string content_;
};
class Editor {
public:
    void type(const std::string& words) { content_ += words; }
    std::string getContent() const { return content_; }
    EditorMemento save() const { return EditorMemento(content_); }
    void restore(const EditorMemento& memento) { content_ = memento.getContent(); }
private:
    std::string content_;
};
class EditorCaretaker {
public:
    void saveState(const EditorMemento& memento) { history_.push(memento); }
    EditorMemento undo() {
        if (history_.empty()) {
            throw std::runtime_error("No states to undo.");
        }
        EditorMemento memento = history_.top();
        history_.pop();
        return memento;
    }
private:
    std::stack<EditorMemento> history_;
};

接下来,我们可以使用Editor类和EditorCaretaker类来实现撤销和重做功能:

int main() {
    Editor editor;
    EditorCaretaker caretaker;
    editor.type("This is a sample text. ");
    caretaker.saveState(editor.save());
    editor.type("Adding more text. ");
    caretaker.saveState(editor.save());
    editor.type("And even more text. ");
    std::cout << "Current content: " << editor.getContent() << std::endl;
    // Undo the last two operations.
    editor.restore(caretaker.undo());
    editor.restore(caretaker.undo());
    std::cout << "Content after undo: " << editor.getContent() << std::endl;
    return 0;
}

在这个例子中,我们首先创建了一个Editor对象和一个EditorCaretaker对象。在进行文本操作之后,我们使用save()方法创建一个备忘录对象,并将其传递给EditorCaretaker对象的saveState()方法以保存状态。当需要撤销操作时,我们可以通过调用EditorCaretaker对象的undo()方法来获取先前保存的备忘录对象,并使用restore()方法将编辑器状态恢复到该备忘录对象所保存的状态。

这个实际案例展示了如何在C++应用中使用备忘录模式来实现撤销和重做功能。通过使用备忘录模式,我们可以轻松地保存和恢复文本编辑器的状态,同时保持了对象的封装性。这个设计模式为实现复杂操作提供了强大的支持,同时提高了代码的可维护性和可扩展性。

在实际开发过程中,备忘录模式可以广泛应用于各种场景,如游戏存档、版本控制系统等。通过合理地运用备忘录模式,我们可以实现更加高效和灵活的系统。

此外,还可以将备忘录模式与其他设计模式结合使用,以实现更丰富的功能。例如,在实现文本编辑器的撤销和重做功能时,我们可以将备忘录模式与命令模式结合使用。这样,我们可以将文本操作封装为命令对象,然后使用备忘录模式来保存和恢复这些命令对象的状态。这种组合将充分利用两种设计模式的优势,实现一个功能强大、易于维护和扩展的系统。

总之,备忘录模式为处理对象状态的保存和恢复提供了一个有效的解决方案。在实际开发中,我们需要根据具体需求和场景选择合适的设计模式,以提高代码质量和实现更加高效的系统。

总结(Conclusion)

备忘录模式的重要性(The importance of Memento pattern)

备忘录模式是一种行为型设计模式,其主要目的是在不破坏对象封装性的前提下,捕获并保存对象的内部状态,以便后续可以将对象恢复到先前的状态。备忘录模式在实际应用中具有广泛的应用场景,例如撤销操作、重做操作、游戏存档、版本控制系统等。通过使用备忘录模式,我们可以提高代码的可维护性、可扩展性以及易用性,从而构建出高质量、高性能的软件系统。

选择合适的设计模式(Choosing the right design pattern)

在实际开发过程中,选择合适的设计模式是至关重要的。每种设计模式都有其特定的应用场景和优缺点,因此我们需要根据项目的需求和场景来选择适合的设计模式。在决定是否使用备忘录模式时,我们需要考虑以下几点:

  1. 是否需要保存和恢复对象的状态?
  2. 是否希望在不破坏对象封装性的前提下实现状态的保存和恢复?
  3. 是否需要支持撤销和重做等操作?

如果以上问题的答案都是肯定的,那么备忘录模式很可能是一个合适的选择。同时,我们还需要关注备忘录模式与其他设计模式之间的关系,以便在需要时能够灵活地组合和应用这些设计模式,从而实现更加高效、灵活和可维护的系统。

目录
相关文章
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
142 17
|
8月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
333 77
|
8月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
193 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
8月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
169 19
|
8月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
205 13
|
8月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
183 12
|
8月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
164 10
|
8月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
103 10
|
8月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
265 10
|
8月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
190 7