C++实现的间接寻址

浏览数：20 / 时间：2015年06月08日

之前学过，数据描述方法中有公式化描述，链表描述，间接寻址和模拟指针，在之前已经将公式化描述和链表描述通过代码的形式展现出来了，现在贴出简介寻址的代码。其中简介寻址是融合了公式化描述和链表描述的有点，使用一个指针表来记录数据的位置，指针表相当于一个数组，这样在插入，删除的时候，其中的数据的位置并没有发生变化，而仅仅就是指针表的指向发生了变化，同时很多操作又能像公式化一样通过O（1）的复杂度进行操作。下面贴出我的代码：
其中的Exception.h请参考之前的代码：

#ifndef _INDIRECT_H_
#define _INDIRECT_H_

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

template<class T>
class IndirectList{
public:
    IndirectList(int MaxListSize=10);
    ~IndirectList();

    /*如果length=0，则链表为空*/
    bool isEmpty() const{return length == 0;}

    /*返回链表的长度*/
    int Length() const {return length;}

    /*看能否找到第k个元素，找到后给x赋值*/
    bool Find(int k,T& x) const;

    /*找到元素是x的元素的位置*/
    int Search(const T& x) const;

    /*从链表中删除第k个元素，并赋值给x*/
    IndirectList<T>& Delete(int k,T& x);

    /*在链表的第k个位置插入元素x*/
    IndirectList<T>& Insert(int k,const T& x);

    /*打印输出整个链表*/
    void print();
private:
    int length;  //链表的长度
    int MaxSize;  //链表的最大长度
    T **table;     //模拟指针表
};

template<class T>
IndirectList<T>::IndirectList(int MaxListSize)
{
    this->MaxSize = MaxListSize;  //获取最大长度
    table = new T*[MaxSize];  //初始化模拟指针
    length = 0;     //设置当前长度为0
}

template<class T>
IndirectList<T>::~IndirectList()
{
    for(int i = 0;i < length;i++)
        delete table[i];  //删除模拟指针
    delete [] table;
}

template<class T>
bool IndirectList<T>::Find(int k, T &x) const
{
    if(k < 1 || k > length)
        throw OutOfBounds();   //越界了

    x = *table[k-1];

    return true;
}

template<class T>
IndirectList<T>& IndirectList<T>::Delete(int k, T &x)
{
    if(Find(k,x)){
        for(int i = k;i < length;i++) {
            /*第k个元素之后的元素向前移动一个*/
            table[i-1] = table[i];
        }

        length--;  //当前长度减一
        return *this;
    }else{
        throw OutOfBounds();
    }
}

template<class T>
IndirectList<T>& IndirectList<T>::Insert(int k, const T &x)
{
    if(k < 0 || k > length)
        throw OutOfBounds();  //越界
    if(length == MaxSize)
        throw NoMem();  //已经到达最大长度了

    for(int i = length-1;i >= k;i--){
        /*第k个元素之后的元素向后移动一位*/
        table[i+1] = table[i];
    }

    /**
     * 新建一个间接地址
     */
    table[k] = new T;
    *table[k] = x;

    length++;

    return *this;
}

template<class T>
int IndirectList<T>::Search(const T &x) const
{
    for(int i = 0;i < length;i++){
        if(*table[i] == x){
            return i+1;
        }
    }

    return -1;
}

/**
 * 打印输出整个链表的内容
 */
template<class T>
void IndirectList<T>::print()
{
    for(int i = 0;i < length;i++){
        std::cout << *table[i] << " ";
    }

    std::cout << std::endl;
}

#endif