间接寻址（Indirect Addressing）

间接寻址（indirect addressing）是公式化描述和链表描述的组合。采用这种描述方法，可以保留公式化描述方法的许多优点——可以根据索引在O(1)的时间内访问每个元素、可采用二叉搜索方法在对数时间内对一个有序表进行搜索等等。与此同时，也可以获得链表描述方法的重要特色——在诸如插入和删除操作期间不必对元素进行实际的移动。因此，大多数间接寻址链表操作的时间复杂性都与元素的总数无关。
IndirectAdd.h

#ifndef INDIRECTADD_H
#define INDIRECTADD_H
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

template <typename T>
class IndirectList;

template <typename T>
ostream & operator << (ostream & out, const IndirectList<T> & Inl);

template<typename T>
class IndirectList{
    friend ostream & operator << <T> (ostream & out,const IndirectList<T> & InL);
public:
    IndirectList(int MaxListSize = 10);
    ~IndirectList();
    bool IsEmpty() const {return length == 0;}
    int Length() const {return length;}
    bool Find(int k, T & x) const;
    int Search(const T & x) const;
    IndirectList<T> & Delete(int k,T & x);
    IndirectList<T> & Insert(int k, const T & x);
    void Output(ostream & out) const;
private:
    T ** table;
    int length;
    int MaxSize;
};

template<typename T>
IndirectList<T>::IndirectList(int MaxListSize)
{
    MaxSize = MaxListSize;
    table = new T * [MaxSize];
    length = 0;
}
template<typename T>
IndirectList<T>::~IndirectList()
{
    for (int i = 0; i < length;i++)
        delete table[i];
    delete [] table;
}
template<typename T>
bool IndirectList<T>::Find(int k, T & x) const
{
    if (k < 0 || k >= length) return false;
    x  = *table[k];
    return true;
}
template<typename T>
int IndirectList<T>::Search(const T &x) const
{
    for(int i=0; i < length;i++)
    {
        if (*table[i] == x)
            return i;
    }
    return -1;
}
template<typename T>
IndirectList<T> & IndirectList<T>::Delete(int k, T &x)
{
    if (Find(k,x))
    {
        for (int i = k ; i < length;i++)
            table[i-1] = table[i];
        length--;
        return *this;
    }
    else
        cout<<"OutOfBounds"<<endl;
}

template<typename T>
IndirectList<T> & IndirectList<T>::Insert(int k, const T &x)
{
    if (k < 0 || k > length)
        cout<<"OutOfBounds"<<endl;
    if (length == MaxSize)
        cout<<"NoMemory"<<endl;
    for(int i = length-1; i >= k; i--)
    {
        table[i+1] = table[i];
    }
    table[k] = new T;
    *table[k] = x;
    length++;
    return *this;
}
template<typename T>
void IndirectList<T>:: Output(ostream & out) const
{
    for (int i = 0; i < length;i++)
        out << *table[i]<<" ";
}
template<typename T>
ostream & operator << (ostream & out, const IndirectList<T> & Inl)
{
    Inl.Output(out);
    return out;
}
#endif

AppEx.cpp

#include <iostream>
#include "IndirectAdd.h"

using namespace std;

int  main()
{
    IndirectList<int> bob(10);
    cout<<bob.IsEmpty()<<endl;
    bob.Insert(0,24);
    cout<<bob<<endl;
    return 0;
}