菲波那契堆--一份高级数据结构的作业。实现了包括插入节点

   y->right = y;
   y->left = y;
   x->child = y;
  }  
  ++(x->degree);
  y->childcut = false;

 }

 /* 将node从parent的子女中删除 */
 void Cut(Node<key_type> * node, Node<key_type> * parent){
  if(node = node->right){
   node->right = node->left = node;
   parent->child = 0;
  }else{
   node->right->left = node->left;
   node->left->right = node->right;   
  }
  (parent->degree)--;
  node->parent = 0;
  node->childcut = false;
 }
 
 /* 瀑布修剪 */
 void CascadingCut(Node<key_type> * node){
  Node<key_type> * z = node->parent;
  if(z){
   if(z->childcut == false){
    z->childcut = true;
   }else{
    Cut(node, z);
    CascadingCut(z); /* 递归调用瀑布修剪 */
   }
  }
 }

public:
 Node<key_type> * min;
 unsigned long n;

};

int main(){
 
 FibonacciHeap<int>  MyHeap;     /* 初始化FibonacciHeap对象 */ 
 fstream output("test_log.txt", ios::out); /* 创建用于记录测试结果的文件 */

 cout << "FibonacciHeap Test : " << "Powered By lbblscy" << endl;
 output << "FibonacciHeap Test : " << "Powered By lbblscy" << endl;
 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 /* 开始进行插入测试 */
 cout << "FibonacciHeap Test 1 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;
 output << "FibonacciHeap Test 1 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;

 Node<int> * TempNode;      /* FibonacciHeap结点对象 */
 srand((unsigned int)(time(NULL)%10000)); /* 将当前时间作为随机数发生器的种子 */
 int recoder[MAX_NUM], temp_key, i = 0, j = 0, flag = 0;

 for(i = 0; i < INSERT_NUM; i++){

  /* 确保每次生成不同的随机数进行插入测试 */
  do{
   flag = 0;
   temp_key = int(rand()/10);
   for(j = 0; j < MAX_NUM; j++){
    if(recoder[j] == temp_key){
     flag = 1;
     break;
    }
   }
  }while(flag);
  
  cout << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  output << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  TempNode = new Node<int>(temp_key);
  MyHeap.Insert(TempNode); /* 插入堆中 */
  cout << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
  output << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
 }

 cout << endl << "FibonacciHeap Test 1 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 1 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 cout << endl << "FibonacciHeap Test 2 : Delete " << DEL_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 2 : Delete " << DEL_NUM << " Nodes!" << endl << endl;

 /* 开始进行删除最小元素测试 */
 for(i = 0; i < DEL_NUM; i++){
  cout << "#Loop " << i << "  " << '\t';
  output << "#Loop " << i << "  " << '\t';
  TempNode = MyHeap.GetMinimum();
  if(TempNode){
   cout << "Last Minimum Key : " << TempNode->GetKey() << " " << '\t' << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
   output << "Last Minimum Key : " << TempNode->GetKey() << " " << '\t' << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
  }else{
   cout << "Error : The FibonacciHeap has already been empty!" << endl;
   output << "Error : The FibonacciHeap has already been empty!" << endl;
  }
 }

 cout << endl << "FibonacciHeap Test 2 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 2 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;
 
 /* 开始进行二次插入测试，为了测试任一结点的删除操作 */

 /* 
  FibonacciHeap结点指针数组，
  用于测试任一结点的删除与减少key的操作
  每次生成的新结点的指针存入该数组中
 */
 Node<int> ** A = new Node<int> *[(MyHeap.Size() + INSERT_NUM) * sizeof(Node<int>*)];

 cout << endl << "FibonacciHeap Test 3 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 3 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;

 for(i = 0; i < INSERT_NUM; i++){

  /* 确保每次生成不同的随机数进行插入测试 */
  do{
   flag = 0;
   temp_key = int(rand()/10);
   for(j = 0; j < MAX_NUM; j++){
    if(recoder[j] == temp_key){
     flag = 1;
     break;
    }
   }
  }while(flag);

  cout << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  output << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  TempNode = new Node<int>(temp_key);
  A[i] = MyHeap.Insert(TempNode); /* 插入堆中 */
  cout << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
  output << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
 }

 cout << endl << "FibonacciHeap Test 3 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 3 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 /* 开始进行任一结点的删除操作测试 */
 
 cout << endl << "FibonacciHeap Test 4 : Random Delete " << RANDOM_DEL_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 4 : Random Delete " << RANDOM_DEL_NUM << " Nodes!" << endl << endl;

 for(i = 0; i < RANDOM_DEL_NUM; i++){

  /* 确保每次生成不同的随机数进行随机删除测试 */
  do{
   flag = 0;
   temp_key = int(rand()%MyHeap.Size());
   for(j = 0; j < MAX_NUM; j++){
    if(recoder[j] == temp_key){
     flag = 1;
     break;
    }
   }
  }while(flag);

  Node<int> * DELNOD = MyHeap.DeleteNode(A[temp_key]);
  cout << "#Loop " << i << "  " << '\t' << "Random Node : " << temp_key << "  " << '\t' << "Key Value : " << DELNOD->GetKey() << endl;
  output << "#Loop " << i << "  " << '\t' << "Random Node : " << temp_key << "  " << '\t' << "Key Value : " << DELNOD->GetKey() << endl;
  
 }
 
 delete[] A; /* 释放数组空间 */

 cout << endl << "FibonacciHeap Test 4 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 4 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 /* 开始进行三次插入测试，为了测试任一结点的减少key的操作 */

 /* 
  FibonacciHeap结点指针数组，
  用于测试任一结点的删除与减少key的操作
  每次生成的新结点的指针存入该数组中
 */
 A = new Node<int> *[(MyHeap.Size() + INSERT_NUM) * sizeof(Node<int>*)];

 cout << endl << "FibonacciHeap Test 5 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 5 : Insert " << INSERT_NUM << " Nodes!" << endl << endl;

 for(i = 0; i < INSERT_NUM; i++){

  /* 确保每次生成不同的随机数进行插入测试 */
  do{
   flag = 0;
   temp_key = int(rand()/10);
   for(j = 0; j < MAX_NUM; j++){
    if(recoder[j] == temp_key){
     flag = 1;
     break;
    }
   }
  }while(flag);

  cout << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  output << "#Loop " << i << "  " << '\t' << "Current Key : " << temp_key << "  " << '\t';
  TempNode = new Node<int>(temp_key);
  A[i] = MyHeap.Insert(TempNode); /* 插入堆中 */
  cout << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
  output << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
 }

 cout << endl << "FibonacciHeap Test 5 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 5 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 /* 开始进行任一结点的key值减少操作测试 */
 
 cout << endl << "FibonacciHeap Test 6 : Random Decrease Key " << RANDOM_DEL_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 6 : Random Decrease Key " << RANDOM_DEL_NUM << " Nodes!" << endl << endl;
 int temp_key_value;
 for(i = 0; i < RANDOM_MOD_NUM; i++){

  /* 确保每次生成不同的随机数进行随机删除测试 */
  do{
   flag = 0;
   temp_key = int(rand()%INSERT_NUM);
   for(j = 0; j < MAX_NUM; j++){
    if(recoder[j] == temp_key || A[temp_key] == NULL){
     flag = 1;
     break;
    }
   }
  }while(flag);
  //cout << (int)A[temp_key] << endl;
  temp_key_value = A[temp_key]->GetKey();
  Node<int> * RANDOM = MyHeap.DecreaseKey(A[temp_key], temp_key);
  cout << "#Loop " << i << "  " << '\t' << "Random Node Key : " << temp_key_value << " " << "\t\t" << "Current Key Value : " << RANDOM->GetKey() << endl;
  output << "#Loop " << i << "  " << '\t' << "Random Node Key : " << temp_key_value << " " << "\t\t" << "Current Key Value : " << RANDOM->GetKey() << endl;
  
 }
 
 delete[] A;

 cout << endl << "FibonacciHeap Test 6 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 6 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 cout << endl << "FibonacciHeap Test 7 : Delete " << DEL_NUM << " Nodes!" << endl << endl;
 output << endl << "FibonacciHeap Test 7 : Delete " << DEL_NUM << " Nodes!" << endl << endl;

 /* 开始进行第二次删除最小元素测试 */
 for(i = 0; i < DEL_NUM; i++){
  cout << "#Loop " << i << "  " << '\t';
  output << "#Loop " << i << "  " << '\t';
  TempNode = MyHeap.GetMinimum();
  if(TempNode){
   cout << "Last Minimum Key : " << TempNode->GetKey() << " " << '\t' << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
   output << "Last Minimum Key : " << TempNode->GetKey() << " " << '\t' << "Current Minimum Key : " << MyHeap.min->GetKey() << endl;
  }else{
   cout << "Error : The FibonacciHeap has already been empty!" << endl;
   output << "Error : The FibonacciHeap has already been empty!" << endl;
  }
 }

 cout << endl << "FibonacciHeap Test 7 Finished! "<< endl << endl;
 output << endl << "FibonacciHeap Test 7 Finished! "<< endl << endl;

 cout << "*****************************************************************************" << endl;
 output << "*****************************************************************************" << endl;

 cout << endl << "All FibonacciHeap Test  Finished! "<< endl << endl;
 output << endl << "All FibonacciHeap Test  Finished! "<< endl << endl;

 return 0;
}





Trackback: http://tb.donews.net/TrackBack.aspx?PostId=1153388