<<前 [TOP] 次>>
Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。
【QUE_STUCK.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> /*header of STUCK*/ typedef struct STUCK { struct STUCK *prev; void *data; }STUCK; STUCK *newObj(void *data); void *get_stuck(void); void add_stuck(void *data); static STUCK *First=NULL; STUCK *newObj(void *data){ STUCK *p; p = (STUCK *)malloc(sizeof(STUCK)); p->prev=NULL; p->data=data; return p; } void *get_stuck(void) { STUCK *lp = First; void *data; if(lp ==NULL) { /*データにキューがないとき*/ return NULL; } data = lp->data; lp = lp->prev; free(First); First = lp; return data; } void add_stuck(void *data) { STUCK *lp = First; STUCK *newl,*p; if(lp == NULL) { /*リストが空なら*/ First = newObj(data); } else { p=lp; newl = newObj(data); newl->prev = p; lp=newl; First = newl; } } int main() { char *s1; char *s2; char *s3; char *s4; float zenki; float kouki; float report; float shutsuseki; char buf1[512]; char buf2[512]; char buf3[512]; char buf4[512]; int i=0; std::ifstream fin; fin.open("C:\\test\\Data.txt",std::ios::in); while (fin >> buf1 >> buf2 >> buf3 >> buf4 >> zenki >> kouki >> report >> shutsuseki ){ s1 = (char *)malloc( strlen(buf1) + 1 ); strcpy_s(s1, strlen(buf1) + 1, buf1); s2 = (char *)malloc( strlen(buf2) + 1 ); strcpy_s(s2, strlen(buf2) + 1, buf2); s3 = (char *)malloc( strlen(buf3) + 1 ); strcpy_s(s3, strlen(buf3) + 1, buf3); s4 = (char *)malloc( strlen(buf4) + 1 ); strcpy_s(s4, strlen(buf4) + 1, buf4); add_stuck(s1); add_stuck(s2); add_stuck(s3); add_stuck(s4); } for ( ; First;) { std::cout <<(char *)( First->data) << std::endl; get_stuck(); } }
リストで何度も使ってきたように、構造体で新しい型を定義することができます。
struct List { struct List *next; void *data; };
これは新しいstruct List型という型を作っていることになるのですが、表現方法としてはintなどに対してstruct Listと書くのはあまり型という感じがしないかもしれません。
そこでこのstruct Listを省略して書く方法が用意されています。
このため新しい宣言が「typedf」で次のようになります。
typedf struct List LIST;
このように書くことで新しい型名LISTが定義されます。
以降はstruct Listの変わりにLISTが使えるようになります。
LIST *newl;
なお２度に分けて書かずに以下のように書くこともできます。
typed struct List { struct List *next; void *data; } LIST;
この際LISTは変数名ではなく新しい型の名前であることに注意してください。
キューは入出力機構の実装によく用いられるメカニズムで最初に入ってきたデータから処理し、その後入ってきたデータは最後の列に並んでいくという処理をします。
まずデータが入ってくる場合ですが、入ってくるデータはすべてリストの最後に付け加えます。
つまりキューからデータを取り出す場合には必ずリストの先頭から取り出すようにします。
ヘッダーは次のようになります。
/* header of QUE */ typed struct Que { struct Que *next; void *data; } QUE; static QUE *First;
ここでtypedfを用いてQUEを作っていますが、リストの最初の要素の場所をどうやって保持するかという点がリストの実現方法と少し異なります。
この例では最初からモジュール内部にFirstという静的外部変数 staticを用意しています。
このstaticを宣言するとモジュールの外側からはこの変数が利用できなくなります。
もちろんモジュール内部では普通にいつも通り使えます。
キューからデータを取り出す関数は、最初の要素からデータを取り出してその要素をリストから取り除きます。
もしキューにある要素がない場合はNULLを返します。
void *get_que(void) { QUE *lp = First; void *data; if(lp==NULL){ /* データがキューにないとき */ return NULL; } data = lp->data; lp = lp->next; free(First); First=lp; return data; }
次にキューに一個新たにデータを追加する関数では、リストの最後にデータを作って追加します。
キューにデータがない場合にのみFirstを更新します。
void add_que(void *data) { QUE *lp = First; if(lp!=NULL) { while(lp->next!=NULL) { lp=lp->next; } lp = lp->next = (QUE*)malloc(sizeof(QUE)); } else { lp = First=(QUE*)malloc(sizeof(QUE)); } lp->data = data; lp->next = NULL; return; }
スタックは机の上に本を重ねて置いていくようなものだと考えます。
つまり最初に置かれた本は一番下にあり、スタックに本を積んでいき取り出すときには一番上に置かれた本が取り出されます。
最初に置かれた本は最後に取り出されることになるのです。
スタックを実現するにはリストの最後にデータを追加し、常にリストの最後のデータを取り出すようにすればよいです。
サンプルプログラムについて説明します。
このプログラムはスタックをリストを使って実装しています。
get_stuck()関数でデータを取り出して、取り出したデータを消去しています。
実行結果はデータが逆順に出力されます。
これがスタックの動作です。
このサンプルプログラムはCドライブの「test」フォルダに入れた[Data.txt]ファイルを読み込みます。
【C:\test\Data.txt】
yamada 2001 1 1 70 65 15 15 suzuki 2001 2 3 80 90 10 13 satou 2001 3 2 80 60 13 12 tanaka 2000 11 1 65 70 12 15
Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。
【QUE_STUCK2.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> /*header of STUCKQUE*/ typedef struct STUCKQUE { struct STUCKQUE *prev; struct STUCKQUE *next; void *data; }STUCKQUE; STUCKQUE *newObj(void *data); void *get_stuck(void); void *get_que(void); void add_stuckque(void *data); static STUCKQUE *First=NULL; static STUCKQUE *After=NULL; STUCKQUE *newObj(void *data){ STUCKQUE *p=NULL; p = (STUCKQUE *)malloc(sizeof(STUCKQUE)); p->prev=NULL; p->next=NULL; p->data=data; return p; } void *get_stuck(void) { STUCKQUE *lp = After; void *data; if(lp ==NULL) { /*データにキューがないとき*/ return NULL; } data = lp->data; lp = lp->prev; free(After); After = lp; return data; } void *get_que(void) { STUCKQUE *lp = First; void *data; if(lp==NULL) { /*データがないとき*/ return NULL; } data = lp->data; lp = lp->next; free(First); First = lp; return data; } void add_stuckque(void *data) { STUCKQUE *newl = NULL, *p = NULL; if(First == NULL) { /*リストが空なら*/ First = newObj(data); } if(After == NULL) { /*リストが空なら*/ After = newObj(data); } else { p=First; newl=newObj(data); while(p->next!=NULL){ p=p->next; } p->next=newl; newl->prev=p; After=newl; } } int main() { char *s; char buf[512]; std::ifstream fin; fin.open("C:\\test\\Welcome.txt", std::ios::in); while (fin >> buf) { s = (char *)malloc(strlen(buf) + 1); strcpy_s(s, strlen(buf) + 1, buf); add_stuckque(s); } /* キューとて使うとき */ for (; First;) { std::cout << (char *)(First->data) << std::endl; get_que(); } }
双方向リンクリストを使うと、キュートしても、スタックとしても使えるようなデータ構造が記述できます。
これを仮にスタックキューと呼びます。
スタックキューでは便宜上、常にデータを取り出す際には最後尾のデータが取り出されるものしています。
従ってスタックとして使うときには最後尾にデータを追加し、キューとして使うときには最前列にデータを追加すればよいです。
このようなスタックキューを設計しモジュールとして使えるようにしました。
このサンプルプログラムではキューとして使う場合の記述をしています。
もしスタックとして使用する場合は、最後の部分を以下のように書き換えます。
/* スタックとして使うとき */ for ( ; After;) { std::cout <<(char *)( After->data)<< std::endl; get_stuck(); } }
キューとして使う場合（[QUE_STUCK2.cpp]）の実行結果です。
このサンプルプログラムはCドライブの「test」フォルダに入れた[Welcome.txt]ファイルを読み込みます。
【C:\test\Welcome.txt】
#include <iostream>
int main() {
std::cout << "ようこそ！C++の世界へ！";
std::cout << std::endl;
}
スタックとして使用する場合の実行結果です。
↓↓クリックして頂けると励みになります。
