Реализация и тестирование хэш-таблицы

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

В данной лабораторной работе нужно реализовать алгоритм бинарного поиска (поиска делением пополам).

Алгоритм в качестве входных данных получает массив отсортированных по возрастанию целых чисел int[] и число, которое необходимо найти. В ответ возвращает индекс наденного элемента массива, либо -1, если число отсутствует в массиве.

Стартовый шаблон программы:

using System;

 

namespace ConsoleApplication

{

class Program

{

public static int BinarySearch(int[] array, int value)

{

//код поиска значения value в массиве array

}

 

static void Main(string[] args)

{

TestNegativeNumbers();

TestNonExistentElement();

 

Console.ReadKey();

}

 

private static void TestNegativeNumbers()

{

//Тестирование поиска в отрицательных числах

int[] negativeNumbers = new[] {-5, -4, -3, -2};

if (BinarySearch(negativeNumbers, -3)!= 2)

Console.WriteLine("! Поиск не нашёл число -3 среди чисел {-5, -4, -3, -2}");

else

Console.WriteLine("Поиск среди отрицательных чисел работает корректно");

}

private static void TestNonExistentElement()

{

//Тестирование поиска отсутствующего элемента

int[] negativeNumbers = new[] {-5, -4, -3, -2};

if (BinarySearch(negativeNumbers, -1) >= 0)

Console.WriteLine("! Поиск нашёл число -1 среди чисел {-5, -4, -3, -2}");

else

Console.WriteLine("Поиск отсутствующего элемента вернул корректный результат работает корректно");

}

}

}

В программе нужно реализовать проверки:

1. Поиск одного элемента в массиве из 5 элементов

2. Поиск среди отрицательных чисел (реализован в шаблоне)

3. Поиск отсутствующего в массиве элемента (реализован в шаблоне)

4. Поиск элемента, повторяющегося несколько раз

5. Поиск в пустом массиве (содержащем 0 элементов)

6. Поиск в массиве из 100001 элементов

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

Реализация и тестирование алгоритма быстрой сортировки

В данной лабораторной работе нужно разработать алгоритм быстрой сортировки https://ru.wikipedia.org/wiki/Быстрая_сортировка

Прототип функции:

public static void QuickSort(int[] array)

Размер массива можно получить, обратившись к array.Length.

Для генерации случайных чисел воспользуйтесь классом Random

var rnd = new Random();

 

rnd.Next(); // возвращает случайное число от 0 до int.MaxValue

rnd.Next(0, 5); // возвращает случайное число от 0 до 4 включительно

Нужно реализовать следующие проверки:

1. Сортировка массива из трёх элементов. После сортировки второй элемент больше первого, третий больше второго

2. Сортировка массива из 100 одинаковых числе работает корректно

3. Сортировка массива из 1000 случайных элементов. Проверить что 10 случайных пар элементов массива после сортировки упорядочены (их пары больший тот, чей индекс больше)

4. Сортировка пустого массива работает корректно

5. Сортировка массива из 1 500 000 000 элементов работает корректно (если на вашем компьютере 8+ Гб памяти)

Реализация и тестирование хэш-таблицы

В данной лабораторной работе необходимо реализовать Хэш-таблицу (https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0).

Хэш-таблица – это ассоциативный контейнер, позволяющий быстро находить объекты по т.н. ключу.

Структура данных должна иметь следующую структуру публичных методов:

 

class HashTable

{

/// <summary>

/// Конструктор контейнера

/// </summary>

/// <param name="size">Размер хэ-таблицы</param>

public HashTable(int size)

{

 

}

 

/// <summary>

/// Метод складывающий пару ключь-значение в таблицу

/// </summary>

/// <param name="key"></param>

/// <param name="value"></param>

public void PutPair(object key, object value)

{

 

}

 

/// <summary>

/// Поиск значения по ключу

/// </summary>

/// <param name="key">Ключь</param>

/// <returns>Значение, null если ключ отсутствует</returns>

public object GetValueByKey(object key)

{

 

}

}

На время разработки можете использовать системный контейнер Dictionary<Key,Value>, однако после завершения разработки тестов от него нужно избавиться. Системный контейнер не обязательно получает размер в параметре конструктора: он поддерживает динамическое расширение. Вашей структуре не обязательно поддерживать эту возможность: можно полагаться на то, что в неё не будет добавлено больше чем size элементов.

Тесты:

1. Добавление трёх элементов, поиск трёх элементов

2. Добавление одного и того же ключа дважды с разными значениями сохраняет последнее добавленное значение

3. Добавление 10000 элементов в структуру и поиск одного из них

4. Добавление 10000 элементов в структуру и поиск 1000 недобавленных ключей, поиск которых должен вернуть null

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

