《算法》第三章部分程序 part 4
2024-04-16 23:55:44
▶ 书中第三章部分程序，加上自己补充的代码，包括散列表、线性探查表
● 散列表
package package01; import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.SequentialSearchST;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key, Value>
{
private static final int INIT_CAPACITY = 4; // 默认构造函数参数
private int n; // 待插入元素数
private int m; // 散列表尺寸
private SequentialSearchST<Key, Value>[] st; // 散列表 public class01()
{
this(INIT_CAPACITY);
} public class01(int capacity)
{
m = capacity;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} private void resize(int capacity)
{
class01<Key, Value> temp = new class01<Key, Value>(capacity);
for (int i = 0; i < m; i++)
{
for (Key key : st[i].keys())
temp.put(key, st[i].get(key));
}
m = temp.m;
n = temp.n;
st = temp.st;
} public boolean contains(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % m;
} public Value get(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
return st[hash(key)].get(key);
} public void put(Key key, Value val)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
if (val == null)
{
delete(key);
return;
}
if (n >= 10 * m) // 平均链表长度不小于 10，扩容
resize(2 * m);
int i = hash(key);
if (!st[i].contains(key))
n++;
st[i].put(key, val);
} public void delete(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
if (!contains(key))
return;
int i = hash(key);
if (st[i].contains(key))
n--;
st[i].delete(key);
if (m > INIT_CAPACITY && n <= 2 * m) // 平均链表长度小于 2，缩容
resize(m / 2);
} public Iterable<Key> keys()
{
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++)
{
for (Key key : st[i].keys())
queue.enqueue(key);
}
return queue;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}
● 线性探查表
package package01; import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key, Value>
{
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private Key[] keys;
private Value[] vals; public class01()
{
this(INIT_CAPACITY);
} public class01(int capacity)
{
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} private void resize(int capacity)
{
class01<Key, Value> temp = new class01<Key, Value>(capacity);
for (int i = 0; i < m; i++)
{
if (keys[i] != null)
temp.put(keys[i], vals[i]);
}
m = temp.m;
keys = temp.keys;
vals = temp.vals; } public boolean contains(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % m;
} public Value get(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) // 表荷载不会超过 1/2，所以不会绕圈
{
if (keys[i].equals(key))
return vals[i];
}
return null;
} public void put(Key key, Value val)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
if (val == null)
{
delete(key);
return;
}
if (n >= m / 2) // 荷载超过一半了，扩容
resize(2 * m);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % m)
{
if (keys[i].equals(key))
{
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
} public void delete(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
if (!contains(key))
return;
int i = hash(key);
for (; !key.equals(keys[i]); i = (i + 1) % m); // 找到目标元素
keys[i] = null; // 删除目标元素
vals[i] = null;
for (i = (i + 1) % m; keys[i] != null; i = (i + 1) % m) // 在下一个 null 之前，所有元素重新插入
{
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
}
n--;
if (n > 0 && n <= m / 8) // 荷载小于 1/8， 缩容
resize(m / 2);
} public Iterable<Key> keys()
{
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++)
{
if (keys[i] != null)
queue.enqueue(keys[i]);
}
return queue;
}
private boolean check()
{
if (m < 2 * n) // 检查容量
{
System.err.println("\n<check> m < 2 * n.\n");
return false;
}
for (int i = 0; i < m; i++) // 检查 hash
{
if (keys[i] == null)
continue;
if (get(keys[i]) != vals[i])
{
System.err.println("\n<check> hash error at i = ", i, ", key[i] = ", get(keys[i]), ", val[i] = ", vals[i], ".\n");
return false;
}
}
return true;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}
最新文章
- SpringMVC拦截器
- div垂直居中的几种方法
- 基于现有数据库的Code First模式迁移更新数据库
- IOS第六天(3:scrollView 图片轮播器)
- 使用CXF创建REST WEBSERVICE
- HDU 5918 SequenceI (2016 CCPC长春站 KMP模版变形)
- tcprstat测试服务器请求响应时间
- zc702-自定义AXI-IP核实验
- [原][openstack-pike][controller node][issue-3][horizon] dashboard show internal error 500 Cannot serve directory /var/www/html
- 服务器被minerd
- CLR(Common Language Runtime) 公共语言运行库
- junit 测试quartz
- DCGAN in Tensorflow生成动漫人物
- SSD论文理解
- USACO 6.1 Cow XOR
- SQL Server 高级SQL
- 【BZOJ4456】[Zjoi2016]旅行者 分治+最短路
- Oracle udev 绑定磁盘（转）
- Gradle的快速入门
- HDU 1201 Fibonacci Again
热门文章
- Nuke的色彩匹配节点思路
- Complexity and Tractability (3.44) - The Traveling Salesman Problem
- 【微软版本】redis 安装启动及设置密码<windows>
- 【正则表达式】使用正则表达式的group，查找出String中的参数值
- Android开发之环境配置篇
- Java-Runoob-高级教程-实例-方法：12. Java 实例 – Enum（枚举）构造函数及方法的使用-um
- Spring的LoadTimeWeaver(代码织入)(转)
- 如何进行CodeReview
- 获取器操作都是针对数据而不是数据集的，要通过append()方法添加数据表不存在的字段
- 20165312 预备作业3 Linux安装及学习