Алгоритмы поиска. Линейный поиск. Двоичный поиск. Алгоритмы поиска
 Скачать 244.42 Kb.
|
|
- количество слов заранее неизвестно; - количество слов определяется только в конце работы. Решение – список. Алгоритм: - создать список; - если слова в файле закончились, то стоп. - прочитать слово и искать его в списке; - если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; - перейти к шагу 2. При работе со списками необходимо уметь создать новый узел, добавить узел в начало списка, в конец списка, после заданного узла, до заданного узла, искать нужный узел в списке, удалить узел. Функция CreateNode – создает узел.
В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Очередь – это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка. Двусторонняя очередь – это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так в конце списка. Добавление элемента в очереди возможно лишь в конец очереди, выборка – только из начала очереди, при этом выбранный элемент из очереди удаляется. Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие. Очередь – информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления – другой, называемый головой. Типовые операции над очередями: -добавление элемента в очередь (помещение в хвост); -удаление элемента из очереди (удаление из головы); - проверка, пуста ли очередь; - очистка очереди. Очередь называют структурой типа FIFO (First In – First Out) – первым пришел, первым ушел. На рисунке изображена очередь из 3-ех элементов. Добавление элемента -> в б а ->удаление элемента конец начало Если максимальный размер очереди заранее известен, его можно реализовать в программе в виде массива. Если максимальный размер заранее неизвестен или требуется сделать его динамическим, для реализации используют список.
Дерево – иерархическая структура данных, хранящая набор элементов. Каждый элемент имеет значение и может указывать на ноль или более других элементов. На каждый элемент указывает только один другой элемент. Единственным исключением является корень дерева, на который не указывает ни один элемент. Входящие в дерево элементы называются его вершинами. Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учета порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными ребрами или упорядоченным деревом. Упорядоченные деревья являются наиболее распространенными среди древовидных структур. Двоичное дерево поиска – одно из разновидностей упорядоченного дерева. Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определенными их позициями в массиве. Операции:
Применение: -управление иерархией данных; - упрощение поиска информации; - оптимизация программ; -в качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов и др. Дерево – структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. С помощью деревьев изображаются отношения подчиненности (иерархия, старший-младший, родитель – ребенок). Предок узла х – это узел, из которого существует путь по стрелкам в узел х. Потомок узле х – это узел, в который существует путь по стрелкам из узла х. Высота дерева – это наибольшее расстояние от корня до листа. Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей. Применение двоичных деревьев: -поиск данных в специально построенных деревьях (БД) -сортировка данных -вычисление арифметических выражений -кодирование Ключ – это характеристика узла, по которой выполняется поиск. Обход дерева – это перечисление всех узлов в определенном порядке.
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг) Направленный граф – это граф, в котором все дуги имеют направления. Цепь – это последовательность ребер, соединяющих две вершины. Цикл – это цепь из какой-то вершины в нее саму. Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина). Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Легко найти примеры графов в самых разнообразных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы. Граф называется: -связным, если для любых вершин u и v есть путь из u и в v -сильно связным или ориентировано связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь -деревом, если он связный и не содержит простых циклов - полным, если любые его две вершины соединены ребром -взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра и др. Способы представления графа в информатике: -Матрица смежности – таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот). -Список ребер – это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами – номерами вершин этого ребра. Список ребер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности. 8.Использование массивов и указателей для моделирования сложных структур данных. Массив – это упорядоченный набор данных, для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа. Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными, с двумя – двумерными и т.д. Одномерный массив нестрого соответствует вектору в математике, двумерный – матрице. Чаще всего применяются массивы с одним или двумя индексами, реже – с тремя, еще большее количество индексов встречается крайне редко. Динамическим называется массив, размер которого может меняться во время исполнения программы. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объемы данных, а регулировать размер массива в соответствии с реально необходимыми объемами. Обычные, не динамические массивы называют еще статическими. Элементы массива располагаются в последовательных ячейках памяти, обозначаются именем массива и индексом. Каждое из значений, составляющих массив, называется элементом массива. Количество индексов элементов массива определяет размерность массива. По этому признаку массивы делятся на одномерные (линейные), двумерные, трехмерные и тд. В си можно определить массив любого типа. Int mas[3] описан массив из 3 целых чисел. Нумерация в массивах начинается с 0-го элемента. Массив можно инициализировать при описании. В этом случае нет необходимости указывать его размер int mas[]={23,25,8} Создан массив из 3-элементов: Mas[0]=23; Mas[1]=25; Mas[2]=81; Указатель – это переменная, значением которой является адрес другой переменной. Для описания указателей используется операция косвенной адресации *. Например, указатель целого типа uk описывается так: int *uk. Унарная операция &, примененная к некоторой переменной, показывает, что нам нужен адрес этой переменной, а не ее текущее значение. Если переменная uk объявлена как указатель, то оператор присваивания uk=&x означает: «взять адрес переменной х и присвоить его значение переменной-указателю uk». Унарная операция * , примененная к указателю, обеспечивает доступ к содержимому ячейки памяти, на которую ссылается указатель. Например, *uk можно описать словами как «то, что содержится по адресу, на который указывает uk». Указатели могут использоваться в выражениях. Если, например, переменная uk указывает на целое х, то *uk может во всех случаях использоваться вместо х; так, *uk+1 увеличивает х на единицу, а *uk=0 равносильно х=0. Если uk – некоторый указатель, то uk++ увеличивает его значение и он теперь указывает на следующий, соседний адресуемый объект.
Текстовый процессор – вид прикладной компьютерной программы, предназначенной для производства (включая набор, редактирование, форматирование, иногда печать) любого вида печатной информации. Иногда текстовый процессор называют текстовым редактором второго рода. Текстовыми процессорами в 1970-е – 1980-е годы называли предназначенные для набора и печати текстов машины индивидуального и офисного использования, состоящие из клавиатуры, встроенного компьютера для простейшего редактирования текста, а также электрического печатного устройства. Позднее наименование «текстовый процессор» стало использоваться для компьютерных программ, предназначенных для аналогичного использования. Текстовые процессоры, в отличие от текстовых редакторов, имеют больше возможностей для форматирования текста, внедрения в него графики, формул, таблиц и других объектов. Поэтому они могут быть использованы не только для набора текстов, но и для создания различного рода документов, в том числе официальных. Наиболее известным примером текстового процессора является Microsoft Word. Современные текстовые процессоры предоставляют пользователю широкие возможности по подготовке документов. Это и функции редактирования, допускающие возможность любого изменения, вставки, замены, копирования и перемещения фрагментов в рамках одного документа и между различными документами, контекстового поиска, функции форматирования символов, абзацев, страниц, разделов документа, верстки, проверки грамматики и орфографии, использования списков, таблиц, рисунков, графиков и диаграмм. Значительное сокращение времени подготовки документов обеспечивают такие средства автоматизации набора текста, как автотекст, автозамена, использование форм, шаблонов и мастеров типовых документов. Наличие внешней памяти компьютер обеспечивает удобное длительное хранение подготовленных ранее документов, быстрый доступ к ним в любое время. Существенно упрощают процедуру ввода данных сканеры и голосовые устройства. Существующие системы распознавания текстов, принимаемых со сканера, включают функцию экспорта документа в текстовые редакторы. Широкий спектр печатающих устройств в сочетании с функциями подготовки документа к печати, предварительного просмотра, обеспечивают получение высококачественных черно-белых и цветных копий. При работе в локальных и глобальных компьютерных сетях пользователь имеет возможность обмениваться документами с удаленными пользователями, отправляя документы по электронной почте непосредственно из текстового редактора, готовить данные в формате Web-страниц. Текстовые данные являются наиболее распространенным видом данных при работе с компьютером. Для работы с тексом используют два основных класса программного обеспечения: -текстовые редакторы; -текстовые процессоры. Текстовые редакторы служат в основном для ввода и редактирования (правки) текста. Они не имеют средств для оформления внешнего вида документа и применяются в тех случаях, когда эти средства являются лишними и отвлекают от творческой работы или не нужны (например, при подготовке документов, пересылаемых по электронной почте). При использовании текстового редактора создается текстовый файл, который содержит только коды символов, которые были введены. Это означает, что все текстовые редакторы работают с текстом одинаково. Текст, введенный в одном редакторе, можно редактировать другим редактором, не испытывая при этом никаких затруднений. Текстовые процессоры используют в тех случаях, когда имеет значение не только содержание текста, но и его внешний вид (например, при подготовке официальных документов). Текстовый процессор позволяет управлять оформлением текста при его выдаче на экран и принтер. Документ, созданный текстовым процессором, содержит не только текст, но и информацию о том, как он должен быть оформлен. Эта информация заключена в невидимых кодах, которые не печатаются ни на экране, ни на бумаге, но влияют на то, как происходит печать. Разные текстовые процессоры используют для оформления текста разные коды (говорят – документы имеют разные форматы). Поэтому перенос форматированных текстовых документов из одного текстового процессора в другой не всегда возможен и не всегда прост. В тех случаях, когда такой перенос сделать не удается, переносят только текст, без кодов форматирования (говорят – перенос с потеряй форматирования), после чего вновь оформляют текст в новом текстовом процессоре. Что можно делать с помощью текстового процессора? -набирать текст; -сохранять текст на диск и загружать текст с диска; -редактировать (изменять); -выбирать шрифт и его размер; -выводить текст на печать, желательно с предварительным просмотром страниц; -осуществлять поиск и поиск с заменой; -возможность загружать большие документы; -возможность одновременного просмотра нескольких документов (многооконный режим); - наличие буфера для переноса фрагмента документа внутри окна и между окнами; - форматировать документ( задавать поля, задавать абзацы и отступы, задавать выравнивание текста (по левому, по правому краям, по центру, по ширине), задавать межстрочный интервал, задавать нумерацию страниц, задавать размер страниц, располагать текст в нескольких колонках); -вставлять в текст графические изображения, таблицы, формулы и т.д. - осуществлять проверку орфографии. 11.Общая характеристика и функциональные возможности табличных процессоров. Современные табличные процессоры имеют очень широкие функциональные и вспомогательные возможности, обеспечивающие удобную и эффективную работу пользователя. Перечислим основные возможности, общие для всех систем этого класса. 1. Контекстная подсказка. Вызывается из контекстного меню или нажатием соответствующей кнопки в пиктографическом меню. 1. Справочная система. Организована в виде гипертекста и позволяет легко и быстро осуществлять поиск нужной темы. 3. Многовариантность выполнения операций. Практически все операции могут быть выполнены одним из трех—четырех способов, из которых пользователь выбирает наиболее удобный. 4. Контекстное меню. Разворачивается по щелчку кнопки (обычно правой) «мыши» на выбранном объекте. Речь идет, например, о месте таблицы, где в данный момент собирается работать пользователь. Наиболее часто используемые функции обработки, доступные в данной ситуации, собраны в контекстном меню. 5. Пиктографическое меню. Командам, с которыми работают чаще всего, соответствуют пиктограммы, расположенные под строкой меню. Они образуют пиктографическое меню. После щелчка клавишей манипулятора «мышь» на пиктограмме выполняется связанная с ней команда. Пиктографические меню могут быть составлены индивидуально. 6. Рабочие группы, или рабочие папки. Документы удобно объединять в рабочие папки и рассматривать их как одно целое, если речь идет о копировании, загрузке, изменении или других процедурах. В нижней части электронной таблицы расположен алфавитный указатель (регистр), который обеспечивает доступ к рабочим листам. Пользователь имеет возможность задавать название листам в папке (вместо алфавитного указателя), что делает наглядным содержимое регистра, а значит облегчает поиск и переход от документа к документу. 7. Средства для оформления и модификации экрана и таблиц. Внешний вид рабочего окна и прочих элементов экранного интерфейса может быть определен в соответствии с требованиями пользователя, благодаря чему работа становится максимально удобной. Среди таких возможностей — разбиение экрана на несколько окон, фиксация заголовков строк и столбцов и т.д. 8. Средства оформления и вывода на печать таблиц. Для удобства пользователя предусмотрены все функции, обеспечивающие печать таблиц, такие как выбор размера страницы, разбиение на страницы, установка размера полей страниц, оформление колонтитулов, а также предварительный просмотр получившейся страницы. 9. Средства оформления рабочих листов. Современные табличные процессоры предоставляют широкие возможности по форматированию таблиц, такие как выбор шрифта и стиля, выравнивание данных внутри клетки, выбор цвета фона клетки и шрифта, изменение высоты строк и ширины колонок, черчение рамок различного вида, задание формата данных внутри клетки (например: числовой, текстовый, финансовый, дата и т.д.), а также автоформатирование — в систему уже встроены различные способы оформления таблиц, и пользователь имеет возможность выбрать наиболее подходящий формат из уже имеющихся. 10. Шаблоны. Табличные процессоры, как и текстовые, позволяют создавать шаблоны рабочих листов, которые применяются для формирования бланков писем и факсов, различных калькуляций. Если шаблон предназначен для других пользователей, то можно разрешить заполнять такие бланки, но запретить изменение их формы. 11. Связывание данных. Абсолютная и относительная адресации являются характерной чертой всех табличных процессоров, в современных системах они позволяют работать одновременно с несколькими таблицами, которые могут быть тем или иным образом связаны друг с другом. Например, трехмерные связи, обеспечивающие работу с несколькими листами, идущими подряд; консолидация рабочих листов, с помощью которой обрабатываются суммы и средние значения и ведется статистическая обработка при использовании данных разных областей одного рабочего листа, нескольких рабочих листов и даже нескольких рабочих книг; благодаря связанной консолидации удается не только получить результат вычислений по нескольким таблицам, но и динамически его пересчитывать в зависимости от изменения исходных значений. Регистрируйтесь! Одна из самых популярных онлайн игр в интернете! Карос Величайшая онлайн игра, присоединяйтесь! Карос онлайн Новая бесплатная онлайн игра! 12. Вычисления. Для удобства вычисления в табличных процессорах имеются встроенные функции, а именно: математические, статистические, финансовые, функции даты и времени, логические и другие. Мастер функций позволяет выбрать нужную функцию и, подставив значения, получить результат. 13. Деловая графика. Трудно представить себе современный табличный процессор без возможности построения различного типа двумерных, трехмерных и смешанных диаграмм. Насчитывается более 20 различных типов и подтипов диаграмм, которые можно построить в современной системе данного класса. Также многообразны и доступны способы оформления диаграмм, например, вставка и оформление легенд и меток данных, оформление осей (возможность вставки линий сеток) и другие. Помимо этого, современные системы работы с электронными таблицами снабжены такими мощными средствами построения и анализа деловой графики, как вставка планок погрешностей, возможность построения тренда и выбор функции линии тренда. 14. Выполнение табличными процессорами функций баз данных. Эта функция обеспечивает заполнение таблиц аналогично заполнению базы данных (т.е. через экранную форму), защиту данных, сортировку по ключу или по нескольким ключам, обработку запросов к базе данных, создание сводных таблиц. Кроме того, все современные программы работы с электронными таблицами включают в себя средства обработки внешних баз данных, которые позволяют работать с файлами, созданными, например, в формате dBase или PARADOX. 15. Моделирование. Подбор параметров и моделирование — одни из самых важных возможностей табличных процессоров. С помощью простых приемов удается находить оптимальные решения для многих задач. Методы оптимизации варьируются от простого подбора (при этом значения ячеек-параметров изменяются так, чтобы число в целевой ячейке стало равным заданному) до метода линейной оптимизации со многими переменными и ограничениями. При моделировании иногда желательно сохранять промежуточные результаты и варианты поиска решения. Для этого создаются сценарии, которые представляют собой описание решаемой задачи. 16. Макропрограммирование. Для автоматизации выполнения часто повторяемых действий удобно воспользоваться встроенным языком программирования макрокоманд. Разделяют макрокоманды и макрофункции. Благодаря макрокомандам упрощается работа с табличным процессором и расширяется список его собственных команд. При помощи макрофункций определяют собственные формулы и функции и таким образом расширяют набор функций, предоставляемый системой. В простейшем случае макрос — это записанная последовательность нажатия клавиш, перемещений и щелчков кнопками «мыши». Такая последовательность подается «воспроизведению», как магнитофонная запись. Ее можно обработать и каким-то образом изменить, например организовать цикл, переход, подпрограмму. Современные программы обработки электронных таблиц позволяют пользователю создавать и использовать диалоговые окна, которые по своему внешнему виду и удобству работы не отличаются от существующих в системе, что делает диалог с макрокомандой максимально удобным. |