広告
↓発売日：2018年09月22日↓
 |
新品価格 |
単方向リスト
今回は自己参照構造体を使ったデータ構造の基本、リスト構造を作ります。
↑リスト構造による簡易電話帳↑
もちろん実用に耐えうるものではありませんのであくまでプログラミングの入門用としてお使いください。
使い方
以下のソースファイルを開く→[ctrl+a]ですべて選択→[ctrl+c]でコピー→お使いの開発環境のエディタなどに[ctrl+v]貼り付け→保存→コンパイル→実行
あとはメニュー項目に従って操作してください。
注意
名前を入力する時は苗字、名前の間の空白を空けずに入力してください。
入力は全て半角英数小文字で行ってください。
その他もろもろ含め十分なエラー対策はしてないので常識の範囲内で自己責任でお使いください。
リスト構造って？
リスト構造っていうのはあるデータに次のデータのアドレスが入っていて、そのまたあるデータにはその次のデータのアドレスが入っていて・・・、のように数珠つなぎになっているデータ構造になります。
※数珠の終わりを示す「null」という目印が現れるまでひたすらアドレスを辿っていきます※
リスト構造の長所
例えば配列にデータを詰める時、末尾にデータを追加する分には簡単ですが、先頭または途中にデータを挿入、後のデータを一つずつ後方にずらすなどの場合は大変な手間がかかりますよね。
そんな時、リスト構造はそこのデータをつなぎかえるだけで済むので適切なデータにこの構造を用いれば配列などに比べとても高速に処理する事ができるというワケです。
リスト構造が難しいという方は
リスト構造は自己参照構造体という謎の構造体を使う事のみならず、アドレスを扱うポインタ、メモリ動的確保、解放の「malloc()・free()」関数など初心者泣かせの技術を駆使して作られる為に難しくてわかりづらいという声がよく聞かれます。
そんな方の為におそらく馴染み深いであろう配列を使って疑似的にリスト構造の再現を試みてみたのでよかったらのぞいてみてください。
私もこの方法を試したおかげで、だいぶ理解が深まりました。
ただ余計に混乱する場合もあるかと思いますので少し見てダメそうでしたら普通にこちらで学ばれた方が良いかもしれません。
それではさっそくやっていきましょう！
自己参照構造体
struct LIST{
char name[128];
char num[128];
struct LIST* next;
};
まずこちらがややこしさの元凶!?である自己参照構造体になります。
「char name[128]」「char num[128]」は良いとして問題は残りの
struct LIST* next;
こちらですね！
私も当初これを見た時は
「リストの中にリストがあって、さらにその中にリストがあって、さらにその中にリストがあって、さらに・・・」
このようなイメージを抱いておりました！
恐るべき無限ループです！
しかし騙されてはいけません。
これはただ単に「次のリストのアドレス」を持っているにすぎないのです。
ここを構造体と考えるからややこしいのです、たぶん。
まあこのへんで詰まっていると永遠にリスト構造は完成しないのでわからなくてもひとまず飲み込んで少しずつ進めていきましょう。
先頭と末尾の目印
数珠の先頭と末尾のアドレスを保存するポインタ変数を用意します。
/*先頭*/ struct LIST* head; /*末尾*/ struct LIST* tail;
この変数の値を目印に先頭や末尾のリスト追加・削除などを行っていきます。
無効データを表す「NULL」
リストが空の状態、つまり先ほどの「*head,*tail」に何もデータが入ってない時の目印、それとリストの末尾の目印、両方に「NULL」を使用します。
ここで「あれ？末尾はtailって言っていたような・・・？」って思いますよね。
ここが少しややこしいのですが、末尾にリストを追加、削除する時の場合などはこの末尾を表す「tail」を別に用意した方がプログラムが簡潔になるのでそのようにしております。
このあたりはプログラムを実際に見た方がわかりやすいと思われます。
ではこれらを目印にリストの追加、削除、表示などをしていきます。
最小限のリストプログラム
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct LIST{
char name[128];
char num[128];
struct LIST* next;
};
struct LIST* head;
struct LIST* tail;
void add_tail(struct LIST );
void disp_list(void);
void free_list(void);
int main(){
struct LIST input_data;
strcpy(input_data.name,"tanaka");
strcpy(input_data.num,"09011111111");
add_tail(input_data);
strcpy(input_data.name,"saitou");
strcpy(input_data.num,"09022222222");
add_tail(input_data);
strcpy(input_data.name,"watanabe");
strcpy(input_data.num,"09033333333");
add_tail(input_data);
disp_list();
free_list();
return 0;
}
void add_tail(struct LIST input_data){
struct LIST* p;
p = (struct LIST*)malloc(sizeof(struct LIST));
if(tail == NULL){
head = p;
}
else{
tail->next = p;
}
tail = p;
*tail = input_data;
tail->next = NULL;
}
void disp_list(){
struct LIST* p;
int n = 0;
p = head;
printf("\n名前 電話番号\n");
while(p != NULL){
printf("%d:%s %s\n",n + 1,p->name,p->num);
n++;
p = p->next;
}
}
void free_list(){
struct LIST* p;
struct LIST* p2;
p = head;
while(p != NULL){
p2 = p->next;
free(p);
p = p2;
}
head = NULL;
tail = NULL;
}
■実行結果■
いきなりプログラムがどっと増えてしまいましたが、リスト構造はある程度必要なプログラムがどうしてもセットになってしまうのでご了承ください。
末尾に追加
まずはリストを末尾に追加する関数を作ります。
void add_tail(struct LIST input_data){
struct LIST* p;
p = (struct LIST*)malloc(sizeof(struct LIST));
if(tail == NULL){
head = p;
}
else{
tail->next = p;
}
tail = p;
*tail = input_data;
tail->next = NULL;
}
リストを末尾に追加する「add_tail()」になります。
内容を見てみましょう。
まずは一時的に用意した変数「struct LIST* p」に「malloc()」を使ってメモリを確保します。
p = (struct LIST*)malloc(sizeof(struct LIST));
これをもとにリストを末尾に追加していくのですがリストが空の時とそうではない時とで少し処理が分かれます。
リストが空の時
リストが空の時「if(tail == NULL)」の時の処理は
if(tail == NULL){
head = p;
}
tail = p;
と言うように「head,tail」両方に同じアドレスを設定するような感じになります。
この時のリストは一つしかないのでそこが先頭であり末尾でもあるワケです。
リストが一つ以上ある時
次にリストが一つ以上ある場合です。
先ほどの「if」文の「else」部分ですね。
else{
tail->next = p;
}
この時は「tail」の表す場所がそのリストの末尾にあたるので、その次「tail->next」に新しく確保したメモリを保存、
そして同時にそこが新たな末尾になるので
tail = p;
末尾として設定しなおします。
そして引数として受け取ったデータを保存
*tail = input_data;
最後にリストを辿る時の末尾の目印「NULL」を設定すれば
tail->next = NULL;
末尾に追加する関数は完成です。
広告
データを表示
それでは実際にリストの末尾を示す「NULL」を目印にリストを辿ってみましょう！
リスト内のデータを表示する関数「disp_list()」になります。
void disp_list(){
struct LIST* p;
int n = 0;
p = head;
printf("\n名前 電話番号\n");
while(p != NULL){
printf("%d:%s %s\n",n + 1,p->name,p->num);
n++;
p = p->next;
}
}
リストを辿る部分だけを抜き出してみます。
void disp_list(){
struct LIST* p;
p = head;
while(p != NULL){
p = p->next;
}
}
リスト構造プログラムの象徴的部分ですね。
一時的にアドレスを保存する変数「struct LIST* p」を用意してそこに先頭アドレスを保存、
そのアドレスがリストの末尾を示す「NULL」ではない間
while(p != NULL){
}
ひたすらその時のリストが保存している次のリストのアドレスと
p = p->next;
入れ替えます。
こうして「NULL」が来るまでひたすらリストを辿る事ができるというワケですね。
メモリ解放
同じようなやり方でメモリも解放していきます。
メモリをすべて解放する「free_list()」になります。
void free_list(){
struct LIST* p;
struct LIST* p2;
p = head;
while(p != NULL){
p2 = p->next;
free(p);
p = p2;
}
head = NULL;
tail = NULL;
}
メモリは解放された瞬間に構造体のカタチを成さなくなるのでその構造体のもっている次のリストへのアドレスってもんがわからなくなってしまいます。
なので、その前にそのリストが持っている次のアドレスの値を退避させながらメモリを解放していきます。
リストの基本
ざっと説明しましたが、ここまでが単方向リストの基本プログラムになります。
動的にメモリを確保しながらリストを作り上げていくので、最後メモリを解放するまでがセットのプログラムになるわけですね！
あとは今使ったような「○○を目印にリストを辿る」、「アドレスをつなぎかえる」、「無効データNULLを設定」などを駆使して他の機能も実現していきます。
いくつか作ってみたので続けて見てみましょう。
先頭に追加
void add_head(struct LIST input_data){
struct LIST* p;
if(head != NULL){
p = (struct LIST*)malloc(sizeof(struct LIST));
*p = input_data;
p->next = head;
head = p;
}
else{
add_tail(input_data);
}
}
先頭にリストを追加する「add_head()」です。
リストが空の時、末尾「NULL」の設定などに先ほど作った関数「add_tail()」を使うので、その後にこちらの関数は作らなければいけません。
リストが空の時
if(head != NULL){
}
else{
add_tail(input_data);
}
先ほども言いましたとおりそのまま「add_tail()」にデータを渡すだけです。
先頭に追加
if(head != NULL){
p = (struct LIST*)malloc(sizeof(struct LIST));
*p = input_data;
p->next = head;
head = p;
}
新しくメモリを確保、そのメモリの次のアドレスに今までの先頭「head」を設定、そして先頭「head」をその新しく確保したメモリのアドレスに置き換えれば先頭に追加する関数は完成です。
先頭を削除
void del_head(){
struct LIST* p;
if(head != NULL){
p = head->next;
free(head);
head = p;
if(head == NULL){
tail = NULL;
}
}
}
先頭を削除する「del_head()」です。
いきなり先頭部分のアドレスを消去してしまうとその先頭部分が持っている次のアドレスがわからなくなってしまうので先にその先頭部分が持っている次のアドレスを退避させます。
一時的にアドレスを保存する変数を用意して、
struct LIST* p;
そこに先頭の次のアドレスを
p = head->next;
保存すれば退避完了ですね。
あとは先頭を削除、新しい先頭を設定すれば完了です。
free(head); head = p;
もし先頭部分が「NULL」の場合はリストが空の状態になるので末尾の「tail」も
if(head == NULL){
tail = NULL;
}
というように「NULL」を設定してあげます。
末尾を削除
void del_tail(){
struct LIST* p;
if(tail != NULL){
p = head;
while(p != NULL){
if(p->next == tail){
p->next = NULL;
break;
}
p = p->next;
}
free(tail);
tail = p;
if(tail == NULL){
head = NULL;
}
}
}
末尾を削除する「del_tail()」になります。
末尾の削除は先頭の削除より少しだけ複雑になります。
末尾の部分に「NULL」を設定しなおすにあたりその場所を調べる必要があります。
調べる手順ですが、「NULL」までアドレスを辿っていくのはいつも通り。
while(p != NULL){
p = p->next;
}
その途中末尾を示す「tail」のトコロまで来たら辿っていくのを止めます。
if(p->next == tail){
p->next = NULL;
break;
}
「if(p->next == tail)」が現在の末尾ですね。
後はここを「NULL」に設定しなおして、「tail」のメモリを解放、新たな「tail」を設定しなおせば完了です。
リストの総数をカウント
int get_count(){
struct LIST* p;
int n = 0;
if(head != NULL){
p = head;
while (p != NULL){
n++;
p = p->next;
}
return n;
}
else{
return n;
}
}
リストの総数をカウントする「get_count()」です。
リストが空でなければリストの「NULL」までの個数を一つ一つカウントしてその総数を返します。
指定場所のリストを置換
void replace_at(struct LIST input_data,int n){
struct LIST* p;
struct LIST* p2;
int count = 0;
if(head != NULL && n >= 1 && n <= get_count()){
p = head;
while(p != NULL){
if(count == n - 1){
p2 = p->next;
*p = input_data;
p->next = p2;
break;
}
else{
count++;
p = p->next;
}
}
}
}
指定した場所のリストを置き換える「replace_at()」です。
存在しないリスト番号を指定されるなど不正な値を受け取らないように前に作った「get_count()」をエラー対策に使っております。
指定された場所までリストを辿りその場所のリストを置き換えます。
リストを置き換える際に、まるごとリストをコピーするようなカタチをとっているのでその前に次のアドレスの情報を避難させております。
指定場所のリストを削除
void del_at(int n){
struct LIST* p;
struct LIST* p2;
int count = 0;
if(head != NULL && n >= 1 && n <= get_count()){
if(n == 1){
del_head();
}
else{
p = head;
p2 = head->next;
while(p2 != NULL){
if(count == n - 2){
p->next = p2->next;
free(p2);
break;
}
else{
count++;
p = p2;
p2 = p2->next;
}
}
}
}
}
指定した場所のリストを削除する「del_at()」です。
１番目のリストの削除を指定された場合は先頭の削除と同じ意味になるので「del_head()」を呼び出します。
それ以降は２つのポインタ変数に先頭「head」とその次の「head->next」のアドレスを保存、指定された場所までそれぞれ移動していきます。
p = head;
p2 = head->next;
while(p2 != NULL){
if(count == n - 2){
break;
}
else{
count++;
p = p2;
p2 = p2->next;
}
}
指定された場所までたどり着いたら
if(count == n - 2){
p->next = p2->next;
free(p2);
break;
}
間を飛ばすようなカタチで「next」同士をつなぎ合わせます。
その飛ばした間が削除すべきリストになるのでそこを解放すれば完了です。
「if(count == n - 2)」の場所が指定場所になるトコロに注意です。
指定場所にリストを挿入
void insert_at(struct LIST input_data,int n){
struct LIST* p;
struct LIST* p2;
int count = 0;
if(head != NULL && n >= 1 && n <= get_count()){
if(n == 1){
add_head(input_data);
}
else{
p = head;
while(p != NULL){
if(count == n - 2){
p2 = (struct LIST*)malloc(sizeof(struct LIST));
*p2 = input_data;
p2->next = p->next;
p->next = p2;
break;
}
else{
count++;
p = p->next;
}
}
}
}
}
指定した場所にリストを挿入する「insert_at()」です。
１番目にリストを挿入する場合は先頭の挿入と同じ意味になるので「add_head()」を呼び出します。
それ以降は先頭のアドレスを保存、指定された場所までリストを辿っていきます。
p = head;
while(p != NULL){
if(count == n - 2){
break;
}
else{
count++;
p = p->next;
}
}
指定された場所までたどり着いたら
p2 = (struct LIST*)malloc(sizeof(struct LIST)); *p2 = input_data; p2->next = p->next; p->next = p2;
もう一つ用意したポインタ変数に新しくリストを確保
そこに受け取ったデータを入れてその新しく確保したリストの「next」に前までの「next」を代入、前までの「next」を新しく確保したリストにすれば挿入は完了です。
もちろんこれ以外にもいくつか考えられると思いますのでいろいろと工夫してみてください。
広告
↓発売日：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日↓
 |
新品価格 |
