2.6 静态链表

 C++实现带头结点的静态链表

#ifndef STATICLIST_H
#define STATICLIST_H
#include <cassert>
#include <iostream>
using namespace std;
///带头结点的静态链表
const int defaultSize = 100;

template <class T>
struct SLinkNode
{
    T data;
    int link;
};

template <class T>
class StaticList
{
    SLinkNode<T> *elem;
    int maxSize;
    int avil;//可用结点链链首下标

public:
    StaticList(int sz = defaultSize);
    ~StaticList();

    int Length();//返回表长
    int Search(T x);//搜索x
    int Locate(int i);//定位第i个元素

    bool getData(int i, T &x);//获取第i个元素的值
    bool Append(T x);          //在表尾添加新结点
    bool Insert(int i, T x);   //在第i个位置上插入元素x
    bool Remove(int i);//删除第i个位置上元素
    bool IsEmpty();//判断表是否为空

    void output(int type = 0)//按指定格式输出
    {
        if(type != 1)
        {
            int l = 0;
            while(elem[l].link != -1)
            {
                int t = elem[l].link;
                cout<<elem[t].data<<' ';
                l = elem[l].link;
            }
            cout<<endl;
        }
        else{
            for(int j=1;j<avil;j++)
                cout << elem[j].data<<' ' ;
            cout <<endl;
        }

    }
    friend istream& operator >> (istream& in, StaticList<T> &stl)
    {
        T data;
        while (!in.eof()) //在原链表后添加，与其他线性表不同
        {
            in >> data;
            stl.Append(data);
        }
        return in;
    }
    friend ostream & operator<<(ostream &out, StaticList <T> &stl)
    {
        int p = stl.elem[0].link;//elem[0]为附加头结点
        while(p != -1)
        {
            cout << stl.elem[p].data << endl;
            p = stl.elem[p].link;
        }
        cout << endl;
        return out;
    }
};

template <class T>
StaticList<T>::StaticList(int sz)
{
    if(sz>0)
    {
        maxSize = sz;
        avil = 1;
        elem = new SLinkNode<T>[maxSize];
        elem[0].link = -1;
        for(int i=1; i<maxSize-1; i++)
            elem[i].link = i+1;
        elem[maxSize-1].link = -1;
    }
}

template <class T>
StaticList<T>::~StaticList()
{
    delete []elem;
}

template <class T>
int StaticList<T>::Length()//返回表长
{
    int f = elem[0].link;
    int sum = 0;
    while(f != -1)
    {
        f = elem[f].link;
        sum++;
    }
    return sum;
}

template <class T>
int StaticList<T>::Search(T x)//搜索x
{
    int f = elem[0].link;
    while(f != -1)
    {
        if(x == elem[f].data)
            break;
        else
            f = elem[f].link;
    }
    return f;
}

template <class T>
int StaticList<T>::Locate(int i)//定位第i个元素
{
    if(i < 0)
        return -1;
    if(i == 0)
        return 0;

    int f = elem[0].link;
    int s = 1;
    while(f != -1 && s<i)
    {
        f = elem[f].link;
        s++;
    }
    return s;
}

template <class T>
bool StaticList<T>::getData(int i, T &x)//获取第i个元素的值
{
    int loc = Locate(i);
    if(loc==0 || loc==-1)
        return false;
    x = elem[loc].data;
    return true;
}

template <class T>
bool StaticList<T>::Append(T x)          //在表尾添加新结点
{
    if(avil == -1)
        return false;
    int q = avil;
    avil = elem[avil].link;
    elem[q].data = x;
    elem[q].link = -1;
    int p = 0;
    while(elem[p].link != -1)
        p = elem[p].link;
    elem[p].link = q;
    return true;
}

template <class T>
bool StaticList<T>::Insert(int i, T x)   //在第i个位置上插入元素x
{
    int p = Locate(i-1);
    if(p==-1)
        return false;
    int q = avil;
    avil = elem[avil].link;
    elem[q].data = x;
    elem[q].link = elem[p].link;
    elem[p].link = q;
    return true;
}

template <class T>
bool StaticList<T>::Remove(int i)//删除第i个位置上元素
{
    int p = Locate(i-1);
    if(p == -1)
        return false;
    int q = elem[p].link;
    elem[p].link = elem[q].link;
    elem[q].link = avil;
    avil = q;
    return true;
}

template <class T>
bool StaticList<T>::IsEmpty()//判断表是否为空
{
    if(elem[0].link == -1)
        return true;
    else
        return false;
}

//template <class T>
//void StaticList<T>::output(int type=0)//按指定格式输出



#endif
int main()
{
    StaticList<int> list(10);
    list.Append(25);
    list.Append(92);
    list.Append(57);
    list.Append(36);
    list.Append(78);
    cout<<"在表尾追加5个结点："<<endl;
    list.output();
    cout << endl;


    cout<<"在3，1位置插入两个数："<<endl;
    list.Insert(3, 11);
    list.Insert(1, 49);
    list.output();
    cout << endl;

    cout<<"按照在静态链表中存储的顺序："<<endl;
    list.output(1);
    cout << endl;

    cout << "search 36: " << list.Search(36) << endl;
    cout << "search 11: " << list.Search(11) << endl;
    cout << "search 78: " << list.Search(78) << endl;
    cout << "search 50: " << list.Search(50) << endl;
    cout << endl;

    if (list.Remove(5))
    {
        cout << "Remove the 5th data:
";
        list.output();
    }
    cout << endl;

    list.Append(99);
    cout << "After Insert 99 in the rear:
";
    list.output();
    cout << endl;

    cout<<"按照在静态链表中存储的顺序："<<endl;
    list.output(1);
    cout << endl;
    return 0;
}

#运行结果#