C++言語実装リニアテーブルのチェーンテーブルの例
4703 ワード
本稿では,C++言語によるリニアテーブルのチェーンテーブル実装方法について述べる.皆さんの参考にしてください.具体的な分析は以下の通りである.
ノードを挿入、削除するコードは少し多いですが、コードの可読性が向上し、時間の複雑さを増やさず、プログラムのパフォーマンスに影響を与えません.
本稿で述べたことが皆さんのC++プログラム設計に役立つことを願っています.
ノードを挿入、削除するコードは少し多いですが、コードの可読性が向上し、時間の複雑さを増やさず、プログラムのパフォーマンスに影響を与えません.
#include
using namespace std;
template
class CList;
template
class Node
{
friend CList;
private:
T m_data;
Node *m_pNext;
};
template
class CList
{
public:
CList();
~CList();
bool IsEmpty();
void Append(const T &data);
void Delete(const int &pos);
void Print();
int GetLength();
T Find(const int &pos);
void Insert(const int &pos,const T &data);
private:
Node *m_pHead;
Node *m_pEnd;
int m_len;
void Create();
void Destroy();
};
//
template
void CList::Create()
{
m_pHead = new Node;
m_pEnd = new Node;
m_pHead->m_pNext = NULL;
m_pEnd->m_pNext = m_pHead->m_pNext;
m_len = 0;
}
template
CList::CList()
{
Create();
}
//
template
void CList::Destroy()
{
Node *pF = m_pHead->m_pNext;
Node *pT;
while(pF)
{
pT = pF;
pF = pF->m_pNext;
delete pT;
}
}
template
CList::~CList()
{
Destroy();
}
//
template
bool CList::IsEmpty()
{
if(!m_pHead->m_pNext)
{
return true;
}
else
{
return false;
}
}
//
template
void CList::Append(const T &data)
{
Node *pT = new Node;
pT->m_data = data;
pT->m_pNext = NULL;
if(!m_pHead->m_pNext)
{
m_pHead->m_pNext = pT;
}
else
{
(m_pEnd->m_pNext)->m_pNext = pT;
}
m_pEnd->m_pNext = pT;
++m_len;
}
//
template
void CList::Delete(const int &pos)
{
if(pos < 0 || pos < m_len)
{
cout< *pPre = NULL;//
Node *pBehind = NULL;//
Node *pT = m_pHead->m_pNext;//
int ix = -1;
while(pT)
{
++ix;
if(ix == pos - 1 - 1)
{
pPre = pT;
}
else if(ix == pos - 1)
{
pBehind = pT->m_pNext;
break;
}
pT = pT->m_pNext;
}
if(!pPre)// pos
{
delete pT;
m_pHead->m_pNext = pBehind;
--m_len;
return;
}
if(!pBehind)// pos
{
m_pEnd = pPre;
delete pT;
}
pPre->m_pNext = pBehind;
--m_len;
}
//
template
void CList::Print()
{
Node *pT = m_pHead->m_pNext;
while(pT)
{
cout<m_data<m_pNext;
}
cout<
int CList::GetLength()
{
return m_len;
}
//
template
T CList::Find(const int &pos)
{
if(pos <= 0)
{
cout< m_len)
{
cout< *pT = m_pHead->m_pNext;
while(pT)
{
++i;
if(i == pos)
{
return pT->m_data;
}
pT = pT->m_pNext;
}
return NULL;
}
template
void CList::Insert(const int &pos,const T &data)
{
if(pos <= 0 || pos >m_len)
{
cout< *pT = m_pHead->m_pNext;
Node *pPre = NULL;
Node *pBehind = NULL;
while(pT)
{
++i;
if(i == pos - 1)
{
pPre = pT;
}
if(i == pos)
{
pBehind = pT->m_pNext;
break;
}
pT = pT->m_pNext;
}
Node *pNew = new Node;
pNew->m_data = data;
if(!pPre)// pos
{
pNew->m_pNext = m_pHead->m_pNext;
m_pHead->m_pNext = pNew;
++m_len;
return;
}
if(!pBehind)// pos
{
m_pEnd->m_pNext = pNew;
}
pPre->m_pNext = pNew;
pNew->m_pNext = pT;
++m_len;
}
本稿で述べたことが皆さんのC++プログラム設計に役立つことを願っています.