- •1.Этапы разработки компьютерной программы.
- •2.Алгоритмы и их свойства.
- •3.Формы существования алгоритмов; Блок-схемы; Примеры записи алгоритма в виде блок схемы.
- •4.Классификация алгоритмических языков.
- •5.Понятие структурного программирования.
- •6.Характеристика алгоритмического языка Паскаль.
- •7.Элементы языка Паскаль (алфавит, индентификаторы, константы, выражения, операции).
- •8.Структура программ, при использовании для разработки программы алгоритмического языка Паскаль.
- •9.Операторы Паскаля.
- •1. Составной и пустой операторы
- •2. Операторы ветвлений
- •3. Операторы повторений
- •10.Ввод и вывод данных в Паскале.
- •11.Операторы Паскаля: составной оператор и пустой оператор.
- •12. Операторы Паскаля: условный оператор.
- •13. Операторы Паскаля: операторы повторений.
- •14. Операторы Паскаля: операторы цикла с предусловием.
- •16. Операторы Паскаля: оператор цикла с постусловием (repeat… until).
- •17.Операторы Паскаля: оператор цикла с параметрами (for …to …do).
- •18. Операторы Паскаля: оператор безусловного перехода, метки. Оператор безусловного перехода goto
- •19.Подпрограммы в Паскале.
- •20.Процедуры в Паскале.
- •21.Функции в Паскале.
- •Описание и вызов процедур и функций
- •22.Типы данных в Паскале: простые типы.
- •23. Типы данных в Паскале: структурированные типы. Массивы.
- •24. Типы данных в Паскале: структурированные типы. Записи.
- •25. Типы данных в Паскале: структурированные типы. Множества.
- •26. Типы данных в Паскале: структурированные типы. Файлы (понятие файла, доступ к файлу, процедуры и функции для работы с файлами).
- •27. Типы данных в Паскале: структурированные типы. Файлы (текстовые, типизированные, нетипизированые).
- •28.Аппарат формальных и фактических параметров при работе с подпрограммами.
- •Назначение подпрограмм.
- •Механизм подпрограмм, их описание и вызов
- •Параметры подпрограмм ]Назначение параметров
- •[Править]Формальные и фактические параметры
- •[Править]Способ передачи параметров в подпрограмму
- •[Править]Виды подпрограмм
- •29.Массивы.
- •30.Сортировки массивов. Прямые методы сортировки.
- •31.Сортировка вставкой.
- •32.Сортировка массивов. Прямые методы сортировки.
- •33.Сортировка обменом.
- •34.Сортировка массивов. Прямые методы сортировки
- •35. Сортировка выбором.
- •36.Двоичный поиск в массиве.
- •37. Поиск данных в массиве по ключу.
- •38.Средства тп для работы с файлами.
- •39.Классификация структур данных в Паскале.
- •40.Данные статической структуры в Паскале.
- •41.Переменные строкового типа.
- •42.Динамические структуры данных в Паскале.
- •43.Динамическая память. Понятия адреса и указателя. Объявление указателей. Динамическая память
- •Адреса и указатели
- •Объявление указателей
- •44.Динамическая память. Выделение и освобождение динамической памяти.
- •45.Процедуры и функции для работы с динамической памятью.
- •46.Связанные динамические данные.
- •47. Связанные динамические данные: очередь.
- •Принципы работы с динамической очередью
- •48. Связанные динамические данные: стек.
- •Описание стека
- •Работа с динамическим стеком
- •49. Связанные динамические данные: списки. Динамические структуры данных
- •Классификация структур данных
- •Данные динамической структуры:
- •Статические и динамические переменные в Паскале
- •Указатели
- •Объявление указателей
- •Выделение и освобождение динамической памяти
- •Присваивание значений указателю
- •Операции с указателями
- •Присваивание значений динамическим переменным
- •Динамические структуры
- •Описание списка
- •Формирование списка
- •Просмотр списка
- •Удаление элемента из списка
- •Динамические объекты сложной структуры
- •50. Связанные динамические данные: деревья.
- •51.Понятие рекурсии, примеры рекурсивных алгоритмов.
34.Сортировка массивов. Прямые методы сортировки
35. Сортировка выбором.
Просматривается массив и находится наименьший элемент. Затем этот элемент меняется местами с первым элементом. На втором шаге отыскивается минимальный элемент в диапазоне от второго до n-го элемента и меняется местами со вторым элементом. Процесс повторяется для всех элементов до (n-1)-го элемента.
36.Двоичный поиск в массиве.
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это значени.
меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 5. На следующем шаге нужный элемент будет найден. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".
function BSearch (item: DataArray; count:integer; key:DataItem):integer; var low, high, mid: integer; found:boolean; begin low:=1; high:=count; found:=false; { не найден } while (low<=high) and (not found) do begin mid:=(low+high) div 2; if key<item[mid] then high:=mid-1 else if key>item[mid] then low:=mid+1 else found:=true; { найден } end; if found then BSearch:=mid else BSearch:=0; { не найден } end; { конец поиска }
37. Поиск данных в массиве по ключу.
38.Средства тп для работы с файлами.
39.Классификация структур данных в Паскале.
Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.
В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет :
1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;
2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
3) множество допустимых операций, которые применимы к объекту описываемого типа.
В последующих главах данного пособия рассматриваются структуры данных и соответствующие им типы данных. При описании базовых (простых) типов и при конструировании сложных типов мы ориентировались в основном на язык PASCAL. Этот язык использовался и во всех иллюстративных примерах. PASCAL был создан Н.Виртом специально для иллюстрирования структур данных и алгоритмов и традиционно используется для этих целей. Читатель знакомый с любым другим процедурным языком программирования общего назначения (C, FORTRAN, ALGOL, PL/1 и т.д.), без труда найдет аналогичные средства в известном ему языке.
Классификация структур данных