掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.30365

構造体配列の要素を比較して順位を付けたい
投稿者---さき(2007/06/25 17:06:33)


お世話になります。
構造体配列の要素を比較して順位を付けたいんです。
ソートすれば早い話だとご指摘があると思いますけど
ソートせずに比較して順位を付けたいんです。
私が考えたプログラムはループや比較が多くて変かな?と
思いましたので、未熟な私にご教授いただけたら嬉しいです。
環境は依存しないと思います。

構造体には要素aと要素bを用意しています。
aの値が大きいもの順で、aの値が同じならbの値の高いもの順に
順位を付けていきます。
(要するにa→bの降順ソートみたいなものです)
以下に私の考えたソースを載せます。

順位比較用の構造体
typedef struct
{
    int a;    //比較条件要素a
    int b;    //比較条件要素b
    int juni;   //順位
} STR;

void main()
{
    STR str[]={
        {1,3,0},
        {8,5,0},
        {3,8,0},
        {5,7,0},
        {6,5,0},
        {8,2,0},
        {7,1,0},
        {8,5,0},
        {8,3,0},
        {5,4,0}
    };

    //構造体の個数算出
    int max = sizeof(str) / sizeof(STR);
    //構造体の最初を比較対象としてセット
    int index = 0;
    //順位のループ
    for( int i = 1; i <= max; i++ ){
        for( int j = 0; j < max; j++ ){
            // 順位を付けていないもの(juni=0)が比較対象
            if(str[j].juni == 0 ){
                if( str[j].a > str[index].a ){
                    index = j;
                }else if( str[j].a == str[index].a && j != index ){
                    //要素aが同じ場合は要素bを比較する
                    if( str[j].b > str[index].b ){
                        index = j;
                    }
                }
            }
        }
        //比較結果で最大のものに順位を入れる
        str[index].juni = i;
        //構造体の初期比較対象をセット
        for( int k = 0; k < max; k++ ){
            if( str[k].juni == 0 ){
                index = k;
                break;
            }
        }
    }
}


結果
str
[0] {a=1 b=3 juni=10 }
[1] {a=8 b=5 juni=1 }
[2] {a=3 b=8 juni=9 }
[3] {a=5 b=7 juni=7 }
[4] {a=6 b=5 juni=6 }
[5] {a=8 b=2 juni=4 }
[6] {a=7 b=1 juni=5 }
[7] {a=8 b=5 juni=2 }
[8] {a=8 b=3 juni=3 }
[9] {a=5 b=4 juni=8 }

結果は思ったとおりなので問題ないのですけど、
冒頭でも言いましたように私はC言語はまだまだ未熟です。
ループとか少ない方がプログラムとして良いと思いますので、
もっと良い方法があれば教えていただけないでしょうか。
よろしくお願いします。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:構造体配列の要素を比較して順位を付けたい 30371 ゾン兵衛 2007/06/25 22:41:30
<子記事> Re:構造体配列の要素を比較して順位を付けたい 30373 yoh2 2007/06/25 23:20:41


No.30371

Re:構造体配列の要素を比較して順位を付けたい
投稿者---ゾン兵衛(2007/06/25 22:41:30)



 これでどうでしょうか。
#include <stdio.h>

typedef struct
        {
            int a;    //比較条件要素a
            int b;    //比較条件要素b
            int juni;   //順位
        } STR;

int main(void)
{
    STR str[] = {{1,3,1}, {8,5,1}, {3,8,1}, {5,7,1}, {6,5,1},
                {8,2,1}, {7,1,1}, {8,5,1}, {8,3,1}, {5,4,1},};
    int i, j;
    int max = sizeof(str) / sizeof(STR);
    
    for(i = 0; i < max - 1; i ++){
        for(j = i + 1; j < max; j ++){
            str[i].juni += (str[i].a < str[j].a);
            str[j].juni += (str[i].a > str[j].a);
            if(str[i].a == str[j].a){
                str[i].juni += (str[i].b < str[j].b);
                str[j].juni += (str[i].b > str[j].b);
            }
        }
    }
    for(i = 0; i < max; i ++){
        printf("[%d] {a = %d b = %d juni = %2d}\n",
                 i, str[i].a, str[i].b, str[i].juni);
    }
    return 0;
}




この投稿にコメントする

削除パスワード

No.30373

Re:構造体配列の要素を比較して順位を付けたい
投稿者---yoh2(2007/06/25 23:20:41)


>私が考えたプログラムはループや比較が多くて変かな?と
>思いましたので、未熟な私にご教授いただけたら嬉しいです。

