Imię ..........Piotr
Nazwisko ........Lewicki
Wiek ..
Wzrost 72.4409449 inch
Waga ...2574.9728 oz
Narodowość .........Polska

30-06-2010

Binary search – wyszukiwanie binarne – język java

Filed under: Java — Tagi: , , , — Levik @ 11:59

Ja na pierwszym roku studiów musiałem chyba około 3 razy napisać wyszukiwanie binarne na różnego rodzaju laboratoriach poczynając od podstawach programowania, a kończąc na Algorytmach i strukturach danych. Także myślę, że ktoś może z tego przykładu skorzystać. Dodam tylko, że wyszukiwanie binarne można rozwiązać w sposób rekurencyjny. Dość naturalny do wyobrażenia w tym przypadku. Kod poniżej prezentuje właśnie to podejście.

Co do samego algorytmu jak zawsze nie będę się przemęczał (nie dlatego, że mi się nie chce, ale inni opisali go już setki razy)

Wyszukiwanie binarne



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class BinarySearch {
 
	public static int tab[] = {3,5,12,20,28,34,38,41,55,67,71,78,81,85,94,99,102};
 
	//funkcja zwraca indeks elementu, jeśli go nie ma zwróci -1
	public static int binSearch(int find,int left,int right){
		//System.out.println("Szukam "+find+" lewy: "+left+" a prawy: "+right);
		int index=(left+right)/2;
 
		if(tab[index]==find){
 
			return index;
 
		} else {
 
			if(left>right){
 
				//System.out.println("Nie ma takiej liczby!");
				return -1;
 
			} else {
 
				if(tab[index]<find){
 
					return binSearch(find,index+1,right);
 
				} else {
 
					return binSearch(find,left,index-1);
				}
			}
		}
	}
 
	public static void main(String[] args){
		System.out.println(binSearch(67,0,16));
	}
 
}

Pozdrawiam Piotr!!!

28-06-2010

Sortowanie przez kopcowanie – Kopiec zupełny – HeapSort – Java

Filed under: Java — Tagi: , , — Levik @ 17:00

Hej, dzisiaj zaliczyłem ostatni przedmiot, kurs. Także sesja GAME OVER czytaj. „Mission Accomplished”. Tekst rodem z RED ALERT.

sesja zaliczona

Zapewne wrzucę jeszcze kilka swoich kodów na stronkę. Dzisiaj sortowanie przez kopcowanie zaimplementowane obiektowo. Struktura kopca zupełnego znajduje się w pliku heap.java, a jego przykładowe zastosowanie (tutaj sortowanie) w pliku test.java.

Oto kod:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//********************************
//wierzchołek   1
//lewy potomek  2*i
//prawy potomek 2*i+1
//********************************
public class Heap {
 
	private int tab[];
	private int size = 0;
 
	public Heap(int size){
		tab = new int[size+1];
	}
 
	public void insert(int val){
		tab[++size]=val;
		up();
	}
 
	public void up(){
		int temp=tab[size];
		int n=size;
 
		while( (n!=1) && (tab[n/2]<=temp) ){
			tab[n] = tab[n/2];
			n=n/2;
		}
		tab[n]=temp;
	}
 
	public int getFirst(){
		int temp=tab[1];
		tab[1]=tab[size--];
		down();
		return temp;
	}
 
	public void down(){
		int i=1;
		while(true){
			int pos=2*i;
 
			if(pos>size)
				break;
 
			if(pos+1<=size)
				if(tab[pos]<tab[pos+1])
					pos++;
 
			if(tab[i]>=tab[pos])
				break;
 
			int temp = tab[pos];
			tab[pos]=tab[i];
			tab[i]=temp;
 
			i=pos;
		}
	}
}

…a teraz kod przykładu…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Test {
 
	public static void main(String[] args){
		int tab[] = {32,43,2,46,23,1,0,-34,54,230};
 
		Heap heap = new Heap(10);
 
		for(int i=0;i<tab.length;i++)
			heap.insert(tab[i]);
 
		for(int i=tab.length;i>0;i--)
			tab[i-1]=heap.getFirst();
 
		System.out.println("Tablica posortowana");
 
		for(int i=0;i<tab.length;i++)
			System.out.println(tab[i]);
	}
 
}

