Advertisement
add1ctus

Втора

Dec 9th, 2015
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.77 KB | None | 0 0
  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. import java.util.Scanner;
  6.  
  7. class Map<K extends Comparable<K>,E> {
  8.  
  9.     public K key;
  10.     public E value;
  11.  
  12.     public Map (K key, E val) {
  13.         this.key = key;
  14.         this.value = val;
  15.     }
  16.  
  17. }
  18.  
  19. class SLLNode<E> {
  20.     protected E info;
  21.     protected SLLNode<E> next;
  22.  
  23.     public SLLNode(E info, SLLNode<E> next) {
  24.         this.info = info;
  25.         this.next = next;
  26.     }
  27.    
  28. }
  29.  
  30. class SLLHT<K extends Comparable<K>, E> {
  31.  
  32.     private SLLNode<Map<K,E>>[] htable;
  33.    
  34.     public SLLHT(int m) {
  35.             /*kreiranje na prazna hesh tabela*/
  36.         htable = (SLLNode<Map<K,E>>[]) new SLLNode[m];
  37.                 for(int i=0;i<m;i++)
  38.                     htable[i]=null;
  39.     }
  40.  
  41.     private int hash(K key) {            
  42.            // Ednostavna verzija, neefikasna!
  43.         return (key.toString().charAt(0)-'a') % htable.length;
  44.     }
  45.  
  46.     public SLLNode<Map<K,E>> find(K look) {
  47.         int h = hash(look);
  48.         for (SLLNode<Map<K,E>> node = htable[h]; node != null; node = node.next) {
  49.             if (look.equals(node.info.key))
  50.                 return node;
  51.                 }
  52.                 /*ako vo tabelata ne se pronajde kluch ist so preneseniot
  53.                  * se vrakja null vrednost*/
  54.                 return null;
  55.     }
  56.  
  57.     public void insert(K key, E val) {     
  58.             /* vo tabelata se vmetnuva jazol, chie info pole
  59.              * go sodrzhi parot (key,val) */
  60.                 Map<K, E> entry = new Map(key, val);
  61.         int h = hash(key);              
  62.         for (SLLNode<Map<K,E>> node = htable[h]; node != null; node = node.next) {
  63.             if (key.equals(node.info.key)) {
  64.                 node.info = entry;
  65.                                 /*ako se pronajde jazol so ist kluch,
  66.                                  * se resetira vrednosta*/                                
  67.                 return;
  68.             }
  69.         }
  70.                 /* ako ne se pronajde jazolot vo soodvetnata kofichka
  71.                  * se dodava na pochetok vo nejzinata povrzana lista  */
  72.         htable[h] = new SLLNode<Map<K,E>>(entry, htable[h]);
  73.     }
  74.  
  75.     public void delete(K key) {
  76.         int h = hash(key);
  77.         for (SLLNode<Map<K,E>> pred = null, node = htable[h]; node != null; pred = node, node = node.next) {
  78.             if (key.equals(node.info.key)) {
  79.                             /*ako se najde zapisot i e na pochetok na listata*/
  80.                 if (pred == null)
  81.                     htable[h] = node.next;
  82.                 else
  83.                             /*ako se najde zapisot i ne e na pochetok na listata*/
  84.                     pred.next = node.next;
  85.                 return;
  86.             }
  87.         }
  88.     }
  89.                
  90. }
  91. public class SLLHashTables {
  92.    
  93.     public static void main(String[] args) {
  94.         Scanner input = new Scanner(System.in);
  95.        
  96.         int N = input.nextInt();
  97.        
  98.         SLLHT<String, String> mapa = new SLLHT(2*N);
  99.        
  100.         for(int i = 0 ; i < N ; ++i)
  101.             mapa.insert(input.next().toLowerCase(), input.next());
  102.        
  103.         input.nextLine();
  104.         String[] recenica = input.nextLine().split(" ");
  105.         for(int i = 0 ; i < recenica.length ; ++i)
  106.         {
  107.             String sign = new String();
  108.             if(!Character.isAlphabetic(recenica[i].charAt(recenica[i].length() - 1)))
  109.             {
  110.                 sign += recenica[i].charAt(recenica[i].length() - 1);
  111.                 recenica[i] = recenica[i].substring(0, recenica[i].length()-1);
  112.                
  113.             }
  114.             SLLNode<Map<String, String>> entry = mapa.find(recenica[i].toLowerCase());
  115.             for(;;)
  116.             {
  117.                 if(entry == null)
  118.                 {
  119.                     System.out.print("? ");
  120.                     break;
  121.                 }
  122.                 else if(entry.info.key.equals(recenica[i].toLowerCase()))
  123.                 {
  124.                     System.out.print(entry.info.value + sign + " ");
  125.                     break;
  126.                 }
  127.                 else
  128.                     entry = entry.next;
  129.             }
  130.         }
  131.     }
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement