# 数据描述 3 – 间接寻址 & 模拟指针

### 间接寻址

#### 基本概念

#ifndef INDRECTLIST_H_ #define INDRECTLIST_H_ #include<iostream>  template<class T> class IndrectList{ private:     T **table;      // 一维T类型指针数组     int length, MaxSize; public:     IndrectList(int MaxListSize = 10);     ~IndrectList();     bool isEmpty() const{ return length == 0; }     int Length() const { return length; }     bool Find(int k, T&x)const;     int Search(const T& x)const;     IndrectList<T>& Delete(int k, T& x);     IndrectList<T>& Insert(int k, const T& x);     void Output(std::ostream& out)const; };  #endif

#### 操作

template<class T> IndrectList<T>::IndrectList(int MaxListSize){     MaxSize = MaxListSize;     table = new T *[MaxSize];     length = 0; }  template<class T> IndrectList<T>::~IndrectList(){     // 删除表     for (int i = 0; i < length; i++)         delete table[i];     delete[] table; }

template<class T> bool IndrectList<T>::Find(int k, T& x)const{     if (k<1 || k>length)         return false;     x = *table[k - 1];     return true; }  template<class T> int IndrectList<T>::Search(const T& x)const{     // 返回x所处位置，如果没有则返回0；     for (int i = 0; i < length; i++){         if (*table[i] == x)             return ++i;     }     return 0; }

template<class T> IndrectList<T>& IndrectList<T>::Delete(int k, T&x){     if (Find(k, x)){         // 向前移动指针         for (int i = k; i < length; i++)             table[i - 1] = table[i];         length--;         return *this;     } else      throw OutOfBounds(); }

template<class T> IndrectList<T>& IndrectList<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--)         table[i + 1] = table[i];     table[k] = new T;     *table[k] = x;     length++;     return *this; }

### 模拟指针

#ifndef SIMPOINTER_H_ #define SIMPOINTER_H_  template<class T> class SimNode{     T data;     int link; };  template<class T> class SimSpace{ private:     int NumberOfNodes, first;     SimNode<T>*node;    // 节点数组 public:     SimSpace(int MaxSpaceSize = 100);     ~SimSpace(){ delete[] node; }     // 分配一个节点     int Allocate();     // 释放节点i     void Deallocate(int& i); };  #endif

#### SimSpace的操作

template<class T> SimSpace<T>::SimSpace(int MaxSpaceSize){     NumberOfNodes = MaxSpaceSize;     node = new SimNode<T>[NumberOfNodes];     // 初始化可用空间表，创建一个节点链表     for (int i = 0; i < NumberOfNodes-1; i++)         node[i].link = i + 1;     // 链表的最后一个节点     node[NumberOfNodes - 1].link = -1;     // 链表的第一个节点     first = 0; }  template<class T> int SimSpace<T>::Allocate(){     // 分配一个自由节点     if (first == -1)         throw NoMem();     int i = first;     first = node[i].link;    // first 指向下一个自由节点     return i; }  template<class T> void SimSpace<T>::Deallocate(int & i){     // 释放节点     // 使i成为可用空间表的第一个节点     node[i].link = first;     first = i;     i = -1; }

template<class T> SimSpace<T>::SimSpace(int MaxSpaceSize) {      // 使用两个可用空间表的构造函数     NumberOfNodes = MaxSpaceSize;     node = new SimNode<T> [NumberOfNodes];     // 初始化可用空间表     firstl = 0;     first2 = -1; }  template<class T> int SimSpace<T>::Allocate() {      // 分配一个自由节点     if (first2 == -1) {// 第2个表为空     if (firstl == NumberOfNodes) throw NoMem();     return firstl++;}     // 分配链表中的第一个节点     int i = first2;     first2 = node[i].link;     return i; }

### 描述方法的比较

1. 使用间接寻址与使用链表描述所需要的空间大致相同，二者都比使用公式化描述所需要的空间更多。
2. 链表描述和间接寻址，在执行链表的插入和删除操作所需要的时间复杂性都与链表元素本身的大小无关；相反，使用公式化描述时，插入和删除操作的复杂性与元素的本身大小呈 线性关系
3. 公式化描述和间接寻址，在确定表的长度以及访问表中第k个元素所需要的时间复杂性均为\$/theta(1)\$;而使用链表描述，这两种操作的时间复杂性分别是\$/theta(length)\$和\$O(k)\$。
4. 间接寻址比较适合这样的应用：表元素本身很大，较频繁地进行插入、删除操作以及确定表的长度、访问第k个元素。
5. 如果线性表本身已经按序排列，那么使用公式化描述或间接寻址进行搜索所需要时间均为\$O(logn)\$,而使用链表描述时，所需要的时间是\$O(n)\$.