MVVM-Model-Report

目录


DSV Model Design

设计任务

设计极为基础的数据结构, 以查找树(有序词典)为主要实现模型; 设计二叉查找树, 平衡二叉树, 伸展树, 左式堆, 哈夫曼树(贪心构造算法), 红黑树;

  • 设计模型基类, 方便ViewModel层进行暴露

    • 抽象各种模型共用的属性与方法, 设计必要的虚函数与纯虚函数

    • 设计基类(模板)树节点, 设计基类(模板)树

  • 设计模型二叉查找树(Binary Search Tree)

    • 支持操作: 插入, 删除, 查找, 清空
    • 结构: 二叉树, 树的度为2
    • 性质: 左右满足全序关系
  • 设计模型平衡二叉树(AVL Tree)

    • 支持操作: 插入, 删除, 查找, 清空
    • 结构: 二叉树, 树的度为2
    • 性质: 二叉查找树, 平衡因子(Balance Factor) \in {-1, 0, 1}
  • 设计模型伸展树(Splay Tree)

    • 支持操作: 插入, 删除, 查找, 清空
    • 结构: 二叉树, 树的度为2
    • 性质: 二叉查找树, 插入, 查找后的key 通过单旋转或双旋转至根节点
  • 设计模型左式堆(Leftist Heap)

    • 支持操作: 插入, 删除最大(最小), 清空
    • 结构: 二叉树
    • 性质: 堆序(偏序关系), NPL(左子树) >= NPL(右子树)
  • 设计模型哈夫曼树(Huffman Tree)(使用Huffman 构造算法)

    • 支持操作: 插入, 删除后通过Huffman贪心算法重新构建, 清空
    • 结构: 二叉树
    • 性质: 本质是左0右1的字典树
  • 设计模型红黑树(RB-Tree)

    • 支持操作: 插入, 删除, 查找, 清空
    • 结构: 二叉树
    • 性质:
      1. 每一个节点是红红色或黑色
      2. 根节点是黑色的
      3. 叶子节点NIL是黑色的
      4. 有树边相连的2个节点不同时为红色
      5. 从任意节点出发, 黑高度与路径无关

设计思路与方案

  • 回到顶部

  • 模型基类设计方案

    • 提供共有的基本成员函数, 如中序, 层序遍历等
    • 提供共有的成员对象left, right, key, depth
    • 继承属性通知发生器(Proxy_PropertyNotification<T>)
    • 继承命令通知发生器(Proxy_CommandNotification<T>)
    • 设计virtual析构函数, virtual清空函数(不同模型将使用不同清空动作)
  • 二叉查找树设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现插入, 删除, 查找算法
    • 节点不需要增加其他属性
    • 树不需要增加其他属性
  • 平衡二叉树设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现插入, 删除, 查找算法, RR, LL, LR, RL算法
    • 节点增加属性height信息, parent信息
    • 树不需要增加其他属型性
  • 伸展树设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现插入, 删除, 查找算法, RR, LL, LR, RL算法, 删除调整, 插入调整算法
    • 节点增加属性 parent信息
    • 树不需要增加其他属性
  • 左式堆设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现Merge算法, 在此基础上实现插入, 删除算法
    • 节点增加属性NPL(Null Path Length)信息
    • 树不需要增加其他属性
  • 哈夫曼树设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现Huffman贪心构造算法
  • 红黑树设计方案

    • 树节点继承基类树节点, 树继承基类树
    • 实现插入, 删除, 查找算法, RR, LL, LR, RL算法, 删除调整, 插入调整算法
    • 删除分为左右对称共8个case, 插入分为左右对称共6个case
    • 节点增加属性NPL(Null Path Length)信息, Red, Black信息
    • 树增加属性NIL节点的信息

