帐前卒专栏

code, software architect, articles and novels.
代码,软件架构,博客和小说

这个树的定义的确很有问题。其实AVLTree和SplayTree以及RedBlackTree都是self-adjusting Tree

因为如果是树做索引那么大部分的时间将用来查找。这个树在查找上可以将查找的节点提升到树根,插入时也是一样。这样提高了查找的效率。并且操作系统有一种说法是近来用
到的,将来用到的几率也会很大(LRU原理)。删除,既然删除对于此树来说再也没有什么,那就直接删除算了。

根据这几点想法。自己做一个self-adjusting Tree。但是还没有验证是否能达到实际水平的O(nlogn)。虽然理论上这个树并不能达到这样一个时间
复杂度。但是对于实际数据来说,还是有可能达到的。不知道有没有这么lucky。

因为对于这个树来说插入和查找操作其实差不多。

所以下面只介绍插入操作。找到要插入的地方,反遍历单旋转(这里和SplayTree不同一点是只使用单旋转)

TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)

返回值为当前子树根节点

1.subroot是否为空,创建新的节点,并返回subroot

2.如果不为空

A.subroot中的值 < data中的值,对subroot右子树调用insertNode(),subroot
与当前右子树根节点采用旋转操作。将两个节点位置对换。

B.subroot中的值 > data中的值,对subroot左子树调用insertNode(),subroot
与当前左子树根节点采用旋转操作。将两个节点位置对换。

C.subroot中的值 == data中的值,do nothing

3.查看该节点是否已成为根节点。如果是的话,调整根节点的值。

下面给出代码。

  1. template < class T>
  2. class SelfTree: public BinaryTree
  3. {
  4. private :
  5. // return the sub tree root
  6. //        a               b
  7. //       /       ->        /
  8. //      b                   a
  9. TreeNode* sLeftRotate(TreeNode* a,TreeNode* b)
  10. {
  11. a->setLeft(b->getRight());
  12. b->setRight(a);
  13. return b;
  14. }
      1. // return the sub tree root
  15. //        a               b
  16. //         /     ->      /
  17. //          b           a
  18. TreeNode* sRightRotate(TreeNode* a, TreeNode* b)
  19. {
  20. a->setRight(b->getLeft());
  21. b->setLeft(a);
  22. return b;
  23. }
        1. TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)
  24. {
  25. if (subroot == NULL)
  26. {
  27. subroot = new TreeNode(data);
  28. return subroot;
  29. }
  30. else
  31. {
  32. TreeNode* tempNode = NULL;
  33. TreeNode* tempRoot = NULL;
  34. if (subroot->getData() > data)
  35. {
    1. tempNode = insertNode(subroot->getLeft(),subroot,data);
  36. tempRoot = sLeftRotate(subroot,tempNode);
    1. }
  37. else if (subroot->getData() < data)
  38. {
  39. tempNode = insertNode(subroot->getRight(),subroot,data);
  40. tempRoot = sRightRotate(subroot,tempNode);
  41. }
  42. else
  43. {
  44. throw “the same key” ;
  45. }
    1. if (prev == NULL)
  46. {
  47. this ->head = tempRoot;
  48. }
  49. else
  50. {
  51. if (prev->getData() > tempRoot->getData())
  52. {
  53. prev->setLeft(tempRoot);
  54. }
  55. else
  56. {
  57. prev->setRight(tempRoot);
  58. }
  59. }
  60. return tempRoot;
  61. }
  62. }
  63. public :
  64. SelfTree(T& data):BinaryTree(data)
  65. {
    1. }
    1. ~SelfTree()
  66. {
    1. }
    1. void insertNode(T& data)
  67. {
  68. insertNode( this ->head,NULL,data);
  69. }
    1. };

AVLTree本身就是二叉查找树。为了保证查找效率在O(nlogn),所以有时要对树高进行必要的调整。

AVLTree拥有自己的法则使得插入、删除、查找都在O(nlogn)时间内完成。

下面写了一个AVLTreeNode类,好像和TreeNode类一样。

下面写AVLTree类,这个类重要的地方在与插入和删除操作。查找操作和BinarySearchTree一致。但是至今还没有找到一个有效的方法来使用Binar
ySearchTree中的Search。除非将Search方法抽象为一个接口。

暂时先不管太多。

先看左旋和右旋操作。

  1. // return the subRoot
  2. //        a                   b
  3. //       /                  /   /
  4. //      b        ->        c     a
  5. //     /
  6. //    c
  7. AVLNode* LLRotate(AVLNode* a, AVLNode* b)
  8. {
  9. a->setLeft(b->getRight());
  10. b->setRight(a);
    1. a->setAHeight(0);
  11. b->setAHeight(0);
  12. //a->setAHeight(getAVLHeight(a));
  13. //b->setAHeight(getAVLHeight(b));
  14. return b;
  15. }
    1. // return the subRoot
  16. //        a                      b
  17. //          /                  /   /
  18. //            b        ->     a     c
  19. //              /
  20. //                c
  21. AVLNode* RRRotate(AVLNode* a, AVLNode* b)
  22. {
  23. a->setRight(b->getLeft());
  24. b->setLeft(a);
    1. a->setAHeight(0);
  25. b->setAHeight(0);
  26. //a->setAHeight(getAVLHeight(a));
  27. //b->setAHeight(getAVLHeight(b));
  28. return b;
  29. }
      1. // return the subRoot
  30. //        a                      c
  31. //          /                  /   /
  32. //            b        ->     a     b
  33. //           /                 /
  34. //          c                   d
  35. //         /
  36. //        d
  37. AVLNode* RLRotate(AVLNode* a, AVLNode* b, AVLNode* c)
  38. {
    1. b->setLeft(c->getRight());
  39. c->setRight(b);
  40. a->setRight(c->getLeft());
  41. c->setLeft(a);
      1. //a->setAHeight(getAVLHeight(a));
  42. //c->setAHeight(getAVLHeight©);
  43. //b->setAHeight(getAVLHeight(b));
    1. if (c->getAbsoluteAHeight() == 1)
  44. {
  45. if (b->getAHeight() == 0)
  46. {
  47. b->setAHeight(-1);
  48. }
  49. else
  50. {
  51. b->setAHeight(0);
  52. }
  53. a->setAHeight(1);
  54. c->setAHeight(0);
    1. }
  55. else
  56. {
  57. if (b->getAHeight() == 0)
  58. {
  59. b->setAHeight(-1);
  60. }
  61. else
  62. {
  63. b->setAHeight(0);
  64. }
  65. a->setAHeight(0);
  66. c->setAHeight(0);
    1. }
      1. return c;
  67. }
    1. // return the subRoot
  68. //        a                      c
  69. //       /                     /   /
  70. //      b              ->     b     a
  71. //       /                         /
  72. //        c                       d
  73. //         /
  74. //          d
  75. AVLNode* LRRotate(AVLNode* a, AVLNode* b, AVLNode* c)
  76. {
  77. b->setRight(c->getLeft());
  78. c->setLeft(b);
  79. a->setLeft(c->getRight());
  80. c->setRight(a);
      1. //a->setAHeight(getAVLHeight(a));
  81. //c->setAHeight(getAVLHeight©);
  82. //b->setAHeight(getAVLHeight(b));
    1. if (c->getAbsoluteAHeight() == 1)
  83. {
  84. if (b->getAHeight() == 0)
  85. {
  86. b->setAHeight(1);
  87. }
  88. else
  89. {
  90. b->setAHeight(0);
  91. }
    1. a->setAHeight(-1);
  92. c->setAHeight(0);
    1. }
  93. else
  94. {
    1. if (b->getAHeight() == 0)
  95. {
  96. b->setAHeight(1);
  97. }
  98. else
  99. {
  100. b->setAHeight(0);
  101. }
  102. a->setAHeight(0);
  103. c->setAHeight(0);
    1. }
          1. return c;
  104. }
  105. 这里旋转后调整平衡因子是关键部分。这是我自己总结的方法,经少量测试暂时没有出现问题。这个调整方法好像与大多数书本和网络程序的方法不一致。不清楚到底哪个是正确的。但是如果不使用这种直接赋值的方法,可以使用递归查找树高的方法保障万无一失的解决这个问题。这里使用的 右树高减左树高得平衡因子 的方法。

