プログラマ専用SNS ミクプラ

あらかじめ、ハッシュ表に格納された整数(構造体のメンバ)を、その整数を添え字とした配列に格納することによってソートを行いたいです。また、その配列はそれぞれが連結リストになっています。
自分で考えてみたのですが、どうもうまくいきません。
SIZE:ハッシュ表の長さ

コード:

struct W {
  struct W *next;
  char *str;
  int count;
};typedef struct W w;

w *s_w[20];

 for(j=0;j<SIZE;j++){
    for(q=w[j];q!=NULL;q=q->next){
      s_w[q->count]=q;
      s_w[q->count]->next = (w*)malloc(sizeof(w));
      s_w[q->count]=s_w[q->count]->next;
    }
  }

まだよく理解できていないですが、
とりあえずwは型名なのでq=w[j]というのはおかしいでしよう。

すいません、qも構造体です。

しょしょさんが書きました:すいません、qも構造体です。

C言語でqに対してアロー演算子(->)が使用されているので、それはおかしいでしょう。
qはポインタではないですか？

しょしょさんが書きました:あらかじめ、ハッシュ表に格納された整数(構造体のメンバ)を、その整数を添え字とした配列に格納することによってソートを行いたいです。また、その配列はそれぞれが連結リストになっています。

書かれているコードの理解は難しそうだと思ったので、自分で最初から実装してみました。

► スポイラーを表示

コード:

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

typedef struct {
  int num; /* 整数(構造体のメンバ) */
} data_t;

typedef struct list_t_tag {
  data_t data;
  struct list_t_tag *next;
} list_t;

int main(void) {
  /* ハッシュ表(ハッシュ関数を使うとは言ってない) */
  data_t hassyuhyou[] = {
    {77}, {51}, {-13}, {18}, {37},
    {-39}, {77}, {81}, {-11}, {61}
  };
  int SIZE = sizeof(hassyuhyou) / sizeof(*hassyuhyou);
  list_t **list_array_buffer, **list_array;
  int min, max;
  int i, count;

  /* 整数を格納する配列を用意する */
  /* いくつ要素が必要かを調べる */
  min = 0; /* 実際は正の整数しかなくても0から確保するので、0に初期化 */
  max = 0; /* 実際は負の整数しかなくても0は確保するので、0に初期化 */
  for (i = 0; i < SIZE; i++) {
    if (hassyuhyou[i].num < min) min = hassyuhyou[i].num;
    if (hassyuhyou[i].num > max) max = hassyuhyou[i].num;
  }
  /* 実際に配列を用意する */
  /* min～maxの添字が使えるようにする */
  list_array_buffer = malloc(sizeof(list_t*) * (max - min + 1));
  if (list_array_buffer == NULL) {
    perror("malloc array");
    return 1;
  }
  /* 負の添字が使えるように下駄を履かせる(minは0以下であることに注意) */
  list_array = list_array_buffer - min;
  for (i = min; i <= max; i++) {
    list_array[i] = NULL;
  }

  /* ハッシュ表に格納された整数を配列に入れる */
  /* 逆順に処理することで、同じ順位の要素の順番を保つ安定性が簡単に得られる */
  for (i = SIZE - 1; i >= 0; i--) {
    list_t *new_node = malloc(sizeof(list_t));
    if (new_node == NULL) {
      perror("node malloc");
      return 1;
    }
    new_node->data = hassyuhyou[i];
    new_node->next = list_array[new_node->data.num];
    list_array[new_node->data.num] = new_node;
  }
  /* 配列からデータを取り出し、ソートした結果を得る */
  /* ついでに連結リストとを開放する */
  count = 0;
  for (i = min; i <= max; i++) {
    list_t *cur = list_array[i];
    while (cur != NULL) {
      list_t *next = cur->next;
      hassyuhyou[count++] = cur->data;
      free(cur);
      cur = next;
    }
  }
  /* 配列を開放する */
  /* 下駄を履かせたlist_arrayではなく、もとのlist_array_bufferを開放することに注意 */
  free(list_array_buffer);

  /* 確認のため、ソートした結果を出力する */
  for (i = 0; i < SIZE; i++) {
    printf("%d\n", hassyuhyou[i].num);
  }

  return 0;
}

しょしょさんが書きました:自分で考えてみたのですが、どうもうまくいきません。

具体的に何がどううまくいかないのですか？
うまくいく方法を教えてほしいのであれば、得たい実行結果と現状観測される実行結果を教えてください。
コンパイルエラーやリンクエラーが出て、その解決法を教えて欲しいのであれば、エラーメッセージをそのまま(ユーザー名などの個人情報は隠して)提示してください。
コンパイルしているソースコード全体ももし提示できるのであれば、提示していただけるとわかりやすくなると思います。

プログラマ専用SNS ミクプラ

バケットソートについて質問です。

バケットソートについて質問です。

Re: バケットソートについて質問です。

Re: バケットソートについてしょしょ質問です。

Re: バケットソートについてしょしょ質問です。

Re: バケットソートについて質問です。