Томсккий политехнический университет

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Национальный исследовательский

ТОМСККИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


Институт Кибернетики

230100 «Информатика и вычислительная техника»

Кафедра ОСУ

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ

Пояснительная записка к курсовой работе

Вариант №8

Студент гр. 8В83 ___________________ Д. Н. Лайком

^{(подпись)}

___________________

^(дата)

Руководитель ___________________ О. Б. Фофанов

доцент, канд. техн. наук ^{(подпись)}

___________________

^(дата)

Томск 2010

СОЖЕРЖАНИЕ


Введение

Целью курсовой работы является закрепление материала, изучаемого в предыдущем семестре по дисциплине «Структуры и алгоритмы обработки данных»: программирование реальных заданий с использованием наиболее распространенных в информационных технологиях структур данных и алгоритмов их обработки.

Курсовая работа включает следующие разделы:

1. 
   Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и тд)
   
2. 
   Поиск информации в различных структурах данных с использованием классических алгоритмов поиска в текстовой информации
   
3. 
   Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных
   
4. 
   Реализация структур данных типа дерево и типовые алгоритмы их обработки
   
5. 
   Реализация функций расстановки (хеширование) и различных методов разрешения коллизий
   

Сферой практического применения в курсовой работе является «8. Страховая фирма», все примеры, связанные с практическим применением будут относиться именно к этой сфере деятельности.

1. Моделирование абстрактных типов данных (АТД) для различных реализаций.

Разработать алгоритм и соответствующее приложение, моделирующее вычислительную систему с постоянным шагом по времени (дискретное время) в соответствии с вариантом индивидуального задания с использованием конкретных реализаций АТД стек и очередь. Результат работы программы представить в виде таблицы 1.1. В первом столбце указывается время моделирования 0,1,2,…,N. Во втором – для каждого момента времени указываются имена объектов (очереди – F1,F2,…,FN; стеки - S1,S2,…,SM; процессоры - P1,P2,…,PK), а в третьем – задачи (имя,время), находящиеся в объектах.

8. Система состоит из двух процессоров P1 и P2 и двух очередей F1, F2 и стека S (рис.1.8). В систему могут поступать запросы на выполнение задач двух типов - Т1 и Т2. Задача типа Т1 может выполняться только процессором P1. Задача типа Т2 может выполняться любым процессором. Запрос можно представить записью.

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte; {тип запроса}

end;

Генератор задач

О

Ч

Е

Р

Е

Д

Ь

F2

О

Ч

Е

Р

Е

Д

Ь

F1

Стек

P1

P2

Рис. 1. Структура программы

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F1 не пуста и процессор P1 свободен, то задача из очереди F1 поступает на обработку в процессор P1. Если процессор Р1 обрабатывает задачу типа Т2, а процессор Р2 свободен, то задача из процессора Р1 поступает в процессор Р2, а задача из очереди F1 в процессор Р1, если же процессор Р2 занят, то задача из процессора Р1 помещается в стек.

Если очередь F2 не пуста и процессор P2 свободен, то задача из очереди F2 поступает на обработку в процессор P2. Если процессор Р2 занят, а процессор Р1 свободен и очередь F1 пуста, то задача из очереди F2 поступает в процессор Р1, а задача из стека поступает на обработку в свободный процессор Р2, если F2 пуста, или в свободный процессор Р1, если очередь F1 пуста и задачу нельзя поместить в процессор Р2.
Код программы:

Код главной программыю

