C++数据结构--.哈希表独立表链地址法迭代器的设计

川长思鸟来 2021-11-17 02:28 222阅读 0赞

**1.哈希表独立表链地址法中迭代器的设计  
 \*hashTable:哈希表对象的地址  
 \*currentBucket：迭代器遍历的当前桶的索引  
\*currentLoc:当前哈希表元素  
例如：虚线为遍历元素顺序  
![20130805133025765][]  
  
  
  
  
实现代码：  
Tips:  
可以把哈希表独立表链地址法的结构看成二维数组  
  
 \#ifndef hashIterator\_H  
\#define hashIterator\_H  
  
class hashIterator  
\{  
friend class hashTable<T,hashFun>;  
private:  
hashTable<T,hashFun> \*ptable; //哈希表对象地址   
size\_t row;//迭代器遍历的当前行的索引   
typename list<T>::iterator it; //当前迭代器   
hashIterator(hashTable \*pt , size\_t r ,typename list<T>::iterator i ):**

**ptable(pt) , row(r) , it(i)\{\}**

**void nextRow()// 返回哈希表下一行非空的第一个元素   
\{   
for(int i=row+1;i<ptable->rows;i++)//从下一行开始扫描，直到第一个元素非空   
\{   
if(!ptable->table\[i\].empty())  
\{   
row=i;  
it=ptable->table\[i\].begin(); //返回第一个元素   
return;  
\}  
\}  
  
row=-1; //返回end()   
\}  
public:  
hashIterator()\{\}  
  
bool operator==(const hashIterator &rh)//等于操作符   
\{   
if(row==-1&&rh.row==-1) // 定义row==-1为end()   
 return true;  
else if(row==rh.row) //如果不是end()，则需比较迭代器   
 return it==rh.it;  
else //定义不同行时不具有比较性   
 return false;  
\}  
  
bool operator!=(const hashIterator &rh)//不等于操作符   
\{   
return !operator==(rh);  
\}  
  
hashIterator& operator++() //前置++   
\{   
if(row==-1) //定义end（）不可++   
 \{   
cerr<<"end(),can't ++"<<endl;  
return \*this;  
\}  
  
 it++;  
if(it==ptable->table\[row\].end())   
nextRow();  
  
return \*this;   
\}  
  
  
  
hashIterator operator++(int) //后置++   
\{   
hashIterator tem(\*this);  
\++\*this;  
return tem;  
\}  
  
T& operator\*() //解引用操作符   
\{   
if(row==-1)  
 cerr<<"can't derefference "<<endl;  
else  
 return \*it;  
\}  
\};  
  
  
\#endif  
  
  
  
  
哈希表迭代器的测试详见**

### [C++数据结构--.哈希表线性探测开放寻址法与独立表链地址法][C_--.] ###

[20130805133025765]: /images/20211116/b59bece723b04a018ce86e9820da916d.png
[C_--.]: http://blog.csdn.net/piniheaven/article/details/9766529