Stack & Queue & List 3.

Presentation on theme: "Stack & Queue & List 3."— Presentation transcript:

1 Stack & Queue & List 3

2 スタック スタックとは、データを棚の下から積んでいき、 必要に応じて上から順番に取り出す方法 (Last In First Out) …1次元配列を使用する （例）上図で考える。 （１）書類１,書類２、書類３という順序で棚に 入れる。（一番上から順に書類3, 書類2, 書類1) （２）取り出すときは一番上から順に取り出す。 (書類3, 書類2, 書類1)の順になる

3 push / pop push…スタックにデータを積む関数 pop…..スタックからデータを取り出す関数 stack[] スタック配列
sp……..スタックポインタ(一番上のものはどれ か) stack[sp++] = data; // push sp--; // pop

4 /* スタックのpush/pop */ #include <stdio.h> #define MaxSize 100 /* スタック・サイズ*/ int stack[MaxSize]; /* スタック*/ int sp=0; /* スタックポインタ*/ /* スタックに追加*/ /* return 0; 無事に追加できた*/ /* return -1; スタックがあふれた(これ以上はいらない) */ int push(int n) { if (sp < MaxSize) { stack[sp] = n; sp++; return 0; } else return -1; /* スタックが一杯*/

5 /* スタックからデータを取り出す*/ /* return 0; 無事に取り出せた*/ /* return 1; スタックが空なので取り出せない(sp <= 0) */ int pop(int *n) { if (sp > 0) { sp--; *n = stack[sp]; return 0; } else return -1; /* スタックが空*/ int main() { int c, n; while (printf("]"), (c=getchar())!=EOF) { rewind(stdin); if (c=='i' || c == 'I') { // push printf("data--> "); scanf("%d", &n); rewind(stdin); if (push(n)==-1) { printf("スタックが一杯\n"); if (c=='o' || c == 'O') { // pop if (pop(&n)==-1) printf("スタックは空\n"); printf("stack data --> %d\n", n);

6 ハノイの塔（シミュレーション）

7 /* ハノイの塔(シミュレーション) */ #include <stdio.h> #include <conio.h> void hanoi(int,int,int,int); void move(int,int,int); int pie[20][3]; /* 20:円盤の最大枚数、:棒の数*/ int sp[3],N; /* スタック・ポインタ*/ void main(void) { int i; printf("円盤の枚数? "); scanf("%d", &N); for (i=0;i<N;i++) pie[i][0] = N-i; /* 棒a に円盤を積む*/ sp[0]=N; sp[1]=0; sp[2]=0; /* スタック・ポインタの初期値設定*/ hanoi(N, 0, 1, 2); } void hanoi(int n,int a,int b,int c) { if (n>0) { hanoi(n-1, a, c, b); /* a からc へb を使って移動*/ move(n,a,b); /* 一番下の盤をa からb へ移動*/ hanoi(n-1, c, b, a); /* c からb へa を使って移動*/

8 void move(int n,int s,int d) { /* 円盤の移動シミュレーション*/
int i,j; pie[sp[d]][d] = pie[sp[s]-1][s]; /* s -> d へ円盤移動*/ sp[d]++; /* スタック・ポインタの更新*/ sp[s]--; /* 数字に対応. 0 = 'a' 1 = 'a'+1='b' 2='a'+2 = 'c' */ printf("\n%d 番の円盤を　%c-->%c へ移す\n\n", n, 'a'+s, 'a'+d); for (i=N-1; i>=0;i--) { for (j=0;j<3;j++) { if (i<sp[j]) printf("%8d", pie[i][j]); else printf("　　"); } printf("\n"); printf("\n　　　a　　　　b　　　　c"); getch(); /* エコー・なし*/

9 キュー キューとは,First Int First Out(最初に入れたもの を最初に取り出す) 順番待ちみたいなもの。
Queue[] …キュー Head; …….待ち行列の先頭 Tail; ……..待ち行列の終端 リング状の配列にする（無駄がないように） head と tail の間に1つスペースを空けておく （head=tail となったとき、空の状態と区別でき ない。

10 /* キュー*/ #include <stdio.h> #define MaxSize 100 /* キュー・サイズ*/ int queue[MaxSize]; int head=0; /* 先頭データへのポインタ*/ int tail=0; /* 終端データへのポインタ*/ int queuein(int); int queueout(int *); void main(void) { int c, n; while (printf("]"), (c=getchar())!=EOF) { rewind(stdin); if (c=='i' || c == 'I') { printf("data--> "); scanf("%d", &n); rewind(stdin); if (queuein(n)==-1) { printf("キューが一杯\n"); } if (c=='o' || c == 'O') { if (queueout(&n)==-1) printf("キューは空\n"); else printf("queue data --> %d\n", n);

11 int queuein(int n) { /* キューにデータを入れる*/
if ((tail+1)%MaxSize != head) {　 /*tail が head の直前にない*/ queue[tail] = n; tail++; tail=tail%ModSize; return 0; } else return -1; /* キューが一杯*/ int queueout(int *n) { /* キューからデータを取り出す*/ if (tail!=head) { *n=queue[head]; head++; head=head%ModSize; return -1; /* キューが空*/

12 キューデータの表示 head から tail をエコーする

13 /* キュー*/ #include <stdio.h> #define MaxSize 100 /* キュー・サイズ*/ int queue[MaxSize]; int head=0; /* 先頭データへのポインタ*/ int tail=0; /* 終端データへのポインタ*/ int queuein(int); int queueout(int *); void disp(void); // 追加 void main(void) { int c, n; while (printf("]"), (c=getchar())!=EOF) { rewind(stdin); switch (c) { case 'i': case 'I': printf("data--> "); scanf("%d", &n); rewind(stdin); if (queuein(n)==-1) printf("キューが一杯\n"); break; case 'o': case 'O': if (queueout(&n)==-1) printf("キューは空\n"); else printf("queue data--> %d\n", n); case 'l': case 'L': // 追加 disp(); }

14 int queuein(int n) { /* キューにデータを入れる*/
if ((tail+1)%MaxSize != head) { queue[tail] = n; tail++; tail=tail%maxSize; return 0; } else return -1; /* キューが一杯*/ int queueout(int *n) { /* キューからデータを取り出す*/ if (tail!=head) { *n=queue[head]; head++; head=head%maxSize; return -1; /* キューが空*/ void disp(void) { /* キューの内容を表示する*/ int i; i=head; while (i!=tail) { printf("%d\n", queue[i]); i++; i=i%MaxSize;

15 リストの作成

16 入力とは逆順なリスト キーボードから入力したデータとは逆順につな がったリストを作成 １番目に入力したデータを終端にする。
最後に入力したデータは最初(headで指す)

17 入力順のリストの作成 old …1つ前の領域を表すポインタ old->pointer=p; で、pをリストの後につなげ
　old=p; でp位置を新たなold位置とする。 データ入力が終わったらポインタにNULLをおく

18 /* リストデータの作成（入力順）*/ #include <stdio.h> #include <malloc.h> struct tfield { char name[20]; char tel[20]; struct tfield *pointer; }; struct tfield *talloc(void); void main(void) { struct tfield *head, *p, *old; head = talloc(); scanf("%s %s", head->name, head->tel); old=head; while (p=talloc(), scanf("%s %s", p->name, p->tel)!=EOF) { old->pointer = p; old = p; } old->pointer = NULL; p=head; while (p!=NULL) { printf("%15s%15s\n", p->name, p->tel); p=p->pointer; struct tfield *talloc(void) { return (struct tfield *)malloc(sizeof(struct tfield));

19 ダミー・ノード ダミー・ノードを先頭にいれたリストを作る さっきのやつは先頭ノードは前処理でリストに つなげておかなければならなかった.
今回はダミー・ノードを先頭として、2番目以降 のノードを実際のデータとするリストを考える。

20 /* リストデータの作成（ダミー・ノード）*/
#include <stdio.h> #include <malloc.h> struct tfield { char name[20]; char tel[20]; struct tfield *pointer; }; struct tfield *talloc(void); void main(void) { struct tfield *head, *p, *old; /* ダミー・ノード*/ head = talloc(); old=head; while (p=talloc(), scanf("%s %s", p->name, p->tel)!=EOF) { old->pointer = p; old = p; } old->pointer = NULL; p=head->pointer; // ダミー・ノードを飛ばす while (p!=NULL) { printf("%15s%15s\n", p->name, p->tel); p=p->pointer; struct tfield *talloc(void) { return (struct tfield *)malloc(sizeof(struct tfield));