import java.util.Stack; /** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 30.10.2010 * Time: 22:31:37 * To change this template use File | Settings | File Templates. */ public class Coursework { public static void main(String args[]) { //Очереди Queue F1 = new Queue(); Queue F2 = new Queue(); //Стек Stack S = new Stack(); //Процессоры Processor P1 = new Processor(); Processor P2 = new Processor(); Writer writer=null; try{ writer = new Writer("D:\\work.txt"); } catch(Exception e){}; //Генератор задач for(int i = 0; i < 100; i++) { Request T = new Request((int)(Math.random()*20) , (int)(Math.random()+1.5)); System.out.println("T.Time = " + T.Time + "\t" + "T.Type = " + T.Type); if(T.Type == 1) { F1.Add(T); System.out.println("Содержание F1 = " + T.Time); } if(T.Type == 2) { F2.Add(T); System.out.println("Содержание F2 = " + T.Time); } } int i=0; while ((F1.Count>0) || (F2.Count>0) || (!P1.isFree()) || (!P2.isFree()) || (!S.empty())) { if ( F1.Count>0) { if (P1.isFree()) { P1.add(F1.SRD()); } else { if ((P1.Data.Type==2)&&P2.isFree;()) { P2.add(P1.Data); P1.add(F1.SRD()); } if ((P1.Data.Type==2)&&(!P2.isFree())) { S.push(P1.Data); P1.add(F1.SRD()); } } } //абзац if ( F2.Count>0) { if (P2.isFree()) { P2.add(F2.SRD()); } else { if ((P1.isFree())&&(F1.Count==0)) { P1.add(F2.SRD()); if (F2.Count==0) { if(!S.isEmpty()) { P2.add((Request)S.pop()); } } if ((F1.Count==0)&&(!P2.isFree())) { if(!S.isEmpty()) { P1.add((Request)S.pop()); } } } } } //Записываем данные в файл try{ Reporter.WriteCounttime(writer, i); Reporter.WriteStack(writer, S); Reporter.WriteQueue(writer, F1); Reporter.WriteQueue(writer, F2); Reporter.WriteProcessors(writer, P1); Reporter.WriteProcessors(writer, P2); Reporter.WriteLine(writer); }catch(Exception e){}; i++; P1.Tact(); P2.Tact(); } } }

Код очереди:

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 30.10.2010 * Time: 23:06:11 * To change this template use File | Settings | File Templates. */ public class Queue { Request requests[] = new Request[10000]; public int Count = 0; public Queue() { Count = 0; } public void Add(Request i) { requests[++Count]=i; } public Request get(int r) { if(Count == 0) { return null; } int i = 0; boolean b = true; while(b != false) { if(i == r) { b = false; } else { i++; } } return requests[i + 1]; } public Request SRD() { if(Count == 0) { return null; } Request r; r = requests[Count]; requests[Count] = null; Count--; return r; } public void Delete(int r) { int i = 0; boolean b = true; while(b != false) { if(i == r) { requests[i] = null; for(int j = (i + 1); j < (requests.length - 1); j++) { requests[j] = requests[j + 1]; } } else { i++; } } } }

Код процессора

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 30.10.2010 * Time: 23:13:33 * To change this template use File | Settings | File Templates. */ public class Processor { public Request Data; public Processor() { Data=null; } public boolean isFree() { if (Data==null) return true; return Data.Time<=0; } public void add(Request a) { Data = a; } public String getInfo() { return Data.GetInformation(); } public void Tact() { if (Data.Time>0) Data.Time--; } }

Код запроса:

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 30.10.2010 * Time: 22:38:35 * To change this template use File | Settings | File Templates. */ public class Request { public int Time; public int Type; public Request(int time , int type) { Time = time; Type = type; } public String GetInformation() { return "Type: "+Integer.toString(Type)+", Time: "+Integer.toString(Time); } }

Код Write_to_file

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 17.12.2010 * Time: 23:56:40 * To change this template use File | Settings | File Templates. */ import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; /* * Класс Write_to_file * Записывает строки в файл */ public class Write_to_file { private String Filename; FileOutputStream FOS; public Write_to_file(String filename) throws FileNotFoundException { Filename=filename; FOS = new FileOutputStream(Filename); } public void finalize() throws Throwable { FOS.close(); } public void AddLine(String s) throws IOException { s+="\r\n"; FOS.write(s.getBytes()); } public void AddLine(int i) throws IOException { String s = Integer.toString(i); s+="\r\n"; FOS.write(s.getBytes()); } }

Код Report:

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 17.12.2010 * Time: 23:57:12 * To change this template use File | Settings | File Templates. */ import java.io.IOException; import java.util.ArrayList; import java.util.Stack; public class Report { //вывод момента времени public static void WriteCounttime(Write_to_file writetofile, int counttime) throws IOException { writetofile.AddLine(counttime); } public static void WriteLine(Write_to_file writetofile) throws IOException{ writetofile.AddLine("-----------------------------------------------------------------"); } //вывод стека public static void WriteStack(Write_to_file writetofile, Stack stack) throws IOException{ writetofile.AddLine("\tStack:"); ArrayList arraylist=new ArrayList(); for (int k=0; k Request inquiry = (Request)stack.pop(); writetofile.AddLine("\t\t"+inquiry.GetInformation()); arraylist.add(inquiry); } for (int k=arraylist.size()-1; k>=0;k--) { Request inquiry = arraylist.get(k); stack.push(inquiry); } } //вывод очереди public static void WriteQueue(Write_to_file writetofile, Queue queue) throws IOException{ writetofile.AddLine("\tQueue:"); ArrayList arraylist=new ArrayList(); while (queue.Count>0) { Request inquiry = (Request)queue.SRD(); writetofile.AddLine("\t\t"+inquiry.GetInformation()); arraylist.add(inquiry); } for (int k=arraylist.size()-1; k>=0;k--) { Request inquiry = (Request)arraylist.get(k); queue.Add(inquiry); } } //вывод процессоров public static void WriteProcessors(Write_to_file writetofile, Processor p) throws IOException{ writetofile.AddLine("\tProcessor:"); writetofile.AddLine("\t\t"+p.getInfo()); } }

Пример вывода программы

Вывод: В результате выполнения данного пункта курсовой работы были приобретены навыки работы с АТД односвязный список, также были приобретены навыки организации процессора. Были приобретены навыки «псевдо распараллеливания» работы программы.

2. Поиск информации в различных структурах данных
Изучение алгоритмов поиска контекста в больших объемах текстовой информации и закрепление навыков в проведении сравнительного анализа алгоритмов.

1. Реализовать алгоритмы поиска:

• 
  Алгоритм Боуэра-Мура
  

2. Построить графики зависимости количества операций сравнения от

количества символов в массиве.

3. Определить временную сложность алгоритма и сравнить с экспериментальными исследованиями

Алгоритм Боуэра-Мура

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 10.12.2010 * Time: 9:08:58 * To change this template use File | Settings | File Templates. */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; /** * * Быстрый алгоритм поиска подстроки в строке. * Преимущества: хорошая скорость работы на длинных строках, содержащих много * различных символов. * Недостатки: замедление скорости работы при наличии большого числа повторяющихся символов и фрагментов строк в образце. * * Скорость работы: * - в лучшем случае О(n/m) * - в среднем О(n) * - в худшем случае О(n*m) */ public class BoyerMoore { private static final int shLen = 256; private static int hash(char c) { return c & 0xFF; } // После каждого вызова функции поиска содержит общее число сравнений. private static int compares = 0; /** * Алгоритм Бойена - Мура реализован в виде статического метода класса, * получающего исходные строки в качестве аргументов и возвращающего * индекс найденной подстроки в качестве результата. * * Если подстрока не найдена - результат работы равен -1. * * @param where - исходная строка, в которой ищут. * @param what - подстрока, которую ищут. * @return - найденный индекс или -1 */ public static int boyerMoore(String where, String what) { compares = 0; int n = where.length(); // Длина исходной строки int m = what.length(); // Длина образца // Массив сдвигов формируется в предположении, что коды символов // находятся в диапазоне от 0 до 255, однако можно хешировать символы, // выбирая меньшую длину массива int[] shifts = new int[shLen]; // Для символов, отсутствующих в образце, сдвиг равен длине образца for (int i = 0; i < shLen; i++) { shifts[i] = m; } // Для символов из образца сдвиг равен расстоянию от // последнего вхождения символа в образец до конца образца for (int i = 0; i < m-1; i++) { shifts[hash(what.charAt(i))] = m-i-1; } for (int i = 0; i <= n-m; ) { // Сравнение начинается с конца образца for (int j = m-1; j>=0; j--) { compares++; if (where.charAt(i+j) == what.charAt(j)) { if (j == 0) return i; } else { break; } } // Сдвиг производится в соответствии с кодом последнего из сравниваемых символов i += shifts[hash(where.charAt(i+m-1))]; } return -1; } /** * Тестовая процедура: запускает алгоритм и выводит результат его работы. * @param args */ public static void main(String[] args)throws IOException { String filename="D:\\BoyerMoore.txt"; String SearchString = "Раскольников"; BufferedReader fileIn = new BufferedReader(new FileReader(filename)); String Value; int Counter=0; long startTime = System.nanoTime(); while((Value = fileIn.readLine()) != null) { Counter++; int offset = boyerMoore(Value, SearchString); if (offset!=-1) { //подстрока найдена System.out.println("Строка "+Counter); startTime = System.nanoTime()-startTime; System.out.println("Time of search = " + startTime + " нс"); break; } } } }

Пример вывода

Строка 11 Time of search = 2462194 нс

Графическое представление результатов

Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Алгоритм основан на трёх идеях:

1. Сканирование слева направо, сравнение справа налево.

Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на n символов символов вправо, и проверка снова начинается с последнего символа.

Определение количества n символов:

Эвристика стоп-символа.

В таблице стоп-символов указывается последняя позиция в needle (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 — соответственно, −1).

Эвристика совпавшего суффикса.
Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Для каждого возможного суффикса S шаблона needle указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S.

Теоретическую оценку сложности алгоритма в общем виде можно описать как:

O(|haystack|+|needle|+|Σ|)

haystack — строка, в которой выполняется поиск

needle — шаблон поиска

Σ — алфавит, на котором проводится сравнение.

3. 
   Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных
   

Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.

Исходные наборы данных – массивы или файлы соответствующего типа (по № варианта).

Проследить динамику роста требуемого для сортировки времени.

Проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.

Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.

Построить соответствующие таблицы и графики сравнительного анализа различных методов сортировки (по времени, размерности и исходной упорядоченности)

Провести исследования:

для выбранных алгоритмов внутренней сортировки (метод Шелла с собственным алгоритмом изменения числа серий и сортировка Хоара с выбором медианы на каждом шаге разделения)

Теоретические сведения:

Алгоритм пузырька - Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

public void Bubble() { ArrayList b = new ArrayList(); for (int i = 0; i < A.Count; i++) b.Add(A[i]); for (int i=0; i for (int j=0; j if ((int)b[i]>(int)b[i+1]) { int u = (int)b[i+1]; b[i+1]=b[i]; b[i]=u; }

Метод простых вставок

Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1], R[2], ..., R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место.
Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. На j-м шаге К[j] сравнивается по очереди с K[j-1], K[j-2], ... ( K[1]<=K[2]<=...<=K[j-1] ) до тех пор, пока выполняется условие K[j] < K[i] ( i = j-1, j-2, ... ) или достигнут левый конец упорядоченной подтаблицы ( i = 1, K[j] < K[1] ). Выполнение условия K[j] >= K[i] означает, что запись R[j] нужно вставить между R[i] и R[i+1]. Тогда записи R[i+1], R[i+2], ..., R[j-1] сдвигаются на одну позицию, и запись R[j] помещается в позицию i+1.

Количество операций сравнения для данного метода вставки равно N(N-1)/4. Максимальное количество перестановок при использовании этого метода примерно равно (N*N)/4.
Метод вставки обычно используется тогда, когда записи вносятся в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушалась. Этот метод эффективен когда записи часично упорядочены, т.е. записи находятся не далеко от своих конечных положений.

public void Insert() { int x; int j; ArrayList b = new ArrayList(); for (int i = 0; i < A.Count; i++) b.Add(A[i]); for (int i = 1; i < b.Count; i++) { x = (int)b[i]; j = i - 1; while ((x < (int)b[j]) && (j > 0)) { b[j + 1] = b[j]; j--; } b[i] = x; } TimeSpan s = DateTime.Now.TimeOfDay - now; textBox2.Text = Convert.ToString(s.Seconds + s.Milliseconds / 1000.0); }

Метод бинарных вставок

Этот метод упоминается Джоном Мочли в 1646г. в первой публикации по машинной сортировке. 

Данный метод является улучшенной версией предыдущего метода простых вставок. Он основывается на том факте, что мы вначале ищем место куда нужно вставить элемент, а затем уже вставляем. Это дает существенный выигрыш по числу сравнений, но число перестановок по прежнему остается большим. 

Поскольку все методы массива перед записью R[j] уже упорядочены, то можно использовать более эффективный метод поиска места куда надо вставить R[j]. В данном случае это алгоритм бинарного поиска. Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т.д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений. 

Общее число сравнений равно приблизительно N*logN, число перестановок попржнему остается квадратично зависимым от N. 

public void BinInsert() { ArrayList b = new ArrayList(); for (int i = 0; i < A.Count; i++) b.Add(A[i]); for (int i = 1; i < b.Count; i++) { if ((int)b[i - 1] > (int)b[i]) { int x = (int)b[i]; int left = 1; int right = i - 1; do { int spred = (left + right) / 2; if ((int)b[spred] < (int)x) { left = spred + 1; } else { right = spred - 1; } } while (left <= right); for (int j = i - 1; j >= left; j--) b[j + 1] = b[j]; b[left] = x; } } TimeSpan s = DateTime.Now.TimeOfDay - now; textBox3.Text = Convert.ToString(s.Seconds + s.Milliseconds / 1000.0); }

Метод Шелла

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами —сортировка вставками либо сортировка простыми обменами с предварительными «грубыми» проходами.

При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками или простыми обменами). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше), но она не предпочтительна, так как всё равно остается медленной.

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• 
  отсутствие потребности в памяти под стек
  
• 
  отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла
  

public void shellSort() { ArrayList b = new ArrayList(); for (int i = 0; i < A.Count; i++) b.Add(A[i]); int step = b.Count /8; while (step > 0) { int i, j; for (i = step; i < b.Count; i++) { int value = (int)b[i]; for (j = i - step; (j >= 0) && ((int)b[j] > value); j -= step) b[j + step] = b[j]; b[j + step] = value; } step /= 2; }

Сортировка Хоара

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

static private void Quicksort(ArrayList ar, int left, int right) { if (left == right) return; int i = left + 1; int j = right; int pivot = (int)ar[left]; while (i < j) { if ((int)ar[i] <= pivot) i++; else if ((int)ar[j] > pivot) j--; else { int m = (int)ar[i]; ar[i] = ar[j]; ar[j] = m; } } if ((int)ar[j] <= pivot) { int m = (int)ar[left]; ar[left] = ar[right]; ar[right] = m; Quicksort(ar, left, right - 1); } else { Quicksort(ar, left, i - 1); Quicksort(ar, i, right); } }

Обработка результатов

Прямой порядок:

Метод	Размерность массива
	500	1000	3000	5000	8000	10000	30000
Метод пузырька	0,006	0,021	0,183	0,516	1,302	2,049	18,481
Метод простых вставок	0,000	0,000	0,000	0,000	0,000	0,000	0,002
Метод бинарных вставок	0,000	0,001	0,001	0,001	0,000	0,000	0,001
Метод Шелла	0,000	0,000	0,001	0,002	0,003	0,006	0,022
Метод Хоара	0,003	0,009	0,008	0,022	0,058	0,078	0,096

Обратный порядок:

Метод	Размерность массива
	500	1000	3000	5000	8000	10000	30000
Метод пузырька	0,006	0,020	0,186	0,516	1,300	2,047	18,338
Метод простых вставок	0,003	0,015	0,129	0,340	0,878	1,405	12,363
Метод бинарных вставок	0,003	0,011	0,090	0,263	0,639	0,984	8,870
Метод Шелла	0,000	0,000	0,001	0,004	0,009	0,011	0,027
Метод Хоара	0,000	0,001	0,007	0,018	0,046	0,068	0,085

Случайный порядок:

Метод	Размерность массива
	500	1000	3000	5000	8000	10000	30000
Метод пузырька	0,005	0,021	0,191	0,183	1,312	2,056	18,645
Метод простых вставок	0,000	0,001	0,001	0,001	0,005	0,003	0,010
Метод бинарных вставок	0,001	0,005	0,046	0,047	0,324	0,513	4,880
Метод Шелла	0,001	0,001	0,002	0,002	0,008	0,014	0,045
Метод Хоара	0,010	0,010	0,010	0,020	0,060	0,080	0,240

Реализация структур данных типа дерево и типовые алгоритмы их обработки

Реализовать методы создания сильноветвящихся деревьев реализующих информацию соответствующей предметной области, а также методы поиска, удаления и добавления узлов в них.

Реализация:

/** * Created by IntelliJ IDEA. * User: LaykomDN * Date: 29.12.2010 * Time: 19:59:58 * To change this template use File | Settings | File Templates. */ import java.util.Random; public class Courswork_4{ public static void main(String[] args){ Insurance_Company Company = new Insurance_Company("Insurance_Company РосГосСтрах"); Random ran = new Random(); for (int i = 100;i <= 500; i++) { Insurance r = new Insurance("Ins" , Integer.toString(i), ran.nextInt()%4+1, ran.nextInt()%3+1, true, ran.nextInt()%10+1, ran.nextInt()%10); Company.Add(r); } //создаем сервисы Insurance s1 = new Insurance("service", "autoinsurance", -1, -1, true, 0.5, 3); Insurance s2 = new Insurance("service", "Home insurance", -1, -1, true, 60*24, 3); Insurance s3 = new Insurance("service", "Stuff", -1, -1, true, 60*24, 1); Insurance s4 = new Insurance("service", "I", -1, -1, true, 60*24, 1); Insurance s5 = new Insurance("service", "Business", -1, -1, true, 60*3, 1); Insurance s6 = new Insurance("service", "Hands of programmer", -1, -1, true, 60*24, 30); Company.Add(s1); Company.Add(s2); Company.Add(s3); Company.Add(s4); Company.Add(s5); Company.Add(s6);}} import java.util.ArrayList; public class Insurance_Company { public String Name; public ArrayList list; public Insurance_Company(String Name) { this.Name=Name; list = new ArrayList(); } public Insurance Find(String name) { for (int i=0;i Insurance insurance =(Insurance) list.get(i); if (insurance.Name.equals(name)) return insurance; } for (int i=0;i Insurance insurance =(Insurance) list.get(i); Insurance resitem= insurance.Find(name); if (resitem!=null) return resitem; } return null; } private Boolean isExists(String str) { for (int i=0; i Insurance c = (Insurance) list.get(i); if (c.Name.equals(str)) return true; } return false; } public void Add(Insurance insurance) { if (insurance.Type=="Ins") { String n = insurance.Name.substring(0, 1); if (!isExists(n)) { Insurance d = new Insurance("node", n); list.add(d); System.out.println("Добавлена страховка"); } Insurance d = Find(n); d.List.add(insurance); System.out.println("Добавлена страховка"); }else if (insurance.Type=="service") { if (!isExists("service")) { Insurance d = new Insurance("node", "service"); list.add(d); System.out.println("Добавлен сервис"); } Insurance d = Find("service"); d.List.add(insurance); System.out.println("Добавлен сервис"); } } public void deleteItem(String name) { Insurance insurance = Find(name); deleteItem(insurance); } //удаление узла public void deleteItem(Insurance insurance) { for (int i=0; i Insurance it = (Insurance) list.get(i); if (it.Name== insurance.Name) list.remove(i); } for (int i=0;i Insurance it=(Insurance) list.get(i); it.deleteItem(insurance.Name); } }

Реализация функций расстановки (хэширование) и различных методов разрешения коллизий.

Теоритические сведения

Хеширование (англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хэш-функциями или функциями свёртки, а их результаты называют хэшем, хэш-кодом или дайджестом сообщения (англ. message digest).

Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, крипто стойкость и т. п.). Выбор той или иной хэш-функции определяется спецификой решаемой задачи.

Хэш-функция 1: Hash_1

public static int Hash_1(String str) { int d2=1; byte b[] = str.getBytes(); for (int i=0; i { d2*=b[i]+i; d2+=i; } return (d2)%Hash.MaxCount; }

Хэш-функция 2: Hash_2

Данный алгоритм работает следующим образом: по коду символа находится его соответствие в таблице Table, далее происходит дизъюнкция хэша с бинарный сдвиг влево на 32-rotate с хэшем с бинарным сдвигом вправо на rotate. Затем хэш умножается на некоторое число, значение которого меняется.

static char sTable[] ={ 0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9, 0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28, 0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53, 0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2, 0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8, 0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90, 0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76, 0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d, 0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18, 0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4, 0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40, 0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5, 0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2, 0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8, 0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac, 0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46 }; public static int Hash_2(String str){ int hash = 0; int rotate = 2; int seed = 0x1A4E41; byte b[] = str.getBytes(); for (int i = 0; i hash += sTable[ b[i]& 255]; hash = (hash << (32 - rotate) ) | (hash >> rotate); hash = (hash + i ) * seed; } return (Math.abs((hash + str.length()) * seed))%HashTable.MaxCount; }

Хэш-функция 3: Hash_3

Суть алгоритма в том, что на каждом шаге прибавляем к хэшу Ord текущего символа входной строки, а затем умножаем хэш на некоторое число, значение которого меняется.

static int Hash_3 (String str) { int hash = 0; int i = 0; int b = 378551; int a = 63689; byte b1[] = str.getBytes(); for (i = 0; i < str.length(); i++) { hash = hash * a + b1[i] * b1[i]; a = a * b+i; } return (Math.abs(hash))%HashTable.MaxCount; }

Метод разрешения коллизий – Квадратичное опробование.

При использовании квадратичного опробования, что шаг перебора элементов не линейно зависит от номера попытки найти свободный элемент

a = h(key2) + c*i + d*i ²

Благодаря нелинейности такой адресации уменьшается число проб при большом числе ключей-синонимов.

Обработка результатов:

Графики распределения количества коллизий на массиве из 1000 элементов.

Хорошая хэш-функция та, множество значений которой равномерно распределено по множеству значений аргумента. По полученным графикам видно, что хэш-функции Hash_2 и Hash_3 примерно дают примерно одинаковое распределение коллизий. Хэш-функция Hash_1 является самой неудачной из предложенных т.к. имеет наибольшую плотность коллизий в каждой ячейке