最近更新したページ
2013-10-20
2013-09-29
2013-09-23
2012-01-07
2011-11-09
2011-10-23
2011-10-09
2011-10-01
2011-09-29
2011-09-03
2011-08-07
2011-08-02
2011-07-29
2011-07-10
2011-05-05
2011-05-04
2011-04-24
2011-04-13
2011-04-05
2011-03-26
2011-02-18
2011-02-15
2010-12-26
2010-12-07
2010-12-05
2010-11-23
2010-09-28
2010-09-23
2010-08-26
2010-08-22
2010-07-16
2010-01-17
2010-01-11
2009-10-04
2009-08-21
2009-08-13
2009-06-18
2009-06-01
2009-04-29
2009-02-16
2009-02-11
2009-02-03
2008-07-22
2008-07-21
2008-07-15
2008-07-14
2008-07-13
2008-07-12
2008-07-08
2008-07-05
2008-06-28
2008-06-17
2008-06-05
2008-06-02
2008-06-01
2008-05-29
2008-05-26
2008-05-21
2008-05-19
2008-05-18
2007-10-31
2007-10-27
2007-09-28
2007-09-23
2007-09-17
2007-09-16
2007-09-14
2007-09-11
2007-06-18
2007-04-15
2006-12-21
2006-11-30
2006-11-22
2006-08-17
2006-03-29
2006-03-28
2006-03-27

C/C++ 構造体とソート


構造体とソート


 C/C++ 構造体とポインタ頁 sample 5-4 ベースに構造体メンバによるソートを考察。

構造体・配列・ソートのサンプル

 qsort / 標準外ソート関数による構造体配列のソートについては期待値が出るようになった。
 構造体の動的配列、std::sort の構造体配列ソートはうまく行ってない。


 さて・・・ C/C++ ソート(並べ替え)頁を中途で STL/動的配列など・・・と遷移したため、ソートは qsort() 関数しかかじってない・・・

 必要な知識:構造体の動的配列処理。演算子のオーバーロード(オペレータの知識)...
 触った知識:関数ポインタ...その他関数テンプレート...なども若干。

void sort(struct student*, int, int(*)(const void*, const void*));

 このような void で型指定無しで不特定の変数(ポインタ)を渡し、受取り側でキャスト(C言語でも利用可)しているが、動きとしては C++ の関数テンプレートに似ているような気がする。具体的にどう違うのか?関数テンプレートで置き換えられるのかは不明である。

問題点と対策
  • qsort std::sort では、複数回ソートの並びを維持できない。(早いが不安定)
    • 対策:標準ソートを使わない、または、比較関数で吸収(汎用性低下)する。
  • 標準ソートは、処理に時間が掛かる。(安定・汎用性が向上するが遅い)
    • 実際:1万件超で体感的に遅い。6万件なら耐えられほど遅い。(pc環境依存)
    • 対策:高速なソートアルゴリズムを使用する。

※相反する対策となる。双方を満足するアルゴリズムを残念ながら現状知らない。
※ソートの種類:バブルソート(単純交換法)、クイックソート、・・・他あり。


▲上へ [ 編集 ]

標準のソート関数を使わず「構造体配列」をソートする

 C/C++ 関数ポインタ より転記:sample 5::関数ポインタを利用したソート
 構造体配列のソートを、ソート関数を別途用意しておこなうテスト。

