Литература.
Моделирование абстрактных типов данных (АТД) для различных реализаций
Предполагая, что узел h красный и правый узел и левый узел правого узла черные, сделать правый узел h или один из дочерних узлов красным. If (contains (hi)) return rank (hi) — rank (lo) + 1; //если дерево содержит наибольший, то вернуть количество ключей между наибольшим и наименьшим +1. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., «Мир», 1978 г., переиздание — М… Читать ещё >
Литература. Моделирование абстрактных типов данных (АТД) для различных реализаций (реферат, курсовая, диплом, контрольная)
- 1. А. Ахо, Дж. Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. М., Изд-во «Вильямс», 2000 г.
- 2. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., «Мир», 1976 г., переиздание — М., Изд-во «Вильямс», 2000 г.
- 3. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., «Мир», 1978 г., переиздание — М., Изд-во «Вильямс», 2000 г.
- 4. Н. Вирт Алгоритмы + структуры данных = программы. М., «Мир», 1985 г.
- 5. Н. Вирт Алгоритмы и структуры данных. М., Издат-во «Вильямс», 1998 г.
- 6. У. Топп, У. Форд. Структуры данных в С++. М., Изд-во «Бином», 2000 г.
Приложение А.
namespace Nastya_Kurs01.
{.
class Program.
{.
static void Main (string[] args).
{.
LinkedList L = new LinkedList ();
L.AddListElement (); L. AddListElement ();
Stack S = Program. List_Stack (L);
//Console.WriteLine (S.Pop ().Value);
L = Program. Stack_List (S);
Console.WriteLine (L.GetListElement (0).Value);
Console.ReadKey ();
}.
static Stack List_Stack (LinkedList List).
{.
Stack Stack = new Stack (List.GetSize ());
for (int i = 0; i < List. GetSize (); i++).
{.
Stack.Push (new StackElement (List.GetListElement (i).Value));
}.
return Stack;
}.
static LinkedList Stack_List (Stack Stack).
{.
LinkedList LinkedList = new LinkedList ();
int n = Stack. GetSize ();
for (int i = 0; i < n; i++).
{.
LinkedList.AddNode (Stack.Pop ().Value);
}.
return LinkedList;
}.
}.
class ListElement.
{.
public ListElement (int value).
{.
this.value = value;
}.
private int value;
public int Value.
{.
get { return this. value; }.
set { this. value = value; }.
}.
private ListElement next;
public ListElement Next.
{.
get { return next; }.
set { next = value; }.
}.
}.
class LinkedList //Класс связного списка.
{.
public LinkedList ().
{.
this.size = 0;
this.head = null;
this.tail = null;
this.thisList = this;
}.
private int size;
private ListElement head;
private ListElement tail;
private LinkedList thisList;
public int GetSize () { return size; } // метод получить размер
public void AddListElement () // метод добавить.
{.
ListElement newElement = new ListElement (size);
this.size++;
if (this.head == null).
{.
this.head = newElement;
this.tail = newElement;
}.
else.
{.
this.tail.Next = newElement;
this.tail = newElement;
}.
}.
public void AddNode (int value).
{.
ListElement newElement = new ListElement (value);
this.size++;
if (this.head == null).
{.
this.head = newElement;
this.tail = newElement;
}.
else.
{.
this.tail.Next = newElement;
this.tail = newElement;
}.
}.
public ListElement GetListElement (int number).
{.
if (number > this. size).
{.
Console.WriteLine («Данного элемента не существует»);
return null;
}.
else.
{.
ListElement Element = this. head;
for (int i = 0; i < number; i++).
{.
Element = Element. Next;
}.
return Element;
}.
}.
public void DeleteList () // метод удалить лист.
{.
this.thisList = new LinkedList ();
}.
}.
class StackElement{.
public StackElement (int value).
{.
this.value = value;
}.
private int value;
public int Value.
{.
get { return this. value; }.
set { this. value = value; }.
}.
}.
class Stack.
{.
private StackElement[] This;
private int topIndex;
public Stack (int size).
{.
this.This = new StackElement[size];
}.
public int GetSize ().
{.
return this.This.Length;
}.
public bool IsEmpty ().
{.
return This[0] == null;
}.
public void Push (StackElement item).
{.
if (This[0] == null).
{.
This[0] = item;
topIndex = 0;
}.
else.
{.
topIndex = topIndex + 1; This[topIndex] = item;
}.
}.
public StackElement Pop ().
{.
if (IsEmpty ()).
{.
Console.WriteLine («Стек пустой»);
return null;
}.
else.
{.
StackElement e = This[topIndex];
if (topIndex ≠ 0).
topIndex = topIndex-1;
return e;
}.
}.
}.
}.
Приложение Б.
Класс main ()
import java.util.Dictionary;
import java.util.Hashtable;
public class part2.
{.
public static void main (String[] args).
{.
String KEY="Интернет магазин"; //ключ, по которому будем искать в тексте.
Dictionary dict=new Hashtable (); //создаем словарь.
String S=new String («Интернет магазин — это специализированный сайт, предлагающий посетителям возможности по приобретению тех или иных товаров или услуг. Идея продавать что-то через Интернет по возрасту сравнима с самим Интернетом. Однако период интенсивного развития онлайновых магазинов связан с появлением веба. Интернет-магазин может быть создан и торговой фирмой, уже имеющей большой опыт продаж в офлайне, и коллективом энтузиастов, решивших сразу начать с онлайна. Онлайновая торговля имеет целый ряд отличительных особенностей, требующих особенного подхода.»);
//текст, в котором будет реализован поиск.
try
{.
file.WriteObject(S);
dict.put (4, «Интернет магазин»); //ключ 4.
System.out.println (file.ReadObject().length ()+" символов"); //длина текста (=7710).
long t1=System.currentTimeMillis(); //засекаем время начала поиска по ключу.
KMP.KnuthMorrisPratt(file.ReadObject(), KEY); //используя чтение из файла, находим по ключу KEY.
long t2=System.currentTimeMillis(); //окончание времени поиска по ключу.
long t3=System.currentTimeMillis(); //засекаем время начала поиска по ключу.
int key=4; //ищем подстроку Интернет магазин.
KMP.KnuthMorrisPratt(file.ReadObject(), dict. get (key)); //используя чтение из файла, находим строки по ключам из словаря.
long t4=System.currentTimeMillis(); //окончание времени поиска по ключу.
System.out.println («Время поиска по ключу: „+(t2-t1) +“ мс»); // вывод результата.
System.out.println («Время поиска со словарем: „+(t4-t3) +“ мс»); // вывод результата.
}.
catch (Exception e) //если файл не найден, бросаем исключение.
{.
e.getMessage ();
}.
}.
}.
Класс KMP, в котором описан алгоритм поиска ключа
public class KMP.
{.
public static int KnuthMorrisPratt (String where, String what).
{.
int n=where.length (); //длина строки, в которой происходит поиск.
int m=what.length (); //длина подстроки.
//формирование таблицы сдвигов.
int[] table=new int [m]; //таблица сдвигов (массив).
table[0]=0; //значение первого элемента =0.
int shift=0; //сдвиг равен 0.
for (int q=1; q.
{.
while (shift > 0 && (what.charAt (shift) ≠ what. charAt (q))) //ищем совпадающее начало кусочка текста и подстроки.
shift = table[shift-1]; //меняем сдвиг.
if (what.charAt (shift)==what.charAt (q)) shift++; //считаем количество вхождений символов.
table[q]=shift; //записываем значения в таблицу — создаем префиксную функцию.
}.
//поиск с использованием таблицы сдвигов.
shift=0; //сдвиг равен 0.
for (int i=0; i.
{.
while (shift>0 && what. charAt (shift)≠where.charAt (i)) //если первые символы не совпали, то.
shift=table[shift-1]; //двигаем текст на максимально возможное знаечение.
if (what.charAt (shift)==where.charAt (i)) //если символы совпадают, то.
shift++; //увеличиваем количество совпавших символов.
if (shift==m) //если длина совпадения равна длине подстроки.
return i-m+1; //подстрока найдена.
}.
return -1; //если ничего не найдено, возвращаем некорректное значение.
}.
}.
Класс file, позволяющий создать и использовать файл
import java.io.*;
public class file //создание — чтение файла.
{.
public static void WriteObject (String S) throws IOException //создание файла, на вход идет строка (в нашем случае текст).
{.
FileOutputStream fileOutput=new FileOutputStream («file.dat»); //открываем файловый поток.
ObjectOutputStream objectOutput=new ObjectOutputStream (fileOutput); //открываем поток, в который будем записывать объект (в нашем случае текст).
objectOutput.writeObject (S); //записываем в файл строку.
fileOutput.close (); //закрываем поток.
objectOutput.close (); //закрываем поток.
}.
public static String ReadObject () throws IOException, ClassNotFoundException //извлечение файла.
{.
FileInputStream fileInput=new FileInputStream («file.dat»); //открываем файловый поток.
ObjectInputStream objectInput=new ObjectInputStream (fileInput); //открываем поток, из которого будем читать объект (в нашем слкчае текст).
String s=(String) objectInput. readObject (); //создаем переменную, в которую записываем текст.
fileInput.close (); //закрываем поток.
objectInput.close (); //закрываем поток.
return s; //возвращаем строку (текст).
}.
}.
Приложение В.
using System;
using System. Diagnostics;
using System.Collections.Generic;
using System. Linq;
using System. Text;
namespace PersonnelDepartmentApp {.
public class Sorting {.
public void swap (int[] arr, int i, int j) {.
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}.
public void swap (int[] arr, int i) {.
int temp;
temp = arr[i];
arr[i] = arr[i — 1];
arr[i — 1] = temp;
}.
public int maxValue (int[] arr) {.
int maxValue = int. MinValue;
for (int i = 0; i < arr. Length; i++) {.
if (arr[i] > maxValue) {.
maxValue = arr[i];
}.
}.
return maxValue;
}.
public int[] selectionSort (int[] mass) {.
int[] a = (int[]) mass. Clone ();
int len = a. Length;
for (int i = 0; i < len — 1; i++) {.
int min = i;
for (int j = i + 1; j < len; j++) {.
if (a[j] < a[min]) {.
min = j;
}.
}.
if (min ≠ i) {.
int t = a[i];
a[i] = a[min];
a[min] = t;
}.
}.
return a;
}.
public int[] bubbleSort (int[] mass){.
int[] arr = (int[]) mass. Clone ();
for (int i = arr. Length-1; i > 0; i—){.
for (int j = 0; j < i; j++){.
if (arr[j] > arr[j+1]).
swap (arr, j, j+1);
}.
}.
return arr;
}.
public int[] gnomeSort (int[] mass) {.
int[] a = (int[]) mass. Clone ();
int size = a. Length, i = 1, j = 2;
while (i < size) {.
//для сортировки по убыванию поменяйте знак сравнения на <
if (a[i — 1] > a[i]) {.
i = j;
j = j + 1;
} else {.
swap (a, i);
i = i — 1;
if (i == 0) {.
i = j;
j = j + 1;
}.
}.
}.
return a;
}.
public int[] insertionSort (int[] mass) {.
int[] m = (int[]) mass. Clone ();
int t, i, j;
for (i = 0; i < m. Length; i++) {.
t = m[i];
for (j=i-1; j>=0 && m[j] > t; j—).
m[j+1] = m[j];
m[j+1] = t;
}.
return m;
}.
public void merge (int[] Mas, int left, int right, int medium) {.
int j = left;
int k = medium + 1;
int count = right — left + 1;
if (count <= 1).
return;
int[] TmpMas = new int[count];
for (int i = 0; i < count; i++) {.
if (j <= medium && k <= right) {.
if (Mas[j] < Mas[k]).
TmpMas[i] = Mas[j++];
else.
TmpMas[i] = Mas[k++];
} else {.
if (j <= medium).
TmpMas[i] = Mas[j++];
else.
TmpMas[i] = Mas[k++];
}.
}.
j = 0;
for (int i = left; i <= right; i++) {.
Mas[i] = TmpMas[j++];
}.
}.
public void mergeSort (int[] a, int l, int r) {.
int m;
// Условие выхода из рекурсии.
if (l >= r).
return;
m = (l + r) / 2;
// Рекурсивная сортировка полученных массивов.
mergeSort (a, l, m);
mergeSort (a, m + 1, r);
merge (a, l, r, m);
}.
public int[] bucketSort (int[] mass) {.
int[] items = new int[mass.Length];
// Предварительная проверка элементов исходного массива.
if (items == null || items. Length < 2) {.
return mass;
}.
int maxValue = items[0];
int minValue = items[0];
for (int i = 1; i < items. Length; i++) {.
if (items[i] > maxValue).
maxValue = items[i];
if (items[i] < minValue).
minValue = items[i];
}.
List[] bucket = new List[maxValue — minValue + 1];
for (int i = 0; i < bucket. Length; i++) {.
bucket[i] = new List ();
}.
// Занесение значений в пакеты.
for (int i = 0; i < items. Length; i++) {.
bucket[items[i] - minValue]. Add (items[i]);
}.
int position = 0;
for (int i = 0; i < bucket. Length; i++).
{.
if (bucket[i]. Count > 0).
{.
for (int j = 0; j < bucket[i]. Count; j++).
{.
items[position] = (int) bucket[i][j];
position++;
}.
}.
}.
return items;
}.
public int[] shellSort (int[] mass) {.
int[] a = (int[]) mass. Clone ();
int i, j, k, h, m=0, b=a.Length;
int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11 969, 27 901,.
- 84 801, 213 331, 543 749, 1 355 339, 3 501 671, 8 810 089, 21 521 774,
- 58 548 857, 157 840 433, 410 151 271, 1 131 376 761, 2 147 483 647 };
while (d[m] < b) {.
++m;
}.
while (—m >= 0) {.
k = d[m];
for (i=k; i.
j=i;
h=a[i];
while ((j >= k) && (a[j-k] > h)) {
a[j]=a[j-k];
j = j-k;
}
a[j] = h;
}
}
return a;
}
public int[] heapSort (int[] mass) {
int[] a = (int[]) mass. Clone ();
int n = a. Length, i, sh = 0, b = 0;
while (true) {
b = 0;
for (i = 0; i < n; ++i) {
if (i*2 + 2 + sh < n) {
if (a[i+sh] > a[i*2 + 1 + sh] || a[i + sh] > a[i*2 + 2 + sh]) {
if (a[i*2+1+sh] < a[i*2+2+sh]) {
int t = a[i+sh];
a[i+sh] = a[i*2+1+sh];
a[i*2+1+sh] = t;
b = 1;
} else if (a[i*2+2+sh] < a[i*2+1+sh]) {
int t = a[i+sh];
a[i+sh] = a[i*2+2+sh];
a[i*2+2+sh] = t;
b = 1;
}
}
} else if (i * 2 + 1 + sh < n) {
if (a[i+sh] > a[i*2+1+sh]) {
int t = a[i+sh];
a[i+sh] = a[i*2+1+sh];
a[i*2+1+sh] = t;
b=1;
}
}
}
if (b == 0) {
sh++;
}
if (sh+2==n)
break;
}
return a;
}
public int partition (int[] array, int start, int end) {
int marker = start;
for (int i = start; i <= end; i++) {
if (array[i] <= array[end]) {
int temp = array[marker];
array[marker] = array[i];
array[i] = temp;
marker += 1;
}
}
return marker — 1;
}
public void quickSort (int[] array, int start, int end) {
int pivot;
if (start >= end) {
return;
}
pivot = partition (array, start, end);
quickSort (array, start, pivot-1);
quickSort (array, pivot+1, end);
}
public void stoogeSort (int[] item, int left, int right) {
int tmp, k;
if (item[left] > item[right]) {
tmp=item[left];
item[left]=item[right];
item[right]=tmp;
}
if ((left+1)>=right)
return;
k = (int) ((right — left + 1) / 3);
stoogeSort (item, left, right-k);
stoogeSort (item, left+k, right);
stoogeSort (item, left, right-k);
}
public void executeTest (int[] quantity) {
Random random = new Random ();
Sorting sorter = new Sorting ();
for (int i = 0; i < quantity. Length; i++) {
Console.WriteLine («Отчёт по массиву из «+ quantity[i] + «элементов:»);
int[] mass = new int[quantity[i]];
for (int j = 0; j < quantity[i]; j++) {
mass[j] = random. Next (10 000);
}
long start = 0, end = 0;
Console.Write («Сортировка выбором:»);
try {
start = Stopwatch. GetTimestamp ();
sorter.selectionSort (mass);
end = Stopwatch. GetTimestamp ();
Console.Write ((end — start) + «нс «);
} catch (Exception e) {
Console.Write (e.Message + ««);
Console.WriteLine (e.StackTrace);
}
Console.Write («Сортировка простыми обменами, сортировка пузырькa:»);
try {
start = Stopwatch. GetTimestamp ();
sorter.bubbleSort (mass);
end = Stopwatch. GetTimestamp ();
Console.Write ((end — start) + «нс «);
} catch (Exception e) {
Console.Write (e.Message + ««);
Console.WriteLine (e.StackTrace);
}
Console.Write («Гномья сортировка:»);
try {
start = Stopwatch. GetTimestamp ();
sorter.gnomeSort (mass);
end = Stopwatch. GetTimestamp ();
Console.Write ((end — start) + «нс «);
} catch (Exception e) {
Console.Write (e.Message + ««);
Console.WriteLine (e.StackTrace);
}
Console.Write («Сортировка вставками:»);
try {
start = Stopwatch. GetTimestamp ();
sorter.insertionSort (mass);
end = Stopwatch. GetTimestamp ();
Console.Write ((end — start) + «нс «);
} catch (Exception e) {
Console.Write (e.Message + ««);
Console.WriteLine (e.StackTrace);
}
Console.Write («Сортировка слиянием:»);
try {
start = Stopwatch. GetTimestamp ();
sorter.mergeSort ((int[]) mass. Clone (), 0, mass. Length — 1);
end = Stopwatch. GetTimestamp ();
Console.Write ((end — start) + «нс «);
} catch (Exception e) {
Console.Write (e.Message + ««);
Console.WriteLine (e.StackTrace);
}
Console.Write («Блочная сортировка…
h.right = x. left; //правому узлу h присваиваем левый узел текущего узла
x.left = h; //левому узлу текущего узла присваиваем узел h
x.color = x.left.color; //перекрашиваем текущий узел в цвет узла слева
x.left.color = RED; //узлу слева текущего узла х присваиваем красный цвет
x.N = h. N; //переприсваиваем значение числа узлов
h.N = size (h.left) + size (h.right) + 1; //считаем количество узлов, начиная с h
return x; //возвращаем текущий узел
}
private void flipColors (Node h) //перекрашивание узлов
{
h.color = !h.color; //меняем цвет текущего узла на противоположный
h.left.color = !h.left.color; //меняем цвет левого узла на противоположный
h.right.color = !h.right.color; //меняем цвет правого узла на противоположный
}
private Node moveRedLeft (Node h) //перекрасить в красный цвет дочерний узел слева
{
flipColors (h); //перекрасить узел h и его дочерние узлы
if (isRed (h.right.left)) //если левый узел правого узла h красный, то
{
h.right = rotateRight (h.right); //правый узел — результат правого вращения
h = rotateLeft (h); //узел — результат левого вращения
}
return h; //вернуть узел
}
// Предполагая, что узел h красный и правый узел и левый узел правого узла черные, сделать правый узел h или один из дочерних узлов красным
private Node moveRedRight (Node h) //перекрасить в красный цвет дочерний узел справа
{
flipColors (h); //перекрасить узел h и его дочерние узлы
if (isRed (h.left.left)) //если левый узел левого узла h красный, то
h = rotateRight (h); //узел — результат правого вращения
return h; //вернуть узел
}
private Node balance (Node h) //восстановление красно-черного дерева
{
if (isRed (h.right)) h = rotateLeft (h); //если узел справа красный, то левое вращение
if (isRed (h.left) && isRed (h.left.left)) h = rotateRight (h); //если узел, А слева и левый узел В узла, А красные, то правое вращение
if (isRed (h.left) && isRed (h.right)) flipColors (h); //если оба дочерних узла красные, то перекрасить узлы
h.N = size (h.left) + size (h.right) + 1; //посчитать количество узлов
return h; //вернуть узел
}
public int height () //высота дерева
{
return height (root); //вызов метода с ссылкой на корень дерева
}
private int height (Node x) //метод вычисления высоты дерева
{
if (x == null) //если корень пустой, то
return -1; //вернуть -1
return 1 + Math.max(height (x.left), height (x.right)); //вернуть 1 + (максимальная высота из левого и правого поддеревьев)
}
public Key min () //минимальное значение ключа
{
if (isEmpty ()) //если дерево пустое, вернуть
return null; //null
return min (root).key; //вызвать метод поиска минимального ключа
}
private Node min (Node x) //поиск минимального ключа
{
if (x.left == null) //если узла слева нет, то
return x; //вернуть текущий узел
else //иначе
return min (x.left); //вызываем рекурсивно метод для узла слева
}
public Key max () //максимальное значение ключа
{
if (isEmpty ()) return null; //если дерево пустое, вернуть null
return max (root).key; //вызвать метод поиска максимального ключа
}
private Node max (Node x) //поиск максимального ключа
{
if (x.right == null) return x; //если узла справа нет, то вернуть текущий узел
else return max (x.right); //иначе вызвать рекурсивно этот метод для узла справа
}
public int rank (Key key) //количество ключей, меньших или = заданному
{
return rank (key, root); //вызов метода
}
private int rank (Key key, Node x) //количество ключей, меньших или = заданному, начиная с х
{
if (x == null) return 0; //если узел пустой, вернуть 0
int cmp = key. compareTo (x.key); //сравнение ключа текущего узла и заданного ключа
if (cmp < 0) return rank (key, x. left); //если заданный меньше, то вызываем рекурсивно метод для левого узла
else if (cmp > 0) return 1 + size (x.left) + rank (key, x. right); //иначе если заданный больше, то вызываем рекурсивно метод для правого узла
else return size (x.left); //иначе возвращаем количество
}
public Iterable keys () //все ключи
{
return keys (min (), max ()); //вернуть все ключи
}
public Iterable keys (Key lo, Key hi) //все ключи
{
Queue queue = new LinkedList (); //очередь для добавления ключей в порядке возрастания
keys (root, queue, lo, hi); //добавление ключей в очередь
return queue; //вернуть очередь
}
public void keys (Node x, Queue queue, Key lo, Key hi) //добавление ключей в очередь, начиная с узла х, между минимальным и максимальным
{
if (x == null) return; //если узел пустой, выйти из метода
int cmplo = lo. compareTo (x.key); //сравнение с меньшим
int cmphi = hi. compareTo (x.key); //сравнение с большим
if (cmplo < 0) keys (x.left, queue, lo, hi); //если меньше меньшего, выполнить рекурсивно метод для левого узла
if (cmplo = 0) queue. add (x.key); //если меньше или = меньшему или больше или = большему, то просто добавить в очередь
if (cmphi > 0) keys (x.right, queue, lo, hi); //если больше большего, то выполнить рекурсивно метод для правого узла
}
public int size (Key lo, Key hi) //количество ключей между меньшим и большим ключами
{
if (lo.compareTo (hi) > 0) return 0; //если разница между наименьшим и наибольшим больше 0, то вернуть 0
if (contains (hi)) return rank (hi) — rank (lo) + 1; //если дерево содержит наибольший, то вернуть количество ключей между наибольшим и наименьшим +1
else return rank (hi) — rank (lo); //иначе вернуть количество ключей между наибольшим и наименьшим
}
private boolean isBalanced (Node x, int black) //сбалансированно ли дерево
{
if (x == null) return black == 0; //если текущая узел пустой, вернуть 0 черных узлов
if (!isRed (x)) black++; //если узел черный, пересчитать черные узлы
return isBalanced (x.left, black) && isBalanced (x.right, black); //вернуть, сбалансированно ли дерево справа и слева
}
}
Приложение Д.
Класс main ()
import java.util.Scanner;
public class main.
{.
public static void main (String args[]).
{.
Scanner scan = new Scanner (System.in); //создание объекта для ввода с клавиатуры.
System.out.println («Тестирование хеш-таблицы «);
System.out.println («Введите размер таблицы»);
HashTable ht = new HashTable (scan.nextInt ()); //создание экземпляра таблицы.
char ch; //символ при вводе «n» или «у» .
do //действия при нажатии «y» (да).
{.
System.out.println («Операции хеш-таблицы «);
System.out.println («1. Вставка «);
System.out.println («2. Удаление»);
System.out.println («3. Найти по ключу»);
int choice = scan. nextInt (); //считывание номера операции.
switch (choice) //варианты:
{.
case 1: //при нажатии «1» .
System.out.println («Введите ключ и значение»);
ht.insert (scan.next (), scan. nextInt ()); //считывание ключа и значения.
break; //прерывание действия.
case 2: //при нажатии «2» .
System.out.println («Введите ключ»);
ht.remove (scan.next ()); //удаление по ключу.
break; //прерывание.
case 3: //при нажатии «3» .
System.out.println («Введите ключ»);
System.out.println («Значение искомого ключа = «+ ht. get (scan.next ())); //вывод значения ключа.
break; //прерывание.
default: //при вводе некорректного символа.
System.out.println («Ошибка «);
break; //прерывание.
}.
ht.printHashTable (); //отображение хеш-таблицы.
System.out.println («Хотите продолжить? (Введите y или n) «);
ch = scan. next ().charAt (0); //чтение символа у или n.
}.
while (ch == 'Y'|| ch == 'y'); //условие при выполнении действий с хеш-таблицей.
}.
}.
Класс HashTable
public class HashTable //класс хеш-таблицы.
{.
private int TABLE_SIZE; //размер таблицы для создания объекта HashEntry.
private int size; //размер таблицы.
private HashEntry[] table; //таблица.
private int primeSize; //размер таблицы (для вычисления хеш-функции).
public HashTable (int ts) //конструктор
{.
size = 0;
TABLE_SIZE = ts;
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++).
table[i] = null;
primeSize = getPrime ();
}.
public int size ().
{.
return this.size;
}.
public int getPrime () //получить число, меньшее, чем размер таблицы для вычисления функции myhash2.
{.
for (int i = TABLE_SIZE — 1; i >= 1; i—) //рассматриваем весь размер таблицы.
{.
int fact = 0; //счетчик.
for (int j = 2; j <= (int) Math.sqrt(i); j++) //рассматриваем числа от 2 до корень (i).
if (i % j == 0)//если от деления нет остатка, то.
fact++; //прибавляем 1.
if (fact == 0) //если в счетчике ничего не было,.
return i; //вернуть размер таблицы-1.
}.
return 3; //вернуть 3.
}.
public int get (String key) //получить значение по ключу.
{.
int hash1 = myhash1(key); //вычисление функции myhash1.
int hash2 = myhash2(key); //вычисление функции myhash2.
while (table[hash1] ≠ null) //пока просмотр таблицы не окончится.
{.
if (table[hash1]. key. equals (key)) //если значение ключа равно искомому,.
return table[hash1]. value; //возвратить значение найденного ключа.
hash1 += hash2; //вычисляем хеш-функцию.
hash1%= TABLE_SIZE; //вычисляем хеш-значение.
}.
return -1; //ключ не найден.
}.
public void insert (String key, int value) //добавление в таблицу пары ключ-значение.
{.
if (size == TABLE_SIZE) //если размер таблицы равен уже заданному размеру, то.
{.
System.out.println («Таблица заполнена»);
return;
}.
int hash1 = myhash1(key); //вычисление функции myhash1.
int hash2 = myhash2(key); //вычисление функции myhash2.
while (table[hash1] ≠ null) //пока просмотр таблицы не окончится.
{.
hash1 += hash2; //вычисляем хеш-функцию.
hash1%= TABLE_SIZE; //вычисляем хеш-значение.
}.
table[hash1] = new HashEntry (key, value); //создаем новое значение таблицы.
size++; //увеличиваем размер на 1.
}.
public void remove (String key) //удаление по ключу.
{.
int hash1 = myhash1(key); //вычисление функции myhash1.
int hash2 = myhash2(key); //вычисление функции myhash2.
while (table[hash1] ≠ null && !table[hash1]. key. equals (key)) //пока просмотр таблицы не окончится и значение ключа не равно искомому,.
{.
hash1 += hash2; //вычисляем хеш-функцию.
hash1%= TABLE_SIZE; //вычисляем хеш-значение.
}.
table[hash1] = null; //очищаем значение таблицы.
size—; //уменьшаем размер таблицы на 1.
}.
private int myhash1(String x) //хеш-функция, которая дает хеш-значение для ключа (String).
{.
int hashVal = x. hashCode (); //получение хеш-кода.
hashVal %= TABLE_SIZE; //хеш-значение.
if (hashVal < 0) //если хеш-значение меньше нуля, то.
hashVal += TABLE_SIZE; //прибавим к нему размер таблицы.
return hashVal; //вернуть хеш-значение.
}.
private int myhash2(String x) //хеш-функция для двойного хеширования.
{.
int hashVal = x. hashCode (); //получение хеш-кода.
hashVal %= TABLE_SIZE; //хеш-значение.
if (hashVal < 0) //если хеш-значение меньше нуля, то.
hashVal += TABLE_SIZE; //прибавим к нему размер таблицы.
return primeSize — hashVal % primeSize; //вернуть хеш-значение (размер таблицы — остаток от деления хеш-значения на размер таблицы).
}.
private int hashFunc2 (String key) //хеш-функция умножением.
{.
float f; //индекс в таблице (массиве).
float A=(float) 0.6 180 339 887 499; //любое число в диапазоне 0.1.
int sss=key.length (); //получение длины ключа.
f = sss * A; //умножить ключ на константу А=(sqrt (5)-1)/2.
f = f — (int) f; // взять дробную часть.
return (int) (size*f); // возвратить число в диапазоне 0… size-1.
}.
private int hashFunc3 (String key) //хеш-функция делением с остатком.
{.
int len=key.length (); //получение длины ключа.
int j=len%TABLE_SIZE; //остаток от деления на размер таблицы.
return j; //вернуть значение.
}.
public void printHashTable () //вывод хеш-таблицы.
{.
System.out.println («Хеш-таблица»);
for (int i = 0; i < TABLE_SIZE; i++) //рассматриваем весь размер таблицы.
if (table[i] ≠ null) //если таблица не пуста, то.
System.out.println (table[i]. key +" «+table[i]. value); // вывести ключ и значение ключа.
}.
}.
Класс HashEntry
public class HashEntry //класс для создания таблицы.
{.
String key; //ключ.
int value; //значение ключа.
public HashEntry (String key, int value) //конструктор при создании таблицы.
{.
this.key = key;
this.value = value;
}.
}.