メインコンテンツへスキップ
見出し画像

データ構造と使用例をまとめた!

    こんにちは「つけらっとゲームス」プログラム担当のとちです。
    今回はデータ構造のお話をしようと思います。

    データ構造は、情報(システム)関係の学科で学ぶ高校生、大学生、専門学校生にとって最初のあたりに出てくる内容でもあり、基本情報技術者試験の範囲にもありますので、学生さんの復習に使えると思います!

    もちろん個人や小規模なインディーゲーム開発において、覚えておくと便利なデータ構造もありますし、使用例(サンプルコード)としても使えます!

    特に独学でゲーム開発をしている方は、雰囲気で覚えている可能性があるので、頭の整理をする際にご利用くださいね!



    データ構造って何だ?

    プログラムでは様々なデータを使います。

    単純な変数であっても、整数型、文字列型、浮動小数点型など色々なデータ型がありますよね。それと同様にデータ構造についても色々な構造があったりします。

    ※そもそも変数について「自信ない…」いう方にはコチラがオススメです。

    普段からプログラムに触れている人は、わざわざデータ構造が何なのかを細かく分類して使うことはあんまり無いでしょう。しかし、データ管理の際に適したデータ構造を自然と選択していると思います。

    これを言葉で説明するなら、以下のようなデータ構造があります。

    ・配列
    ・リスト
    ・レコード
    ・スタック
    ・キュー
    ・木構造

    まずはこれらがどんな「カタチ」をしているのか、まとめますね。

    配列型

    複数のデータ型から構成されるデータ構造です。
    「はい、意味わからん!」なので図表にします。

    あるクラスの、ある科目のテストの点数を配列でデータ化します。
    ちなみに30人の生徒がいる場合は、基本的に添え字が0から始まるので29までの30個の要素が必要となります。

    画像

    配列は基本情報技術者試験でもよく出てきます。ゲーム開発においても、ちょっとしたデータ管理なら配列で対応できるので覚えると幸せになれます。

    リスト型

    「リスト」という表現をすると配列もリストといえますがプログラム関連で扱う場合は、順序付けられたデータの集合体でデータ部とポインタ部に分かれているデータ構造を指します。

    また、配列と厳密に区別する為に「連結リスト」とか「リンクリスト」とも言います。でも面倒臭いのでリストって呼んじゃいます。

    図表で説明するとこんな感じになります。
    青森県内の市をデータ化したリストです。

    画像

    スタート番号が(1)なので最初のデータは「青森市」となります。
    青森市のポインタは4なので、次は(4)の「弘前市」となります。
    弘前市のポインタは3なので、次は(3)の「八戸市」となります。

    これだと単方向にしか次データを探せません。
    ということで、双方向リストというものがあります。

    画像

    双方向リストはポインタ部が2つ必要となります。
    前ポインタを利用することで、終端から始端へデータを戻っていくことも可能となります!

    もう少し考え方を進めて下の図表の様に「始端の前ポインタに終端」を「終端の次ポインタに始端」をいれるとループも可能になります。
    これを循環リストといいます。

    画像

    レコード型

    お互いに関連するデータをひとつにまとめたモノをレコード型といいます。
    配列やリストをまとめると、より効率的な処理が可能となります。

    つけらっとゲームスで開発しているゲーム規模であれば、このレコード型くらいで十分に対応できています。

    ということで、わたし個人では最もよく使うデータ構造となってます。

    例としては「勉強したのに作れない」を解決したい!で使用した以下のようなデータとなります。

    ただし、その記事中にはサンプルコードがないので、これはどこか別の記事で説明した方が良いかもしれませんねぇ…

    画像

    スタック型・キュー型

    スタックは後入れ先出しのデータ構造です。
    スタックにデータ格納することをプッシュ、データを取り出すことをポップといいます。

    これ、何に使われるのかというと…いまパッと思いつくのが各種ツール類でミスったときに「Ctrl+Z」でひとつ戻す機能がありますよね。あれです。

    これに対し、キューは先入れ先出しのデータ構造です。
    あんまり喋った記憶がないんですけど、キューにデータ格納することをエンキュー、データを取り出すことをデキューっていいます。

    (普段はキューに入れるとか、キューに入ってたとか、そういう言い方してるんですよね、わたしも勉強になりました!)

    何らかの処理をしたい時に前作業が残っている場合、やりたい処理を覚えておいて、残っている作業が終わり次第やりたい処理をするってヤツです。
    文章にすると、ワケわからん。

    銀行などの窓口で整理番号を貰って、その番号が電光掲示板に表示されるまで待っているシステムがそれです。

    もっと単純な例があったわ!
    印刷中のプリンターに、次の文書を印刷させようとするとキューに印刷データが貯まっていきますよね。それです!

    画像

    木構造

    階層でデータを持つのが木構造です。
    身近な例でいうと、ディレクトリ(フォルダ)管理がこれです。

    ルートディレクトリの下に更にディレクトリが連なっていて、その中には必要なファイル類が入っています。ほら、木構造だ!

    画像

    木構造は並び替え(ソート)処理にも使います。
    冒頭でも述べた通り、そのあたりが基本情報技術者試験に出てきたりするので覚えておくと良いでしょう。

    木構造を使った並び替えアルゴリズムに関しては、いつか別の記事で解説できたらいいなーと思っています。


    Unity(c#)でListを使う!

    以前、配列について詳しく解説する記事を投稿していますが、

    上の記事は単純な配列(Array)のサンプルを用いており「List」については触れていないので、ここで説明しますね。ただ、配列について「自信がない…」という方は、先に上の記事を読むと理解しやすいです。

    リスト? 配列?

    では、改めてc#のListについて説明しましょう。

    データ構造の分類の中に「リスト」があるので混乱しますが、c#のListは全く無関係ではないものの、厳密にはデータ構造における「リスト」とは違うものです。Listは配列の仲間です。

    データ構造の分類におけるリストの例は後述のLinkedListで説明します。

    本当混乱するわっ! 文章が無駄に長くなるっ! やめてっ!

    説明したいけど説明の仕方に悩む、ついさっきのわたしの発言より引用

    Listは動的配列です。動的配列って時点で言葉が難しいですね。
    言い方を変えると、基本的にListは可変長、Arrayは固定長です。

    int[]     testTensuA = new int[5];			// 数値型の配列(Array)定義(5教科)
    List<int> testTensuL = new List<int>()		// 数値型のリスト(List)定義

    テスト点数を配列で管理するとしましょう。
    1行目の配列(Array)では5つの要素があると定義されています。
    2行目のListでは何個の要素があるか定義していません。

    中学校の中間テストは5教科ですが、期末テストだと音楽や保健体育なども追加される可能性がありますよね。配列(Array)の場合は再定義する必要がありますが、Listは要素を追加できるという違いがあります。

    シンプルな使い方

    では、テストの点数がわかったのでリストに入れます。

    画像
    void simple_int_Test()
    {
    	List<int> testTensu  = new List<int>();			// 数値型のリスト定義
    	testTensu.Add(92);								// リストに国語の点数を入れる
    	testTensu.Add(84);								//   〃  数学   〃
    	testTensu.Add(78);								//   〃  理科   〃
    	testTensu.Add(85);								//   〃  社会   〃
    	testTensu.Add(73);								//   〃  英語   〃
    
    	Debug.Log("国語の点数:" + testTensu[0]);		// 国語の点数をコンソールに表示		(国語はリストの0番目に入れた!)
    	Debug.Log("リスト長さ:" + testTensu.Count);		// リストの長さをコンソールに表示	(リストの要素数は何個あるか?)
    }

    上から3行目、testTensuという名前のリストを宣言しています。
    続いて4行目、testTensuに92をAdd(追加)しています。
    5行目以下も同様に数字をAdd(追加)しているのがわかりますね。

    国語の点数を知りたい時は、testTensuの最初に追加したので、testTensu[0]を表示すると中身がわかります!数学だったら[1]ですし、理科だったら[2]となります。
    ちなみにtestTensuの長さを知りたい時はtestTensu.Countです。

    上記プログラムを実行するとコンソールには以下のように表示されます。

    画像

    配列(Array)をListに入れて全件表示

    先程のコードでは1教科に対し1行を使って追加していました。
    次のサンプルコードでは配列に各教科の点数をまとめてます。

    testTensuというリストに対して、testInDataという配列(Array)を入れるには、testTensu.AddRange(testInData)と書きます。便利ですね。

    void simple_int_Test_inArrayData()
    {
    	string    dispLogTx  = "";								// 表示用変数定義
    	List<int> testTensu  = new List<int>();					// 数値型のリスト定義
    	int[]     testInData = new int[5]{92,84,78,85,73};		// 数値型の配列定義(国語,数学,理科,社会,英語)の点数
    	testTensu.AddRange(testInData);							// 数値型の配列をリストに追加する
    															//
    	for(int ix = 0; ix < testTensu.Count; ix++)				// ■リスト長までループする
    	{														// │
    		dispLogTx = dispLogTx + testTensu[ix] + " / ";		// └ 表示用変数に取得した点数を追記していく
    	}														//
    	Debug.Log(dispLogTx);									// 表示用変数をコンソール表示
    }

    その後のfor文では要素番号(添え字)がリストの長さtestTensu.Countまでループしています。ループ中に要素の中身を表示用の変数dispLogTxに追記していますね。

    これなら全教科が1行のデバッグメッセージで返答されて見やすい!

    画像

    データを削除したい

    先程までのサンプルコードでは点数(数値)を扱っていましたが、もちろん文字列だって扱えます。次は不要なデータの削除をしてみます。

    void string_Add_Remove()
    {
    	string DispLogTx    = "";												// 表示用変数定義
        List<string> fruits = new List<string>(){"リンゴ","ミカン","スイカ"};		// 文字列型のリスト定義と初期化
        fruits.Add("バナナ");													// 要素の追加 バナナ
        fruits.Add("ミカン");													// 要素の追加 ミカン
        fruits.Remove("ミカン");													// 要素の削除(先に見つけたミカンを削除する)
    																			//
        foreach (string ListTx in fruits)										// ■リストの要素を出力するループ
        {																		// │
            DispLogTx += ListTx + " / ";										// └ 表示用変数にリストの要素を追加していく
        }																		//
        Debug.Log(DispLogTx);													// 表示用変数をコンソールに表示
    }

    上から4行目、リストの宣言と同時に初期値を入れる方法です。
    この方法でも1行でリストの中身に各データを入れることができます。
    リスト名はfruitsで、現時点ではリンゴ、ミカン、スイカが入っています。

    5行目でバナナを追加。リンゴ、ミカン、スイカ、バナナになります。
    6行目でミカンを追加。リンゴ、ミカン、スイカ、バナナ、ミカンです。

    7行目でミカンを削除。すると先の方にあるミカンを削除します。
    削除する時は「リスト名.Remove(消したいもの)」だとわかりますね。
    結果、コンソールを見ると正しく動いているようです。

    画像

    このサンプルコードではfor文ではなくforeach文を使っています。
    リストの中身を変数ListTxに入れて、それを表示用変数DispLogTxに追記しています。この書き方がわかりやすい方はこちらを使うと良いでしょう!

    同じデータを全部削除したい

    先程は、リストの先に入っていたミカンを削除しましたが、ミカン全部を消したい時はこんな書き方をするといいみたいです!

    fruits.RemoveAll(str => str == "ミカン");	// 要素の削除(ミカンだったら全て削除する)

    リストfruitsの中身を変数strにいれて、strがミカンだったら消してます。

    画像

    要素番号で消したい

    リストの中身が判明していれば、ここまでのように果物の名前を指定して削除することもできますが、名前ではなく要素番号(添え字)の場所を消したいこともあるでしょう。その場合は以下のように…

    fruits.RemoveAt(1);			// 要素の削除(indexの1番目、スイカを削除する)

    添え字(index)は基本的に0から始まるので、0はリンゴ、1がスイカ、2がバナナでした。指定した添え字が1なのでスイカが消えたら正解!

    画像

    正しく動いているようです!


    Unity(c#)でLinkedListを使う!

    データ構造的にリスト型と、Unity(c#)で使うListとは厳密には違うよって話をしました。これマジで混乱するんで、ここでもう一度と書きますね。

    データ構造型のリスト型は「連結リスト型」または「リンクリスト型」と書いたら混乱しないのに、なんでリスト型に省略しちゃったんだよ!!

    説明したいけど説明の仕方に悩む、ついさっきのわたしの発言より引用

    というわけでUnity(c#)で説明するなら!
    LinkedListが「【連結】リスト型」です!

    データ構造で言う「リスト型」ではポインタが設定されていて、次のデータがどれなのか(または、前のデータがどれなのか)がデータの中で判断できるようになっています。LinkedListも順番をノード(節)で判断できます。

    シンプルな使い方

    以下のサンプルコードを見てください。
    先程までListを定義していた箇所がLinkedListに代わっているのがわかりますね。また要素を追加する際にはAddではなく、AddLast、AddFirstが使われています。

    void LinkedListTest_1()
    {
    	string DispLogTx         = "";							// 表示用変数定義
    	LinkedList<string> foods = new LinkedList<string>();	// 文字列型のリンクドリスト定義
    															//
        foods.AddLast("そば");									// foodsの最後に追加
        foods.AddLast("うどん");									// foodsの最後に追加
        foods.AddFirst("寿司");									// foodsの先頭に追加
    	foods.AddLast("牛丼");									// foodsの最後に追加
    															//
        foreach (string ListTx in foods)						// ■foodsの要素を出力するループ
        {														// │
            DispLogTx += ListTx + " / ";						// └ 表示用変数にfoodsの中身を追加していく
        }														//
    	Debug.Log(DispLogTx);									// 表示用変数をコンソールに表示
    }

    その言葉の通り、上記のコードを実行すると以下のようになります。

    画像

    ただし、見た目と内部的なデータの持ち方は異なるかもしれません…
    何故ならデータ構造の分類における「リスト型」すなわち「連結リスト型」はポインタでデータが連結しているからです。

    画像
    画像

    まぁ、プログラムを組む上ではここまで認識する必要はありませんけどね!

    要素の追加

    先程のサンプルコードに以下を追加します。
    中身を見ると新たにLinkedListNodeってのが定義されています。

    inPointというノードが宣言されました。
    ノード inPoint はfoodsというLinkedListの中の"うどん"を探しています。
    つまり ノード inPoint は"うどん"の位置にいます。

    LinkedListNode<string> inPoint = foods.Find("うどん");					// ノード定義 >> foodsから"うどん"を探す
    foods.AddAfter(inPoint,  "そうめん");									// ノード inPointの後に追加
    foods.AddBefore(inPoint, "焼きそば");									// ノード inPointの前に追加
    																		//
    DispLogTx = "";															// 表示用変数を初期化
    foreach (string ListTx in foods)										// ■foodsの要素を出力するループ
    {																		// │
        DispLogTx += ListTx + " / ";										// └ 表示用変数にfoodsの中身を追加していく
    }																		//
    Debug.Log(DispLogTx);													// 表示用変数をコンソールに表示

    先程まではAddLast、AddFirstで要素を追加していましたが、追加したコードではAddAfter、AddBeforeがあります。

    ノード inPoint の後に"そうめん"を追加する場合は AddAfterを、
    ノード inPoint の前に"焼きそば"を追加する場合は AddBeforeです。
    これを実行すると…

    画像

    "うどん"の後に"そうめん"、前に"焼きそば"が表示されました。
    正しく動いていますね。

    要素の削除

    要素を追加できるなら、削除も必要です。
    先程までのサンプルコードに、更に以下のコードを追加します。

    foods.Remove("うどん")では、LinkedListであるfoodsにある"うどん"というデータを消しています。これはわかりやすいですね。

    foods.Remove("うどん");							// 値を指定して削除
    foods.RemoveFirst();							// 先頭を削除
    foods.RemoveLast();								// 最後を削除
    
    DispLogTx = "";									// 表示用変数を初期化
    foreach (string ListTx in foods)				// ■foodsの要素を出力するループ
    {												// │
        DispLogTx += ListTx + " / ";				// └ 表示用変数にfoodsの中身を追加していく
    }												//
    Debug.Log(DispLogTx);							// 表示用変数をコンソールに表示

    その下の行ではfoodsの先頭、その下の行ではfoodsの最後を削除します。
    ということは…

    画像

    まず、"うどん"が消えています。
    先頭と最後にある"寿司"と"牛丼"も消えています!


    LinkedListって何に使えるの?

    ここまで詳しく書いておいてアレですが、これって何に使えるんでしょう?

    Listはデータ管理に便利そうなのはわかるけど、
    LinkedListは先頭や最後を指定してデータを追加、削除できるので…

    そうなんです、リスト型なんだけどスタック、キューに活用できるんです。っていうか、スタック、キューを実現する為には配列かリストが無いと厳しいんですけどね。

    ゲームに使うなら…

    時間制限のあるホラーゲームや脱出ゲームで、インベントリのサイズ容量が決まっていて、しかもプレイヤーを焦らせるためにバックパックにいれた順序をしっかり管理していて、好きなアイテムを取り出せない…スタック型インベントリとか!

    バックパックに穴が開いていて気がついたら先に入れたアイテムがどっかに落ちてるという、キューを使った穴あきインベントリとか!

    ……面白そうですね!!


    おわりに

    データ構造における分類を説明している内に「読む人によってはc#のListをリスト型と連想するかも…これマズくね?」と思ってから記事が2倍に伸びてしまいました。

    c#で使用するListは「リスト型」ではなく「配列型」と言えます。
    もっと厳密に言うとListは「連結リスト型」ではなく「動的配列型」にあたります。

    「じゃぁ、c#でリスト型ってどうすんのよ!?」と気になる人もいるだろう、学生も読んでいるだろうし役に立つ記事にしたい。と思ってたら記事が更に伸びました。

    「連結リスト型」の考え方ならLinkedListを使うといいですよ。

    そして、スタックやキューの考え方をシステム上で実現するには、配列やリストの考え方を理解しないと難しいですよ。

    というお話でした。

    さて、早くも5月が過ぎようとしています。
    近頃、色々なことが重なって少々忙しくなってきました。これまで週一回のペースで投稿してきたnoteは、ストックしておいた話でなんとか続けていますが、こちらからの反応等は遅れ気味になると思います。ご了承ください。

    すっごく長い記事になってしまいましたが、読んだ皆様、本当にお疲れ様でした。また別の記事でお会いしましょう!


    ここからはオススメ記事の紹介です。

    もうちょっと勉強したいなーって方にはコチラがオススメです。
    これらの勉強に使えそうな関連記事は以下にまとめてます!(↓)

    「読むとゲームができるマガジン」もオススメです。
    まずは身近なソフトで作ってみるのもアリかも!
    Excelでもある程度のゲームは作れますよ(↓)

    あなたへのおすすめ