シングルチェーンテーブルの実装(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;
}