Strukture za sve

User · **Poslato:** 01.07.2006. 16:55:41

OK.
Idemo nanovo.

Subject: LISTE

Kod:

public interface List { //abstract list interface
   //   return true if list is empty
   public boolean isEmpty();
   //   remove all items from list
   public void makeEmpty();
}
   
public interface ListItr { //abstract list iterator
   //   insert item x after current position
   public void insert(Object x) throws ItemNotFound;
   //   set current position to item x
   public boolean find(Object x);
   //   remove item x
   public void remove(Object x) throws ItemNotFound;
   //   true if current position references a valid node
   public boolean isInList();
   //   return item in current position
   public Object retrieve();
   //   replace old item with x
   public void update(Object x) throws ItemNotFound;
   //   set position prior to the first position
   public void zeroth();
   //   set current position to the first position
   public void first();
   //   move current position to the next node
   public void advance();
}

Kod:

class ListNode {
   //   element can be of any type
   Object element; // reference to the next element
   ListNode next;
   ListNode(Object el, ListNode nx) //constructors
   { element = el; next = nx; }
   ListNode( ) { this(null, null); } 
}

Spregnuta lista:

Kod:

public class LinkedList implements List {
   ListNode header; // friendly field
   public LinkedList()
   { header = new ListNode( ); }
   public boolean isEmpty( )
   { return header.next == null; }
   public void makeEmpty( )
   { header.next = null; }
}

Kod:

public class LinkedListItr implements ListItr {
   protected LinkedList currentList;
   protected ListNode curPos; //current position
   //   constructors
   public LinkedListItr(LinkedList list) {
      currentList = list;
      curPos = list.isEmpty() ? list.header :
         list.header.next;
   }
   public LinkedListItr(List list) throws ClassCastException
   { this( (LinkedList) list); }
   
   //   operations
   public void zeroth( )
   { curPos = currentList.header; }
   public void insert(Object x) throws ItemNotFound {
      if (curPos == null)
         throw new ItemNotFound("Insertion error");
      curPos.next = new ListNode(x, curPos.next);
      //   curPos refers now to the newly inserted node
      curPos = curPos.next;
   }
   
   public void update(Object x) throws ItemNotFound { 
      if (curPos == null)
         throw new ItemNotFound("Update error");
      curPos.element = x;
   }
   
   public boolean find(Object x) {
      ListNode itr = currentList.header.next;
      while (itr != null && ! itr.element.equals(x) )
         itr = itr.next;
      if (itr == null) return false;
      curPos = itr;
      return true;
   }
   
   public void remove(Object x) throws ItemNotFound {
      ListNode itr = currentList.header;
      while ( itr.next != null && ! itr.next.element.equals(x) )
         itr = itr.next;
      if (itr.next == null)
         throw new ItemNotFound("Remove fails");
      itr.next = itr.next.next; // remove
      curPos = currentList.header;
   }
   
   public Object retrieve( )
   { return isInList() ? curPos.element : null; }
   
   public void first( )
   { curPos = currentList.header.next; }
   
   public void advance( )
   { if (curPos != null) curPos = curPos.next; }
   
   public boolean isInList( )
   { return curPos != null && curPos != currentList.header; }
   
} //end of class LinkedListItr

Pretrazivanje spregnute liste

Kod:

public class SortListItr extends LinkedListItr {
   public SortListItr(List list) // constructor
   { super(list); }
   
   public void insert(Object x) throws ItemNotFound {
      if (x instanceof Comparable)
         insert( (Comparable) x);
      else throw new ItemNotFound("SortListItr "
            + "insert requires an object of type"
            + " Comparable");
   }
   
   //   insert in sorted order
   public void insert(Comparable x) {
      ListNode prev = currentList.header;
      ListNode curr = currentList.header.next;
      while ( curr != null && ((Comparable) curr.element).lessThan(x)) {
         curr = curr.next;
         prev = prev.next; 
      }
      curPos = prev; //curPos is in LinkedListItr
      try { super.insert(x); }
      catch(ItemNotFound e) { } //cannot happen
   }
}

Scully · **Poslato:** 01.07.2006. 16:57:12

baneizalfe je napisao:

Data je jednostruko spregnuta lista celih brojeva sortirana u rastućem redosledu. Definiše ovu strukturu kao apstraktni tip i implementirajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.

Kod:

//Mislim da bi bilo najbolje da se element doda na pocetak liste,
//pa ako je veci od sledeceg, da zamene mesta i tako do kraja

// Dodavanje elementa na pocetak liste
   public void Add(Object aData){
      mHead = new ListNode(aData, mHead);
      mCurrent = mHead;
      while(mCurrent.Next!=null){
         if(mCurrent>mCurrent.Next){
            Object pom=mCurrent.Next;
            mCurrent.Next=mCurrent;
            mCurrent=pom;
         }
      }
      
   }

Ne znam kako da pretvorim ovo u pastraktni tip...

ovde umesto

Object pom=mCurrent.Next;

treba

ListNode pom = new ListNode(aData, mCurrnet.Next);

imas to u jos nekim primerima... i jos nesto.. kad imas void ne mozes davati return vec (valjda) throw-ujes exception..

User · **Poslato:** 01.07.2006. 17:14:58

Subject: Red ili Queue

Interfejs

Kod:

public interface Queue {
   public void enqueue(Object x);
   public Object getFront( ) throws Underflow;
   public Object dequeue( ) throws Underflow;
   public boolean isEmpty( );
   public void makeEmpty( );
}

Queue preko Niza (Array)

Kod:

