- •Иркутский государственный университет путей сообщения кафедра “информатика” конспект лекций по дисциплине “программирование на алгоритмическом языке высокого уровня”
- •Иркутск
- •Программирование и алгоритмические языки в историческом аспекте
- •Введение в Паскаль
- •Алфавит Паскаля
- •Служебные (ключевые) слова
- •Константы
- •Запись чисел
- •Переменные
- •Типы данных
- •Стандартные функции
- •Выражения
- •Выражения целого типа
- •Выражения вещественного типа
- •3,61·109 X – 526,237 3.61e9 * X – 526.237 * Sqrt(0.2*y) Выражения логического типа
- •Операторы присваивания
- •Программа и этапы ее разработки. Структура программы
- •Var X, s : Word;
- •Комментарии
- •Ввод данных
- •Вывод данных
- •Бесформатный способ вывода
- •±D.DdddddddddE±dd
- •Форматный способ вывода
- •Структуры данных
- •Массивы
- •Var a : Array [1..2,1..3] Of Integer;
- •Error 201: Range check error
- •Var a : tMatrix;
- •Var Doska : Array [‘a’..’h’,1..8] Of Char;
- •Var Roma : Array [1..787] Of Word;
- •Var Roma : Array [-754..33] Of Word;
- •Var Ozenka : Array [1..2,1..3] Of Word;
- •Var Ozenka : Array [Fam, Predm] Of 2..5;
- •Var a: Array [1..3, 1..4, 1..5] Of Integer;
- •Var I, j: Byte;
- •Алгоритм и его свойства
- •Схемы алгоритмов
- •Базовые структуры
- •Цепочка
- •Ветвления
- •Альтернатива
- •If (условие)
- •Вариант 2 – с использованием операции конъюнкция
- •Часто встречающиея ошибки программирования:
- •Var X, y, s_left, s_right, alfa, sin_alfa, segment : Real;
- •Переключатель
- •Var Month: 1..12;
- •Бесконечные циклы
- •Циклы с предусловием
- •Var I, s : Word;
- •Var I, s, n : Word;
- •Программа
- •Var n, min, max, s, count: Word;
- •Часто встречающиея ошибки программирования:
- •Циклы с постусловием
- •Var I, s : Word;
- •Var I, s, n : Word;
- •Программа
- •Var n,min,max,s,count: Word;
- •Var k : Word;
- •X, y, s : Real;
- •Var Month: 1..12;
- •Var n, s : Word;
- •Var I, s : Word;
- •Примеры:
- •Var I, j, k : Word;
- •Var I, i_max, vector_max : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, s : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, m : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, s, count : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, min, max, i_min, i_max : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, i_otr, i_pol : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, posl : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, j, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, k : Integer;
- •Var I, j, k, posl : Integer;
- •Var I, j, k, m : Integer;
- •Var I, j, k, i_max, j_min : Word;
- •Var I, j, t : Integer;
- •V : Array [1..K] Of Integer;
- •Var I, j, m, t : Integer;
- •V : Array [1..K] Of Integer;
- •Var I, j, b, c : Word;
- •Часто встречающиея ошибки программирования:
- •Множества
- •Var r : tSymb;
- •Основные операции со множествами
- •Типизированные файлы
- •Var f_int : tFile_Int;
- •Var n : Integer;
- •Функции для работы с типизированными файлами
- •И процедуры:
- •Var n : Integer;
- •Текстовые файлы
- •Var f_text : tFile_text;
- •Программа:
- •Var stud_1 : tStudent;
- •Var student : tKadr;
- •Var coord : tCoord;
- •Ключ : ();
- •Подпрограммы
- •Подпрограммы-функции
- •Var p : Real;
- •Var s : Real;
- •Var I: Word;
- •Var a, b, c : Integer;
- •Var a, b, c : Integer;
- •Var a, b : Integer;
- •Var a, b, c: Integer;
- •Рекурсия
- •5 * 4 * Factorial(3)
- •5 * 4 * 3 * Factorial(2)
- •5 * 4 * 3 * 2 * Factorial(1)
- •Var k: Integer; Func_2
- •Var temp : Integer;
- •Особенности рекурсии:
- •Процедуры
- •Var I: Word;
- •Var I, i_min, i_max: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j: Word;
- •Программные модули
- •Структура модуля
- •Interface
- •Implementation
- •Var f: Text;
- •Var p: Real;
- •Var temp: Real;
- •Компиляция модулей
- •Взаимное использование модулей
- •Ссылки и динамические переменные
- •Var a, b: tPntint;
- •X, y: tPntchar;
- •Динамические структуры данных
- •Связные списки
- •Inf: Integer;
- •Var head, q : tPoint;
- •Inf: Integer;
- •Var head, q : tPoint;
- •Добавление нового элемента в список
- •Var head, q, r: tPoint;
- •Inf: Integer;
- •Var head, q, r : tPoint;
- •Удаление элемента из списка
- •Inf: Integer;
- •Var head, q, r : tPoint;
- •Сортированные списки
- •Var head, q, r, V: tPoint;
- •Inf: Integer;
- •Var head, q, r, V : tPoint;
- •Бинарные деревья
- •Var root, q, V: tRebro;
- •Интерфейс:
- •Var root, q, V : tRebro;
- •Поиск заданного узла в дереве
- •Var root, q, V : tRebro;
- •Удаление узла из дерева
- •Var root, q, V, r : tRebro;
- •Объектно-ориентированное программирование
- •Var X, y, dx, dy: Word;
- •Var x0, y0, dx, dy: Word;
- •Var x0, y0, dx, dy, radius: Word;
- •Var x0, y0, dx, dy, radius: Word;
- •Основы алгебры логики
- •Логическая функция не (отрицание)
- •Логическая функция и (конъюнкция – логическое умножение)
- •Логическая функция или (дизъюнкция – логическое сложение)
- •Логическое следование (импликация)
- •Логическое совпадение(эквивалентность)
- •Закон исключенного третьего
- •Закон противоречия
- •Закон двойного отрицания
- •Закон контрапозиции
- •Закон расширенной контрапозиции
- •Закон перестановки посылок
- •Закон силлогизма
- •Закон де Моргана
- •Системы счисления
- •Двоичная система счисления
- •Восьмеричная система счисления
- •Шестнадцатиричная система счисления
- •Арифметические операции в двоичной системе счисления
- •1111 11 11 - Переносы
- •Арифметические операции в восьмеричной системе счисления
- •Арифметические операции в 16-ричной системе счисления
- •1. Ошибки при компиляции
- •2. Ошибки времени выполнения а) Ошибки системы ms-dos
- •Б)Ошибки ввода-вывода
- •В)Критические ошибки
- •Г)Фатальные ошибки
Динамические структуры данных
Основное преимущество, предоставляемое ссылками и динамическими переменными, состоит в том, что они дают возможность создавать объекты со сложной, изменяющейся в процессе работы программы структурой – динамические структуры данных– связные списки, стеки, очереди, деревья.
Динамические структуры не имеют постоянного размера, поэтому память под отдельные элементы таких структур выделяется в момент, когда они создаются в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры нет необходимости, занимаемая им память освобождается.
Поскольку элементы динамических структур располагаются в памяти не по порядку и даже не в одной области, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента, как при работе с массивами. Связь между элементами динамической структуры устанавливается через указатели, содержащие адреса элементов в памяти. Такое представление данных в памяти называется связным.
Таким образом, кроме информационных полей, ради которых создается структура и которые являются видимыми для пользователя, динамические структуры содержат поля для связи с другими элементами, видимые только для программиста-разработчика. С помощью связного представления данных обеспечивается высокая изменчивость структуры.
Динамические структуры обладают следующими преимуществами:
размер структуры ограничивается только объемом памяти компьютера,
при изменении логической последовательности элементов структуры (добавлении или удалении элемента, изменении порядка следования элементов) требуется только коррекция указателей.
С другой стороны, такие структуры обладают рядом недостатков:
работа с указателями требует высокой квалификации программиста,
на указатели расходуется дополнительная память
дополнительный расход времени на доступ к элементам связной структуры.
Связные списки
Связный список– это динамическая структура, имеющая вид цепочки связанных между собой элементов, причем каждый предыдущий элемент в ней хранит информацию о месте (адресе ячейки памяти), где расположен следующий за ним элемент.
Такая ситуация напоминает очередь к врачу в приемной: каждый пациент знает, за кем он занимал очередь, хотя все посетители могут сидеть в каком угодно порядке на свободных стульях.
Связанный список состоит из элементов типа запись, причем каждый элемент имеет два поля –информационноеиссылочное. В информационном поле (полях) хранитсязначениеэлемента списка – числа, строки и т.д., а в ссылочном –ссылка(адрес ячейки памяти) на следующий за ним элемент:
Type TPoint = ^TElement;
TElement = Record
Inf: Integer;
Next: TPoint;
End;
Var head, q : tPoint;
Определен новый тип TPoint– ссылка на объекты типаTElement, причемTElement– это запись, имеющая два поля:Inf- целого типа иNext- типаTPoint. Здесь мы впервые сталкиваемся с ситуацией, когда в правой части определения для типаTPointвстречается имя типаTElement, который определен позже. В Паскале разрешается такоерекурсивноеопределение типов, если один из них являетсяссылочным.
Таким образом, переменные head иqтипаTPointявляются записями, одно из полей которых содержит ссылку на адрес ячейки памяти, отводимой для переменной этого же типа. Значит, каждый элемент создаваемого списка будет содержать ссылку на такой же элемент списка. Признаком того, что данный элемент являетсяпоследнимв списке, является равенство поля ссылки этого элемента значениюNil–пустойссылки. На каждый элемент списка, кроме первого, имеется ссылка от предыдущего элемента. Поэтому при формировании любого списка необходимо вводить переменную, значение которой является ссылка на текущийпервыйэлемент списка –головусписка. Такой переменной у нас являетсяhead. Если список еще не сформирован, то есть в нем нет ни одного элемента (пустойсписок), то значение этой переменной должно равнятьсяNil.
Построим список из трех элементов, содержащих числа 5, -3, -12 (причем 5 - голова, а -12 - хвост). Пусть в ссылочном поле переменнойheadвсегда хранится адрес текущего первого элемента списка. Переменнуюqбудем использовать для выделения с помощью оператораNew(q)места в памяти для размещения очередного элемента списка.
В начале построения списка ни одного элемента в нем нет – список пуст, поэтому нет и его начала:
New(head);
Head := Nil;
Список начнем строить споследнегоэлемента, равного-12: определим для него место в памяти и информационную часть:
New(q);
q^.Inf := -12;
Сейчас этот элемент является первым (и пока единственным), поэтому одновременно и последним элементом списка. Поэтому ссылочная часть его должна быть равнаhead, имеющему значениеNil– за этим элементом других элементов нет:
q^.Next := head;
апеременнаяheadдолжна уже содержать ссылку на этот первый созданный элемент списка:
head := q;
Таким образом, переменная headсейчас хранит адрес ячейки памяти, созданной операциейNew(q),в которой записан первый элемент списка-12.
Вставим перед ним элемент, равный -3: определим для него место в памяти и информационную часть:
New(q);
q^.Inf := -3;
При этом в памяти сохраняется уже созданный элемент списка, ссылка на который хранится вhead:
Вновь созданный элемент будет первым элементом списка, поэтому ссылку headна последний (старый первый) элемент поместим в его ссылочную часть:
q^.Next := head;
ав освободившуюся переменнуюheadпоместим ссылку на него – новый первый элемент списка (эта переменная всегда должна указывать на голову списка):
head := q;
Наконец, создадим первый (в порядке следования) элемент списка, равный 5:
New(q);
q^.Inf := 5;
Поместим в его ссылочную часть ссылку на ранее созданный (следующий за ним в списке) элемент, равный -3, а в переменнуюhead– ссылку на него самого:
q^.Next := head;
head := q;
В результате создан связный список, в каждом элементе которого хранится адрес (ссылка) следующего за ним элемента, а ссылка на первый элемент списка находится в переменных headиq.
Ссылочное поле (в нашем случае .Next) само является указателем, поэтому, например, значением переменнойhead^.Next^.Infбудет являться информационное поле второго по списку элемента, т.е.-3, а значением переменнойhead^.Next^.Next- ссылочное поле этого элемента, т.е. ссылка на третий элемент списка. Так, наращивая переменнуюhead, можно добраться до конца списка.
Таким образом, рассмотренный способ построения списка “с хвоста” заключается в создании пустого списка и повторяющемся выполнении ряда однотипных шагов, добавляющих в начало списка новые элементы.
Например, программа построения списка, элементами которого являются квадраты целых чисел от 1доn, имеет вид (воспользуемся имеющимся описанием переменных):
New(head);
head := Nil;
For i:=n DownTo 1 Do
Begin
New(q);
q^.Inf := i*i;
q^.Next := head;
head := q;
End;
После создания этого списка значением переменной headбудет являться ссылка на его первый элемент. Прочитаем созданный список – выведем на экран информационные поля его элементов, начиная с первого:
q := head; указатель – на первый элемент списка
While (q<>Nil) Do пока ссылка не пустая (последний элемент)
Begin
Write(q^.Inf:6); выводим значение очередного элемента
q := q^.Next; делаем шаг по списку – берем следующий элемент
End;
В данном случае при выполнении цикла Whileзначением указателяqбудут являться поочередно ссылки на первый, второй, третий и т.д. элементы списка, и, наконец,Nil. Это происходит потому, что после присваивания
q := q^.Next;
значением переменной qбудет или ссылка на следующий элемент списка, хранящаяся в ссылочной части этого текущего элемента, илиNil, если достигнут конец списка.
Пользуясь этим способом перехода от предыдущего элемента к последующему, можно просмотреть или весь список от начала до конца, или его часть.
Пример: ввести с клавиатуры последовательность целых чисел (конец ввода – число0), сформировать из них список, определить количество введенных чисел, вывести список на экран.
Интерфейс:
Первое число: -12
Следующее число: -3
Следующее число: 5
Следующее число: 0
Введено чисел: 3
Введенные числа:
5 -3 -12
Программа:
Program Spisok;
Uses CRT;
Type TPoint = ^TElement;
TElement = Record