-1 
    List List:: mergesort(List m)
    {
    if(m.count() <= 1)
           return m;
        else
       {
    List l,r;
        node* temp = m.head;
        node* ptemp = m.head;
        node* first = m.head;
        int c = m.count();
        for(int i = 1; temp->next!=NULL && i<=(c/2)+1; i++)
        {
         ptemp = temp;
         temp = temp->next;
         }

      ptemp->next = NULL;

      while(first!=NULL)
      {
         l.insert(first->data);
         first = first->next;
      }

      while(temp!=NULL)
      {
        r.insert(temp->data);
         temp = temp->next;
      }

      cout<<"\t\t";
      l.display();
      cout<<"\t\t";r.display();cout<<"\n";

      l = mergesort(l);
      r = mergesort(r);
     }
 }

マージソートアルゴリズムの分割ステップ中の各ステップを表示しようとしています。

たとえば、次の List を入力します: 5 3 7 14 2

望ましい出力： -

              5 3 7 14 2

     5 3 7                  14 2

  5 3      7              14     2

5     3     7           14         2

私が得るものは：

              5 3 7 14 2

     5 3 7                  14 2

     5 3                    7             

     5                      3
     14                     2

私は何をすべきか？私はあらゆる可能なことを試みましたが、近づくことさえできません。どんな体でも助けてくれませんか？

さて、これはデバッグ後に私が理解していることです。関数mergesort()の内部は次のとおりです。

マージソート(5 3 7 14 2)

マージソート(5 3 7)

マージソート(5 3)

マージソート(14 2)

私が必要とするのは:-

mergesort(5 3 7 14 2)
mergesort(5 3 7)   
       mergesort(14 2)   
mergesort(5 3)

何も考えられません。助けてください。

4

2 に答える 2

1

木を間違って配置しています。コンソール出力で上に移動できないため、そのように「マージソート ツリー」が表示されることはありません。代わりに、ツリーを 90 度回転させる必要があります。このような

List List:: mergesort(List m, int depth)
{
   for (int i = 0; i < depth; ++i)
       cout << '\t';
   display();
   cout << '\n';

   ...
   l = mergesort(l, depth + 1);
   r = mergesort(r, depth + 1);

}

depth 変数は、この呼び出しでソートする値を表示する前に表示するインデントの量を制御します。各呼び出しの値は、個別の行に表示されます。これにより、ツリーが 90 度回転し、ルートがコンソールの左端に表示され、子ノードが親に続き、徐々に右に移動します。

于 2012-11-18T11:33:15.510 に答える
0

あなたが説明したようなツリーを作成しようとする方法（ただしmergesort()、1つの要素シーケンスに対して別のレベルを作成しないため、まったく同じではありません）は、中間状態のツリーを構築してから、幅優先探索ウォークを使用することですツリーを実際に表示します。ツリーを個別のデータ構造として実際に構築する代わりに、mergesort()再帰を使用せずに中間ステップを自分で制御し、暗黙的なツリーの幅優先探索ウォークを効果的に使用することができます。

以下は、私が意味するものの例です。出力は適切にフォーマットされていませんが、少なくとも各行には期待される内容が含まれています。また、出力には、分割と中間マージの両方の中間結果が表示されます。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std::placeholders;

typedef std::vector<int> range;

std::ostream& print_range(std::ostream& out, range const& v)
{
    out << '[';
    if (!v.empty()) {
        std::copy(v.begin(), v.end() - 1,
                  std::ostream_iterator<int>(out, ", "));
        out << v.back();
    }
    return out << "] ";
}

std::vector<range>
mergesort(std::vector<range> const& rs)
{
    std::cout << "> ";
    std::for_each(rs.begin(), rs.end(),
                  [](range const& r) { print_range(std::cout, r); });
    std::cout << "\n";
    if (rs.end() != std::find_if(rs.begin(), rs.end(),
                                 [](range const& r) {
                                     return 1 < r.size();
                                 })) {
        std::vector<range> sr;
        std::for_each(rs.begin(), rs.end(),
                      [&](range const& r) {
                          sr.push_back(range(r.begin(),
                                             r.begin() + r.size() / 2));
                          sr.push_back(range(r.begin() + r.size() / 2,
                                             r.end()));
                      });
        sr = mergesort(sr);
        std::vector<range> result;
        for (range::size_type i(0); i + 1 < sr.size(); i += 2) {
            result.push_back(range());
            std::merge(sr[i].begin(), sr[i].end(),
                       sr[i + 1].begin(), sr[i + 1].end(),
                       std::back_inserter(result.back()));
        }
        std::cout << "< ";
        std::for_each(result.begin(), result.end(),
                      [](range const& r) { print_range(std::cout, r); });
        std::cout << "\n";
        return result;
    }
    else {
        return rs;
    }
}

range mergesort(range const& input)
{
    return mergesort(std::vector<range>(1, input)).front();
}

int main()
{
    try
    {
        range input{std::istream_iterator<int>(std::cin),
                std::istream_iterator<int>()};
        mergesort(input);
    }
    catch (std::exception const& ex)
    {
        std::cout << "ERROR: " << ex.what() << '\n';
    }
}
于 2012-11-18T13:07:45.293 に答える