Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.92 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  6.  
  7. K key;
  8. E value;
  9.  
  10. public MapEntry (K key, E val) {
  11. this.key = key;
  12. this.value = val;
  13. }
  14.  
  15. public int compareTo (K that) {
  16. @SuppressWarnings("unchecked")
  17. MapEntry<K,E> other = (MapEntry<K,E>) that;
  18. return this.key.compareTo(other.key);
  19. }
  20.  
  21. public String toString () {
  22. return "<" + key + "," + value + ">";
  23. }
  24. }
  25.  
  26. class SLLNode<E> {
  27. protected E element;
  28. protected SLLNode<E> succ;
  29.  
  30. public SLLNode(E elem, SLLNode<E> succ) {
  31. this.element = elem;
  32. this.succ = succ;
  33. }
  34.  
  35. @Override
  36. public String toString() {
  37. return element.toString();
  38. }
  39. }
  40.  
  41. class CBHT<K extends Comparable<K>, E> {
  42.  
  43. // An object of class CBHT is a closed-bucket hash table, containing
  44. // entries of class MapEntry.
  45. private SLLNode<MapEntry<K,E>>[] buckets;
  46.  
  47. @SuppressWarnings("unchecked")
  48. public CBHT(int m) {
  49. // Construct an empty CBHT with m buckets.
  50. buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  51. }
  52.  
  53. private int hash(K key) {
  54. // Translate key to an index of the array buckets.
  55. return Math.abs(key.hashCode()) % buckets.length;
  56. }
  57.  
  58. public SLLNode<MapEntry<K,E>> search(K targetKey) {
  59. // Find which if any node of this CBHT contains an entry whose key is
  60. // equal
  61. // to targetKey. Return a link to that node (or null if there is none).
  62. int b = hash(targetKey);
  63. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  64. if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  65. return curr;
  66. }
  67. return null;
  68. }
  69.  
  70. public void insert(K key, E val) { // Insert the entry <key, val> into this CBHT.
  71. MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  72. int b = hash(key);
  73. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  74. if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  75. // Make newEntry replace the existing entry ...
  76. curr.element = newEntry;
  77. return;
  78. }
  79. }
  80. // Insert newEntry at the front of the 1WLL in bucket b ...
  81. buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  82. }
  83.  
  84. public void delete(K key) {
  85. // Delete the entry (if any) whose key is equal to key from this CBHT.
  86. int b = hash(key);
  87. for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  88. if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  89. if (pred == null)
  90. buckets[b] = curr.succ;
  91. else
  92. pred.succ = curr.succ;
  93. return;
  94. }
  95. }
  96. }
  97.  
  98. public String toString() {
  99. String temp = "";
  100. for (int i = 0; i < buckets.length; i++) {
  101. temp += i + ":";
  102. for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  103. temp += curr.element.toString() + " ";
  104. }
  105. temp += "\n";
  106. }
  107. return temp;
  108. }
  109.  
  110. }
  111.  
  112.  
  113. public class Lozinki {
  114. public static void main (String[] args) throws IOException {
  115. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  116. int N = Integer.parseInt(br.readLine());
  117.  
  118. CBHT<String, String> table = new CBHT<String,String>(N);
  119.  
  120.  
  121. for(int i=1;i<=N;i++){
  122. String imelozinka = br.readLine();
  123. String[] pom = imelozinka.split(" ");
  124. table.insert(pom[0],pom[1]);
  125. }
  126.  
  127. String cita = br.readLine();
  128. while(br.ready()!=false)
  129. {
  130. String value[] = cita.split(" ");
  131. SLLNode<MapEntry<String, String>> key = table.search(value[0]);
  132. if(key!= null&&key.element.value.equals(value[1]))
  133. {
  134. System.out.println("Najaven");
  135. return;
  136. }
  137. else
  138. {
  139. System.out.println("Nenajaven");
  140. }
  141. cita = br.readLine();
  142. }
  143.  
  144. }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement