Добавлен: 28.03.2023
Просмотров: 174
Скачиваний: 2
ВВЕДЕНИЕ
Тема данной курсовой работы: «Поиск слова в упорядоченном массиве».
При решении многих задач часто возникает необходимость установить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в массиве фамилий фамилия Петров. Задачи такого типа называются поиском в массиве.
Массивы – это набор элементов, имеющих одинаковый тип данных, или, по-другому, массивы – это набор элементов, имеющих одинаковое имя и один и тот же тип данных. Индекс массива начинается с 0 до n-1.
Актуальность данной темы обуславливается тем, что текстовые массивы данных встречаются повсюду. Это и электронные книги, и страницы сайтов, и документы и многое другое. Найти необходимое слово – частая и распространенная задача. Рассмотрение принципов поиска слова позволит понять данную задачу и способы её дальнейшей автоматизации. Массивы очень широко используются при разработке различного рода приложений. Массивы являются распространенным и полезным способом сохранения многих различных частей связанных данных. Массивы полезны при создании отсортированных и неотсортированных списков данных, при сохранении таблиц данных и для выполнения многих других задач. С понятием «массив» приходится работать и при решении научно-технических и экономических задач, связанных с обработкой совокупностей большого количества значений.
Цель работы: изучить принципы поиска слова в массивах.
Для выполнения цели необходимо выполнить ряд задач:
- рассмотреть понятие массива;
- рассмотреть понятие поиска слова;
- рассмотреть примеры использования.
Глава 1. Рассмотрение понятия «массив»
Переменная позволяет хранить одно значение за раз. Например, нам необходимо сохранить номер броска ста студентов. Для этой задачи необходимо объявить 100 переменных, а затем присвоить значения каждой из них. Но если студентов 10000 или больше, объявлять столько переменных плохое решение. В такой ситуации, лучший способ – это массивы.
Массив – это коллекция из одного или нескольких значений одного типа. Каждое значение называется элементом массива. Элементы массива имеют одно и то же имя переменной, но каждый элемент имеет свой собственный уникальный номер индекса (также известный как индекс). Массив может быть любого типа, например: int, float, и charт.д. Если массив имеет тип , intто это элементы должны быть типа intтолько.
Массивы и их представление приведены ниже на рисунке 1.
Рисунок 1 – Представление массива
Индекс массива: расположение элемента в массиве имеет индекс, который идентифицирует элемент. Индекс массива начинается с 0.
Элемент массива: элементы, хранящиеся в массиве, называются элементом. Элементы могут быть доступны через его индекс.
Длина массива: длина массива определяется на основе количества элементов, которые массив может хранить. В приведенном выше примере длина массива равна 6, что означает, что он может хранить 6 элементов.
Когда объявляется массив размера и типа, компилятор выделяет достаточно памяти для хранения всех элементов данных.
Переменные стандартного типа можно изобразить отдельными маленькими ячейками. То же самое относится и к переменным перечисляемого и интервального типов – рисунок 2.
Рисунок 2 – Графическое представление переменной
В данных ячейках могут содержаться любые значения из диапазона, определяемого их типами.
Базовый тип массива – это тип элементов, из которых составлен массив (в каждом массиве все компоненты одного типа) – рисунок 3. Элементы можно обрабатывать так же, как переменные базового типа. Однако такое использование элементов массива в качестве обычных переменных не дает никакой выгоды.
Рисунок 3 – Графическое представление массива
1.1 Одномерные массивы
Предположим, что программа работает с большим количеством однотипных данных. Например, около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. 100 переменных в программе и для каждой переменной написать одно и тоже выражение вычисления значения – очень неэффективно.
Есть более простое решение. Это использование такой структуры (типа) данных как массив. Массив представляет собой последовательность ячеек памяти, в которых хранятся однотипные данные. При этом существует всего одно имя переменной связанной с массивом, а обращение к конкретной ячейке происходит по ее индексу (номеру) в массиве.
Индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив. Порядковый номер элемента массива называется индексом этого элемента.
Все элементы определенного массива имеют один и тот же тип. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой – из чисел типа real.
Массив можно создать несколькими способами – рисунок 3.
Рисунок 3 – Пример создания массива на языке программирования Pascal
Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента.
Простой массив является одномерным. Он представляет собой линейную структуру – рисунок 4.
Рисунок 4 – Пример обращения к массиву на языке программирования Pascal
Общие правила объявления одномерного массива:
- переменная массива должна быть объявлена перед использованием в программе;
- объявление должно иметь тип данных (int, float, char, double и т. Д.), Имя переменной и индекс;
- индекс представляет размер массива. Если размер объявлен как 10, программисты могут хранить 10 элементов;
- индекс массива всегда начинается с 0. Например, если переменная массива объявлена как s [10], то она колеблется от 0 до 9;
- каждый элемент массива хранится в отдельной ячейке памяти.
1.2 Двумерные массивы
Одномерный массив можно представить как линейную структуру, в которой элементы следуют друг за другом. Однако бывают более сложные структуры данных. Например, двумерные массивы, которые можно описать как таблицу, в ячейках которой располагаются значения. Для обращения к данным массива указывается номера их строк и столбцов. Часто табличные массивы называют матрицами.
Одномерный массив представляет информацию в линейном порядке, одномерным списком. Однако данные, связанные с определенными системами (цифровое изображение, настольная игра и т. д.), «живут» в двух измерениях. Чтобы визуализировать эти данные, нужна многомерная структура данных, то есть многомерный массив. Двумерный массив – это не что иное, как массив массивов.
В качестве массива можно представить ужин. Можно иметь одномерный список всего, что едите: салат, помидоры, стейк, картофельное пюре, торт, мороженое.
А можно получить двумерный список из трех блюд, каждый из которых содержит две вещи, которые едите: (салат, помидоры) и (стейк, пюре) и (торт, мороженое).
В первом случае одномерный массив выглядит так:
int [] myArray = {0,1,2,3};
А двумерный массив выглядит так:
int [] [] myArray = {{0,1,2,3}, {3,2,1,0}, {3,5,6,1}, {3,8,3,4}};
Лучше рассматривать двумерный массив как матрицу. Матрица может рассматриваться как сетка чисел, расположенных в строках и столбцах.
Обычно двумерные массивы на языке программирования Pascal описываются так – рисунок 5, однако можно их описывать и по-другому – рисунок 6:
Рисунок 5 – Описание массива 1
Рисунок 6 – Описание массива 2
При этом описание может быть в разделе type и тогда создается новый тип, который можно использовать при объявлении переменных. Или массив может быть описан непосредственно в разделе переменных. m и n – это константы, их можно опустить и вставить конкретные значения, но лучше так не делать. Обычно подразумевают, что в интервале от 1 до m определяется количество строк, а в интервале от 1 до n – количество столбцов массива.
Для обращения к элементу двухмерного массива необходимо указать имя массива и в квадратных скобках через запятую – значения двух индексов (первый указывает номер строки, а второй – номер столбца), на пересечение которых стоит элемент (например, a[i,2]:=6). В языке программирования Pascal допустимо разделение индексов с помощью квадратных скобок (например, a[i][5]:= 7).
Если описывается двумерный массив как типизированная константа, то при задании значений его элементов он рассматривается как массив массивов. При этом в общих круглых скобках через запятую перечисляются заключенные в круглые скобки значения элементов строк (каждая строка в своих скобках) – рисунок 7.
Рисунок 7 -Константа
Размерность массива (т.е. количество содержащихся в нем значений) определяется произведением количества строк на количество столбцов. В примере в массив помещается 15 значений – рисунок 8.
Когда пользователь вводит очередное число, то процедура read считывает его и помещает в ячейку с текущими индексами i и j. Когда i равна единице, значение j меняется пять раз, и, значит, заполняется первая строка таблицы. Когда i равна двум, значение j снова меняется пять раз и заполняется вторая строка таблицы. Аналогично заполняется третья строка таблицы. Внутренний цикл for в общей сложности совершает 15 итераций, внешний только 3.
Как пользователь вводит значения – не важно. Он может их разделять либо пробелом, либо переходом на новую строку.
Вывод значений двумерного массива организован в виде таблицы. Выводятся 3 строки по 5 чисел в каждой. Внутри строк числа разделяются пробелом.
В программе следует использовать константы. В случае чего их значения можно поменять всего лишь в одном месте.
При описании открытого массива необходимо указать тип элементов, из которых он состоит, но не указывать границы индексов. Таким образом можно сформировать «безразмерный» массив. Размер такого массива можнт задаваться и изменяться при выполнении программы – динамическое распределение памяти. Переменные этих массивов - указатели на динамически выделяемую область памяти. Это означает, что в этих переменных будут содержаться адреса начала массива, а не сам массив. Пример программы представлен на Рисунке 9.
Обычно открытые массивы используются для передачи в подпрограмму массивов переменных размеров. Это позволяет с помощью одной и той же подпрограммы обрабатывать массивы произвольной длины.
Двумерный массив также можно использовать для хранения объектов, что особенно удобно при программировании эскизов, в которых используются некие «сетки» или «доски».
Например, можно написать программу, использующую двумерный массив для рисования изображения в градациях серого.
Рисунок 8 – Пример работы с массивом
Основные операции над массивами:
- траверс – печать всех элементов массива один за другим;
- вставка – добавляет элемент по указанному индексу;
- удаление – удаляет элемент по указанному индексу;
- поиск – поиск элемента в массиве по заданному индексу или значению;
- обновить – обновляет элемент по указанному индексу.
Рисунок 9 – Пример программы с массивом на языке Pascal
В следующей главе будут рассмотрены методы поиска в массивах.
Глава 2. Рассмотрение понятия «поиск» в массиве
Переменная содержит один элемент данных. Может возникнуть ситуация, когда для хранения похожих и связанных данных требуется много переменных. В этой ситуации использование массива может упростить программу, храня все связанные данные под одним именем. Это означает, что программа может быть написана для поиска по массиву данных гораздо быстрее, чем необходимость писать новую строку кода для каждой переменной. Это уменьшает сложность и длину программы, что облегчает поиск и устранение ошибок.