C++达成动态顺序表
发布时间:2021-11-15 16:01:25 所属栏目:教程 来源:互联网
导读:顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。这样的存储方式使得线性表逻辑上相邻的元素,其在物理存储单元中也是相邻的。只要知道了第一个元素的存储地址,就可以知道线性表中任何一个元素
顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。这样的存储方式使得线性表逻辑上相邻的元素,其在物理存储单元中也是相邻的。只要知道了第一个元素的存储地址,就可以知道线性表中任何一个元素的存储地址。本文利用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__ 代码当中的问题及思考提示将在以后探讨。 (编辑:济南站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |