さくっりデータ構造_01　//配列とリスト

ポホヨラの村人A

2022年6月10日 22:09

アルゴリズムの基本となるデータ構造をサクッと説明しよう企画第一段

案外筆者も忘れてる部分が多いので、多々間違えるかと思いますが大目に見てもらえると助かります。

本記事はC言語をある程度理解できている事を前提としています。ご注意ください。

配列

と、いう訳でデータ構造の基礎中の基礎配列です。
配列とは、あるデータ型をまとめて扱う方法の一つですね。

この配列の配列を作ると２次元配列、２次元配列の配列を作ると三次元配列として扱えるデータの量が増えていくわけですね。

この配列には、メリットどデメリットがあります。

メリット：配列にアクセスする時間が短い
例えばのある点iにアクセスしようとしたとき、次のように表記します

array[i]

i=2として、上記の例の配列にアクセスすると、66という数字が出てきます。

->array[] = {33, 4, 66, 8, 99}
->i=2
->array[i]
66

デメリット：メモリの確保量が静的で大きくなり易い
事前にどれだけデータを保存したい場合、この配列では少し困ったことになりまよね。例えば事前に5個分のメモリを事前に作っておいたものの、いざデータを入れる段階で6個データが来ると困ってしまいす。

->array[5];
->array = {0, 1, 2, 3, 4, 5}
Error!!
//array[0]=0,array[1]=1, array[2]=2,array[3]=3,array[4]=4
//array[5]は確保していない！！

と、事前にデータの為にメモリを確保していなくても扱える仕組みが必要になってくるわけです。

因みに、リストはちょうど配列と逆の特徴をもちますね。

メリット：予めメモリを確保する必要がない
これは特に、グラフを表現するときには配列と顕著にさがでてくる点ですね。配列の場合確保メモリはメモリが頂点の二乗に、リストの場合は辺の数になります。何となく頂点より、辺の数の方が少なくなりそうな感じはするかと思います。
まあ、完全グラフで頂点の数をnとすると、辺はn(n-1)/2ぐらいなので、nの二乗よりは小さくなる気はします。（超適当）

デメリット:データにアクセスするのにそこそこ時間が掛かる
リストの場合は、頭や尻尾から順次データを見て行く都合上どうしても時間がかかってしまいます。最悪では、そのリストの長さ分の時間がかかってしまいますね。

for(int i = 0; i <　List.size(); i++){
    Node = Node->next;
    if(Node == nil){
        printf("最後尾に到達\n");
        return;
    }
}

みたいな感じ。まあ、ループしてる点から見て、そこそこ時間はかかりそうだな、とは思えますね。あ、因みにこのように端っこから片っ端に調べる方法を線形探査といいます。見ての通りあんまり良い探査方法ではありませんが、実装するのはそこそこ楽です。

ではでは、次にリストの操作方法について見ていきたいと思います。

挿入

何時もの奴ですね。
１番目のように上にリストが並んでいます。挿入したい番目の下に新しいデータがあると思ってくださいな。
この新しいデータのポインタに目的のデータの次のポインタを設定します。つまり、２番目ですね。
最後に、重複しているポインタを修正して、新しく挿入したいデータのポインタを入れることで挿入操作が終了します。３番目の図ですね。
はい、我ながら何を言っているのかさっぱり分かりませんね。ぶっちゃけ、上記の図を見て頂いたほうが速いと思います。コードで書くと多分次の感じです。

List *node = top;

for(int i = 0; i < address; i++){
    PreNode = PreNode->next;
    if(PreNode == nil){
        printf("最後尾に到達\n");
        return;
    }
}

List *addNode;
addNode->next = PreNode->next;
PreNode->next = addNode;

多分こんな感じじゃないかなぁ……。あ、因みにＮＵＬＬの代わりにＮＵＬＬを表すデータＮＩＬを想定しています。こんな感じで、データがすっぽ抜けたり異常を起こさないように端っこにいる特殊データを番兵と呼ぶそうです。

