指数木の実装

Question

私は、ドキュメントから指数関数ツリーを実装しようとしていたが、ここではそれを実装する方法を私のため明らかではないが、コード内の1つの場所は次のとおりです。ここで

#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; 
} 

は紙Iのリンクです'm参照先： 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); 
}