刚回家两天，还没歇停休息下，就开始马不停蹄的上车训练..........车开得越来越快，加速和飞车的感觉真的比较爽——后果是教练在旁边不停碎烦：慢一点慢一点，控制速度！。。。被教练骂了.....9号考车，还是夜考，黑不咙咚的估计可以混过去.................

 

考完车，拿到驾照，嘿嘿，那时候就开车到处玩!!!    kevin貌似对我新手开车出去心惊肉跳的........嘿嘿~~~

 

 

题目4 Hash表问题(有的书说的是 散列表，好像貌似可能就是同一个东西）；里面就改了个find的函数，其他就是代码重用，偷懒抄来的............

1． 问题描述：假设有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求对其非零元素进行散列存储，使之能够按元素的行、列值存取元素（即元素的行、列值联合为元素的关键字），试采用除留余数法构造散列函数和线性探查法处理冲突，分别设计出建立散列表和查找散列表的算法。
2． 实现设计：
①由题意可知，整个稀疏矩阵中非零元素的个数为100个。为了散列存储这100个非零元素，需要使用一个称为散列表的一维数组，该数组中元素的类型为：
                 
 Struct DataType
                     {
                       int  row;  //存储非零元素行下标
                       int  col;   //存储非零元素列下标
                       float  val;  //存储非零元素值
                    }；
    ②假定用H[m]表示这个散列表，其中m为散列表的长度，若取装载因子为0.8左右，则令 M=127 为宜(127为质数)；
    ③按照题目要求，需根据稀疏矩阵非零元素的行下标和列下标存取散列表中的元素，所以每个元素的行下标和列下标共同组成元素的关键字。假定用x表示一个非零元素，按除留余数法构造散列函数，并考虑尽量让得到的散列地址均匀分布，可以采用如下的散列函数：
Hash(x)=(13*x.row+17*x.col) % m.

3. 附录：程序清单如下：

#include <iostream.h>
typedef char ElemType;
#include "HashTable.h"

void main(void)
{
 HashTable A(127);
 DataType *a=new DataType[];
 a[0].row=2;a[0].col=22;a[0].value='H';
 a[1].row=34;a[1].col=21;a[1].value='E';
 a[2].row=56;a[2].col=34;a[2].value='R';
 a[3].row=64;a[3].col=11;a[3].value='T';
 a[4].row=98;a[4].col=78;a[4].value='G';
 a[5].row=76;a[5].col=97;a[5].value='D';
 a[6].row=67;a[6].col=54;a[6].value='E';
 a[7].row= 4;a[7].col=87;a[7].value='A';
 a[8].row=2;a[8].col =22;a[8].value='e';

 DataType item;

 int n=9;
 for(int i=0;i<n;i++)A.Insert(a[i]);

 for(i=0;i<n;i++)
 {
  int j=A.Find(a[i]);
  if(j>0)
  {
   item=A.GetValue(j);
   cout<<"j="<<j<<" "<<"ht[]="<<item.value<<endl;
  }
 }

 DataType x;
 cout<<"请输入数据元素的row=";cin>>x.row;
 cout<<"请输入数据元素的col=";cin>>x.col;
 cout<<"请输入数据元素的value=";cin>>x.value;

 int k=A.IsIn(x);
 if(k==1)cout<<x.value<<"在哈希表中!"<<endl;
 else cout<<x.value<<"不在哈希表中!"<<endl;
}

执行测试程序，测试结果如下：
j=19 ht[]=H
j=37 ht[]=E
j=36 ht[]=R
j=3 ht[]=T
j=60 ht[]=G
j=97 ht[]=D
j=11 ht[]=E
j=7 ht[]=A
j=20 ht[]=e
请输入数据元素的row=4
请输入数据元素的col=87
请输入数据元素的value=A
A在哈希表中!

 

j=19 ht[]=H
j=37 ht[]=E
j=36 ht[]=R
j=3 ht[]=T
j=60 ht[]=G
j=97 ht[]=D
j=11 ht[]=E
j=7 ht[]=A
j=20 ht[]=e
请输入数据元素的row=4
请输入数据元素的col=65
请输入数据元素的value=J
J不在哈希表中!

 

 

 

哈希表头文件"HashTable.h"程序代码：
enum KindOfItem {Empty, Active, Deleted};
struct DataType      
{
 int row;       //行号
 int col;       //列号
 ElemType value;                     //元素值
};

struct HashItem
{
 DataType data;
 KindOfItem info;

 HashItem(KindOfItem i = Empty): info(i){}
 HashItem(const DataType &D, KindOfItem i = Empty): data(D), info(i){}
 int operator ==(HashItem &a)
  {return data.value == a.data.value;}
 int operator !=(HashItem &a)
  {return data.value != a.data.value;}
};

class HashTable
{
private:
 HashItem *ht;      //哈希表数组
 int TableSize;      //哈希表的长度（即m）
 int currentSize;     //当前的表项个数
public:
 HashTable(int m);     

 ~HashTable(void)     
  {delete []ht;}

 int Find(const DataType &x)const; 

 int Insert(const DataType &x);  
 int Delete(const DataType &x);  
 int IsIn(const DataType &x)   
  {int i = Find(x); return i >= 0 ? 1: 0;}
 DataType GetValue(int i)const  
  {return ht[i].data;}
};

//哈希表类实现
HashTable::HashTable(int m)    
{
 TableSize = m;      //置哈希表长度
 ht = new HashItem[TableSize];  //申请动态数组空间
 currentSize = 0;     //置初始的当前表项个数
}

int HashTable::Find(const DataType &x)const    
{
 int i=(13*x.row+17*x.col)%TableSize;
 int j = i;
 while(ht[j].info == Active && ht[j].data.value != x.value ) //说明存在冲突
 {
  j = (j + 1) % TableSize;  //用哈希冲突方法继续查找
  if(j == i) return -TableSize;//说明已遍历整个哈希表未找到且表已满
 }
 
 if(ht[j].info == Active)
  return j;       //找到，返回正值
 else
  return -j;       //未找到，返回负值

}

int HashTable::Insert(const DataType &x)
{
 int i = Find(x);       //调用Find(x)

 if(i > 0) return 0;      //数据元素x已经存在
 else if(i != -TableSize) //数据元素x不存在且哈希表未满
 {
  ht[-i].data = x;     //数据元素赋值
  ht[-i].info = Active;    //置活动标记
  currentSize++;      //当前表项个数加1
  return 1;       //返回插入成功状态
 }
 else return 0;       //返回插入失败状态
}

int HashTable::Delete(const DataType &x) //删除
{
 int i = Find(x);       //调用Find(x)

 if(i >= 0)
 {
  ht[i].info = Deleted;    //置删除标记
  currentSize--;      //当前表项个数减1
  return 1;       //返回删除成功状态
 }
 else return 0;       //返回删除失败状态
}