C++实现数据结构（顺序表）

#pragma once
#include 
#include 
using namespace std;
#define MAXLENGTH 100


template
class sqList
{
public:
//基本操作

	//初始化顺序表
	sqList();

	//单元素尾插法
	bool InitsqList(elemtype e);

	//批量尾插法
	bool MoreInitsqList();

	//指定位置插入元素
	bool InsertsqList(int i , elemtype e);

	//指定位置删除元素
	elemtype DelsqList(int i);

	//查找指定元素的位置
	int LocateElem(elemtype e);

	//查找指定位置的元素
	elemtype SelectElem(int i);

	//求表长
	int LengthList();

	//打印顺序表
	void PrintfList();


//查找算法

	//顺序查找
	void Search(elemtype e);

	//二分查找
	void Search_bin(elemtype e);


//排序算法

	//插入排序
	void InsertSort();

	//希尔排序
	void ShellSort();

	//冒泡排序
	void BubblsSort();

	//快速排序
	void QuickSort(int left,int right);

	//选择排序
	void SelectSort();


private:
	int length;
	elemtype data[MAXLENGTH];
};

#include "sqList.h"
#include 
using namespace std;

//初始化顺序表
template
inline sqList::sqList()
{
	this->length = 0;
	this->data[MAXLENGTH];
}

//尾插法建表
template
bool sqList::InitsqList(elemtype e)
{
	if (this->length >= MAXLENGTH)
	{
		return false;
	}
	this->data[length] = e;
	this->length++;
	return true;
}

//批量尾插法建表
template
bool sqList::MoreInitsqList()
{
	if (this->length >= MAXLENGTH)
	{
		return false;
	}
	elemtype e;
	while (cin >> e)
	{
		if (this->length >= MAXLENGTH)
		{
			return false;
			break;
		}
		this->data[length] = e;
		this->length++;
	}
	return true;

}

//在指定位置插入
template
bool sqList::InsertsqList(int i, elemtype e)
{
	if (this->length >= MAXLENGTH)
	{
		return false;
	}
	if (i > this->length)
	{
		return false;
	}
	for (int j = length; j > i; j--)
	{
		this->data[j] = this->data[j - 1];
	}
	this->data[i] = e;
	this->length++;
}

//在指定位置删除
template
elemtype sqList::DelsqList(int i)
{
	if (i<0 || i>length)
	{
		return false;
	}
	elemtype e = this->data[i];
	for (i; i < length-1; i++)
	{
		this->data[i]=this->data[i+1];
	}
	this->length--;
	return e;
}

//定位元素
template
int sqList::LocateElem(elemtype e)
{
	if (this->length == 0)
	{
		return -1;
	}
	for (int i = 0; i < length; i++)
	{
		if (this->data[i] == e)
		{
			return i;
		}
	}
}

//下标查找元素
template
elemtype sqList::SelectElem(int i)
{
	if (i<0 || i>length)
	{
		return -1;
	}
	return this->data[i];
}

//求表长
template
int sqList::LengthList()
{
	return this->length;
}

//遍历打印顺序表
template
void sqList::PrintfList()
{
	cout << "顺序表打印："<< endl;
	for (int i = 0; i < this->length; i++)
	{
		cout << this->data[i] << ",";
	}
	cout << "打印结束" << endl;//为什么不打印？
}

//顺序查找
template
void sqList::Search(elemtype e)
{
	if (this->length <= 0)
	{
		cout << "顺序表为空" << endl;
	}
	int cont = 0;
	for (int i = 0; i < this->length; i++)
	{
		if (this->data[i] == e)
		{
			cout << "查找成功，位置为第：" << i << "位" << endl;
			cont++;
		}
	}
	if (cont == 0)
	{
		cout << "查找失败" << endl;
	}
}

//二分查找
template
void sqList::Search_bin(elemtype e)
{
	this->InsertSort();
	int left = 0;
	int right= this->LengthList()-1;
	int mid = (left + right) / 2;
	while (leftdata[mid])
		{
			right = mid-1;
		}
		else if (e > this->data[mid])
		{
			left = mid+1 ;
		}
		else if (e == data[mid])
		{
			cout << "查找成功,在数组第" << mid << "位置" << endl;
			break;
		}
		mid = (left + right) / 2;
	}
	if (left >= right)
	{
		cout << "元素不存在" << endl;
	}

}

//插入排序
template
void sqList::InsertSort()
{
	if (this->length < 2)
	{
		cout << "无法排序" << endl;
		exit;
	}
	int i,j;
	for (i = 1; i < length; i++)								//从第二个元素开始遍历
	{
		if (this->data[i] < this->data[i - 1])					//如果比前一个元素小，则开始插入排序
		{
			int temp = this->data[i];
			for (j = i - 1; this->data[j] > temp && j>=0; j--)	//比temp元素大的元素都往后移一位
			{
				this->data[j + 1] = this->data[j];
			}
			this->data[j+1] = temp;								//将temp元素插入排序位置
		}
	}
	this->PrintfList();
}

//希尔排序
template
void sqList::ShellSort()
{
	if (this->length < 2)
	{
		cout << "无法排序" << endl;
	}
	int i, j;
	int step, temp;
	for (step = this->length / 2; step >= 1; step /= 2)
	{
		for (i = step; i < this->length; i++)
		{
			int temp = this->data[i];
			for (j = i - step; this->data[j] > temp && j >= 0; j-=step)	
			{
				this->data[j + step] = this->data[j];
			}
			this->data[j + step] = temp;
		}
		this->PrintfList();
	}
}

//冒泡排序
template
void sqList::BubblsSort()
{ 
	if (this->length < 2)
	{
		cout << "排序失败" << endl;
	}
	int i, j, temp;
	for (i = 0; i < this->length-1; i++)
	{
		for (j = 0; j < length - i-1; j++)
		{
			if (this->data[j] > this->data[j + 1])
			{
				temp = this->data[j];
				this->data[j] = this->data[j + 1];
				this->data[j + 1] = temp;
			}
		}
		this->PrintfList();
	}
}

//快速排序
template
void sqList::QuickSort(int left, int right)
{
	if (this->length < 2)
	{
		cout << "排序失败" << endl;
	}
	int i = left;
	int j = right;
	int key = this->data[left];
	int temp;
	while (i < j)
	{
		while (i < j && this->data[j] >= key)	//第一趟从右指针开始往左滑动比较
		{
			j--;
		}
		temp = this->data[i];			//当交换条件满足时，
		this->data[i] = this->data[j];
		this->data[j] = temp;

		while (idata[i]<=key)
		{
			i++;
		}
		temp = this->data[j];			//当交换条件满足时，
		this->data[j] = this->data[i];
		this->data[i] = temp;
	}
	this->data[i] = key;
	cout << "排序zhong" << endl;
	if (i - 1 > left)
	{
		QuickSort(left, i - 1);
	}
	if (i + 1 < right)
	{
		QuickSort(i + 1, right);
	}
}

//选择排序
template
void sqList::SelectSort()
{
	if (this->length)
	{
		cout << "排序失败" << endl;
	}
	int i, j;
	int min,temp;

	for(i=0;idata[j] < this->data[min])
			{
				min = j;
			}
		}
		if (i != min)
		{
			temp = this->data[i];
			this->data[i] = this->data[min];
			this->data[min] = temp;
		}
	}
}