Файл: Энциклопедия учителя информатики. Выпуск 5 Е. В. Андреева, И. Н. Фалина Окончание. Начало см в 142007 10. Операторы языка программирования Оператор.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 711
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
алгоритмические конструкции, т.е. алгоритм, записанный таким образом, может не соответствовать требованиям структурного программирования. Наконец, обозримыми являются блок-схемы только для небольших алгоритмов. При составлении блок-схем надо внимательно следить за структурностью алгоритма, т.е. блок-схема произвольного алгоритма должна быть композицией схем основных алгоритмических конструкций, в противном случае программирование подобного алгоритма будет затруднено.ПрограммыПри записи алгоритма как в словесной форме, так и в виде блок-схем допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы, в частности, компьютеры. Поэтому алгоритм, предназначенный для того или иного исполнителя, должен быть записан на “понятном” ему языке, c использованием только СКИ (см. статью “Исполнитель алгоритмов”). И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык для компьютера-исполнителя принято называть языком программирования (см. статью “Языки программирования”), а запись алгоритма на этом языке — программой для компьютера.Программами являются и запись нормальных алгоритмов Маркова, и машина Тьюринга для решения конкретной задачи (см. статью “Теория алгоритмов”).Методические рекомендацииНа разных ступенях школьного образования используются различные способы записи алгоритмов. В начальной школе это в первую очередь словесная форма записи, реже — блок-схемы. При работе с учебными исполнителями, например, входящими в комплект “Роботландии”, алгоритмы записываются на языке соответствующего исполнителя, что является очень важным шагом к осмыслению понятия формализации алгоритмов.В базовом курсе информатики алгоритмы записывают с помощью блок-схем, на школьном алгоритмическом языке или языке программирования высокого уровня. В школьном курсе информатики наиболее часто используют такие языки, как Pascal и Basic.В профильной школе возможен переход к профессиональным версиям языков программирования, например, Delphi или Visual Basic. Однако неоправданным является построение сквозного курса информатики, в котором акцент делается на изучение именно языков программирования, например, сначала изучается Basic, потом Pascal, а потом С. Если на освоение программирования можно выделить достаточное число часов, то правильнее отвести их на изучение различных алгоритмов, в том числе выходящих за рамки базового курса информатики, а также на знакомство с современными технологиями и парадигмами программирования (см. “
Разработка программ”, “Объектно-ориентированное программирование”).15. Структуры данных
Понятие структуры данныхНеобходимым условием построения алгоритма является формализация данных, т.е. приведение информации к некоторой информационной модели (см. “Информационные модели”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных.Абстрактная структура данных описывает признаки и свойства объекта, взаимосвязь между элементами объекта, а также возможные операции над данным объектом или классом объектов.Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) объектами. Такими объектами — базовыми абстрактными структурами данных, используемыми в информатике, являются:· целые числа;· вещественные числа;· символы;· логические значения.Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.К таким абстрактным структурам данных относятся:· векторы (конечные массивы);· таблицы (матрицы), а в общем случае — многомерные массивы;· графы;· динамические структуры:o последовательности символов, чисел;o строки;o списки;o очереди;o стеки;o деревья;o графы.Удачный выбор структуры данных часто является залогом создания эффективного алгоритма и программы, его реализующей: используя аналогию структур данных и реальных объектов, можно находить эффективные решения задач.Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов, поддерживаемых данным языком программирования (см. “
Операторы языка программирования”). Для компьютерного представления абстрактных структур используются структуры данных,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных: одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур, размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.СпискиЛинейный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элементов в произвольное место списка и удаление любого элемента. Линейный список однозначно задается указателем на начало списка. Типовыми операциями над списками являются: обход списка, поиск заданного элемента, вставка элемента сразу после или перед определенным элементом, удаление заданного элемента, объединение двух списков в один, разбиение одного списка на два и более списков и т.п.В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент. Таким образом, все элементы списка упорядочены. Однако обработка линейного односвязного списка не всегда удобна, т.к. отсутствует возможность движения в противоположную сторону — от конца списка к началу. В линейном списке можно обойти все элементы, только двигаясь последовательно от текущего элемента к следующему, начиная с первого, прямой доступ к i-му по счету элементу невозможен.Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство — они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.Кольцевые списки
— такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов!Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре — удаление элемента из списка с сохранением его кольцевой структуры.Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.Стек — частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента). Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуруданных стек. Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:i — номер анализируемого символа;n — количество символов в выражении.1. i = 0.2. i = i + 1.3. Если i
n, то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.4. Если i-й символ отличен от символов скобок, то переход на п. (2).5. Если i-й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).6. Если i-й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “
Разработка программ”, “Объектно-ориентированное программирование”).15. Структуры данных
Понятие структуры данныхНеобходимым условием построения алгоритма является формализация данных, т.е. приведение информации к некоторой информационной модели (см. “Информационные модели”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных.Абстрактная структура данных описывает признаки и свойства объекта, взаимосвязь между элементами объекта, а также возможные операции над данным объектом или классом объектов.Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) объектами. Такими объектами — базовыми абстрактными структурами данных, используемыми в информатике, являются:· целые числа;· вещественные числа;· символы;· логические значения.Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.К таким абстрактным структурам данных относятся:· векторы (конечные массивы);· таблицы (матрицы), а в общем случае — многомерные массивы;· графы;· динамические структуры:o последовательности символов, чисел;o строки;o списки;o очереди;o стеки;o деревья;o графы.Удачный выбор структуры данных часто является залогом создания эффективного алгоритма и программы, его реализующей: используя аналогию структур данных и реальных объектов, можно находить эффективные решения задач.Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов, поддерживаемых данным языком программирования (см. “
Операторы языка программирования”). Для компьютерного представления абстрактных структур используются структуры данных,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных: одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур, размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.СпискиЛинейный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элементов в произвольное место списка и удаление любого элемента. Линейный список однозначно задается указателем на начало списка. Типовыми операциями над списками являются: обход списка, поиск заданного элемента, вставка элемента сразу после или перед определенным элементом, удаление заданного элемента, объединение двух списков в один, разбиение одного списка на два и более списков и т.п.В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент. Таким образом, все элементы списка упорядочены. Однако обработка линейного односвязного списка не всегда удобна, т.к. отсутствует возможность движения в противоположную сторону — от конца списка к началу. В линейном списке можно обойти все элементы, только двигаясь последовательно от текущего элемента к следующему, начиная с первого, прямой доступ к i-му по счету элементу невозможен.Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство — они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.Кольцевые списки
— такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов!Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре — удаление элемента из списка с сохранением его кольцевой структуры.Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.Стек — частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента). Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуруданных стек. Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:i — номер анализируемого символа;n — количество символов в выражении.1. i = 0.2. i = i + 1.3. Если i
n, то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.4. Если i-й символ отличен от символов скобок, то переход на п. (2).5. Если i-й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).6. Если i-й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “