(c言語)リングバッファのキューの無駄をなくす
状況
リングバッファのキューは先頭に戻す処理時に1つ無駄ができることを知ったので、改善策を考えた。(enqueueのみ)
リングバッファのキューとは
リングバッファのキューは、キューの限界に領域まで達したら、先頭に戻すことでデキューをタイミングよくすれば無限に入るキューが完成する。
これがリングバッファのキューである。
enqueue以外のコードに関しては以下である。
#include <stdio.h> #include <stdlib.h> #define SIZE 4 struct queue { int head, tail; char elem[SIZE]; }; char dequeue(struct queue *q) { char val; if (q->head == q->tail) { printf("queue underflow\n"); exit(1); } else { val = q->elem[q->head]; q->head++; if (q->head >= SIZE) { q->head = 0; } return val; } } int main(void) { struct queue Q; char e, moji[5]; int input, i; Q.head = 0; Q.tail = 0; printf("キューに格納されている値\n"); for (i = 0; i < 10; i++) { printf("%i:::%c\n", i, Q.elem[i]); } while (1) { // メニュー表示 printf("操作を選択:\n"); printf(" 1: 格納\n"); printf(" 2: 取得\n"); scanf("%d", &input); // 操作を入力 switch (input) { case 1: // 格納 printf("格納する文字を入力してください:"); scanf("%s", moji); enqueue(&Q, moji[0]); printf("\n"); printf("キューに格納されている値\n"); for (i = Q.head; i <= Q.tail; i++) { printf("%i::%c\n", i, Q.elem[i]); } printf("tailの値::%d\n", Q.tail); printf("headの値::%d\n", Q.head); break; case 2: //出力 e = dequeue(&Q); printf("%c\n", e); printf("キューに格納されている値\n"); for (i = Q.head; i <= Q.tail; i++) { printf("%i::%c\n", i, Q.elem[i]); } printf("tailの値::%d\n", Q.tail); printf("headの値::%d\n", Q.head); break; break; } } return 0; }
問題となる例とコード
以下が今回の問題となる部分です。
- 先頭に値を入れていない。(*1)
- または、全てが埋まった瞬間にoverflowとなってしまい、デキューの可能性を否定している。(*2)
*1
void enqueue(struct queue *q,char val){ q->tail++; if(q->tail==SIZE){//最後まで行ったら先頭に戻す q->tail=0; } if(q->tail==q->head){//先頭と最後の指す位置が同じならoverflowとする printf("queue overflow\n"); }else{ q->elem[q->tail] = val;//値の代入 } }
*2
void enqueue(struct queue *q,char val){ q->elem[q->tail] = val;//値の代入 q->tail++; if(q->tail==SIZE){//最後まで行ったら先頭に戻す q->tail=0; } if(q->tail==q->head){//先頭と最後の指す位置が同じならoverflowとする printf("queue overflow\n"); } }
解決のためのコード
上記の問題を解決するために以下のようなコードにします。
void enqueue(struct queue *q, char val) { if ((q->tail) % SIZE == (q->head) % SIZE && (q->tail) != 0) { printf("queue overflow\n"); } else { q->elem[(q->tail) % SIZE] = val; q->tail++; } return; }
処理内容
- tailをSIZEで割った値の余りとheadをSIZEで割った値の余りを比較する
- 一緒であり、tailの値が0でないoverflowとする
- 違うならtailをSIZEで割った値の余り番目に値を代入する
詳細
- リングバッファで何回も周回してもSIZEで割った際の余りは常に1周目の場所と同じところを指すため、SIZEで割った余りの値を参考にoverflow等を判定している。
- また、if文の条件式において、&&の後ろは&&の前半部分のみだけだと、一番最初にenqueueをした際にはじかれてしまうので、最初でないことを示すために書いている。
まとめ
- 今回、リングバッファのキューにおいて無駄があったため解決策を探した。
- 正直、余りを使った構造で無駄をなくす構造なのでoverflowしていないのにおかしいと思う人はぜひ活用していただきたい。
(c言語)ポインタを用いたリスト
ココでは主に挿入と削除について話します。(最後に作成したものをチェックするprintも紹介します。)
- 単方向リスト
- 双方向リスト
単方向リスト
単方向リストとは
単方向リストは下の図のようなもので、1つのリストが次の行先のみを知っているようなものです。
上の図を以下の図のように変換することで挿入(insert)及び削除(delete)を作る際にイメージしやすくなります。
実際に書いてみましょう
挿入(insert)及び削除(delete)以外の部分は以下のようになります。
struct node{ struct node *next; //nextのアドレスを入れる部分 int elem; //値を入れる部分 }; struct node* head(void){ struct node* n;//箱の生成 n=(struct node*)malloc(sizeof(struct node));//箱の拡張 n->next = NULL;//箱の行き先をnullにする return n; } void main(){ struct node* list; list=head; }
ここからがinsert及びdeleteです
void insert(struct node* p, char elem) { struct node* n; //新しく値を代入する箱を作る n = (struct node*)malloc(sizeof(struct node)); //箱の大きさを拡張する n->elem = elem; //値を代入 n->next = p->next; // nの行先をpの行き先にする p->next = n; //作った箱の行先をpにする=次にpが来る } void delete(struct node* p){ if(p->next != NULL){ p->next=p->next->next; //pの行き先を次の次にする=一つ飛ばす } }
注意点
insertでは受け取った引数のpの次に値を挿入し、deleteでは受け取った引数pの次の値を削除する形となります。
作成時のポイント
- 追加する箱を考えて、追加する箱のnext部分を先に指定する。
- その後で追加した箱の一つ後ろ(引数で渡したもの)のnextを変える。
双方向リスト
双方向リストとは
双方向リストは下の図のようなもので、1つのリストが次の行先を知っていて、また、1つのリストが前の行き先も知っているようなものです。
上の図を以下の図のように変換することで挿入(insert)及び削除(delete)を作る際にイメージしやすくなります。
実際に書いてみましょう
挿入(insert)及び削除(delete)以外の部分は以下のようになります。
struct node{ struct node *next; //nextのアドレスを入れる場所 struct node *prev; //prevのアドレスを入れる場所 int elem; //値を入れる場所 }; struct node* head(void){ struct node *n;//箱の生成 n=(struct node*)malloc(sizeof(struct node));//箱の拡張 n->next = NULL;//箱の行き先を指定 n->prev = NULL;//箱の戻り値を指定(使うことはない) return n; } void main(){ struct node* list; list=head; }
ここからがinsert及びdeleteです
void insert(struct node* p, int elem) { struct node* n; //新しく値を代入する箱を作る n = (struct node*)malloc(sizeof(struct node)); //箱の大きさを拡張する n->elem = elem; //値を代入 if (p->next == NULL) { //一個目の代入のみ n->next = p->next; // nの行き先をpの行き先の次の物にする n->prev = p; // nの戻り先をpにする p->next = n; // pの行き先をnにする } else { n->next = p->next; // nの行き先をpの行き先の次の物にする n->prev = p; // nの戻り先をpの戻り先pにする p->next->prev = n; // pの行き先の一つ前をnにする p->next = n; // pの行き先をnにする } } void delete(struct node* p){ if(p != NULL){ p->prev->next=p->next;//pの一つ前(prev)を一つ後(next)を繋げる p->next->prev=p->prev;//pの一つ後(next)と一つ前(prev)を繋げる } }
注意点
insertでは受け取った引数のpの次に値を挿入し、deleteでは受け取った引数pを削除する形となります。
作成時のポイント
- 新しく挿入する値のprevとnextの行き先を先に決める
- headのみの場合とhead以外がある場合で注意をする
- 図に書きながら、prevとnextの行き先を線で結び、コードを書いたら消すようにする。
おまけ(作ったリストの全表示)
リストの中身のみ表示(単方向、双方向対応)
void printlist(struct node* p) { //listを渡す p = p->next; //listの先に行く for (; p != NULL; p = p->next) { printf("%c ", p->elem); //表示 } printf("\n"); }
リストの詳細を表示(単方向リスト用)
void detailprintf_1(struct node* p) { //listを渡す int i = 0; p = p->next; //listの一つ先へ進む for (; p != NULL; p = p->next) { printf("[%d]elem:%c\n", i, p->elem); //値の表示 if (p->next != NULL) { printf("[%d]nextelem:%c\n", i, p->next->elem); //nextの表示 } else { printf("[%d]nextelem:NULL(end)\n", i); //nextがNULLだったNULL(end)と表示 } i++; //先頭からの番号を数える } }
リストの詳細を表示(双方向リスト用)
void detailprintf_2(struct node* p) { //listを渡す int i = 0; p = p->next; //listの一つ先に進む for (; p != NULL; p = p->next) { printf("[%d]elem:%c\n", i, p->elem); //値の表示 if (p->next != NULL) { printf("[%d]nextelem:%c\n", i, p->next->elem); //nextの表示 } else { printf("[%d]nextelem:NULL(end)\n", i); //nextがNULLだったNULL(end)と表示 } if (i != 0) { printf("[%d]prevelem:%c\n", i, p->prev->elem); //prevの表示 } else { printf("[%d]prevelem:HEAD\n", i); //prevがheadだったらHEADと表示 } i++; //先頭からの番号を数える } }
結果(双方向リスト)
int main(void) { struct node* list; list = head(); insert(list, 'a'); insert(list, 'b'); insert(list->next, 'c'); insert(list, 'd'); insert(list, 'e'); delete (list->next); printlist(list); detailprintf(list); return 0; }
d b c a [0]elem:d //先頭(0番目)の値 [0]nextelem:b //次の値(1番目) [0]prevelem:HEAD //前の値(-1番目) [1]elem:b //1番目の値 [1]nextelem:c //次の値(2番目) [1]prevelem:d //前の値(0番目) [2]elem:c //2番目の値 [2]nextelem:a //次の値(3番目) [2]prevelem:b //前の値(1番目) [3]elem:a //3番目の値 [3]nextelem:NULL(end) //次の値(4番目) [3]prevelem:c //前の値(2番目)
まとめ
今回、ポインタを用いたリストの単方向リスト、双方向リストについて書きました。
図を書きながらやるとイメージしやすいです。
(C言語)文字配列と文字列の違い。
フォーマット演算子等についての違いが知りたい方は、以下の記事で書いてますので是非参考にしてみてください。
始めに
上の記事で int array [ ] ≒int* arrayと説明し、 ニアリーイコールがついていますがこのことについて話します。
どちらともぱっと見キャストとして使うことが可能ですが、内部の構造が若干違います。
実は
- char array[ ]="abcde"<=>char array[ ]={"a","b","c","d","e"}となっています。
- char* array<=>const char* arrayはそのままです。
この大きな差は
- 領域なのか値なのかです。
- スコープ(範囲)が異なる
ここで問題になるのが値が代入できない点です。
詳しく見ていきましょう
代入できない
char a[ ]="abcde"; char* b="ABCDE"; b=a; printf("%s\n",b);
結果
abcde
これはできる。じゃあ逆は??
char a[ ]="abcde"; char* b="ABCDE"; a=b; //ここが違う printf("%s\n",b);
結果
error: assignment to expression with array type 8 | a = b; | ^
出来ない。。
このように代入できないときが発生します。
これはaは[ ]で定義しており、[ ] は領域を指し、アドレスを格納するメモリが存在しないからです。
補足
a[0]=v等のことならできます。
スコープが異なる
パターン1
char* aa(){ char* array="abcde";//ここが* return array; } void main(){ puts(aa()); }
結果
abcde
パターン2
char* aa(){ char array[ ]="abcde";//ここが[ ] return array; } void main(){ puts(aa()); }
結果
warning: function returns address of local variable [-Wreturn-local-addr] 6 | return array; | ^~~~~
エラーが出てしまいました。
このエラーは返り値でローカル変数返すなよ。。と言っていてスコープが狭いことを意味します。
こういったところで注意が必要になります。
まとめ
- [ ]で作った文字配列はアドレスの変更ができない。(1つ1つの変更なら可能)
- [ ]で作った文字配列はスコープが自分自身のみ
参考
(C言語)2重ポインタについて
2重ポインタについて少しですがわかりやすくまとめて置きます。
そもそもポインタとは、
変数を定義したときに変数はアドレスというものを持っていて、その別名として変数名があるような形になっています。 このアドレスをつかさどるのがポインタです。
ポインタを使うことで変数をアドレスとして使うことができます。
ここで変数名で使えばいいやんと思うかもしれないが、c言語には文字列という概念が備わっていないので、アドレスを活用して文字列を使います。
1重のポインタ
書き方
int a=10; int\* p; //int \*pでも大丈夫 p=&a; //&は後ろの変数のアドレスを読み取るものです。 printf("%d\n",\*p);// \*はアドレス値から値を読み取ります。
詳しく日本語で説明
- 整数aの値を10とする。(10は値であってアドレスではないです。)
- 整数ポインタ変数pを宣言する。(ポインタ変数にもcharの型etc..があります。)
- 整数ポインタ変数pにaのアドレス値を代入します。
- 整数ポインタ変数pに入っている数値(アドレス)の値を出力します。
これは1重のポインタです。
- *(宣言時)・・・ポインタ変数ですよって意味
- &・・・変数からアドレスと読み取る
- * ・・・アドレスから変数(の値)を読み取る
(アドレス値は適当です。)
&と*は対義語みたいなものです。
2重ポインタ
書き方
int a=10; int\* p; int\* pp; p=&a; //&は後ろの変数のアドレスを読み取るものです。 pp=&p printf("%d\n",\*\*pp);// \*はアドレス値から値を読み取ります。
詳しく日本語で説明
- 整数aの値を10とする。
- 整数ポインタ変数pを宣言する。
- 整数ポインタ変数ppを宣言する。<-違うところ
- 整数ポインタ変数pにaのアドレス値を代入します。
- 整数ポインタ変数ppにpのアドレス値を代入します。
- 整数ポインタ変数ppに入っている数値(アドレス)の値を出力します。
(アドレス値は適当です。)
最後なんて**となっていて*が2つもあります。
この*の数で何重ポインタと言っているのです。
↓↓こんな感じです。。↓↓
まとめ
- *と&は対義語
- わからなくなったら一つ一つ置換(代入するとわかりやすい)
(C言語) 配列宣言の仕方([] *)
C言語の配列
c言語の配列で1年弱でようやく理解したのでまとめました。
- 配列のキャストについて
- printf時のフォーマット指定子
配列のキャスト
軽いまとめ
int array≒int* array
char array≒char* array
[] , *をすることでキャストを宣言します。
補足
キャストとは...
なんでも入ってよい箱(配列,変数)ではなく、専用の箱を作るイメージ
この箱には整数のみ、この箱には小数のみetc...
なぜ≒なのかは下の記事について詳しく書きます。
じゃあなかったらどうなるの??
char array="abcd";で宣言をする
void main(){ //#include <stdio.h>をしています char array="abcd"; printf("%s",array); }
結果
test.c: In function ‘main’: test.c:6:16: warning: initialization of ‘char’ from ‘char *’ makes integer from pointer without a cast [-Wint-conversio ] 3 | char array = "abcd"; | ^~~~~~
これはキャストされていないことを意味し、おいおい1文字しか受け付けないところに2文字以上入れるなよ的な感じです。
ここでchar array[]またはchar* array にすることでキャストされうまく実行いたします。
void main(){ char array1[]="abcd"; //[]でキャスト char* array2="abcd"; //*でキャスト printf("%s",array1); printf("%s",array2); }
結果
abcd abcd
printfの%d,%c,%sの違い
%d,%cはそれぞれ一文字の数字と文字対応 %sは文字列に対応
簡単じゃんと思うかもしれないが、変数の指定の仕方に注意。。。
char* array="abcd"; printf("%c\n",*array);//*あり printf("%s\n",array);//*なし
結果
a abcd
array=array[0]を意味します。 もし2番目のbを取り出したければ(array+1) or array[1]することでうまくいきます。
char* array="abcd"; printf("%c\n",*(array+1));//*あり printf("%c\n",array[1]);//*なし
結果
b b
このように配列名は先頭のポインタを指しますがその際*を付けるのか付かないのかで意味が大きく変わってくるので注意が必要です。
まとめ
- 配列を宣言する時は[]または*をつける
- 文字列を表示する時は*なし。1文字のみの時は*あり。
(Rails) deviselogin出来ないときの対処法(devise)
状況
sign upはできるがloginができない。
(Sign upはname,email,passwordで登録し、Log in時はname,passwordで認証する。)
原因
ストロングパラメーターは設定していたが、/config/initializers/devise.rbのほうを変えていなかった
apprication_controller
before_action :configure_permitted_parameters, if: :devise_controller? private def configure_permitted_parameters devise_parameter_sanitizer.permit(:sign_up, keys: [:name])#変更前 devise_parameter_sanitizer.permit(:sign_up, keys: [:email])#変更後 end
devise.rb
config.authentication_keys = [:email]#変更前 config.authentication_keys = [:name]#変更後
詳細
emailとnameの指定が逆だった。
意味としては、apprication_controllerでsign up時にemail登録を許可し、devise.rbでuser認証時のチェックをnameで行いますよ
ここで実験
- devise.rb->email,apprication_controller->nameの場合
- devise.rb->email,apprication_controller->emailの場合
- devise.rb->name,apprication_controller->nameの場合
- devise.rb->name,apprication_controller->emailの場合
error
- 成功
- 登録時::name can't be blank,ログイン時::Unpermitted parameter: :name
- 登録時::Email can't be blank
- ログイン時::Unpermitted parameter: :name
実験からの考察
user認証をするときに値を取得するのはdevise.rbのほうで行い、 登録する時はdevise.rb,apprication_controller両方を用いる。
まとめ
email以外で認証する時は、devise.rbも変えよう!
(Rails) @book.user_idと@book.userの違い
model
book | user |
---|---|
id | id |
book | name |
user_id |
注意::userとbookには1:Nの関係がある。
状況
この時、bookからuserを指定する時に2通りの書き方ができるように思える。
@book.user_idと@book.userである。(@bookにはidが1つの入る)
しかし、これらは異なるものである↓↓
@book.user_id・・・user_id
@book.user・・・Userのレコード
詳細
@book.user_id #@bookでレコードを指定し、そのレコードのカラムであるuser_idを指定する。 @book.user #@bookでレコードを指定し、そのuser_id=user.idのuserのレコードをしてする。
@book.user_id @bookでレコードを指定(水色)し、.user_idでuser_idを指定(赤色)する。 @book.user @bookでレコードを指定(水色)し、.userでuser_idと同じuserの中のidを指定(赤色)する。そしてそのレコードを指定(黄色)する
上が@book.user_idで下が@book.userである
おまけ
modelに関数を書いた際は、@book.userの方でUserのレコードを指定しないと使えないことに注意。
まとめ
@book.user_id・・・user_id
@book.user・・・Userのレコード
def display_name(user_id) user_id.name end