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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

4845閲覧

リスト構造を用いたスタックの実現について

masuter0413

総合スコア50

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/10/30 14:35

現在、リスト構造を用いたスタックの実現を目指しています。以下のようなスタックと同じ動作を実現したいです。スタックとリストのきほんてきな部分は完成したんですがどのようにしてリストでスタックを実現すればいいでしょうか。まずリストのコードで自分なりの解釈をコメントで書いてるんですがおかしいところがあれば指摘していただきたいです。
リストに関する先生の説明は次のようです。
/////////////////////////////////////////////////////////////////////////////////////////////////
リストでは後戻りは出来ないので、先頭のオブジェクトへのポインタは 必ず覚えていなければならない。関数 addList() はそうした リストの先頭オブジェクトへのアドレスを引数に取る。関数内部では、 まず、新しいオブジェクトを malloc() で割り当て、 それの後ろにはもうデータがないので最初から next に NULL を代入しておく。 次に、先頭のオブジェクトへのポインタが NULL でないならば、リストにいくらかの オブジェクトが連なっているのであるから,先頭から順に次のオブジェクトへのアドレスを取り出し、最後のオブジェクト になるまで移動し、先に確保したオブジェクトをこのリストの最後の オブジェクトの後ろにぶら下げるために、そのアドレス(new)を 最後のオブジェクトの next に入れている。 (図 4.1.1)。

c

1//リスト 2 3#include<stdio.h> 4#include<stdlib.h> 5 6struct LIST { 7 struct LIST*next; 8 int body; 9}; 10struct LIST * addList(struct LIST ** pstart) { 11 struct LIST *p, *new; 12 p = *pstart;//ヘッダセルへのアドレス 13 if ((new = (struct LIST *) malloc(sizeof(struct LIST))) == NULL) { 14 return NULL; /* メモリ確保失敗 */ 15 } 16 //newには構造体の先頭アドレスが代入される 17 new->next = NULL;//NULLで初期化 18 19 if (p != NULL) { /* リストに要素が存在するとき */ 20 while (p->next != NULL) { 21 p = p->next; /* リストの末尾を探す */ 22 } 23 p->next = new; /* リストの末尾につなげる */ 24 //(mallocで確保した構造体の先頭アドレスを渡す) 25 } 26 else { 27 *pstart = new; /* 最初の要素の場所を *pstart に */ 28 //リストに要素が存在しないとき新たに作成した構造体をヘッダセルにする 29 } 30 return new; //ヘッダセルのアドレスを返す 31} 32struct LIST * delList(struct LIST ** pstart, struct LIST * target) { 33 //psstart:リストの先頭アドレス target:削除対象のセルへのポインタ 34 struct LIST * p = *pstart;//pにリストの先頭アドレス代入 35 struct LIST * new; 36 if (p == target) { /* 先頭の要素を削除するとき */ 37 *pstart = p = target->next; /* 2番目の要素が先頭になる */ 38 } 39 else { 40 while (p->next != target) { /* 削除対象のひとつ手前まで移動 */ 41 p = p->next; 42 } 43 p->next = target->next; /* target を飛ばした連鎖を作る */ 44 } 45 free(target); 46 return p; 47} 48struct LIST * midList(struct LIST *before, struct LIST *new) { 49 //beforeはセルを挿入したい場所の前に位置するセル 50 //newは新たに挿入したいセル 51 struct LIST *p = before;//pにbeforeのアドレス代入 52 new->next = before->next;//挿入するセルの次のセルをbeforeの次のセルにつなげる 53 before->next = new;//挿入するセルの前にbeforeをつなげる 54 return new; 55} 56 57int main() { 58 struct LIST*start;//リストの先頭アドレスを覚える 59 start = NULL; //ヘッダセルは空で初期化 60 addList(&start); 61 return 0; 62}

c

1//スタック 2#include<stdio.h> 3#include<string.h> 4#define SIZE 1024 5 6struct Stack { 7 int data[SIZE]; 8 int now; 9}; 10int main() { 11 //プロトタイプ宣言 12 int push(struct Stack*, int); 13 int pop(struct Stack *, int*); 14 int initStack(struct Stack *); 15 void printStack(struct Stack *); 16 int i; 17 struct Stack stack; 18 struct Stack *p; 19 p = &stack; 20 initStack(p);//構造体初期化 21 for (i = 1; i <= 5; i++) { 22 push(p, i); 23 printStack(p); 24 } 25 for (i = 5; i > 0; i--) { 26 pop(p, &i); 27 printStack(p); 28 } 29 return 0; 30} 31int push(struct Stack *stack, int new) { 32 if (stack->now < SIZE) { 33 stack->data[stack->now] = new; 34 stack->now++; 35 return 1; 36 } 37 else { 38 return 0; 39 } 40} 41int pop(struct Stack *stack, int *get) { 42 if (stack->now > 0) { 43 stack->now--; //5>4>3>2>1 44 *get = stack->data[stack->now];//変数iのアドレスにdata[stack=>now]のデータを格納 45 return 1; 46 } 47 else { 48 return 0; 49 } 50} 51int initStack(struct Stack *stack) { 52 stack->now = 0; 53 if (memset(stack->data, 0, sizeof(stack->data)) != NULL) { 54 return 1; 55 } 56 else { 57 return 0; 58 } 59} 60void printStack(struct Stack *stack) { 61 int i; 62 printf("Stack [ "); 63 for (i = 0; i < stack->now; i++) { 64 printf(" %d", stack->data[i]); 65 } 66 printf("]\n"); 67}

スタック実行例

c

1Stack [ 1] 2Stack [ 1 2] 3Stack [ 1 2 3] 4Stack [ 1 2 3 4] 5Stack [ 1 2 3 4 5] 6Stack [ 1 2 3 4] 7Stack [ 1 2 3] 8Stack [ 1 2] 9Stack [ 1] 10Stack [ ]

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

たぶん、
addList
delList
で実現できると思います。

投稿2018/11/01 11:11

ai_2013_dev

総合スコア338

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

リストって双方向リストじゃなくて単方向リストなのね。

stackの実現には通常

  • 末尾への追加
  • 末尾の削除
  • 末尾の取得

が必要です。が、単方向リストだと、任意の要素へのアクセスにはO(n)のコストが掛かってしまいます。言い換えるとstack操作をなにかしようとするたびに要素数Nに比例するコストが掛かるということです。

なので発想を切り替えて

  • 先頭要素の前に追加(stackに積む操作)
  • 先頭要素の削除(stackを取る操作)
  • 先頭要素の取得(stackを取る操作)

で実現させましょう。これならO(1)です。

投稿2018/10/30 14:41

編集2018/10/30 14:44
yumetodo

総合スコア5850

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

masuter0413

2018/10/31 13:45

スタックを実現する場合addlist()とmidlist()はどのように使いわければいいでしょうか
yumetodo

2018/11/02 04:33

midlistは不要じゃないかなと
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問