[C++知识库]C++实现线性表的顺序存储

1、头文件

创建LinerList.h文件

#pragma once
#include<iostream>
using namespace std;

template<class T>
class LinerList
{
public:
	LinerList(int ms);				//构造函数，创建空列表
	~LinerList();					//析构函数，删除表

	//在第k个位置插入元素x，返回插入后的线性表
	LinerList<T>& insert(int k, const T& x);
	//判断表是否为空，空返回true
	bool isEmpty() const;
	//返回表中的元素个数
	int getLength() const;
	//将表中第k个元素保存到x中，若不存在则返回false
	bool getData(int k, T& x);
	//将表中第k个元素修改为x，若不存在则返回false
	bool modifyData(int k, const T& x);
	//返回x在表中的位置，如果不在表里返回0
	int find(const T& x);
	
	//按位置删除第k个元素，并把它保存到x中，返回删除后的线性表
	LinerList<T>& removebyIndex(const int k, T& x);
	//按元素删除查找的元素，并把它保存到y中，返回删除后的线性表
	LinerList<T>& removebyValue(const T& x, T& y);

	void outPut(ostream& out) const;

protected:
	int length;		//现有元素长度
	int max_size;	//表总长度
	T* element;		//数组首地址
};

template<class T>
LinerList<T>::LinerList(int ms)
{
	max_size = ms;
	element = new T[max_size];
	length = 0;
}

template<class T>
LinerList<T>::~LinerList()
{
	delete[] element;
}

template<class T>
LinerList<T>& LinerList<T>::insert(int k, const T& x)
{
	if (k<0 || k>length + 1)
		cout << "数组下表越界，添加失败！" << endl;
	else
	{
		if (length == max_size)
			cout << "此表已满，插入失败！" << endl;
		else    //插入元素，先挪走后面的，再插入
		{
			for (int i = length - 1; i >= k - 1; i--)
			{
				element[i + 1] = element[i];
			}
			element[k - 1] = x;
			length++;
		}
	}
	return *this;
}

template<class T>
bool LinerList<T>::isEmpty() const
{
	if (length == 0)
		return true;
	else
		return false;
}

template<class T>
int LinerList<T>::getLength() const
{
	return length;
}

//想获取表中第k个元素所有信息，如果直接return的话，会出现很多浅拷贝的问题，而且如果元素比较复杂，信息return效率低
//这里以引用的方式传进来一个参数
template<class T>
bool LinerList<T>::getData(int k, T& x)
{
	if (k<0 || k>length)
	{
		return false;
	}
	x = element[k - 1];		

	return true;
}

template<class T>
bool LinerList<T>::modifyData(int k, const T& x)
{
	if (k<0 || k>length)
	{
		return false;
	}

	element[k - 1] = x;
	return true;
}

template<class T>
int LinerList<T>::find(const T& x)
{
	for (int i = 0; i < length; i++)
	{
		if (element[i] == x)
			return (i + 1);
	}
	return -1;
}

template<class T>
LinerList<T>& LinerList<T>::removebyIndex(const int k, T& x)
{
	if (k<0 || k>length)
	{
		return false;
	}
	
	getData(k, x);

	for (int i = k - 1; i < length - 1; i++)
	{
		element[i] = element[i + 1];
	}
	length--;
	
	return *this;
}
template<class T>
LinerList<T>& LinerList<T>::removebyValue(const T& x, T& y)
{
	int index = find(x);
	if (index != 0)
	{
		return removebyIndex(index, y);
	}
	else
	{
		cout << "没有此元素，删除失败！" << endl;
		return *this;
	}
		
}

//实现顺序表的输出
template<class T>
void LinerList<T>::outPut(ostream& out) const
{
	for (int i = 0; i < length; i++)
	{
		out << element[i] << endl;
	}
}

//全局函数
//重载运算符<<
template<class T>
ostream& operator <<(ostream& out, const LinerList<T>& x)
{
	x.outPut(out);
	return out;
}

对于函数functionA() const 与functionB(const int x)
1、首先functionA是一个类的成员函数时才有意义，这样的functionA是不能修改任何成员数据data，如果想改数据，只能在定义数据前面加关键字mutable
2、functionB表示传进去的参数不能修改，被const了

2、测试

新建main.cpp文件进行测试

#include<iostream>
using namespace std;
#include"LinerList.h"
int main()
{
	LinerList<int> list(10);
	list.insert(1, 10);
	list.insert(2, 70);
	list.insert(3, 20);
	list.insert(2, 1);
	list.insert(5, 6);
	list.insert(6, 3);
	cout << list << endl;

	list.modifyData(6, 100);
	int i = list.find(100);
	cout << i;

	
	int x = 0;
	
	list.removebyIndex(4, x);
	cout << list << endl;
	list.removebyValue(100, x);
	cout << list << endl;

	return 0;
}