動作テストプログラム sample 5
※qsort で使ったソース使い回し。
#include <iostream>
#include <string>
using namespace std;
// 関数プロトタイプ
void out_dsp(struct student*, const int);
int no_comp(const void*, const void *);
int age_comp(const void*, const void *);
void sort(struct student*, int, int(*)(const void*, const void*));
void swap(struct student*, struct student*);
// 構造体定義
struct student {
   int    no;
   int    age;
   string Birthday;
   string blood_type;
   string boy_girl;
   string name;
   string memo;
};
/****************
main
*****************/
void main() {
   cout << "■ 1. main()     ・・・ プログラムの開始 ・・・" << endl;
   int max_no = 9;
   struct student seito[] = {
      { 7, 14, "5/28",  "O",  "g", "三原 千春",     "山崎と幼なじみ" },
      { 3, 14, "7/13",  "O",  "b", "李 小狼",       "無口" },
      { 4, 13, "3/25",  "B",  "g", "李 苺鈴",       "気が強い" },
      { 1, 14, "4/1",   "A",  "g", "木之本 桜",     "はにゃーん・ほえ〜" },
      { 6, 13, "6/1",   "AB", "b", "山崎 貴史",     "ホラ吹き" },
      { 2, 13, "9/3",   "A",  "g", "大道寺 知世",   "ビデオ撮影に執着" },
      { 8, 14, "6/24",  "A",  "g", "佐々木 利佳",   "落ち着いている" },
      { 9, 13, "10/11", "AB", "g", "柳沢 奈緒子",   "眼鏡っ子で怪談好き" },
      { 5, 13, "3/23",  "AB", "b", "柊沢 エリオル", "クロウの生まれ変わり" },
   };
   // --- sort ---
   cout << "■ 2. main()     ・・・ seito[].no  による sort ・・・" << endl;
   sort(seito, max_no, no_comp);
   cout << "■ 3. main()     ・・・ seito[].age による sort ・・・" << endl;
   sort(seito, max_no, age_comp);
   // --- 表示 ---
   out_dsp(seito, max_no);
   cout << "■ 5. main()     ・・・ プログラムの終了 ・・・" << endl;
}
/****************
関数・サブルーチン
*****************/
// sort関数(function)
void sort(struct student* p, int n,
                 int (*p_cp)(const void* x, const void* y) ) {
   int k = n-1;
   while(k>=0) {
      int i=1, j=-1;
      for(; i<=k; i++) {
          if ( p_cp( p+i-1, p+i ) > 0 ) {  // ここが関数ポインタの要
             j = i-1;
             swap(p+i, p+j);               // 値の入替
          }
      }
      k = j;
   }
}
// swap sub
void swap(struct student* x, struct student* y) {
   struct student temp = *x;
   *x = *y;
   *y = temp;
}
// sort 比較関数(sub) 2種
int no_comp(const void* x, const void * y) {  // student->no の比較
   struct student* a = (struct student *) x;
   struct student* b = (struct student *) y;
   if      (a->no < b->no)             return -1;
   else if (a->no > b->no)             return  1;
   else                                return  0;
}
int age_comp(const void* x, const void * y) { // student->age を比較
   struct student* a = (struct student *) x;
   struct student* b = (struct student *) y;
   if      (a->age < b->age)           return -1;
   else if (a->age > b->age)           return  1;
   else                                return  0;
}
// 表示用 sub
void out_dsp(struct student* seito, const int max_no ) {
   cout << "■ 4. out_dsp()  ・・・ 全データを表示 ・・・" << endl << endl;
   cout << "no age birth bt bg name               memo" << endl; 
   cout << "----------------------------------------------------" << endl;
   for(int i=0; i<max_no; i++) {
      printf("%2i %3i %6s %3s %3s %-18s %s \n",
                  seito[i].no,
                  seito[i].age,
                  seito[i].Birthday.c_str(),
                  seito[i].blood_type.c_str(),
                  seito[i].boy_girl.c_str(),
                  seito[i].name.c_str(),
                  seito[i].memo.c_str()
            );
   }
   cout << "----------------------------------------------------" << endl;
   cout << "*bt=血液型 *bg=性別" << endl << endl;
}
※表示用に修正してないが動く。-> 表示用に修正入れたので動くか不明。
※あちこちボロがあったので修正。動作チェック済み。

表示サンプル
■ 1. main()     ・・・ プログラムの開始 ・・・
■ 2. main()     ・・・ seito[].no  による sort ・・・
■ 3. main()     ・・・ seito[].age による sort ・・・
■ 4. out_dsp()  ・・・ 全データを表示 ・・・

no age birth bt bg name               memo
----------------------------------------------------
 2  13    9/3   A   g 大道寺 知世        ビデオ撮影に執着
 4  13   3/25   B   g 李 苺鈴            気が強い
 5  13   3/23  AB   b 柊沢 エリオル      クロウの生まれ変わり
 6  13    6/1  AB   b 山崎 貴史          ホラ吹き
 9  13  10/11  AB   g 柳沢 奈緒子        眼鏡っ子で怪談好き
 1  14    4/1   A   g 木之本 桜          はにゃーん・ほえ〜
 3  14   7/13   O   b 李 小狼            無口
 7  14   5/28   O   g 三原 千春          山崎と幼なじみ
 8  14   6/24   A   g 佐々木 利佳        落ち着いている
