大家好啊，这里是c++之旅第十一弹，跟随我的步伐来开始这一篇的学习吧！

如果有知识性错误，欢迎各位指正！！一起加油！！

创作不易，希望大家多多支持哦！

一,数据结构的概念：

1.什么是数据结构？

数据结构是指计算机存储和组织数据的方式

使用合理的数据结构能够提高程序的运行效率，内存利用率等

2.数据结构的两个层次：

（1）逻辑结构：分为线性和非线性两种，线性即为没有分支的一个接着一个，非线性即为有分支或无逻辑上的连续关系

（2）存储结构：

①线性：分为连续存储（数组）和链式存储（链表）

②非线性：索引存储和散列存储

二，顺序表：

1.属于线性表中的连续存储型

2.顺序表的特点：

（1）、因为地址是连续的所以可以通过下标(索引)访问

（2）、顺序表可以是静态（静态定好大小的数组）也可以是动态（用指针来开辟的空间）

（3）、顺序表随机访问方便，但是插入和删除中间的数据比较困难

3.顺序表的功能实现及完善：（eg：数组的增删查改）

类模板的使用可以避免每一次使用时需要写逻辑代码：

头文件CMyArray.h内容如下：

<code>template <class T>//typename可以用来替换class

class CMyArray

{

T *pBuff;

size_t maxSize;

size_t len;

public:

CMyArray();

CMyArray(CMyArray const& other);

~CMyArray();

public:

void push_back(T const& elem);//尾部添加

void insert(int index, T const& elem);//在index位置插入

void pop_back();//尾部删除

void erase(int index);//删除index位置的值

T& at(int index);//得到下标index的值

int find(T const& elem) const;//查找参数是否在数组中

public:

bool empty() const;//判断当前数组是否是空

size_t size() const;//得到当前数组元素个数

size_t maxLen() const;//得到当前数组可以存放的最大元素个数

private:

void _resetMemory();//扩容内存

};

​

template <class T>

void CMyArray<T>::_resetMemory()

{

if (len >= maxSize)

{

maxSize += (maxSize >> 1) > 1 ? (maxSize >> 1) : 1;

T *pTemp = new T[maxSize];

for (size_t i = 0; i < len; ++i)

pTemp[i] = pBuff[i];

if (pBuff) delete[] pBuff;

pBuff = pTemp;

}

}

​

template <class T>

size_t CMyArray<T>::maxLen() const

{

return maxSize;

}

​

template <class T>

size_t CMyArray<T>::size() const

{

return len;

}

​

template <class T>

bool CMyArray<T>::empty() const

{

return len == 0;

//return pBuff == nullptr;

//使用这个可能有指针指向的内存为未知而不是空的情况，而此时数组实际为空了，所以用上面那个方式更准确

}

​

template <class T>

int CMyArray<T>::find(T const& elem) const

{

for (size_t i = 0; i < len; ++i)

{

if (pBuff[i] == elem)

return i;

}

return -1;

}

​

template <class T>

T& CMyArray<T>::at(int index)

{

if (index < 0 || index >= (int)len)

throw "out_of_range";

return pBuff[index];

}

​

template <class T>

void CMyArray<T>::erase(int index)

{

if (index < 0 || index >= (int)len)

throw "out_of_range";

for (size_t i = index; i < len; ++i)

pBuff[i] = pBuff[i + 1];

len--;

}

​

template <class T>

void CMyArray<T>::pop_back()

{

len--;

}

​

template <class T>

void CMyArray<T>::insert(int index, T const& elem)

{

if (index < 0 || index >= (int)maxSize)

throw "out_of_range";

//if (len >= maxSize)

//{

// maxSize += (maxSize >> 1) > 1 ? (maxSize >> 1) : 1;

// T *pTemp = new T[maxSize];

// for (size_t i = 0; i < len; ++i)

// pTemp[i] = pBuff[i];

// if (pBuff) delete[] pBuff;

// pBuff = pTemp;

//}

//重复内容进行了封装

_resetMemory();

​

for (int i = (int)len - 1; i >= index; --i)

pBuff[i + 1] = pBuff[i];

pBuff[index] = elem;

len++;

}

​

template <class T>

void CMyArray<T>::push_back(T const& elem)

{

//if (len >= maxSize)

//{

// maxSize += (maxSize >> 1) > 1 ? (maxSize >> 1) : 1;

// T *pTemp = new T[maxSize];

// for (size_t i = 0; i < len; ++i)

// pTemp[i] = pBuff[i];

// if (pBuff) delete[] pBuff;

// pBuff = pTemp;

//}

_resetMemory();

pBuff[len++] = elem;

}

​

template <class T>

CMyArray<T>::CMyArray(CMyArray const& other)

{

maxSize = other.maxSize;

len = other.len;

pBuff = nullptr;

if (other.pBuff)

{

pBuff = new T[maxSize];

for (size_t i = 0; i < len; ++i)

pBuff[i] = other.pBuff[i];

}

}

​

template <class T>

CMyArray<T>::~CMyArray()

{

if (pBuff)

delete[] pBuff;

pBuff = nullptr;

maxSize = len = 0;

}

​

template <class T>

CMyArray<T>::CMyArray()

{

pBuff = nullptr;

maxSize = len = 0;

}

.cpp文件内容如下：

#include "CMyArray.h"

void main()

{

CMyArray<int> ma;

for (int i = 0; i < 10; ++i)

ma.push_back(i + 1);

ma.insert(1, 123);

ma.pop_back();

ma.erase(3);

for (size_t i = 0; i < ma.size(); ++i)

printf("%d\t",ma.at(i));

printf("\n");

​

}