none
リンクトリストのソートについて RRS feed

  • 質問

  • C言語で構造体のリンクトリストを作成しています。

    構造体は次のようなものです。

    typedef struct person {
     int  pcode;
     char *pname;
     int  page;
     struct person *next;
     struct person *prev;
    } person_t;

    typedef struct root {
     struct person *head;
     struct person *tail;
    } root_t;
    ここで、person_tのメンバであるpcodeをキーにしてソートしたいのですが、リンクトリストのソート方法がわかりません。

    どなたかご教授願えないでしょうか。

    よろしくお願いいたします。

    2007年6月22日 16:25

すべての返信

  • ソート・アルゴリズムは何を使いましょうか?

    どんなアルゴリズムであれ、要素の交換はnext/prev以外の各メンバを交換すればいいのですけども。

     

    もっとオススメなのはC++でやっちまえば:

    struct person { int pcode; string pname; int page; };

    list<person> pl; // personを要素とする双方向リスト

    ...

    pl.sort(); // ソートはこれ一発(比較関数が適切に定義されているなら)

    2007年6月22日 17:19
  • ソート・アルゴリズムは、クイック・ソートを使いたいと思っています。

    現在、配列用のソース・ファイルを元に書き換えを行っている最中です。

    なかなか、悪戦苦闘しています。

    2007年6月23日 4:45
  • えー!?

     

    quick-sortはランダムアクセスできるデータ構造じゃないとn番目の

    要素をポイントするのに要する時間コストがバカにならんでしょ。

     

    リスト構造ならその性質からしてマージ・ソートなんかがいいんじゃないでしょか。

     

    2007年6月23日 5:54
  •  επιστημη さんからの引用
    もっとオススメなのはC++でやっちまえば:

    struct person { int pcode; string pname; int page; };

    list<person> pl; // personを要素とする双方向リスト

    ...

    pl.sort(); // ソートはこれ一発(比較関数が適切に定義されているなら)

     

    お試し。

    #include <iostream>
    #include <string>
    #include <list>
    #include <iterator>
    #include <algorithm>

    struct person {
      int  code;
      std:Tongue Tiedtring name;
      int  age;
    };

    person make_person(int c, const char* n, int a) {
      person result;
      result.code = c;
      result.name = n;
      result.age = a;
      return result;
    }

    bool name_less(const person& x, const person& y) {
      return x.code < y.code;
    }

    std:Surprisestream& operator<<(std:Surprisestream& stream, const person& p) {
      return stream << p.code << ' ' << p.name << ' ' << p.age;
    }

    int main() {
      std::list<person> container;
      container.push_back(make_person(5,"apple",10));
      container.push_back(make_person(6,"orange",11));
      container.push_back(make_person(2,"banana",12));
      container.push_back(make_person(3,"cherry",12));
      std:Surprisestream_iterator<person> out(std::cout, "\n");
      std::cout << "before\n";
      std::copy(container.begin(), container.end(), out);
      std::cout << std::endl;
      container.sort(name_less);
      std::cout << "after\n";
      std::copy(container.begin(), container.end(), out);
      std::cout << std::endl;
    }

    2007年6月23日 6:35
  • マージソートでうまくいきました。
    2007年6月24日 6:14