下面给出这样的两个函数,其中getAVLHeight是核心方法。

  1. int getHeight(AVLNode* node)
  2. {
  3. if (node == NULL)
  4. {
  5. return 0;
  6. }
  7. else
  8. {
  9. int leftHeight = getHeight(node->getLeft());
  10. int rightHeight = getHeight(node->getRight());
  11. if (leftHeight > rightHeight)
  12. {
  13. return leftHeight+1;
  14. }
  15. else
  16. {
  17. return rightHeight+1;
  18. }
  19. }
  20. }
    1. int getAVLHeight(AVLNode* node)
  21. {
  22. if (node == NULL)
  23. {
  24. return 0;
  25. }
  26. else
  27. {
  28. int leftHeight = getHeight(node->getLeft());
  29. int rightHeight = getHeight(node->getRight());
  30. return rightHeight - leftHeight;
  31. }
  32. }
  33. 删除、插入操作有点复杂。

插入操作:

1.先找到可能要调整的那个节点A,这里的可能要调整的节点即为插入路径中平衡因子为+1或者为-
1的点。(这里一定要记得不要自作聪明的认为如果向左插入,+1节点就不会是可能节点)

2.插入应该插入的节点,调整从A至目标节点的平衡因子。并且记录是否增长了子树树高(是否插入节点没有兄弟节点)。

3.插入后查看是否增长子树树高,如果增长树高,再查看A是否已经不平衡。如果不平衡,调整,否则,插入完成。

(这里要注意A节点为树根的情况,或者无A节点的情况)

因为下面的程序首先将树根设定为可能要调整的节点A,所以没有出现无A节点的情况。

以上三点,我看过很多教科书,发现讲解有些含糊,或者本身就是略写。这里并没有采用递归操作。

  1. void insertNode(AVLNode* node)
  2. {
  3. AVLNode* subRoot = this ->head;
  4. if (subRoot == NULL)
  5. {
  6. subRoot = node;
  7. return ;
  8. }
  9. AVLNode* ppoRoot = NULL;
  10. AVLNode* poRoot = NULL;
  11. AVLNode* pRoot = NULL;
        1. poRoot = subRoot;
    1. while (subRoot != NULL)
  12. {
  13. pRoot = subRoot;
  14. if (subRoot->getData() > node->getData())
  15. {
    1. if (isPossibleNode(subRoot->getLeft(),node))
  16. {
  17. poRoot = subRoot->getLeft();
  18. ppoRoot = subRoot;
  19. }
  20. subRoot = subRoot->getLeft();
    1. }
  21. else if (subRoot->getData() < node->getData())
  22. {
    1. if (isPossibleNode(subRoot->getRight(),node))
  23. {
  24. poRoot = subRoot->getRight();
  25. ppoRoot = subRoot;
  26. }
  27. subRoot = subRoot->getRight();
  28. }
  29. else
  30. {
  31. throw “the same key” ;
  32. }
  33. }
    1. bool isChangeHeight = false ;
  34. if (pRoot->getData() > node->getData())
  35. {
    1. pRoot->setLeft(node);
  36. if (pRoot->getRight() == NULL)
  37. {
  38. isChangeHeight = true ;
  39. }
  40. else
  41. {
  42. pRoot->setAHeight(pRoot->getAHeight()-1);
  43. }
  44. }
  45. else if (pRoot->getData() < node->getData())
  46. {
    1. pRoot->setRight(node);
  47. if (pRoot->getLeft() == NULL)
  48. {
  49. isChangeHeight = true ;
  50. }
  51. else
  52. {
  53. pRoot->setAHeight(pRoot->getAHeight()+1);
  54. }
  55. }
      1. if (poRoot != NULL && isChangeHeight)
  56. {
  57. // s->a update Height
  58. subRoot = poRoot;
  59. while (subRoot != node)
  60. {
  61. if (subRoot->getData() > node->getData())
  62. {
  63. subRoot->setAHeight(subRoot->getAHeight()-1);
    1. subRoot = subRoot->getLeft();
    1. }
  64. else if (subRoot->getData() < node->getData())
  65. {
  66. subRoot->setAHeight(subRoot->getAHeight()+1);
    1. subRoot = subRoot->getRight();
    1. }
    1. }
    1. subRoot = poRoot;
  67. AVLNode* a = poRoot;
  68. AVLNode* b = NULL;
  69. AVLNode* c = NULL;
  70. AVLNode* tempRoot = NULL;
  71. if (a->getAbsoluteAHeight() > 1)
  72. {
  73. if (subRoot->getData() > node->getData())
  74. {
  75. b = subRoot->getLeft();
  76. if (a->getAHeight()* b->getAHeight() > 0)
  77. {
  78. //LLRotate
  79. tempRoot = LLRotate(a,b);
    1. }
  80. else
  81. {
  82. //LRRotate
  83. c = b->getRight();
  84. tempRoot =LRRotate(a,b,c);
  85. }
    1. }
  86. else if (subRoot->getData() < node->getData())
  87. {
  88. b = subRoot->getRight();
  89. if (a->getAHeight()* b->getAHeight() > 0)
  90. {
  91. //RRRotate
  92. tempRoot = RRRotate(a,b);
  93. }
  94. else
  95. {
  96. //RLRotate
  97. c = b->getLeft();
  98. tempRoot =RLRotate(a,b,c);
  99. }
  100. }
  101. if (ppoRoot!=NULL)
  102. {
  103. if (ppoRoot->getData() > tempRoot->getData())
  104. {
  105. ppoRoot->setLeft(tempRoot);
  106. }
  107. else
  108. {
  109. ppoRoot->setRight(tempRoot);
  110. }
  111. }
  112. else
  113. {
  114. this ->head = tempRoot;
  115. }
  116. }
      1. }
    1. }

