顺序表的c++实现

顺序表是在计算机内存中以数组的形式保存的线性表。栈和队列都是具有特殊存取方式的顺序表。

线性表采用顺序存储方式存储就称为顺序表。

顺序表比栈和队列更有普遍性，大概有以下功能

#ifndef List_hpp
#define List_hpp

class List
{
public:
    List(int size);             //创建顺序表
    ~List();                    //销毁顺序表
    void ClearList();           //清空顺序表
    bool ListFull() const;      //顺序表判满
    bool ListEmpty() const;     //顺序表判空
    int ListLength();           //顺序表长度
    bool GetElem(int i,char *p);//找到第i个元素
    int LocateElem(char *p);    //找到元素位置
    bool PriorElem(char *currentElem,char *preElem);//获得目标元素的前驱
    bool NextElem(char *currentElem,char *nextElem);//获得目标元素的后继
    bool ListInsert(int i,char *p);                 //在位置i插入元素
    bool ListDelete(int i,char *p);                 //删除位置i元素
    void ListTraverse();                            //遍历顺序表
private:
    char *_pList;
    int _iSize;
    int _iListLen;
    int _Index;
};

#endif /* List_hpp */

根据需要，加入了一个成员变量_Index用作游标

线性表的通用函数实现(构造，销毁，清空，判满，判空，求长度）

List::List(int size)
{
    _iSize=size;
    _pList=new char[_iSize];
    ClearList();
}

List::~List()
{
    delete[] _pList;
    _pList=NULL;
}

void List::ClearList()
{
    _iListLen=0;
}

bool List::ListFull() const
{
    if(_iListLen==_iSize)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool List::ListEmpty() const
{
    if(_iListLen==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int List::ListLength()
{
    return _iListLen;
}

根据位置求元素和已知元素求位置

位置求元素要先判断该位置是否存在元素，根据元素求元素位置同样要判断顺序表中是否存在该元素，想用c++的异常与抛出来做，但是没学好，明天再专门整理异常与抛出的知识。

bool List::GetElem(int i,char *p)
{
    if(i<0||i>=_iListLen)
    {
        return false;
    }
    else
    {
        *p=_pList[i];
        return true;
    }
}

int List::LocateElem(char *p)
{
    bool Elem=false;
    for(_Index=0;_Index<_iListLen;_Index++)
    {
        if(*p==_pList[_Index])
        {
            Elem=true;
            break;
        }
    }
    if(Elem)
    {
        return _Index;
    }
    else
    {
        std::cout<<"error!"<<std::endl;
        return -1;
    }
}

求目标元素的前驱与后继，要先去的目标元素位置，然后判断是否有前驱或后继。

bool List::PriorElem(char *currentElem,char *preElem)
{
    LocateElem(currentElem);
    if(_Index>0&&_Index<_iListLen)
    {
        *preElem=_pList[_Index-1];
        return true;
    }
    else
    {
        return false;
    }
}

bool List::NextElem(char *currentElem,char *nextElem)
{
    LocateElem(currentElem);
    if(_Index>=0&&_Index<_iListLen-1)
    {
        *nextElem=_pList[_Index+1];
        return true;
    }
    else
    {
        return false;
    }
}

在位置i插入元素是，要判断顺序表是否为满，再判断该位置是否超过了顺序表长

bool List::ListInsert(int i,char *p)
{
    if(ListFull())
    {
        return false;
    }
    else
    {
        if(i<0||i>_iListLen)
        {
            return false;
        }
        else
        {
            for(_Index=_iListLen;_Index>i;_Index--)
                _pList[_Index]=_pList[_Index-1];
            _pList[i]=*p;
            _iListLen++;
            return true;
        }
    }
}

删除元素时，同时将被删除的元素取了出来，同样要先判断是否为空，再判断位置是否超过了表长

bool List::ListDelete(int i,char *p)
{
    if(ListEmpty())
    {
        return false;
    }
    else
    {
        if(i<0||i>=_iListLen)
        {
            return false;
        }
        else
        {
            *p=_pList[i];
            for(_Index=i;_Index<_iListLen;_Index++)
                _pList[_Index]=_pList[_Index+1];
            _iListLen--;
            return true;
        }
    }
}

最后，通用的遍历收尾

void List::ListTraverse()
{
    using namespace std;
    
    cout<<endl;
    for(_Index=0;_Index<_iListLen;_Index++)
    {
        cout<<_pList[_Index]<<endl;
    }
    cout<<endl;
}