C++スタックの実装

4706 ワード
C++学習
山は完全な二叉木です.スタックは、要素の配置によって、最大スタック(max-heap)と最小スタック(min-heap)に分けることができます.
  • 最大ヒープ:各ノードの値がサブノード以上である最大の完全ツリーです.したがって、最も大きな山の中で、ルートノードは完全な二叉木の最大ノードである.
  • 最小ヒープ:最小の完全ツリーで、各ノードの値がサブノード以下またはそれに等しい.したがって、最小スタックでは、ルートノードは、この完全な二叉木の最小ノードである.

    • スタックはSTLコンテナコンポーネントに帰属するのではなく、優先キュー(priority queue)の下位層として実装される.スタックは完全な二叉木で、全体の二叉木は最下層の葉ノードを除いて満たされているが、最下層の葉ノードは左から右に隙間がないので、arrayまたはvectorを利用してすべてのノードを格納することができる.スタックアルゴリズムはヘッダファイルalgorithmで実現され、主な操作はpush_Heapアルゴリズム、pop_Heapアルゴリズム、sort_heapアルゴリズムとmake_Heapアルゴリズムは、最大スタックを例に、一つ一つ紹介します.
  • push_Heapアルゴリズム実装構想:新しく挿入された要素を最下位レベルvectorのend()に挿入する.この場合、最も多くの条件を満たすために、新しいノードを親ノードと比較し、キー値が親ノードより大きい場合は、位置を交換し、交換位置が注:このメソッドは、最小スタックを使用する場合にパラメータ:greater()を入力できるシミュレーション関数(カスタム比較ルール)を受け入れます.あるいはvectorのヘッダの末尾を表す2つの反復器、および新しい要素、および下層容器の末尾に挿入しないと、予期せぬ結果をもたらす可能性がある.
  • pop_heapアルゴリズム実現構想:pop_Heap操作は実際にはルートノードを取り出し、下位コンテナの最後の位置(つまりルートノードと最後のリーフノードを交換する)に移動します.この場合、最も多くの条件を満たすために、ルートノードを子供ノード点と比較し、キー値が子供ノードより小さい場合は、大きな子供ノードと位置を交換する必要があります.このようにして、交換位置がリーフノードまたはリーフノードになるまで遡ります.STLライブラリでのプロトタイプ:図2,pop_heapプロトタイプ注意:この方法は、最小スタックを使用する場合にパラメータ:greater()を入力するシミュレーション関数(カスタム比較ルール)を受け入れます.あるいはvectorの頭と尾を表す2つの反復器です.
  • sort_Heapアルゴリズムの考え方:pop_heap操作は、最大要素を最下位コンテナの最後に置くたびにpop_を繰り返し呼び出すとHeap操作により、インクリメンタルシーケンスが得られます.スタック並べ替えの時間的複雑さ,最悪(O(nlogn),最良(O(nlogn),平均(O(nlogn),不安定並べ替えアルゴリズム.注:このメソッドは、最小スタックを使用する場合にパラメータ:greater()を入力できるシミュレーション関数(カスタム比較ルール)を受け入れます.あるいはvectorの頭と尾を表す2つの反復器です.
  • make_heapアルゴリズム実装構想:make_heapオペレーションは、n個の要素がすでに存在するシーケンスを最大スタックに構築するために使用され、そのコアオペレーションはフィルタリング法である.空のシーケンスの場合、push_を繰り返し呼び出すことができます.Heap操作で、最大スタックを構築します.注:このメソッドは、最小スタックを使用する場合にパラメータ:greater()を入力できるシミュレーション関数(カスタム比較ルール)を受け入れます.あるいはvectorの頭と尾を表す2つの反復器です.

    • STLのスタックの応用:
  • スタックmake_heap(_first,_last,_comp)はデフォルトで最大スタックを作成します.比較関数で比較関数に大きいサイズ(>)を付ける場合は、
    • より大きいサイズです.
  • スタックにデータpush_を追加heap(_first,_last)コンテナにデータを追加してpush_を呼び出すheap();
  • スタックからデータpopを削除heap(_first,_last)pop_を呼び出すにはHeap()は、コンテナからデータを削除します.
  • スタックソートsort_heap(_first,_last,)のソート後は合法的なスタックではありません.スタックのソートはみんな知っているでしょう.
    //改善待ち
    #include
#include
#include
using namespace std;
void print_ivec(vector<int>::iterator begin, vector<int>::iterator end)
{
    for(;begin != end; ++begin)
        cout << *begin << '\t';
    cout << endl;
}

//          
bool cmp(int a,int b)
{ 
  return a>b;
}

int main(int argc, char* argv[])
{
    int a[] = {1, 12, 15, 20, 30};
    vector<int> ivec(a, a + sizeof(a) / sizeof(a[0]));
    print_ivec(ivec.begin(), ivec.end());

    //       
    make_heap(ivec.begin(), ivec.end(),cmp);   
    print_ivec(ivec.begin(), ivec.end());
    //       
    pop_heap(ivec.begin(), ivec.end(),cmp);
    ivec.pop_back();

    print_ivec(ivec.begin(), ivec.end());

    //       
    ivec.push_back(0);
    push_heap(ivec.begin(), ivec.end(),cmp);

    print_ivec(ivec.begin(), ivec.end());

    //               。。。     。。。
    sort_heap(ivec.begin(), ivec.end(),cmp);  //         
    print_ivec(ivec.begin(), ivec.end());
    return 0;
}
    • csvファイルから取得した値を名前にしたディレクトリをたくさん作る
    2本の直線の挟み角