さまざまなデータ構造をC++で書いてみる(1)

データ構造

こんにちは。

1年くらい前に取り上げたデータ構造では,プログラムをJavaとPythonで書いていました。ほとんど同じプログラムをC++に直してみようと思います。

片方向リスト用のノードをC++で書いてみる

以前データ構造を取り上げたときと同じ流れで進めます。

重複する内容はリンクをはっておくことにします。

それでは早速プログラムを載せます。

はじめにヘッダファイルです。

もしコピペして使う場合には,ファイル名は MyNode.h にしておいてください。

#ifndef _MYNODE_H_
#define _MYNODE_H_
#endif
#include <string>
using namespace std;
    
class MyNode {
public:
	MyNode();
	string getElement();
	void setElement(string);
	MyNode* getNext();
	void setNext(MyNode*);
	string to_String();
private:
	string element;
	MyNode* next;
};

次にクラス定義のファイルになります。

ファイル名は mynode.cpp にしておいてください。

#include "MyNode.h"
#include <string>
using namespace std;
    
MyNode::MyNode()
{
	this->next = nullptr;
}
    
string MyNode::getElement(void)
{
	return this->element;
}
    
void MyNode::setElement(string element)
{
	this->element = element;
}
    
MyNode* MyNode::getNext()
{
	return this->next;
}
    
void MyNode::setNext(MyNode* next)
{
	this->next = next;
}
    
string MyNode::to_String()
{
	string result = "[" + this->element + "]";
	if (this->next != nullptr) {
		result += " → ";
	}
	return result;
}

連結リストをC++で書いてみる

以前の投稿内容です。

これをC++で書きます。

ヘッダファイルのファイル名は mylinkedlist.h にしておいてください。

#include"MyNode.h"
#ifndef _MYLINKEDLIST_H_
#define _MYLINKEDLIST_H_
#endif
#include <string>
using namespace std;
    
class MyLinkedList
{
public:
	MyLinkedList();
	int size();
	void add(int, string);
	void add(string);
	void set(int, string);
	string get(int);
	void remove(int);
	string toString();
    
private:
	MyNode* head;
	MyNode* getNthNode(int);
};

次にクラス定義のファイルになります。

ファイル名は mylinkedlist.cpp にしておいてください。

#include "MyLinkedList.h"
#include<string>
    
MyLinkedList::MyLinkedList()
{
	this->head = nullptr;
}
    
int MyLinkedList::size()
{
	int size = 0;
	MyNode* tmp = this->head;
	while (tmp != nullptr) {
		tmp = tmp->getNext();
		size++;
	}
	return size;
}
    
void MyLinkedList::add(int index, string element)
{
	MyNode* n = new MyNode();
	n->setElement(element);
	if (index == 0) {
		n->setNext(this->head);
		this->head = n;
		return;
	}
	MyNode* tmp = this->getNthNode(index - 1);
	n->setNext(tmp->getNext());
	tmp->setNext(n);
}
    
void MyLinkedList::add(string element)
{
	this->add(this->size(), element);
}
    
void MyLinkedList::set(int index, string element)
{
	this->getNthNode(index)->setElement(element);
}
    
string MyLinkedList::get(int index)
{
	return this->getNthNode(index)->getElement();
}
    
void MyLinkedList::remove(int index)
{
	if (index == 0) {
		this->head = this->head->getNext();
		return;
	}
	MyNode* tmp = this->getNthNode(index - 1);
	tmp->setNext(tmp->getNext()->getNext());
}
    
string MyLinkedList::toString()
{
	string result = "";
	for (int i = 0; i < this->size(); i++) {
		result += this->getNthNode(i)->to_String();
	}
	return result;
}
    
MyNode* MyLinkedList::getNthNode(int index)
{
	MyNode* result = this->head;
	for (int i = 0; i < index; i++) {
		result = result->getNext();
	}
	return result;
}

それでは,連結リストの動作確認をしてみます。

そのためのプログラムです。このプログラムのファイル名は任意で大丈夫です。

#include<iostream>
#include"MyLinkedList.h"
using namespace std;
    
int main() {
	MyLinkedList* l = new MyLinkedList();
    
	l->add("青森県");
	cout << l->toString() << endl;
    
	l->add("みやぎ県");
	cout << l->toString() << endl;
    
	l->add(0, "北海道");
	cout << l->toString() << endl;
    
	l->add(2, "岩手県");
	cout << l->toString() << endl;
    
	l->add("秋田県");
	cout << l->toString() << endl;
    
	l->set(3, "宮城県");
	cout << l->toString() << endl;
    
	cout << l->get(1) << endl;
	l->remove(1);
	cout << l->toString() << endl;
    
	l->remove(0);
	cout << l->toString() << endl;
}

それでは,実行結果です。

[青森県]
[青森県] → [みやぎ県]
[北海道] → [青森県] → [みやぎ県]
[北海道] → [青森県] → [岩手県] → [みやぎ県]
[北海道] → [青森県] → [岩手県] → [みやぎ県] → [秋田県]
[北海道] → [青森県] → [岩手県] → [宮城県] → [秋田県]
青森県
[北海道] → [岩手県] → [宮城県] → [秋田県]
[岩手県] → [宮城県] → [秋田県]

今回はこれでおしまいにします。それではまた。

Posted by 春日井 優