public class QueueAr implements Queue {
   private Object array[];
   private int count, front, back;
   static final int DEF_SIZE = 10;
   public QueueAr( ) { //constructor
   array = new Object[DEF_SIZE];
   makeEmpty( );
}
   
public void makeEmpty( ) {
   count = front = 0;
   back = array.length-1;
}
   
public boolean isEmpty( ) { return count==0; }
   
public void enqueue(Object x) {
   if (count == array.length) doubleSize();
   back = (back+1) % array.length;
   array[back] = x;
   count++; 
}

public Object dequeue( ) throws Underflow {
   if (isEmpty())
   throw new Underflow("Empty queue");
   count--;
   Object item = array[front];
   front = (front+1) % array.length;
   return item;
}

public Object getFront() throws Underflow {
   if (isEmpty())
      throw new Underflow("Empty queue");
   return array[front];
}

//   dynamically increase the size of array
private void doubleSize( ) {
   Object [] newArray;
   newArray = new Object[2*array.length];
   //   copy elements
   for (int i = 0; i < count; i++) {
      newArray[i] = array[front];
      front = (front+1) % array.length;
   }
   array = newArray;
   front = 0;
   back = count - 1;
}

Queue preko spregnute liste

Kod:

public class QueueLi implements Queue {
   private ListNode front, back;
   public QueueLi( ) { makeEmpty( ); }
   
   public void makeEmpty( )
   { front = back = null; }
   
   public boolean isEmpty( )
   { return front == null; }
   
   public Object dequeue( ) throws Underflow {
      if ( isEmpty() )
         throw new Underflow("Empty queue");
      Object item = front.element;
      front = front.next;
      return item;
   }
   
   public Object getFront( ) throws Underflow {
      if ( isEmpty() )
         throw new Underflow("Empty queue");
      return front.element;
   }
   
   public void enqueue(Object x) {
      if ( isEmpty() ) //make one-element queue
         back = front = new ListNode(x, null);
      else //regular case
         back = back.next = new ListNode(x, null);
   }
}

User · **Poslato:** 01.07.2006. 17:23:26

Subject: Stack

Stack interfejs:

Kod:

public interface Stack {
   void push(Object x);
   void pop( ) throws Underflow;
   Object top( ) throws Underflow;
   Object topAndPop( ) throws Underflow;
   boolean isEmpty( );
   void makeEmpty( );
}

Primer Stack-a:

Kod:

public final class TestStack {
   public static void main(String args[]) {
      Stack s = new StackAr();
      for (int i = 0; i < 10; i++)
         s.push( new Integer(i+100) );
      System.out.print("Contents: ");
      try {
         while (! s.isEmpty() )
            System.out.print(" " + s.topAndPop());
         System.out.println( );
      } 
      catch(Underflow e) { }
   }
}

Stack preko Array:

Kod:

public class StackAr implements Stack {
   private Object array[];
   private int topOfStack;
   static final int DEF_SIZE = 10;
   
   public StackAr() {
      array = new Object[DEF_SIZE];
      topOfStack = -1; 
   }
   
   public boolean isEmpty( ) 
   { return topOfStack == -1; }
   
   public void makeEmpty( )
   { topOfStack = -1; }
   
   public void push(Object x)
   {
      if (topOfStack == array.length-1) doubleSize();
      array[ ++topOfStack ] = x;
   }
      
   public Object top( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      return array[topOfStack];
   }
   
   public void pop( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      topOfStack--;
   }
   
   public Object topAndPop( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      return array[ topOfStack-- ];
   }
   
   //   double size of array
   private void doubleSize( ) {
      Object newArray[] = new Object[2*array.length];
      for (int i = 0; i <= topOfStack; i++)
         newArray[i] = array[i];
      array = newArray;
   }
}

Stack preko spregnute liste:

Kod:

public class StackLi implements Stack {
   private ListNode topOfStack;
   
   public StackLi( ) //constructor
   { topOfStack = null; }

   public boolean isEmpty( )
   { return topOfStack == null; }
   
   public void makeEmpty( )
   { topOfStack = null; }
   
   public void push(Object x)
   { topOfStack = new ListNode(x, topOfStack); }
   
   public void pop( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      topOfStack = topOfStack.next;
   }
   
   public Object top( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      return topOfStack.element;
   }
   
   public Object topAndPop( ) throws Underflow {
      if (isEmpty())
         throw new Underflow("Empty stack");
      Object item = topOfStack.element;
      topOfStack = topOfStack.next;
      return item;
   }
}

kliford · **Poslato:** 01.07.2006. 17:42:32

Scully je napisao:

shredder je napisao:

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

ne valja ti ovaj kod. Kod spregnutih listi ne mozes da pristupas elementima preko indexa. To moze kod nizova.

Moooze!!! Upravo gledam Vezbe 5, radili smo fju GetNode resava ovu stvar... mada baneizalfe ti ces moradi da pises i tu fju koju upotrebljavas u ovom slucaju GetNode! Naravno ni meni ovaj nacin nije pao na pamet dok nisam videla u svesku.. :fokus:

Mislim da ovde nije poenta resiti preko indexa, jer nam onda ne bi bio potreban podatak da su elementi sortirani

User · **Poslato:** 01.07.2006. 17:44:57

Subject: Binarna stabla (Binary tree)

Cvor:

Kod:

final class BinaryNode {
   //   friendly data; accessible by other packages
   Object element;
   BinaryNode left, right;
   
   //   constructors
   //   specify an element and right and left subtrees
   BinaryNode(Object elem, BinaryNode lt, BinaryNode rt) {
      element = elem;
      left = lt;
      right = rt;
   }
   //   specify a binary tree with a root contains element
   BinaryNode(Object elem)
   { this(elem, null, null); }
   
   //   specify an empty binary tree
   BinaryNode( ) 
   { this(null); }

   //   operations
   static int size(BinaryNode t) { //recursive
      if (t == null) return 0;
      else return (1 + size(t.left) + size(t.right));
   }
   
