各種検索アルゴリズムの効率比較

タイトルの説明:順序が整ったN個の整数のシーケンス(データは1からNまで)を与えて、このシーケンスの中で指定した整数を探して、そして異なるアルゴリズムの運行時間を観察します.3種類の検索アルゴリズムを調べる:半折検索、バランス二叉ソートツリーの検索、B-ツリーの検索.要求:(1)ツリーテーブルを構築するアルゴリズムは各種の可能な入力データシーケンスを考慮しなければならない.(2)要求に応じてツリーテーブル構造を出力することができる.(3)最悪の場合、3種類の検索アルゴリズムの複雑さを分析する.(4)3種類のアルゴリズムのN=100500100000100000000400080808000010000での性能を測定し比較し、以下の3つの方面の仕事を完成することを要求する:1テストデータセットごとに、各検索アルゴリズムのASLを統計計算する;②試験データセット毎に複数回実行して実行時間の平均値を得る.③アルゴリズムの実際の実行結果(ASLと実行時間)のグラフを作成し、理論解析の時間的複雑さの整合性を検証する.

#include<iostream>
#include<stdio.h>
#include <time.h>
#include <malloc.h>

using namespace std;

#define CLOCKS_PER_SEC ((clock_t)1000)
#define MaxSize 100002
#define M 100
int Step;
int Bjishu;
using namespace std;

typedef struct
{
    int key;

}DataType;
typedef struct
{
    DataType list[MaxSize];
    int size;
}SeqList;

typedef struct node
{
    DataType data;
    struct node *LeftChild;//
    struct node *RightChild;//
    struct node *Parent;
    int i;//height
}BITreeNode, BTnode, *Tree;//        

typedef struct Node
{
    struct Node *parent;        /*      */
    int key[M];              /*     ，0     (M-1 )*/
    struct Node *ptr[M];        /*      */
}B_TNode;//B_    


void ListInitiate(SeqList *L)
{
    L->size = 0;
}
int ListLength(SeqList L)
{
    return L.size;
}
int ListInsert(SeqList *L, int x)
{
    // int j;
    if (L->size >= MaxSize)
    {
        printf("     
");
        return 0;
    }
    else
    {
        //for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];
        L->list[L->size].key = x;
        L->size++;
        return 1;
    }
}
int BInarySearch(SeqList S, DataType x)//    
{
    int js = 1;                        //    
    int low = 0;
    int high = S.size - 1;
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;             //    
        if (S.list[mid].key == x.key)return js;
        else if (S.list[mid].key<x.key)low = mid + 1;
        else if (S.list[mid].key>x.key)high = mid - 1;
        js++;
    }
    return -1;
}
int Hetree(BTnode *Root)
{
    if (Root == NULL)return 0;
    return
        Hetree(Root->LeftChild)>Hetree(Root->RightChild) ? Hetree(Root->LeftChild) + 1 : Hetree(Root->RightChild) + 1;
}


int IsBlance(BTnode *Root)//        )
{
    int bf;
    if (Root != NULL)
    {
        bf = Hetree(Root->LeftChild) - Hetree(Root->RightChild);
        if ((bf<-1) || (bf>1))
            return 0;//   
        else
        {
            if (IsBlance(Root->LeftChild) && IsBlance(Root->RightChild))
                return 1;
            else
                return 0;
        }
    }
    return 1;
}
BTnode *R_Rotate(BTnode *Root, BTnode *p)//LL    (  )
{
    BTnode *b, *q, *c, *d;
    q = p->Parent;
    b = p->LeftChild;
    c = b->LeftChild;
    d = b->RightChild;
    p->LeftChild = d;
    if (d != NULL)
        d->Parent = p;
    b->RightChild = p;
    p->Parent = b;
    if (q == NULL)
    {
        Root = b;
        b->Parent = NULL;            //b      ， b     
    }
    else if (q->LeftChild == p)        //  a        
    {
        q->LeftChild = b;            // b   q    
        b->Parent = q;            //b     q
    }
    else if (q->RightChild == p)        //  a        
    {
        q->RightChild = b;            // b   q    
        b->Parent = q;            //b     q
    }
    return Root;
}


