Stack & Queue & List
3
スタック
• スタックとは、データを棚の下から積んでいき、
必要に応じて上から順番に取り出す方法
(Last In First Out) …1次元配列を使用する
• (例)上図で考える。
(1)書類1,書類2、書類3という順序で棚に
入れる。(一番上から順に書類3, 書類2, 書類1)
(2)取り出すときは一番上から順に取り出す。
(書類3, 書類2, 書類1)の順になる
push / pop
•
•
•
•
push…スタックにデータを積む関数
pop…..スタックからデータを取り出す関数
stack[] スタック配列
sp……..スタックポインタ(一番上のものはどれ
か)
• stack[sp++] = data; // push
• sp--; // pop
/* スタックの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; /* スタックが一杯*/
}
/* スタックからデータを取り出す*/
/* 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");
else
printf("stack data --> %d\n", n);
}
}
}
ハノイの塔(シミュレーション)
/* ハノイの塔(シミュレーション) */
#include <stdio.h>
#include <conio.h>
void hanoi(int,int,int,int);
void move(int,int,int);
int pie[20][3];
int sp[3],N;
/* 20:円盤の最大枚数、:棒の数*/
/* スタック・ポインタ*/
void main(void) {
int i;
printf("円盤の枚数? ");
scanf("%d", &N);
for (i=0;i<N;i++)
pie[i][0] = N-i;
sp[0]=N; sp[1]=0; sp[2]=0;
/* 棒a に円盤を積む*/
/* スタック・ポインタの初期値設定*/
hanoi(N, 0, 1, 2);
}
void hanoi(int n,int a,int b,int c) {
if (n>0) {
hanoi(n-1, a, c, b);
move(n,a,b);
hanoi(n-1, c, b, a);
}
}
/* a からc へb を使って移動*/
/* 一番下の盤をa からb へ移動*/
/* c からb へa を使って移動*/
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(); /* エコー・なし*/
}
キュー
• キューとは,First Int First Out(最初に入れたもの
を最初に取り出す)
• 順番待ちみたいなもの。
• Queue[] …キュー
• Head; …….待ち行列の先頭
• Tail; ……..待ち行列の終端
• リング状の配列にする(無駄がないように)
• head と tail の間に1つスペースを空けておく
(head=tail となったとき、空の状態と区別でき
ない。
/* キュー*/
#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);
}
}
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 0;
}
else
return -1;
/* キューが空*/
}
キューデータの表示
• head から tail をエコーする
/* キュー*/
#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);
break;
case 'l':
case 'L': // 追加
disp();
break;
}
}
}
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 0;
}
else
return -1;
/* キューが空*/
}
void disp(void) {
/* キューの内容を表示する*/
int i;
i=head;
while (i!=tail) {
printf("%d\n", queue[i]);
i++;
i=i%MaxSize;
}
}
リストの作成
入力とは逆順なリスト
• キーボードから入力したデータとは逆順につな
がったリストを作成
• 1番目に入力したデータを終端にする。
• 最後に入力したデータは最初(headで指す)
入力順のリストの作成
• old …1つ前の領域を表すポインタ
• old->pointer=p; で、pをリストの後につなげ
old=p; でp位置を新たなold位置とする。
データ入力が終わったらポインタにNULLをおく
/* リストデータの作成(入力順)*/
#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));
}
ダミー・ノード
• ダミー・ノードを先頭にいれたリストを作る
• さっきのやつは先頭ノードは前処理でリストに
つなげておかなければならなかった.
• 今回はダミー・ノードを先頭として、2番目以降
のノードを実際のデータとするリストを考える。
/* リストデータの作成(ダミー・ノード)*/
#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));
}
ダウンロード

Cゼミ2回目