版权声明:您好,转载请留下本人博客的地址,谢谢 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指向的是数据的地址的地址,进行一个间接寻址,这个类似于计算机组成原理上的简介寻址。
好好体会一下,就会明白的!!加油!!