動態順序表（C++實現），動態順序

動態順序表（C++實現），動態順序

順序表是在計算機內存中以數組的形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。

本文利用C++語言，在Windows平台 Visual Studio 2013開發環境下實現

1：動態增容  2：打印單鏈表  3：尾插  4：尾刪  5：頭插  6：頭刪  7：查找數據  8：在某位置後插入數據  9：刪除某位置的數據 10：找到並刪除x

/***************************************************************************************************************/
/*
     功能：應用C++語言實現順序表的各項操作
         
     基本的成員函數：
                   構造函數、拷貝構造函數、賦值運算符的重載、析構函數      


          **                  1：動態增容
          **                  2：打印單鏈表    
          **                  3：尾插
          **                  4：尾刪
          **                  5：頭插       
          **                  6：頭刪    
          **                  7：查找數據   
          **                  8：在某位置後插入數據   
          **                  9：刪除某位置的數據
          **                 10：刪除x    
          **
          **                                      By ：Lynn-Zhang
          **                                                                                                      
                                                                                                */
/********************************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;
#include <assert.h>

typedef int DataType;

class SeqList
{
public:
    SeqList()
        :_array(NULL)
        , _size(0)
        , _capicity(0)
    {}
    SeqList(const SeqList & sList)
        :_array(new DataType[sList._size])
        , _size(sList._size)
        , _capicity(sList._capicity)
    {
        //memcpy(_array, sList._array, sizeof(sList._array));
        memcpy(_array, sList._array, sizeof(DataType)*_size);
    }
    SeqList& operator=(const SeqList& sList)
    {
        if (&sList != this)
        {
            DataType *tmp = new DataType[sList._size];
            delete[] _array;

            _array = tmp;
            _size = sList._size;
            _capicity = sList._capicity;
            memcpy(_array, sList._array, sizeof(DataType)*_size);
        }
        return *this;
    }
    ~SeqList()
        {
            if (_array != NULL)
            {
                delete[] _array;
                _size = 0;
                _capicity = 0;
            }
        }

    void CheckCapacity();    // 測容/擴容
    void Print();                    // 打印順序表
    void PushBack(const DataType & x);  // 尾插
    void PopBack();        // 尾刪
    void PushFront(const DataType & x);   // 頭插
    void PopFront();    // 頭刪
       
    int Find(const DataType & x);   //查找數據
    void Insert(size_t pos, const DataType & x);   //某位置後插入數據
    void Erase(size_t pos);     //刪除某位置的數據
    int Remove(const DataType & x);   //刪除數據x

private:
    DataType* _array;      //數據塊指針
    size_t   _size;             //定義當前有效數據的個數
    size_t _capicity;         //容量

};

　　 測容，如果容量不夠要進行擴容

void SeqList::CheckCapacity()
{
           if (_size >= _capicity)
           {
                    _capicity = 2 * _capicity + 5;
                    _array = (DataType *)realloc(_array, _capicity*sizeof (DataType ));
           }
}

　　打印順序表

void SeqList::Print() 
{
           for (int i = 0; i < _size; ++i)
           {
                    cout << _array[i] << " " ;
           }
           cout << endl;
}

　　在尾部添加數據

void SeqList::PushBack(const DataType & x)
{
           CheckCapacity();    //添加數據前要進行測容
           _array[_size++] = x ;     //這裡注意：添加完數據意思要給size加1
}

　　尾刪

void SeqList::PopBack()
{
           if (_size == 0)
           {
                    cout << "This SeqList is Empty !" << endl;
                    return;
           }
           else
           {
                    _array[--_size]=NULL ;
           }
}

　　 頭插

void SeqList::PushFront(const DataType & x)   //頭插
{
           if (_size == 0)
           {
                    PushBack(x );
                    return;
           }
           else
           {
                    CheckCapacity();
                    int key = _size;
                    while (key)
                    {
                              _array[key--] = _array[key - 1];
                    }
                    _array[0] = x;
                    _size++;
           }
}

　　 頭刪

void SeqList::PopFront()  //頭刪
{
           if (_size == 0||_size==1)
           {
                    PopBack();
           }
           else
           {
                    for (int i = 0; i < _size-1;i++)
                    {
                              _array[i] = _array[i + 1];
                    }
                    --_size;
           }
}

　　固定位置插入數據

void SeqList::Insert(size_t pos , const DataType& x)   
{
           assert( pos<_size);    //需檢驗pos的合法性
           CheckCapacity();
           if (pos == _size - 1)   //在最後一個位置插入數據等於尾插
           {
                    PushBack(x );
                    return;
           }
           else
           {
                    for (int i = _size; i > pos; --i)
                    {
                              _array[i] = _array[i - 1];
                    }
                    _array[pos ] = x ;
                    _size++;
           }
}

　　查找數據

int SeqList::Find(const DataType & x)    
{
           assert(_array != NULL);
           for (int i = 0; i < _size; i++)
           {
                    if (_array[i] == x )
                              return i;
           }
           return -1;
}

　　固定位置刪除數據

void SeqList::Erase(size_t pos )     //固定位置刪除數據
{
           assert(_array!= NULL);
           assert( pos < _size);
           if (pos == _size - 1)
           {
                    PopBack();
                    return;
           }
           if (pos == 0)
           {
                    PopFront();
                    return;
           }
           for (int i = pos; i < _size-1; i++)
           {
                    _array[i] = _array[i + 1];
           }
           --_size;
}

　　刪除x

int  SeqList::Remove(const DataType & x)   //刪除x
{
           assert(_array);
           int pos=Find(x );
           if (pos != -1)
           {
                    Erase(pos);
                    return 1;
           }
           else
           {
                    return -1;
           }
                    
}

　　測試用例

//void Test1()
//{
//   SeqList list1;
//   list1.PushBack(1);
//   list1.PushBack(2);
//   list1.PushBack(3);
//   list1.PushBack(4);
//   list1.PushBack(5);
//
//   list1.Print();
//
//   SeqList list2;
//   list2.PushBack(0);
//   list2.PushBack(9);
//   list2.PushBack(8);
//   list2.PushBack(7);
//   list2.PushBack(6);
//   list2.Print();
//
//   list1 = list2;
//   list1.Print();
//
//   SeqList list3(list1);
//   list3.Print();
//}
 
void Test2()
{
           SeqList list1;
 
           //list1.PushFront(0);
           //list1.Print();
 
           list1.PushBack(1);
           list1.PushBack(2);
           list1.PushBack(3);
           list1.PushBack(4);
           list1.PushBack(5);
           list1.Print();
 
           //list1.PopFront();
           //list1.Print();
           /*list1.Insert(2, 0);
    list1.Print();*/
           //cout <<"該數字出現在：_array["<< list1.Find(5) <<"]"<< endl;
           //list1.Erase(2);
           
           int ret=list1.Remove(7);
           if (ret == -1)
           {
                    cout << "not exit !" << endl;
           }
           else
           {
                    list1.Print();
           }
}
int main()
{
           //Test1();
           Test2();
           system("pause" );
           return 0;
}