C++实现顺序表

╰半橙微兮° 2022-07-17 04:16 142阅读 0赞

#pragma once
    #include<assert.h>
    
    typedef int DataType;
    class SeqList
    {
    public:
               //传统写法调用的构造函数
              SeqList()
                       :_array( NULL)
                       ,_size(0)
                       ,_capacity(0)
              {}
               //现代写法调用的构造函数
              SeqList( DataType* array ,size_t size)
                       :_array( new DataType [size])
                       , _size( size)
                       , _capacity( size)
              {
                       memcpy(_array, array, sizeof (DataType)* size);
              }
    
    
              ~SeqList()
              {
                        if (_array)
                       {
                                  delete[] _array;
                       }
              }
    
               //深拷贝传统写法
               /*SeqList(const SeqList& s)
                       :_array(new DataType[s._size])
                       , _capacity(s._size)
                       , _size(s._size)
              {
                       memcpy(_array, s._array, sizeof(DataType)*_size);  
              }
    
              SeqList& operator=(const SeqList&s)
              {
                       if (this != &s)
                       {
                                 DataType* tmp = new DataType[s._size];
                                 delete[] _array;
                                 _array = tmp;
                                 _size = s._size;
                                 _capacity = s._size;
                                 memcpy(_array, s._array, sizeof(DataType)*s._size);
                       }
                       return *this;
              }*/
    
    
               //现代写法
               //按size拷贝构造
              SeqList( const SeqList & s) 
                       :_array( NULL)
              {
                        SeqList tmp(s ._array, s._size);  
                       swap(_array, tmp._array);
                       _size = s._size;     //s._size赋值给_size
                       _capacity = s._size;//所以把s._size赋值给新的_capacity
              }
               //赋值运算符的重载
               SeqList& operator=(SeqList s)   //无const 无引用
                       
              {
                       swap( s._array,_array);
                       _size = s._size;
                       _capacity = s._capacity;
                        return *this ;
              }
    
    public:
               void PushBack(DataType x)
              {
                       CheckCapacity();
                       _array[_size++] = x;
              }
    
               void PopBack()
              {
                        if (--_capacity )
                       {
                                 _array[_size--];
                       }
                        if (_size == 0)
                                 cout << "NULL";
              }
    
               void PushFront(DataType x)
              {
                       CheckCapacity();
                       _size++;  
                        for (int i =_size-1; i >=0; i--)  //_size-1  i>=0
                       {
                                 _array[i + 1] = _array[i];
                       }
                       
                       _array[0] = x;
    
              }
               void PopFront()
              {
                        if (_size <= 0)
                       {
                                 cout << "NULL";
                                  return;
                       }
                        else
                       {
                                  for (int i = 0; i <_size; i++ )
                                 {
                                          _array[i] = _array[i + 1];       
                                 }
                                 _size--;
                       }
              }
               void Insert(size_t pos, DataType x )
              {
                       
                        if (pos == 0)
                       {
                                 PushFront( x);
                       }
                        else
                       {
                                 _size++;
                                  for (int i = _size - 1; i >= pos; i--)
                                 {
                                          _array[i] = _array[i - 1];
                                 }
                                 
                                 _array[ pos] = x ;
                       }
              }
    
               //attention
               void Erase(size_t x)
              {
                        int count = 0;
                        for (int i = 0; i <= _size; ++i)
                       {
                                  if (_array[i] == x )
                                 {
                                          count++;
                                 }
                                  else
                                 {
                                          _array[i - count] = _array[i];
                                 }
                                 
                       }
                        //放在循环外面
                       _size -= count;
    
              }
    
    
               int Find(DataType x)
              {
                        for (int i = 0; i < _size; i++)
                       {
                                  if (x == _array[i])
                                 {
                                           return i;
                                 }
                       }
              }
    
    
    
               void PrintList()
              {
                        for (int i = 0; i < _size; ++i)
                       {
                                  //if (_array[i])
                                 cout << _array[i] << "->";
                       }
                       cout << "NULL"<<endl;
              }
    private:
               void CheckCapacity()
              {
                        if (_size >= _capacity)
                       {
                                 _capacity = 2 * _capacity + 3;
                                 _array =( DataType*) realloc(_array, (sizeof(DataType ))*_capacity);
                                  //realloc后将指针赋给新的空间
                                  //sizeof(DataType)*_capacity
                       }
              }
    private:
               DataType* _array;
               size_t _size;
               size_t _capacity;
    };
    
    
    
     void Test1()
    {
               SeqList s1;   //先定义一各变量
               s1.PushBack(1);
               s1.PushBack(2);
               s1.PushBack(3);
               s1.PushBack(4);
               s1.PushBack(5);
               s1.PrintList();
               /* SeqList s2(s1);
               s2.PrintList();*/
               s1.PopBack();
               s1.PopBack();
               s1.PopBack();
               s1.PopBack();
               s1.PrintList();
              
    }
    
     //PushFront()
     void Test2()
     {
               SeqList s1;
               s1.PushFront(1);
               s1.PushFront(2);
               s1.PushFront(3);
               s1.PushFront(4);
               s1.PushFront(5);
               s1.PrintList();
    
               s1.PopFront();
               s1.PopFront();
               s1.PopFront();
               s1.PrintList();
     }
     //pushback  Insert
     void Test3()
     {
               SeqList s1;   //先定义一各变量
               s1.PushBack(1);
               s1.PushBack(2);
               s1.PushBack(3);
               s1.PushBack(4);
               s1.PushBack(5);
               s1.PrintList();
               s1.Insert(0, 0);
               s1.Insert(1, 6);
               s1.Insert(7, 5);
               s1.PrintList();
     }
    
     void Test4()
     {
               SeqList s1;
               s1.PushBack(1);
               s1.PushBack(2);
               s1.PushBack(3);
               s1.PushBack(4);
               s1.PushBack(5);
               s1.PushBack(5);
               s1.PushBack(5);
               s1.PrintList();
               s1.Erase(5);
               s1.PrintList();
     }
    
     void Test5()
     {
               SeqList s1;
               s1.PushBack(1);
               s1.PushBack(2);
               s1.PushBack(3);
               s1.PushBack(4);
               s1.PushBack(5);
               s1.PrintList();
               //s1.Erase(5);
               int ret5 = s1.Find(5);
               int ret4 = s1.Find(4);
               int ret3 = s1.Find(3);
               int ret2 = s1.Find(2);
               int ret1 = s1.Find(1);
               cout << ret5 << ret4 << ret3 << ret2 << ret1 << endl;
    
     }
    
     void TestSeqList6()
     {
               SeqList s1;
               s1.PushBack(2);
               s1.PushBack(2);
               s1.PushBack(3);
               s1.PushBack(2);
               s1.PushBack(4);
               s1.PushBack(2);
               s1.PushBack(5);
               s1.PushBack(2);
    
               s1.Erase(2);
               s1.PrintList();
     }