Типы и структуры данных

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 28.10.2017
Размер файла 430,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

return x; //возвращаем текущий узел

}

private Node rotateLeft(Node h) //левое вращение

{

Node x = h.right; //текущему узлу присваиваем правый узел узла h

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<Key> keys() //все ключи

{

return keys(min(), max()); //вернуть все ключи

}

public Iterable<Key> keys(Key lo, Key hi) //все ключи

{

Queue<Key> queue = new LinkedList <Key>(); //очередь для добавления ключей в порядке возрастания

keys(root, queue, lo, hi); //добавление ключей в очередь

return queue; //вернуть очередь

}

public void keys(Node x, Queue<Key> 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 && cmphi >= 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("Тестирование хеш-таблицы\n\n");

System.out.println("Введите размер таблицы");

HashTable ht = new HashTable(scan.nextInt()); //создание экземпляра таблицы

char ch; //символ при вводе "n" или "у"

do //действия при нажатии "y" (да)

{

System.out.println("\nОперации хеш-таблицы\n");

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("Ошибка \n ");

break; //прерывание

}

ht.printHashTable(); //отображение хеш-таблицы

System.out.println("\nХотите продолжить? (Введите y или n)\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.6180339887499; //любое число в диапазоне 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("\nХеш-таблица");

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;

}

}

Размещено на Allbest.ru

...

Подобные документы

  • Сущность языка программирования, идентификатора, структуры данных. Хранение информации, алгоритмы их обработки и особенности запоминающих устройств. Классификация структур данных и алгоритмов. Операции над структурами данных и технология программирования.

    контрольная работа [19,6 K], добавлен 11.12.2011

  • Изучение применяемых в программировании и информатике структур данных, их спецификации и реализации, алгоритмов обработки данных и анализ этих алгоритмов. Программа определения среднего значения для увеличивающегося количества чисел заданного типа.

    контрольная работа [16,0 K], добавлен 19.03.2015

  • Формы представляемой информации. Основные типы используемой модели данных. Уровни информационных процессов. Поиск информации и поиск данных. Сетевое хранилище данных. Проблемы разработки и сопровождения хранилищ данных. Технологии обработки данных.

    лекция [15,5 K], добавлен 19.08.2013

  • Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.

    курсовая работа [459,0 K], добавлен 09.08.2012

  • Анализ характеристик объекта компьютеризации. Разработка структур данных, алгоритмов и программного обеспечения системы управления базой данных. Особенности синтеза структур данных. Разработка алгоритмов системы и оценка результатов тестирования.

    курсовая работа [37,0 K], добавлен 07.12.2010

  • Определение понятия структур данных. Рассмотрение информации и ее представления в памяти. Особенности непозиционных и позиционных систем счисления. Классификация структур данных, операции над ними. Структурность данных и технология программирования.

    презентация [359,3 K], добавлен 20.05.2015

  • Исследование существующих методов организации динамических структур данных. Методы реализации мультисписковых структур используя особенности языка C++. Физическая структура данных для сохранения в файл. Разработка алгоритмов и реализация основных функций.

    курсовая работа [504,1 K], добавлен 25.01.2015

  • Проблемы с организацией данных. Определение и классификация динамических структур данных. Линейные односвязные, двухсвязные, кольцевые списки. Очередь, стеки. Описание основных типов данных и функции для работы с ними. Листинг программы, пример ее работы.

    контрольная работа [290,6 K], добавлен 17.07.2012

  • Разработка программного комплекса, позволяющего проиллюстрировать работу с иерархическими структурами данных. Способы изображения древовидной структуры. Двоичное (бинарное) дерево поиска. Описание алгоритмов, которые используются в программном комплексе.

    курсовая работа [747,2 K], добавлен 09.06.2013

  • Сущность потоков информации, циркулирующих в мире. Особенности создания и система управления базами данных. Общая характеристика правовых информационных структур. Методы и формы распространения баз данных по законодательству в интернете и на CD дисках.

    реферат [33,7 K], добавлен 24.12.2008

  • Основные принципы концепции типа данных в языках программирования. Разновидности структур данных. Дискретные и непрерывные скалярные типы. Файл, последовательность, множество. Линейный список. Сложность алгоритмов. Построение рекурсивных подпрограмм.

    презентация [2,5 M], добавлен 14.10.2013

  • Особенности строковых типов данных и их обработка. Записи как совокупность поименованных компонентов различных типов, основные принципы работы с ними. Массивы - элементы и массивы структур. Понятие и свойства объединений. Файлы и работа с ними в языке СИ.

    презентация [73,1 K], добавлен 09.12.2013

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

    презентация [57,8 K], добавлен 14.10.2013

  • Концепции хранилищ данных для анализа и их составляющие: интеграции и согласования данных из различных источников, разделения наборов данных для систем обработки транзакций и поддержки принятия решений. Архитектура баз для хранилищ и витрины данных.

    реферат [1,3 M], добавлен 25.03.2013

  • Что такое базы данных, визуализация информации базы. Структура и свойства простейшей базы данных. Характеристика определений, типов данных, безопасность, специфика формирования баз данных. Подходы к проектированию технического задания. Работа с таблицами.

    презентация [4,3 M], добавлен 12.11.2010

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

    отчет по практике [1,3 M], добавлен 28.12.2008

  • Рассмотрение общей характеристики данных. Исследование особенностей и назначения линейных, табличных и иерархических структур данных, анализ процесса их упорядочения. Рассмотрение основных режимов обработки данных. Описание алгоритма решения задачи.

    реферат [27,4 K], добавлен 20.04.2019

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

    дипломная работа [2,2 M], добавлен 24.06.2012

  • Алгоритмы обработки массивов данных. Система управления базами данных. Реляционная модель данных. Представление информации в виде таблицы. Система управления базами данных реляционного типа. Графический многооконный интерфейс.

    контрольная работа [2,8 M], добавлен 07.01.2007

  • Типы изображений (черно-белые, полутоновые, цветные) и их форматы. Устройства, создающие цифровые изображения, и их параметры. Применение и характеристики методов сжатия изображений. Поиск по содержимому в базах данных изображений. Структуры баз данных.

    презентация [360,4 K], добавлен 11.10.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.