4

構造体配列を2つの基準でソートする方法(クイックソートアルゴリズムを使用)を見つけようとしています。たとえば、次の構造体があるとします。

struct employee{
   char gender[12];
   char name[12];
   int id;
};

私の入力は次のとおりです。

struct employee arr[3]=
{
    {"male","Matt",1234},
    {"female","Jessica",2345},
    {"male","Josh",1235}
};

最初に性別で要素を並べ替え、次に ID を昇順で並べ替えたいと考えています。例としては、最初にすべての男性の ID を順番に印刷し、次にすべての女性の ID を印刷します。qsort 関数を使用せずにこれを実行しようとしていますが、チェックする方法が少しわかりません。これが私のソート機能です：

void quicksort(struct employee *arr, int left, int right)
{
    int pivot, l, r, temp;
    if(left < right)
    {
        p = left;
        l = left;
        r = right;
        while(l < r)
        {

            while(arr[l].id <= arr[p].id && l <= right)
                l++;
            while(arr[r].id > arr[p].id && r >= left)
                r--;

            if(l < r)
            {
                temp = arr[l].id;
                arr[l].id = arr[r].id;
                arr[r].id = temp;
            }
        }


        temp = arr[r].id;
        arr[r].id = arr[p].id;
        arr[p].id = temp;

        quicksort(arr, left, r-1);
        quicksort(arr, r+1, right);
    }
}

助言がありますか？strcmp を使用できると思っていましたが、関数内のどこに含めるかわかりません。

4

5 に答える 5

5

確かに、比較関数とそのためのスワッパーをインライン化できます。以下のコードは非常に基本的なもので、有効なポインターに依存していますが、おわかりいただけると思います。また、クイックソートを自由にトリミングして、途中でオフになったものを修正しました（願っています）。

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

// employee record
struct employee
{
    char gender[12];
    char name[12];
    int id;
};

// swap employee records
void swap_employee(struct employee *left, struct employee *right)
{
    struct employee tmp = *right;
    *right = *left;
    *left = tmp;
}

// compare employee records
int compare_employee(const struct employee* left,
                     const struct employee* right)
{
    int gender = strcmp(left->gender, right->gender);
    return (gender ? gender : (left->id - right->id));
}

// quicksort for employees
static void quicksort_(struct employee *arr, int left, int right)
{
    struct employee p = arr[(left+right)/2];    // as good as any
    int l = left, r = right;   // movable indicies

    while (l <= r)
    {
        while (compare_employee(arr+l, &p) < 0)
            ++l;
        while (compare_employee(arr+r, &p) > 0)
            --r;
        if (l <= r)
        {
            swap_employee(arr+l, arr+r);
            ++l; --r;
        }
    }

    if (left < r)
        quicksort_(arr, left, r);
    if (l < right)
        quicksort_(arr, l, right);
}

// exposed API
void quicksort(struct employee *arr, int count)
{
    if (arr && (count>0))
        quicksort_(arr, 0, count-1);
}

/* sample usage */
int main(int argc, char *argv[])
{
    struct employee arr[]=
    {
        {"male","Matt",1234},
        {"female","Jessica",2345},
        {"male","Josh",1235},
        {"female","Betsy",2344},
        {"male","Roger",1233}
    };

    quicksort(arr, sizeof(arr)/sizeof(arr[0]));

    for (int i=0;i<sizeof(arr)/sizeof(arr[0]);++i)
        printf("%s, %s, %d\n", arr[i].gender,arr[i].name, arr[i].id);

    return EXIT_SUCCESS;
}

結果

female, Betsy, 2344
female, Jessica, 2345
male, Roger, 1233
male, Matt, 1234
male, Josh, 1235
于 2012-11-14T07:05:13.733 に答える
1

それは難しいことではありません。構造体を比較するには、関数（または「ハードコーディング」したいコードブロック）が必要です。あなたが与えたサンプルコードでは、を使用して現在のオブジェクトを比較していますarr[l].id <= arr[p].id。つまり、要素がどこに収まるかを判断するために id のみを検討しています。この時点で、他のフィールドを使用して比較する必要があります。関数を使用すると、はるかに整頓されます（以前の質問でそのような関数を提供しました）。

また、スワップ時に id フィールドのみをシフトし、データ項目の名前と性別を変更しません。構造体全体を移動する必要があります。

于 2012-11-14T05:45:35.693 に答える
0

組み込みの を使用して、qsort最初に性別を比較し、最初の比較で「同点」の場合にのみ ID 番号を参照するコンパレータ関数を渡します。

于 2012-11-14T05:34:39.160 に答える
0

配列を最初に性別でソートする必要があると思います。1 つは男性用、もう 1 つは女性用です。次に、quicksort 関数を使用して、これら 2 つの配列内で並べ替えます。

strcmp を使用して、元の配列を 2 つの配列 (男性用と女性用) に並べ替えることができます。

于 2012-11-14T05:45:18.027 に答える
0 
int compare_employee (struct employee * a, struct employee * b) {
    int diff = strcmp(a->gender, b->gender);

    if (diff) // if gender different
        return -diff; // sort descending, please double check this and reverse in case I am wrong

    return a->id - b->id; // else sort by id
}

の場合は負の数、 の場合a < bは正の数a > b、等しい場合はゼロを出力します。

独自のクイックソートで使用するか、qsortコンパレーターとして使用します。

于 2012-11-14T05:49:16.223 に答える