静的チェーンテーブル(C++実装)——データ構造(沈俊版)(初心者用)に基づく
58352 ワード
静的チェーンテーブル(C++実装)——データ構造に基づく(沈俊版)
データ構造を初めて勉強して、喜ばないなら噴き出さないでください.みんなの指摘を歓迎します!
静的チェーンテーブルは、配列を用いて記憶空間をシミュレートしてチェーンテーブルを実現するものであり、配列内の各要素にリンクポインタ(配列の下付き)を付加すると、静的チェーンテーブル構造が形成されます.各要素の物理的位置を変更せずに、再リンクするだけでこれらの要素の論理順序を変更できます.配列によって定義されているため、演算中に格納される空間の大きさは変更されません.静的チェーンテーブルと呼ばれます.
静的チェーンテーブル(C++)ソースコード
データ構造を初めて勉強して、喜ばないなら噴き出さないでください.みんなの指摘を歓迎します!
静的チェーンテーブルは、配列を用いて記憶空間をシミュレートしてチェーンテーブルを実現するものであり、配列内の各要素にリンクポインタ(配列の下付き)を付加すると、静的チェーンテーブル構造が形成されます.各要素の物理的位置を変更せずに、再リンクするだけでこれらの要素の論理順序を変更できます.配列によって定義されているため、演算中に格納される空間の大きさは変更されません.静的チェーンテーブルと呼ばれます.
静的チェーンテーブル(C++)ソースコード
// StaticLinkList.h
#ifndef STATICLINKLIST_H // ，
#define STATICLINKLIST_K
#define MAXSIZE 1000
#include<iostream>
using namespace std;
template <typename T> //
class StaticLinkList;
template <typename T>
class Node //
{
private:
T data; // ，
int next; // ， ； next -1
friend class StaticLinkList<T>; // ，
};
template <typename T>
class StaticLinkList //
{
private: // （ ， ， ）
int avail; //avail （ ） ， 0，
int head; //head （ ） ， 0
Node<T> *sll; //
int size; //
public:
StaticLinkList(); //
StaticLinkList(T v[],int n,int Size=MAXSIZE); //
virtual ~StaticLinkList();
StaticLinkList(const StaticLinkList<T> &List);
StaticLinkList<T> & operator=(const StaticLinkList<T> &List);
void Insert(const T &e,const int &n); // （ n ）
void InsertElem(const T &e); //
void FreeList();
void DeleteElem(const int &n,T &e);
void SetElem(const int &n,const T &e);
void Reverse(); // ，
int Search(const T &e) const; // ， -1
int Getlength() const; // （ ）
bool Full() const;
bool Empty() const;
void Output(ostream &out) const;
};
template <typename T>
StaticLinkList<T>::StaticLinkList()
{
avail = 0;
head = -1; // head=-1
size = MAXSIZE;
sll = new Node<T>[MAXSIZE];
for(int i=0;i<MAXSIZE-1;i++)
sll[i].next = i+1;
sll[MAXSIZE-1].next = -1; // next -1
}
template <typename T>
StaticLinkList<T>::StaticLinkList(T v[],int n,int Size) // ,
{
head = 0;
size = Size;
sll = new Node<T>[Size];
for(int i=0;i<Size-1;i++) // next ，
sll[i].next = i+1;
sll[Size-1].next = -1; // next 0
for(int i=1;i<=n;i++)
sll[i].data = v[i-1];
sll[n].next = -1; // next -1
avail = (n+1)>=Size?-1:(n+1); // avail
}
template <typename T>
StaticLinkList<T>::~StaticLinkList()
{
FreeList();
}
template <typename T>
StaticLinkList<T>::StaticLinkList(const StaticLinkList<T> &List)
{
*this = List;
}
template <typename T>
StaticLinkList<T> & StaticLinkList<T>::operator=(const StaticLinkList<T> &List) //
{
if( &List == this ) //
return *this;
FreeList();
if(List.Empty())
return *this;
sll = new Node<T>[List.size];
head = List.head;
avail = List.avail;
size = List.size;
for(int i=0;i<size;i++)
sll[i].next = List.sll[i].next; // next
int x = List.head;
while(x!=-1) //
{
sll[x].data = List.sll[x].data;
x = sll[x].next; // p = p-> next ， x
}
return *this;
}
template <typename T>
void StaticLinkList<T>::Insert(const T &e,const int &n) // （ n ）
{
if(Full()) //
{
cout<<" ， ！"<<endl;
return;
}
if( !Empty() ) // ：
{
int t = avail,x = head; // t avail， ，
avail = sll[avail].next; // avail
for(int i=0;i<n;i++)
x = sll[x].next; // （ ） n ， next t
sll[t].next = sll[x].next; // next x next ，
sll[x].next = t;
sll[t].data = e;
}
else // ：
{
head = 0;
avail = 2;
sll[1].data = e;
sll[1].next = -1; // sll[1]
}
}
template <typename T>
void StaticLinkList<T>::InsertElem(const T &e) //
{
if(Full())
{
cout<<" ， ！"<<endl;
return;
}
if( !Empty())
{
int t = avail ;
avail = sll[avail].next;
sll[t].next = sll[head].next;
sll[t].data = e;
sll[head].next = t;
}
else
{
head = 0;
avail = 2;
sll[1].data = e;
sll[1].next = -1;
}
}
template <typename T>
void StaticLinkList<T>::FreeList()
{
head = -1;
avail = 0;
if(sll != NULL )
delete [] sll;
}
template <typename T>
void StaticLinkList<T>::DeleteElem(const int &n,T &e)
{
if(Empty())
{
cout<<" ， ！"<<endl;
return;
}
int x = head,y = head,z = avail;
for(int i=0;i<n-1;i++)
y = sll[y].next;
x = sll[y].next;
e = sll[x].data;
sll[y].next = sll[x].next;
avail = x;
sll[avail].next = z;
if(Empty())
{
avail = 0;
head = -1;
for(int i=0;i<size-1;i++)
sll[i].next = i+1;
sll[size-1].next = -1;
}
}
template <typename T>
void StaticLinkList<T>::SetElem(const int &n,const T &e)
{
if(Empty())
return;
int x = head;
for(int i=0;i<n;i++)
x = sll[x].next;
sll[x].data = e;
}
template <typename T>
void StaticLinkList<T>::Reverse()
{
if( Empty() || Getlength() == 1 )
return;
int a[Getlength()+1],x = head,j=0;
while(x != -1)
{
a[j++] = sll[x].next;
x = sll[x].next;
}
x = 0;
int n = Getlength();
for(int i = 1;i<= n;i++)
{
sll[x].next = a[n-i];
x = sll[x].next;
}
sll[x].next = -1;
}
template <typename T>
int StaticLinkList<T>::Search(const T &e) const
{
int pos = -1,x = head,i=0;
while(x != -1)
{
if( e == sll[x].data )
pos = i;
x = sll[x].next;
i++;
}
return pos;
}
template <typename T>
int StaticLinkList<T>::Getlength() const
{
int num = 0,x = head;
while(x != -1)
{
x = sll[x].next;
if( x != -1)
num++;
}
return num;
}
template <typename T>
bool StaticLinkList<T>::Full() const
{
if(Getlength() == size - 1)
return true;
else
return false;
}
template <typename T>
bool StaticLinkList<T>::Empty() const
{
if(Getlength() == 0)
return true;
else
return false;
}
template <typename T>
void StaticLinkList<T>::Output(ostream &out) const
{
if( !Empty() )
{
out<<" ：Head-->";
out<<"sll["<<head<<']'<<"///"<<"-->";
int x = head;
x = sll[x].next;
while( x!=-1 )
{
out<<"sll["<<x<<']'<<sll[x].data<<"-->";
x = sll[x].next;
}
out<<"-1"<<endl;
}
else
out<<" "<<endl;
if( !Full() )
{
out<<" ：Avail-->";
int x = avail,i = 1;
for(int i=0;i<10 && x != -1;i++ )
{
out<<"sll["<<x<<']'<<"-->";
x = sll[x].next;
}
out<<"-1";
}
else
out<<" "<<endl;
}
template <typename T>
ostream & operator<<(ostream &out,const StaticLinkList<T> &List)
{
List.Output(out);
return out;
}
#endif // STATICLINKLIST_H