0

次のようなレコードを含む .dat ファイルがある場合:

805816899 Andrew
803975268 Bob
912684297 Jeff
123546789 Louis
751354687 Kevin

リストを ID 番号でソートしてから画面に書き込むために使用する最も簡単なデータ構造は何ですか? BST が最も理にかなっており、最も効率的であると考えていますが、このような小さなファイルを扱う場合は、スタックの方が簡単で高速です。

また、どのように実装しますか？

4

2 に答える 2

1

最も簡単なのは、BST を使用してそれらをソートすることでしたstd::map<int, std::string>。これは、内部で BST を使用して自己ソートされたデータ構造です (ただし、標準では明示的に指定されていません)。ルックアップが必要ない場合は、std::set代わりにユーザー定義型の を使用できます (次の段落を参照)。

それらをフラットな配列のような構造に格納する場合は、小さな構造体を作成して情報を保持し、そのインスタンスを に格納しstd::vector、適切な比較関数を と組み合わせて使用std::sort​​して並べ替えを行うことができます。

基地局:

#include <string>
#include <map>
std::map<int, std::string> m;
m[805816899] = "Andrew";
m[803975268] = "Bob";

等々。

配列のようなソリューション:

struct Foo 
{ 
  Foo(int ID, const std::string& name) : ID(ID), name(name) {}
  int ID; 
  std::string name;
};
// comparison for sorting
bool comp(const Foo& lhs, const Foo& rhs) { return lhs.ID < rhs.ID; }

#include <vector>
#include <algorithm>
....
std::vector<Foo> v;
v.push_back(Foo(805816899, "Andrew"));
v.push_back(Foo(803975268, "Bob"));
// add more entries
std::sort(v.begin(), v.end(), comp);
于 2013-01-30T18:08:16.553 に答える
0

トライはソート全体を実装する最も簡単な方法であり、IDの長さが一定の場合はO(n)だと思います。

#include <iostream>
#include <cassert>
#include <string>

class node {
  bool final;
  union {
    node *next[10];
    char *name;
  };
  node *get_at(int index)
  {
    assert(!final);
    return next[index] ? next[index] : (next[index] = new node);
  }

public:
  node() : final(false) { std::fill(next, next+10, (node*)0); }
  ~node() {
    if (final)
      delete name;
    else
      for (int i=0; i<10; ++i)
        delete next[i];
  }

  void insert(const char *id, std::string const& s)
  {
    if (*id) {
      get_at(*id - '0')->insert(id+1, s);
    } else {
      final=true;
      name = new char[s.size()+1]();
      std::copy(s.begin(), s.end(), name);
    }
  }

  void print_all(std::ostream& os) const
  {
    if (final)
      os << name << '\n';
    else
      for (int i = 0; i < 10; ++i)
        if (next[i])
          next[i]->print_all(os);
  }
};

int main()
{
  node top;
  for (std::string id, name; std::cin >> id >> name;)
    top.insert(id.c_str(), name);
  top.print_all(std::cout);
}
于 2013-01-30T18:24:25.917 に答える