ivana_andreevska

Baranje studenti spored index HASH

Feb 4th, 2022
296
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.94 KB | None | 0 0
  1. import java.util.Map;
  2. import java.util.Objects;
  3. import java.util.Scanner;
  4.  
  5. class CBHT<K extends Comparable<K>, E> {
  6.  
  7.     // An object of class CBHT is a closed-bucket hash table, containing
  8.     // entries of class MapEntry.
  9.     private SLLNode<MapEntry<K, E>>[] buckets;
  10.  
  11.     @SuppressWarnings("unchecked")
  12.     public CBHT(int m) {
  13.         // Construct an empty CBHT with m buckets.
  14.         buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
  15.     }
  16.  
  17.     private int hash(K key) {
  18.         // Translate key to an index of the array buckets.
  19.         return Math.abs(key.hashCode()) % buckets.length;
  20.     }
  21.  
  22.     public SLLNode<MapEntry<K, E>> search(K targetKey) {
  23.         // Find which if any node of this CBHT contains an entry whose key is
  24.         // equal
  25.         // to targetKey. Return a link to that node (or null if there is none).
  26.         int b = hash(targetKey);
  27.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  28.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  29.                 return curr;
  30.         }
  31.         return null;
  32.     }
  33.  
  34.     public void insert(K key, E val) {        // Insert the entry <key, val> into this CBHT.
  35.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  36.         int b = hash(key);
  37.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  38.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  39.                 // Make newEntry replace the existing entry ...
  40.                 curr.element = newEntry;
  41.                 return;
  42.             }
  43.         }
  44.         // Insert newEntry at the front of the 1WLL in bucket b ...
  45.         buckets[b] = new SLLNode<MapEntry<K, E>>(newEntry, buckets[b]);
  46.     }
  47.  
  48.     public void delete(K key) {
  49.         // Delete the entry (if any) whose key is equal to key from this CBHT.
  50.         int b = hash(key);
  51.         for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  52.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  53.                 if (pred == null)
  54.                     buckets[b] = curr.succ;
  55.                 else
  56.                     pred.succ = curr.succ;
  57.                 return;
  58.             }
  59.         }
  60.     }
  61.  
  62.     public String toString() {
  63.         String temp = "";
  64.         for (int i = 0; i < buckets.length; i++) {
  65.             temp += i + ":";
  66.             for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  67.                 temp += curr.element.toString() + " ";
  68.             }
  69.             temp += "\n";
  70.         }
  71.         return temp;
  72.     }
  73.  
  74. }
  75.  
  76. class MapEntry<K extends Comparable<K>, E> implements Comparable<K> {
  77.  
  78.     // Each MapEntry object is a pair consisting of a key (a Comparable
  79.     // object) and a value (an arbitrary object).
  80.     K key;
  81.     E value;
  82.  
  83.     public MapEntry(K key, E val) {
  84.         this.key = key;
  85.         this.value = val;
  86.     }
  87.  
  88.     public int compareTo(K that) {
  89.         // Compare this map entry to that map entry.
  90.         @SuppressWarnings("unchecked")
  91.         MapEntry<K, E> other = (MapEntry<K, E>) that;
  92.         return this.key.compareTo(other.key);
  93.     }
  94.  
  95.     public String toString() {
  96.         return "<" + key + "," + value + ">";
  97.     }
  98. }
  99.  
  100. class SLLNode<E> {
  101.     protected E element;
  102.     protected SLLNode<E> succ;
  103.  
  104.     public SLLNode(E elem, SLLNode<E> succ) {
  105.         this.element = elem;
  106.         this.succ = succ;
  107.     }
  108.  
  109.     @Override
  110.     public String toString() {
  111.         return element.toString();
  112.     }
  113. }
  114. class Student
  115. {
  116.     String ime;
  117.     String prezime;
  118.     int index;
  119.     String smer;
  120.  
  121.     Student(){}
  122.  
  123.     Student(String ime , String prezime , int index , String smer)
  124.     {
  125.         this.ime=ime;
  126.         this.prezime=prezime;
  127.         this.index=index;
  128.         this.smer=smer;
  129.     }
  130.  
  131.     @Override
  132.     public String toString() {
  133.         return "Ime:"+ime+" "+"Prezime:"+prezime+" "+"Index:"+index+" "+"Smer:"+smer+" ";
  134.     }
  135. }
  136.  
  137. public class Main {
  138.     public static void main(String[] args) {
  139.         Scanner input=new Scanner(System.in);
  140.         int n=input.nextInt();
  141.  
  142.         CBHT<Integer,Student>tabela=new CBHT<>(2*n);
  143.  
  144.         for(int i=0;i<n;i++)
  145.         {
  146.             String ime=input.next();
  147.             String prezime=input.next();
  148.             int index=input.nextInt();
  149.             String smer=input.next();
  150.  
  151.             Student s=new Student(ime,prezime,index,smer);
  152.             tabela.insert(index,s);
  153.         }
  154.         System.out.println("Searching...");
  155.         while (true)
  156.         {
  157.             Integer index=input.nextInt();
  158.             if(index.equals(-1))
  159.                 break;
  160.  
  161.             SLLNode<MapEntry<Integer,Student>> curr=tabela.search(index);
  162.  
  163.             if(curr!=null)
  164.             {
  165.                 System.out.println(curr.element.value);
  166.             }
  167.             else
  168.                 System.out.println("/");
  169.         }
  170.     }
  171.  
  172. }
Advertisement
Add Comment
Please, Sign In to add comment