広告
↓発売日：2018年09月22日↓
 |
新品価格 |
疑似単方向リスト
今回は配列を使って疑似的にデータ構造の基本、リスト構造を作ります。
↑疑似リスト構造による簡易電話帳↑
もちろん実用に耐えうるものではありませんのであくまでプログラミングの入門用としてお使いください。
使い方
以下のソースファイルを開く→[ctrl+a]ですべて選択→[ctrl+c]でコピー→お使いの開発環境のエディタなどに[ctrl+v]貼り付け→保存→コンパイル→実行
あとはメニュー項目に従って操作してください。
注意
電話帳は初期設定で最大２０件登録できます。
２１件目を登録しようとするとおそらく無限ループになります。
名前を入力する時は苗字、名前の間の空白を空けずに入力してください。
入力は全て半角英数小文字で行ってください。
その他もろもろ含め十分なエラー対策はしてないので常識の範囲内で自己責任でお使いください。
リスト構造って？
リスト構造っていうのはあるデータに次のデータのアドレスが入っていて、そのまたあるデータにはその次のデータのアドレスが入っていて・・・、のように数珠つなぎになっているデータ構造になります。
※数珠の終わりを示す「null」という目印が現れるまでひたすらアドレスを辿っていきます※
リスト構造の長所
例えば配列にデータを詰める時、末尾にデータを追加する分には簡単ですが、先頭または途中にデータを挿入、後のデータを一つずつ後方にずらすなどの場合は大変な手間がかかりますよね。
そんな時、リスト構造はそこのデータをつなぎかえるだけで済むので適切なデータにこの構造を用いれば配列などに比べとても高速に処理する事ができます。
疑似的に、とは？
本来Ｃ言語によるリスト構造はポインタを用いた自己参照構造体というものを使って実現するのですが、これがなかなか難しいのでまずはイメージなどが湧きやすいように馴染みのある配列を使って疑似的に再現しようというワケです。
私もこの方法を聞いて試したトコロだいぶ理解が深まりました。
ただ、余計に混乱する場合もあるかと思いますので少し目を通してダメそうでしたら通常の自己参照構造体を用いたリスト構造についても解説しておりますのでそちらをご覧になって頂ければと思います。
それではさっそくやっていきましょう！
メモリ作成
まずは疑似的なメモリを作成します。
#include <stdio.h>
#define MAX_LIST 20
struct LIST{
char name[128];
char num[128];
int next;
int flag;
};
struct LIST list[MAX_LIST];
void disp_memory(void);
int main(){
list[1].flag = 1;
list[3].flag = 1;
list[5].flag = 1;
printf("使用中のメモリ(使用中:1 未使用:0)\n");
disp_memory();
printf("\n");
return 0;
}
void disp_memory(){
int i;
for(i=0;i<MAX_LIST;i++){
printf("[%d]",list[i].flag);
}
}
■実行結果■
こちらが今回疑似的なメモリとなる構造体になります。
#define MAX_LIST 20
struct LIST{
char name[128];
char num[128];
int next;
int flag;
};
struct LIST list[MAX_LIST];
２０個のメモリを用意しました。
そして今回重要なのがこのメモリが使用中かどうかを表す「flag」という変数になります。
実行結果のように、この「flag」が「1」の時はメモリ使用中、「0」の時はメモリ未使用という設定でいきます。
残りの変数は
char name[128]; char num[128];
これは電話帳の名前と電話番号にあたる変数になります。
もちろんこれでなければいけないというワケではないのでお好みのデータにしていただいて大丈夫です。
あとは
int next;
こちらが次のアドレスを保存する変数になります。
この値をもとにリストを辿っていきます。
メモリ確保、メモリ解放
メモリが用意できたので、このメモリをプログラムの実行中に確保、解放する関数「malloc()」「free()」などにあたるものをこの設定で再現していきます。
#include <stdio.h>
#define MAX_LIST 20
struct LIST{
char name[128];
char num[128];
int next;
int flag;
};
struct LIST list[MAX_LIST];
void disp_memory(void);
int my_malloc(void);
void my_free(int );
int main(){
int p,p2,p3;
p = my_malloc();
p2 = my_malloc();
p3 = my_malloc();
printf("使用中のメモリ(使用中:1 未使用:0)\n");
disp_memory();
printf("\n\n");
my_free(p);
my_free(p2);
my_free(p3);
printf("使用中のメモリ(使用中:1 未使用:0)\n");
disp_memory();
printf("\n");
return 0;
}
void disp_memory(){
int i;
for(i=0;i<MAX_LIST;i++){
printf("[%d]",list[i].flag);
}
}
int my_malloc(){
int i;
for(i=0;i<MAX_LIST;i++){
if(list[i].flag == 0){
list[i].flag = 1;
break;
}
}
return i;
}
void my_free(int num){
list[num].flag = 0;
}
■実行結果■
まずはメモリを確保する「my_malloc()」関数を見てみます。
int my_malloc(){
int i;
for(i=0;i<MAX_LIST;i++){
if(list[i].flag == 0){
list[i].flag = 1;
break;
}
}
return i;
}
先ほど用意した２０個のメモリ上の未使用のメモリを探索して未使用のものが見つかれば使用中に、そしてループを抜けてこの時のメモリの番号、いわばアドレスを戻り値として返します。
つまりは配列の添え字にあたる「0番～19番」までがこの疑似メモリのアドレスとなるわけですね。
次にメモリを解放する関数「my_free()」を見てみます。
void my_free(int num){
list[num].flag = 0;
}
これは単純に引数にもらったアドレスのメモリを解放するだけの関数になります。
実行結果をみるとメモリの確保と解放ができたみたいですね。
リスト構造作成開始
それでは下準備ができたトコロで数珠つなぎのデータ構造、リスト構造の作成を開始したいと思います！
先頭と末尾の目印
数珠の先頭と末尾のアドレスを保存する変数を用意します。
/*先頭*/ int head; /*末尾*/ int tail;
この変数の値を目印に先頭や末尾のリスト追加・削除などを行っていきます。
広告
無効データを表す「-1」
次に無効なデータを表す目印を設定します。
#define MY_NULL -1
「MY_NULL」と名付けました。
これがずばり何なのかと一言で説明するのはなかなか難しいので、使い方から説明したいと思います。
リストが空の状態
head = MY_NULL; tail = MY_NULL;
例えばリストに何もデータがない状態を表したい時は、先ほどの先頭・末尾のアドレスを表す変数「head,tail」にこの「MY_NULL」を設定します。
先ほども言いましたが、ここの疑似アドレスのメモリ番号は「0番～19番」ですよね。
もし疑似メモリを増やした場合でも「0番～19番」より番号が増えていくだけなので「MY_NULL」→「-1」とは絶対に被らないというワケです。
リストの末尾
同じ理由でリストの末尾にこの「MY_NULL」を設定しておきます。
この「MY_NULL」を目印に「while」文などでリストを辿るワケです。
ここで「あれ？末尾はtailって言っていたような・・・？」って思いますよね。
ここが少しややこしいのですが、末尾にリストを追加、削除する時の場合などはこの末尾を表す「tail」を別に用意した方がプログラムが簡潔になるのでそのようにしております。
このあたりはプログラムを実際に見た方がわかりやすいと思われます。
ではこれらを目印にリストの追加、削除、表示などをしていきます。
最小限のリストプログラム
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_LIST 20
#define MY_NULL -1
struct LIST{
char name[128];
char num[128];
int next;
int flag;
};
struct LIST list[MAX_LIST];
void init(void);
void add_tail(const char* ,const char* );
void disp_list(void);
void disp_memory(void);
void free_list(void);
int my_malloc(void);
void my_free(int );
int head,tail;
int main(){
char input_name[128];
char input_num[128];
init();
strcpy(input_name,"tanaka");
strcpy(input_num,"09011111111");
add_tail(input_name,input_num);
strcpy(input_name,"saitou");
strcpy(input_num,"09022222222");
add_tail(input_name,input_num);
strcpy(input_name,"watanabe");
strcpy(input_num,"09033333333");
add_tail(input_name,input_num);
disp_list();
printf("\n使用中のメモリ(使用中:1 未使用:0)\n");
disp_memory();
printf("\n\n");
free_list();
printf("使用中のメモリ(使用中:1 未使用:0)\n");
disp_memory();
printf("\n");
return 0;
}
void init(){
head = MY_NULL;
tail = MY_NULL;
}
void add_tail(const char* input_name,const char* input_num){
int p;
p = my_malloc();
if(tail == MY_NULL){
head = p;
}
else{
list[tail].next = p;
}
tail = p;
strcpy(list[tail].name,input_name);
strcpy(list[tail].num,input_num);
list[tail].next = MY_NULL;
}
void disp_list(){
int p;
int n = 0;
p = head;
printf("\n名前 電話番号\n");
while(p != MY_NULL){
printf("%d:%s %s\n",n + 1,list[p].name,list[p].num);
n++;
p = list[p].next;
}
}
void disp_memory(){
int i;
for(i=0;i<MAX_LIST;i++){
printf("[%d]",list[i].flag);
}
}
void free_list(){
int p;
int p2;
p = head;
while(p != MY_NULL){
p2 = list[p].next;
my_free(p);
p = p2;
}
head = MY_NULL;
tail = MY_NULL;
}
int my_malloc(){
int i;
for(i=0;i<MAX_LIST;i++){
if(list[i].flag == 0){
list[i].flag = 1;
break;
}
}
return i;
}
void my_free(int num){
list[num].flag = 0;
}
■実行結果■
いきなりプログラムがどっと増えてしまいましたが、リスト構造はある程度必要なプログラムがどうしてもセットになってしまうのでご了承ください。
初期化
最初リストは空の状態なので先頭、末尾のアドレスを保存する変数「head,tail」も無効データ「MY_NULL」で初期化しておきます。
void init(){
head = MY_NULL;
tail = MY_NULL;
}
末尾に追加
リストを末尾に追加する関数を作ります。
void add_tail(const char* input_name,const char* input_num){
int p;
p = my_malloc();
if(tail == MY_NULL){
head = p;
}
else{
list[tail].next = p;
}
tail = p;
strcpy(list[tail].name,input_name);
strcpy(list[tail].num,input_num);
list[tail].next = MY_NULL;
}
リストを末尾に追加する「add_tail()」になります。
内容を見てみましょう。
まずは一時的に用意した変数「p」に先ほど作ったメモリを確保する「my_malloc()」を使って未使用のメモリアドレスを保存します。
p = my_malloc();
これをもとにリストを末尾に追加していくのですがリストが空の時とそうではない時とで少し処理が分かれます。
リストが空の時
リストが空の時「if(tail == MY_NULL)」の時の処理は
if(tail == MY_NULL){
head = p;
}
tail = p;
と言うように「head,tail」両方に同じアドレスを設定するような感じになります。
この時のリストは一つしかないのでそこが先頭であり末尾でもあるワケです。
リストが一つ以上ある時
次にリストが一つ以上ある場合です。
先ほどの「if」文の「else」部分ですね。
else{
list[tail].next = p;
}
この時は「list[tail]」の表す場所がそのリストの末尾にあたるので、その次「list[tail].next」に新しく確保したメモリ番号を保存、
そして同時にそこが新たな末尾になるので
tail = p;
末尾として設定しなおします。
そして引数として受け取ったデータを保存
strcpy(list[tail].name,input_name); strcpy(list[tail].num,input_num);
最後にリストを辿る時の末尾の目印「MY_NULL」を設定すれば
list[tail].next = MY_NULL;
末尾に追加する関数は完成です。
データを表示
それでは実際にリストの末尾を示す「MY_NULL」を目印にリストを辿ってみましょう！
リスト内のデータを表示する関数「disp_list()」になります。
void disp_list(){
int p;
int n = 0;
p = head;
printf("\n名前 電話番号\n");
while(p != MY_NULL){
printf("%d:%s %s\n",n + 1,list[p].name,list[p].num);
n++;
p = list[p].next;
}
}
リストを辿る部分だけを抜き出してみます。
void disp_list(){
int p;
p = head;
while(p != MY_NULL){
p = list[p].next;
}
}
リスト構造プログラムの象徴的部分ですね。
一時的にアドレスを保存する変数「p」を用意してそこに先頭アドレスを保存、
そのアドレスがリストの末尾を示す「MY_NULL」ではない間
while(p != MY_NULL){
}
ひたすらその時のリストが保存している次のリストのアドレスと
p = list[p].next;
入れ替えます。
こうして「MY_NULL」が来るまでひたすらリストを辿る事ができるというワケですね。
メモリ解放
同じようなやり方でメモリも解放していきます。
メモリをすべて解放する「free_list()」になります。
void free_list(){
int p;
int p2;
p = head;
while(p != MY_NULL){
p2 = list[p].next;
my_free(p);
p = p2;
}
head = MY_NULL;
tail = MY_NULL;
}
この設定では起こりえないですが、実際の「malloc()」「free()」を用いたリスト構造プログラムではメモリは解放された瞬間に構造体のカタチを成さなくなるのでその構造体のもっている次のリストへのアドレスってもんがわからなくなってしまいます。
なので、その前にそのリストが持っている次のアドレスの値を退避させながらメモリを解放していきます。
リストの基本
ざっと説明しましたが、ここまでが単方向リストの基本プログラムになります。
実際のリスト構造でも動的にメモリを確保しながらリストを作り上げていくので、最後メモリを解放するまでがセットのプログラムになるわけですね！
あとは今使ったような「○○を目印にリストを辿る」、「アドレスをつなぎかえる」、「無効データMY_NULLを設定」などを駆使して他の機能も実現していきます。
いくつか作ってみたので続けて見てみましょう。
先頭に追加
void add_head(const char* input_name,const char* input_num){
int p;
if(head != MY_NULL){
p = my_malloc();
strcpy(list[p].name,input_name);
strcpy(list[p].num,input_num);
list[p].next = head;
head = p;
}
else{
add_tail(input_name,input_num);
}
}
先頭にリストを追加する「add_head()」です。
リストが空の時、末尾「MY_NULL」の設定などに先ほど作った関数「add_tail()」を使うので、その後にこちらの関数は作らなければいけません。
リストが空の時
if(head != MY_NULL){
}
else{
add_tail(input_name,input_num);
}
先ほども言いましたとおりそのまま「add_tail()」にデータを渡すだけです。
先頭に追加
if(head != MY_NULL){
p = my_malloc();
strcpy(list[p].name,input_name);
strcpy(list[p].num,input_num);
list[p].next = head;
head = p;
}
新しくメモリを確保、そのメモリの次のアドレスに今までの先頭「head」を設定、そして先頭「head」をその新しく確保したメモリのアドレスに置き換えれば先頭に追加する関数は完成です。
先頭を削除
void del_head(){
int p;
if(head != MY_NULL){
p = list[head].next;
my_free(head);
head = p;
if(head == MY_NULL){
tail = MY_NULL;
}
}
}
先頭を削除する「del_head()」です。
いきなり先頭部分のアドレスを消去してしまうとその先頭部分が持っている次のアドレスがわからなくなってしまうので先にその先頭部分が持っている次のアドレスを退避させます。
一時的にアドレスを保存する変数を用意して、
int p;
そこに先頭の次のアドレスを
p = list[head].next;
保存すれば退避完了ですね。
あとは先頭を削除、新しい先頭を設定すれば完了です。
my_free(head); head = p;
もし先頭部分が「MY_NULL」の場合はリストが空の状態になるので末尾の「tail」も
if(head == MY_NULL){
tail = MY_NULL;
}
というように「MY_NULL」を設定してあげます。
末尾を削除
void del_tail(){
int p;
if(tail != MY_NULL){
p = head;
while(p != MY_NULL){
if(list[p].next == tail){
list[p].next = MY_NULL;
break;
}
p = list[p].next;
}
my_free(tail);
tail = p;
if(tail == MY_NULL){
head = MY_NULL;
}
}
}
末尾を削除する「del_tail()」になります。
末尾の削除は先頭の削除より少しだけ複雑になります。
最終的に末尾の部分に「MY_NULL」を設定しなおすのですが、その場所を調べる必要があります。
list[tailの一つ前].next = MY_NULL;
イメージとしてはこんな感じですね。
そしてこの一つ前の部分のアドレスを保存している変数はないので、少し手間ですが先頭からそこまで辿る必要があります。
いつものように一時変数を用意してそこに先頭部分のアドレスを保存、辿っていきます。
while(p != MY_NULL){
if(list[p].next == tail){
list[p].next = MY_NULL;
break;
}
p = list[p].next;
}
「if(list[p].next == tail)」この時が「tailの一つ前」の状態なのでこの部分を「MY_NULL」に設定、ループを抜けます。
あとは新たに末尾を設定しなおしてリストが空なら「head」も「MY_NULL」に設定して完了です。
リスト構造本番へ
いかかがでしたでしょうか？
実際のリスト構造は自己参照構造体という謎の構造体に加え、ポインタやメモリの動的確保・解放などおそらく入門者にとって実感が湧きずらい機能を駆使して作り上げていくのできっとハードルが高いのかなと思われます。
こうしてメモリを配列に、アドレスを配列の添え字に、など使い慣れたものに置き換える事によって何がどの部分を意味しているのかというのが、少しばかりわかりやすくなったのではないでしょうか？
余計に混乱してしまった方は申し訳ないです。
という事でここまではあくまでも疑似的なリスト構造の作り方になります。
本番の自己参照構造体を用いたリスト構造の方もできるだけ今回の作り方と同じように作ってありますのでよかったら覗いてみてください。
広告
↓発売日：2016年02月29日↓
 |
12歳からはじめる ゼロからのC言語 ゲームプログラミング教室 新品価格 |
↓発売日：2018年06月22日↓
 |
新品価格 |
↓発売日：2018年03月09日↓
 |
新品価格 |
↓発売日：2017年06月14日↓
 |
新品価格 |
↓発売日：2018年05月21日↓
 |
新品価格 |
↓発売日：2017年12月07日↓
 |
新品価格 |
↓発売日：2017年02月08日↓
 |
新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ) 新品価格 |
↓発売日：2017年09月26日↓
 |
新品価格 |
