ページ 11

連結リストによるスタックの実現

Posted: 2012年5月30日(水) 00:26
by 狼太郎
連結リストを使用してstackを実現するプログラムを組む課題が出たのですが、どのようにすればいいのか全く分かりません。

コード:

#include<stdio.h>
#include<stdlib.h>
struct node{
	int data;
	struct node *next;
};

void push(struct node *top,int data);/*push関数のプロトタイプ[A]*/
int pop(struct node *top);/*pop関数のプロトタイプ[B]*/

int main(){
	struct node *top;
	int choice,data;
	struct node top1;/*[C]*/
	top=&top1;
	top->next=NULL;
	printf("----------------------------------------\n");
	printf("Stack Program: 0.Exit   1.push    2.pop \n");
	printf("----------------------------------------\n");
	
	while(1){
		printf("\n Your Operation:");
		scanf("%d",&choice);
	if(choice==0) exit(0);
	else if(choice==1){ /*push*/
		printf("          Enter data:");
		scanf("%d",&data);
		push(top,data);
	}
	else if(choice==2){ /*pop*/
		data=pop(top);
		if(data==-1)printf("Stack is empty!!!\n");
		else printf("Deleted data is %d\n",data);
		}
	else printf("error\n");
	}
	return 0;
}
/****************************************************
*push 関数
*	引数 1:top ノードのアドレス
*	引数  2:pushするデータ
*	戻り値: なし
****************************************************/
void push(struct node *top,int data)/*D*/
{
	struct node *new;
	new=top;/*[E]*/
	new->data=data;/*[F]*/
	new->next=NULL;/*[G]*/
	top->next=new;/*[H]*/
}

/***************************************************
*pop関数
* 引数:top ノードのアドレス
* 戻り値:popされたデータ(-1の場合はempty)
*
***************************************************/
int pop(struct node *top)/*I*/
{
	struct node *p;
	int data;

	if(top->next==NULL) return -1;
	else{
		p=top;/*[j]*/
		top->next=NULL;/*[K]*/
		data=p->data;/*[L]*/
		free(p);
		return data;
	}
}
A~Lまでの所が空欄になっていた所です。
popをするときにエラーが起きてしまいます。
メモリが許す限りいくつでも数値を格納するにはどうすればいいのでしょうか?

Re: 連結リストによるスタックの実現

Posted: 2012年5月30日(水) 01:13
by Poco
[J]と[K]がおかしいです。

データ構造を見るに、top->nextがスタックの頂上ですよね?

pop()実行前に、以下のように、スタックの要素が3つあったとします。
top->element1->element2->element3

これがpop()実行後、以下のようにスタックの要素が2つにならないといけないんですよね?
top->element2->element3

これを踏まえた上で、
pop()実行前の状態でtop->nextの値は何ですか?
pop()実行後の状態でtop->nextの値は何にならなければなりませんか?

Re: 連結リストによるスタックの実現

Posted: 2012年5月30日(水) 06:24
by box
せっかくですから、現在のスタックの中身を出力する、という関数も用意した方が
いいのではないか、という気がします。
デバッグ用に使う、という意図を含めて。
課題提出用として不要なら、デバッグ後に外せばいいだけですし。

Re: 連結リストによるスタックの実現

Posted: 2012年5月30日(水) 11:07
by 狼太郎
回答ありがとうございます
ぼこさん→[J][K]以外は大丈夫でしょうか?[K]にはtop->next=p;
を入れてみましたが[J]に入るものがやはり分かりません。
boxさん→

コード:

			else if(choice==1){ /*push*/
		printf("          Enter data:");
		scanf("%d",&data);
		push(top,data);

		printf("%d%d\n",top->data,top->next->data);
	}
としてみましたがどちらにも同じ値が代入されているみたいです

Re: 連結リストによるスタックの実現

Posted: 2012年5月30日(水) 11:24
by box
私が「関数化する方がいいんじゃないですか?」と書いたのは、例えばこういうことです。

コード:

	printf("---------------------------------------------------\n");
	printf("Stack Program: 0.Exit   1.push    2.pop     3.print\n");
	printf("---------------------------------------------------\n");
のようなメニューを作っておいて、3を入力すると、その時点でのスタックの中身を全部吐き出す関数

コード:

void print(struct node *top);
を作れば、何かと便利じゃないですか?ということです。

Re: 連結リストによるスタックの実現

Posted: 2012年5月30日(水) 15:09
by YuO
とりあえず,[E] ~ [H]は何を意図してこう書いたのでしょうか。
これでは連結リストになりません。
ちなみに,[L]の次の行でfreeを使っているのはヒントだと思いますが……。
# ポインタの理解が怪しい?

[J]と[K]もおかしいですが,これについては,「topとは何か」を考えてみるとよいと思います。
# 連結リストをわかっている前提ですが