----------------------------------------------------
*bt=血液型 *bg=性別

■ 5. main()     ・・・ プログラムの終了 ・・・
続行するには何かキーを押してください . . .
※見事に年齢順、出席No順とすることが出来た。
※qsort や std::sort でも、比較関数の工夫で同様のことは可能と思われる。
※ただし、汎用性と使い回しでは、多分安定ソートベースが使いやすい。

VC++ や Turbo C++ で表示がすぐ終わるってしまい結果が確認できない場合。
int main() {
   ・・・ 中略 ・・・
   {
      int c = getchar(); // または、 cin >> c; とすることで一時停止する。
   }
   return;
※蛇足。(今回 Turbo C++ も利用してみて感じたこと。vc++ は「デバッグ無しで開始」すると止まるため不要だった。)

 ...というか、MS VC++ 専用の積りでないのだが、Turbo C++ で同じコードをコンパイル出来ない。・・・ 何故? ・・・

 もちろん!ターC でも「Hello World !」はコンパイルできてます。。。(^。^)。。。


▲上へ [ 編集 ]


qsort を使用した構造体配列のソート

 qsort ベースで vector と templete を使おうと頑張ったが...見事に撃沈した。

sample struct_qsort
#include <iostream>
#include <string>
using namespace std;
// 構造体の定義
struct student {
   int    no;
   int    age;
   string Birthday;
   string blood_type;
   string boy_girl;
   string name;
   string memo;
};
int no_comp(const void* x, const void * y);
int age_comp(const void* x, const void * y);
void out_dsp(struct student* p, const int n );
// ---------------------------------------------------------------
// main
// ---------------------------------------------------------------
void main() {
   cout << "■ 1. main()     ・・・ プログラムの開始 ・・・" << endl;
   int max_no = 9;
   struct student seito[] = {
      { 7, 14, "5/28",  "O",  "g", "三原 千春",     "山崎と幼なじみ" },
      { 3, 14, "7/13",  "O",  "b", "李 小狼",       "無口" },
      { 4, 13, "3/25",  "B",  "g", "李 苺鈴",       "気が強い" },
      { 1, 14, "4/1",   "A",  "g", "木之本 桜",     "はにゃーん・ほえ〜" },
      { 6, 13, "6/1",   "AB", "b", "山崎 貴史",     "ホラ吹き" },
      { 2, 13, "9/3",   "A",  "g", "大道寺 知世",   "ビデオ撮影に執着" },
      { 8, 14, "6/24",  "A",  "g", "佐々木 利佳",   "落ち着いている" },
      { 9, 13, "10/11", "AB", "g", "柳沢 奈緒子",   "眼鏡っ子で怪談好き" },
      { 5, 13, "3/23",  "AB", "b", "柊沢 エリオル", "クロウの生まれ変わり" },
   };
   // --- sort --------------------------------------------------------
   cout << "■ 2. main()     ・・・ seito[].no  による qsort ・・・" << endl;
   qsort( seito, max_no, sizeof(struct student), no_comp);
   cout << "■ 3. main()     ・・・ seito[].age による qsort ・・・" << endl;
   qsort( seito, max_no, sizeof(struct student), age_comp);^
   // --- 表示 --------------------------------------------------------
   out_dsp(seito, max_no);
}
// qsort 比較関数
int no_comp(const void* x, const void * y) {
  struct student* a = (struct student *) x;
  struct student* b = (struct student *) y;
  if		(a->no < b->no)		return -1;
  else if	(a->no > b->no)		return  1;
  else	                                return  0;
}
int age_comp(const void* x, const void * y) {
  struct student* a = (struct student *) x;
  struct student* b = (struct student *) y;
  if		(a->age < b->age)	return -1;
  else if	(a->age > b->age)	return  1;
  else                                 return  0;
}
// 表示用
void out_dsp(struct student* seito, const int max_no ) {
   cout << "■ 4. out_dsp()  ・・・ 全データを表示 ・・・" << endl << endl;
   cout << "no age birth bt bg name               memo" << endl; 
   cout << "----------------------------------------------------" << endl;
   for(int i=0; i<max_no; i++) {
      printf("%2i %3i %6s %3s %3s %-18s %s \n",
                  seito[i].no,
                  seito[i].age,
                  seito[i].Birthday.c_str(),
                  seito[i].blood_type.c_str(),
                  seito[i].boy_girl.c_str(),
                  seito[i].name.c_str(),
                  seito[i].name.c_str()
    );
   }
   cout << "----------------------------------------------------" << endl;
   cout << "*bt=血液型 *bg=性別" << endl << endl;
}
※vector で作成した配列処理がうまくいかなかったため、固定サイズの配列で動作確認。
※new , delete 仕様の動的配列なら可能と思うが....。

表示サンプル
■ 1. main()     ・・・ プログラムの開始 ・・・
■ 2. main()     ・・・ seito[].no  による qsort ・・・
■ 3. main()     ・・・ seito[].age による qsort ・・・
■ 4. out_dsp()  ・・・ 全データを表示 ・・・

no age birth bt bg name               memo
----------------------------------------------------
 5  13   3/23  AB   b 柊沢 エリオル      柊沢 エリオル
 2  13    9/3   A   g 大道寺 知世        大道寺 知世
 6  13    6/1  AB   b 山崎 貴史          山崎 貴史
 4  13   3/25   B   g 李 苺鈴            李 苺鈴
 9  13  10/11  AB   g 柳沢 奈緒子        柳沢 奈緒子
 7  14   5/28   O   g 三原 千春          三原 千春
 8  14   6/24   A   g 佐々木 利佳        佐々木 利佳
 1  14    4/1   A   g 木之本 桜          木之本 桜
 3  14   7/13   O   b 李 小狼            李 小狼
----------------------------------------------------
*bt=血液型 *bg=性別

続行するには何かキーを押してください . . .
※seito[].no の sort を引き継げない。構造体(複数条件)ソートには不向きと思われる。

▲上へ [ 編集 ]

リンク


内部リンク


外部リンク


  • 現在ありません

▲上へ

構造体とポインタのサンプルコード


 C/C++ 構造体とポインタ頁より、以下コードを sample 5-4 をベースに不要なテスト等を削除、レコード(メンバ)全体を表示するように変更。構造体メンバによるソートの基準として利用。

動的な構造体配列の例


 STL/構造体/ポインタを使用した動的な構造体配列の例

sample 5-5 cpp

vector 及び string型を含んだ構造体サンプルコード。
#pragma warning (disable:4313) // printf の worning を黙らせる
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void move_arr(vector<student>& v);
void out_dsp(vector<student>& v);
// 構造体の定義
struct student {
   int    no;
   int    age;
   string Birthday;
   string blood_type;
   string boy_girl;
   string name;
   string memo;
};
// main
void main() {
   cout << "■ 1. main()     ・・・ プログラムの開始 ・・・" << endl;
   vector<student>    v_seito;
   struct student     seito;

   move_arr(v_seito);           // 2.テストデータの代入
   out_dsp(v_seito);            // 3.処理された動的構造体配列の表示
}
// 動的配列へ代入されたデータを表示する
void out_dsp(vector<student>& v_seito) {
   cout << "■ 3. out_dsp()  ・・・ 全データを表示 ・・・" << endl << endl;
   cout << "no age birth bt bg name               memo" << endl; 
   cout << "----------------------------------------------------" << endl;
   vector<student>::iterator it;
   for(it=v_seito.begin(); it<v_seito.end(); it++) {
      printf("%2i %3i %5s %2s %2s %-18s %s \n",
              it->no,
              it->age,
              (it->Birthday).c_str(),
              (it->blood_type).c_str(),
              (it->boy_girl).c_str(),
              (it->name).c_str(),
              (it->memo).c_str()
     );
   }
   cout << "----------------------------------------------------" << endl;
   cout << "*bt=血液型 *bg=性別" << endl << endl;
}
// テストデータの代入
void move_arr(vector<student>& v_seito) {
   int max_no = 9;
   struct student seito[] = {
      { 1, 14, "4/1",   "A",  "g", "木之本 桜",     "はにゃーん・ほえ〜" },
      { 2, 13, "9/3",   "A",  "g", "大道寺 知世",   "ビデオ撮影に執着" },
      { 3, 14, "7/13",  "O",  "b", "李 小狼",       "無口" },
      { 4, 13, "3/25",  "B",  "g", "李 苺鈴",       "気が強い" },
      { 5, 13, "3/23",  "AB", "b", "柊沢 エリオル", "クロウの生まれ変わり" },
      { 6, 13, "6/1",   "AB", "b", "山崎 貴史",     "ホラ吹き" },
      { 7, 14, "5/28",  "O",  "g", "三原 千春",     "山崎と幼なじみ" },
      { 8, 14, "6/24",  "A",  "g", "佐々木 利佳",   "落ち着いている" },
      { 9, 13, "10/11", "AB", "g", "柳沢 奈緒子",   "眼鏡っ子で怪談好き" }
   };
   cout << "■ 2. move_arr() ・・・ テストデータの代入 ・・・" << endl;
   for(int i=0; i<max_no; i++) {
      v_seito.push_back( seito[ i ] );
   }
}

▲上へ [ 編集 ]

sample 5-5 表示サンプル

■ 1. main()     ・・・ プログラムの開始 ・・・
■ 2. move_arr() ・・・ テストデータの代入 ・・・
■ 3. out_dsp()  ・・・ 全データを表示 ・・・

no age birth bt bg name               memo
-------------------------------------------------------
 1  14   4/1  A  g 木之本 桜          はにゃーん・ほえ〜
 2  13   9/3  A  g 大道寺 知世        ビデオ撮影に執着
 3  14  7/13  O  b 李 小狼            無口
 4  13  3/25  B  g 李 苺鈴            気が強い
 5  13  3/23 AB  b 柊沢 エリオル      クロウの生まれ変わり
 6  13   6/1 AB  b 山崎 貴史          ホラ吹き
 7  14  5/28  O  g 三原 千春          山崎と幼なじみ
 8  14  6/24  A  g 佐々木 利佳        落ち着いている
 9  13 10/11 AB  g 柳沢 奈緒子        眼鏡っ子で怪談好き
-------------------------------------------------------
*bt=血液型 *bg=性別

続行するには何かキーを押してください . . .

▲上へ [ 編集 ]

独自ソートの動作チェック(構造体以前)

 std::sort, qsort を使用せず、以下のコードを、構造体を使って実現する方法を考える。

構造体
struct sortdata {
   int idx;
   int data;
};
※これをベースに修正する。

※qsort は複数条件ソートで以前の並びを維持できない。
※std::sort は、なんか難しそうなので取り合えずパス。

  • 問題点
    • テストデータ作成関数 testArrData() が、構造体に未対応。


sample sort
#include <iostream>
#include "testArrData.h"
using namespace std;
void swap(int* x, int* y);
void sort(int* p, int* pi, int n);
int main(void) {
   const int arr_elm = 100;
   int idx[arr_elm];
   int arr_tbl[arr_elm];
   testArrData(arr_tbl, arr_elm);
   sort(arr_tbl, idx, arr_elm);           // sort 実行
   for(int i=0; i < arr_elm; i++) {       // 結果表示
      printf("idx[%3i]:%3i \n",idx[i], arr_tbl[i]);
   }
}
// sort
void sort(int* p, int* pi, const int n) {
   int k = n-1;
   while(k>=0) {
      int i=1, j=-1;
      for(; i<=k; i++) {
         if( *(p+i-1) > *(p+i) ) {
            j = i-1;
            swap(p+i, p+j);  // 対象データ
            swap(pi+i,pi+j); // 並び順も合せて入替える
         }
      }
      k = j;
   }
}
// swap
void swap(int* x, int* y) {
   int temp = *x;
   *x = *y;
   *y = temp;
}
※初期の index を idx へ構造体を使用せず保持し、ソート後の状態が確認可能に修正。

▲上へ [ 編集 ]
2008年07月12日(土) 12:16:07 Modified by cafeboy1




スマートフォン版で見る

×

この広告は60日間更新がないwikiに表示されております。