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

我试图在“合并排序算法的划分步骤”中展示每个步骤。

例如我输入这个列表：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()不会为一个元素序列创建另一个级别）是建立一个中间状态树，然后使用广度优先搜索步行树的实际显示它。除了将树实际构建为单独的数据结构之外，您还可以实现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 回答