「データ構造」ソート——スタックソート(C++実装)

前言:「データ構造」はコンピュータ専門の重点学科として、将来の大学院受験、就職にかかわらず、その考察が重要であり、前の文章はすでにこれについて論述したことがある.プログラマーの「プログラミング能力」を考察する一つの方法として、データ構造の思想をプログラミング言語で正確に符号化する方法が試されている.すべての「データ構造」の教科書は、各データ構造とアルゴリズムの思想を詳しく説明し、具体的なプログラミング言語コードまたは偽コードを与えた.アルゴリズム思想は真剣に本を読むだけで、やはり比較的に掌握しやすくて、本当に私達を試練して、アルゴリズム思想から具体的な符号化のこの思考過程まで、どのように符号化して実現することを考えて、この過程は逃げられないので、他の人の既存のコードを参考にしない限り、しかししばらくの間後できっと忘れます(100パーセント、私は何度も忘れました).だから、できるだけプログラミングが実現する前に、自分ではっきりした考えを持って、自分で実現してみて、それからデバッグして、脳細胞が足りないので、他の人の書いたことを参考にします.
0、コード:本明細書のすべてのコードはgithubに置く:https://github.com/thinkChao/Data-Structure/blob/master/%E5%A0%86%E6%8E%92%E5%BA%8F.cppで、必要なのはダウンロードしたり直接実行したりすることができて、1つのcppファイルだけあって、すでにテストに合格しました.
1、ヒープの順序についての4点の説明(注意:本稿で私が言ったヒープは、いずれも大頂ヒープを指す.):1)、スタックの特徴は親ノードの値が2つの子供ノードの値より大きいか等しいかであり、1つのスタックは完全な二叉木であるため、配列を採用して二叉木を格納することは非常に便利である.したがって,配列全体のシーケンス,すなわち,二叉木の階層遍歴結果(上から下,左から右)であることが分かる.
2)、スタックを構築する過程:最後の非端末ノードから、その子供ノードの大きさを比較し、子供が彼より大きいものがあれば交換する.もし両方が彼より年上だったら?それは最大のそれと交換します.
3)、いくつかの計算が必要なノード:私たちは最後の非端末ノードから遍歴を開始するので、配列中の位置を知って、その位置を知って、残りは1つ目、つまりルートノードまで順次減少する必要があります.また、ノードの左の子供と右の子供の位置を知る必要があります.スタックは完全に二叉木であり,配列記憶を採用しているため,計算は規則的である.

      size，        i（i 1  ）。
            ：size/2
        ：2*i
        ：2*i+1

4)、ヒープの順序付けの流れ:配列を指定し、ヒープを構築-->ヒープを出力するルートノード(配列の最初の要素)-->ルートノードを0に設定-->ヒープを再構築-->ヒープを出力するルートノード-->......3、コードを添付する:

#include 
using namespace std;
#define ArraySize 8


void create_heap(int data[],int size)
{
    for(int i=(size/2);i>0;i--) //              ，     
    {
        int l_kid=2*i;  //      
        int r_kid=2*i+1;    //      
        int tmp;    //                       
        int k;  //    
        int j=i;
        while(l_kid<=size)  //                 
        {
            
            tmp=l_kid;
            if(l_kiddata[tmp-1])
                break;
            else
            {
                k=data[j-1];
                data[j-1]=data[tmp-1];
                data[tmp-1]=k;
                l_kid=tmp*2;
                j=tmp;
            }
        }
    }
}

void heap(int data[],int size)
{
    create_heap(data,size);//   
    cout<>data[i];
    /*    */
    heap(data,8);
    /*      */
    cout<