设计实现

  • 回到顶部

  • 模型基类实现

    • 模型基类树节点模板声明
       template <typename T>
       struct BaseNode {
         T key;
         BaseNode *left;
         BaseNode *right;
         
         int depth;
         int inorderIndex; 
         NodeType state;
         NodeColor color;
         
         BaseNode(const T& key);
         virtual ~BaseNode(); 
        };
      
    • 模型基类树模板声明
       template <typename T, typename S = std::less<T>>
       class BaseTree : public Proxy_PropertyNotification<BaseTree<T, S>>, 
                  public Proxy_CommandNotification<BaseTree<T, S>> {
       protected:
         BaseNode<T> *root;
       protected:
         void inorder(BaseNode<T> *cur, int *count);
         void levelorder();
       public:
         BaseTree();
         virtual ~BaseTree();
         BaseNode<T> *getRoot();
         virtual BaseNode<T> *getNIL();
         void clear();
       };
      
  • 二叉查找树实现

    • 二叉查找树 . 树节点模板声明
       template<typename T>
       struct BSTNode : public BaseNode<T>{
         BSTNode(const T& key);
         virtual ~BSTNode(); // auto-recursion freeTree! hahah ==!
       };
      
    • 二叉查找树 . 树模板声明
       template <typename T, typename S = less<T>>
       class BST : public BaseTree<T, S> {
         BaseNode<T> *insert(BaseNode<T> *cur, const T& key);
         void erase(BSTNode<T> *pos, BSTNode<T> *parent); // deprecated
         void erase(BaseNode<T> *pos);
       public:
       #ifdef BST_DEBUG
         void print(BaseNode<T> *cur);
         void print();
       #endif
         BST();
         virtual ~BST();
         void insert(const T& key);
         BSTNode<T> *find(const T& key);
         void erase(const T& key);
       };
      
  • 平衡二叉树实现

    • 平衡二叉树 . 树节点模板声明
       template<typename T>
       struct AVLNode : public BaseNode<T>{
         int height;
      
         AVLNode(const T& key);
         ~AVLNode(); // auto-recursion freeTree! hahah ==!
       };
      
    • 平衡二叉树 . 树模板声明
       template<typename T, typename S = less<T>>
       class AVLTree : public BaseTree<T, S> {	
         // root is a BaseNode 
         // pointer is a member of BaseTree
         int getHeight(BaseNode<T> *_pos);
         BaseNode<T> *RR(BaseNode<T> *pos);
         BaseNode<T> *LL(BaseNode<T> *pos);
         BaseNode<T> *RL(BaseNode<T> *pos);
         BaseNode<T> *LR(BaseNode<T> *pos);
         void erase(BaseNode<T> *pos);
         BaseNode<T> *insert(BaseNode<T> *pos, const T& key); //recurson for implementation
       public:
       #ifdef AVL_DEBUG
         void print(BaseNode<T> *cur);
         void print();
       #endif
         AVLTree();
         virtual ~AVLTree();
         void insert(const T& key);	
         void erase(const T& key);
         AVLNode<T> *find(const T& key);
       };
      
  • 伸展树实现

    • 伸展树 . 树节点模板声明
       template <typename T>
       struct SPTNode : BaseNode<T> {
         BaseNode<T> *parent;
      		
         SPTNode(const T& key, BaseNode<T> *parent);
         virtual ~SPTNode();
      
         // this == parent
         SPTNode *RR();
         SPTNode *LL();
      
         // this == grandfa + grandma
         SPTNode *zig_zig(SPTNode *pos); // this->root -> new this->root
         SPTNode *zig_zag(SPTNode *pos); // grand is this; pos is child!
       };
      
    • 伸展树 . 树模板声明
       template <typename T, typename S = less<T>>
       class SplayTree : public BaseTree<T, S>{
         void fixup(SPTNode<T> *pos);     // after finding or inserting
         BaseNode<T> *
         insert(const T& key, BaseNode<T> *father, BaseNode<T> *pos); // for recurssion
         void erase(BaseNode<T> *pos);
       public:
       #ifdef SPT_DEBUG
         void print() const;
       #endif
         SplayTree();
         virtual ~SplayTree();
         SPTNode<T> *find(const T& key); // return this->root; const member func is naive!!!
         void insert(const T& key);
         void insert_recursion(const T& key);
         void erase(const T& key);
       };
      
  • 左式堆实现

    • 左式堆 . 树节点模板声明
       template <typename T>
       struct LeftistNode : public BaseNode<T> {
         int NPL;
         LeftistNode(const T& key);
         virtual ~LeftistNode();
       };
      
    • 左式堆 . 树模板声明
       template <typename T, typename S = less<T>>
       class LeftistHeap : public BaseTree<T, S> {
         BaseNode<T> *merge1(BaseNode<T> *h1, BaseNode<T> *h2);
         void merge2(LeftistNode<T> *h1, LeftistNode<T> *h2);
         BaseNode<T> *insert(BaseNode<T> *origin, const T& key);
       public:
       #ifdef LEFTISTHEAP_DEBUG
         void print(LeftistNode<T> *cur);
         void print();
       #endif	
         LeftistHeap();
         virtual ~LeftistHeap();
         void insert(const T& key);
         void erase();                     // erase minimal
       };
      
  • 哈夫曼树实现

    • 哈夫曼树 . 树节点模板声明
       template<typename T>
       struct HFNode : public BaseNode<T>
       {
        	HFNode(const T& value);
        	virtual ~HFNode();
       };
      
    • 哈夫曼树 . 树模板声明 ```C++ template<typename T, typename S = less > class HFTree : public BaseTree<T, S>{ private: std::vector content; void create();

    public: HFTree(); virtual ~HFTree();

    void insert(const T& value); void erase(const T& value); void clear(); HFNode *find(const T& value);

    }; ```

  • 红黑树实现

    • 红黑树 . 树节点模板声明
       template <typename T>
       struct RBTNode : public BaseNode<T> {
         BaseNode<T> *parent;
         RBTNode(const T& key);
         virtual ~RBTNode();
       };
      
    • 红黑树 . 树模板声明 ```C++

    template <typename T, typename S = less> class RBT : public BaseTree<T, S> { BaseNode *LL(BaseNode *NIL, BaseNode *pivot); BaseNode *RR(BaseNode *NIL, BaseNode *pivot); // pivot is povit

      BaseNode<T> *insert(BaseNode<T> *oRoot, const T& key);
      RBTNode<T> *insertFixup(RBTNode<T> *newRoot, RBTNode<T> *current);
    
      RBTNode<T> *find(const T& key, BaseNode<T> *NIL);
    
      BaseNode<T> *erase(BaseNode<T> *oRoot, BaseNode<T> *pos);
      RBTNode<T> *eraseFixup(RBTNode<T> *newRoot, RBTNode<T> *x);
    
      void inorder(BaseNode<T> *cur, int *count, BaseNode<T> *NIL);
      void levelorder(BaseNode<T> *NIL);
      void clear(BaseNode<T> *cur, BaseNode<T> *NIL);  public:	  #ifdef RBT_DEBUG
      void print(BaseNode<T> *cur, BaseNode<T> *NIL);
      void print();  #endif	
      RBT();
      virtual ~RBT();
      void insert(const T& key);
      RBTNode<T> *find(const T& key);
      void erase(const T& key);
      void clear();
      virtual BaseNode<T> *getNIL() override;  };  ```
    

