ArrayLinkedList

ArrayLinkedList.cpp

#include<iostream>
using namespace std;

template<class Elem>
class AList{
private:
    int maxSize;//链表所能存储的最大元素数量
    int listSize;//当前实际的元素数量
    int fence;//当前操作位置，俗称“栅栏”
    Elem *listArray;//存放链表元素的数组
    
public:

    //构造函数
    AList(int size = 0){
        maxSize = size;
        listSize = fence = 0;
        listArray = new Elem[maxSize];
    }
    /*找不到那个弯弯的符号，注掉先
    //析构函数
    ALsit(){
        delete [] listArray;
    }
    */
    //清除函数clear()
    void clear(){
        delete []listArray;
        listSize = fence =0;
        listArray = new Elem[maxSize];
    }

    //一系列的“栅栏”操作
    void setStart(){ fence = 0; }
    void setEnd(){ 
        fence = listSize;//指向最后一个元素的后一位置
    }
    void prev(){
        if(fence!=0)fence--;
    }
    void next(){
        if(fence<listSize-1)//注意是listSize-1
            fence++;
    }
    int leftLength(){return fence;}
    int rightLength(){return listSize - fence;}
    bool setPos(int pos){
        //注意返回值是bool类型
        //那么就应该对任何不成功的操作进行显式处理
        if(pos>=0&&pos<=listSize)
            fence = pos;
        else return pos>=0&&pos<=listSize;
    }
    bool getValue(Elem & it){//get函数跟以往习惯不同，
        //返回的不是value值，而是该操作是否成功
        //把返回值复制到it上
                            
        if(rightLength()==0)
            //说明此时的fence在逻辑上的end位置
            //从setEnd()函数可知，end位置为数
            //组最后一格的后一位置，而end位置是没有元素的
                            
            return false;
        else{
            it = listArray[fence];
            return true;
        }
    }

    //成员函数的声明
    bool insert(Elem item);
    bool append(Elem item);
    bool remove(Elem& item);
    bool find  (Elem item);
    void print();


};
//插入函数insert()实现
template<class Elem>
bool AList<Elem>::insert(Elem item){
    if(listSize == maxSize)return false;
    //整体后移一格，把fence那一位置腾出来
    for(int i = listSize;i>fence;i--)
        listArray[i]=listArray[i-1];
    listArray[fence] = item;
    listSize ++;
    return true;
}

//追加函数append()实现
template<class Elem>
bool AList<Elem>::append(Elem item){
    if(listSize == maxSize)return false;
    listArray[listSize++] = item;
    return true;
}

//删除函数remove()实现
template<class Elem>
bool AList<Elem>::remove(Elem& item){
    if(rightLength()==0)return false;
    item = listArray[fence];
    for(int i=fence;i<listSize-1;i++)
        listArray[i]=listArray[i+1];
    listSize--;
    return true;
}
template<class Elem>
bool AList<Elem>::find(Elem item){
    Elem it;
    for(setStart();getValue(it);next()){
        if(item == it)return true;//找到了
    }
    return false;//没有找到
}
template<class Elem>
void AList<Elem>::print(){
    cout<<"The AList is: < ";
    for(int i= 0;i<fence;i++)
        cout<<listArray[i]<<" ";
    cout<<"| ";
    for(int i=fence;i<listSize;i++)
        cout<<listArray[i]<<" ";
    cout<<">"<<endl;
}

//测试函数
int main(){
    const int SIZE = 10;
    AList<int> list(SIZE);
    list.print();
    list.append(1);
    list.append(2);
    list.append(3);
    list.print();

    list.next();
    list.print();

    list.insert(4);
    list.print();

    int remItem;
    list.next();
    list.print();
    list.remove(remItem);
    list.print();
    cout<<"被删除的元素为："<<remItem<<endl;

    if(list.find(3))cout<<"3 在链表中"<<endl;
    else cout<<"3 不在链表中"<<endl;
    return 0;
}