Пиши Дома Нужные Работы

Обратная связь

Порядок проведення індівідуальної роботи

Для виконання роботи кожен студент повинен:

1. Відповісти на контрольні питання та пройти усне опитування за теоретичним матеріалом лабораторної роботи;

2. Отримати варіант завдання у викладача;

3. Скласти алгоритм розв’язання задачі;

4. Записати код програми на комп’ютері;

5. Відкомпілювати програму та виправити всі помилки;

6. Запустити програму на виконання;

7. Отримати результати роботи програми і показати їх викладачу;

8. Підготувати і захистити звіт до індівідуальної роботи.

Оформлення і захист звіту

Підготовлений до захисту звіт до лабораторної роботи повинен містити:

1. титульний лист, де вказані номер і назва лабораторної роботи, відомості про виконавця;

2. номер варіанта роботи та текст завдання;

3. відповіді на контрольні запитання до лабораторної роботи;

4. текст програми алгоритмічною мовою Java;

5. лістинг результатів виконання програми.

 

 


 

ДОДАТОК А

Програмний код двійкового дерева пошуку

 

class Node

{

public int iData; // data item (key)

public double dData; // data item

public Node leftChild; // this node’s left child

public Node rightChild; // this node’s right child

public void displayNode() // display ourself

{

System.out.print('{');

System.out.print(iData);

System.out.print(", ");

System.out.print(dData);

System.out.print("} ");

}

} // end class Node

 

////////////////////////////////////////////////////////////////

import java.io.*;

import java.util.*;

public class Tree {

private Node root; // first node of tree

public Tree() // constructor

{ root = null; } // no nodes in tree yet

public Node find(int key) // find node with given key

{

Node current = root; // start at root

while(current.iData != key) // while no match,

{

if(key < current.iData) // go left?

current = current.leftChild;

else // or go right?

current = current.rightChild;

if(current == null) // if no child,

return null; // didn’t find it

}

return current; // found it

} // end find()

public void insert(int id, double dd)



{

Node newNode = new Node(); // make new node

newNode.iData = id; // insert data

newNode.dData = dd;

if(root==null) // no node in root

root = newNode;

else // root occupied

{

Node current = root; // start at root

Node parent;

while(true) // (exits internally)

{

parent = current;

if(id < current.iData) // go left?

{

current = current.leftChild;

if(current == null) // if end of the line,

{ // insert on left

parent.leftChild = newNode;

return;

}

} //

else // or go right?

{

current = current.rightChild;

if(current == null) // if end of the line

{ // insert on right

parent.rightChild = newNode;

return;

}

}

}

}

}

// ----------------------------------------------------

public boolean delete(int key) // delete node

{ // (assumes non-empty list)

Node current = root;

Node parent = root;

boolean isLeftChild = true;

while(current.iData != key) // search for node

{

parent = current;

if(key < current.iData) // go left?

{

isLeftChild = true;

current = current.leftChild;

}

else // or go right?

{

isLeftChild = false;

current = current.rightChild;

}

if(current == null) // end of the line,

return false; // didn’t find it

} // end while

if(current.leftChild==null &&

current.rightChild==null)

{

if(current == root) // if root,

root = null; // tree is empty

else if(isLeftChild)

parent.leftChild = null; // disconnect

else // from parent

parent.rightChild = null;

}

else if(current.rightChild==null)

if(current == root)

root = current.leftChild;

else if(isLeftChild)

parent.leftChild = current.leftChild;

else

parent.rightChild = current.leftChild;

else if(current.leftChild==null)

if(current == root)

root = current.rightChild;

else if(isLeftChild)

parent.leftChild = current.rightChild;

else

parent.rightChild = current.rightChild;

else //

{

Node successor = getSuccessor(current);

if(current == root)

root = successor;

else if(isLeftChild)

parent.leftChild = successor;

else

parent.rightChild = successor;

successor.leftChild = current.leftChild;

} // end else two children

return true; // success

} // end delete()

// ----------------------------------------------------

private Node getSuccessor(Node delNode)

{

Node successorParent = delNode;

Node successor = delNode;

Node current = delNode.rightChild; // go to right child

while(current != null) // until no more

{ // left children,

successorParent = successor;

successor = current;

current = current.leftChild; // go to left child

}

if(successor != delNode.rightChild) // right child,

{ // make connections

successorParent.leftChild = successor.rightChild;

successor.rightChild = delNode.rightChild;

}

return successor; }

// ----------------------------------------------------

 

public void traverse(int traverseType)

{

switch(traverseType)

{

case 1: System.out.print("\nPreorder traversal: ");

preOrder(root);

break;

case 2: System.out.print("\nInorder traversal: ");

inOrder(root);

break;

case 3: System.out.print("\nPostorder traversal: ");

postOrder(root);

break;

}

System.out.println();

}

// ----------------------------------------------------

private void preOrder(Node localRoot)

{

if(localRoot != null)

{

System.out.print(localRoot.iData + " ");

preOrder(localRoot.leftChild);

preOrder(localRoot.rightChild);

}

}

// ----------------------------------------------------

private void inOrder(Node localRoot)

{

if(localRoot != null)

{

inOrder(localRoot.leftChild);

System.out.print(localRoot.iData + " ");

inOrder(localRoot.rightChild);

}

}

// ----------------------------------------------------

private void postOrder(Node localRoot)

{

if(localRoot != null)

{

postOrder(localRoot.leftChild);

postOrder(localRoot.rightChild);

System.out.print(localRoot.iData + " ");

}

}

// ----------------------------------------------------

public void displayTree()

{

Stack globalStack = new Stack();

globalStack.push(root);

int nBlanks = 32;

boolean isRowEmpty = false;

System.out.println( "......................................................");

while(isRowEmpty==false)

{

Stack localStack = new Stack();

isRowEmpty = true;

for(int j=0; j<nBlanks; j++)

System.out.print(' ');

while(globalStack.isEmpty()==false)

{

Node temp = (Node)globalStack.pop();

if(temp != null)

{

System.out.print(temp.iData);

localStack.push(temp.leftChild);

localStack.push(temp.rightChild);

if(temp.leftChild != null || temp.rightChild != null)

isRowEmpty = false;

}

else

{

System.out.print("--");

localStack.push(null);

localStack.push(null);

}

for(int j=0; j<nBlanks*2-2; j++)

System.out.print(' ');

} // end while globalStack not empty

System.out.println();

nBlanks /= 2;

while(localStack.isEmpty()==false)

globalStack.push( localStack.pop() );

} // end while isRowEmpty is false

System.out.println(".....................................");

} // end displayTree()

} // end class Tree

 

 

