C++实现的间接寻址

2015/05/19 19:33
阅读数 77

之前学过,数据描述方法中有公式化描述,链表描述,间接寻址和模拟指针,在之前已经将公式化描述和链表描述通过代码的形式展现出来了,现在贴出简介寻址的代码。其中简介寻址是融合了公式化描述和链表描述的有点,使用一个指针表来记录数据的位置,指针表相当于一个数组,这样在插入,删除的时候,其中的数据的位置并没有发生变化,而仅仅就是指针表的指向发生了变化,同时很多操作又能像公式化一样通过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

代码相对来说比较简单,只不过其中比较难懂的就是
T** table,其中table指向的是T**,
table指向的是T,也就是数据T的地址,由此可知table指向的是数据的地址的地址,进行一个间接寻址,这个类似于计算机组成原理上的简介寻址。
好好体会一下,就会明白的!!加油!!

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部