17-05-2010

Binarne drzewo poszukiwań – Binary Search Tree – BST – JAVA

Filed under: Java — Tagi: , , — Levik @ 16:39

Hej,

tym razem oddaję w wasze ręce binarne drzewo poszukiwań. Pisząc kod korzystałem z książki „Algorytmy od podstaw” więc siłą rzeczy kod jest podobny. Jeśli dopiero zaczynacie zabawę z drzewami pomocny może być aplet pod tym adresem.

Główne klasy to:
drzewo - BSTree: insert(), delete(),search(),preOrder(),inOrder(),postOrder();
pojedyńczy węzeł - Node: min(),max(),succ(),pred(),height();

[...]Binarne drzewo poszukiwań (skrót BST, z ang. Binary Search Tree) – dynamiczna struktura danych w postaci drzewa binarnego stosowana do szybkiego wyszukiwania. Drzewa BST służą do realizacji bardziej abstrakcyjnych struktur danych, np. zbiorów, czy słowników.[...]

Oto drzewo wykorzystane w przykładzie:

drzewo BST


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

public class BSTree {
	private Node root;
	private Comparator comp;
 
	//konstruktor
	public BSTree(Comparator comparator){
		comp = comparator;
	}
 
	//wyświetlanie inOrder
	public void inOrder(Node node){
		if(node!=null){
			inOrder(node.getLeft());
			System.out.print(node+", ");
			inOrder(node.getRight());
		}
	}
 
	//wyświetlanie preOrder
	public void preOrder(Node node){
		if(node!=null){
			System.out.print(node+", ");
			preOrder(node.getLeft());
			preOrder(node.getRight());
		}
	}
 
	//wyświetlanie postOrder
	public void postOrder(Node node){
		if(node!=null){
			postOrder(node.getLeft());
			postOrder(node.getRight());
			System.out.print(node+", ");
		}
	}
 
	//usuwanie wartości z drzewa
	public Node delete(Object value){
		Node node = search(value);
		if(node==null)
			return null;
 
		Node deleted;
 
		if(node.getLeft()!= null && node.getRight() != null)
			deleted = node.succ();
		else
			deleted = node;
 
		Node replacement;
 
		if(deleted.getLeft() != null)
			replacement = deleted.getLeft();
		else
			replacement = deleted.getRight();
 
		if(replacement != null)
			replacement.setParent(deleted.getParent());
 
		if(deleted == root)
			root = replacement;
		else
			if(deleted.isSmaller())
				deleted.getParent().setLeft(replacement);
			else
				deleted.getParent().setRight(replacement);
 
		if(deleted != node){
			Object deletedValue = node.getValue();
			node.setValue(deleted.getValue());
			deleted.setValue(deletedValue);
		}
 
		return deleted;
	}
 
	//wstawianie wartości do drzewa
	public Node insert(Object value){
		Node parent = null;
		Node node = root;
		int result = 0;
 
		while(node!=null){
			parent = node;
			result = comp.compare(value, node.getValue());
 
			if(result<=0)
				node = node.getLeft();
			else
				node = node.getRight();
		}
 
		Node inserted = new Node(value);
		inserted.setParent(parent);
 
		if(parent==null)
			root=inserted;
		else 
			if(result<0)
				parent.setLeft(inserted);
			else 
				parent.setRight(inserted);
 
		return inserted;
	}
 
	//wyszukiwanie elementu
	public Node search(Object value){
 
		Node node = root;
 
		while(node!=null){
			int result = comp.compare(value, node.getValue());
 
			if(result==0)
				return node;
 
			if(result<0)
				node = node.getLeft();
			else
				node = node.getRight();
		}
		return null;
	}
 
	public Node getRoot(){
		return root;
	}
 
	public String toString(){
		return root.toString();
	}
}

No i proszę oto nasza klasa węzeł…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

public class Node implements Cloneable {
 
	private Node parent;
	private Node left;
	private Node right;
 
	private Object value;
 
	public Node(Object value){
		this(value,null,null);
	}
 
	public Node(Object v,Node l,Node r){
		value=v;
		left=l;
		right=r;
 
		if(left!=null){
			left.setParent(this);
		}
 
		if(right!=null){
			right.setParent(this);
		}
	}
 