import java.io.*;

import java.util.*;

public class TreeApp {

public static void main(String[] args) throws IOException

{

int value;

Tree theTree = new Tree();

theTree.insert(50, 1.5);

theTree.insert(25, 1.2);

theTree.insert(75, 1.7);

theTree.insert(12, 1.5);

theTree.insert(37, 1.2);

theTree.insert(43, 1.7);

theTree.insert(30, 1.5);

theTree.insert(33, 1.2);

theTree.insert(87, 1.7);

theTree.insert(93, 1.5);

theTree.insert(97, 1.5);

while(true)

{

System.out.print("Enter first letter of show, ");

System.out.print("insert, find, delete, or traverse: ");

int choice = getChar();

switch(choice)

{

case 's':

theTree.displayTree();

break;

case 'i':

System.out.print("Enter value to insert: ");

value = getInt();

theTree.insert(value, value + 0.9);

break;

case 'f':

System.out.print("Enter value to find: ");

value = getInt();

Node found = theTree.find(value);

if(found != null)

{

System.out.print("Found: ");

found.displayNode();

System.out.print("\n");

}

else

System.out.print("Could not find ");

System.out.print(value + '\n');

break;

case 'd':

System.out.print("Enter value to delete: ");

value = getInt();

boolean didDelete = theTree.delete(value);

if(didDelete)

System.out.print("Deleted " + value + '\n');

else

System.out.print("Could not delete ");

System.out.print(value + '\n');

break;

case 't':

System.out.print("Enter type 1, 2 or 3: ");

value = getInt();

theTree.traverse(value);

break;

default:

System.out.print("Invalid entry\n");

} // end switch

} // end while

} // end main()

public static String getString() throws IOException

{

InputStreamReader isr = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(isr);

String s = br.readLine();

return s;

}

// ---------------------------------------------------------

public static char getChar() throws IOException

{

String s = getString();

return s.charAt(0);

}

//----------------------------------------------------------

public static int getInt() throws IOException

{

String s = getString();

return Integer.parseInt(s);

}

// ----------------------------------------------------

} // end class TreeApp

 


 

ДОДАТОК В

Хеш-таблиця

 

The hashChain.java Program

// hashChain.java

 

import java.io.*;

////////////////////////////////////////////////////////////////

class Link

{ // (could be other items)

private int iData; // data item

public Link next; // next link in list

// -------------------------------------------------------------

public Link(int it) // constructor

{ iData= it; }

// -------------------------------------------------------------

public int getKey()

{ return iData; }

// -------------------------------------------------------------

public void displayLink() // display this link

{ System.out.print(iData + “ “); }

} // end class Link

 

////////////////////////////////////////////////////////////////

class SortedList

