>>この記事には書き直した新しいページがあります。<<
<<前 [TOP] 次>>
Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。
【ListTest1.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> struct eLIST *newObj(char * data); struct eLIST *insList( struct eLIST **pstart, char *data ); struct eLIST { struct eLIST *next; char *body; }; /* eLIST のオブジェクトを作り、それはdataを保持 */ struct eLIST *newObj(char *data){ struct eLIST *p; p = (struct eLIST *)malloc(sizeof(struct eLIST)); p->next=NULL; p->body=data; return p; } /* 一般的な要素の追加、但し先頭への追加のみできず */ struct eLIST *insList( struct eLIST **pstart, char *data ){ struct eLIST *newl = NULL, *p = NULL; if(*pstart==NULL){ /* リストが空なら */ *pstart=newObj(data); } else{ if(p==NULL){ /* after が NULL なら末尾を探す */ p=*pstart; while(p->next != NULL){ p=p->next; } } newl = newObj(data); newl->next = p->next; p->next = newl; } return newl; } void main() { struct eLIST *start=NULL; struct eLIST *xp; char *s; char buf[512]; int i=0; 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); xp=insList(&start, s); } for (xp=start; xp; xp=xp->next) { std::cout << xp->body << std::endl; } }
リストでは、メモリを確保する際に余分にメモリを確保して、その余分なメモリにアドレスを入れておきます。
自分のアドレスを入れておいても意味がないので、次のメモリを確保した際に前のメモリオブジェクト中にその新しく確保したメモリへのアドレスを入れておきます。
このようにすることで、先頭のオブジェクトへのアドレスを覚えていれば、次のアドレスはそのオブジェクト中に埋め込まれているので、芋づる式にすべてのオブジェクトが探索できるようになります。
この意味に置いて、リストは直線的につながっているので、線形リスト、片方向リストとも呼ばれています。
struct LIST { struct LIST *next; char body[20]; };
この定義で重要なのは、struct LIST *next；です。
通常、構造体の定義に自分自身を用いてはならないのですが、この場合はポインタなのでこの限りではありません。
このようにしてできたnextには、もしそのオブジェクトが最後のオブジェクトならば次のデータは存在しませんので、NULLを入れておきます。
NULLは何も存在しないという意味で使われます。
リストの追加は、次のようにします。
struct LIST *newList( struct LIST **pstart){ struct LIST *p = NULL, *newl = NULL; p = *pstart; newl = (struct LIST *)malloc(sizeof(struct LIST); newl->next = NULL; if(p!=NULL){ /* リストに要素が存在するとき */ while(p->next!=NULL) { /* リストの末尾を探す */ p=p->next; } p->next = newl; /* リストの末尾につなげる */ } else { *pstart = newl; /* 最初の要素の場所を*pstartに */ } return newl; }
リストでは後戻りできないので、先頭のオブジェクトへのポインタは必ず覚えていなければなりません。
上の関数newList()はそうしたリストの先頭オブジェクトへのアドレスを引数にとります。
関数内部では、まず、新しいオブジェクトをmalloc()で割り当てて、それの後ろにはもうデータがないので最初からnextにNULLを代入しておきます。
次に、先頭のオブジェクトへのポインタがNULLでないならば、リストにいくらかのオブジェクトが連なっていますから、先頭から順に次のオブジェクトへのアドレスを取り出し、最後のオブジェクトになるまで移動し、先に確保したオブジェクトをこのリストの最後のオブジェクトの後ろにぶら下げるために、そのアドレス（newl）を最後のオブジェクトのnextに入れています。
一方、引数をstruct LIST **にしているのは、使うときには実際のリストの先頭へのアドレスを保持しているポインタ変数のアドレスを渡すようにします。
従って、この関数を実際に使う場合には以下のようにして使う必要があります。
struct LIST *start=NULL; ・・・・ newList(&start);
リストから特定のオブジェクトを削除する場合には、単にfree()してはいけません。
きちんとオブジェクトの連鎖から取り除いた後にfree()しなければなりません。
/* 要素を削除 */ struct LIST * delList( struct LIST **pstart, struct LIST * target){ struct LIST *p=*pstart; struct LIST *newl; if(p==target){ /* 先頭の要素を削除するとき */ *pstart = target->next; /* ２番目の要素が先頭になります */ } else{ while(p->next!=target){ /* 削除対象の一つ手前まで移動 */ p=p->next; } p->next=target->next; /* targetを飛ばした連鎖を作る */ } free(target); return p; }
上のプログラムでは、引数にリストの先頭と削除対象のオブジェクトへのポインタ（target）を与え、targetを指している一つ前のオブジェクトのnextを一つ飛ばしのオブジェクトへと入れ替えてから、targetのオブジェクトをメモリから削除しています。
リスト構造の柔軟性は、リストへのオブジェクトの挿入でも見られます。
リストの挿入は、すでにオブジェクトが用意されていた場合次のように簡単なものです。
struct LIST *midList( struct LIST *before, struct LIST *newl) { struct LIST *p = before; newl->next = before->next; before->next = newl; return target; }
ここで、beforeはオブジェクトを挿入したい場所の前に位置するリンクのオブジェクトであり、newlは新たに挿入したいオブジェクトです。
ポイントは、beforeの次にnewlが来るようにし、newlの後ろにもともとbeforeの後ろに位置していたオブジェクトを繋げることです。
ただし、このプログラムでは先頭にオブジェクトを入れることができないので注意してください。
ファイルの入出力について説明します。
ファイルを入出力に使うためには、まず実際のデータの入出力に先立って、どのファイルをどの様に使うかを指定しなければいけません。
これをファイルをオープンするといいます。
このために使われる関数が、open()ですが、C++では少し特殊なやり方で用います。
#include<fstream> ・・・ std::ifstream fin; fin.open( "newfile.txt" );
std::cinを用いて出力するやり方に少し似ていますが、自分でfinという変数を宣言しなければならない点が少し違います。
また、宣言した後に、どのファイルに対して読み書きを行うかを指定するために、ファイル名をopen()を用いて指定しなければなりません。
なお、open()関数を使うには先頭で#include
例えば、”test.data”というファイルを読み込み用にオープンするには以下のように指定します。
#include<fstream> ・・・・ std::ifstream fin; ・・・・ fin.open("test.data", std::ios::in);
同じように書き込みようにファイルをオープンするには以下のようにします。
#include<fstream> ・・・・ std::ofstream fout; ・・・・ fout.open("test.data", std::iso::out); ・・・・
もし、このファイルが存在しない場合には新たに自動的に作成されますが、逆に存在した場合にはそのファイルの中身はすべて消されてしまいますので注意が必要です。
std::iso::outモードではファイルを消してしまうことになりますので、ファイルを消さずに書き込みを行うにはstd::iso::appモードを用います。
char *file_name="test.data"; ・・・・ fout.open(file_name, std::iso::app);
この場合、もしファイルが存在したならば、そのファイルの最後に追加して書き込みがなされます。
ファイルが存在しないならば、新たに作成される点はstd::iso::outモードと同じです。
実際の入出力については次の項目で取り扱うことにして、入出力が終了し、ファイルの読み書きを終了し、オープンしたファイルをクローズする際にはclose()を用います。
#include<fstream> ・・・・ std::ofstream fout; ・・・・ fout.open("test.data", std::iso::out); ・・・・ fout.close();
ファイルに対する入出力は、std::cinやstd::coutと同じようにして一文字の読み書も出来ます。
std::ifstream fin; fin.open("test.data"); fin << "test";
ではこのサンプルプログラムについて少し説明します。
このプログラムは片方向リンクリストのサンプルプログラムです。
ファイルから読み込んだ文字列を記憶し、読み込み終了後、それらを順に出力するプログラムです。
newObj()関数では、dataのメモリを確保し、構造体のメンバーにアドレスを代入して返します。
main()関数の
for (xp=start; xp; xp=xp->next) {
std::cout << xp->body << std::endl;
}
の部分では、リストのデータを画面に出力しています。
xpがNULLになるまでループ続きます。
今回は、[Welcome.txt]というファイルをCドライブに作成した「test」というフォルダに入れています。
【C:\test\Welcome.txt】
#include <iostream>
int main() {
std::cout << "ようこそ！C++の世界へ！";
std::cout << std::endl;
}そのアドレス指定が以下の部分です。
fin.open("C:\\test\\Welcome.txt", std:: ios::in);
実行結果です。
[Welcome.txt]の内容が表示されます。
Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。
【ListTest2.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> struct eLIST *newObj(void * data); struct eLIST *inList( struct eLIST **pstart, struct eLIST **after, void *data ); struct eLIST { struct eLIST *next; struct eLIST *prev; void *body; }; /* eLIST のオブジェクトを作り、それはdataを保持 */ struct eLIST *newObj(void *data){ struct eLIST *p; p = (struct eLIST *)malloc(sizeof(struct eLIST)); p->next=NULL; p->prev=NULL; p->body=data; return p; } /* 一般的な要素の追加、但し先頭への追加のみできず */ struct eLIST *inList( struct eLIST **pstart,struct eLIST **after, void *data ){ struct eLIST *newl = NULL, *p = NULL; if(*pstart==NULL){ /* リストが空なら */ *pstart=newObj(data); } else{ p=*pstart; newl=newObj(data); while(p->next!=NULL){ p=p->next; } p->next=newl; newl->prev=p; *after=newl; } return newl; } void main() { struct eLIST *start=NULL; struct eLIST *after=NULL; struct eLIST *xp; 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); xp=inList(&start,&after,s); } for (xp=start; xp; xp=xp->next) { std::cout << (char *)(xp->body) << std::endl; } for (xp=after ;xp; xp=xp->prev) { std::cout << (char *)(xp->body) << std::endl; } }
これまでのリストは、頭から順にしか探索できないもので、その意味で片方向リンクリストと呼ばれますが、ここでは後戻りもできる双方向リンクリストについて考えます。
struct dLINK { struct dLINK *prev; /* 前のオブジェクトへのポインタ */ struct dLINK *next; /* 後ろのオブジェクトへのポインタ */ void *data; };
双方向リンクリストで重要な点は、リストの両端にあるオブジェクトでは、必ずprevか、あるいはnext変数の何れかがNULLになっている点です。
双方向リンクリストでは、片方向リンクリストと違って、特別な先頭アドレスを覚えておく必要はなく、リストのどれかのオブジェクトの位置さえ失わなければ、常にリストの全オブジェクトが得られますが、そのためにリスト中をいったりきたりしなければならなくなるので、効率という点からするとやはり先頭アドレスを保持していた方が良いでしょう。
このサンプルプログラムは、双方向リンクリストの例になっています。
[Welcome.txt]を順方向と逆方向に表示します。
今回は構造体のメンバーの型にvoidを使用しました。
void *body;
これにより、いろいろな型のデータを格納できます。
使用するときは、 (char *)(xp->body)などとして、キャストします。
実行結果です。
Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。
【ListTest3.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> struct eLIST *newObj(int point,void *name, void *nyuugaku_nen, void *kumi, void *gakunen ); struct eLIST *inList( struct eLIST **pstart,int point,void *name, void *nyuugaku_nen, void *kumi, void *gakunen ); /* eLIST*/ struct eLIST { struct eLIST *next; struct eLIST *prev; void *name; void *nyuugaku_nen; void *kumi; void *gakunen; int point; }; /* eLIST のオブジェクトを作り、それはdataを保持 */ struct eLIST *newObj(int point,void *name, void *nyuugaku_nen, void *kumi, void *gakunen){ struct eLIST *p; p = (struct eLIST *)malloc(sizeof(struct eLIST)); p->next=NULL; p->prev=NULL; p->point=point; p->name=name; p->nyuugaku_nen=nyuugaku_nen; p->kumi=kumi; p->gakunen=gakunen; return p; } /* 一般的な要素の追加、但し先頭への追加のみできず */ struct eLIST *inList( struct eLIST **pstart, int point,void *name, void *nyuugaku_nen, void *kumi, void *gakunen){ struct eLIST *newl = NULL, *p = NULL; if(*pstart==NULL){ /* リストが空なら */ *pstart=newObj(point,name,nyuugaku_nen,kumi,gakunen); } else{ if(p==NULL){ /* after が NULL なら末尾を探す */ p=*pstart; while(p->next != NULL){ p=p->next; } } newl =newObj(point,name,nyuugaku_nen,kumi,gakunen); newl->next = p->next; p->next = newl; } return newl; } void main() { struct eLIST *start=NULL; struct eLIST *xp; char *s1; char *s2; char *s3; char *s4; char buf1[512]; char buf2[512]; char buf3[512]; char buf4[512]; int zenki; int kouki; int report; int shutsuseki; 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); int point =(zenki+(kouki/2)+(report*2)+(shutsuseki*20/15))/2; xp=inList(&start, point,s1,s2,s3,s4); } for (xp=start;xp;xp=xp->next) { std::cout << (char *)(xp->name) << std::endl; std::cout << (char *)(xp->nyuugaku_nen) << std::endl; std::cout << (char *)(xp->kumi) << std::endl; std::cout << (char *)(xp->gakunen) << std::endl; std::cout << xp->point << std::endl; } }
学生のデータ[Data.txt]をリストへと格納するプログラムです。
[Data.txt]はCドライブの「test」フォルダに入れてあります。
【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
通年成績も計算し、格納しています。
データは、スペースで区切られ、順に、名前、入学年度、学年、組、前期点数、後期点数、前期レポート提出回数、後期レポート提出回数になっています。
この、スペースで区切られたデーターが、以下の部分で読み込まれます。
while (fin >> buf1 >> buf2 >> buf3 >> buf4 >> zenki >> kouki >> report >>shutsuseki ){
buf1が名前に対応します。
以下、スペースで区切られている順に対応しています。
名前、入学年度、学年、組、通年点数が順番に表示されます。
実行結果です。
<<前 [TOP] 次>>
