C++实现动态顺序表
我叫河蟹 2017-04-05
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。这样的存储方式使得线性表逻辑上相邻的元素，其在物理存储单元中也是相邻的。只要知道了第一个元素的存储地址，就可以知道线性表中任何一个元素的存储地址。本文利用C++语言，在Windows平台 Visual Studio 2015开发环境下实现。功能：应用C++语言实现顺序表的各项操作。基本的成员函数：构造函数、拷贝构造函数、赋值运算符的重载、析构函数。
// 顺序表构造成功之后，里面存放了n个元素data
Vector(size_t n, const DataType& data = DataType());
Vector(const Vector& v);
Vector& operator=(const Vector& v);
~Vector();
void PushBack(const DataType& data); //尾插
void PopBack(); //尾删
void Print()//打印顺序表
// 给顺序表重新赋值，该函数执行完里面存放了n个元素data
void Assign(size_t n, const DataType& data);
// 在顺序表的pos位置上插入元素data
void Insert(size_t pos, const DataType& data);
// 删除顺序表pos位置上的元素
void Erase(size_t pos);
// 改变顺序表中的元素为n个，如果n>原来顺序表中的元素的个数，多出来的空间用data来填充
void ReSize(size_t n, const DataType& data = DataType());
// 清空顺序表中的元素-->请自己动手验证是否需要清理vector中的空间
void Clear();
// 返回顺序表中有效元素的大小
size_t Size()const;
// 返回顺序表中空间容量的大小
size_t Capacity()const;
// 顺序表是否为空，若为空返回true，否则返回null
bool Empty()const;
// 通过下边访问顺序表index位置上的元素。 思考为什么要成对的来重载
DataType& operator[](size_t index);
const DataType& operator[](size_t index)const;
// 返回顺序表中第一个元素的引用，思考为什么要返回应用，为什么要成对重载
DataType& Front();
const DataType& Front()const;
// 返回顺序表中最后一个的元素的引用，思考为什么要返回引用，为什么要成对重载
DataType& Back();
const DataType& Back()const;
void _CheckCapacity()// 动态扩容
int Find(const DataType & data)//查找数据
#ifndef __VECTOR_H__
#define __VECTOR_H__
#include<iostream>
#include<stdio.h>
#include<assert.h>
using namespace std;
#define COW 4
typedef int DataType;
class Vector
{
public:
Vector()
: _array(NULL)
, _size(0)
, _capacity(0)
{}
// 顺序表构造成功之后，里面存放了n个元素data
Vector(size_t n, const DataType& data = DataType())
{
_array = new DataType[n];
_size = n;
_capacity = n;
for(size_t i = 0; i<n;i++)
_array[i] = data;
}
Vector(const Vector& v)
:_array(new DataType[v._size])
, _size(v._size)
,_capacity(v._capacity)
{
memcpy(_array, v._array, sizeof(DataType)*_size);
}
Vector& operator=(const Vector& v)
{
if (this != &v)
{
DataType *temp = new DataType[v._size];
temp = v._array;
delete[] _array;
_array = temp;
_size = v._size;
_capacity = v._capacity;
memcpy(_array, v._array, sizeof(DataType)*_size);
}
return *this;
}
~Vector()
{
if (_array)
{
delete[] _array;
_array = NULL;
_size = 0;
_capacity = 0;
}
}
public:
void PushBack(const DataType& data)
{
_CheckCapacity();
_array[_size++] = data;
}
void PopBack()
{
assert(!Empty());
--_size;
}
void Print()
{
for (size_t i = 0; i < _size; ++i)
{
cout << _array[i] << " ";
}
cout << endl;
}
// 给顺序表重新赋值，该函数执行完里面存放了n个元素data
void Assign(size_t n, const DataType& data)
{
assert(n<_size);
for (size_t i = 0; i<n; i++)
_array[i] = data;
}
// 在顺序表的pos位置上插入元素data
void Insert(size_t pos, const DataType& data)
{
assert(pos<_size); //需检验pos的合法性
_CheckCapacity();
if (pos == _size - 1) //在最后一个位置插入数据等于尾插
{
PushBack(data);
return;
}
else
{
for (size_t i = _size; i > pos; --i)
{
_array[i] = _array[i - 1];
}
_array[pos] = data;
_size++;
}
}
// 删除顺序表pos位置上的元素
void Erase(size_t pos)
{
assert(pos<_size); //需检验pos的合法性
if (pos == _size - 1) //在最后一个位置删除数据等于尾删
{
PopBack();
return;
}
else
{
for (size_t i = pos; i < _size - 1; i++)
{
_array[i] = _array[i + 1];
}
--_size;
}
}
// 改变顺序表中的元素为n个，如果n>原来顺序表中的元素的个数，多出来的空间
// 请用data来填充
void ReSize(size_t n, const DataType& data = DataType())
{
if (n > _size)
{
size_t i = _size;
_size = n;
_CheckCapacity();
for (i; i < n; i++)
_array[i] = data;
}
else
{
size_t i = n;
for(i; i<_size; i++)
PopBack();
}
}
// 清空顺序表中的元素-->请自己动手验证是否需要清理vector中的空间
void Clear()
{
delete[] _array;
_array = NULL;
_size = 0;
_capacity = 0;
}
// 返回顺序表中有效元素的大小
size_t Size()const
{
return _size;
}
// 返回顺序表中空间容量的大小
size_t Capacity()const
{
return _capacity;
}
// 顺序表是否为空，若为空返回true，否则返回null
bool Empty()const
{
return _size == 0;
}
// 通过下边访问顺序表index位置上的元素
// 思考为什么要成对的来重载
DataType& operator[](size_t index)
{
assert(index);
return _array[index];
}
const DataType& operator[](size_t index)const
{
assert(index);
return _array[index];
}
// 返回顺序表中第一个元素的引用，思考为什么要返回应用，为什么要成对重载
DataType& Front()
{
return _array[0];
}
const DataType& Front()const
{
return _array[0];
}
// 返回顺序表中最后一个的元素的引用，思考为什么要返回引用，为什么要成对重载
DataType& Back()
{
return _array[_size - 1];
}
const DataType& Back()const
{
return _array[_size - 1];
}
private:
// 动态扩容-->该函数中有坑，请找出坑在哪？
void _CheckCapacity()
{
// 2*_capacity 有问题？
if (_size >= _capacity)
{
DataType* pTemp = new DataType[_capacity * 2];
//memcpy(pTemp, _array, _size*sizeof(DataType));
for (size_t index = 0; index < _size; ++index)
pTemp[index] = _array[index];
delete[] _array;
_array = pTemp;
_capacity *= 2;
}
}
int Find(const DataType & data)
{
assert(_array != NULL);
for (size_t i = 0; i < _size; i++)
{
if (_array[i] == data)
return i;
}
return -1;
}
private:
DataType* _array;
size_t _size; // 保存有效元素的个数
size_t _capacity; // 空间的实际大小
};
#endif //__VECTOR_H__
代码当中的问题及思考提示将在以后探讨。
