CMPS 2010 - поиск и сортировка массивов

Содержание: [Показать]

Цель этой лабораторной работы - поиск, сортировка и изменение одномерного массива. В этой лабораторной работе рассматриваются гл. 8, и мы можем использовать некоторые функции из лабораторной работы 7.

Напишите свою программу в своем 2010/9 /на Odin. Назовите его lab9.cpp. Вы напишете единую программу, которая выполняет все перечисленные ниже функции.

Основная функция

Создайте целочисленный массив размером 25. Вызовите функцию random () перед циклом do while, чтобы в начале программы ваш массив был заполнен случайными числами.

Создайте меню с помощью цикла do-while и переключателя, аналогичного вашему меню в лабораторной работе 7.

Функция отображения.

Если выбрана опция «0», отобразить текущий массив. Вы можете использовать функцию отображения из лабораторной работы 7.

Прототип функции:void display (int arr [], int size); или void display (int * arr, int size);

1. Уникальные случайные числа

Если выбран вариант «1», заполните массив новым набором чисел и отобразите их. Создайте функцию random (), которая заполняет ваш массив уникальными числами в диапазоне [5, 50]. Повторяющиеся номера не допускаются. (Подсказка: см. Алгоритм линейного поиска в главе 8 и узнайте, как он работает.) Вы можете использовать те же параметры функции, что и случайная функция Лаборатории 7.

Напоминание:это формат функции rand (): rand% (range) + min

Прототип функции:void random (int * arr, int size); или void random (int arr [], int size, int min, int max);

2. Алгоритмы поиска

    Создайте функцию linear_search, которая возвращает позицию числа, которое вы пытаетесь найти. Если число не найдено, функция поиска должна вернуть -1.

Прототип функции:int linear_search (int * arr, int size, int number);

Прототип функции:int binary_search (int * arr, int size, int number);

3. Отсортируйте ваш массив.

    Создайте функцию пузырьковой сортировки, которая сортирует массив в порядке возрастания.

4. Поиск и сортировка фактов

  1. Линейный поиск [ делает | не] требует упорядочивания данных.
  2. Линейный поиск имеет наихудшую временную сложность [ O (n) | O (n ^ 2) | O (журнал п)].
  3. Двоичный поиск [ делает | не] требует упорядочивания данных.
  4. Двоичный поиск имеет наихудшую временную сложность [ O (n) | O (n ^ 2) | O (журнал п)].
  5. [ Линейный | Двоичный поиск] лучше, чем [ Линейный | Двоичный] Искать, когда данные не упорядочены.
  6. [ Линейный | Двоичный поиск] лучше, чем [ Линейный | Двоичный] Поиск, когда данные упорядочены.
  7. Пузырьковая сортировка [ эффективна | неэффективно] для больших массивов.
  8. [ Пузырь | selection] sort перемещает элементы по одному элементу за раз.
  9. [ Пузырь | selection] sort немедленно перемещает элементы в их конечную позицию в массиве.

5. Измените свой массив.(Выберите 2 или более)

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

Примечание.Необязательно создавать регистр «9», который позволяет вам переключаться между линейным или двоичным поиском для случаев «5» - «8», если вы хотите реализовать задачи, указанные ниже, с использованием обоих поисков. Когда выбрана опция «9», ваше меню обновится, и в нем появится надпись «Двоичный поиск для 5-8» или «Линейный поиск для 5-8». Вы можете сделать это, добавив следующие коды в правые части вашей программы:

Заменять

Если выбран вариант «5», отобразите текущий массив, спросите пользователя, какое число они хотят заменить и каким числом заменить его, и отобразите новый массив. Номер, который они хотят заменить, должен существовать в массиве. Кроме того, число, которое они хотят ввести в массив, должно быть уникальным.

Менять

Если выбран вариант «6», отобразить текущий массив, попросить пользователя поменять местами два числа и отобразить новый массив. Введенные числа должны существовать в массиве. Введенные ими числа не могут совпадать.

Вставить и сдвинуть

Если выбрана опция «7», отобразить текущий массив, попросить пользователя ввести число и индекс, в который он будет помещен, и отобразить новый массив. Введенный номер должен быть уникальным. Введенный индекс должен быть действительным индексом. Начиная с индекса, введенного пользователем, элементы в массиве должны сдвинуться на 1 позицию индекса больше, чем их предыдущий индекс. В массиве не будет места для 26-го числа, поэтому элемент, который раньше был в индексе 24, исчезнет.

Удалить и сдвинуть

Если выбрана опция «8», отобразить текущий массив, попросить пользователя удалить число и отобразить новый массив. Номер, который нужно удалить, должен существовать. Начиная с индекса удаленного числа, элементы в массиве должны сдвинуться на 1 позицию индекса меньше, чем их предыдущий индекс. Будет место для нового 25-го числа, поэтому вы должны создать новый элемент в индексе 24. Этот новый номер должен быть уникальным.

6. Четное по возрастанию и нечетное по убыванию

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

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

Поиск и сортировка 2D-массивов

  1. Создайте 2D-массив с размером строки 3 и размером столбца 10.
  2. Создайте функцию, которая заполняет ваш 2D-массив уникальными случайными числами в диапазоне [-15, 15]. Найдите свой 2D-массив. Если сгенерированное случайное число уже существует, сгенерируйте новое случайное число. Если случайное число еще не существует, поместите случайное число в 2D-массив.

Прототип функции:void random2D (int arr2D [r_size] [c_size], int r_size, int c_size);

Прототип функции:void display2D (int arr2D [r_size] [c_size], int r_size, int c_size)

Прототип функции:void bubble2D_asc (int arr2D [r_size] [c_size], int r_size, int c_size)