В данной лабораторной работе нужно реализовать алгоритм бинарного поиска (поиска делением пополам).

Алгоритм в качестве входных данных получает массив отсортированных по возрастанию целых чисел int[] и число, которое необходимо найти. В ответ возвращает индекс наденного элемента массива, либо -1, если число отсутствует в массиве.

Стартовый шаблон программы:

using System;

 

namespace ConsoleApplication

{

class Program

{

public static int BinarySearch(int[] array, int value)

{

//код поиска значения value в массиве array

}

 

static void Main(string[] args)

{

TestNegativeNumbers();

TestNonExistentElement();

 

Console.ReadKey();

}

 

private static void TestNegativeNumbers()

{

//Тестирование поиска в отрицательных числах

int[] negativeNumbers = new[] {-5, -4, -3, -2};

if (BinarySearch(negativeNumbers, -3)!= 2)

Console.WriteLine("! Поиск не нашёл число -3 среди чисел {-5, -4, -3, -2}");

else

Console.WriteLine("Поиск среди отрицательных чисел работает корректно");

}

private static void TestNonExistentElement()

{

//Тестирование поиска отсутствующего элемента

int[] negativeNumbers = new[] {-5, -4, -3, -2};

if (BinarySearch(negativeNumbers, -1) >= 0)

Console.WriteLine("! Поиск нашёл число -1 среди чисел {-5, -4, -3, -2}");

else

Console.WriteLine("Поиск отсутствующего элемента вернул корректный результат работает корректно");

}

}

}

В программе нужно реализовать проверки:

1. Поиск одного элемента в массиве из 5 элементов

2. Поиск среди отрицательных чисел (реализован в шаблоне)

3. Поиск отсутствующего в массиве элемента (реализован в шаблоне)

4. Поиск элемента, повторяющегося несколько раз

5. Поиск в пустом массиве (содержащем 0 элементов)

6. Поиск в массиве из 100001 элементов

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

Реализация и тестирование алгоритма быстрой сортировки

В данной лабораторной работе нужно разработать алгоритм быстрой сортировки https://ru.wikipedia.org/wiki/Быстрая_сортировка

Прототип функции:

public static void QuickSort(int[] array)

Размер массива можно получить, обратившись к array.Length.

Для генерации случайных чисел воспользуйтесь классом Random

var rnd = new Random();

 

rnd.Next(); // возвращает случайное число от 0 до int.MaxValue

rnd.Next(0, 5); // возвращает случайное число от 0 до 4 включительно

Нужно реализовать следующие проверки:

1. Сортировка массива из трёх элементов. После сортировки второй элемент больше первого, третий больше второго

2. Сортировка массива из 100 одинаковых числе работает корректно

3. Сортировка массива из 1000 случайных элементов. Проверить что 10 случайных пар элементов массива после сортировки упорядочены (их пары больший тот, чей индекс больше)

4. Сортировка пустого массива работает корректно

5. Сортировка массива из 1 500 000 000 элементов работает корректно (если на вашем компьютере 8+ Гб памяти)

Реализация и тестирование хэш-таблицы

В данной лабораторной работе необходимо реализовать Хэш-таблицу (https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0).

Хэш-таблица – это ассоциативный контейнер, позволяющий быстро находить объекты по т.н. ключу.

Структура данных должна иметь следующую структуру публичных методов:

 

class HashTable

{

/// <summary>

/// Конструктор контейнера

/// </summary>

/// <param name="size">Размер хэ-таблицы</param>

public HashTable(int size)

{

 

}

 

/// <summary>

/// Метод складывающий пару ключь-значение в таблицу

/// </summary>

/// <param name="key"></param>

/// <param name="value"></param>

public void PutPair(object key, object value)

{

 

}

 

/// <summary>

/// Поиск значения по ключу

/// </summary>

/// <param name="key">Ключь</param>

/// <returns>Значение, null если ключ отсутствует</returns>

public object GetValueByKey(object key)

{

 

}

}

На время разработки можете использовать системный контейнер Dictionary<Key,Value>, однако после завершения разработки тестов от него нужно избавиться. Системный контейнер не обязательно получает размер в параметре конструктора: он поддерживает динамическое расширение. Вашей структуре не обязательно поддерживать эту возможность: можно полагаться на то, что в неё не будет добавлено больше чем size элементов.

Тесты:

1. Добавление трёх элементов, поиск трёх элементов

2. Добавление одного и того же ключа дважды с разными значениями сохраняет последнее добавленное значение

3. Добавление 10000 элементов в структуру и поиск одного из них

4. Добавление 10000 элементов в структуру и поиск 1000 недобавленных ключей, поиск которых должен вернуть null