《数据结构与算法》期末练习题_2010-2011-1_带答案(6)

if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

}

return OK; }//Insert_Arc

20、假设有一个1000*1000的稀疏矩阵，其中1%的元素为非零元素，现要求哈希表作存储结构。试设计一个哈希表并编写相应算法，对给定的行值和列值确定矩阵元素在哈希表上的位置。

Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k {

h=2*(100*(row/10)+col/10); //作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key))

h=(h+1) 000;

if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash

分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).

G.arcs[i][j].adj=1;

G.arcnum++;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构与算法》期末练习题_2010-2011-1_带答案(6)在线全文阅读。