C言語関係掲示板

過去ログ

No816 リストのソート

[戻る] [ホームページ]
No.10329

リスト構造
投稿者---トト(2003/11/06 17:40:54)


学校の課題なんですが何とか終ったけど最後の
p_add->nextp=p_top;
p_top=p_add;
のところが実は違うらしいのです。
2行じゃ終らないとかって聞いたのですが自分ではこれでいいと思うので
どう違うのかがわかりません。
なにが違うのか教えて下さい。



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

#define MAX 128

typedef struct pl{
    struct pl *nextp;
    int number;
    char *name;
} PlayerList;

PlayerList *readNumberandName();
void printList(PlayerList *);
void freeList(PlayerList *);

void printListforDebug(PlayerList *, char *);

PlayerList *addPlayertoList(PlayerList *, PlayerList *);

int main ()
{

    PlayerList dummy = {
        NULL,
        0,
        "ダミー"
    };
   
    PlayerList *p_listtop = &dummy, *p_new;
   
    while ((p_new = readNumberandName()) != NULL ) {
      
        p_listtop = addPlayertoList(p_listtop, p_new);
       
    }

    printList(p_listtop);
    
    freeList(p_listtop);
    p_listtop = NULL;
    return 0;
}


PlayerList *readNumberandName()
{
    char buf[MAX];
    int len;
    PlayerList *p_pl;

    p_pl = (PlayerList *)malloc(sizeof(PlayerList));
    if (p_pl == NULL) {
        printf("メモリの確保に失敗\n");
        exit(-1);
    }
    p_pl->nextp = NULL;

    printf("選手の背番号: ");
 
    if (fgets(buf, MAX, stdin) == NULL) {
        free(p_pl);
        p_pl = NULL;
        return NULL;
    }
    p_pl->number = atoi(buf);

    printf("選手の名前: ");
    if (fgets(buf, MAX, stdin) == NULL) {
        free(p_pl);
        p_pl = NULL;
        return NULL;
    }

    len = strlen(buf);
    if (len > 0){
        if (buf[len-1] == '\n'){
            buf[len-1] = '\0';
            len--;
        }
    }

    p_pl->name = (char *)malloc(len+1);  
    if (p_pl->name == NULL) {
        printf("メモリの確保に失敗\n");
        free(p_pl);
        p_pl = NULL;
        exit(-1);
    }
    strcpy(p_pl->name, buf);

    return p_pl;
}

void freeList(PlayerList *p_top)
{
    PlayerList *p_pl, *p_next;

    for (p_pl = p_top; p_pl->nextp != NULL; p_pl = p_next) {
        p_next = p_pl->nextp;
        free(p_pl->name);
        free(p_pl);
    }
}


void printList(PlayerList *p_pl)
{
    printf("\n\n");

    if (p_pl != NULL ) {
        for (; p_pl->nextp != NULL; p_pl = p_pl->nextp)
            printf("背番号%2d を持つ選手は %s です\n",
                   p_pl->number, p_pl->name);
    }

    printf("\n");
}

void printListforDebug(PlayerList *p_pl, char *message)
{
    printf("DEBUG %s:\n", message);
   
    for (; p_pl != NULL; p_pl = p_pl->nextp)
        printf("背番号%2d を持つ選手は %s です\n", p_pl->number, p_pl->name);

    printf("DEBUG %s:\n", message);
}

PlayerList *addPlayertoList(PlayerList *p_top, PlayerList *p_add)
{
    PlayerList *p_pl;

    p_add->nextp=p_top;
    p_top=p_add;
}





標準入力から背番号と選手名を次々に読み込み、背番号順になるように
リストに追加し、最後に背番号と選手名を昇順に出力する。


プログラムの仕様:

1.次のような自己参照、及び背番号と選手名を持つ構造体 PlayerList を
定義する。

typedef struct pl{
struct pl *nextp;
int number;
char *name;
} PlayerList;

2. リストの先頭にダミーを置く

3. 標準入力から選手の背番号の入力を次々に求め、構造体に格納する。
そしてこの構造体をリストに背番号順に挿入していく。

4. EOF(Ctrl-D)が入力されるとリストの内容を表示して終わる。

No.10336

Re:リスト構造
投稿者---たか(2003/11/06 19:15:00)


>学校の課題なんですが何とか終ったけど最後の
>p_add-&gt;nextp=p_top;
> p_top=p_add;
>のところが実は違うらしいのです。
>2行じゃ終らないとかって聞いたのですが自分ではこれでいいと思うので
>どう違うのかがわかりません。
>なにが違うのか教えて下さい。