   static int height(BinaryNode t) { //recursive
      if (t == null) return -1;
      else return (1 + Math.max(height(t.left), height(t.right)));
   }
   
   BinaryNode duplicate( ) {
      BinaryNode root = new BinaryNode(element);
      if (left != null)
         root.left = left.duplicate();
      if (right != null)
         root.right = right.duplicate();
      return root;
   } 
}

Drvce:

Kod:

public class BinaryTree {
   private BinaryNode root;
   
   //   constructors
   public BinaryTree( ) { root = null; }
   
   public BinaryTree(Object rootItem)
   { root = new BinaryNode(rootItem); }
      
   public BinaryNode getRoot( ) { return root; }

   //   operations
   public boolean isEmpty( )
   { return root == null; }
   
   public void makeEmpty( ) { root = null; }
   
   public int size( )
   { return BinaryNode.size(root); }
   
   public int height( )
   { return BinaryNode.height(root); }
      
   public void duplicate(BinaryTree rhs) {
      if (this != rhs)
      root = rhs.root.duplicate(); 
   }

   //    merge t1, t2 and root (with rootItem)
   public void merge(Object rootItem, BinaryTree t1, BinaryTree t2) {
      if (t1.root == t2.root && t1.root != null) {
         System.err.println("Left tree == right tree; " + " merge aborted");
         return;
      }
      root = new BinaryNode(rootItem, t1.root, t2.root);
      
      //   remove aliases
      if (this != t1) t1.root = null;
      if (this != t2) t2.root = null;
   }
}

Interfejs za prolaze: prefix, infix i postfix:

Kod:

public interface TreeOperation {
   public void processNode(Object element);
}

Prefix prolaz (rekurzivno):
1. Procesiraj koren.
2. Rekurzivno poseti sve cvorove levog podstabla.
3. Rekurzivno poseti sve cvorove desnog podstabla.

Kod:

//   this is continuation of the class BinaryNode
//   TreeOperation is an interface
//   with one method: processNode()
public void preOrderTraversal(TreeOperation op) {
   op.processNode(element);
   if (left != null) left.preOrderTraversal(op);
   if (right != null) right.preOrderTraversal(op);
}

Infix prolaz (rekurzivno):
1. Rekurzivno poseti sve cvorove levog podstabla.
2. Procesiraj koren.
3. Rekurzivno poseti sve cvorove desnog podstabla.

Kod:

public void inOrderTraversal(TreeOperation op) {
   if (left != null) left.inOrderTraversal(op);
   op.processNode(element);
   if (right != null) right.inOrderTraversal(op);
}

Postfix prolaz (rekurzivno):
1. Rekurzivno poseti sve cvorove levog podstabla.
2. Rekurzivno poseti sve cvorove desnog podstabla.
3. Procesiraj koren.

Kod:

public void postOrderTraversal(TreeOperation op) {
   if (left != null) left.postOrderTraversal(op);
   if (right != null) right.postOrderTraversal(op);
   op.processNode(element);
}

Primer koriscenja prolaza kroz stablo:

Kod:

public class PrintTree implements TreeOperation {
   public void processNode(Object element) {
      System.out.print(" "+((Integer) element));
   } 
}
   
public class testTraversal {
   public static void main(String [] args) {
      BinaryTree bt = new BinaryTree();

      //   here generate the tree bt with

      //   Integer elements
      ...
      PrintTree pt = new PrintTree();
      bt.getRoot().preOrderTraversal(pt);
      System.out.println();
      ...
   } 
}

kliford · **Poslato:** 01.07.2006. 17:49:36

Scully je napisao:

i jos nesto.. kad imas void ne mozes davati return vec (valjda) throw-ujes exception..

Exceptioni nemaju veze sa izlaznim tipom metode na taj nacin... void samo oznacava da nemas izlaz u vidu nekog objekta ili pr4omenljive, nego da ta metoda samo odradi neki posao (recimo stampanje necega) i to je to...

I void metode mogu imati return, ali samo u obliku return;... time oznacavas prekid u vrsenju metode...

User · **Poslato:** 01.07.2006. 17:51:36

Subject: Binary Search Tree (BST) - Binarno Stablo Pretrazivanja

BST kod ft. Ubaci, Izbaci, Nadji, etc...

Kod:

public class BinarySearchTree {
   protected BinaryNode root;

   //   constructor
   public BinarySearchTree( )
   { root = null; }
   
   public void insert(Comparable x) throws DuplicateItem
   { root = insert(x, root); }
   
   public void remove(Comparable x) throws ItemNotFound
   { root = remove(x, root); }
   
   public Comparable find(Comparable x) throws ItemNotFound
   { return find(x, root).element; }
   
   public boolean isEmpty( )
   { return root == null; }
   
   public void makeEmpty( )
   { root = null; }
   
   //   internal methods
   //   find node containing the smallest item
   protected BinaryNode findMin(BinaryNode t) throws ItemNotFound {
      if (t == null)
         throw new ItemNotFound("Empty tree");
      while (t.left != null) t = t.left;
      return t;
   }

   //   find node containing item x
   protected BinaryNode find(Comparable x, BinaryNode t) throws ItemNotFound {
      while (t != null)
         if (x.compares(t.element) < 0)
            t = t.left;
         else if (x.compares(t.element) > 0)
            t = t.right;
         else return t; // found
      throw new ItemNotFound("Item not found");
   }

   protected BinaryNode insert(Comparable x, BinaryNode t) throws DuplicateItem {
      if (t == null) t = new BinaryNode(x);
      else if (x.compares(t.element) < 0)
         t.left = insert(x, t.left);
      else if (x.compares(t.element) > 0)
         t.right = insert(x, t.right);
      else
         throw new DuplicateItem("Duplicate item");
      return t;
   }
   