单元测试

  • 回到顶部

  • 二叉查找树
     #include "BST.h"
     int main()
     {
              BST<int> *bst = new BST<int>;
              bst->insert(5);
              bst->insert(3);
              bst->insert(4);
              bst->insert(6);
              bst->insert(2);
              bst->insert(1);
              bst->insert(7);
              bst->insert(8);
              bst->insert(9);
              bst->insert(10);
              bst->insert(11);
    	
              bst->erase(5);
              bst->erase(4);
              bst->erase(3);
    
              bst->print();
    
              delete bst;
              return 0;
     }
    
  • 程序运行输出

testBST

  • 平衡二叉树 ```C++ #include “AVLTree.h”

int main() { AVLTree *atree = new AVLTree;

    atree->insert(1);
    atree->insert(2);
    atree->insert(3);
    atree->insert(4);
    atree->insert(5);
    atree->insert(6);
    atree->insert(7);
    atree->insert(8);
    atree->erase(8);
    atree->erase(5);
    atree->erase(7);
    atree->erase(6);
    atree->print();
    delete atree;
    return 0;    }    ```    - 程序运行输出

testAVL

  • 伸展树 ```C++ #include “SplayTree.h” #include

using namespace std;

int main() { SplayTree *myTree = new SplayTree(); myTree->insert(1); myTree->insert(2); myTree->insert(3); myTree->insert(4); myTree->insert(5); myTree->insert(6); myTree->find(1); myTree->find(2); myTree->find(3); myTree->find(5);

    myTree->erase(5);
    cout << "--------------------------------" << endl;
    myTree->print();	
    myTree->erase(4);
    cout << "--------------------------------" << endl;
    myTree->print();	
    myTree->erase(3);
    cout << "--------------------------------" << endl;
    myTree->print();
    myTree->erase(2);
    cout << "--------------------------------" << endl;
    myTree->print();
    myTree->erase(1);
    cout << "--------------------------------" << endl;
    myTree->print();
    myTree->erase(6);
    cout << "--------------------------------" << endl;
    myTree->print();
    delete myTree;
    return 0;    }    ```    - 程序运行输出