再看删除操作。

采用的是 http://www.cs.uga.edu/~eileen/2720/Notes/AVLTrees-II.ppt
这个ppt介绍的删除操作。

因为删除操作要反遍历到树根,所以这里无奈采用是递归操作。

bool deleteNode(AVLNode* subRoot, AVLNode* prev, T& node);

这个操作返回值:如果子树树高变化,那么返回true,否则返回false。

1.如果子树为Null,函数返回false

2.比较subRoot里的data值和node中的data值。

A.如果subRoot->data<
node.data,需要递归下右子树,如果这个递归返回true,将subRoot的平衡因子调整为-1,如果为false就return false。

B.subRoot->data >
node.data需要递归下左子树,如果这个递归返回true,将subRoot的平衡因子调整为+1,如果为false就return false。

C.subRoot->data == node.data.

1)如果此时subRoot只有一个孩子或者没有孩子,那么删除时树高一定会改变。另外做一个简单的删除操作即可。该左孩子代替此节点还是右孩子代替它,如何代替其实
和BinarySearchTree一样。再return true

2)如果有两个孩子,去左子树中找到替代品,然后将这个subRoot的数据域完全变为此替代品后,去左子树中用再用deleteNode方法将替代品删除。如果de
leteNode操作返回true,那么显然subRoot的平衡因子要加1.

3.如果subRoot的平衡因子已经为2或者-2,那么以subRoot为根开始调整。

A.如果调整后subRoot平衡因子为0,return true

B.不为0,return false。

下面是实际代码

  1. bool deleteNode(AVLNode* subRoot, AVLNode* prev, T& node)
  2. {
  3. if (subRoot == NULL)
  4. {
  5. return false ;
  6. }
  7. bool isChangeHeight = false ;
  8. if (subRoot->getData() > node)
  9. {
  10. isChangeHeight = deleteNode(subRoot->getLeft(),subRoot,node);
  11. if (isChangeHeight)
  12. {
  13. subRoot->setAHeight(subRoot->getAHeight()+1);
  14. }
    1. }
  15. else if (subRoot->getData() < node)
  16. {
  17. isChangeHeight = deleteNode(subRoot->getRight(),subRoot,node);
  18. if (isChangeHeight)
  19. {
  20. subRoot->setAHeight(subRoot->getAHeight()-1);
  21. }
    1. }
  22. else
  23. {
  24. AVLNode* assignNode = NULL;
  25. if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
  26. {
  27. // no child
    1. isChangeHeight = true ;
  28. deleteNode(subRoot,prev,assignNode);
  29. return isChangeHeight;
  30. }
  31. else if (subRoot->getLeft() == NULL && subRoot->getRight() != NULL)
  32. {
  33. // no left child
  34. isChangeHeight = true ;
  35. assignNode = subRoot->getRight();
  36. deleteNode(subRoot,prev,assignNode);
  37. return isChangeHeight;
    1. }
  38. else if (subRoot->getRight() == NULL && subRoot->getLeft() != NULL)
  39. {
  40. // no right chlid
  41. isChangeHeight = true ;
  42. assignNode = subRoot->getLeft();
  43. deleteNode(subRoot,prev,assignNode);
  44. return isChangeHeight;
  45. }
  46. else
  47. {
  48. // have both children
  49. assignNode = getMaxNode(subRoot->getLeft());
  50. T data = assignNode->getData();
  51. bool isChange = deleteNode(subRoot->getLeft(),subRoot,data);
  52. cout << "use " << data<< " replace " << subRoot->getData()<<endl;
  53. subRoot->setData(data); // copy all data to subRoot
    1. if (isChange)
  54. {
  55. subRoot->setAHeight(subRoot->getAHeight()+1);
  56. }
  57. }
    1. if (subRoot->getAbsoluteAHeight() == 2)
  58. {
  59. AVLNode* a = subRoot;
  60. AVLNode* b = NULL;
  61. AVLNode* c = NULL;
  62. AVLNode* tempRoot = NULL;
  63. if (subRoot->getAHeight() == 2)
  64. {
  65. // move to left
  66. b = subRoot->getRight();
  67. switch (b->getAHeight())
  68. {
  69. case 1:
  70. tempRoot = RRRotate(a,b);
  71. isChangeHeight = true ;
  72. break ;
  73. case -1:
  74. c = b->getLeft();
  75. tempRoot = RLRotate(a,b,c);
  76. isChangeHeight = true ;
  77. break ;
  78. case 0:
  79. tempRoot = RRRotate(a,b);
  80. isChangeHeight = false ;
  81. break ;
  82. }
    1. }
  83. else if (subRoot->getAHeight() == -2)
  84. {
  85. // move to right
  86. b = subRoot->getLeft();
  87. switch (b->getAHeight())
  88. {
  89. case 1:
  90. c = b->getRight();
  91. tempRoot = LRRotate(a,b,c);
  92. isChangeHeight = true ;
    1. break ;
  93. case -1:
  94. tempRoot = LLRotate(a,b);
  95. isChangeHeight = true ;
  96. break ;
  97. case 0:
  98. tempRoot = LLRotate(a,b);
  99. isChangeHeight = false ;
  100. break ;
  101. }
    1. }
    1. if (prev == NULL)
  102. {
  103. this ->head = tempRoot;
  104. }
  105. else
  106. {
  107. if (prev->getData() > tempRoot->getData())
  108. {
  109. prev->setLeft(tempRoot);
  110. }
  111. else
  112. {
  113. prev->setRight(tempRoot);
  114. }
  115. }
  116. }
        1. }
    1. return isChangeHeight;
    1. }

