Порядок проведення індівідуальної роботи Для виконання роботи кожен студент повинен:
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
|