SeqList

Dear 丶 2022-09-26 13:57 117阅读 0赞

#pragma once
    #include <assert.h>
    #include <iostream>
    using namespace std;
    typedef int DataType;
    class SeqList
    {
    public:
    	SeqList()
    		:_array(NULL)
    		, _size(0)
    		, _capacity(0)
    	{}
    	SeqList(DataType* array, size_t size)
    	{
    		_array = new DataType[size];
    		memcpy(_array, array, sizeof(DataType)*size);
    		_size = size;
    		_capacity = size;
    	}
    	SeqList(const SeqList& s)
    		:_array(NULL)
    		, _size(0)
    		, _capacity(0)
    	{
    		SeqList tmp(s._array, s._size);
    		tmp.Swap(*this);
    	}
    	SeqList& operator=(SeqList s)
    	{
    		s.Swap(*this);
    		return *this;
    	}
    	void Swap(SeqList& s)
    	{
    		std::swap(_array,s._array);
    		std::swap(_size,s._size);
    		std::swap(_capacity, s._capacity);
    	}
    	~SeqList()
    	{
    		if (_array)
    		{
    			delete[] _array;
    			_array = NULL;
    			_size = 0;
    			_capacity = 0;
    		}
    	}	
    	void Print()
    	{
    		for (int i = 0; i <(int) _size; ++i)
    		{
    			cout << _array[i] << " ";
    		}
    		cout << endl;
    	}
    	void PushBack(const DataType& x)
    	{
    		_CheckCapacity(_size + 1);
    		_array[_size++] = x;
    	}
    	void PopBack()
    	{
    		if (_size == 0)
    		{
    			return;
    		}
    		_size--;
    	}
    	void PushFront(const DataType& x)
    	{
    		_CheckCapacity(_size + 1);
    		for (int i = (int)_size - 1; i >= 0; i--)
    		{
    			_array[i + 1]=_array[i];
    		}
    		_array[0] = x;
    		_size++;
    	}
    	void PopFront()
    	{
    		if (_size == 0)
    		{
    			return;
    		}
    		for (int i =1; i <(int)_size; i++)
    		{
    			_array[i - 1] = _array[i];
    		}
    		_size--;
    	}
    	void Insert(DataType index, DataType x)
    	{
    		_CheckCapacity(_size + 1);
    		for (int i = (int)_size - 1; i >= index; i--)
    		{
    			_array[i + 1] = _array[i];
    		}
    		_array[index] = x;
    		_size++;
    	}
    	//修改某个位置的值
    	void Modified(DataType index, DataType x)
    	{
    		if (index > _size-1)
    		{
    			return;
    		}
    		_array[index] = x;
    	}
    	//删除某个位置的值
    	void Removed(DataType index)
    	{
    		int i=0;
    		if (index > _size-1)
    		{
    			return;
    		}
    		for (i =index + 1; i < _size; i++)
    		{
    			_array[i - 1] = _array[i];
    		}
    		--_size;
    	}
    	DataType Find(DataType x,DataType index)
    	{
    		for (int i = index; i < _size; i++)
    		{
    			if (_array[i] == x)
    			{
    				return i;
    			}
    		}
    		return -1;
    	}
    	//删除x，flag=1,删除所有x
    	void Erase(DataType x, int flag)
    	{
    		int index = Find(x, 0);
    		while (index != -1)
    		{
    			Removed(index);
    			if (flag == 1)
    			{
    				index = Find(x, index);
    			}
    			else
    			{
    				return;
    			}
    		}
    	}
    	//冒泡排序
    	void Sort()
    	{
    		int i = 0, j = 0;
    		int exchange = 0;
    		for (i = (int)_size - 1; i > 0; i--)
    		{
    			for (j = 0; j < i; j++)
    			{
    				if (_array[j]>_array[j + 1])
    				{
    					int tmp = _array[j];
    					_array[j] = _array[j + 1];
    					_array[j + 1] = tmp;
    					exchange = 1;
    				}
    			}
    			if (exchange == 0)
    			{
    				break;
    			}
    		}
    	}
    	int BinarySearch(DataType x)
    	{
    		int left = 0;
    		int right = _size - 1;
    		while (left <= right)
    		{
    			int mid = (right - left) / 2 + left;
    			if (_array[mid] == x)
    			{
    				return mid;
    			}
    			if (_array[mid] > x)
    			{
    				left = mid+1;
    			}
    			if (_array[mid] < x)
    			{
    				right = mid-1;
    			}
    		}
    		return -1;
    	}
    	size_t Size()
    	{
    		return _size;
    	}
    
    	size_t Capacity()
    	{
    		return _capacity;
    	}
    private:
    	void _CheckCapacity(size_t size)
    	{
    		if (size > _capacity)
    		{
    			_capacity = size > 2 * _capacity ? size : 2 * _capacity;
    			DataType* tmp = new DataType[_capacity];
    			memcpy(tmp, _array, sizeof(DataType)*_size);
    			delete[] _array;
    			_array = tmp;
    		}
    	}
    private:
    	DataType* _array;
    	size_t _size;
    	size_t _capacity;
    };