博客

数组(Array)是一种线性表的数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。数组的数据元素不仅仅局限于普通数据类型，它也可以是组合项，例如结构体，甚至于也可以是另一种数据结构。数组支持随机访问，根据下标随机访问的时间复杂度为O(1),但数组但删除和查找效率较为低下，平均情况下时间复杂度为O(n)。也可以使用容器进行替代

代码实现和线性表相似度很大，我就直接改写

线性表的实现

给读者做演示，原文链接：https://blog.csdn.net/Chiang2018/article/details/82709827。

// array.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>  
#include <new>  
 
//Array  数组实现  
//定义  
template<class T>  
class Array  
{  
public :  
    Array(int MaxListSize=10);  //构造函数
    ~Array()                             //析构函数 
    {
        delete[] elements;
    }  
  
    bool IsEmpty() const             //判断是否为空
    {
        return length==0;
    }  

    int Length() const               //获取数组长度
    {
        return length;
    }  

    bool Find(int k,T& x)const; //返回第k个元素到x中 

    int Search(const T& x)const;  //查找元素值为x

    int Delete(int k,T& x);  //删除第K个元素，并将值赋值到x

    int Insert(int k,const T& x);  //插入第k个元素，其值为x

    void Output() ;  
  
private:  
    int length;  //数组长度
    int MaxSize; //数组最大长度
    T *elements;//一维动态数组  
  
};  

//实现...  
template<class T>  
Array<T>::Array(int MaxListSize)  
{   
    MaxSize=MaxListSize;  
    elements=new T[MaxSize];  
    length=0;  
}  
  
template<class T>  
bool Array<T>::Find(int k,T& x)const  
{  
    if(k<1||k>length) 
    {
        return false;  
    }

    x=elements[k-1];  
    return true;  
}  
  
template<class T>  
int Array<T>::Search(const T& x)const  
{  
    for(int i=0;i<length;i++)  
    {
        if(elements[i]==x) 
        {
            return ++i;
        }
    }
    return -1;  
}  
  
template<class T>  
int Array<T>::Delete(int k,T& x)  
{  
    if(Find(k,x))  
    {  
        for(int i=k;i<length;i++)  
        {
            elements[i-1]=elements[i];
        }
        length--;  
        return k;  
    }  
    else
    {
        return -1; 
    }
}  
  
template<class T>  
int Array<T>::Insert(int k,const T& x)  
{  
    if(k<0||k>length||length==MaxSize) 
    {
        return -1;
    }

    for(int i=length-1;i>=k;i--)  
    {
        elements[i+1]=elements[i];  
    }
    elements[k]=x;  
    length++;  
    return k;  
}  
  
template<class T>  
void Array<T>::Output()  
{  
    for(int i=0;i<length;i++)
    {
        std:: cout<<elements[i]<<"   ";  
    }
    std::cout<<std::endl;
}  
 
void LinearListSample()  
{  
    Array<int> L(5);  
    std::cout<<"Length=  "<<L.Length()<<std::endl;  
    std::cout<<"IsEmpty= "<<L.IsEmpty()<<std::endl;  
  
    L.Insert(0,2);
    L.Insert(1,6);  
    L.Output();
    std::cout<<"IsEmpty="<<L.IsEmpty()<<std::endl;  
  
    int z;  
    L.Find(1,z);  
    std::cout<<"First elemet is "<<z<<std::endl;  
    std::cout<<"Length="<<L.Length()<<std::endl;  
  
    L.Delete(1,z);  
    std::cout<<"Deleted element is "<<z<<std::endl;  
    L.Output();
}  

int main(int argc, _TCHAR* argv[])  
{  
    LinearListSample();  
  
    //暂停操作  
    char str;  
    std::cin>>str;  
    //程序结束  
    return 0;  
}  

运行结果也与原文一致，就不再贴图了！

https://blog.csdn.net/Chiang2018/article/details/82709827。