线性表之顺序表（C++版）-创新互联

线性表之顺序表（C语言版本）http://t.csdn.cn/GHizI

SeqlistC.h文件

#pragma once

#include#include
using namespace std;

const int InitSize = 8;

templateclass SeqList
{
private:
	T* data;
	int capacity;//容量
	int size;//大小
public:
	SeqList() :size{ 0 }, capacity{InitSize} //无参构造函数，创建一个容量为InitSize的空表
	{
		data = new T[InitSize]; 
		if (data == nullptr)
		{
			cout<< "erro"<< endl;
		}
	}
	SeqList(T arr[], int n); //初始化容量，创建一个有值的顺序表
	
	//拷贝构造函数
	SeqList(const SeqList& seq)
	{
		size = seq.size;
		capacity = seq.capacity;
		data = new T[seq.size];
		memcpy(data, seq.data, sizeof(T) * seq.capacity);
	}
	//重载“+”运算符
	SeqList operator+(const SeqList& sq)
	{
		int n = size + sq.size;
		T* newdata = new T[n];
		int a = size;//this线性表大小
		int b = sq.size;//aq线性表大小
		T* sra = data;
		T* srb= sq.data;
		T* newsrc = newdata;
		while (a--)
		{
			*newsrc++ = *sra++;
		}
		while (b--)
		{
			*newsrc++ = *srb++;
		}
		
		return SeqList(newdata,n);//调用其构造函数
	}


	//赋值函数
	SeqList& operator=(const SeqList& a)
	{
		if (this != &a)
		{
			//释放原有空间，防止原有空间大小不够，重新申请空间
			delete[] data;
			data = new T[a.size];
			memcpy(data, a.data, sizeof(T) * a.capacity);
			this->size = a.size;
			this->capacity = a.capacity;

		}
		return *this;
	}


	~SeqList() 
	{
		delete[] data;
		size = 0;
		capacity = 0;
	}

	void push_back(T val);//尾插
	void Show()const;//显示
	void push_front(T val);//头插
	void pop_back();//尾删
	void pop_front();//头删
	void inser_pos(T val, int pos);//按位置插入
	T find(T val)const;//按值查找
	int length()const { return size; }//长度
	void delete_pos(int pos);//按位置删除
	void delete_val(T val);//按值删除
	void Sort();//排序
	void Reverse();//逆序
	void Clear() { size = 0; }//清空
	bool Inc();//增容
};
//交换函数
templatevoid Swap(T& a, T& b)
{
	T tmp = 0;
	tmp = a;
	a = b;
	b = tmp;
}
//初始化容量，创建一个有值的顺序表
templateSeqList:: SeqList(T arr[], int n) 
{
	data = new T[InitSize];
	if (data == nullptr)
	{
		cout<< "erro"<< endl;
	}
	capacity = InitSize;
	while (n >this->capacity)
	{
		if (this->Inc())
		{
			break;
		}
		else
		{
			cout<< "erro"<< endl;
		}
	}
	for (int i = 0; i< n; ++i)
	{
		data[i] = arr[i];
	}
	size = n;
}


//增容
templatebool SeqList::Inc()
{
	T* newdata = new T[capacity * 2];
	if (newdata == nullptr)
	{
		cout<< "erro"<< endl;
	}
	int n = size;//线性表大小
	T* src = data;
	T* newsrc = newdata;
	while (n--)
	{
		*newsrc++ = *src++;
	}
	this->data = newdata;
	this->capacity = this->capacity * 2;
	return true;
}

//显示
templatevoid SeqList::Show()const
{
	if (this->size == 0)
	{
		cout<< "没有数据"<< endl;
	}
	else
	{
		for (int i = 0; i< this->size; ++i)
		{
			cout<< this->data[i]<< " ";
		}
		cout<< endl;
	}
}

//尾插
templatevoid SeqList::push_back(T val)
{
	if (size >= capacity && !Inc())
	{
		cout<< "顺序表满了，不能尾插"<< endl;
		return;
	}
	data[size] = val;
	size++;
}

//头插
templatevoid SeqList::push_front(T val)
{
	if (size >= capacity && !Inc())
	{
		cout<< "顺序表满了，不能头插"<< endl;
		return;
	}
	for (int i = size; i >0; --i)
	{
		data[i] = data[i - 1];
	}
	data[0] = val;
	size++;

}

//尾删
templatevoid SeqList::pop_back()
{
	assert(this != nullptr);
	size--;
}

//头删
templatevoid SeqList::pop_front()
{
	assert(this != nullptr);
	for (int i = 1; i< size; ++i)
	{
		data[i - 1] = data[i];
	}
	size--;
}

//按位置插入
templatevoid SeqList::inser_pos(T val, int pos)
{
	//判断位置是否合法
	if (pos<0 || pos>size)
		cout<< "pos erro"<< endl;
	if (size == capacity && !Inc())
	{
		cout<< "Inc erro"<< endl;
	}
	for (int i = size; i >pos; --i)
	{
		data[i] = data[i - 1];
	}
	data[pos] = val;
	size++;

}

//按值查找
templateT SeqList::find(T val)const
{
	if (size == 0)
		cout<< "空表"<< endl;
	for (int i = 0; i< size; ++i)
	{
		if (data[i] == val) return i;
	}
	return -1;
}

//按位置删除
templatevoid SeqList::delete_pos(int pos)
{
	assert(this != nullptr);
	if (pos< 0 || pos >= size)
		cout<< "pos err"<< endl;
	for (int i = pos; i< size - 1; i++)
	{
		data[i] = data[i + 1];
	}
	size--;

}

//按值删除
templatevoid SeqList::delete_val(T val)
{
	assert(this != nullptr);
	int pos = find(val);
	if (pos == -1)
		cout<< "val不存在"<< endl;
	delete_pos(pos);
}

//排序
templatevoid SeqList::Sort()
{
	for (int i = 0; i< size - 1; ++i)
	{
		for (int j = 0; j< size - i - 1; j++)
		{
			if (data[j] >data[j + 1])
			{
				Swap(data[j], data[j + 1]);
			}
		}
	}
}

//逆序
templatevoid SeqList::Reverse()
{
	int left = 0; int right = size - 1;
	while (left< right)
	{
		Swap(data[left], data[right]);
		left++;
		right--;
	}
}

test.cpp测试代码

#include"SeqlistC.h"

int main()
{
	int arr[5] = { 1,2,3,4,5};
	int brr[3] = { 6,7,8 };
	SeqListsq = SeqList(arr, 5);
	sq.Show();
	SeqListsq1;
	sq1.Show();
	SeqListsq2 = SeqList(arr, 3);
	sq2.Show();
	sq = sq + sq2;
	sq.Show();
	sq.push_back(6);
	sq.Show();
	sq.push_front(0);
	sq.Show();
	sq.pop_back();
	sq.Show();
	sq.pop_front();
	sq.Show();
	sq.inser_pos(0, 3);
	sq.Show();
	cout<<"元素0的位置是："<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