削除

はい、またまた何時もの図でございます。

こちらは比較的に簡単ですね。
削除したいデータの一つ前にポインタに、削除したいデータの次のデータのアドレスを入れます。
次に削除したいデータ内のポインタを削除すればこれで削除の操作は終了です。

List *node = top;

for(int i = 0; i < address - 1; i++){
    PreNode = PreNode->next;
    if(PreNode == nil){
        printf("最後尾に到達\n");
        return;
    }
}

if(PreNode == top){
    top = PreNode->next;
    delete PreNode;
}else{
    List *node = PreNode->next;
    PreNode->next = node->next;
    delete node;
}

こんな感じだったらいいなぁ……（相変わらず自信の無い人）

コード

と、いう訳で実装するとこんな感じになるかと思われます。

#include<iostream>

class LinkedList {
private:
	class Node {
	public:
		int val;
		Node* next;
	};

	Node* nil;
	Node* top;
public:

	LinkedList() {
		nil = new Node;
		nil->next = nil;
		nil->val = NULL;
		top = nil;
	}

	~LinkedList() {
		clear();
		delete nil;
	}

	void addList(int val) {
		Node* node, * tmp;
		node = new Node;
		node->val = val;
		node->next = nil;
		if (top == nil) {
			top = node;
		}
		else {
			for (tmp = top; tmp->next != nil; tmp = tmp->next) {}
			tmp->next = node;
		}
	}

	void insertNode(int val, int address) {
		if (address < 0) {
			printf("不正なアクセスです\n");
			return;
		}

		Node* nextNode = top;

		for (int i = 0; i < address - 1; i++) {
			nextNode = nextNode->next;
			if (nextNode == nil) {
				printf("存在しない番号にアクセスしようとしています\n");
				return;
			}
		}

		Node* node = new Node;
		node->val = val;

		if (address != 0) {
			node->next = nextNode->next;
			nextNode->next = node;
		}
		else {
			node->next = top;
			top = node;
		}

	}

	void deleteNode(int address) {
		if (address < 0) {
			printf("不正なアクセスです\n");
			return;
		}

		Node* node = top;

		for (int i = 0; i < address - 1; i++) {
			node = node->next;
			if (node == nil) {
				printf("存在しない番号にアクセスしようとしています\n");
				return;
			}
		}

		if (address != 0) {
			Node* nextNode = node->next;
			node->next = nextNode->next;
			nextNode->val = NULL;
			delete nextNode;
		} else {
			top = node->next;
			delete node;
		}
	}

	void print() {
		Node* tmp;
		for (tmp = top; tmp != nil; tmp = tmp->next) {
			std::cout << tmp->val << " ";
		}

		std::cout << std::endl;
	}

	void clear() {
		Node* tmp, * pretmp;
		for (tmp = top; tmp != nil;) {
			pretmp = tmp;
			tmp = tmp->next;
			delete pretmp;
		}
		top = nil;
	}

};

int main() {
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	LinkedList list;
	list.addList(1);
	list.addList(2);
	list.insertNode(9, 1);
	list.print();
	list.insertNode(10, 0);
	list.addList(3);
	list.print();
	list.clear();
	list.addList(5);
	list.addList(4);
	list.addList(6);
	list.print();
	list.deleteNode(1);
	list.print();
	list.deleteNode(0);
	list.print();
	return 0;
}

一応動作は確認しましたが、あんまり自信は無いのでご自分でご確認の程をお願いいたします（他力本願）
あ、あと命名規則が超適当です。い、いや違うのじゃ、書いてるうちに自分での何書いてるのかだんだん分からんくなってきたなんて事なんて無いのじゃ。
いや、スパゲッティーですみません……

次回

さくっりデータ構造_01 //配列とリスト

配列

リスト

挿入

削除

コード

いいなと思ったら応援しよう！

さくっりデータ構造_01　//配列とリスト