C++實作的間接尋址

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/44922481

之前學過，資料描述方法中有公式化描述，連結清單描述，間接尋址和模拟指針，在之前已經将公式化描述和連結清單描述通過代碼的形式展現出來了，現在貼出簡介尋址的代碼。其中簡介尋址是融合了公式化描述和連結清單描述的有點，使用一個指針表來記錄資料的位置，指針表相當于一個數組，這樣在插入，删除的時候，其中的資料的位置并沒有發生變化，而僅僅就是指針表的指向發生了變化，同時很多操作又能像公式化一樣通過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指向的是資料的位址的位址，進行一個間接尋址，這個類似于計算機組成原理上的簡介尋址。

好好體會一下，就會明白的！！加油！！