很有道理 2016-11-04 05:14 采纳率: 0%
浏览 878

hashing表如何遍历输出表中的数据呢??

//Dictionary.h
#pragma once
#include
#include
using namespace std;
template
class Dictionary {
private:
void operator =(const Dictionary&) {}
Dictionary(const Dictionary&) {}

public:
Dictionary() {}
virtual ~Dictionary() {}
//virtual void clear() = 0;
virtual void insert(const Key& k, const E& e) = 0; //
//virtual E remove(const Key& k) = 0;
//virtual E removeAny() = 0;
virtual E find(const Key& k)const = 0; //
virtual int size() = 0; //
};

template
class KVpair {
private:
Key k;
E e;
public:
KVpair() {}
KVpair(Key kval,E eval)
{
k = kval; e = eval;
}
KVpair(const KVpair&o)
{
k = o.k; e = o.e;
}
void operator=(const KVpair&o)
{
k = o.k; e = o.e;
}

Key key() { return k; }
void setKey(Key ink) { k = ink; }
E value() { return e; }

};

template
class hashdict :public Dictionary {
private:
KVpair*HT;
int M;
int currcnt;
Key EMPTYKEY;

int p(Key K,int i)const 
{return i;}             //linear probing

int h(int x)const { return x%M; }
int h(char*x)const {
    int i, sum;
    for {sum = 0, i = 0; x[i] != '\0'; i++ }sum += (int)x[i];
    return sum%M;
}

void hashInsert(const Key&k, const E&e) {
    int home;
    int pos = home = h(k);
    for (int i = 1; EMPTYKEY != (HT[pos]).key(); i++) {
        Assert(k != (HT[pos]).key(), "Duplicates not allowed");
        pos = (home + p(k, i)) % M;
    }
    KVpair<Key, E>temp(k, e);
    HT[pos] = temp;
}
E hashSearch(const Key&k)const {
    int home;
    int pos = home = h(k);
    for (int i = 1; (k != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key()); i++)
        pos = (home + p(k, i)) % M;
    if (k == (HT[pos]).key())
        return (HT[pos]).value();
    else return NULL;
}

public:
hashdict(int sz, Key k) {
M = sz;
EMPTYKEY = k; //"k"defines an empty slot
currcnt = 0;
HT = new KVpair[sz];
for (int i = 0; i < M; i++)
(HT[i]).setKey(EMPTYKEY); //setKey
}

~hashdict() { delete HT; }

E find (const Key&k)const
{
    return hashSearch(k);
}
int size() { return currcnt; }

void insert(const Key&k, const E&it) {
    Assert(currcnt < M, "Hash table is full");
    hashInsert(k, it);
    currcnt++;
}

};
void Assert(bool val, string s) {
if (!val) {
cout << "Assertion Failed: " << s << endl;
exit(-1);
}
}

//hashList.cpp
#include "stdafx.h"
#include "Dictionary.h"
#include
using namespace std;

int main()
{
hashdicthashlist(5, 0);
hashlist.insert(1, 1);
hashlist.insert(2, 1);
hashlist.insert(3, 1);
hashlist.insert(4, 1);
hashlist.insert(55, 2);
int i = hashlist.size();
return 0;
}

  • 写回答

1条回答 默认 最新

  • 很有道理 2016-11-04 05:17
    关注

    还有删除函数要怎么写(通过改写或者添加Dictionary里边的方法),最终使墓碑标记可以正常工作

    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB动图的问题
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名