模板实现动态顺序表

红太狼 2022-10-02 04:57 191阅读 0赞

**定义类模板时，成员函数可以定义在类内部，也可以在类模板外定义。**

**    此时成员函数中若有类型参数存在，则需注意：**

**(1)要在成员函数定义之前进行模板声明。**

**   (2)在成员函数名前加上“ 类名<类型参数> ”**

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include<iostream>
    using namespace std;
    #include<assert.h>
    
    // 定义模板类  （类型参数为T）
    template<typename  T>
    class SeqList
    {
    public:
    	SeqList();
    	SeqList(const SeqList & sList);
    	SeqList& operator=(const SeqList& sList);
    
    	//函数实现
    	void CheckCapacity();  //检查容量并扩容
    	void PushBack(const T & x);     //尾插
    	void PopBack();                 //尾删
    	void PushFront(const T & x);    //头插
    	void PopFront();                //尾删       
    	int Find(const T & x);          //查找x
    	void Print();                   //打印链表
    	void Insert(size_t pos, const T& x);    //在某个位置后插入x
    	void Erase(size_t pos);                 //删除某位置的数据
    	int Remove(const T & x);                //删除x(先找后删)
    
    	~SeqList()
    	{
    		if (_array != NULL)
    		{
    			delete[] _array;
    			_size = 0;
    			_capicity = 0;
    		}
    	}
    
    private:
    	T* _array;
    	size_t  _size;
    	size_t _capicity;
    
    };
    
    template<typename T>      //模板声明
    SeqList<T>::SeqList()     //在类模板体外定义构造函数
        :_array(NULL)
        , _size(0)
        , _capicity(0)
    {}
    
    template<typename T>         //模板声明
    SeqList<T>::SeqList(const SeqList & sList)       //在类模板体外定义拷贝构造函数
        :_array(new T[sList._size])
        , _size(sList._size)
        , _capicity(sList._capicity)
    {
    	memcpy(_array, sList._array, sizeof(T)*_size);
    }
    
    template<typename T>        //模板声明
    SeqList<T>& SeqList<T>:: operator=(const SeqList<T>& sList) //赋值运算符重载
    {
    	if (&sList != this)
    	{
    		T *tmp = new T[sList._size];
    		delete[] _array;
    
    		_array = tmp;
    		_size = sList._size;
    		_capicity = sList._capicity;
    		memcpy(_array, sList._array, sizeof(T)*_size);
    	}
    	return *this;
    }
    
    template<typename T>                    //模板声明
    void SeqList<T>::CheckCapacity()
    {
    	if (_size >= _capicity)
    	{
    		_capicity = 2 * _capicity + 5;
    		_array = (T *)realloc(_array, _capicity*sizeof (T));
    	}
    }
    
    template<typename T>
    void SeqList<T>::Print()
    {
    	for (int i = 0; i < _size; ++i)
    	{
    		cout << _array[i] << " ";
    	}
    	cout << endl;
    }
    
    template<typename T>
    void SeqList<T>::PushBack(const T & x)
    {
    	CheckCapacity();
    	_array[_size++] = x;
    }
    
    template<typename T>
    void SeqList<T>::PopBack()
    {
    	if (_size == 0)
    	{
    		cout << "This SeqList is Empty !" << endl;
    		return;
    	}
    	else
    	{
    		_array[--_size] = NULL;
    	}
    }
    
    template<typename T>
    void SeqList<T>::PushFront(const T & x)
    {
    	if (_size == 0)
    	{
    		PushBack(x);
    		return;
    	}
    	else
    	{
    		CheckCapacity();
    		int key = _size;
    		while (key)
    		{
    			_array[key--] = _array[key - 1];
    		}
    		_array[0] = x;
    		_size++;
    	}
    }
    
    template<typename T>
    void SeqList<T>::PopFront()
    {
    	if (_size == 0 || _size == 1)
    	{
    		PopBack();
    	}
    	else
    	{
    		for (int i = 0; i < _size - 1; i++)
    		{
    			_array[i] = _array[i + 1];
    		}
    		--_size;
    	}
    }
    
    template<typename T>
    void SeqList<T>::Insert(size_t pos, const T& x)
    {
    	assert(pos<_size);
    	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++;
    	}
    }
    
    template<typename T>
    int SeqList<T>::Find(const T & x)
    {
    	assert(_array != NULL);
    	for (int i = 0; i < _size; i++)
    	{
    		if (_array[i] == x)
    			return i;
    	}
    	return -1;
    }
    
    template<typename T>
    void SeqList<T>::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;
    }
    
    template<typename T>
    int  SeqList<T>::Remove(const T & x)
    {
    	assert(_array);
    	int pos = Find(x);
    	if (pos != -1)
    	{
    		Erase(pos);
    		return 1;
    	}
    	else
    	{
    		return -1;
    	}
    
    }
    
    //测试用例
    void Test()
    {
    	SeqList<int>  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()
    {
    	Test();
    	system("pause");
    	return 0;
    }

转载于:https://blog.51cto.com/iynu17/1758561