指數樹實現

Question

我試圖實現從文件指數樹，但這裏是在代碼中一個地方，讓人聽不清楚，我如何實現它：

#include<iostream> 
using namespace std; 
struct node 
{ 
    int level; 
    int count; 
    node **child; 
    int data[]; 

}; 
int binary_search(node *ptr,int element) 
{ 
    if(element>ptr->data[ptr->count-1]) return ptr->count; 
    int start=0; 
    int end=ptr->count-1; 
    int mid=start+(end-start)/2; 
    while(start<end) 
    { 
     if(element>ptr->data[mid]) { start=mid+1;} 
     else 
     { 
      end=mid; 
     } 

     mid=start+(end-start)/2; 

    } 

    return mid; 
} 
void insert(node *root,int element) 
{ 
    node *ptr=root,*parent=NULL; 
    int i=0; 
    while(ptr!=NULL) 
    { 

     int level=ptr->level,count=ptr->count; 
     i=binary_search(ptr,element); 
     if(count<level){ 
      for(int j=count;j<=i-1;j--) 
       ptr->data[j]=ptr->data[j-1]; 
     } 
      ptr->data[i]=element; 
      ptr->count=count+1; 
      return ; 

     } 

    parent=ptr,ptr=ptr->child[i]; 

    //Create a new Exponential Node at ith child of parent and 
//insert element in that 

    return ; 

} 
int main() 
{ 


return 0; 
} 

下面是紙我一個鏈接是指： http://www.ijcaonline.org/volume24/number3/pxc3873876.pdf 這個地方是在評論中，我怎麼能創建一個新的指數節點在i級？喜歡這個？

parent->child[i]=new node; 
insert(parent,element); 

Answer 1

在該結構的端部的空數組的存在指示這是C樣式碼而不是C++（這是一個C Hack for flexible arrays）。我會繼續使用C風格的代碼，因爲慣用的C++代碼會更喜歡將標準容器用於子代和數據成員。

以下代碼的一些註釋和評論：

• 有一定數量的與僞代碼的鏈接文件到一個地步，這是更好地忽略它，從零開始開發的代碼問題。縮進級別不清楚循環結束，所有循環索引不正確，查找插入點的檢查是不正確的，等等......
• 我沒有包括任何刪除已分配內存的代碼，所以代碼會按原樣泄漏。
• 零大小的數組可能不被所有的編譯器支持（我相信這是一個C99功能）。例如，VS2010給我發出警告C4200說它不會生成默認的複製/分配方法。
• 我添加了createNode()函數，它給出瞭如何在給定級別分配節點的原始問題的答案。
• 添加了一個非常基本的測試，似乎可以正常工作，但是在我對代碼感到滿意之前需要進行更徹底的測試。
• 除了不正確的僞碼之外，紙張還有其他一些錯誤或者至少有問題的內容。例如，關於圖2，它說「這清楚地表明圖的斜率是線性的」，因爲圖很明顯不是線性的。即使作者的意思是「接近線性」，它至少也能延伸真相。我也會對他們用於測試的整數集合感興趣，而這些整數似乎沒有被提及。我假定他們使用了一個隨機集合，但我希望至少看到幾組隨機數以及幾個預定義的集合，例如已經排序或反向排序的集合。

。

int binary_search(node *ptr, int element) 
{ 
    if (ptr->count == 0) return 0; 
    if (element > ptr->data[ptr->count-1]) return ptr->count; 

    int start = 0; 
    int end = ptr->count - 1; 
    int mid = start + (end - start)/2; 

    while (start < end) 
    { 
     if (element > ptr->data[mid]) 
      start = mid + 1; 
     else 
      end = mid; 

     mid = start + (end - start)/2; 
    } 

    return mid; 
} 


node* createNode (const int level) 
{ 
    if (level <= 0) return NULL; 

     /* Allocate node with 2**(level-1) integers */ 
    node* pNewNode = (node *) malloc(sizeof(node) + sizeof(int)*(1 << (level - 1))); 
    memset(pNewNode->data, 0, sizeof(int) * (1 << (level - 1))); 

     /* Allocate 2**level child node pointers */ 
    pNewNode->child = (node **) malloc(sizeof(node *)* (1 << level)); 
    memset(pNewNode->child, 0, sizeof(int) * (1 << level)); 

    pNewNode->count = 0; 
    pNewNode->level = level; 

    return pNewNode; 
} 


void insert(node *root, int element) 
{ 
    node *ptr = root; 
    node *parent = NULL; 
    int i = 0; 

    while (ptr != NULL) 
    { 
     int level = ptr->level; 
     int count = ptr->count; 
     i = binary_search(ptr, element); 

     if (count < (1 << (level-1))) 
     { 
      for(int j = count; j >= i+1; --j) 
       ptr->data[j] = ptr->data[j-1]; 

      ptr->data[i] = element; 
      ++ptr->count; 
      return; 
     } 

     parent = ptr; 
     ptr = ptr->child[i]; 
    } 

    parent->child[i] = createNode(parent->level + 1); 
    insert(parent->child[i], element);  
} 


void InOrderTrace(node *root) 
{ 
    if (root == NULL) return; 

    for (int i = 0; i < root->count; ++i) 
    { 
     if (root->child[i]) InOrderTrace(root->child[i]); 
     printf ("%d\n", root->data[i]); 
    } 

    if (root->child[root->count]) InOrderTrace(root->child[root->count]); 
} 


void testdata (void) 
{ 
    node* pRoot = createNode(1); 

    for (int i = 0; i < 10000; ++i) 
    { 
     insert(pRoot, rand()); 
    } 

    InOrderTrace(pRoot); 
}