BTnode *L_Rotate(BTnode *Root, BTnode *p)//RR    
{
    BTnode *b, *q, *c, *d;
    q = p->Parent;

    b = p->RightChild;
    c = b->RightChild;
    d = b->LeftChild;

    p->RightChild = d;
    if (d != NULL)
        d->Parent = p;

    b->LeftChild = p;
    p->Parent = b;

    if (q == NULL)
    {
        Root = b;                //         b， b    Root
        b->Parent = NULL;        //b      ， b     
    }
    else if (q->LeftChild == p)    //  p        
    {
        q->LeftChild = b;        // b   q    
        b->Parent = q;        //b     q
    }
    else if (q->RightChild == p)    //  p        
    {
        q->RightChild = b;        // b   q    
        b->Parent = q;        //b     q
    }

    return Root;
}
BTnode *LR_Rotate(BTnode *Root, BTnode *p)
{
    BTnode *b, *q, *c, *d;
    q = p->Parent;
    b = p->LeftChild;
    c = b->LeftChild;
    d = b->RightChild;
    p->LeftChild = d;
    if (d != NULL)
        d->Parent = p;
    b->RightChild = p;
    p->Parent = b;
    if (q == NULL)
    {
        Root = b;
        b->Parent = NULL;            //b      ， b     
    }
    else if (q->LeftChild == p)        //  a        
    {
        q->LeftChild = b;            // b   q    
        b->Parent = q;            //b     q
    }
    else if (q->RightChild == p)        //  a        
    {
        q->RightChild = b;            // b   q    
        b->Parent = q;            //b     q
    }
    return Root;
}
BTnode *RL_Rotate(BTnode *Root, BTnode *p)
{
    BTnode *b, *q, *c, *d;
    q = p->Parent;

    b = p->RightChild;
    c = b->RightChild;
    d = b->LeftChild;

    p->RightChild = d;
    if (d != NULL)
        d->Parent = p;

    b->LeftChild = p;
    p->Parent = b;

    if (q == NULL)
    {
        Root = b;                //         b， b    Root
        b->Parent = NULL;        //b      ， b     
    }
    else if (q->LeftChild == p)    //  p        
    {
        q->LeftChild = b;        // b   q    
        b->Parent = q;        //b     q
    }
    else if (q->RightChild == p)    //  p        
    {
        q->RightChild = b;        // b   q    
        b->Parent = q;        //b     q
    }

    return Root;
}
int blancebinarytreesearch(BTnode *Root, int x)//         
{
    BTnode *p;
    int count = 0;
    if (Root != NULL)
    {
        p = Root;
        while (p != NULL)
        {
            count++;
            if (p->i == x)return count;
            else if (x<p->i)p = p->LeftChild;
            else if (x>p->i)p = p->RightChild;
        }
    }
    return 0;
}
int InPEtree(BTnode **Root, int x)//            
{
    BTnode *cur, *parent = NULL, *p, *q;
    cur = *Root;
    while (cur != NULL)
    {
        if (x == cur->i)return 0;
        parent = cur;
        if (x<cur->i)cur = cur->LeftChild;
        else if (x>cur->i)cur = cur->RightChild;
    }
    p = (BTnode *)malloc(sizeof(BTnode));
    p->i = x;
    p->LeftChild = NULL;
    p->RightChild = NULL;
    p->Parent = NULL;
    if (parent == NULL)*Root = p;
    else if (x<parent->i)
    {
        parent->LeftChild = p;
        p->Parent = parent;
    }
    else if (x>parent->i)
    {
        parent->RightChild = p;
        p->Parent = parent;
    }

    int bf;

    if (IsBlance(*Root) == 0)        //          
    {
        bf = Hetree(parent->LeftChild) - Hetree(parent->RightChild);
        while ((bf >= -1) && (bf <= 1))
        {
            parent = parent->Parent;
            bf = Hetree(parent->LeftChild) - Hetree(parent->RightChild);
        }
        q = parent;///             
        if (p->i>q->i&&p->i>q->RightChild->i)//      q           。
        {
            *Root = L_Rotate(*Root, q);
        }
        else if (p->i>q->i&&p->i<q->RightChild->i)//      A           
        {
            *Root = RL_Rotate(*Root, q);
        }
        else if (p->i<q->i&&p->i>q->LeftChild->i)//      q           
        {
            *Root = LR_Rotate(*Root, q);
        }
        else //     A           
        {
            *Root = R_Rotate(*Root, q);
        }
    }
    return 1;
}