最后贴上AVLTree的完整类代码

  1. #include “AVLNode.h”
    1. template< class T>
  2. class AVLTree
  3. {
  4. private :
  5. AVLNode* head;
    1. int getHeight(AVLNode* node)
  6. {
  7. if (node == NULL)
  8. {
  9. return 0;
  10. }
  11. else
  12. {
  13. int leftHeight = getHeight(node->getLeft());
  14. int rightHeight = getHeight(node->getRight());
  15. if (leftHeight > rightHeight)
  16. {
  17. return leftHeight+1;
  18. }
  19. else
  20. {
  21. return rightHeight+1;
  22. }
  23. }
  24. }
    1. int getAVLHeight(AVLNode* node)
  25. {
  26. if (node == NULL)
  27. {
  28. return 0;
  29. }
  30. else
  31. {
  32. int leftHeight = getHeight(node->getLeft());
  33. int rightHeight = getHeight(node->getRight());
  34. return rightHeight - leftHeight;
  35. }
  36. }
      1. void clearSubTree(AVLNode* node)
  37. {
  38. if (node != NULL)
  39. {
  40. clearSubTree(node->getLeft());
  41. clearSubTree(node->getRight());
  42. delete node;
  43. }
  44. }
    1. void printTree(AVLNode* subTree, int count)
  45. {
  46. if (subTree!=NULL)
  47. {
    1. printTree(subTree->getRight(), count+1);
  48. for ( int i = 0; i < count; i++)
  49. {
  50. cout << "   " ;
  51. }
  52. cout <getData()<<endl;
  53. printTree(subTree->getLeft(),count+1);
  54. }
  55. }
      1. void printInMidOrder(AVLNode* subTree)
  56. {
  57. if (subTree!=NULL)
  58. {
  59. printInMidOrder(subTree->getLeft());
      1. cout <getData()<<endl;
  60. printInMidOrder(subTree->getRight());
  61. }
  62. }
    1. bool isPossibleNode(AVLNode* node, AVLNode* comNode)
  63. {
  64. if (node != NULL && node->getAbsoluteAHeight() == 1)
  65. {
  66. return true ;
  67. }
  68. return false ;
  69. }
    1. void insertNode(AVLNode* node)
  70. {
  71. AVLNode* subRoot = this ->head;
  72. if (subRoot == NULL)
  73. {
  74. subRoot = node;
  75. return ;
  76. }
  77. AVLNode* ppoRoot = NULL;
  78. AVLNode* poRoot = NULL;
  79. AVLNode* pRoot = NULL;
        1. poRoot = subRoot;
    1. while (subRoot != NULL)
  80. {
  81. pRoot = subRoot;
  82. if (subRoot->getData() > node->getData())
  83. {
    1. if (isPossibleNode(subRoot->getLeft(),node))
  84. {
  85. poRoot = subRoot->getLeft();
  86. ppoRoot = subRoot;
  87. }
  88. subRoot = subRoot->getLeft();
    1. }
  89. else if (subRoot->getData() < node->getData())
  90. {
    1. if (isPossibleNode(subRoot->getRight(),node))
  91. {
  92. poRoot = subRoot->getRight();
  93. ppoRoot = subRoot;
  94. }
  95. subRoot = subRoot->getRight();
  96. }
  97. else
  98. {
  99. throw “the same key” ;
  100. }
  101. }
    1. bool isChangeHeight = false ;
  102. if (pRoot->getData() > node->getData())
  103. {
    1. pRoot->setLeft(node);
  104. if (pRoot->getRight() == NULL)
  105. {
  106. isChangeHeight = true ;
  107. }
  108. else
  109. {
  110. pRoot->setAHeight(pRoot->getAHeight()-1);
  111. }
  112. }
  113. else if (pRoot->getData() < node->getData())
  114. {
    1. pRoot->setRight(node);
  115. if (pRoot->getLeft() == NULL)
  116. {
  117. isChangeHeight = true ;
  118. }
  119. else
  120. {
  121. pRoot->setAHeight(pRoot->getAHeight()+1);
  122. }
  123. }
      1. if (poRoot != NULL && isChangeHeight)
  124. {
  125. // s->a update Height
  126. subRoot = poRoot;
  127. while (subRoot != node)
  128. {
  129. if (subRoot->getData() > node->getData())
  130. {
  131. subRoot->setAHeight(subRoot->getAHeight()-1);
    1. subRoot = subRoot->getLeft();
    1. }
  132. else if (subRoot->getData() < node->getData())
  133. {
  134. subRoot->setAHeight(subRoot->getAHeight()+1);
    1. subRoot = subRoot->getRight();
    1. }
    1. }
    1. subRoot = poRoot;
  135. AVLNode* a = poRoot;
  136. AVLNode* b = NULL;
  137. AVLNode* c = NULL;
  138. AVLNode* tempRoot = NULL;
  139. if (a->getAbsoluteAHeight() > 1)
  140. {
  141. if (subRoot->getData() > node->getData())
  142. {
  143. b = subRoot->getLeft();
  144. if (a->getAHeight()* b->getAHeight() > 0)
  145. {
  146. //LLRotate
  147. tempRoot = LLRotate(a,b);
    1. }
  148. else
  149. {
  150. //LRRotate
  151. c = b->getRight();
  152. tempRoot =LRRotate(a,b,c);
  153. }
    1. }
  154. else if (subRoot->getData() < node->getData())
  155. {
  156. b = subRoot->getRight();
  157. if (a->getAHeight()* b->getAHeight() > 0)
  158. {
  159. //RRRotate
  160. tempRoot = RRRotate(a,b);
  161. }
  162. else
  163. {
  164. //RLRotate
  165. c = b->getLeft();
  166. tempRoot =RLRotate(a,b,c);
  167. }
  168. }
  169. if (ppoRoot!=NULL)
  170. {
  171. if (ppoRoot->getData() > tempRoot->getData())
  172. {
  173. ppoRoot->setLeft(tempRoot);
  174. }
  175. else
  176. {
  177. ppoRoot->setRight(tempRoot);
  178. }
  179. }
  180. else
  181. {
  182. this ->head = tempRoot;
  183. }
  184. }
      1. }
    1. }
      1. // return the subRoot
  185. //        a                   b
  186. //       /                  /   /
  187. //      b        ->        c     a
  188. //     /
  189. //    c
  190. AVLNode* LLRotate(AVLNode* a, AVLNode* b)
  191. {
  192. a->setLeft(b->getRight());
  193. b->setRight(a);
    1. a->setAHeight(0);
  194. b->setAHeight(0);
  195. //a->setAHeight(getAVLHeight(a));
  196. //b->setAHeight(getAVLHeight(b));
  197. return b;
  198. }
    1. // return the subRoot
  199. //        a                      b
  200. //          /                  /   /
  201. //            b        ->     a     c
  202. //              /
  203. //                c
  204. AVLNode* RRRotate(AVLNode* a, AVLNode* b)
  205. {
  206. a->setRight(b->getLeft());
  207. b->setLeft(a);
    1. a->setAHeight(0);
  208. b->setAHeight(0);
  209. //a->setAHeight(getAVLHeight(a));
  210. //b->setAHeight(getAVLHeight(b));
  211. return b;
  212. }
      1. // return the subRoot
  213. //        a                      c
  214. //          /                  /   /
  215. //            b        ->     a     b
  216. //           /                 /
  217. //          c                   d
  218. //         /
  219. //        d
  220. AVLNode* RLRotate(AVLNode* a, AVLNode* b, AVLNode* c)
  221. {
    1. b->setLeft(c->getRight());
  222. c->setRight(b);
  223. a->setRight(c->getLeft());
  224. c->setLeft(a);
      1. //a->setAHeight(getAVLHeight(a));
  225. //c->setAHeight(getAVLHeight©);
  226. //b->setAHeight(getAVLHeight(b));
    1. if (c->getAbsoluteAHeight() == 1)
  227. {
  228. if (b->getAHeight() == 0)
  229. {
  230. b->setAHeight(-1);
  231. }
  232. else
  233. {
  234. b->setAHeight(0);
  235. }
  236. a->setAHeight(1);
  237. c->setAHeight(0);
    1. }
  238. else
  239. {
  240. if (b->getAHeight() == 0)
  241. {
  242. b->setAHeight(-1);
  243. }
  244. else
  245. {
  246. b->setAHeight(0);
  247. }
  248. a->setAHeight(0);
  249. c->setAHeight(0);
    1. }
      1. return c;
  250. }
    1. // return the subRoot
  251. //        a                      c
  252. //       /                     /   /
  253. //      b              ->     b     a
  254. //       /                         /
  255. //        c                       d
  256. //         /
  257. //          d
  258. AVLNode* LRRotate(AVLNode* a, AVLNode* b, AVLNode* c)
  259. {
  260. b->setRight(c->getLeft());
  261. c->setLeft(b);
  262. a->setLeft(c->getRight());
  263. c->setRight(a);
      1. //a->setAHeight(getAVLHeight(a));
  264. //c->setAHeight(getAVLHeight©);
  265. //b->setAHeight(getAVLHeight(b));
    1. if (c->getAbsoluteAHeight() == 1)
  266. {
  267. if (b->getAHeight() == 0)
  268. {
  269. b->setAHeight(1);
  270. }
  271. else
  272. {
  273. b->setAHeight(0);
  274. }
    1. a->setAHeight(-1);
  275. c->setAHeight(0);
    1. }
  276. else
  277. {
    1. if (b->getAHeight() == 0)
  278. {
  279. b->setAHeight(1);
  280. }
  281. else
  282. {
  283. b->setAHeight(0);
  284. }
  285. a->setAHeight(0);
  286. c->setAHeight(0);
    1. }
          1. return c;
  287. }
      1. AVLNode* getMaxNode(AVLNode* subRoot)
  288. {
  289. if (subRoot == NULL)
  290. {
  291. return NULL;
  292. }
  293. if (subRoot->getRight() == NULL)
  294. {
  295. return subRoot;
  296. }
  297. else
  298. {
  299. return getMaxNode(subRoot->getRight());
  300. }
  301. }
    1. void deleteNode(AVLNode* subRoot, AVLNode* prev,AVLNode* assignNode)
  302. {
  303. if (prev == NULL)
  304. {
  305. this ->head = assignNode;
    1. }
  306. else
  307. {
  308. if (prev->getLeft() == subRoot)
  309. {
  310. prev->setLeft(assignNode);
    1. }
  311. else if (prev->getRight() == subRoot)
  312. {
  313. prev->setRight(assignNode);
    1. }
  314. }
    1. delete subRoot;
  315. }
    1. bool deleteNode(AVLNode* subRoot, AVLNode* prev, T& node)
  316. {
  317. if (subRoot == NULL)
  318. {
  319. return false ;
  320. }
  321. bool isChangeHeight = false ;
  322. if (subRoot->getData() > node)
  323. {
  324. isChangeHeight = deleteNode(subRoot->getLeft(),subRoot,node);
  325. if (isChangeHeight)
  326. {
  327. subRoot->setAHeight(subRoot->getAHeight()+1);
  328. }
    1. }
  329. else if (subRoot->getData() < node)
  330. {
  331. isChangeHeight = deleteNode(subRoot->getRight(),subRoot,node);
  332. if (isChangeHeight)
  333. {
  334. subRoot->setAHeight(subRoot->getAHeight()-1);
  335. }
    1. }
  336. else
  337. {
  338. AVLNode* assignNode = NULL;
  339. if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
  340. {
  341. // no child
    1. isChangeHeight = true ;
  342. deleteNode(subRoot,prev,assignNode);
  343. return isChangeHeight;
  344. }
  345. else if (subRoot->getLeft() == NULL && subRoot->getRight() != NULL)
  346. {
  347. // no left child
  348. isChangeHeight = true ;
  349. assignNode = subRoot->getRight();
  350. deleteNode(subRoot,prev,assignNode);
  351. return isChangeHeight;
    1. }
  352. else if (subRoot->getRight() == NULL && subRoot->getLeft() != NULL)
  353. {
  354. // no right chlid
  355. isChangeHeight = true ;
  356. assignNode = subRoot->getLeft();
  357. deleteNode(subRoot,prev,assignNode);
  358. return isChangeHeight;
  359. }
  360. else
  361. {
  362. // have both children
  363. assignNode = getMaxNode(subRoot->getLeft());
  364. T data = assignNode->getData();
  365. bool isChange = deleteNode(subRoot->getLeft(),subRoot,data);
  366. cout << "use " << data<< " replace " << subRoot->getData()<<endl;
  367. subRoot->setData(data); // copy all data to subRoot
    1. if (isChange)
  368. {
  369. subRoot->setAHeight(subRoot->getAHeight()+1);
  370. }
  371. }
    1. if (subRoot->getAbsoluteAHeight() == 2)
  372. {
  373. AVLNode* a = subRoot;
  374. AVLNode* b = NULL;
  375. AVLNode* c = NULL;
  376. AVLNode* tempRoot = NULL;
  377. if (subRoot->getAHeight() == 2)
  378. {
  379. // move to left
  380. b = subRoot->getRight();
  381. switch (b->getAHeight())
  382. {
  383. case 1:
  384. tempRoot = RRRotate(a,b);
  385. isChangeHeight = true ;
  386. break ;
  387. case -1:
  388. c = b->getLeft();
  389. tempRoot = RLRotate(a,b,c);
  390. isChangeHeight = true ;
  391. break ;
  392. case 0:
  393. tempRoot = RRRotate(a,b);
  394. isChangeHeight = false ;
  395. break ;
  396. }
    1. }
  397. else if (subRoot->getAHeight() == -2)
  398. {
  399. // move to right
  400. b = subRoot->getLeft();
  401. switch (b->getAHeight())
  402. {
  403. case 1:
  404. c = b->getRight();
  405. tempRoot = LRRotate(a,b,c);
  406. isChangeHeight = true ;
    1. break ;
  407. case -1:
  408. tempRoot = LLRotate(a,b);
  409. isChangeHeight = true ;
  410. break ;
  411. case 0:
  412. tempRoot = LLRotate(a,b);
  413. isChangeHeight = false ;
  414. break ;
  415. }
    1. }
    1. if (prev == NULL)
  416. {
  417. this ->head = tempRoot;
  418. }
  419. else
  420. {
  421. if (prev->getData() > tempRoot->getData())
  422. {
  423. prev->setLeft(tempRoot);
  424. }
  425. else
  426. {
  427. prev->setRight(tempRoot);
  428. }
  429. }
  430. }
        1. }
    1. return isChangeHeight;
    1. }
        1. public :
  431. AVLTree(T& data)
  432. {
  433. head = new AVLNode(data);
  434. }
    1. AVLTree(AVLNode* head)
  435. {
  436. clearSubTree( this ->head);
  437. this ->head = head;
  438. }
    1. ~AVLTree()
  439. {
  440. clearSubTree(head);
  441. }
    1. void printTree()
  442. {
  443. printTree( this ->head,0);
  444. }
    1. void printInMidOrder()
  445. {
  446. printInMidOrder( this ->head);
  447. }
      1. void insertNode(T& data)
  448. {
  449. insertNode( new AVLNode(data));
    1. }
    1. void deleteNode(T& data)
  450. {
  451. deleteNode( this ->head,NULL,data);
  452. }
  453. /bool isUnbalancePoint(AVLNode node, AVLNode* compareNode)
  454. {
    1. if(node->getAbsoluteAHeight() == 1)
  455. {
    1. if(node->getAHeight == 1 && node->getData() < compareNode->getData() )
  456. {
  457. return true;
  458. }
  459. else if(node->getAHeight == -1 && node->getData() > compareNode->getData())
  460. {
  461. return true;
  462. }
  463. }
  464. return false;
  465. }*/
      1. };

