C言語で自己参照構造体(beforeとnextで繋げてます)で名簿をつくり、年齢で昇順ソートをしようと考えています。
 そこで、ソート関数の「qsort」というものを使ってソートしたいのですが、どのように使ったらいいのでしょうか?

 参考例などがありましたら、教えていただけますか?
 よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

標準関数のqsortを使用するのですよね?


qsortには配列を渡してあげなきゃいけないので
ノードで持っているのを配列に作り直してからqsortをかけて
最後にノードの再構築をしなくてはならないと思います。


struct person{
 struct person* before;
 struct person* next;
 int age
};

/* 比較関数 */
int compare(const void *e1, const void *e2)
{
 struct person* p1 = *((person**)e1);
 struct person* p2 = *((person**)e2);
 return p1->age - p2->age;
}

struct person* sort(struct person* top)
{
 int i,count;
 struct person *new_top;
 struct person *p;
 struct person *prev;
 struct person** array;

 /* 要素数をカウント */
 for(count=0,p=top;p;p=p->next) count++;

 /* 配列を作成 */
 array = (struct person**)malloc(count*sizeof(struct person*));
 for(i=0,p=top;p;p=p->next) array[i++]=p;

 /* qsort */
 qsort(array,count,sizeof(struct person*),compare);

 /* nodeを作り直す */
 prev = new_top = array[0];
 new_top->before = null;
 new_top->next = null;
 for(i=1;i<count;i++){
  prev->next = p = array[1];
  p->before = prev;
  p->next = null;
  prev = p;
 }

 //配列の開放
 free(array);
 return new_top;
}

