ショッピングモール  


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


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

No.2898

malloc関数を用いた構造体のクイックソート
投稿者---初心者(2004/11/01 18:58:35)


ソース自体は作り表示はされるのですが、
ソートされずにそのまま表示されてしまいます。
間違ってる箇所やソートされない原因あれば教えてください。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Person_Data_NULL ((struct person_data *) NULL)
struct person_data{
    int index;
    char name[11];
    int number;
    float weight;
    struct person_data *next_person_data;
    struct person_data *prev_person_data;
};

struct root_data{
    struct person_data *person_data_p;
};


/* クイックソート */

void quicksort(int sort,struct person_data *left_p,struct person_data *right_p){
    
    struct person_data *pivot = NULL;
    struct person_data *temp = NULL;
    struct person_data *start_data = NULL;
    struct person_data *end_data = NULL;

    start_data = left_p;
    end_data = right_p;

    /*入れ替え用tempの領域確保*/
    temp = (person_data *)malloc(sizeof(person_data));
    memset(temp,0,sizeof(temp));

    /*基準値の決定*/
    for(pivot = left_p; pivot->index<(left_p->index + right_p->index)/2;){
        pivot = pivot->next_person_data;
    }

    for(;;){
        /*基準値を基に数値の検索*/
        if(sort == 1){
            while(strcmp(left_p->name,pivot->name)<0)
                left_p = left_p->next_person_data;
            
            while(strcmp(right_p->name,pivot->name)>0)
                right_p = right_p->prev_person_data;
            
        }else if(sort == 2){
            while(left_p->number < pivot->number)
                left_p = left_p->next_person_data;
            
            while(right_p->number > pivot->number)
                right_p = right_p->prev_person_data;
            
        }else if(sort == 3){
            while(left_p->weight < pivot->weight)
                left_p = left_p->next_person_data;
            
            while(right_p->weight > pivot->weight)
                right_p = right_p->prev_person_data;
            
        }
        if(left_p->index >= right_p->index) break;
        
        /*数値の入れ替え*/
        strcpy(temp->name,left_p->name);
        strcpy(left_p->name,right_p->name);
        strcpy(right_p->name,temp->name);

        temp->number = left_p->number;
        left_p->number = right_p->number;
        right_p->number = temp->number;

        temp->weight = left_p->weight;
        left_p->weight = right_p->weight;
        right_p->weight = temp->weight;

        left_p = left_p->next_person_data;
        right_p = right_p->prev_person_data;
        }

    /*左右部に分けてのクイックソート*/
    if(left_p->next_person_data > start_data)   quicksort(sort,left_p->next_person_data,start_data);
    if(end_data < right_p->prev_person_data)    quicksort(sort,end_data,right_p->prev_person_data);
    }
/*ダミープログラム*/
void main(){
    struct root_data start_data,end_data;
    int count,sort,end;
    struct person_data *person_data_p;

    start_data.person_data_p = Person_Data_NULL;

    for(count = 0;; count++){
        if(count == 0){
            person_data_p = start_data.person_data_p
                =(struct person_data *)malloc(sizeof(struct person_data));
            person_data_p -> prev_person_data = Person_Data_NULL;
        }else{
            end_data.person_data_p = person_data_p;
            person_data_p = person_data_p->next_person_data
                =(struct person_data *)malloc(sizeof(struct person_data));
            person_data_p->prev_person_data = end_data.person_data_p;
        }
        person_data_p->next_person_data = Person_Data_NULL;

        printf("Your name ? ->");
        scanf("%s",&person_data_p->name);
        printf("Your number ? ->");
        scanf("%d",&person_data_p->number);
        printf("Your weight ? ->");
        scanf("%f",&person_data_p->weight);
        printf("if continue input 1 or end input 2->");
            scanf("%d",&end);
        person_data_p->next_person_data = Person_Data_NULL;
        if(end == 2){
            end_data.person_data_p = person_data_p;
            break;
        }
    }
    printf("sort name->1 number->2 weight->3\n");
    scanf("%d",&sort);

    quicksort(sort,start_data.person_data_p,end_data.person_data_p);

    for(person_data_p = start_data.person_data_p;
        person_data_p != Person_Data_NULL;
        person_data_p = person_data_p->next_person_data){
        printf("%s\t",person_data_p->name);
        printf("%d\t",person_data_p->number);
        printf("%.1f\n",person_data_p->weight);
    }
}




この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> 書き忘れましたすみません。 2899 初心者 2004/11/01 19:19:52
<子記事> Re:malloc関数を用いた構造体のクイックソート 2900 ぽこ 2004/11/02 00:58:13
<子記事> Re:malloc関数を用いた構造体のクイックソート 2902 かずま 2004/11/02 10:00:03
<子記事> Re:malloc関数を用いた構造体のクイックソート 2905 初心者 2004/11/03 00:32:44


No.2899

書き忘れましたすみません。
投稿者---初心者(2004/11/01 19:19:52)


使ってるパソコンは、windowsXPでソフトはVisual C++.NETです。
よろしくお願いします。


この投稿にコメントする

削除パスワード

No.2900

Re:malloc関数を用いた構造体のクイックソート
投稿者---ぽこ(2004/11/02 00:58:13)