BinarySearchTree和BinaryTree其实可以使用相同的构造和析构函数,所以继承吧。懒得再写一遍

template
class BinarySearchTree:public BinaryTree
{
public:
BinarySearchTree(T& data):BinaryTree(data)
{

}

~BinarySearchTree()
{

}
void insertNode(TreeNode* node)
{
insertNode(this->head,node);
}

void insertNode(T& data)
{
TreeNode* newNode = new TreeNode(data);
insertNode(this->head,newNode);
}

void deleteNode(T& data)
{
deleteNode(NULL,this->head,data);
}

TreeNode* searchNode(T& data)
{
return searchNode(this->head,data);
}

private:
TreeNode* insertNode(TreeNode* subTree,TreeNode* node)
{
if(subTree == NULL)
{

subTree = node;
}
else
{

if(subTree->getData() > node->getData())
{
subTree->setLeft(insertNode(subTree->getLeft(),node));

}
else if(subTree->getData() < node->getData())
{
subTree->setRight(insertNode(subTree->getRight(),node));
}
else
{
throw “insert same key”;
}
}
return subTree;
}

TreeNode* searchNode(TreeNode* subTree,T& data)
{
if(subTree == NULL)
{
return NULL;
}
else
{
if(subTree->getData() > data)
{
searchNode(subTree->getLeft(),data);
}
else if(subTree->getData() < data)
{
searchNode(subTree->getRight(),data);
}
else
{
return subTree;
}
}

}

void deleteNode(TreeNode* pSubTree,TreeNode* subTree,T& data)
{
if(subTree == NULL)
{
return ;
}
else
{
if(subTree->getData() > data)
{
deleteNode(subTree,subTree->getLeft(),data);
}
else if(subTree->getData() < data)
{
deleteNode(subTree,subTree->getRight(),data);
}
else
{
TreeNode* assignNode = NULL;
if(subTree->getLeft() == NULL && subTree->getRight() == NULL)
{
// no left, no right

}
else if(subTree->getLeft() == NULL && subTree->getRight() != NULL)
{
// no left child, but has right child
assignNode = subTree->getRight();
}
else if(subTree->getLeft() != NULL && subTree->getRight() == NULL)
{
// no right, has left child
assignNode = subTree->getLeft();
}
else
{
// Or has both right and left child
TreeNode* parent = NULL;
assignNode = getMaxNode(subTree->getLeft(),&parent);
if(parent!= NULL)
{
parent->setRight(NULL);
assert(assignNode!=NULL);
assignNode->setLeft(subTree->getLeft());
}
assignNode->setRight(subTree->getRight());
}
if(pSubTree != NULL)
{

if(pSubTree->getLeft() == subTree)
{
pSubTree->setLeft(assignNode);
}
else
{
pSubTree->setRight(assignNode);
}
}
else
{
this->head = assignNode;
}
delete subTree;
}
}
}

TreeNode* getMaxNode(TreeNode* subTree,TreeNode** pNode)
{
if(subTree == NULL)
{
return NULL;
}
if(subTree->getRight()!= NULL)
{
pNode = &subTree;
return getMaxNode(subTree->getRight(),pNode);
}
else
{

return subTree;
}

}

};

