ヒープの探索

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
MEA
記事: 7
登録日時: 2週間前

ヒープの探索

#1

投稿記事 by MEA » 1週間前

ヒープを、2分木における後行順で探索するプログラムを作成する課題が出たのですが、下のコードのpostorderの所をどのようにしたら本来配列であるヒープを2分木のように探索できるのでしょうか?

コード:

#include<stdio.h>
#define hmax 100

struct heap {
    int box[hmax+1];
    int size;
};


void swap(int *u,int *v)
{
    int temp;

    temp = *u;
    *u = *v;
    *v = temp;
}

void initialize(struct heap *h)
{
    h->size = 0;
}

void insert(struct heap *h, int item)
{
    int i;

    i = ++h->size;
    h->box[i] = item;
    while(i > 1 && h->box[i]  >  h->box[i/2]){
        swap(&h->box[i], &h->box[i/2]);
        i /= 2;
    }
}

int postorder(struct heap *h,int k)
{
  
}

int main()
{
  int i;
  struct heap h;

  initialize(&h);
  insert(&h,3);
  insert(&h,8);
  insert(&h,5);
  insert(&h,9);
  insert(&h,12);
  insert(&h,18);
  insert(&h,7);
  insert(&h,20);
  insert(&h,13);
  insert(&h,15);
  printf("heap.box[]:");
  for(i=1;i<=h.size;i++){
    printf("%d",h.box[i]);
  }
  printf("\n");
  postorder(&h,1);

  return 0;
}

アバター
みけCAT
記事: 6273
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: ヒープの探索

#2

投稿記事 by みけCAT » 1週間前

ヒープは木構造なので「本来配列であるヒープ」というのは意味がよくわかりませんが、
postorderの所を「insert関数において子や親への辺をどう表現しているかを考え、適切に実装してコンパイルする」
と探索できるようになると思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“C言語何でも質問掲示板” へ戻る