>ソース自体は作り表示はされるのですが、
>ソートされずにそのまま表示されてしまいます。
>間違ってる箇所やソートされない原因あれば教えてください。

原因は分かりませんが、ソースを眺めて"?"と思ったところをば。

1.構造体のSWAP
> /*数値の入れ替え*/
> strcpy(temp->name,left_p->name);
> strcpy(left_p->name,right_p->name);
> strcpy(right_p->name,temp->name);
     ・・・(略)・・・
> right_p->weight = temp->weight;

構造体の代入で行けませんか?

2.ソート範囲
/*左右部に分けてのクイックソート*/
> if(left_p->next_person_data > start_data) quicksort(sort,left_p->next_person_data,start_data);
> if(end_data < right_p->prev_person_data) quicksort(sort,end_data,right_p->prev_person_data);

引数の名前を見るに、ソートするリストの開始要素と終了要素が逆のような。。
if文の中の条件もmalloc()で確保した領域のアドレスを比較しても意味ないです。

3.初期化してない?
名前や体重等の入力→構造体へ代入の際に構造体メンバindexに何も入っていないようですが。。
ソートのルーチンの中で基準値を求める処理にindexを利用しているのでまずいのでは?


この投稿にコメントする

削除パスワード

No.2901

Re:malloc関数を用いた構造体のクイックソート
投稿者---ぽこ(2004/11/02 01:09:35)


ちょんぼです。
下のコメントは嘘でした、すみません(-_-;)

>1.構造体のSWAP
>> /*数値の入れ替え*/
>> strcpy(temp->name,left_p->name);
>> strcpy(left_p->name,right_p->name);
>> strcpy(right_p->name,temp->name);
>     ・・・(略)・・・
>> right_p->weight = temp->weight;
>
>構造体の代入で行けませんか?



この投稿にコメントする

削除パスワード

No.2902

Re:malloc関数を用いた構造体のクイックソート
投稿者---かずま(2004/11/02 10:00:03)


与えられたソースを見る気が起こらなかったの、ちょっと違うプログラムを
書いてみました。リストは双方である必要はないと思うのですが。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct PersonData {
    int   index;
    char  *name;
    int   number;
    float weight;
    struct PersonData *next;
} PersonData;

void *e_malloc(size_t n)
{
    void *p = malloc(n);
    if (p == NULL) puts("out of memory"), exit(1);
    return p;
}

PersonData *concat(PersonData *a, PersonData *b)
{
    PersonData *p;
    if (a == NULL) return b;
    for (p = a; p->next; p = p->next) ;
    p->next = b;
    return a;
}

PersonData * quicksort(
    PersonData *p, int comp(const PersonData *, const PersonData *))
{
    PersonData *pivot, *lt = NULL, *eq = NULL, *gt = NULL, *next;

    if (p == NULL || p->next == NULL) return p;
    for (pivot = p; p; p = next) {
        int diff = comp(p, pivot);
        next = p->next;
        if (diff < 0)
            p->next = lt, lt = p;
        else if (diff > 0)
            p->next = gt, gt = p;
        else
            p->next = eq, eq = p;
    }
    return concat(quicksort(lt, comp), concat(eq, quicksort(gt, comp)));
}

int comp1(const PersonData *a, const PersonData *b)
{
    return strcmp(a->name, b->name);
}

int comp2(const PersonData *a, const PersonData *b)
{
    return (a->number < b->number) ? -1 : (a->number > b->number);
}

int comp3(const PersonData *a, const PersonData *b)
{
    return (a->weight < b->weight) ? -1 : (a->weight > b->weight);
}

int (*comp[3])(const PersonData *, const PersonData *) = {
    comp1, comp2, comp3
};

int main(void)
{
    PersonData *head = NULL, *p;
    int index = 0, sort;  char name[256];

    for (;;) {
        p = e_malloc(sizeof(PersonData));
        printf("Your name (end = '.')? ->");
        if (scanf("%s", name) != 1 || strcmp(name, ".") == 0) break;
        p->name = e_malloc(strlen(name) + 1);
        strcpy(p->name, name);
        printf("Your number ? ->");
        if (scanf("%d", &p->number) != 1) break;
        printf("Your weight ? ->");
        if (scanf("%f", &p->weight) != 1) break;
        p->index = ++index;
        p->next = head;
        head = p;
    }

    do {
        printf("sort name->1 number->2 weight->3\n");
        if (scanf("%d", &sort) != 1) return 1;
    } while (sort < 1 || sort > 3);

    head = quicksort(head, comp[sort-1]);

    for (p = head; p; p = p->next)
        printf("%-8s %-8d %.1f\n", p->name, p->number, p->weight);
    return 0;
}



この投稿にコメントする

削除パスワード

No.2905

Re:malloc関数を用いた構造体のクイックソート
投稿者---初心者(2004/11/03 00:32:44)


ソートの範囲に関して、ぽこさんのご指摘通りでした。
indexに関しては、inputを入れ忘れていました。
数値によってはもう少しエラーが出ますが、
大分改善されました。ありがとうございます^^。

かずまさんのソースに関しては、まだ試していないので、
改良の参考にさせていただきます。
ありがとうございます。



この投稿にコメントする

削除パスワード

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




掲示板提供:Real Integrity