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++ C++/CLI C# 関連
- VC++ 2005 Express のインストール
- C/C++ の簡単なプログラム例
- 変数・定数
- 応用的プログラミング
- プログラムの分割/ダイナミックリンクライブラリ など
- その他
- C/C++ その他::書式文字/ESC code など
- VB2005リファレンス（覚え書き）
- SQL文：SQLステートメント
- VBA(VisualBasic for Applications)
外部リンク
- 現在ありません
▲上へ
構造体とポインタのサンプルコード
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