   //   remove the smallest element
   protected BinaryNode removeMin(BinaryNode t) throws ItemNotFound {
      if (t == null)
         throw new ItemNotFound("Empty tree");
      if (t.left != null)
         t.left = removeMin(t.left);
      else t = t.right;
      return t;
   }
   
   //   remove node containing item x
   protected BinaryNode remove(Comparable x, BinaryNode t) throws ItemNotFound {
      if (t == null)
         throw new ItemNotFound("Empty tree");
      if (x.compares(t.element) < 0)
         t.left = remove(x, t.left);
      else if (x.compares(t.element) > 0)
         t.right = remove(x, t.right);
      else if (t.left != null && t.right != null) {
         // item x is found; t has two children
         t.element = findMin(t.right).element;
         t.right = removeMin(t.right);
      } else //t has only one child
         t = (t.left != null) ? t.left : t.right;
      return t;
   }
}

Scully · **Poslato:** 01.07.2006. 18:28:32

kliford je napisao:

Kod:

array[start = (++start % array.length)]

Bice da sam kreten

Ovo mi uopste nije jasno!!! Sta se ovde radi?

mislim... cemu sve ovo sa ostatkom deljenja???

mene ovo podseca na HASHing :zbun:

joj ljudi pretrpali ste me informacijama.. previse sam :zbun:

... gde da pohvatam sve ovo.. zakljucak, sto manje znas (da ne znas) to bolje...

Hoce li mi neko objasniti sta u stvari predstavlja O( ) i kako se racuna!!?

baneizalfe · **Poslato:** 01.07.2006. 18:43:41

kliford je napisao:

Scully je napisao:

shredder je napisao:

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

ne valja ti ovaj kod. Kod spregnutih listi ne mozes da pristupas elementima preko indexa. To moze kod nizova.

Moooze!!! Upravo gledam Vezbe 5, radili smo fju GetNode resava ovu stvar... mada baneizalfe ti ces moradi da pises i tu fju koju upotrebljavas u ovom slucaju GetNode! Naravno ni meni ovaj nacin nije pao na pamet dok nisam videla u svesku.. :fokus:

Mislim da ovde nije poenta resiti preko indexa, jer nam onda ne bi bio potreban podatak da su elementi sortirani

Pazi, GetNode ce ti raditi u svakom slucaju, i da su sortirani, i da nisu... Mozda su hteli da vide dal pratimo vezbe. Ja sam to nasao u materijalima sa vezbi

baneizalfe · **Poslato:** 01.07.2006. 18:49:06

Citiraj:

Nego jel znate da uradite ovo:

Napisati funkciju koja prihvata pokazivač na koren AVL binarnog stabla i štampa sadržaj čvorova stabla u rastućem redosledu.

To ti je infix obilazak pri cemu ispisujes sadrzaj svakog cvora koji obidjes

Aj leba ti napisi to... E da, kako se proverava 2 uslov za avl sablo, tj da li je svako podstablo stablo?

I jos nesto, jel zna neko da oba primera transformacije kljuceva u adresu?

Scully · **Poslato:** 01.07.2006. 20:28:38

baneizalfe je napisao:

Data je jednostruko spregnuta lista celih brojeva sortirana u rastućem redosledu. Definiše ovu strukturu kao apstraktni tip i implementirajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.

Kod:

//Mislim da bi bilo najbolje da se element doda na pocetak liste,
//pa ako je veci od sledeceg, da zamene mesta i tako do kraja

// Dodavanje elementa na pocetak liste
   public void Add(Object aData){
      mHead = new ListNode(aData, mHead);
      mCurrent = mHead;
      while(mCurrent.Next!=null){
         if(mCurrent>mCurrent.Next){
            Object pom=mCurrent.Next;
            mCurrent.Next=mCurrent;
            mCurrent=pom;
         }
      }
      
   }

Ne znam kako da pretvorim ovo u pastraktni tip...

ako mene pitate ovo je vrlo labavo.. vec rekoh za ovu prvu liniju posle IF-a, mislim da bi se ovako izgubio mHead, i jos jedna stvar.. ovo nije DLLN, ako npr. treci i cetvrti menjaju mesta kako ce drugi posle da pokazuje na "novi" treci..

???

po meni bi ovde trebalo ici do elementa koji je veci

Kod:

public void UbaciSortirano(Object aData)
{
   if (mHead == null) //lista prazna
   {
      mHead = new ListNode(aData, mHead)
      mCurrent = mHead;
   
   } else if (mHead.Next = null && mHead.Data > Data) //lista sadrzi jedan element koji je vici od ovog koga ubacujemo, znaci novi treba da bude prvi... 
          {
              mHead = new ListNode(aData, mHead)   

   } else { //za sve ostale slucajeve ukljucujuci && kad je element koga doajemo veci od svih pa na ga stavljamo na poslednje mesto

      mCurrent = mHead; // ne znam da li ovo mora, ali bi na pocetku mCurrent trebao da pokazuje na prvi element

      while (aData > mCurrent.Next.aData && mCurrent.Next != null)
      {
          mCurrent = mCurrent.Next;

      }

         mCurrent.Next = new ListNode(aData, mCurrent.Next)
   }
}

ajde nek neko pregleda valjda li ovo sta, ili bar objasnite kako je sigurno, pretty please

Punoglavac · **Poslato:** 01.07.2006. 20:58:53

Pozdrav, imam dva pitanja i jedno obavestenje...

Obavestenje je da ce vam doci (99%) jedan od sledecih zadataka...
20. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava olančavanjem.

24. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava otvorenim adresiranjem.

A pitanja su kako se ovo radi?
I drugo, da li za obicno B stablo levo dete mora biti manje od korena i desno vece od njega ili to nema veze?

shredder · **Poslato:** 01.07.2006. 21:35:24

Evo nasao sam na puskicama ova dva zadatka uradjena, ali ovo je valjda C.
Kad bi neko mogao da ovo "pretvori" u javu, dobro bi bilo. Mozda neko od starijih kolega?

Kod:

/*HASHING – Linearno probanje*/
#include <stdio.h>
struct zapis{int kljuc;      int info;
             };
struct {struct zapis z; 
        int slobodan;
       }TABELA[n];
struct zapis *hashing(int k)
  {int a;
   a=k%n;
   if (TABELA[a].z.kljuc==k) return                  
    &TABELA[a].z;
   while (++a<n)
    if (TABELA[a].z.kljuc==k) return 
     &TABELA[a].z;
   return null;
  }



/*HASHING – Olančavanje */
struct zapis{int kljuc;      int info;
             };
struct elem{struct zapis z;
            struct elem *sl;
           };
struct {struct zapis z; 
        int slobodan;
        struct elem*sl;
       }TABELA[a];
struct zapis *hashing (int k)
  {int a;
   struct elem *p;
   a=k%n;
   if (TABELA[a].z.kljuc==k)return 
    &TABELA[a].z;
   p=TABELA[a].lista;
   while (p!=null)
     {if (p->z.kljuc==k) return &p->z;
      p=p->sled;
     }
   return null;
  }

Scully · **Poslato:** 01.07.2006. 21:36:18

Punoglavac je napisao:

Pozdrav, imam dva pitanja i jedno obavestenje...

Obavestenje je da ce vam doci (99%) jedan od sledecih zadataka...
20. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava olančavanjem.

24. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava otvorenim adresiranjem.

A pitanja su kako se ovo radi?
I drugo, da li za obicno B stablo levo dete mora biti manje od korena i desno vece od njega ili to nema veze?

otkud ti to... ja gledam ove rokove i ne bih rekla da se to mnooogo cesto pojavljuje..

a asist rekao od od kodova bice ono sto smo radili i tu neke varijante, tri cetiri linije koda, a ja se ne secam da su nam davali kod za hashing i sl... malo me nervira to kad nam na verzbama 3x ponavlja i radimo milion zadataka za ubacivanjem/izbacivanjem elemenata u B, B* stabla a ovi kodovi rasturaju.. or is it just me.. :aaa:

to vazi za B stabla koliko ja znam.. ali moje pitanje je za binarna.. kod obicnih binarnih ne mora to da vazi jeeeel

Paf · **Poslato:** 01.07.2006. 23:03:49

Ja imam jedno pitanje...
Zna li neko za sve ove strukture koje smo radili koliki su im O(). Ako bi neko mogao da ispise, ne bi bilo lose. Dolaze pitanja tipa:

Kakva je kompleksnost algoritma za pretraživanje jednostruko/dvostruko spregnute liste koja ima n elemenata?

A mi naravno ni na vezbama ni na predavanjima nismo radili nista slicno

User · **Poslato:** 01.07.2006. 23:34:34

Imas na slajdu o sortiranju koji mozes da skines sa sajta struktura. Ako me ne bude mrzelo okacicu kasnije.

edit:
Evo i objasnjenja za pitanja iz raznih tema:

Povezana lista
Povezana lista (linked list) je nista drugo nego niz elemenata, od kojih svaki ima 2 polja. U jednom je vrednost elementa (ono sto bi bilo na tom mestu u obicnom nizu), a u drugom pokazivac na sledeci element niza. Zadnji element pokazuje na NULL.
Slika

Prednosti ovakve strukture podataka su ubacivanje i izbacivanje elemenata iz liste u vremenskoj slozenosti O(1).

Stek
Stek (stack) je LIFO (Last In First Out) lista. Naime, kada treba smestiti novi element u stek, on se stavlja na njegov kraj (PUSH operacija), pri cemu se i pri uzimanju elemenata sa steka oni takodje uzimaju sa kraja (POP operacija). Stek inace koristi i sam kompajler pri rekurziji, tako da je jedna od primena steka bas simuliranje rekurzije.

Red
Red (queue) je FIFO (First In First Out) lista. U ovu listu se elementi stavljaju na kraj, ali uzimaju sa pocetka (kao red u prodavnici).

Hash tablice
Hash tablice (hash tables) nastaju hashiranjem elemenata. Naime, svaki element koji zelimo smestiti u ovu strukturu podataka hashiramo, tj. sracunamo vrednost koju neka hash funkcija daje za njega, i smestimo na to mesto u tabelu. Primer: Treba zapamtiti imena ucenika nekog razreda i jos neki podatak o svakom, recimo broj telefona. Primer hash funkcije je recimo zbir ascii vrednosti svih slova u imenu po modulu velicine tablice (sto je najpozeljnije neki prost broj). Ako je to mesto vec zauzeto, dodajemo jos jedan unos u isto polje (mozemo hash tablicu dakle pamtiti kao matricu, ili kao niz povezanih listi, sto je bolja implementacija). Sada kad trebamo naci Markov broj telefona, sabracemo ascii vrednosti slova u reci "Marko", uzeti tu vrednost po modulu velicine tablice, i traziti na tom mestu u hash tablici. Prednost ove strukture podataka je vreme pristupa elementu O(1).

Drvo
Za one koji su upoznati, drvo (tree) predstavlja graf koji nema nijedan krug (ciklus). Koncepcija ove strukture podataka je vec i iz samog imena jasna, a narocito uz sliku:
Slika

Za neki pocetni cvor kazemo da je "koren" (root) drveta, za svaki cvor one koji su "nadole" od njega i direktno povezani sa njim kazemo da su njegova "deca" (children), a zajedno sa onima nadole sa kojima je povezan preko vise od jedne ivice kazemo da su njegovi "potomci" (descendants). Svaki cvor koji je "nagore" od nekog i povezan sa njim je njegov "predak" (ancestor). Neki cvor zajedno sa svim njegovim potomcima cini poddrvo (subtree) ciji je on root. Najcesce se koristi binarno drvece, u kome svaki cvor ima najvise dvoje dece. Takodje, ovde svaki cvor ima svoje levo i desno poddrvo.

Binarno drvo pretrage
Binarno drvo pretrage (binary search tree) je takvo drvo u kome je za neki cvor njegovo levo dete uvek manje od njega, a desno uvek vece. U ovakvom drvetu je za trazenje ubacivanje ili izbacivane nekog elementa potrebno vreme O(log n). Medjutim, ako su elementi lose rasporedjeni, svaka od ovih operacija moze odneti cak O(n) vremena!

AVL drvo
AVL drvo je "izbalansirano" binarno drvo pretrage. U njemu je razlika visina levog i desnog poddrveta za svaki cvor najvise 1. Naime, pri svakom dodavanju ili izbacivanju elemenata, obraca se paznja da drvo ostane izbalansirano kao sto je receno, pri cemu se za taj korak ne sme potrositi vise od O(log n) vremena. Slozenosti svih operacija su kod ovakvog drveta uvek tacno O(log n).

Heap
Heap je jos jedna vrsta binarnog drveta, kod koga je zadovoljen uslov da su deca svakog cvora uvek veca ili jednaka od samog tog cvora (moze se praviti i obrnuto, da su deca uvek veca od oca). Ova struktura podataka ima izuzetno sirok spektar upotrebe. Naime, cesto je potrebno u svakom trenutku znati koji je najmanji element nekog niza. Koristeci heap, ovu informaciju imamo u O(1) (to je ustvari prvi element u heap-u). Updateovanje heap-a, sto ce reci izbacivanje ili ubacivane elementa radi se u O(log n).

Trazenje u hash tablicama
Ako koristimo hash tablice, trazenje elementa je vrlo jednostavno. Samo ga treba "pluggovati" u hash funkciju i time ga nadjemo u O(1).

Trazenje u binarnom drvetu pretrage i AVL drvetu
I ove strukture podataka, kao i hash tablice, su takve da im je jedna od poenti upravo trazenje elemenata. Kod obe je proces isti: podjemo od root-a celog drveta. Ukoliko je on element koji trazimo, kraj. Ako ne, vidimo da li je element koji trazimo manji ili veci od njega. Ako je manji, isti postupak (rekurzivno) ponavljamo za levo poddrvo, ako je veci za desno. Kao sto je vec receno, slozenost je O(log n), sa tim da u nebalansiranom drvetu moze da bude i znatno gora (ali i bolja!).

Linearna pretraga
Pretpostavimo da imamo obican niz od n elemenata. Linearna pretraga se sastoji u tome da prodjemo sve elemente niza trazeci onaj koji nam treba. Slozenost: O(n).

Binarna pretraga
Imamo sortiran (rastuce) niz od n elemenata u kome treba naci neki. Neka je na pocetku left=1 i right=n. U svakoj iteraciji, nadjemo element middle kao srednji izmedju left i right. Ukoliko je trazeni element jednak tom middle, kraj. Ako je middle veci od njega, kazemo right=middle, u suprotnom left=middle, i ponavljamo isti postupak. Vrlo jednostavan, ali vrlo cesto upotrebljavan koncept. Slozenost je, naravno, O(log n).

Selection, Insertion i Bubble Sort
Ovo su tri vrlo jednostavna algoritma za sortiranje elemenata. Svi su izuzetno jednostavni, ali slozenosti O(n²).

Quick Sort
Verovatno najbolji algoritam za sortiranje. Radi po sledecem principu: odredimo neki, bilo koji, element da bude pivot. Sada ispremestamo sve elemente niza tako da su prvo svi oni manji, pa onda svi oni veci od pivota. Sada, za svaki od ova dva dela rekurzivno pozovemo quicksort. Izuzetno elegantan i praktican algoritam, a lak za kodiranje. Slozenosti je O(n log n), mada ona nije uvek ista. U najgorem mogucem slucaju ona moze biti i O(n²), medjutim, u praksi, quicksort obicno daje bolje rezultate od svih ostalih algoritama za sortiranje.

Merge Sort
Merge Sort radi na principu “podeli i vladaj”. On naime podeli niz na dva dela, rekurzivno se poziva za oba, a kada se vrati, ta dva dela spaja (merge) u jedan sortirani. Slozenost je uvek O(n log n). Merge sort se jos moze i koristiti za racunanje broja inverzija permutacije, uz par redova dodatih u trenutku kada se nizovi spajaju.

Heap Sort
Heap Sort niz sortira tako sto ga smesti u heap. Vec znamo da operacije umetanja i skidanja sa heapa imaju slozenost O(log n). Dakle ovaj algoritam ce imati ukupnu slozenost O(n log n), jer svaki element treba prvo da ubacimo u heap, pa kad smo formirali ceo, izbacujemo uvek prvi element dokle god ne ispraznimo heap.

preuzeto sa ES

ili:
Selection sort:

Shell sort:

Insertion sort:

Bubble sort:

Quick sort:

Merge sort:

Heap sort:

kliford · **Poslato:** 02.07.2006. 02:16:43

baneizalfe je napisao:

Citiraj:

Nego jel znate da uradite ovo:

Napisati funkciju koja prihvata pokazivač na koren AVL binarnog stabla i štampa sadržaj čvorova stabla u rastućem redosledu.

To ti je infix obilazak pri cemu ispisujes sadrzaj svakog cvora koji obidjes

Aj leba ti napisi to...

Kod:

    public static void infixVisit(AVLNode n){
        if (n.left != null)
            infixVisit(n.left);
        System.out.println (n.data);
        if (n.right != null)
            infixVisit(n.right);
    }

Sta je problem?

Scully · **Poslato:** 02.07.2006. 09:06:29

moze i ovako.. bilo da vezbama... za razlicit prolaz samo menjate redosled poslednja tri reda..

Kod:

public static void infixVisit(AVLNode aNode)
{
   if (aNode == null)
   return;

   infixVisit(aNode.left);
   System.out.println(aNode.Data);
   infixVisit(aNode.right);
}

Hoce li neko da pregleda prethodni zadatak sto ispisah

i jos jednom... a kako se racuna to O () tj sta ustvari predstavlja...

Evo npr. Stablo za binarno pretrazivanja ima ukupno M cvorova a visinu K. Vreme potrebno za pronalazenje nekog cvora u stablu je proporcionalno sa:
a) M + K
b) M*K
c) M
d) K

I jos nesto.. ima li ko kod za proveravanje da li je stablo HEAP i da li je AVL? I taj Hasing???

shredder · **Poslato:** 02.07.2006. 12:11:25

@ scully

Najefikasnlje pretražlvanje je onda kada je BST balanslrano (svi listovi na istoj visini) koje u tom slučaju iznosi log2N t.j jednako je visini stabla.