番号順に入れていくという条件が満たされていません。
そしてダミーは入力とともに後ろ側に追いやられていきますが、これは
そのままにしておきました。

PlayerList *addPlayertoList(PlayerList *p_top, PlayerList *p_add)
{
  PlayerList *p_pl, *p_prev;

  p_prev = NULL;
  for (p_pl = p_top; p_pl->nextp != NULL; p_pl = p_pl->nextp) {
    if (p_pl->number >= p_add->number) break;
    p_prev = p_pl;
  }
  
  if (p_prev != NULL)
    p_prev->nextp = p_add;
    
  p_add->nextp = p_pl;
  
  return (p_prev == NULL) ? p_add : p_top;
}



No.10338

Re:リスト構造
投稿者---たか(2003/11/06 19:37:22)


おっとっと忘れていました。
このようなソート法を「単純挿入法」と言います。
今回のようなリスト構造があらかじめ背番号順にソートされている
ような場合は非常に効率が良い方法です。

No.10353

リスト構造
投稿者---トト(2003/11/07 13:34:03)


これで解決しました。たかさんありがとう

No.10354

リスト構造
投稿者---トト(2003/11/07 15:21:19)


もう一つ質問があるのですが
同じ背番号があるとその後に新しい選手を挿入することになるけど同じ背番号があるときにはその前に挿入するようにするには、どこをどう変更すればいいのですか?。
あと関数を呼び出すごとに新しく変数が用意されると思って、真ん中のあたりの
p_pl->name = (char *)malloc(len+1); の所を malloc を使わずに
p_pl->name = buf;
とするとセグメーテーション違反(Segmantation fault)が出て動作しなかったのですがなぜ動かないのですか

No.10355

Re:リスト構造
投稿者---たか(2003/11/07 17:01:25)


>同じ背番号があるとその後に新しい選手を挿入することになるけど同じ背番号があるときにはその前に挿入するようにするには、どこをどう変更すればいいのですか?。

現在の状態で前に挿入すると思います。後ろに挿入するには

if (p_pl->number > p_add->number) break;

とすればよいです。

>あと関数を呼び出すごとに新しく変数が用意されると思って、真ん中のあたりの
> p_pl->name = (char *)malloc(len+1); の所を malloc を使わずに
> p_pl->name = buf;
>とするとセグメーテーション違反(Segmantation fault)が出て動作しなかったのですがなぜ動かないのですか

それをすると2つの不都合が起きます。まず、入力された名前は全て同じ
領域buf[]を共有する事になり、buf[]はreadNumberandName()のローカル
変数ですからこの関数から抜けたらbuf[]は消滅しますからnameはどこを
指しているか不定になります。そのため後からnameを参照しようとすると
実行結果は未定義となります。コアを吐いたのはそのせいでしょう。

strcpy(p_pl->name, buf);

も危なっかしいですね。自分に自分を上書きしているだけだから大丈夫
だとは思いますが。

次に、freelist()中の

free(p_pl->name);

で、p_pl->nameはNULLではありませんからmalloc()で確保したのではない
しかも既に消滅しているbuf[]の領域を強行的にfree()しようとしますか
ら、実行結果は未定義です。

No.10356

お願いします。
投稿者---たく(2003/11/07 18:34:17)


このプログラムでたかさんがと
(p_prev == NULL)? p_add : p_top;
書いてあるのですが、それをifにかえれるのですか?

No.10357

Re:お願いします。
投稿者---たか(2003/11/07 18:53:32)


>このプログラムでたかさんがと
>(p_prev == NULL)? p_add : p_top;
>書いてあるのですが、それをifにかえれるのですか?

if (p_prev == NULL) return p_add;
else return p_top;


ですね。

No.10360

Re:お願いします。
投稿者---たく(2003/11/08 02:04:07)


そうなんですか。ありがとうございます。


No.10367

またまたお願いします。
投稿者---たく(2003/11/08 12:40:40)


同じ背番号があるとその後に新しい選手を挿入することになる。では、同じ背番号があるときにはその前に挿入するようにするには、どこをどう変更すればよいのですか?

No.10369

Re:またまたお願いします。
投稿者---たか(2003/11/08 14:49:29)


>同じ背番号があるとその後に新しい選手を挿入することになる。では、同じ背番号があるときにはその前に挿入するようにするには、どこをどう変更すればよいのですか?

ですからNo.10336の例がそうなります。>演算子と>=演算子の違いがそう
させるのです。