谁对除留取余法比较熟悉的啊 - 数据结构与算法

楼主

问题点数：0 回复次数：10

谁对除留取余法比较熟悉的啊

可以举个例子告诉我吗

[[it] 本帖最后由 deleter 于 2008-7-30 19:09 编辑 [/it]]

搜索更多相关主题的帖子: 留取　例子　

第 2 楼

得分:0

是关于哈希表的吗？

无

第 3 楼

得分:0

我有代码,要不?

Fighting~~~~~~~~

第 4 楼

得分:0

[bo][un]很远的那颗星[/un] 在 2008-7-31 10:25 的发言：[/bo]

我有代码,要不?

好的

物理学家的问题在于他们总是试图用作弊的方法获得结果。
数学家的问题在于他们总是试图获得最幼稚的问题的结果。
软件测试工程师的问题在于他们总是试图用作弊的方法获得最幼稚的问题的结果。

第 5 楼

得分:0

[bo][un]blueboy82006[/un] 在 2008-7-30 21:38 的发言：[/bo]

是关于哈希表的吗？

当然是哈希表

第 6 楼

得分:0

给我一份把！！谢谢了

第 7 楼

得分:0

除留余数法(division)
设散列表中允许的地址数为 m ,取一个不大于 m ,但最接近或等于 m 的质数 p 作为除数,用 hash(key) = key % p 把关键码转换成散列地址.

Fighting~~~~~~~~

第 8 楼

得分:0

代码,以前写的,测试函数被我改了几次,那时我主要也是学习,所以可能对我作用大一点,对大家可能没什么用,就不贴了,下面先贴HashTable.h ,再楼下给出它的实现代码.

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include<iostream>
const int defaultsize = 100;
enum KindOfStatus{ Active,Empty,Deleted};
template<class E,class K>
struct ChainNode
{
    E data;
    ChainNode<E,K> *link;
};
template<class E,class K>
class HashTable
{
private:
    int divisor;                                   //除数，必须是质数
    int CurrentSize,TableSize;                 //当前桶数,最大容量（桶的个数）
    ChainNode<E,K> *ht;                         //散列表存储数组
    KindOfStatus *info;                         //状态数组
    ChainNode<E,K> *FindPos(const K k1);     //散列
    int operator ==(E &e1){ return *this ==e1;}
    int operator !=(E& e1){ return *this !=e1;}
public:
    HashTable(int d,int sz=defaultsize);
    HashTable<E,K>& operator = (const HashTable<E,K> &ht2);
    bool Search(const K k1,E& e1);
    bool Insert(const E& e1);
    bool Remove(const K k1,E& el);
    void MakeEmpty();
    ~HashTable()
    {
        delete [ ]ht; delete [ ]info;
    }
};

Fighting~~~~~~~~

第 9 楼

得分:0

二次探查就没写了.

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include "HashTable.h"
template<class E,class K>
HashTable<E,K>::HashTable(int d,int sz)
{
    divisor = d;
    TableSize = sz;
    CurrentSize = 0;
    ht = new E[TableSize];
    info = new KindOfStatus[TableSize];
    for (int i=0;i<TableSize;i++)
        info[i] = Empty;
};
//使用线性探查法的搜索法
template<class E,class K>
ChainNode<E,K> *HashTable<E,K>::FindPos(const K k1)
{
    //搜索关键码为K1的元素
    int i = k1%divisor;               //计算初始桶号
    int j = i;                    //j是检测下一空桶下标
    do
    {
        if (info[j] ==Empty ||info[j] ==Active &&ht[j] ==k1) return j;   //找到
        j = (j+1) % TableSize;
    }
    while (j != i);
    return j;
}
template<class E,class K>
bool HashTable<E,K>::Search(const K k1,E &e1)
{
    int i = FindPos(k1);      //搜索
    if (info[i] != Active || ht[i] != k1) return false;
    e1 = ht[i];
    return true;
}

//清除散列表
template<class E,class K>
void HashTable<E,K>::MakeEmpty()
{
    for (int i=0;i<TableSize;i++)
        info[i] = Empty;
    CurrentSize = 0;
}

