【数据结构】线性表的顺序存储结构

青旅半醒 2022-04-04 10:55 367阅读 0赞

线性表：由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：

(a1，a2，…an)

这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。顺序表的特点是，表中逻辑上相邻的数据元素，存储时在物理位置上也一定相邻。换句话说，顺序表以数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间在“逻辑关系上相邻”。

假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点。则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系：

Loc(ai+1)=Loc(ai)+m

顺序表的特点是：逻辑关系上相邻的两个数据元素在物理位置上也相邻。顺序表的优点是：

（1）节省存储空间。由于结点之间的相邻逻辑关系可以用物理位置上的相邻关系表示，因此不需增加额外的存储空间来表示此关系（如链表则需利用指针来表示逻辑相邻关系）。

（2）随机存取。

顺序表的缺点是：插入和删除操作需移动大量数据元素。

以下为代码实现部分，以及测验：

#include<iostream>
    #define MaxSize 100
    #define LISTINSERTMENT 10
    
    typedef int ElemType;
    using namespace std;
    class SqList_d
    {
    private:
        ElemType * elem;
        //ElemType elem_array[MaxSize];//第一种定义；
        int length;
        int ListSize;
    public:
        /*线性表的操作：*/
        SqList_d(int n);//构造函数，初始化；
        ~SqList_d();//析构函数，销毁；
        void SqListInsert(int i,int e);
        int  SqListDelete(int i);
        int SqListLocateElem(int e);//返回数据元素的数值i(按值查找）
        int SqListGetElem(int i);//返回第i个数据元素的值（按位查找）；
        void printlist();//打印数组；
        void SqListAdd();// 增加数组
        int getLength();// 获得长度；
    };
    SqList_d::SqList_d(int n)
    {//构造长度为0，容量为n的。。
        elem = new int [n];
        length =0;
        ListSize=n;
    }
    SqList_d::~SqList_d()
    {//释放表空间；
        delete [] elem;
        length=0;
        ListSize=0;
    }
    void SqList_d::SqListInsert(int i,int e)
    {//将e插入第i个位置
     if(i<1||i>length)
     {
         cout<<"插入位置异常"<<endl;
         return;
     }
     if(length>=MaxSize)
     {
         int *elem1=new int [ListSize+LISTINSERTMENT];
         for(int i=0;i<length;i++)
         {
             elem1[i]=elem[i];
         }
         delete elem;
         elem=elem1;
         ListSize+=LISTINSERTMENT;
     }
         int *p = &elem[i-1],*q=&elem[length-1];
         for(;q >= p;q--)
         {
             *(q+1)=*q;
         }
         *p=e;
         length++;
     }
    
    int SqList_d::SqListDelete(int i)
    {//删除第i个数
        int e;
        if(length==0)
        {
            cout<<"下溢"<<endl;
            return -1;
        }
        if(i<0||i>length)
        {
            cout<<"删除位置异常"<<endl;
            return -1;
        }
        e=elem[i-1];
        int *p=&elem[i-1],*q=&elem[length-1];
        for(;p<q;p++)
        {
            *(p-1)=*p;
        }
        length--;
    }
    int SqList_d::SqListLocateElem(int e)
    {//返回e的位置
        for(int i=0;i<length;i++)
        {
            if(elem[i]==e)
                return i+1;
        }
        return 0;
    }
    int SqList_d::SqListGetElem(int i)
    {//获得第i个位置的数
        if(i<1||i>length)
        {
            cout<<"位置不合法"<<endl;
            return -1;
        }
        return elem[i-1];
    }
    void SqList_d::printlist()
    {
        if(length == 0){
            cout<<" nothing "<<endl;
        }
        else
        {
            for(int i = 0;i < length;i++)
            {
                cout<<elem[i]<<" " ;
            }cout<<endl;
        }}
    int SqList_d::getLength()
    {
        return length;
    }
    void SqList_d::SqListAdd()
    {
        int e;
        cout<<"please input the "<<length <<"th number:";
        cin >> e ;
        elem[length] = e;
        length++;
    }
    int main()
    {
        SqList_d lista(5);
        lista.printlist();
        cout<<"length: "<<lista.getLength()<<endl;
        lista.SqListAdd();
        lista.SqListAdd();
        cout<<"length: "<<lista.getLength()<<endl;
        lista.SqListInsert(1,3);
        lista.SqListInsert(1,4);
        lista.SqListInsert(2,5);
        lista.SqListInsert(3,6);
        lista.printlist();
        return 0;
    }