20260512_3

20260427_3

---

キューを実装する

データを待ち行列として保持する
First In First Out

• 追加は最後から(tail) enqueue
• 取得は先頭から(head) dequeue

スタックの場合

• 追加は最後から push
• 取得も最後から pop
• データの出し入れを行うところがtop

#define SIZE 5
typedef char elemtype;
 
struct queue{
	int head,tail;
	elemtype elem[SIZE];
}
/*headは先頭、tailは次にデータを入れる場所(空の場所)とする*/

キューをある程度消費すると先頭に空白ができてしまう
→ring bufferの利用

headは先頭、tailは次にデータを入れる場所(空の場所)とする

ring bufferの利用時に初期化をhead=0;tail=0;でよくなる

enqueue

1. 書き込む
2. tail++で次に書き込む場所を探す
3. その次にまだ書き込めるのかをチェック

(書き込めることを保証した設計)

void enqueue(struct queue *q,elemtype val){
	q -> elem[q -> tail]=val;
	q -> rail++;
	if (q ->tail >= SIZE){
		q -> tail = 0;
	}
	if(q -> tail == q -> head){
		printf("queue overflow\n");
		exit(1);
	}
}

dequeue

1. データがあるかどうか確認
2. dequeue
3. head++

elemtype dequeue(struct queue *q){
	elemtype val;
	if(q -> head == q -> tail){
		printf("queue underflow\n");
		exit(1);
	}elese{
		val = q -> elem[q -> head];
		q -> head++;
		if(q -> head >= SIZE){
			q -> head = 0;
		}
	}
	return val;
}

参照渡しのポインタで渡された配列のサイズを確実に知る方法がないので、要素数も引数にした方がいいことも(かるいはmalloc)

再帰

関数とは

入力データとして引数をとり、出力データとして戻り値を返す
$y=f(x)$に似ているが、尾根字入力で異なる出力になることもある

関数の中のブロックで宣言される変数はローカル変数
有効範囲=スコープはその関数内で、寿命は関数呼び出しからreturnするまで

等差数列の和は再帰になる

$$\sum _{i=1}^n{a}_i=(a_1+a_n)\times \frac{1}{2}$$

int sum(int a, int n, int d){
	int an=a+d*(n-1);
	return(a+an)*1/2
}

int sum(int a, int b, int d){
	int i, an = a, s = a;
	for(i=2;i<=n;i++){
		an +=d;
		s += an
	}
	return s;
}

$$\sum _{i=1}^n=\{\begin{array}{ll}{a}_1& (n=1)\\ a_n+{\sum }_{i=1}^{n-1}{a}_i& (n\ge 2)\end{array}$$

int sum(int a, int n, int d){
	if(n==1){
		return a;
	}else{
		return(a+d*(n-1))+sum(a, n-1,d);
	}
}

再帰

定義の中で自分自身を呼び出す関数が再帰関数

• 再帰的定義
• 再帰呼び出し

再帰呼び出しの時には同じ関数が別の領域に呼び出される

再帰の使用条件

1. 終端条件がある
2. 再帰を使うことで問題をより小さくできる

計算量

実行時間が入力サイズに対して比例する場合や二乗して増加する場合もある

計算量の比較で異なるアルゴリズムの性能比較が可能に$O(n)$とか$O(1)$とか$O(n^2)$とか$O(\log n)$とか$O(n\log n)$とか