基本的に考え方はこうなります。
実際にコンパイルして確かめたわけじゃないので、エラー等おきるかもしれませんが(^^;

この回答への補足

試してみたのですが、エラーがおきてしまいました。error C2018:文字'0x81'は認識できません。と error C2018:文字'0x40'は認識できません。というようなエラーが出てしまったのですが、これはどういったことなんですか?教えていただけますか?よろしくお願いします。

補足日時:2002/01/25 13:14
    • good
    • 0

>試してみたのですが、エラーがおきてしまいました。



カットアンドペーストしたのなら空白を全角スペースで入れてるので
全角スペースをタブなり半角スペースに変えてみて下さい。
    • good
    • 0
この回答へのお礼

参考になりました。ありがとうございます。また何かありましたら、よろしくお願いします。ではでは

お礼日時:2002/01/30 16:12

標準関数のqsort()は配列に収められたデータをソートするものですから、


おっしゃるような構造のデータには適用できないと思います。
アルゴリズム自体はそれほど難しいものではなく、再帰的アルゴリズムの
練習によく使われたりするものですから、自作されてはいかがでしょう。
検索サイトでクイックソートを検索すると、いくつも紹介しているサイトが
見つかります。
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q構造体のマスクというメンバ

一般的な構造体についての質問です。
例えば CHOOSECOLOR 構造体のようにメンバにマスクを持つ構造体があって、
その構造体に値を代入する関数を使うには、CHOOSECOLOR 構造体のマスクを
設定し、そのマスクで有効にしたメンバだけが値を入れられるんですよね?
マスクを持つ構造体というのは、それに値を入れる関数を使う前に
マスクを指定してから、その構造体のアドレスを関数の引数にセット
するんですよね?
マスクは無視されて、それ以外の全てのメンバに値が入るというわけでは
ないですよね?

Aベストアンサー

CHOOSECOLORにマスクは無いと思いますよ。
CHARFORMATですか?CHARFORMATならEM_GETCHARFORMATでbCharSetメンバだけに値を得ることになっているからEM_GETCHARFORMATするときのマスクは参照されません。
その他、SCROLLINFOとか普通のやつはマスクで有効にしたメンバだけがGet*()で得られるメンバです。

Qqsort/クイックソートについて

構造体の配列をqsortで昇順に並び替えるプログラムを作成しています。
対象は数値項目で、単純にNo順に並び替えるイメージです。

クイックソートは、配列の内容によって処理時間が変わると聞いたので、一番遅くなる場合の時間を調べたいのですが、どのような並びだと一番遅くなるのでしょうか?

Aベストアンサー

「値が等差数列で、並べたい順番と真逆に並んでいる時」が最悪と言われています。

例えば
8、7、6、5、4、3、2、1

1、2、3、4、5、6、7、8
に並べ替える場合など。

但し、ライブラリのqsortは「要素数がある程度少なくなった場合、アルゴリズムをクイックソート以外の物に切り換える場合がある」ので、クイックソートの計算量を検証する場合は「ソートルーチンを自作」しないと、正確な数値は計れません。

Q条件によって構造体のリスト構造を変えたい

こんにちは。

C(C++)で構造体を使っているのですが、まだまだ未熟で使い方が良く分かりません。以下のことを実施したいのですが、やり方をどなたかご教授頂けませんでしょうか。よろしくお願いします。

条件によって構造体のリスト構造を変えたいのです。
例えば、
条件1の場合は
構造体a→構造体b

条件2の場合は、
構造体a→構造体c

上記のようにです。そして構造体のルートから参照先をたどっていくことで、配下の構造体の値を取得したいのです。

文法上許されないようですが、イメージとしては、
struct a aa;
aa.c->b.aa

ということをしたいのです。よろしくお願いします。

struct a{
char a;
char b;
struct c;
:
};

struct b{
char aa;
:
};

struct c{
:
:
};

Aベストアンサー

一番手っ取り早いのは、構造体aの中に、構造体bと構造体cの両方のポインタを持たせておいて、使わない側にはNULLを入れるといった方法でしょうか。

struct a
{
 /* .bまたは.cのNULLではない方が有効 */
 struct b *b;
 struct c *c;
};

他には、構造体aと構造体bの最初のフィールドの型を同じにしておいて、そこにaかbかを判別できる値を格納するようにし、構造体aと構造体bの共用体へのポインタを構造体aに持たせるといった方法です。

struct b
{
 char tag; /* 'b'を格納 */
 ...
};

struct c
{
 char tag; /* 'c'を格納 */
 ...
};

struct a
{
 union
 {
  struct b;
  struct c;
 } *p; /* .p->b.tagが'b'なら構造体b, 'c'なら構造体c */
};

好みかもしれませんが、私なら多分前者を使います。

一番手っ取り早いのは、構造体aの中に、構造体bと構造体cの両方のポインタを持たせておいて、使わない側にはNULLを入れるといった方法でしょうか。

struct a
{
 /* .bまたは.cのNULLではない方が有効 */
 struct b *b;
 struct c *c;
};

他には、構造体aと構造体bの最初のフィールドの型を同じにしておいて、そこにaかbかを判別できる値を格納するようにし、構造体aと構造体bの共用体へのポインタを構造体aに持たせるといった方法です。

struct b
{
 char tag; /* 'b'を格納 */
 ...
};
...続きを読む

Q昇順ソート

sort.txtから読み込んだ値を
昇順でソートして出力するにはどうしたらよいでしょうか?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

/* 比較関数 */
int strcmp_asc(const void *, const void *);

int main(void)
{

FILE*fin, *fout;
inti;
intlength;
chars[256], s2[256];

if( (fin=fopen("sort.txt","r"))==NULL) {
printf("入力ファイルがオープンできません\n");
exit(EXIT_FAILURE);
}
if( (fout=fopen("file2.txt","w"))==NULL) {
printf("出力ファイルがオープンできません\n");
exit(EXIT_FAILURE);
}

while(fgets(s, 256, fin) != NULL) {

/* 要素数を求める */
length = sizeof(s) / 256;

/* 昇順でソート */
qsort(s, length, 256, strcmp_asc);

/*memset(s2, NULL, sizeof(s2));
for (i = 0; i < length; i++)
{

}
*/

fprintf(fout,"%s\n",s2);
}

fclose(fin);
fclose(fout);
return 0;
}

int strcmp_asc(const void *sa, const void *sb)
{
return strcmp((char *)sa, (char *)sb);
}


sort.txt
50
45
35
25
15
10
5
1
32
46
8
7
9
19
18
14
16
13
12
17
11
20
40
30
31
3
2
37
38
36
33
39
34
49
47
48
4
6
44
42
43
41
21
22
26
24
28
29
27
23

sort.txtから読み込んだ値を
昇順でソートして出力するにはどうしたらよいでしょうか?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

/* 比較関数 */
int strcmp_asc(const void *, const void *);

int main(void)
{

FILE*fin, *fout;
inti;
intlength;
chars[256], s2[256];

if( (fin=fopen("sort.txt","r"))==NULL) {
printf("入力ファイルがオープンできません\n");
exit(EXIT_FAILURE);
}
if( (fout=fopen("file2.txt","w"))==NULL) {
prin...続きを読む

Aベストアンサー

★アドバイス
>sort.txtから読み込んだ値を
>昇順でソートして出力するにはどうしたらよいでしょうか?
 読み込み部分が正しくないありませんね。
 ファイルに数値のみしかないならfscanf()関数を使って
 すべてを配列に代入してからソートすれば良いでしょう。
・下にサンプルを載せておきます。

サンプル:
int data[ 10000 ]; ←ちょっと多めに宣言
int max;

// fscanfで読み込み
for ( max = 0 ; max < 10000 ; max++ ){
 if ( fscanf(fin,"%d\n",&data[max]) != 1 ){
  break;
 }
}
// ここでソート
qsort( data, max, sizeof(int), strcmp_value );

注意事項:
・比較関数の strcmp_value は作り直して下さい。
 作り方分かりますよね。
 ポイントは整数値の比較ですよ。

Q構造体の宣言

下記のように構造体の宣言をした所、

struct B_PARAM test;

「`test' の領域サイズがわかりません」というエラーになってしまいました。この構造体を宣言し、値を入れていこうとしています。

ヘッダファイルに構造体の形は定義してあるのですが、
構造体の中に構造体があるからでしょうか?

またこの構造体を正しく宣言するにはどうすればいいのでしょうか?

Aベストアンサー

typedef struct _B_PARAM {
char p1;
char p2[2];
} B_PARAM;

の、_B_PARAM は、構造体の「タグ名」です。
これは、sutruct とともに使う名前です(C++ struct 無しでもOK)
ですから、この例では、struct _B_PARAM で正解です。

後ろの、B_PARAM は、typedef した名前です。

おおざっぱに言えば、
struct _B_PARAM {
char p1;
char p2[2];
}
という構造体を、B_PARAM という名前で読み替えることを宣言しています。
ですから、こちらを使うのであれば、struct 無しの
B_PARAM test; で正解です。

構造体は必ず typedef しなければならないというものではありません。

Qqsortを用いた構造体配列のソート

お世話になります。

http://simd.jugem.jp/?eid=116
を参考にqsortを用いた構造体配列のソートをC言語で記述しようとしています。
上記のページは、構造体のメンバが配列でない場合です
今回は、メンバが配列のときの構造体配列のソートを実現したいと思っています。
つまり、
typedef struct{
int a;
int b[1024];
int c[1024];
}TEST;
という構造体配列があって、
TEST base[256];
と宣言し、メンバの配列の添え字を基準としてソートしたいときには、どのようにqsortを用いれば良いのでしょうか、ということです。
どうしたらよいかわからず途方にくれています。

つまり、下のようなソートが行われるには、どのようなプログラムを書けばいいかということです。

構造体でソートするものとします。
構造体でソートできれば、qsortを使っていなくても構いません。
プログラムの得意な方がおりましたら、ご教授下さい。

<ソート前>
//************************************************
test[ 0].b[0] = 3;
test[ 1].b[0] = 102;
...
test[255].b[0] = 1;
------------
test[ 0].b[1] = 99;
test[ 1].b[1] = 200;
...
test[255].b[1] = 2;
------------
...
------------
test[ 0].b[1023] = 99;
test[ 1].b[1023] = 9;
...
test[255].b[1023] = 200;
//**************************************************


<ソート後>:test[x]ではなく、b[y]を基準としてそれぞれのくくりをソートしたい
//************************************************
test[ 0].b[0] = 1;
test[ 1].b[0] = 3;
...
test[255].b[0] = 102;
------------
test[ 0].b[1] = 2;
test[ 1].b[1] = 99;
...
test[255].b[1] = 200;
------------
...
------------
test[ 0].b[1023] = 9;
test[ 1].b[1023] = 99;
...
test[255].b[1023] = 200;
**************************************************

お世話になります。

http://simd.jugem.jp/?eid=116
を参考にqsortを用いた構造体配列のソートをC言語で記述しようとしています。
上記のページは、構造体のメンバが配列でない場合です
今回は、メンバが配列のときの構造体配列のソートを実現したいと思っています。
つまり、
typedef struct{
int a;
int b[1024];
int c[1024];
}TEST;
という構造体配列があって、
TEST base[256];
と宣言し、メンバの配列の添え字を基準としてソートしたいときには、どのようにqsortを用いれば良いのでしょうか、という...続きを読む

Aベストアンサー

qsortは、ソート対象の個々の要素が連続していないと使えませんね。

1つのソートが256しかないのであれば、単純ソートを自分で書けば良いかと思います。
やや手抜きで書くと、

for(k=0; k<1024; k++){
for(i=0; i<255; i++){
for(j=i+1; j<256; j++){
if(test[i].b[k] > test[j].b[k]){
work=test[i].b[k];
test[i].b[k]=test[j].b[k];
test[j].b[k]=work;
}
}
}
}

Q構造体→文字列→構造体 をする方法

VB6.0の話です。

 不特定の構造体を文字列(String)に格納し、これを最初の構造体に戻す事はできませんか?

 具体的には「共有メモリを使い構造体を文字列にして格納>別ウインドウで文字列を取得して構造体に戻す」と言う事をやりたいんです。
 共有メモリに不特定の構造体をいれる方法でもいいんですが…VALIANTだとサイズが大きすぎて実用性がありませんし、違う主旨の質問をするのも良くないので回答はあくまで「構造体→文字列→構造体 をする方法」と言う事でお願いします。

Aベストアンサー

APIを使えば出来ます。

Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (cStr1 As Any, cStr2 As Any, ByVal iLen As Long)


構造体→文字列
Call CopyMemory(strB, ByVal typeA, Len(typeA))

文字列→構造体
Call CopyMemory(typeA, ByVal strB, Len(typeA))

ただし構造体のメンバに配列があると使えません(VBの配列はメモリを連続してとらない為、メモリーリークします)。

また構造体の中身は string *5 などの固定長である必要があります。

以上です。

Q配列のソート(昇順)

最大で30個の整数データを入力し、それを大きい順に並べ替えるプログラムを1次元配列と繰り返し・if文を使って作成しなさい。 という問題で

#include<stdio.h>

main()
{
int a[30],x,y,z;

printf("Seisu wo 30 ko Nyuryoku \n");
for(x=0;x<=29;x++)
scanf("%d",&a[x]);
printf("before sort...\n");
for(x=0;x<=29;x++)
printf("%d ",a[x]);
for(x=0;x<=28;x++)
for(y=0;y<=28-x;y++)
if(a[y]<a[y+1])
{
z=a[y];a[y]=a[y+1];a[y+1]=z;
}
printf("\n after sort...\n");
for(x=0;x<=29;x++)
printf("%d ",a[x]);
}

ここまで出来たのですが最大で30個ということなので(例)「10個の整数を入力して Z を入力したら終了」
としたいのですがどこをどのようにすればいいですか?

最大で30個の整数データを入力し、それを大きい順に並べ替えるプログラムを1次元配列と繰り返し・if文を使って作成しなさい。 という問題で

#include<stdio.h>

main()
{
int a[30],x,y,z;

printf("Seisu wo 30 ko Nyuryoku \n");
for(x=0;x<=29;x++)
scanf("%d",&a[x]);
printf("before sort...\n");
for(x=0;x<=29;x++)
printf("%d ",a[x]);
for(x=0;x<=28;x++)
for(y=0;y<=28-x;y++)
if(a[y]<a[y+1])
{
z=a[y];a[y]=a[y+1];a[y+1]=z;
}
pri...続きを読む

Aベストアンサー

プログラムをじっくり読んだワケではないですがfor文の条件式に「||」(または)を使って「a[y+1]!=z」(入力がzじゃない間)を追加するみたいにすればいいんじゃないですかね。
質問の意図に合っているといいんですが。

QPGにおいて構造体や列挙型はいつ使いますか?

PGにおいて構造体や列挙型はいつ使いますか?

構造体でテーブルみたいなものに一旦入れて、個別に取り出すときに使うと思うのですが、
DBを使ってたら、構造体を使う場所がよくわかりません。

どういうプログラミング時に構造体・列挙型を使うのか教えてください。

Aベストアンサー

複数の項目を一元管理したいとか、あとで(他人が)見た時に判り易いためとか、使う理由は様々あると思います。

例えば、RPG(ゲーム)のプログラミングで、
キャラクターのパラメーターとしてはHP、MP、ちから、すばやさ、EXP等々ありますね。

これを1つの構造体として定義しておく。

主人公 AS 構造体
仲間1 AS 構造体

のようにすれば、1人1人の各パラメータを宣言する手間が省けますし、
何より見やすいですね。
呼び出すときも、主人公.HP、仲間1.HP となってれば、判り易いです。

Qn個の要素を持つ配列xをシェルソートで昇順に整列

穴埋め問題ですが、for文の j -= k の考えで立ち止まります。
#include <stdio.h>

#define swap(X, Y) 【 1 】 ← X ^= Y, Y ^= X, X ^= Y

void shell(int x[ ], int n);

void main()
{
    int x[12] = {23, 67, 54, 82, 13, 28, 55, 61, 50, 32, 29, 44};
    int n = 12, i ;

    printf("配列(整列前)x => ");
    for( i = 0; i < n - 1; i++ )
        printf("%d, ",x[ i ]);
    printf("%d\n",x[ i ]);
 
    shell(x, n);

    printf("配列(整列後)x => ");
    for( i = 0; i < n - 1; i++ )
        printf("%d, ",x[ i ]);
    printf("%d\n",x[ i ]);
}

void shell(int x[ ], int n)
{
    int i, j, k = n ;

    while( 【 2 】 ){ ← k > 0
        【 3 】 ← k /= 2;
        for( i = 0; 【 4 】; i++)
            for( j = i; 【 5 】; j -= k)
             swap(x[j], x[j + k]);
    }
}

【 1 】【 2 】は自信があるのですが【 3 】はあまり自信がないです。
【 4 】と【 5 】はどうすれば出来ますか教えてください。お願いします。

穴埋め問題ですが、for文の j -= k の考えで立ち止まります。
#include <stdio.h>

#define swap(X, Y) 【 1 】 ← X ^= Y, Y ^= X, X ^= Y

void shell(int x[ ], int n);

void main()
{
    int x[12] = {23, 67, 54, 82, 13, 28, 55, 61, 50, 32, 29, 44};
    int n = 12, i ;

    printf("配列(整列前)x => ");
    for( i = 0; i < n - 1; i++ )
        printf("%d, ",x[ i ]);
    printf("%d\n",x[ i ]);
 
    shell(x, n);

  ...続きを読む

Aベストアンサー

while(k/2>0){ /* (2) */
k /= 2; /* (3) */
for(i=0;i+k<n;i++) /* (4) */
for(j=i;j>=0 && x[j]>x[j+k];j-=k) /* (5) */
swap(x[j],x[j+k]);
}


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング