template<class T>
class NewVector {
public:
NewVector();
~NewVector();
bool push_front(T nData); //添加到头部
bool push_back(T nData); //添加到尾部
bool pop_back(T* pData = 0); //删除最后一个元素
bool pop_front(T* pData = 0); //删除头元素
int max_size(); //返回最大长度
int& operator[](int nIndex); //重载运算符[]
bool insert(int pos, T nData); //从任意位置添加
bool insert1(int pos,int n, T elem); //在pos索引位置插入n个元素elem
bool insert2(int pos,int beg,int end);//在pos位置插入线性表的beg到end的元素，不包括end
int at(int idx);//返回索引为idx的元素
bool erase(int pos, T* pData = 0); //从任意位置删除
bool remove(T elem); //删除指定数据
bool empty(); //是否为空
void clear(); //清空所有
int findData(T elem); //查找元素所在位置的下标
bool findIndex(int nIndex, T* pData=0); //查找索引所对应的数据
int size(); //获取当前元素个数
bool setData(int nIndex, T elem); //修改下标为nIndex的元素的值为nData
void Print();//遍历打印
bool extend(); //扩展空间
bool reduce();//消减空间
private:
T* m_headerPoint; //头指针
int m_max; //当前最多存储元素个数
int m_count; //当前存储元素个数
};
template<class T>
NewVector<T>::NewVector() {
m_max = 5;
m_count = 0;
m_headerPoint = new T[m_max] {};
}
template<class T>
NewVector<T>::~NewVector() {
clear();
}
//添加到头部
template<class T>
bool NewVector<T>::push_front(T nData) {
if (m_count == m_max)
{
extend();
}
for (int i = m_count; i > 0; i--)
{
m_headerPoint[i] = m_headerPoint[i - 1];
}
m_headerPoint[0] = nData;
m_count++;
return true;
}
//添加到尾部
template<class T>
bool NewVector<T>::push_back(T nData) {
if (m_count == m_max) {
if (!extend()) {
return false;
}
}
m_headerPoint[m_count++] = nData;
return true;
}
//删除最后一个元素
template<class T>
bool NewVector<T>::pop_back(T* pData) {
if (empty()) {
return false;
}
if (pData) {
*pData = m_headerPoint[m_count - 1];
}
m_count--;
if (m_max - m_count > 5) {
return reduce();
}
return true;
}
//删除头元素
template<class T>
bool NewVector<T>::pop_front(T* pData) {
if (empty()) { return false; }
for (int i = 0; i < m_count - 1; i++)//往前移动元素
{
m_headerPoint[i] = m_headerPoint[i + 1];
}
if (pData) {
*pData = m_headerPoint[m_count - 1];
}
m_headerPoint[m_count - 1] = 0;
m_count--;
if (m_max - m_count > 5)
{
return reduce();
}
return true;
}
//返回最大长度
template<class T>
int NewVector<T>::max_size() {
return m_max;
}
//重载运算符[]
template<class T>
int& NewVector<T>::operator[](int nIndex) {
return m_headerPoint[nIndex];
}
//从任意位置添加
template<class T>
bool NewVector<T>::insert(int pos, T nData) {
//如果不合法
if (pos<0 || pos > m_count) {
return false;
}
//如果满了
if (m_count == m_max) {
extend();
}
//如果头部插入
if (pos == 0) {
return push_front(nData);
}
//如果尾部插入
else if (pos == m_count) {
return push_back(nData);
}
else {
for (int i = m_count; i > 0; i--) {
m_headerPoint[i] = m_headerPoint[i - 1];
}
m_headerPoint[pos] = nData;
}
m_count++;
return true;
}
//在pos索引位置插入n个元素elem
template<class T>
bool NewVector<T>::insert1(int pos, int n, T elem) {
if (pos<0 || pos>m_count)
{
return false;
}
//空间不足扩容;
if (m_max - m_count <= n)
{
extend();
}
//如果头部插入
if (pos == 0) {
for (int i = 0; i < n; i++) {
push_front(elem);
}
}
//如果尾部插入
else if (pos == m_count) {
for (int i = 0; i < n; i++) {
push_back(elem);
}
}
else {
for (int i = (m_count + n - 1); i > (pos + n - 1); i--)
{
m_headerPoint[i] = m_headerPoint[i - n];
}
for (int i = pos; i < (pos + n); i++)
{
m_headerPoint[i] = elem;
}
}
m_count += n;
return true;
}
//在pos位置插入线性表中的beg到end的元素，不包括end
template<class T>
bool NewVector<T>::insert2(int pos, int beg, int end) {
if (pos<0 || pos>m_count)
{
return false;
}
//空间不足扩容;
if (m_max - m_count <= (end - beg - 1))
{
extend();
}
//如果头部插入
if (pos == 0) {
for (int i = end - 1; i >= beg; i--) {
push_front(m_headerPoint[i]);
}
}
//如果尾部插入
else if (pos == m_count) {
for (int i = beg; i < end; i++) {
push_front(m_headerPoint[i]);
}
}
else {
for (int i = (m_count + (end - beg) - 1); i > (pos + (end - beg) - 1); i--)
{
m_headerPoint[i] = m_headerPoint[i - (end - beg )];
}
for (int i = pos, j = beg; i < (pos + (end - beg)); i++, j++)
{
m_headerPoint[i] = m_headerPoint[j];
}
}
m_count += (end - beg);
return true;
}
//返回索引为idx的元素
template<class T>
int NewVector<T>::at(int idx) {
if (idx<0 || idx>m_count)
{
return -1;
}
else return m_headerPoint[idx];
}
//从任意位置删除
template<class T>
bool NewVector<T>::erase(int pos, T* pData) {
//索引是不是无效
if (pos<0 || pos>m_count) {
return false;
}
//是不是为空
if (empty()) { return false; }
//是不是头部
if (pos == 0) {
return pop_front(pData);
}
//是不是尾部
if (pos == m_count-1) {
return pop_back(pData);
}
if(pData){
*pData = m_headerPoint[pos];
}
//移动元素
for (int i = pos; i < m_count; i++)
{
m_headerPoint[i] = m_headerPoint[i + 1];
}
m_count--;
if (m_max - m_count > 5)
{
return reduce();
}
return true;
}
//删除指定数据
template<class T>
bool NewVector<T>::remove(T elem) {
for (int i = 0; i < m_count; i++)
{
if (m_headerPoint[i] == elem)
{
//找到后根据下标删除数据
return erase(i);
}
}
return false;
}
//是否为空
template<class T>
bool NewVector<T>::empty() {
if (m_count == 0) { return true; }
return false;
}
//清空所有
template<class T>
void NewVector<T>::clear() {
if (m_headerPoint)
{
delete[] m_headerPoint;
m_headerPoint = nullptr;
m_count = 0;
}
}
//查找元素所在位置的下标
template<class T>
int NewVector<T>::findData(T elem) {
for (int i = 0; i < m_count;i++) {
if (m_headerPoint[i] == elem)
{
return i;
}
}
return -1;
}
//查找索引所对应的数据
template<class T>
bool NewVector<T>::findIndex(int nIndex, T* pData) {
if (nIndex < 0 || nIndex >= m_count)
{
return false;
}
for (int i = 0; i < m_count; i++) {
if (m_headerPoint[nIndex])
{
*pData = m_headerPoint[nIndex];
return true;
}
}
return false;
}
//获取当前元素个数
template<class T>
int NewVector<T>::size() {
return m_count;
}
//修改下标为nIndex的元素的值为nData
template<class T>
bool NewVector<T>::setData(int nIndex, T elem) {
if (nIndex < 0 || nIndex >= m_count)
{
return false;
}
m_headerPoint[nIndex] = elem;
return true;
}
//遍历打印
template<class T>
void NewVector<T>::Print() {
for (int i = 0; i < m_count; i++) {
cout << m_headerPoint[i]<<" ";
}
cout << endl;
}
//扩展空间
template<class T>
bool NewVector<T>::extend() {
int* p = new T[m_max + 5]{};
//申请失败
if (!p) { return false; }
for (int i = 0; i < m_count; i++) {
p[i] = m_headerPoint[i];
}
delete m_headerPoint;
m_headerPoint = p;
m_max += 5;
return true;
}
//消减空间
template<class T>
bool NewVector<T>::reduce() {
int* p = new T[m_max - 5]{};
//申请空间失败
if (!p) { return false; }
if (m_max - m_count < 5) return false;//消减失败
for (int i = 0; i < m_count; i++) {
p[i] = m_headerPoint[i];
}
delete m_headerPoint;
m_headerPoint = p;
m_max -= 5;
return true;
}
int main()
{
NewVector<int> newvector;
printf("先尾部插入12345\n");
newvector.push_back(1);
newvector.push_back(2);
newvector.push_back(3);
newvector.push_back(4);
newvector.push_back(5);
printf("在1的位置插入6\n");
newvector.insert(1, 6);
printf("操作后为:\n");
newvector.Print();
printf("现在最大容量为：%d\n", newvector.max_size());
int nData;
printf("头部删除一个元素\n");
newvector.pop_front(&nData);
printf("操作后为:\n");
newvector.Print();
printf("尾部删除一个元素\n");
newvector.pop_back(&nData);
printf("操作后为:\n");
newvector.Print();
printf("在2的位置插入两个8\n");
newvector.insert1(2, 2, 8);
printf("操作后为:\n");
newvector.Print();
printf("在2的位置插入原表中2-4的元素，不包括4\n");
newvector.insert2(2, 2, 4);
printf("操作后为:\n");
newvector.Print();
printf("删除一个元素8\n");
newvector.remove(8);
printf("操作后为:\n");
newvector.Print();
printf("删除下标为3的元素\n");
newvector.erase(3, &nData);
printf("操作后为:\n");
newvector.Print();
if (newvector.findIndex(1, &nData)) {
printf("找到索引为1的元素\n");
}
if (newvector.findData(8)) {
printf("找到元素8\n");
}
printf("现在最大容量为：%d\n", newvector.max_size());
newvector.extend();
printf("主动扩容一次操作后:\n");
newvector.Print();
printf("现在最大容量为：%d\n", newvector.max_size());
printf("进行一次尾部删除操作\n");
newvector.pop_back(&nData);
printf("然后自动判断要不要消减空间大小\n");
printf("现在最大容量为：%d\n", newvector.max_size());
system("pause");
return 0;
}
动态顺序线性表
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 第1章 第一个C程序第2章 C语言基础第3章 变量和数据类型第4章 顺序结构程序设计第5章 条件结构程序设计第6章...
