シングルチェーンテーブルの実装(VC 2008でテストに合格)

4019 ワード

データ構造とアルゴリズムを再確認し、チェーンテーブルを手書きで書き、コードを言わないでください.
#ifndef XKLINKEDLIST_H_H_H_H
#define XKLINKEDLIST_H_H_H_H
template <class T1> struct node
{
	T1 data;
	struct node *next;
};
template <class T2>
class XkLinkedList
{
public:
	XkLinkedList();
	~XkLinkedList();
	bool PushBack(T2 item);
	bool RemoveAt(int index);
	bool InsertAt(int index,const T2 item);
	bool Replace(int index,const T2 item);
	bool  GetAt(int index , T2 &item);
	int GetLength(){return m_length;}
	T2 GetEnd(){return m_end->data;}
	void PrintAll();
	void Clear();
private:
	node<T2> *m_head;
    node<T2> *m_end;
	int m_length;
	node<T2>*  _GetAt(int index);
	bool _IsValidNode(node<T2>* nodePtr);
};
#endif
#include "LinkedList.h"
#include <string>
#include <iostream>
 template <class T2> XkLinkedList<T2>::XkLinkedList(){
	m_head = new node<T2>;
	m_end = m_head;
	m_length = 0;
}

 template <class T2> XkLinkedList<T2>::~XkLinkedList(){
	Clear();
}

template<class T2> bool XkLinkedList<T2>::PushBack(T2 item){
	node<T2>  *NewEndNode = new node<T2>();
	NewEndNode->data = item;
	m_end->next =  NewEndNode;
	m_end = NewEndNode;
	m_length++;
	return true;
}

template <class T2> void XkLinkedList<T2>::PrintAll(){
	node<T2> *loopNode;
	loopNode = m_head;
	while (loopNode!=m_end)
	{
		loopNode = loopNode->next;
		std::cout << loopNode->data << std::endl;
	}
	return ; 
}

template <class T2> bool XkLinkedList<T2>::RemoveAt(int index){
	if( index > m_length || index < 0)  return false;
	node<T2>  *needDeletedNodePtr;
	node<T2>  *preNodePtr;
	needDeletedNodePtr = _GetAt(index);
	preNodePtr = _GetAt(index-1);
	if ( _IsValidNode(needDeletedNodePtr) &&  _IsValidNode(preNodePtr))
	{
		preNodePtr->next = needDeletedNodePtr->next;
		delete needDeletedNodePtr;
		if(index==m_length){
			m_end = preNodePtr;
		}
		--m_length;
		return true;
	}
	return false;
}
template <class T2> bool XkLinkedList<T2>::InsertAt(int index,const T2 item){
	if( index > m_length || index < 0)  return false;
	node<T2> *newNodePtr = new node<T2>();
	node<T2> *preNodePtr = _GetAt(index-1);
	node<T2> *indexNodePtr = _GetAt(index);
	newNodePtr->data = item;
	if ( _IsValidNode(preNodePtr) &&  _IsValidNode(indexNodePtr))
	{
		preNodePtr->next = newNodePtr;
		newNodePtr->next = indexNodePtr;
		++m_length;
		return true;
	}
	return false;
}
template<class T2> bool XkLinkedList<T2>::Replace(int index ,  const T2 item){
	if( index > m_length || index < 0)  return false;
	node<T2> *findNode;
	findNode = _GetAt(index);
	if( _IsValidNode(findNode) ){
		findNode->data = item;
		return true;
	}
	return false;
}
template <class T2> bool  XkLinkedList<T2>::GetAt(int index , T2 &item){
	if( index > m_length || index < 0)  return false;
	node<T2> *findNode;
	findNode = _GetAt(index);
	if( _IsValidNode(findNode) ){
		item = findNode->data;
		return true;
	}
	return false;
}

template <class T2> void XkLinkedList<T2>::Clear(){
	node<T2> *needDeletedNodePtr;
	node<T2> *tempNodePtr = m_head ;
	while (tempNodePtr!=m_end)
	{
		needDeletedNodePtr = tempNodePtr;
		tempNodePtr = tempNodePtr->next;
		delete needDeletedNodePtr;
		m_head = NULL;
		m_end = m_head; 
	}
	return;
}
template <class T2> node<T2>* XkLinkedList<T2>::_GetAt(int index){
	if(index == 0){
		return m_head;
	}
	if(index == m_length){
		return m_end;
	}
	node<T2> *loopNode = m_head->next;
	while((--index) > 0){
		loopNode = loopNode->next;
	}
	return loopNode;
}

template <class T2> bool  XkLinkedList<T2>::_IsValidNode(node<T2>* nodePtr){
	if(nodePtr->next==NULL && nodePtr->data==NULL){
		return false;
	}
	return true;
}