↓↓クリックして頂けると励みになります。
【24 | ポインターの応用】 << 【ホーム】 >> 【26 | キューとスタック】
C++における「リスト」は、要素を順序付けて格納するデータ構造の一種です。
C++でリストを実装する方法はいくつかありますが、今回はポインターを利用したリストの実装を行います。
C++標準ライブラリで提供されているリストの実装方法を参考までにあげておきます。
std::list: C++標準ライブラリで提供されている、双方向連結リストを実装したコンテナです。std::listは、要素の挿入や削除が効率的であり、イテレータを介してリスト内の要素を効率的に走査できます。
C++におけるイテレータは、コンテナ（例えば、配列、リスト、マップなど）内の要素に順番にアクセスするための機能です。
イテレータは、コンテナ内の要素を反復処理するための一般的な手段を提供します。
イテレータはポインターのように振る舞い、特定の要素を指すための機能を持ちますが、ポインターとは異なり、コンテナの内部実装の詳細に依存せず、抽象化されています。
std::forward_list: C++標準ライブラリで提供されている、単方向連結リストを実装したコンテナです。std::forward_listは、要素の挿入が効率的であり、イテレータを介してリスト内の要素を効率的に走査できます。ただし、双方向連結リストとは異なり、逆方向へのイテレーションがサポートされていません。
Visual Studio Codeで以下の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; } int main() { struct eLIST *start=NULL; struct eLIST *xp; char *s; char buf[512]; int i=0; std::ifstream fin; fin.open("Welcome.txt", std:: ios::in); while (fin >> buf){ s = (char *)malloc( strlen(buf) + 1 ); strcpy(s, 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」と同じようにして1文字の読み書も出来ます。
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」というファイルをcppプログラムを保存してあるフォルダに入れています。
そのアドレス指定が以下の部分です。
fin.open("Welcome.txt", std:: ios::in);
フォルダに入れた「Welcome.txt」の内容は以下の通りです。
新規作成 【Welcome.txt】
#include <iostream>
int main() {
std::cout << "ようこそ！C++の世界へ！";
std::cout << std::endl;
}
実行結果は「Welcome.txt」の内容が表示されます。
~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ ListTest1.cpp -o ListTest1 && "/Users/** /Desktop/Programming/CPP/"ListTest1 #include <iostream> int main() { std::cout << "ようこそ！C++の世界へ！"; std::cout << std::endl; }
Visual Studio Codeで以下の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; } int main() { struct eLIST *start=NULL; struct eLIST *after=NULL; struct eLIST *xp; char *s; char buf[512]; std::ifstream fin; fin.open("Welcome.txt",std::ios::in); while (fin>>buf){ s = (char *)malloc( strlen(buf) + 1 ); strcpy(s, 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)」などとして、キャストします。
実行結果です。
~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ tempCodeRunnerFile.cpp -o tempCodeRunnerFile && "/Users/**/Desktop/Programming/CPP/"tempCodeRunnerFile #include <iostream> int main() { std::cout << "ようこそ！C++の世界へ！"; std::cout << std::endl; } } std::endl; << std::cout "ようこそ！C++の世界へ！"; << std::cout { main() int <iostream> #include
Visual Studio Codeで以下の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; } int 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("Data.txt",std::ios::in); while (fin>> buf1 >> buf2 >> buf3 >> buf4 >> zenki >> kouki >> report >> shutsuseki ){ s1 = (char *)malloc( strlen(buf1) + 1 ); strcpy(s1, buf1); s2 = (char *)malloc( strlen(buf2) + 1 ); strcpy(s2, buf2); s3 = (char *)malloc( strlen(buf3) + 1 ); strcpy(s3, buf3); s4 = (char *)malloc( strlen(buf4) + 1 ); strcpy(s4, 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」をリストへと格納するプログラムです。
cppプログラムファイルを保存しているフォルダに入れください。
新規作成【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が名前に対応します。
以下スペースで区切られている順に対応しています。
実行結果を確認してみましょう。
名前、入学年度、学年、組、通年点数が順番に表示されます。
~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ ListTest3.cpp -o ListTest3 && "/Users/** /Desktop/Programming/CPP/"ListTest3 yamada 2001 1 1 76 suzuki 2001 2 3 81 satou 2001 3 2 76 tanaka 2000 11 1 72
【24 | ポインターの応用】 << 【ホーム】 >> 【26 | キューとスタック】
↓↓クリックして頂けると励みになります。