Ovo pise na puskicama sa puskica

kliford · **Poslato:** 02.07.2006. 12:33:04

Scully je napisao:

Hoce li neko da pregleda prethodni zadatak sto ispisah

i jos jednom... a kako se racuna to O () tj sta ustvari predstavlja...

Malo je komplexno rachunanje O()-a, mi smo samo dobili podatak za svaki algoritam koliki mu je

Citiraj:

Evo npr. Stablo za binarno pretrazivanja ima ukupno M cvorova a visinu K. Vreme potrebno za pronalazenje nekog cvora u stablu je proporcionalno sa:
a) M + K
b) M*K
c) M
d) K

Neko ti je jos pre odgovorio M*K, a i ja mislim da je tako

Sad, hoce li neko meni pojasniti ovo:
u zadatku koji kaze da napisemo ubaci() i izbaci() metode koje ubacuju i izbacuju cvorove iz reda implementiranog preko niza, vi ubacujete i izbacujete cvorove po ne znam kom principu, a po definiciji u red se elementi ubacuju na pocektu reda, a izbacuju sa kraja???

parasite · **Poslato:** 02.07.2006. 14:26:34

A sta je sa ovom apstraktnim tipovima, kako se oni rade?
Kako da je definisem kaok apstraktni tip? Nikako ne shvatam! :udri:

User · **Poslato:** 02.07.2006. 15:38:16

Darth Vercundus je napisao:

@user:

Mozes li da dodas i za grafove?

Definicije pojmova u teoriji grafova

Graf G predstavlja uredjeni skup (V, E), gde je V skup cvorova (vertices), a E skup ivica (edges), u kome svaka ivica predstavlja par (x, y) cvorova iz V. Kazemo da su dva cvora susedna (adjacent) ako i samo ako postoji ivica koja ih spaja, i takodje da je cvor v susedan (incident) ivici e ako i samo ako je v jedan od cvorova spojenih ivicom e. Broj ivica koje su susedne sa nekom cvorom je stepen (degree) tog cvora. Svi cvorovi koji su susedni nekom cvoru x se nazivaju susedima (neighbors) x. Ivica koja spaja neki cvor x sa samim sobom zove se petlja (loop). Prost graf je graf koji nema ni petlji ni visestrukih ivica, sto znaci da nijedna dva cvora nisu spojena sa vise od jednom ivicom. Graf moze biti neusmeren (undirected) ili usmeren (directed), kod koga svaka ivica ima i svoj smer (znaci ako je x povezano sa w, ne mora biti i da je w povezano sa x). Takodje, graf moze biti i tezinski (weighted) ako svaka ivica ima sebi dodeljenu neku vrednost (tezinu). I netezinski graf moze se posmatrati kao tezinski, s tim sto bi tezina svake ivice bila jednaka (recimo 1). Zato u daljem tekstu necu navoditi eksplicno da li je graf tezinski ili ne, ukoliko to nije od krucijalnog znacaja za sam algoritam. Put (path) od cvora x do nekog drugog cvora y je niz ivica koji spaja ova dva cvora, u kome se svaka ivica iz grafa pojavljuje najvise jedanput. Ako neki niz ivica spaja cvor sa samim sobom, onda se takav niz zove krug (cycle). Drvo (tree) je graf koji nema krugova. Za graf kazemo da je povezan (connected) ako i samo ako za svaka dva njegova cvora postoji put koji ih spaja. Ako graf nije povezan, onda se on moze razbiti na povezane komponente (connected components), disjunktne po cvorovima. Za graf kazemo da je k-povezan akko izmedju svaka dva cvora postoji k puteva disjunktnih po ivicama. Specijalno, za 2-poveznan graf kazemo da je bipovezan. Usmeren graf je jako povezan akko za svaka dva cvora v i w postoji put od x do w kao i od w do x. Ojlerov put (Eulerian tour) u grafu je put (ili krug) koji sadrzi svaku ivicu tacno jednom. Hamiltonov put (Hamiltonian tour) je put (ili krug) koji sadrzi svaki cvor tacno jednom.

Oblilasci grafa

Obilazak grafa (graph traversal) je princip kojim treba obici svaku ivicu i svaki cvor nekog grafa. Ovo je izuzetno cesto potrebno uraditi, stavise deo skoro svakog slozenijeg algoritma je neki obilazak grafa. Ovde cu opisati 2 algoritma za obilazak:

DFS