//重载函数，复制一个散列表ht2
template<class E,class K>
HashTable<E,K>& HashTable<E,K>::operator = (const HashTable<E,K>& ht2)
{
    if(this !=&ht2)
    {
        delete[ ]ht;  delete [ ]info;
        TableSize = ht2.TableSize;
        ht = new E[TableSize];  info = new KindOfStatus[TableSize];
        for(int i=0;i<TableSize;i++)
        {
            ht[i] = ht2.ht[i];             //从源散列表向目的散列表传送
            info[i] = ht2.info[i];
        }
        CurrentSize = ht2.CurrentSize;        //传送当前元素个数
    }
    return *this;                     //返回目标散列表结构指针
};
template<class E,class K>
bool HashTable<E,K>::Insert(const E& e1)
{
    K k1 = e1;            //重载函数，抽取关键码
    int i=FindPos(k1);    //计算桶号
    if (info[i] != Active)  //该桶空，放新元素
    {
        ht[i] = e1;  info[i] = Active;
        CurrentSize++;
        return true;
    }
    if (info[i] ==Active && ht[i] ==e1)
    {
        std::cout<<"表中已有此元素，不能插入！"<<std::endl;
        return false;
    }
    std::cout<<"表已满，不能插入！"<<std::endl;
    return false;
}
template<class E,class K>
bool HashTable<E,K>::Remove(const K k1,E &e1)
{
    int i = FindPos(k1);
    if(info[i] == Active){info[i] =Deleted;  CurrentSize --;   return true;}
    else return false;
}

Fighting~~~~~~~~

第 10 楼

得分:0

/* Note:Your choice is C IDE */
#include "stdio.h"
#define MAX 100
#define NULLKEY -1   /*定义空关键字值*/
#define DELKEY -2    /*定义被删关键字值*/
typedef int keytype;
typedef struct node
{
    keytype key;
    char data;
    int count;      /*探查次数域*/
}HashTable[MAX];
void insertHT(HashTable ha,int n,keytype k,int p)
{
    int i,adr;
    adr=k%p;
    if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)
    {
        ha[adr].key=k;
        ha[adr].count=1;
    }
    else
    {
        i=1;
        do
        {
            adr=(adr+1)%p;
            i++;
        }while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
        ha[adr].key=k;
        ha[adr].count=i;    /*和冲突数据移动后的位置*/
    }
    n++;
}
void creatHT(HashTable ha,keytype x[],int n,int m,int p)
{
    int i,n1=0;
    for(i=0;i<m;i++)
    {
        ha[i].key=NULLKEY;
        ha[i].count=0;
    }
    for(i=0;i<n;i++)
    insertHT(ha,n1,x[i],p);
}
int searchHT(HashTable ha,int p,keytype k)
{
    int i,adr;
    adr=k%p;
    while(ha[adr].key!=NULLKEY && ha[adr].key!=k)
    {
        i++;
        adr=(adr+1)%p;
    }
    if(ha[adr].key==k)
    return adr;
    else return -1;
}
int deleteHT(HashTable ha,int p,int k,int n)
{
    int adr;
    adr=searchHT(ha,p,k);
    if(adr!=-1)
    {
        ha[adr].key=DELKEY;
        n--;
        return 1;
    }
    else return 0;
}
void displayHT(HashTable ha,int n,int m)
{
    int i;
    printf("哈希表地址:\t");
    for(i=0;i<m;i++)
    printf("%3d",i);printf("\n");
    printf("哈希表关键字:\t");
    for(i=0;i<m;i++)
    if(ha[i].key==NULLKEY || ha[i].key==DELKEY)
    printf("   ");
    else
    printf("%3d",ha[i].key);printf("\n");
    printf("探查次数:\t");
    for(i=0;i<m;i++)
    if(ha[i].key==NULLKEY ||ha[i].key==DELKEY)
    printf("   ");
    else
    printf("%3d",ha[i].count);
}
void main()
{
    int x[]={16,74,60,43,54,90,46,31,29,88,77};
    int n=11,m=13,p=13,i,k=29;
    HashTable ha;
    creatHT(ha,x,n,m,p);
    printf("\n");displayHT(ha,n,m);
    i=searchHT(ha,p,k);
    if(i!=-1)
    printf("\nha[%d].key=%d\n",i,k);
    else
    printf("\n未找到%d\n",k);
    k=77;
    printf("删除关键字%d\n",k);
    deleteHT(ha,p,k,n);
    displayHT(ha,n,m);
    i=searchHT(ha,p,k);
    if(i!=-1)
    printf("ha[%d].key=%d\n",i,k);
    else
    printf("\n未找到%d\n",k);
    printf("插入关键字%d\n",k);
    insertHT(ha,n,k,p);
    displayHT(ha,n,m);printf("\n");
}

抽刀断水水更流，举杯消愁愁更愁。