文档章节

C++实现的间接寻址

陈洪波
 陈洪波
发布于 2015/05/19 19:33
字数 772
阅读 16
收藏 0

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

本文转载自:http://blog.csdn.net/hongbochen1223/article/details/44922481

陈洪波
粉丝 2
博文 76
码字总数 1552
作品 0
济南
程序员
私信 提问
关于C++内存利用和回收的问题

今晚上看了书上的一个从间接寻址表中删除元素的简短程序,程序是删除第K个元素 if (Find(k,x)){ for(int i = k; i < length;i++) table[i-1] = table[i]; length--; return *this;} 我不明白...

凌风羽化
2012/12/31
651
4
大神有话说之c++,还在迷茫的朋友可以来看一下

C++ 是一种中级语言,它是由 Bjarne Stroustrup 于 1979 年在贝尔实验室开始设计开发的。C++ 进一步扩充和完善了 C 语言,是一种面向对象的程序设计语言。C++ 可运行于多种平台上,如 Window...

悟空_b201
2018/05/30
0
0
__declspec(dllimport)

我相信写WIN32程序的人,做过DLL,都会很清楚declspec(dllexport)的作用,它就是为了省掉在DEF文件中手工定义导出哪些函数的一个方法。当然,如果你的DLL里全是C++的类的话,你无法在DEF里指...

开心303
2011/07/21
0
0
UIMA C++ SDK 2.4.0 发布

UIMA C++ SDK 2.4.0 发布,这是 UIMA 成为 Apache 组织顶级项目后发布的第一个版本。 发行说明:http://uima.apache.org/d/uimacpp-2.4.0/RELEASE_NOTES.html UIMA C++ 框架产生的目的是为了...

oschina
2012/11/22
864
0
C++ 能否成为你新的脚本语言?

一些背景 第一个我真正喜爱的编程语言是 C。我花了不少时间才找到它:当我还是一个孩子,我就开始在珍贵的ZX Spectrum上使用 Z80 汇编。那些日子是你能够真正掌握你的电脑的时候,你不需要苹...

oschina
2015/05/18
10.2K
46

没有更多内容

加载失败,请刷新页面

加载更多

通过微服务来正确实施SOA

对于组织来说,能够构建、发展和扩展大型应用程序是至关重要的, 但所涉及的挑战使其成为一项艰巨的任务。正因为如此, 微服务凭借能够将单个组件拆分成围绕特定业务功能的独立服务,已成为构建...

Linux就该这么学
9分钟前
1
0
从 Spark 到 Kubernetes — MaxCompute 的云原生开源生态实践之路

2019年5月14日,喜提浙江省科学技术进步一等奖的 MaxCompute 是阿里巴巴自研的 EB 级大数据计算平台。该平台依托阿里云飞天基础架构,是阿里巴巴在10年前做飞天系统的三大件之分布式计算部分...

阿里云官方博客
13分钟前
0
0
使用python来操作redis用法详解

1、redis连接 redis提供两个类Redis和StrictRedis用于实现Redis的命令,StrictRedis用于实现大部分官方的命令,并使用官方的语法和命令,Redis是StrictRedis的子类,用于向后兼容旧版本的red...

dragon_tech
13分钟前
1
0
给研发工程师的代码质量利器 | SOFAChannel#5 直播整理

> SOFA:Channel,有趣实用的分布式架构频道。 > > 本文根据 SOFAChannel#5 直播分享整理,主题:给研发工程师的代码质量利器 —— 自动化测试框架 SOFAActs。 > > 回顾视频以及 PPT 查看地址...

SOFAStack
15分钟前
0
0
段错误总结

https://blog.csdn.net/e_road_by_u/article/details/61415732 一、段错误是什么 一句话来说,段错误是指访问的内存超出了系统给这个程序所设定的内存空间,例如访问了不存在的内存地址、访问...

悲催的古灵武士
16分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部