C++实现的间接寻址

简介: 版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/44922481 之前学过,数据描述方法中有公式化描述,链表描述,间接寻址和模拟指针,在之前已经将公式化描述和链表描述通过代码的形式展现出来了,现在贴出简介寻址的代码。
版权声明:您好,转载请留下本人博客的地址,谢谢 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指向的是数据的地址的地址,进行一个间接寻址,这个类似于计算机组成原理上的简介寻址。
好好体会一下,就会明白的!!加油!!

目录
相关文章
|
定位技术 C++
C++实现俄罗斯方块(附代码)
C++实现俄罗斯方块(附代码)
C++实现俄罗斯方块(附代码)
|
机器学习/深度学习 C++
C++实现实现逆时针旋转矩阵
C++实现实现逆时针旋转矩阵
C++实现实现逆时针旋转矩阵
|
编译器 C++ 容器
【C++要笑着学】迭代器适配器 | 内嵌类型实现反向迭代器 | 迭代器萃取
上一章讲解 list 模拟实现时,我们简单的提到了反向迭代器,我们说反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式(配接器模式)。当时我们做的是简单的了解,本章我们就来探讨这一部分的知识。
151 1
【C++要笑着学】迭代器适配器 | 内嵌类型实现反向迭代器 | 迭代器萃取
|
算法 区块链 C++
【C++要笑着学】vector 核心框架接口的模拟实现 | 基于STL3.0版本的简化vector | 浅谈迭代器失效问题(二)
STL 的源代码整体考虑的东西比较多,还要考虑和其他地方的结合,因此整体的设计是比较复杂的。基于这一系列原因,我们会以简单的形式去实现其核心框架接口,方便去学习 vector。
111 1
【C++要笑着学】vector 核心框架接口的模拟实现 | 基于STL3.0版本的简化vector | 浅谈迭代器失效问题(二)
|
存储 C++
C++异常处理机制由浅入深, 以及函数调用汇编过程底层刨析. C++11智能指针底层模拟实现
C++异常处理机制由浅入深, 以及函数调用汇编过程底层刨析. C++11智能指针底层模拟实现
C++异常处理机制由浅入深, 以及函数调用汇编过程底层刨析. C++11智能指针底层模拟实现
|
存储 Linux C语言
生产者消费者模式保姆级教程 (阻塞队列解除耦合性) 一文帮你从C语言版本到C++ 版本, 从理论到实现 (一文足以)
生产者消费者模式保姆级教程 (阻塞队列解除耦合性) 一文帮你从C语言版本到C++ 版本, 从理论到实现 (一文足以)
生产者消费者模式保姆级教程 (阻塞队列解除耦合性) 一文帮你从C语言版本到C++ 版本, 从理论到实现 (一文足以)
|
设计模式 安全 定位技术
C++从面试常考实现特殊类到单例模式的实现
C++从面试常考实现特殊类到单例模式的实现
C++从面试常考实现特殊类到单例模式的实现
|
存储 Java 应用服务中间件
线程池设计, 从简单的我们平常设计线程池图解,到生活中的类似线程池的处理现实场景, 到简单的C++模拟nginx写的单链表组织工作队列的简单线程池实现 + nginx 部分源码刨析
线程池设计, 从简单的我们平常设计线程池图解,到生活中的类似线程池的处理现实场景, 到简单的C++模拟nginx写的单链表组织工作队列的简单线程池实现 + nginx 部分源码刨析
线程池设计, 从简单的我们平常设计线程池图解,到生活中的类似线程池的处理现实场景, 到简单的C++模拟nginx写的单链表组织工作队列的简单线程池实现 + nginx 部分源码刨析
如何用c++实现异常处理
如何用c++实现异常处理
如何用c++实现异常处理
|
存储 算法 C++
分块刨析从函数原型到分块实现C++STL(vector)
分块刨析从函数原型到分块实现C++STL(vector)
分块刨析从函数原型到分块实现C++STL(vector)