c言語 ヒープを表現する配列

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
bell.pi

c言語 ヒープを表現する配列

#1

投稿記事 by bell.pi » 2ヶ月前

教科書の例題を参考にしながら作ってみたのですが、

「12行目」で記述エラーを発見しました。
「;」を付け忘れています。

というエラーがでてきます。見直しても付け忘れがないので、どこが間違っているのでしょうか?

このような問題です↓
配列Val、Lp、Rpで構成されるヒープがある。この3つの配列で表現されるヒープから幅優先探索でノードの値を取り出しヒープを表現する配列Hを作成するプログラムを作れ。
データ格納例は次のようになっている。
Val,Lp,Rp
[0] 40,4,-1
[1] -1,-1,-1
[2] 90,6,0
[3] 50,-1,-1
[4] 30,-1,-1
[5] 10,-1,-1
[6] 60,5,3

幅優先探索にてノード値を取り出すため、作業用として十分な幅のある配列Qを用意。
配列Q [1][2][3][4][5][6][7][8]・・・

配列Hには根をH[1]、Hの左の子を[ix2]、右の子を[ix2+1]に格納してヒープを表現。
配列Hには処理に十分な大きさがあり、未使用要素には(-1)が格納されています。ヒープを配列Hに格納した実行結果は
配列H 「-1 90 40 10 50 30 -1 -1 ・・・」です。


コード:

#include <stdio.h>

#define MAX 7
void junkai(void);
void soeji_hozon(void);
void saihensei(void);


	typedef struct {
	int Val,Lp,Rp;}
	
	H[MAX]={
	{40,4,-1},{-1,-1,-1},
	{90,6,0},{50,-1,-1},
	{30,-1,-1},{10,-1,-1},
	{60,5,3}};

int Root=2;
	int Q[7],Hp,Tp,I,J;
	
	int main(void){
		Q[7]=Root;
		Hp=0,Tp=0;
		while(Hp<=Tp) junkai();
		I=Root+1;
		H[I]=H[I].Val;
		saihensei();
		Root++;
		
		for(I=0;I<10;I++)
			printf("H[%d]:%d\n",I,H[I]);
			printf("Root=%d",Root);
		
		return 0;
	}

bell.pi

Re: c言語 ヒープを表現する配列

#2

投稿記事 by bell.pi » 2ヶ月前

コードが最後まで貼り付けられていませんでした!
作ったのはこちらです。

コード:

#include <stdio.h>

#define MAX 7
void junkai(void);
void soeji_hozon(void);
void saihensei(void);


	typedef struct {
	int Val,Lp,Rp;}
	
	H[MAX]={
	{40,4,-1},{-1,-1,-1},
	{90,6,0},{50,-1,-1},
	{30,-1,-1},{10,-1,-1},
	{60,5,3}};

int Root=2;
	int Q[7],Hp,Tp,I,J;
	
	int main(void){
		Q[7]=Root;
		Hp=0,Tp=0;
		while(Hp<=Tp) junkai();
		I=Root+1;
		H[I]=H[I].Val;
		saihensei();
		Root++;
		
		for(I=0;I<10;I++)
			printf("H[%d]:%d\n",I,H[I]);
			printf("Root=%d",Root);
		
		return 0;
	}
	
	void junkai(void)
	{
		I=Q[Hp];
		Hp=Hp+1;
		printf("%d",H[I].Val);
		soeji_hozon();
	}
	
	void soeji_hozon(void){
		if(H[I].Lp!=(-1)){
		Tp=Tp+1;
		Q[Tp]=H[I].Lp;
		}
		if(H[I].Rp!=(-1)){
			Tp=Tp+1;
			Q[Tp]=H[I].Rp;
		
		}
	
	}

void saihensei(void){
	int J;
	J=I/2;
	while(J>=1&&H[I]>H[J]){
		H[I]=H[J];
		I=J;
		J=I/2;
	}
}

かずま

Re: c言語 ヒープを表現する配列

#3

投稿記事 by かずま » 2ヶ月前

bell.pi さんが書きました:
2ヶ月前
「12行目」で記述エラーを発見しました。
「;」を付け忘れています。

というエラーがでてきます。見直しても付け忘れがないので、どこが間違っているのでしょうか?
gcc でも、VC++ でも、Borland C++ でもそんなエラーメッセージは出ません。
コンパイラは何ですか?

コード:

struct { int Val, Lp, Rp; } H;        // H は変数名で、その型は構造体。
struct { int Val, Lp, Rp; } H[MAX];   // H は変数名で、その型は構造体の配列
typedef struct { int Val, Lp, Rp; } H;      // H は型名で、それは構造体。
typedef struct { int Val, Lp, Rp; } H[MAX]; // H は型名で、それは構造体の配列

typedef struct { int Val, Lp, Rp; } H[MAX] = { ... };
型名を初期化しようとしています。

typedef がなければ、H は変数なので初期化できますが
typedef があるので、H は型名で初期化できません。
= がここに来てはいけない。ここには ; が来るべきだ、
とコンパイルは言っているのでしょう。

コード:

typedef を削除しても、次のような問題があります。

Q[7]=Root; は変。int Q[7]; では Q[0]~Q[6] しか使用できません。
H[I]=H[I].Val; はエラー。左辺は構造体。右辺は int。
printf("H[%d]:%d\n",I,H[I]); は変。H[I] は構造体。%d では表示できない。
while(J>=1&&H[I]>H[J]){ はエラー。H[I]と H[J]は構造体で比較できない。
問題の実行結果も変です。
配列H 「-1 90 60 40 10 50 30」のように 60 が入るのでは?

そのような実行結果になるプログラムは

コード:

#include <stdio.h>

#define MAX 7

struct {
	int Val, Lp, Rp;
} T[MAX] = {
	{ 40,  4, -1 }, // [0]
	{ -1, -1, -1 }, // [1]
	{ 90,  6,  0 }, // [2]
	{ 50, -1, -1 }, // [3]
	{ 30, -1, -1 }, // [4]
	{ 10, -1, -1 }, // [5]
	{ 60,  5,  3 }, // [6]
};
int Root = 2;
int Q[MAX], H[MAX];

int main(void)
{
	int Hp = 0, Tp = 0, i;
	Q[0] = Root;
	while (Hp <= Tp) {
		i = Q[Hp++];
		if (T[i].Lp != -1) Q[++Tp] = T[i].Lp;
		if (T[i].Rp != -1) Q[++Tp] = T[i].Rp;
	}
	H[0] = -1;
	for (i = 0; i <= Tp i++) H[i+1] = T[Q[i]].Val;
	printf("H:");
	for (i = 0; i < MAX; i++) printf(" %d", H[i]);
	putchar('\n');
	return 0;
}

bell.pi

Re: c言語 ヒープを表現する配列

#4

投稿記事 by bell.pi » 2ヶ月前

使ったのは「EasyIDEC」というのです。

bell.pi

Re: c言語 ヒープを表現する配列

#5

投稿記事 by bell.pi » 2ヶ月前

実行結果は間違いでした。
60が抜けていて、正しくは-1 90 60 40 10 50 30 -1 -1・・・でした。

やはり同じようなエラーが出てきてしまいます。

bell.pi

Re: c言語 ヒープを表現する配列

#6

投稿記事 by bell.pi » 2ヶ月前

コード:

for (i = 0; i <= Tp i++) H[i+1] = T[Q[i]].Val;
個々の部分に「;」がないだけでした。

間違っている部分のご指摘、そして分かりやすい解説ありがとうございます!

返信

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