数据结构---第二章_线性表-顺序表的实现

左手的ㄟ右手 2022-12-31 13:19 197阅读 0赞

基类：

#pragma once
    template<class T>
    class List
    {
    public:
    	void Clear();   // 置空线性表
    	bool IsEmpty();  // 线性表为空时，返回true
    	bool Append(const T value); // 在表尾部添加元素 value，表的长度增加1
    	bool Insert(const int p, const T value); // 在位置p插入元素value，表的长度增加1
    	bool Delete(const int p);   //删除位置 p上的元素，表的长度减1
    	bool GetValue(const int p, T& value); // 把位置p上的元素值返回到变量value中
    	bool SetValue(const int p, const T value); // 把位置p的元素值修改为value
    	bool GetPos(int& p, const T value); // 把值为value的元素的位置返回到变量p中 
    };

子类：

#pragma once
    #include "List.h"
    
    template<class T>
    class ArrayList :public List<T>
    {
    private:
    	T *arrayList; // 存储顺序表的实例
    	int maxSize;  // 顺序表实例的最大长度
    	int curLen;   // 顺序表实例的当前长度
    	int position; // 当前处理位置
    
    public:
    	int Length(); // 当前的长度
    	bool Append(const T value); // 在表尾添加元素value，表的长度增加1
    	bool Insert(const int p, const T value); // 在位置 p 插入元素value
    	bool Delete(const int p); // 删除位置p上的元素，表的长度减1
    	bool GetValue(const int p, T& value);  // 把 p位置上的元素返回到变量value中
    	bool SetValue(const int p, T value); // 把位置p上的元素值修改为value
    	bool GetPos(int& p, const T value);  // 获取值为value的元素的位置。如果没有则p的值为-1。队列中存在值为value 则返回true，否则返回false。
    
    public:
    	ArrayList(const int size)
    	{
    		maxSize = size;
    		arrayList = new T[maxSize];
    		curLen = 0;
    		position = 0;
    	}
    
    	~ArrayList()
    	{
    		delete[]arrayList;
    	}
    
    	void Clear()
    	{
    		delete[]arrayList;
    		curLen = 0;
    		position = 0;
    		arrayList = new T[maxSize];
    	}
    };

在位置p插入元素：

template<class T>
    bool ArrayList<T>::Insert(const int p, const T value)
    {
    	if (curLen >= maxSize)
    	{
    		std::cout << "The list is overflow" << std::endl;
    		return false;
    	}
    
    	if (p < 0 || p > curLen)
    	{
    		std::cout << "insertion point is illegal" << std::endl;
    		return false;
    	}
    
    	for (int i = curLen; i > p; i--)
    	{
    		arrayList[i] = arrayList[i - 1];
    	}
    
    	arrayList[p] = value;
    	curLen++;
    	return true;
    }

在队尾加入元素：

template<class T>
    bool ArrayList<T>::Append(const T value)
    {
    	if (curLen >= maxSize)
    	{
    		std::cout << "The list is overflow" << std::endl;
    		return false;
    	}
    
    	arrayList[curLen] = value;
    	curLen++;
    	return true;
    }

删除位置p的元素：

template<class T>
    bool ArrayList<T>::Delete(const int p)
    {
    	if (p < 0 || p > curLen)
    	{
    		std::cout << "insertion point is illegal" << std::endl;
    		return false;
    	}
    
    	int endLen = curLen - 1;
    	for (int i = p; i < endLen; i++)
    	{
    		arrayList[i] = arrayList[i + 1];
    	}
    
    	curLen--;
    	return true;
    
    }

获取p位置元素：

template<class T>
    bool ArrayList<T>::GetValue(const int p, T& value)
    {
    	if (p < 0 || p > curLen)
    	{
    		std::cout << "insertion point is illegal" << std::endl;
    		return false;
    	}
    
    	value = arrayList[p];
    	return true;
    }

设置p位置的值：

template<class T>
    bool ArrayList<T>::SetValue(const int p, T value)
    {
    	if (p < 0 || p > curLen)
    	{
    		std::cout << "insertion point is illegal" << std::endl;
    		return false;
    	}
    
    	arrayList[p] = value;
    	return true;
    }

查看队列中第一个值为value的元素的位置，如果没有则p为-1

template<class T>
    bool ArrayList<T>::GetPos(int& p, const T value)
    {
    	p = -1;
    	for (int i = 0; i < curLen; i++)
    	{
    		if (value == arrayList[i])
    		{
    			p = i;
    			return true;
    		}
    	}
    
    	return false;
    }

获取当前长度：

template<class T>
    int ArrayList<T>::Length()
    {
    	return curLen;
    }

做的过程中，遇到一点问题，用vs2017编译，如果模板的一些函数声明放在.h文件，实现放在.cpp文件。如果在main.cpp中引用的是ArrayList.h就会报错，但是引用ArrayList,cpp就编译通过了，自己也有点不明所以然，请教他人：

> 首先需要知道的是把模版类的定义和实现分开写了，编译将会出错。
> 
> C++中每一个对象所占用的空间大小，是在编译的时候就确定的，在模板类没有真正的被使用之前，编译器是无法知道，模板类中使用模板类型的对象的所占用的空间的大小的。只有模板被真正使用的时候，编译器才知道，模板套用的是什么类型，应该分配多少空间。这也就是模板类为什么只是称之为模板，而不是泛型的缘故。