やってしまった！思い込みって怖いな・・・文字列だけじゃないんだよ。ということで総称型に変更の巻
こんにちは。
ここまでC++でデータ構造の簡易版を自分で実装してきました。
次に考えていたことをしようと思ったら・・・
なんと、ノードの要素として文字列しか扱えないようにプログラムを書いてしまっていました。
ということで、今回は1月6日・９日・１２日の３回の投稿に含まれるデータ構造のプログラムについて、要素がstringになっている部分を総称型に直していきます。
JavaとC#では使ったことがあり「ジェネリックス」と呼ぶと思っていたら、C++では「テンプレート」と呼ぶんですね。（どうでもよいのですが、テンプレートのイメージとして今日はたい焼きが思い浮かびました。）
それでは、一気に「ノードの作成」、「連結リスト」、「スタック」、「キュー」のプログラムを直していきます。（2分木は次回にします。）
その際に、コンパイルが通るようにすべての実装をヘッダファイルの中でしています。
ノードの修正
まともな説明は省きます。
プログラムだけですが、ほとんど以前のプログラムと同じです。
ちなみにファイル名は MyNode.h です。
#pragma once
#include<sstream>
using namespace std;
template<typename T>
class MyNode
{
public:
MyNode() {
this->_next = nullptr;
}
T getElement() {
return this->_element;
}
void setElement(T element) {
this->_element = element;
}
MyNode<T>* getNext() {
return this->_next;
}
void setNext(MyNode<T>* next) {
this->_next = next;
}
string to_string() {
ostringstream ss;
ss << "[" << this->_element << "]";
if (this->_next != nullptr) {
ss << " → ";
}
return ss.str();
}
private:
T _element;
MyNode<T>* _next;
};
連結リストの修正
どんどん続けていきます。
次は連結リストです。
ちなみにファイル名は MyLinkedList.h です。
#pragma once
#include"MyNode.h"
template<typename T>
class MyLinkedList
{
public:
MyLinkedList() {
this->_head = nullptr;
}
int size() {
int size = 0;
MyNode<T>* tmp = this->_head;
while (tmp != nullptr) {
tmp = tmp->getNext();
size++;
}
return size;
}
void add(int index, T element) {
MyNode<T>* n = new MyNode<T>();
n->setElement(element);
if (index == 0) {
n->setNext(this->_head);
this->_head = n;
return;
}
MyNode<T>* tmp = this->getNthNode(index - 1);
n->setNext(tmp->getNext());
tmp->setNext(n);
}
void add(T element) {
this->add(this->size(), element);
}
void set(int index, T element) {
this->getNthNode(index)->setElement(element);
}
T get(int index) {
return this->getNthNode(index)->getElement();
}
void remove(int index) {
if (index == 0) {
this->_head = this->_head->getNext();
return;
}
MyNode<T>* tmp = this->getNthNode(index - 1);
tmp->setNext(tmp->getNext()->getNext());
}
string to_string() {
ostringstream ss;
for (int i = 0; i < this->size(); i++) {
ss << this->getNthNode(i)->to_string();
}
return ss.str();
}
private:
MyNode<T>* _head;
MyNode<T>* getNthNode(int index) {
MyNode<T>* result = this->_head;
for (int i = 0; i < index; i++) {
result = result->getNext();
}
return result;
}
};
スタックの修正
次はスタックです。
ちなみにファイル名は MyStack.h です。
#pragma once
#include"MyLinkedList.h"
template<typename T>
class MyStack
{
public:
MyStack() {
this->_myList = new MyLinkedList<T>();
}
bool empty() {
return this->_myList->size() == 0;
}
T peek() {
return this->_myList->get(0);
}
T pop() {
T result = this->peek();
this->_myList->remove(0);
return result;
}
void push(T element) {
this->_myList->add(0, element);
}
string to_string() {
return this->_myList->to_string();
}
private:
MyLinkedList<T>* _myList;
};
キューの修正
今回の最後はキューの修正です。（急な修正で焦っています。）
ちなみにファイル名は MyQueue.h です。
#pragma once
#include"MyLinkedList.h"
template<typename T>
class MyQueue
{
public:
MyQueue() {
this->_myList = new MyLinkedList<T>();
}
void offer(T element) {
this->_myList->add(0, element);
}
T peek() {
return this->_myList->get(this->_myList->size() - 1);
}
T poll() {
T result = this->peek();
this->_myList->remove(this->_myList->size() - 1);
return result;
}
bool isEmpty() {
return this->_myList->size() == 0;
}
string to_string() {
return this->_myList->to_string();
}
private:
MyLinkedList<T>* _myList;
};
キューの動作確認用プログラム
一応、キューについての動作確認を行っておきます。
#include"MyQueue.h"
#include <iostream>
#include<string>
int main()
{
MyQueue<int>* qu = new MyQueue<int>();
cout << "is empty? " << qu->isEmpty() << endl;
qu->offer(1);
cout << qu->to_string() << endl;
cout << "is empty? " << qu->isEmpty() << endl;
qu->offer(2);
cout << qu->to_string() << endl;
qu->offer(3);
cout << qu->to_string() << endl;
qu->offer(4);
cout << qu->to_string() << endl;
int s = qu->peek();
cout << s << endl;
cout << qu->to_string() << endl;
s = qu->poll();
cout << s << endl;
cout << qu->to_string() << endl;
cout << qu->peek() << endl;
}
このプログラムと以前のプログラムの大きな違いは <int> で、どのような型が要素になるかを与えているところだけです。
今回はこれでおしまいにします。それではまた。