データ構造——リニアテーブル(シーケンス記憶構造(配列))

5703 ワード

データ構造とアルゴリズム

リニアテーブルの物理構造の2つのセット
リニアテーブルの順序格納構造:一セグメントのアドレスで連続した記憶単員が順次リニアテーブルのデータ要素を記憶する(配列で記憶する線形表はシーケンステーブル)

#         
#include
class linerList{
   public:
      virtual ~linerList() {};            
      virtual bool empty() const=0;         //      ，  true
      virtual int size() const=0;           //         
      virtual T& get(int theIndex) const=0; //     theIndex   
      virtual int indexOf(const T& theElement) const=0;//    theElement        
      virtual void erase(int theIndex)=0;  //     theIndex   
      virtual void insert(int theIndex, const T& theElement)=0;// theElement         theIndex   
 
}

一次元配列の長さを変更します.

template
void changedLength1D(T* a, int oldLength, int newLength)
{
   if (newLength<0)
      throw illegalParameterValue("new length must be >=0");
   T* temp=new T[newLength];
   int number=min(oldLength,newLength);//#include 
   copy(a,a+number,temp);// a   temp//#include 
   delete [] a;
   a=temp;//   free  delete ，    NULL, free delete               ，
           //          ，        “  ”  。           NULL.        
}

# arrayList      ，          linearList     ，            。capacity(      ) checkIndex.

template
class arrayList : public linearList
{
   friend ostream& operator<& x);
   public:
//    ，           
      arrayList(int initialCapicity = 10);
      arrayList(const arrayList&);
      ~arrayList() {delete [] element;}

//ADT  
      bool empty() const {return listSize == 0;}
      int size()  const {return listSize;}
      T& get(int index)const ;
      int indexOf(const T& theElement) const;
      void erase(int theIndex);
      void insert(int theIndex, const T& theElement );
      
      
//    
      int capacity（）const {redturn arrayLength;}
      
   projected:
      void checkIndex(int theIndex) const;//          
      T* element;//            
      int arrayLength;//       
      int listSize;//       
}

クラスのarrayListの構造関数と複製の構造関数

template
arrayList::arraydList (int initialCapacity)
{
   if(initialCapacity<1)
   {ostringstream s;
    s<0";
    throw illegalParameterValue(s.str());
    }
   arrayLength = initialCapacity;
   element = new T[arrayLength];
   listSize = 0;
}

template
arrayList::arrayList (const arrayList& theList )
{
   arrayLength = theList.arrayLength;
   listSize = theList.listSize;
   element = new T[arrayLength];
   copy(theList.element,theList.element + listSize,element);
}

arrayListの基本的な方法

template
void arrayList::checkIndex(int theIndex) const
{//     0 listSize-1  
   if(theIndex < 0 || theIndex >= listSize)
    {ostringstream s
     s << "index=" << theIndex << "size=" << listSize;
     throw illegalIndex(s.str());
    }
}

template
T& arrayList::get(int theIndex) const
{
   checkIndex(theIndex);
   return element[theIndex];
}

template
int arrayList::indexOf(const T& theElement) const
{
   int theIndex = (int)(find(element,element+listSize,theElement)-element)
   if(theIndex == listSize)
    //    
     return -1;
   else return theIndex;
}

template
void arrayList::erase(int theIndex)
{
   checkIndex(theIndex);
   //    ，       theIndex   
   copy(element+theIndex+1,element+listSize,element+theIndex);
   element[--listSize].~T();//      
}


template
void arrayList::insert(int theIndex, const T& theElement )
{
   if(theIndex < 0 || theIndex > listSize)
    {//    
     ostringstream s;
     s << "index="  << theIndex << "size=" << listSize;
     throw illegalIndex(s.str());
    }

//    ，        
   if(listSize == arrayLength)
   {//      ，      
    changeLength1D(element,arrayLength,arrayLength*2);
    arrayLength *= 2;
   }

//           
   copy_backward(element+thedIndex,element+listSize,element+listSize+1);
   element[theIndex] = theElement;
   listSize++;   
}

ostream& operator<& x)
{
   copy(element,element+listSize,ostream_iterator(s))
   retrun s;
}

泛型アルゴリズムのfind:stringタイプではない容器の中で、直接に対応する元素を探し出すことができます.find関数はいくつかのパラメータが必要です.find(a.begin()、a.end()、1)この文はaの頭から尾までを表しています.最初の値は1の元素を見つけて、その元素を指すディズデーザーを返します.
findはstring容器の中で用途が広い:find_first_of,find_ラスター.of,find_not_first_of,find_not_ラスター.ofなどはstringタイプの中に、必要なパラメータもディズエ代機、下付き文字列と探している文字列があります.ここで注意してください.文字列です.単一文字を検索することはできません.string afind(a.begin()、a.end()、asd)という言葉は、aの中で最初の存在するサブストリングと「asd」のサブストリングが等しい文字列の先頭アドレスを見つけます.文字列の最初のアドレスを指すディエゼルを返します.find_ラスター.ofは最後の一つを見つけます.find_.not_first_ofは、最初の「asd」と同じではない文字列の最初のアドレスを見つけることです.
copy_backwardアルゴリズムはcopyと行為の面で似ていますが、コピープロセスはcopyと逆方向に進みます.コピープロセスは最後の要素からコピーし始めます.最初の元素がコピーされるまで.つまり、コピー操作は、ラスター-1から始まり、ファーストが終わるまで行われる.これらの要素も後から前の方にコピーされてターゲット容器に入り、リセット-1からlast-firstの要素をコピーしています.簡単な例を挙げると、vector｛0、1、2、3、4、5｝が知られています.最後の3つの要素(3、4、5)を前の3つ(0、1、2)の位置にコピーする必要があります.first設定値3の位置を、lastを5の次の位置に設定し、resultを3の位置に設定します.次に4を1の位置にコピーして、最後の3を0の位置にコピーします.普通の最初の要素からコピーしたcopy()アルゴリズムに比べて、copy_が気になります.バックウォードはどのようなメリットを提供していますか?一つの答えは、シーケンスが重なっている時に、copy()で要素を重ね合わせた目的のシーケンスの残りの位置、つまり、目的のシーケンスの最初の要素の前の位置にコピーすることができます.copy()アルゴリズムで要素を同じシーケンスの右側にコピーしようとしたら、この操作は成功しません.コピーされた要素はコピーする前に書き換えられますから.それらを右にコピーしたいなら、copy_を使ってもいいです.backward()は、目的のシーケンスの終了時に、シーケンサがソースシーケンスの終了時に、シーケンサの右側にある限りです.【図2】要素を重ね合わせたシーケンスの右側にコピーする場合の、この2つのアルゴリズムの違いを示す図である.

Encaseデータ構造のArayClass