目录

一.什么是顺序表

二.如何实现一个顺序表

一.什么是顺序表

顺序表就是用一段连续的内存来储存数据，就像我们的数组，或者是向量vector一样，本文将总结顺序表一些常规的操作。

二.如何实现一个顺序表

顺序表的实现其实很简单，但是还是有很多值得注意的点，比如，如何实现插入自动增长操作？

请想象以下的场景：你出去外面买烧烤，你买了一根香肠，老板给了你一个袋子，这个很小，现在只装得下一根香肠，但是你突然又想买一根香肠，这个时候怎么办呢？老板他会再拿出一个更大的袋子，将你要买的新香肠和你手里拿的香肠一起放进一个更大的袋子里，这样你就能拿走两根香肠了。回到我们的问题，如何实现自动增长？其实道理也是一样，先申请一块更大的内存（新袋子），将老数据复制过来，新数据加在后面（将原来的香肠和新香肠一起放进新袋子里），再释放原来的内存（原来的袋子不要了，里面没东西了），最后手拿着新袋子回家（把指针比作你的手，意味着指针指向了新的较大的内存）。就是下图的操作了：

那如果我们原来的袋子够装呢？那就装在原来的袋子里面，所以需要判断一够不够，所以我们采用这样的方式（优化版）：

 按照上面的思路我们可以写出以下代码：

#include using namespace std;template class MyArray{public:MyArray();MyArray(_Ty data);MyArray(const MyArray& a);void push_back(_Ty data);void travel();~MyArray();private:_Ty* pArr;int size;int capacity;};templateinline MyArray::MyArray(){pArr = new _Ty;pArr = nullptr;size = capacity = 0;}templateinline MyArray::MyArray(_Ty data){pArr = new _Ty;pArr[0] = data;size = capacity = 1;}templateinline MyArray::MyArray(const MyArray& a){size = a.size;capacity = a.capacity;if (capacity){pArr = new _Ty[capacity];memcpy(pArr, a.pArr, sizeof(_Ty)*size);}}templateinline void MyArray::push_back(_Ty data){//判断是否需要额外开空间if (size >= capacity){//计算要开空间的大小capacity = (((capacity >> 1) > 1) ? (capacity >> 1) : 1) + capacity;//开空间_Ty* pNew = new _Ty[capacity];if (pArr){//拷贝数据memcpy(pNew, pArr, sizeof(_Ty) * size);//释放原来的内存delete[] pArr;}//指向新内存pArr = pNew;}//加入新数据pArr[size++] = data;}templateinline void MyArray::travel(){cout << "capacity:" << capacity << "\t" << "size:" << size << "\t";for (int i = 0; i < size; i++){cout << pArr[i] << " ";}cout << endl;}templateinline MyArray::~MyArray(){if (pArr){delete[] pArr;pArr = nullptr;size = capacity = 0;}}

主函数中：

#include "MyArray.h"int main(){MyArray arr;for (int i = 0; i < 10; i++){arr.push_back(i);arr.travel();}return 0;}

 可以看到打印结果令人赏心悦目，接下来补充剩下的功能函数：

templateinline int MyArray::findD(const _Ty& findData){for (int i = 0; i < size; i++){if (findData == pArr[i]) return i;}return -1;}templateinline void MyArray::push_front(_Ty data){//判断是否需要额外开空间if (size >= capacity){//计算要开空间的大小capacity = (((capacity >> 1) > 1) ? (capacity >> 1) : 1) + capacity;//开空间_Ty* pNew = new _Ty[capacity];if (pArr){//拷贝数据memcpy(pNew + 1, pArr, sizeof(_Ty) * size);//释放原来的内存delete[] pArr;}//指向新内存pArr = pNew;}else{_Ty* temp = new _Ty[size];memcpy(temp, pArr, sizeof(_Ty) * size);memcpy(pArr + 1, temp, sizeof(_Ty) * size);delete[] temp;}//加入新数据pArr[0] = data;size++;}templateinline void MyArray::insertByData(const _Ty& insertData, const _Ty& findData){int pos = findD(findData);if (pos == -1){push_back(insertData);}else if (pos == 0){push_front(insertData);}else{//判断是否需要额外开空间if (size >= capacity){//计算要开空间的大小capacity = (((capacity >> 1) > 1) ? (capacity >> 1) : 1) + capacity;//开空间_Ty* pNew = new _Ty[capacity];if (pArr){//拷贝数据memcpy(pNew, pArr, sizeof(_Ty) * size);//释放原来的内存delete[] pArr;}//指向新内存pArr = pNew;}//加入新数据for (int i = size - 1; i > pos; i--){pArr[i + 1] = pArr[i];}pArr[pos + 1] = insertData;size++;}}inline void MyArray::insertByPos(const _Ty& data, size_t pos){if (pos > size || pos = capacity){//计算要开空间的大小capacity = (((capacity >> 1) > 1) ? (capacity >> 1) : 1) + capacity;//开空间_Ty* pNew = new _Ty[capacity];if (pArr){//拷贝数据memcpy(pNew, pArr, sizeof(_Ty) * size);//释放原来的内存delete[] pArr;}//指向新内存pArr = pNew;}//加入新数据for (int i = size - 1; i > pos; i--){pArr[i + 1] = pArr[i];}pArr[pos + 1] = data;size++;}

老人咖美文网