	//wysokosc
	public int height(Node node){
		return node==null?-1:1+Math.max(height(node.left),height(node.right));
	}
 
	//następnik
	public Node pred(){
		if(getLeft()!=null)
			return getLeft().max();
 
		Node node = this;
 
		while(node.isSmaller())
			node = node.getParent();
 
		return node.getParent();
	}
 
	//następnik
	public Node succ(){
		if(getRight()!=null)
			return getRight().min();
 
		Node node = this;
 
		while(node.isLarger())
			node = node.getParent();
 
		return node.getParent();
	}
 
	//najmniejszy węzeł
	public Node min(){
		Node node = this;
 
		while(node.getLeft()!=null)
			node=node.getLeft();
 
		return node;
	}
 
	//największy węzeł
	public Node max(){
		Node node = this;
 
		while(node.getRight()!=null)
			node=node.getRight();
 
		return node;
	}
 
	public Node clone() throws CloneNotSupportedException {
		Node node = (Node)super.clone();
		return node;
	}
 
	public Object getValue(){
		return value;
	}
 
	public Node getLeft(){
		return left;
	}
 
	public Node getRight(){
		return right;
	}
 
	public Node getParent(){
		return parent;
	}
 
	public void setLeft(Node node){
		left = node;
	}
 
	public void setRight(Node node){
		right = node;
	}
 
	public void setParent(Node node){
		parent = node;
	}
 
	public void setValue(Object val){
		value=val;
	}
 
	public String toString(){
		return value.toString();
	}
 
	//czy jest mniejszym z synow
	public boolean isSmaller(){
		return getParent() != null && this.equals(getParent().getLeft());
	}
 
	//czy jest wiekszym z synow
	public boolean isLarger(){
		return getParent() != null && this.equals(getParent().getRight());
	}
}

Interfejst komparatora, bez niego ani rusz. Poniżej zamieściłem dwa przykładowe komparatory dla liczb (int) i znaków (char).

1
2
3
4
5

public interface Comparator {
 
    public int compare(Object left, Object right) throws ClassCastException;
 
}

Przykładowy komparator dla znaków (char):

1
2
3
4
5
6
7
8

public class CharCom implements Comparator {
 
	public int compare(Object left, Object right) throws ClassCastException {
		int result = (Character)left-(Character)right;
		return result;
	}
 
}

Przykładowy komparator dla liczb (Int):

1
2
3
4
5
6
7
8

public class IntCom implements Comparator {
 
	public int compare(Object left, Object right) throws ClassCastException {
		int result = (Integer)left-(Integer)right;
		return result;
	}
 
}

Niewielki przykład zastosowania kodu:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Test {
 
	public static void main(String[] args){
		BSTree tree = new BSTree(new IntCom());
 
		tree.insert(13);
		tree.insert(14);
		tree.insert(10);
		tree.insert(5);
		tree.insert(12);
		tree.insert(11);
		tree.insert(7);
		tree.insert(4);
		tree.insert(6);
 
		//tree.delete(10);
 
		System.out.println("postOrder:");
		tree.postOrder(tree.getRoot());
		System.out.println("\ninOrder:");
		tree.inOrder(tree.getRoot());
		System.out.println("\npreOrder:");
		tree.preOrder(tree.getRoot());
 
		System.out.println();
		System.out.println("min: "+tree.getRoot().min());
		System.out.println("max: "+tree.getRoot().max());
 
	}
 
}

W razie pytań proszę pisać via e-mail lub zakładkę kontakt.

Pozdrawiam Piotr Lewicki

22-03-2010

Lista jednokierunkowa z głową – Java

Filed under: Java — Tagi: , — Levik @ 17:44

Hej! Na drugim semestrze realizuję kurs „Algorytmu i struktury danych”, pomyślałem, że dla potomnych będę wrzucał kody źródłowe swoich programów. Dużo mówi się też o wzorcach projektowych, więc z pewnością tutaj zagoszczą. Dzisiaj oddaję do waszej dyspozycji listę jedno kierunkową z głową + dodawanie/ usuwanie ostatniego elementu za pomocą ogona.

Pozdrawiam…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

public class LinkedList {
 
     //zmienne składowe
     private Link head; // głowa listy
     private Link tail; // ogon listy, wykorzystywany do dodawania i usuwania z konca listy
     private int size=0; // liczba elementów aktualnie przechowaywanych na liście
 
     //konstruktor
     public LinkedList(){
          head = new Link();
          tail = head;
     }
 
     //dodaj element na początku
     public void addFirst(Object ob){
          Link temp = new Link(head.element,head.next);
          head.element=ob;
          head.next=temp;
          size++;
          tail = get(size+1);
     }
     //dodaj element na końcu - za pomocą ogona
     public void addOnTail(Object ob){
          tail.element = ob;
          tail.next=new Link();
          tail = tail.next;
          size++;
     }
 
     //dodaj element na końcu - sposób bez ogona
     public void addLast(Object ob){
          if(size==0){
               addFirst(ob);
          } else {
               Link last = get(size+1);
               last.element = ob;
               last.next = new Link();
               tail = last.next;
               size++;
          }
     }
 
     //zwraca węzęł o podanym numerze
     private Link get(int index){
          Link temp=head;
          for(int i=0;i<index-1;i++)
               temp = temp.next;
          return temp;
     }
 
     //zwraca element
     public Object getEl(int index){
          Link temp=head;
          for(int i=0;i<index-1;i++)
               temp = temp.next;
          return temp.element;
     }
 
     //wyszukaj elementu zwraca numer elementu na liście, jeśli go nie ma -1
     public int find(Object ob){
          Link temp;
          for(int i=1;i<=size;i++){
               temp = get(i);
               if((temp.element).equals(ob))
               return i;
          }
          return -1;
     }
 
     //usuń pierwszy element
     public void delFirst(){ head=head.next; size--; }
 
     //usuń ostatnij element
     public void delLast(){ tail=get(size); get(size-1).next=tail; tail.next=null; size--; }
 
     //usuń wybrany element
     public boolean del(Object ob){
          int number = find(ob);
 
          if(number!=-1){
               if(number>1 && number<size){
                    Link temp_left = get(number-1);
                    temp_left.next=get(number+1);
                    size--;
                    return true;
               }else{
                    if(number==1){
                         delFirst();
                         return true;
                    } else {
                         delLast();
                         return true;
                    }
               }
          } else
               return false;
     }
 
     //podaj rozmiar listy
     public int size(){ return size; }
 
     //zwróć pierwszy węzeł
     public Link first() { return head; }
 
     //zwróć ostatnij węzeł - nie ogon!!!
     public Link last() { return get(size); }
 
     //toString()
     public String toString(){
          String content = "";
          for(int i=1;i<=size;i++)
               content += get(i).element+" ";
               return content;
          }
     }
 
     //Węzeł listy
     class Link {
          Object element;
          Link next;
 
          public Link(){
               this(null,null);
          }
 
          public Link(Object ob){
               this(ob,new Link());
          }
 
          public Link(Object ob, Link lnk){
               element = ob;
               next = lnk;
          }
     }

Oto przykładowe wykorzystanie listy. W tym wypadku pracujemy z obiektem klasy String, ale może być to zupełnie inna klasa zadeklarowana przez nas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Test {
 
	public static void main(String[] args){
		LinkedList lista = new LinkedList();
 
		System.out.println("Dodaje imie na poczatku:");
		lista.addFirst("Piotr");
		System.out.println("-    "+lista);
 
		System.out.println("Dodaje imie na poczatku:");
		lista.addFirst("Marcin");
		System.out.println("-    "+lista);
 
		System.out.println("Dodaje imie na końcu:");
		lista.addOnTail("Ania");
		System.out.println("-    "+lista);
 
		System.out.println("Usuwam imię 'Ania':");
		lista.del("Ania");
		System.out.println("-    "+lista);
 
		System.out.println("Na liscie znajduja sie "+lista.size()+" elementy");
		System.out.println("Sprawdzam czy na liscie jest imie 'Piotr'");
 
			String temp = "Piotr";
 
			if(lista.find(temp)!=-1)
				System.out.println("Imie znajduje sie na pozycji: "+lista.find(temp));
			else
				System.out.println("Brak elementu");
 
	}
}

- by levik@wp.pl L3VIK -

Jesteś gościem numer - Twój adres IP to: 38.107.179.212