質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.90%

C言語でのチェイニング法によるハッシュの昇順にするには。

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 220

yukihirotahu

score 6

C言語のチェイニング法でハッシュの問題なのですが、このコードを昇順に書き出すようにするにはどうすればよいのでしょうか?
ここのinsert部分を変えて昇順になるようにしたいのですがどうすればよいでしょうか?
いくつかやってみたのですが、できませんでした。どなたかお助けください、、

#include <stdio.h>
#include <stdlib.h>
#define    m    12    /* 配列サイズ*/


/*   リストの基本操作 */

struct element {
    int data;
    struct element *next;
};

struct element *newl()     /* メモリー上にセルの領域を確保 */
{
  return((struct element *) malloc(sizeof(struct element)));
}

struct element *create()   /* 空リストを生成 */
{
    struct element *p;

    p = newl();        /* create(1) */
    p->next = NULL;        /* create(2) */
    return(p);            /* create(3) */
}

void insert(struct element *list, int k, int x) /* リストのk番目にxを挿入 */
{
    struct element *p;

    if (k > 1)                 /* insert(1) */
        insert(list->next, k-1, x);    /* insert(2) */
    else {                    /* insert(3) */
        p = newl();            /* insert(4) */
        p->data = x;            /* insert(5) */
        p->next = list->next;        /* insert(6) */
        list->next = p;            /* insert(7) */
    }
}

int member(struct element *list, int x)  /* リスト中にxがあるかを判定 */
{
    if(list->next == NULL)        /* member(1) */
        return 0;        /* member(2) */
    if(list->next->data == x)    /* member(3) */
        return 1;        /* member(4) */
    else                /* member(5) */
        member(list->next, x);    /* member(6) */
}

void deleteall(struct element *list, int x)  /* リストから整数xをすべて削除する*/
{
    if (list->next == NULL)            /* deleteall(1) */
        return;                /* deleteall(2) */
        if (list->next->data == x){        /* deleteall(3) */
        list->next = list->next->next;    /* deleteall(4) */
        deleteall(list, x);        /* deleteall(5) */
    }            
    else                     /* deleteall(6) */
        deleteall(list->next, x);    /* deleteall(7) */
}

void printlist(struct element *list)    /* リスト内のデータををすべて印刷する*/
{
    if(list->next != NULL){                /* printlist(1) */
        printf(" %d", list->next->data);    /* printlist(2) */
            printlist(list->next);            /* printlist(3) */
    }
}



/*  ハッシュ表の基本操作 */

int hash(int x)       /*  ハッシュ関数 */
{
    return(x % m);                /* hash(1) */
}

void initializehash(struct element *a[]) /*  ハッシュ表の初期化 */
{
    int i;                    /* initializehash(1) */

    for (i = 0;i <= m-1; i++)        /* initializehash(2) */
        a[i] = create();        /* initializehash(3) */
}

void inserthash(struct element *a[], int x)  /*  ハッシュ表にxを挿入 */
{
    insert(a[hash(x)],1,x);            /* inserthash(1) */
}

void deletehash(struct element *a[], int x)  /* ハッシュ表からxを削除する */
{
    int i;

    for (i = 0; i < m; i++)            /* deletehash(1) */
            deleteall(a[i], x);           /* deletehash(2) */
}

int memberhash(struct element *a[], int x) /* ハッシュ表にxがあるかを判定 */
{
    return(member(a[hash(x)], x));        /* memberhash(1) */
}

void printhash(struct element *a[])  /* ハッシュ表を印刷する */
{
    int i;
    for (i = 0; i < m; i++){        /* printhash(1) */
        printf("H[%d",i);        /* printhash(2) */
        printf("] = ");         /* printhash(3) */
        printlist(a[i]);         /* printhash(4) */
        printf("\n");            /* printhash(5) */
    }
}


int main()
{
    int x; 
    struct element *a[m];

    initializehash(a);                /* main(1) */
    printf("Next integer(0:end) = ");         /* main(2) */
    scanf("%d", &x);                      /* main(3) コンソールから整数xを読みこむ */
    while (x != 0) {                /* main(4) */
        inserthash(a, x);            /* main(5) ハッシュ表に挿入する */
        printf("Next integer(0:end) = ");    /* main(6) */
        scanf(" %d", &x);            /* main(7) */
    }
    printhash(a);                    /* main(8) */

  printf("Member integer(0:end) = ");     /* main(9) */
  scanf("%d", &x);                      /* main(10) コンソールから整数xを読みこむ */
  while (x != 0) {                /* main(11) */
      printf("%d", memberhash(a, x));      /* main(12) 1:ハッシュ表にxがある 0:ない */
      printf("\nMember integer(0:end) = ");    /* main(13) */
      scanf(" %d", &x);            /* main(14) */
  }
  printhash(a);                /* main(15) */
  printf("Delete integer(0:end) = ");     /* main(16) */
  scanf("%d", &x);                      /* main(17) コンソールから整数xを読みこむ */
  while (x != 0) {                /* main(18) */
      deletehash(a, x);            /* main(19) ハッシュ表からxを削除する */
           printhash(a);                /* main(20) */
      printf("Delete integer(0:end) = ");    /* main(21) */
      scanf(" %d", &x);            /* main(22) */
  }
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

0

ハッシュ部は省略。

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

/*   リストの基本操作 */

struct element {
    int data;
    struct element* next;
};

/* メモリー上にセルの領域を確保 */
struct element* create_element(int value, struct element* nxt) {
    struct element* p = (struct element*)malloc(sizeof(struct element));
    if ( p != NULL ) {
      p->data = value;
      p->next = nxt;
    }
    return p;
}

/* 昇順となる位置に elementを挿入し、
   新たな先頭elementを返す */
struct element* insert(struct element* list, int x) {
    struct element* prev = NULL;
    struct element* curr = list;

    // 挿入位置を探す
    while ( curr != NULL && curr->data < x ) {
        prev = curr;
        curr = curr->next;
    }
    // elementを挿入する
    if ( prev == NULL ) {
      return create_element(x, list);
    } else {
      prev->next = create_element(x, curr);
      return list;
    }
}

/* リスト内のデータををすべて印刷する*/
void printlist(struct element* list) {
    while ( list != NULL ) {
        printf(" %d", list->data);
        list = list->next;
    }
    printf("\n");
}

int main() {
  struct element* list = NULL;
  int values[] = { 1, 3, 5, 7, 9, 8, 6, 4, 2, 0, 0, 1, 2, 3, 4 };
  int i;
  for ( i = 0; i < 15; ++i ) {
    list = insert(list, values[i]);
    printf("%d : ", values[i]);
    printlist(list);
  }
  return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.90%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る