关于二叉查找树,其实插入和查找是一个很简单是事情。只要学会递归遍历,就可以轻松的做到。对于删除操作,删除规则与被删除节点是否有左右孩子节点有关。

1.当无左右节点。直接删除

2.当有右节点无左节点。将此节点删除,并用右节点取代此节点。

3.当有左节点(不管有无右节点)。删除时,将此树中序遍历中该节点的前一个节点代替该节点,再将该节点删除。

所以第3点要做一个寻找该节点中序遍历的前一节点。其实就是该节点左子树中序遍历的最后一个节点,详见getMaxNode()函数。

先写一个树节点类。使用Temple也可以,不使用的话,使用特定类型,用法比较局限。不过本着“今天尽量不要做出今天不必要的决定”极限编程法制。做一个特殊类型的
BinaryTree,也未尝不可。

这里的TreeNode只有数据域。

  1. template < class T>
  2. class TreeNode
  3. {
  4. private :
  5. T data;
  6. TreeNode * left;
  7. TreeNode * right;
  8. public :
      1. TreeNode(T& data)
  9. {
  10. this ->data = data;
  11. this ->left = NULL;
  12. this ->right = NULL;
  13. }
    1. TreeNode(T& data,TreeNode* left, TreeNode* right)
  14. {
  15. this ->data = data;
  16. this ->left = left;
  17. this ->right = right;
  18. }
    1. ~TreeNode()
  19. {
    1. this ->left = NULL;
  20. this ->right = NULL;
  21. cout << “node (” << this ->data<< “) destory!” <<endl;
  22. // to do
  23. }
    1. T getData()
  24. {
  25. return data;
  26. }
    1. void setData(T& data)
  27. {
  28. this ->data = data;
  29. }
    1. TreeNode * getLeft()
  30. {
  31. return left;
  32. }
    1. void setLeft(TreeNode * left)
  33. {
  34. this ->left = left;
    1. }
    1. TreeNode * getRight()
  35. {
  36. return right;
  37. }
    1. void setRight(TreeNode* right)
  38. {
  39. this ->right = right;
  40. }
      1. };
    1. 下面是BinaryTree的实现。一般来说,一个BinaryTree最重要的函数就是构造和析构。基本的函数是遍历。