testSPT

  • 左式堆 ```C++ #include “LeftistHeap.h” #include

int main() { LeftistHeap *lh = new LeftistHeap; lh->insert(0); lh->insert(2); lh->insert(4); lh->insert(1); lh->insert(3); lh->insert(9); lh->insert(8); lh->insert(6);

    std::cout << "------------------------------------" << std::endl;
    lh->print();
    lh->erase();
    lh->erase();
    std::cout << "------------------------------------" << std::endl;
    lh->print();	

    delete lh;
    return 0;    }    ```    - 程序运行输出

testLeftist

  • 哈夫曼树 ```C++ #include “HFTree.h”

int main() { HFTree *hfmt = new HFTree; hfmt->insert(1); hfmt->insert(10); hfmt->insert(11); hfmt->insert(2); hfmt->insert(3); hfmt->insert(9); hfmt->insert(8); hfmt->insert(7); hfmt->insert(4); hfmt->insert(6); hfmt->insert(5); hfmt->find(1); hfmt->erase(1); delete hfmt; return 0; }

   - 红黑树
   ```C++
   #include "RBT.h"

   int main()
   {
        RBT<int> *rbt = new RBT<int>;
        rbt->insert(3);
        rbt->insert(4);
        rbt->insert(1);
        rbt->insert(2);
        rbt->insert(5);
        rbt->insert(10);
        rbt->insert(9);
        rbt->insert(7);
        rbt->insert(8);
        rbt->insert(6);

        rbt->erase(4);
        rbt->erase(1);
        rbt->erase(2);
        rbt->erase(3);

        rbt->print();
        delete rbt;
        return 0;
   }
  • 程序运行输出

testRBT


图表说明


本课程心得体会

  • 回到顶部

  • 个人CPP工程技能收获
    1. 初步了解大型程序的多人协作开发流程, MVVM UI设计模式可以充分解耦Model, ViewModel, Model之间的关联, 通过基类, 通过接口协议, 可以实现高效的同时协作开发, 提高工作效率
    2. 对模板元编程技术有了新的理解和熟练, 对现代C++特性也有了进一步的了解
  • 个人合作精神收获
    1. 正确的框架, 高效的设计模式, 产品经理恰当的分工是一个开发团队成功的关键, 也是在平时的课程中, 在校园里很难学到的东西, 短学期让我受益匪浅!
    2. 分工之后, 并不是完全分割开发者, 开发者之间也要保持有效的沟通, 才能一起提高工作效率, 设计出令人满意的作品, 艺术品!