c++之旅第十一弹——顺序表

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

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

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

一,数据结构的概念：

1.什么是数据结构？

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

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

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

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

（2）存储结构：

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

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

二，顺序表：

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

2.顺序表的特点：

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

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

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

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

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

头文件CMyArray.h内容如下：

template //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 
void CMyArray::_resetMemory()
{
    if (len >= maxSize)
    {
        maxSize += (maxSize >> 1) > 1 ? (maxSize >> 1) : 1;
        T *pTemp = new T[maxSize];
        for (size_t i = 0; i = (int)len)
        throw "out_of_range";
    return pBuff[index];
}
​
template 
void CMyArray::erase(int index)
{
    if (index = (int)len)
        throw "out_of_range";
    for (size_t i = index; i = (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 = index; --i)
        pBuff[i + 1] = pBuff[i];
    pBuff[index] = elem;
    len++;
}
​
template 
void CMyArray::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  
.cpp文件内容如下：
 
 
#include "CMyArray.h"
void main()
{
    CMyArray ma;
    for (int i = 0; i