下面的类只实现了中序遍历,和树形打印。析构删除节点使用的是后序删除法。

  1. template < class T>
  2. class BinaryTree
  3. {
  4. protected :
  5. TreeNode* head;
    1. void clearSubTree(TreeNode* node)
  6. {
  7. if (node != NULL)
  8. {
  9. clearSubTree(node->getLeft());
  10. clearSubTree(node->getRight());
  11. delete node;
  12. }
  13. }
    1. void printTree(TreeNode* subTree, int count)
  14. {
  15. if (subTree!=NULL)
  16. {
    1. printTree(subTree->getRight(), count+1);
  17. for ( int i = 0; i < count; i++)
  18. {
  19. cout << " " ;
  20. }
  21. cout <getData()<<endl;
  22. printTree(subTree->getLeft(),count+1);
  23. }
  24. }
      1. void printInMidOrder(TreeNode* subTree)
  25. {
  26. if (subTree!=NULL)
  27. {
  28. printInMidOrder(subTree->getLeft());
      1. cout <getData()<<endl;
  29. printInMidOrder(subTree->getRight());
  30. }
  31. }
  32. public :
  33. BinaryTree(T& data)
  34. {
  35. head = new TreeNode(data);
  36. }
    1. BinaryTree(TreeNode* head)
  37. {
  38. this ->head = head;
  39. }
    1. ~BinaryTree()
  40. {
  41. clearSubTree(head);
  42. }
    1. void printTree()
  43. {
  44. printTree( this ->head,0);
  45. }
    1. void printInMidOrder()
  46. {
  47. printInMidOrder( this ->head);
  48. }
  49. };
    1. 如果BinaryTree中还有插入删除操作就好了。但是如何插入,如何删除必须按照一定的规则进行。所以就有后面的二叉查找树、AVLTree、SplayTree、RedBlackTree等各种类型的二叉树。

A:现在睡了吗?(23:30-01:10)

B:起床了吗?(07:30-08:30)

A:你起得真早(11:30-13:30)

B:你起得真晚(15:30-14:00)

A:你现在睡了吗?(23:30-01:10)

…周而复始

A:最近过的怎么样?

B:在家无聊

A:我也感觉很无聊…

…于是大家都不聊了…

暑假期间因为比较清闲,玩了很多游戏。有些是近几年的新游戏,有些是古老的游戏。

自己在玩游戏的过程中也总结出一些游戏设计上的心得。

下面一一介绍:

1.魔法师传奇。这个游戏最近几年出了第2部。可惜不知道是什么原因,画面是跳动的,而且进入游戏后动鼠标就死机。无奈只得将其删除。它是由曾经开发过《幽浮》的英国
著名游戏公司Mythos制作的幻想型实时策略/RPG游戏。

其主要的游戏要素是:升级、自我发展、魔法和兵种组合、兵种相克。

2.真三国无双。这个游戏升级到了第n个版本,似有无穷无尽的版本升级。但不管如何升级,不管是真三国无双还是无双大蛇。其主要的游戏要素是:各种华丽的人物招式(招
式中光影的渲染),人物的3D造型。其实其关卡总是那么几个,地形也没有变化。只是因为各个武将的不同等级会有不同的招式和武器增加了游戏的可玩性。但对于我这样的玩
家并不适用,自己用赵云打通关后,就删掉玩下个游戏了。

3.仙剑系列。这个游戏自95年开始我就在关注中。仙剑这几个版本都打过通关。仙剑系列的最大卖点就是具有浓郁的中国特色,诗词歌赋和熟悉的神仙鬼怪。风火雷土水五行
相克。其成功的主要原因并非其画面和过场动画多么漂亮,而在于其感人的情节。这或许就是RPG游戏的显著特点。想到RPG游戏就想到Diablo,下载了一个根本没有
人物对话的Diablo版本。结果到第三幕我就打不下去了,太枯燥了。根本不知道事件的前因后果,所以玩起来就感觉比同类RPG游戏费劲许多。所以RPG类游戏的显著
特点是:以曲折引人入胜的故事作为背景。至于单一结局还是多个结局其实并没有太多关系。因为很多人只玩出一个结局就不再继续玩了。当然骨灰级玩家例外。仙剑在彩蛋方面
做的不错,很多小宝物隐藏在各个隐蔽的地方。很多玩家其实并不是想通关,而是想收集到全部的物品。值得一提是的:中国的两大RPG系列游戏:仙剑和轩辕剑中的NPC人
物对话很有意思。另外音乐因素也是剧情中的关键因素。故事如果不能吸引人,那就要有好听的音乐。连音乐都很乏味,那就要有绚丽的画面。否则就只有自娱自乐了。这个情况
的代表作品好像是绝代双骄1,它好像就在最后有个刘德华和林青霞的电影片段。不过因其产生于自中国的90年代,所以不再细细追究。

4.魔法门之英雄无敌系列。这个系列的游戏都是战棋类游戏。只是从2D转换为了3D。最引人入胜的是各个种族的兵种和建筑。我一个搞设计的朋友很喜欢这款游戏。还给我
讲了些游戏中兵种3D设计的难易程度。基本的设计都是先设计骨架,然后在设计皮肤和渲染光影。结果发现“骷髅城”的兵种就是其他某一个种族的兵种去掉皮肤后的效果。听
说骨灰级玩家每一步都算计好了,没有多余的步数。但是对于大多数玩家而言,这款游戏就在于兵多拼兵少、兵强拼兵弱。所以此款游戏中大量的种族和地形弥补了普通玩家长时
间玩游戏的枯燥。

5.解谜游戏。此款游戏的游戏模式无外乎将各种物品放在正确的地方。暑假期间玩过几款:CSI——谋杀的三维、幽灵庄园和精密的仪器。游戏之所以能让我坚持不懈的玩通
关在于漂亮的CG和开始引入游戏的少许故事情节。

用C#的Thread做了一个简单计时器。为了让自己45分钟后就可以休息一次,45分钟过后会响音乐提示。