外側のループの後半で、次の初期値を探している分、確かにループの数も
多いのですが、他にも、ネストが深くなっているせいで余計に複雑に
見えるのではないでしょうか。
構造体の比較部分を関数化して、ネストの段数を減らすだけでもそれなりにすっきりすると思いますよ。

// *s1 > *s2ならば非ゼロ、それ以外ならば0。
int str_gt(const STR *s1, const STR *s2)
{
    if(s1->a > s2->a){
        return 1;
    }
    else if((s1->a == s2->a) && (s1->b > s2->b)){
        return 1;
    }
    else{
        return 0;
    }
}

...

    //構造体の個数算出
    int max = sizeof(str) / sizeof(STR);
    //構造体の最初を比較対象としてセット
    int index = 0;
    //順位のループ
    for( int i = 1; i <= max; i++ ){
        for( int j = 0; j < max; j++ ){
            // 順位を付けていないもの(juni=0)が比較対象
            if( (str[j].juni == 0) && str_gt(&str[i], &str[index]) ){
                index = j;
            }
        }
        //比較結果で最大のものに順位を入れる
        str[index].juni = i;
        //構造体の初期比較対象をセット
        for( int k = 0; k < max; k++ ){
            if( str[k].juni == 0 ){
                index = k;
                break;
            }
        }
    }


オマケで、ちょっと考えついたコードをば。
視点を変えて、順位 = 自分より大きい要素の数 + 1、といった性質を利用してみました。
ぱっと見は割とすっきりしていますが、オーダーはさきさんのものと同じで、
要素数の2乗回になりますので、速いコードではありません。
ちなみに同順の要素があってもうまく順位付けできたりします。
// *s1と*s2の大小比較。
// 戻り値 <  0: *s1 < *s2
//        == 0: *s1 == *s2
//        >  0: *s1 > *s2
int str_compare(const STR *s1, const STR *s2)
{
    if(s1->a > s2->a){
        return -1;
    }
    else if(s1->a < s2->a){
        return 1;
    }
    else if(s1->b > s2->b){
        return -1;
    }
    else if(s1->b < s2->b){
        return 1;
    }
    else{
        return 0;
    }
}

...

    for(size_t i = 0; i < max; i++){
        str[i].juni++;  // "+ 1"の分。

        for(size_t j = i + 1; j < max; j++){
            int cmp = str_compare(&str[i], &str[j]);

            // str[i]とstr[j]のうち、小さい方の順位をひとつ下げる。
            if(cmp < 0){
                str[i].juni++;
            }
            else if(cmp > 0){
                str[j].juni++;
            }
        }
    }



この投稿にコメントする

削除パスワード

No.30374

Re:構造体配列の要素を比較して順位を付けたい
投稿者---yoh2(2007/06/25 23:23:46)


は、後半部分のコード、ゾン兵衛さんのと完全に被ったorz


この投稿にコメントする

削除パスワード

No.30375

Re:構造体配列の要素を比較して順位を付けたい
投稿者---yoh2(2007/06/25 23:35:20)


> int str_compare(const STR *s1, const STR *s2)
> {
>     if(s1->a > s2->a){
>         return -1;
>     }
>     else if(s1->a < s2->a){
>         return 1;
>     }
>     else if(s1->b > s2->b){
>         return -1;
>     }
>     else if(s1->b < s2->b){
>         return 1;
>     }
>     else{
>         return 0;
>     }
> }

……不等号まるっきり逆でした。この関数に付けたコメントの方が正解です。
ひっくり返して読んで下さい。

# 落ち着け > 俺


この投稿にコメントする

削除パスワード

No.30378

Re:構造体配列の要素を比較して順位を付けたい
投稿者---さき(2007/06/26 09:41:36)


ゾン兵衛さんyoh2さんどうもありがとうございます。

ゾン兵衛さんの書いて下さった
str[i].juni += (str[i].a < str[j].a);
この発想は知りませんでした。
比較した結果が正ならば1、負ならば0を返しているということですよね?
まだまだ勉強不足です・・・
このような比較はif文でしか使ったことなかったので目から鱗です。

yoh2さんのおっしゃるように比較用の関数を作って
見た目をすっきりさせることも大切だと思います。
見た目が複雑になると、自分でもプログラムを追っていくのが
大変で分かり辛くなります^^
このような着想を書いて下さって感謝しています。

お二方のアドバイスとても参考になりました。
コードをそのまま使ったりはせずに、アドバイスを元に
自分なりに考えてみます。
どうもありがとうございました!


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