void PrintBiTree(BTnode *root, int n)
{
    int i;
    if (root == NULL)return;
    PrintBiTree(root->RightChild, n + 1);
    for (i = 0; i<n - 1; i++)printf(" ");
    if (n>0)
    {
        printf("-----");
        printf("%d
", root->i);
    }
    if (n == 0)
    {
        //printf("--");
        printf("%d
", root->i);
    }
    PrintBiTree(root->LeftChild, n + 1);
}

int B_treetreesearch(B_TNode *Root, int x)//  B- 
{
    int i;
    if (Root == NULL)return 0;
    for (i = 1; i <= Root->key[0]; i++)
    {
        Bjishu++;
        if (x<Root->key[i])break;
        if (x == Root->key[i])return Bjishu;
    }
    return B_treetreesearch(Root->ptr[i - 1], x);
}

B_TNode* B_treetreeinsert(B_TNode *Root, int x)//3.B-      
{
    int i;
    if (Root == NULL)//B_   
    {
        Root = (B_TNode *)malloc(sizeof(B_TNode));
        Root->key[0] = 1;
        Root->key[1] = x;
        for (i = 0; i<M; i++)
            Root->ptr[i] = NULL;
        Root->parent = NULL;
        return Root;
    }
    B_TNode *p = Root, *q, *s;
    q = p;
    while (p != NULL)
    {
        for (i = 1; i <= p->key[0]; i++)
            if (x<p->key[i])break;
        q = p;
        p = p->ptr[i - 1];
    }
    int j;
    q->key[i] = x;

    for (j = q->key[0]; j >= i; j--)
    {
        q->key[j + 1] = q->key[j];
        q->ptr[j + 1] = q->ptr[j];
    }
    q->key[0]++;
    int temp;
    i = q->key[0];
    int m, num = 0;
    while (q->key[0] == Step + 1 - 1)
    {
        num++;
        temp = q->key[(i - 1) / 2 + 1];
        p = q->parent;
        q->key[0] = (i - 1) / 2;//    
        m = (i - 1) / 2 + 1;
        //      
        if (p == NULL)
        {
            p = (B_TNode *)malloc(sizeof(B_TNode));
            for (i = 0; i<M; i++)
                p->ptr[i] = NULL;
            Root = p;
            Root->parent = NULL;
            p->key[0] = 1;
            p->key[1] = temp;
            p->ptr[0] = q;
            p->parent = NULL;
        }
        else
        {
            for (i = 1; i <= p->key[0]; i++)
                if (temp<p->key[i])break;
            for (j = p->key[0]; j >= i; j--)
            {
                p->key[j + 1] = p->key[j];
                p->ptr[j + 1] = p->ptr[j];
            }
            p->key[i] = temp;//
            p->ptr[i - 1] = q;//
            p->key[0]++;
        }
        //    
        s = (B_TNode *)malloc(sizeof(B_TNode));
        for (i = 0; i<M; i++)
            s->ptr[i] = NULL;
        p->ptr[p->key[0]] = s;
        p->ptr[p->key[0] - 1] = q;
        s->key[0] = Step + 1 - 1 - m;
        s->parent = p;
        q->parent = p;
        for (i = 1; i <= s->key[0]; i++)
        {
            s->key[i] = q->key[i + m];
            s->ptr[i - 1] = q->ptr[i + m - 1];    ////////////////

        }
        if (num>1)s->ptr[i - 1] = q->ptr[i + m - 1];
        for (i = 0; i <= s->key[0]; i++)
        {
            if (s->ptr[i] != NULL)s->ptr[i]->parent = s;////////////////
        }
        q = p;
        i = q->key[0];
    }
    return Root;
}
int B_treetreeprint(B_TNode *Root, int n)
{
    int i, j;
    if (Root == NULL)return 0;

    for (i = Root->key[0]; i>0; i--)
    {
        B_treetreeprint(Root->ptr[i], n + 1);
        for (j = 0; j<n; j++)
            printf("----");
        cout << Root->key[i] << endl;
    }
    B_treetreeprint(Root->ptr[0], n + 1);
}
/* int B_treetreeprint(B_TNode *Root,int n) { int i; if(Root==NULL)return 0; if(Root->key[0]>=2) { B_treetreeprint(Root->ptr[2],n+1); for(i=0;i<n;i++) printf("--"); printf("%d ",Root->key[2]); printf("
"); } if(Root->key[0]>=1) { B_treetreeprint(Root->ptr[1],n+1); for(i=0;i<n;i++) printf("--"); printf("%d ",Root->key[1]); printf("
"); //printf("
"); } if(Root->ptr[0]!=NULL) { B_treetreeprint(Root->ptr[0],n+1); // for(i=0;i<n;i++) // printf("---"); } } int B_treetreeprint(B_TNode *Root,int n) { int i; if(Root==NULL)return 0; if(Root->key[0]>=2) { B_treetreeprint(Root->ptr[2],n+1); for(i=0;i<n;i++) printf("--"); printf("%d ",Root->key[2]); printf("
"); } if(Root->key[0]>=1) { B_treetreeprint(Root->ptr[1],n+1); for(i=0;i<n;i++) printf("--"); printf("%d ",Root->key[1]); printf("
"); //printf("
"); } if(Root->ptr[0]!=NULL) { B_treetreeprint(Root->ptr[0],n+1); // for(i=0;i<n;i++) // printf("---"); } } */
int main()
{
    int i;
    int s, j, k, k1, k2, k3, Size, Sizex;
    int x;
    SeqList L;
    DataType Me;
    double runtime;
    double Start, End;
    printf("          Size：");
    //while (scanf("%d", &Size) != EOF&&Size != 0)
    scanf("%d", &Size);
    {
        ListInitiate(&L); //      
        Tree t = NULL;   //        
        Tree zt = NULL; //        
        B_TNode *Root = NULL;
        s = 0;
        printf("   B_   ：");
        scanf("%d", &Step);
        for (i = 0; i<Size; i++)
        {
            InPEtree(&t, i + 1); //Insert (&t,i+1);       
            ListInsert(&L, i + 1);//     
            Root = B_treetreeinsert(Root, i + 1);//  B_ 
        }
        printf("     
");
        PrintBiTree(t, 0);//       PrintfTree(t,1);
        printf("
B_ 
");
        B_treetreeprint(Root, 0);
        //printf("         （1~Size）：");
        Sizex = Size;
        printf("       
");
        scanf("%d",&Sizex);
        if (Sizex <0 || Sizex >Size)
        {
            printf("    ，     ！
");
            return 0;
        }
        //while (Sizex >= 1)
        {

            k1 = 0;  k2 = 0; k3 = 0;          //   
            k1 = blancebinarytreesearch(t, Sizex);
            printf("       %d  %d 
", Sizex, k1);
            Me.key = Sizex;
            k2 = BInarySearch(L, Me);
            printf("       %d  %d 
", Sizex, k2);
            Bjishu = 0;
            printf("B_   %d  %d 
", Sizex, B_treetreesearch(Root, Sizex));
            //printf("         （1~Size）：");
        }

        k = 0;
        Start = clock();//    
        for (i = 0; i<Size; i++)
        {
            k += blancebinarytreesearch(t, i + 1);//SearchBST(t,i+1,s);
        }
        End = clock();//    】
        runtime = (double)(End - Start) / (CLOCKS_PER_SEC*Size);
        printf("%d     
\t\t        ASL= %.2f \t    ：%lf ms
", Size, (float)k / Size, runtime);

        k = 0;
        Start = clock();
        for (i = 0; i<Size; i++)
        {
            Me.key = i + 1;
            k += BInarySearch(L, Me);
        }
        End = clock();
        runtime = (double)(End - Start) / (CLOCKS_PER_SEC*Size);
        printf("\t\t      ASL= %.2f \t     ：%lf ms
", (float)k / Size, runtime);

        Bjishu = 0;
        Start = clock();
        for (i = 0; i<Size; i++)
        {
            B_treetreesearch(Root, i + 1);
        }
        End = clock();
        runtime = (double)(End - Start) / (CLOCKS_PER_SEC*Size);
        printf("\t\t B_   ASL= %.2f \t     ：%lf ms
", (float)Bjishu / Size, runtime);

    }
    return 0;
}