开始使用的TimeSpan相减的方式,在Thread的启动函数中也就是这样写的:

  1. ** public ** ** void ** CountTime()
  2. {
    1. ** while ** ( ** true ** )
  3. {
    1. TimeSpan tsNew = ** new ** TimeSpan(DateTime.Now.Ticks);
  4. TimeSpan tsIn = tsNew - tsOld;
    1. ** if ** (tsIn.Minutes >= 1)
  5. {
    1. ** while ** ( ** true ** )
  6. {
  7. TimeSpan tsNewer = ** new ** TimeSpan(DateTime.Now.Ticks);
  8. TimeSpan tsIner = tsNewer - tsNew;
    1. ** if ** (tsIner.Minutes >= 10)
  9. {
  10. //十分钟后线程重启
  11. tsOld = tsNew;
  12. ** break ** ;
  13. }
    1. }
    1. }
    1. }
  14. }

后来发现这种方法效率太低了。当然,可以使用Thread.Sleep(20);这个函数降低CPU占用时间。其实中间加入Thread.Sleep(20);就可明
显的降低CPU消耗。后来发现C#中的Thread中自带有函数join(),这个函数可以使线程等待一段时间。调用方法如下

th.Join(new TimeSpan(hours, minutes, seconds));在等待的这段时间里线程处于WaitSleepJoin状态。

当然也可以调用Thread.Sleep(millionseconds);这里提一下Sleep和Join的区别

当线程执行Sleep时系统就退出执行队列一段时间,当睡眠结束时,系统会产生一个时钟中断,从而使线程回到执行队列中恢复线程的执行。 ** Sleep方法如果
参数是0,代表这个线程应当挂起让其他等待的线程运行,这里cpu回重新分配控制权,也有可能是刚才的执行的程序。这样就会有cpu占用总是100%的情况发生。
** 有时你界面死了,但是你还是可以移动鼠标。如果是Timeout.Infinite,就代表将使线程休眠,直到它被调用 Thread.Interrupt
的另一个线程中断或被 Thread.Abort 中止为止。
如果父线程先于子线程结束,那么子线程将在父线程结束的同时被迫结束。Thread.Join()方法使父线程等待,直到子线程结束。 Join方法有返回值,当值
为true,代表线程终止。false的话代表线程在等待了那段时间后还未终止。如果在线程Unstarted状态时,调用join()就会有
ThreadStateException异常。如果线程已经终止,那么调用这个函数,会立即得到返回值。

例如下面的主程序

ThreadStart st = New ThreadStart(fun);

Thread th = new Thread(ThreadStart st);

th.Start();

Application.Exit();

//下面是fun函数

void fun()

{

while(true)

{

}

}

这段程序的唯一毛病就是有可能在主程序退出后,从线程还没有结束。(这个从线程真可怜…)

这里顺便再提一下线程的几个状态:

创建:当创建一个新进程时,也为该进程创建了一个线程。线程还可以创建新线程。

就绪:线程已获得除处理机外的所有资源。

运行:线程正在处理机上执行。

阻塞:线程因等待某事件而暂停运行。

终止:一个线程已完成。

但是C#的线程中多了几个状态:

Aborted,AbortRequested,Background,Running,Stopped,StopRequested,Suspended,Susp
endRequested,Unstarted,WaitSleepJoin。

Abort()将导致ThreadState.AbortRequested调用Abort()的线程获得控制权之后导致ThreadState.Aborted,A
bortRequested与Aborted的区别在于一个停止一个未停止。而Stopped则是线程终止。但是我反复试验多次发现当调用Abort()函数后,线程
状态会变为Stopped。如何变为Aborted状态,还在研究中。其他几个状态差不多。都是调用相应的函数会产生相应的状态请求,还有过一段时间才能到底相应的状
态。至于Unstarted是还未调用Start()函数,Running是调用Start()或者Resume()函数的结果。WaitSleepJoin是在等待
I/O,或者是调用Join()方法。 **
这里Join()和Sleep()方法的不同还在于调用Join()线程状态进入WaitSleepJoin,调用Sleep()线程状态还是Running。 **

挂起线程的方法是Suspend();调用这个方法后,线程处于SuspendRequest状态。Suspended()调用后如果线程仍然在执行join()方法
,因为Suspended()要让线程到达安全点之后它才可以将该线程挂起,此时那线程状态就是SuspendRequested|WaitSleepJoin。但是
这里的join里的时钟依然在计数。所以现在还不知道用什么方法来暂停这个join计数,当然也可以不使用join解决彻底暂停线程这个问题。现在不明白哪个Susp
ended()函数是干什么的,因为线程依旧在运行中。另外值得一提的是现在不提倡使用Suspend()和让线程调用Suspend()后再次恢复的Resume(
)方法。 ** 原因很简单,因为这两个方法是由另外的线程执行,另外的线程并不能准确的知道被Suspend()的线程处于何种状态,如某个类的构造函数执行时期
,或者析构等。所以用这个函数来同步很危险。 **


** 另外,要注意的是Thread.Sleep(n)这个n不能精确的控制时间。如果你认为要线程要隔多长时间,这个控制就有问题。如果当前的线程是一个前台线程,那么Thread.Sleep(n)就要在大于n的时间才能退出。如果是后台进程,当主程序退出后,这线程就再也不能唤醒…悲惨…所以一般也建议不用Thread.Sleep()函数。另外Sleep函数也不能用于同步.peter说程序的Sleep函数代表了一个很烂的设计。 **

做了个计时器竟然引发了这些问题…疯…

1. To make things special, you must believe it
special.只有自己认为与众不同,才能做到与众不同,否则依旧庸庸碌碌。

2. No secret is a secret.世上最秘密的莫过于本身就没有秘密。无异于甲方乙方中得那句话:打死我也不说。

3.There are no accident.一切绝非偶然。或许很多人的成功都被世人认为是偶然。可是没有积极的人生态度,也很难抓住那偶然的机遇。所以“一切
绝非偶然”这句用于时时告诫自己,积极进取、磨练自己。

4.You are too concerned with what was and what will be.Yesterday is history,
tomorrow is mistory, but today is a gift, that is why call it
present.不要太注重过去和未来。太看重了反而约束了手脚,不能在现在有所作为。把握现在,做好平时之事,才是掌控未来的关键。

听说这个影片是根据sky的故事改编。虽然不知道真假,但是情节的确很曲折搞笑。当然最后结果还是落入俗套。当然似乎没有啥电影不落入俗套的。

等到几个提示:

1.事在人为。积极进取得做好该做的事情。

2.心无杂念,一心向目的地进发。

3.小心身边的“战友”。不害人,但要提防别人不能害己。

电竞之王=神经病医院故事+魔兽术语+感情磨难+武侠苦练+点点励志

设计一个实用的小型通信录程序,具有查询和删除功能,并且能够打开或修改指定文件及将多个文件组成一个文件。它完全使用类来实现,充分体现了面向对象的程序设计特点。

成员基本信息:如姓名、性别、年龄、工作单位、通信地址、电话号码(固定电话和移动电话)、 E-MAIL 等。

需求有些太笼统,不过笼统自有笼统的好处,可以充分发挥自己的想象力不是??

0%