{

private Link first; // ref to first list item

// -------------------------------------------------------------

public void SortedList() // constructor

{ first = null; }

// -------------------------------------------------------------

public void insert(Link theLink) // insert link, in order

{

int key = theLink.getKey();

Link previous = null; // start at first

Link current = first;

// until end of list,

while( current != null && key > current.getKey() )

{ // or current > key,

previous = current;

current = current.next; // go to next item

}

if(previous==null) // if beginning of list,

first = theLink; // first --> new link

else // not at beginning,

previous.next = theLink; // prev --> new link

theLink.next = current; // new link --> current

} // end insert()

// -------------------------------------------------------------

public void delete(int key) // delete link

{ // (assumes non-empty list)

Link previous = null; // start at first

Link current = first;

// until end of list,

while( current != null && key != current.getKey() )

{ // or key == current,

previous = current;

current = current.next; // go to next link

}

// disconnect link

if(previous==null) // if beginning of list

first = first.next; // delete first link

else // not at beginning

previous.next = current.next; // delete current link

} // end delete()

// -------------------------------------------------------------

public Link find(int key) // find link

{

Link current = first; // start at first

// until end of list,

while(current != null && current.getKey() <= key)

{ // or key too small,

if(current.getKey() == key) // is this the link?

return current; // found it, return link

current = current.next; // go to next item

}

return null; // didn’t find it

} // end find()

// -------------------------------------------------------------

public void displayList()

{

System.out.print(“List (first-->last): “);

Link current = first; // start at beginning of list

while(current != null) // until end of list,

{

current.displayLink(); // print data

current = current.next; // move to next link

}

System.out.println(“”);

}

} // end class SortedList

////////////////////////////////////////////////////////////////

class HashTable

{

private SortedList[] hashArray; // array of lists

private int arraySize;

// -------------------------------------------------------------

public HashTable(int size) // constructor

{

arraySize = size;

hashArray = new SortedList[arraySize]; // create array

for(int j=0; j<arraySize; j++) // fill array

hashArray[j] = new SortedList(); // with lists

}

// -------------------------------------------------------------

public void displayTable()

{

for(int j=0; j<arraySize; j++) // for each cell,

{

System.out.print(j + “. “); // display cell number

hashArray[j].displayList(); // display list

}

}

// -------------------------------------------------------------

public int hashFunc(int key) // hash function

{

return key % arraySize;

}

// -------------------------------------------------------------

public void insert(Link theLink) // insert a link

{

int key = theLink.getKey();

int hashVal = hashFunc(key); // hash the key

hashArray[hashVal].insert(theLink); // insert at hashVal

} // end insert()

// -------------------------------------------------------------

public void delete(int key) // delete a link

{

int hashVal = hashFunc(key); // hash the key

hashArray[hashVal].delete(key); // delete link

} // end delete()

// -------------------------------------------------------------

public Link find(int key) // find link

{

int hashVal = hashFunc(key); // hash the key

Link theLink = hashArray[hashVal].find(key); // get link

return theLink; // return link

}

// -------------------------------------------------------------

} // end class HashTable

 

 

////////////////////////////////////////////////////////////////

class HashChainApp

{

public static void main(String[] args) throws IOException

{

int aKey;

Link aDataItem;

int size, n, keysPerCell = 100;

// get sizes

System.out.print(“Enter size of hash table: “);

size = getInt();

System.out.print(“Enter initial number of items: “);

n = getInt();

// make table

HashTable theHashTable = new HashTable(size);

for(int j=0; j<n; j++) // insert data

{

aKey = (int)(java.lang.Math.random() *

keysPerCell * size);

aDataItem = new Link(aKey);

theHashTable.insert(aDataItem);

}

while(true) // interact with user

{

System.out.print(“Enter first letter of “);

System.out.print(“show, insert, delete, or find: “);

char choice = getChar();

switch(choice)

{

case ‘s’:

theHashTable.displayTable();

break;

case ‘i’:

System.out.print(“Enter key value to insert: “);

aKey = getInt();

aDataItem = new Link(aKey);

theHashTable.insert(aDataItem);

break;

case ‘d’:

System.out.print(“Enter key value to delete: “);

aKey = getInt();

theHashTable.delete(aKey);

break;

case ‘f’:

System.out.print(“Enter key value to find: “);

aKey = getInt();

aDataItem = theHashTable.find(aKey);

if(aDataItem != null)

System.out.println(“Found “ + aKey);

else

System.out.println(“Could not find “ + aKey);

break;

default:

System.out.print(“Invalid entry\n”);

} // end switch

} // end while

} // end main()

//--------------------------------------------------------------

public static String getString() throws IOException

{

InputStreamReader isr = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(isr);

String s = br.readLine();

return s;

}

//-------------------------------------------------------------

public static char getChar() throws IOException

{

String s = getString();

return s.charAt(0);

}

//-------------------------------------------------------------

public static int getInt() throws IOException

{

String s = getString();

return Integer.parseInt(s);

}} // end class HashChainApp

 

МЕТОДИЧНІ ВКАЗІВКИ

 

до виконання лабораторних робіт студентів з дисципліни

ТЕОРІЯ АЛГОРИТМІВ

для студентів I курсу денної форми навчання

Напрям підготовки – комп’ютерні науки

 

 

Укладачі: Шпінарева І.М., к.ф.-м.н.

 

 

Підп. до друку Формат 60Х84/16 Папір офс.

 

Умовн. а.а. Тираж Замовл.

 

 

 

 

Одеський державний екологічний університет,

65016, м. Одеса, вул. Львівська, 15

 

 

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2017 pdnr.ru Все права принадлежат авторам размещенных материалов.