DFS (Depth First Search) je obilazak grafa "u dubinu". Obelezimo sve cvorove da nisu prodjeni. Sada uzmemo neki cvor obelezimo ga kao prodjen, i skeniramo sve njegove susede. Za svakog koji nije prodjen, odmah pozovemo DFS rekurzivno. Jasno je odakle ime ovom algoritmu, jer on graf bukvalno prolazi "u dubinu". Ukoliko je ostao jos neki neobidjen cvor po zavrsetku rada algoritma, znaci da graf nije povezan. Ovo je ujedno i najlaksi moguci nacin za pronalazenje povezanih komponenti grafa. Pri oblisaku grafa, mozemo numerisati cvorove redom kojim ih obilazimo, cime dobijamo DFS numeraciju cvorova. Izuzetno jednostavan algoritam za implementiranje. Slozenost algoritma je O(|V|+|E|), jer svaki cvor i svaku ivicu razmatramo konstantan broj puta (cvor jednom a ivicu dvaput).

BFS

BFS (Breadth First Search) je obilazak grafa "u sirinu". Za ovaj algoritam koristi se struktura podataka red (queue). Red je na pocetku prazan, a onda u njega ubacujemo jedan element. U svakoj iteraciji, uzimamo sledeci element sa reda, i, kao malopre, skeniramo sve njegove susede. Sve koji nisu obidjeni stavljamo na queue. Na ovaj nacin graf obilazimo "red po red", dakle prvo cvor od koga smo posli, pa sve njegove susede na prvom nivou, pa sve na drugom itd. Zato, kada prvi put obidjemo neki cvor v, nivo na kome smo ga obisli je ujedno i najkraci put od polaznog cvora do cvora v (ukoliko graf nije tezinski). Kao i malopre, ukoliko graf nije povezan treba pustiti BFS iz nekog cvora svake komponente. Slozenost algoritma je ista kao i DFS-a, O(|V|+|E|).

Vidimo da su oba algoritma iste slozenosti. Iz mog iskustva (ne garantujem za istinitost podataka koje cu upravo da iznesem), u C-u DFS radi nesto brze nego BFS, za razliku od Pascal-a, gde je obrnuto. Naravno, ovo umnogome zavisi i od tipa grafa, i od optimizacija samog kompajlera i od jos trista cudesa, ali moje testiranje je pokazalo podatke koje sam rekao. Razlika je inace mala, cinjenica je da su algoritmi iste slozenosti, ali ipak osetna.

kliford · **Poslato:** 02.07.2006. 16:12:39

baneizalfe je napisao:

Data je jednostruko spregnuta lista celih brojeva sortirana u rastućem redosledu. Definiše ovu strukturu kao apstraktni tip i implementirajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.

Kod:

//Mislim da bi bilo najbolje da se element doda na pocetak liste,
//pa ako je veci od sledeceg, da zamene mesta i tako do kraja

// Dodavanje elementa na pocetak liste
   public void Add(Object aData){
      mHead = new ListNode(aData, mHead);
      mCurrent = mHead;
      while(mCurrent.Next!=null){
         if(mCurrent>mCurrent.Next){
            Object pom=mCurrent.Next;
            mCurrent.Next=mCurrent;
            mCurrent=pom;
         }
      }
      
   }

Ne znam kako da pretvorim ovo u pastraktni tip...

Mislim da ne bi trebalo ovo sa apstraktnim tipovima da nas brine jer su apstraktne klase one klase koje se ne mgou instancirati, vec samo nasledjivati... Nece nas terati da pisemo celu klasu LLNodeSaGLupomMetodom koja naslejduje klasu LLNode...

Inace, Bane, ne mozes da se igras sa objektima kao da su prosti tipovi.. ako su A i B objekti, i imas pseudokod:
A = 5;
B = A;
A = 7;
//vrednost i A i B su sad 7....
Zatim, ne mozes da pravis instancu klase Object jer je to apstraktna klasa (a i nemas konstruktor new Object()

)...
Trece... kad uporedjujes cvorove, ti uopredjujes njihov sadrzaj... znaci, ne mozes da stavis current>current.next, nego current.data>current.next.data...
Zatim, kad pravis "mHead = _neki_cvor_", moras da stavis "LLNode mHead = _neki_cvor_"... kontash?
Generalno, dobri su ti algoritmi, ali ti kazem da pazis na sintaksne greske

evo tvog algoritma ispravljenog:

Kod:

    public void addSort(int i){ 
      LLNode mHead = new LLNode(i, this); 
      LLNode mCurrent = mHead; 
      while(mCurrent.next!=null){ 
         if(mCurrent.value>mCurrent.next.value){ 
            int pom = mCurrent.value;
            mCurrent.value = mCurrent.next.value; 
            mCurrent.next.value = pom; 
         } 
      } 
}

a evo i mog, koji ne ubacuje cvor na pocetak pa da ga premeshta, nego trazi gde moze da se smesti i odmah ga uglavljuje

Kod:

public static void insertSorted(LLNode n, int i){
        if (n==null)
            return;
        if (n.value < i)
            if (n.next.value > i){
                LLNode newNode = new LLNode(i, n.next);
                n.next = newNode;
            } else
            insertSorted(n.next, i);
        new LLNode(i, n);
    }

kliford · **Poslato:** 02.07.2006. 16:18:23

User je napisao:

Vidimo da su oba algoritma iste slozenosti. Iz mog iskustva (ne garantujem za istinitost podataka koje cu upravo da iznesem), u C-u DFS radi nesto brze nego BFS, za razliku od Pascal-a, gde je obrnuto. Naravno, ovo umnogome zavisi i od tipa grafa, i od optimizacija samog kompajlera i od jos trista cudesa, ali moje testiranje je pokazalo podatke koje sam rekao. Razlika je inace mala, cinjenica je da su algoritmi iste slozenosti, ali ipak osetna.

Daj, bre, ako znas C, idi na prethodnu stranu i prevedi one dve metode, nemoj da zaj.ebavash

FONForum

Strukture za sve

Ko je OnLine