线性表是最简单的数据结构,一般有数组实现和链式描述两种,数组实现可以用基础数组,也可以用vector等结构来实现。
数组本身限制是很多的,必须提前设置好数据类型和长度。
type arrayName [ arraySize ];//基础数组结构
double balance[10];//定义一个一维数组
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};//在定义时一并赋值
//数组长度不能为变量,必须使用const
const int n = 3;
int a[n] = { 1,2,3 };
std::cout << a[0] << std::endl;
使用new方法实现动态数组,这是数组实现线性表的基础
int *psome = new int[10];
psome[0]=0;
psome[1]=1;
delete [] psome ;//创立动态数组一定要记得删除
有了动态数组的实现方法,我们就可以再进一步写出更改数组长度的函数
//shuzu.cpp
using namespace std;
template<class T>
void changeLength1D(T*& a, int oldLength, int newLength) {
T* temp = new T[newLength];
int number = fmin(oldLength, newLength);
copy(a, a + number, temp);
delete[]a;
a = temp;
}
//shuzu.h
template<class T>
void changeLength1D(T*&, int, int);
//main.cpp
#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
using namespace std;
int main()
{
int* a = new int[5]{1,2,3,4,5};//必须是动态数组
changeLength1D(a, 5, 3);
}
这段代码使用模板类以应对不同的变量类型,实现了一定的通用性。除此之外函数在接受参数时使用了引用的技巧, T*& a 的含义时获得指针的引用,a是一个指针,如果不通过引用,我们只能更改a指向的变量的数值,不能改变a的指向,这样就没法在后面删除a指向的数组再令a指向temp指向的数组了。通过指针的指针也能实现同样的效果。
template<class T>
void changeLength1D(T** a, int oldLength, int newLength) {
T* temp = new T[newLength];
int number = fmin(oldLength, newLength);
copy(*a, *a + number, temp);
delete[]*a;
*a = temp;
}
int main()
{
int* a = new int[5]{1,2,3,4,5};
changeLength1D(&a, 5, 3);
}
有了变长函数我们就可以开始定义arraylist类了
template<class T>
class arrayList {
public:
arrayList(int initialcapacity = 10);
arrayList(const arrayList<T>&);
~arrayList(){delete []element;}
bool empty() const { return listSize == 0; }
int size() const { return listSize; }
T& get(int theIndex) const;
void arrayList<T>::erase(int);
void arrayList<T>::insert(int, const T&);
protected:
T* element;
int arrayLength;
int listSize;
};
构造函数:两个构造函数通过函数重载实现创建和复制功能
template<class T>
arrayList<T>::arrayList(int initialCapacity) {
arrayLength = initialCapacity;
element = new T[arrayLength];
listSize = 0;
}
template<class T>
arrayList<T>::arrayList(const arrayList<T>& theList) {//使用引用来避免复制提高效率,const避免不小心修改
arrayLength = theList.arrayLength;
element = new T[arrayLength];
listSize = theList.listSize;
copy(theList.element, theList.element + listSize, element);
}
查找和获取指定位置的元素都很简单,删除和插入稍微复杂一些。删除需要把删除后的元素向左移,插入不仅要平移,还得提前判断一下长度够不够了。
template<class T>
void arrayList<T>::erase(int theIndex) {
copy(element + theIndex + 1, element + listSize, element + theIndex);
element[--listSize].~T();
}
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement) {
if (listSize == arrayLength) {
changeLength1D(element, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
copy_backward(element + theIndex, element + listSize, element + listSize + 1);//必须从最后一个开始平移
element[theIndex] = theElement;
}
其他一些函数比如输出啊,检查啊啥的就不写了~
Comments 1 条评论
博主 W
留言版的光标好看欸!
("▔□▔)/