数据结构1:C++实现变长数组

数组作为线性表的一种，具有内存连续这一特点，可以通过下标访问元素，并且下标访问的时间复杂的是O(1)，在数组的末尾插入和删除元素的时间复杂度同样是O(1)，我们使用C++实现一个简单的边长数组。

数据结构定义

class Array
{
int cur;
int cap;
int *tail;
};

cur是当前元素的个数，cap是数组的总容量，tail是数组最后一个元素的下一个空间地址。

数组接口定义

#include<iostream>
#include<stdlib.h>
#include<time.h>
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size);
public:
Array(int size=15);
~Array();
  // 末尾增加元素
   void push_back(int val);
      // 末尾删除元素
   void pop_back();
       // 按位置增加元素
        void insert(int pos, int val);
          // 按位置删除
    void erase(int pos);
    // 元素查询
    int find(int val);
      // 打印数据
    void show()const;
};

这里的expand函数用于给数组扩容，由于扩容操作是由C++标准库的函数实现的(参考vector)，因此我们将expand函数使用private关键字修饰，代表这个函数只能被Array自身使用。

函数实现

#include<iostream>
#include<stdlib.h>
#include<time.h>
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size)
{
    int *p=new int[size*sizeof(int)];
    memcpy(p,tail,size);
    delete tail;
    tail=p;
    cap=size;
}
public:
Array(int size=15):cap(size),cur(0)
{
   tail=new int[size];
}
~Array()
{
    delete []tail;
    tail=nullptr;//防止产生野指针
}
  // 末尾增加元素
   void push_back(int val)
   {
    if(cur>=cap)
    {
        expand(2*cap);
    }
  tail[cur++]=val;
   }
      // 末尾删除元素
      void pop_back()
      {
        if(cur==0)return;
        cur--;
      }
       // 按位置增加元素
        void insert(int pos, int val)
        {
            if(pos<0||pos>cur)return;
            if(cur>=cap)expand(2*cap);
            for(int i=cur-1;i>=pos;i--)
            {
                tail[i+1]=tail[i];
            }
            tail[pos]=val;
            cur++;
        }
          // 按位置删除
    void erase(int pos)
    {
        if(pos<0||pos>cur||cur==0)return;
        for(int i=pos+1;i<cur;i++)
        {
            tail[i-1]=tail[i];
        }
        cur--;
    }
    // 元素查询
    int find(int val)
    {
        for(int i=0;i<cur;i++)
        {
            if(tail[i]==val)return i;
        }
        return -1;
    }
      // 打印数据
    void show()const
    {
         for(int i=0;i<cur;i++)
        {
            std::cout<<tail[i]<<" ";
        }
        std::cout<<std::endl;
    }
};

接口测试

int main()
{
    Array array;
    srand(time(0));
    for(int i=0;i<10;i++)
    {
        array.push_back(rand()%100);
    }
    array.show();
    array.insert(1,100);
    array.show();
    array.pop_back();
    array.show();
    array.erase(2);
    array.show();
    std::cout<<array.find(100);
}

输出结果

原文地址：https://blog.csdn.net/weixin_74027669/article/details/140235365

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！