データ構造-単一チェーンテーブル_c++

**
ノード構造の定義:**

templateT>
struct Node
{
T data；
Node * link；
Node(){Link=NULL;}
Node(T x,Node *next=NULL)
{ data=x; link=next; }
};

単一チェーンテーブルクラスの定義

template
class LinkList 
{
   Node * head;//      
public:
   LinkList();//      
   LinkList(T a[ ],int n);//   n      (     )
   ~LinkList();//    
   Node *invert(Node *x);//      
   int ListLength();//       
   T get(int pos);//    
   int Locate(T item);//    
   void PrintLinkList();//       
   bool Insert(int i,const T &item);//      
   bool Remove(int i,T&x);//      
};

**
3アルゴリズム設計と実装(クラスのメンバー関数実装)
**(1)デフォルトのコンストラクタ

template<class T>
LinkList::LinkList()    //    1
{ //            
    head=new Node;//      
}

(2)パラメトリックコンストラクタあり

template<class T>
LinkList::LinkList(T a[],int n)    //    2
{  //         
    Node *p,*r;
    head=p=new Node;//      ，p                
    for(int i=0;inew Node(data[i]);
        p->link=r;       //   p        
        p=p->link;       //p    
    }
}

(3)解析関数

template<class T>
LinkList::~LinkList()   //    ，          ，      
{

Node *current=head->link; // current      
    while(current!=NULL) //        ，       
    {   
        Node *r=current;
        current=current->link;
        delete r;
    }
    head->link =NULL; //     
}

(4)シングルチェーンテーブルの反転

template
Node LinkList::*invert(Node *x)
{
    Node *p,*q,*r;
    p=x;
    q=NULL;
    while(p)
    {
        r=q;
        q=p;
        p=p->link;
        q->link=r;
    }
    return q;
}

(5)単鎖表の長さを求める

template
int LinkList::ListLength()
{
    int num=0;
    Node *p=head->link;
    while(P)
    {
        p=p->link;
        num++;
    }
    return num;
}

(6)ビット別検索

template
T LinkList::Get(int pos)
{
    Node *p=head->link;
    j=1;
    while(p&&j<pos)
    {
        p=p->link;
        j++;
     }
     if(!p||j>pos)
     {
         cout<<"      "<exit(1);
     }
     else
      return p->data;
}

(7)値で検索

template<classT>
int LinkList<T>::Locate(T item)
{
    Node<T>*p=head->link;
    int j=1;
    while(p&&p->data!=item)
    {
        p=p->link;
        j++;
    }
    if(p) return j;
    else return 0;
}

(8)挿入操作アルゴリズムの説明:1 i<1であれば挿入に失敗し、終了する;2単鎖テーブルをスキャンし、単鎖テーブルのi-1番目の要素ノードのポインタpを探す;3 pが存在する(pが空でない)場合はその後に挿入し、操作に成功し、そうでなければ挿入できない.

template<class T>
bool LinkList<T>::Insert(int i,const T&item)
{ //      i         item，      true,    false。
    if(i<1) //       
        return false;
    Node<T> *s,*p=head;
    int count=0; // count    
    while(p && count<i-1)//  i-1        front
    {
        p=p->link;
        count++;
    }
    if(!p) //       
        return false; 
    s=new Node<T>(item,p->link);
        s->data=item;
        s->link= p->link;//       （s    ） link  （s->link）  
    p->link=s; //        （p->link）  
    return true;
}

(9)削除操作a)アルゴリズムステップ:(単一チェーンテーブルのpos番目の要素を削除する)①pos<1であれば削除に失敗し、終了する;2単一チェーンテーブルのpos-1番目の要素ノードを探すポインタp;3 pとp->linkが空でなければ、p->linkが指すノードを削除し、そうでなければ削除に失敗する.

template<classT>
bool LinkList<T>::Remove(int i,T&x) //       i   ，   x
{
    if(i<1)   //       
        return false;
    Node<T> *current,*p=head;
    int count=0;// count    
    while(p->link && count<i-1)//  i-1        
    {
        p=p->link;
        count++;
    }
    if(!p->link)  //       ,pos    
        return false;
    current=p->link;  // current       
    p->link=current->link; //      
    x= current->data;
    delete current;
    return true;
}

(10)チェーンテーブル全体の印刷

template<class T>
void LinkList<T>::PrintLinkList()
{
    Node<T>*current = head->link;
    while(current)
    {
        cout<<current->data<<" ";
        current=current->link;
    }
    cout<<endl;
}