ПРОГРАММА И УЧЕБНЫЕ МАТЕРИАЛЫ ЭЛЕКТИВНОГО КУРСА по ИНФОРМАТИКЕ для учащихся 10-11 классов «Построение структур данных с применением динамических переменных и указателей»
Пояснительная записка....................................................................................................................................................... 1
Тематическое планирование.......................................................................................................................................... 2
Текст пособия............................................................................................................................................................................... 2
Определение типов данных в Turbo-Pascal......................................................................................................... 2
Применение динамических переменных и указателей к построению структур данных 12
Задачи............................................................................................................................................................................................... 28
Пояснительная записка
Структуры данных, наряду с алгоритмами, являются главными составляющими компьютерных программ. Большое значение имеет оптимальное конструирование структуры данных при реализации компьютерной модели решаемой задачи. В курсе школьной информатики, как правило, рассматриваются статические данные, однако в таких распространенных языках программирования как C и Pascal имеются средства для создания динамических конструкций. Освоение способов работы с динамическими данными позволяет строить и обрабатывать достаточно сложные компьютерные модели, которые при этом, являются наглядными и интуитивно понятными.
Основной задачей курса «Динамические данные и их применение к решению задач программирования» является расширение и углубление знаний о видах данных и способах управления ими в компьютерных программах. На примере языка Turbo Pascal рассматриваются: динамические переменные и переменные-указатели; некоторые структуры данных, реализуемые на их базе (одно и двусвязные списки, стеки, очереди, двоичные деревья); алгоритмы обработки таких структур данных; соответствующие задачи.
Программа рассчитана на учащихся имеющих навыки программирования языке Pascal.
Объем курса: предлагаемый курс рассчитан на 20 часов
Тематическое планирование
№ п/п | Темы занятий | Количество часов |
1. | Статические и динамические переменные. Переменные-указатели в Turbo Pascal и их использование для работы с динамическими переменными. Записи в Turbo Pascal. Построение и обработка односвязных списков. | 2 |
2. | Решение задач на обработку односвязных списков. | 2 |
3. | Двусвязные списки. | 2 |
4. | Решение задач на обработку двусвязных списков. | 2 |
5. | Стеки и очереди, их реализация с использованием динамических переменных и указателей. | 2 |
6. | Решение задач на обработку стеков и очередей. | 2 |
7. | Двоичные деревья и алгоритмы их обработки. | 4 |
8. | Решение задач на обработку двоичных деревьев и задач повышенной сложности | 4 |
Итого | 20 |
Текст пособия
Определение типов данных в Turbo-Pascal
Стандартные простые типы данных в Turbo-Pascal
В Turbo-Pascal определены следующие основные стандартные простые типы данных, с которыми связаны соответствующие зарезервированные слова.
Числовые
Целый - integer
Вещественный - real
Байтовый - byte
Символьные
Литерный - char
Строчный - string
Логический - boolean
Для каждого из перечисленных выше типов данных могут определяться константы, составляться соответствующего типа выражения, определяться переменные.
Диапазоны значений для различных типов данных имеют ограничения. Integer имеет диапазон значений от –MaxInt до MaxInt, где MaxInt – предопределенная системой константа. Byte – 0..255. Char имеет значением один символ из таблицы символов компьютера. String – цепочка символов длинной от 0 до 255 (строго говоря – этот тип является структурным). Boolean имеет два значения - True (истина) и False (ложь).
Для перечисленных выше типов данных имеются предопределенные процедуры для операций ввода (кроме boolean) и вывода в текстовом виде.
Типы данных логический, целый, байтовый, литерный относятся к так называемым перечисляемым типам, то есть таким для каждого значения которых однозначно определены предыдущий и следующий элементы.
Раздел описаний
В Turbo-Pascal элементы, в отличие от стандартного Паскаля, могут описываться в произвольном порядке.
Описанию элемента предшествует зарезервированное слово, указывающее его вид. Затем следует описание элемента.
Метки Label
Константы Const
Типы Type
Переменные Var
Функции Function
Процедуры Procedure
Форматы описания элементов:
Метки
Label
<целое число1>[, <целое число2> и так далее];
Константы
Const
<идентификатор1>=<значение1>;
[<идентификатор2>=<значение2>;]
… … … …
Типы
Type
<идентификатор1>=<описание типа1>;
[<идентификатор2>=<описание типа2>;]
… … … …
Переменные
Var
<идентификатор11>[,<идентификатор12>, …]:<тип1>;
[<идентификатор12>[,<идентификатор22>, …]:<тип2>;]
… … … …
Приведем пример содержащий описания элементов некоторых типов
Program prim01;
Label
1,5;
Const
H=4.3;
Type
F=array [1..8] of real;
Var
A, b,c:integer;
X:f;
……………
Типы данных, определяемые пользователем
Язык Паскаль имеет мощные возможности для конструирования пользователем собственных типов данных. Описание типов данных позволяет создавать такие структуры данных, которые позволяют решать задачи оптимальными способами, делают решение более наглядным, дают возможность установить соответствие между структурами данных принятыми в теоретических исследованиях и реализованными в программах.
В Паскале имеют место простые типы данных и сложные или структурные. Сложные типы данных представляют собой набор компонентов связанных общим именем и расположенных в смежной области памяти. Доступ к компонентам производится с использованием индексной адресации, тогда как к простым типам данных применяется прямая адресация[1].
Основными типами структурных данных относятся массивы (array) и записи (record).
Массивы
Массив является сложной переменной, представляющей собой связанный общим именем набор элементов одного базового типа, доступ к компонентам которой производится с использованием индексов.
Описание типа массив производится в разделе описаний и имеет следующий формат.
Type
<имя типа>=array <диапазон индексов> of <имя базового типа>;
Диапазон индексов определяет количество измерений и набор значений каждого из них. Диапазон индексов задается перечисляемым типом и является чаще всего отрезком такого типа. Применение в качестве индексов отрезков типа Char или определенного пользователем перечисляемого типа повышает наглядность и, в некоторых случаях, упрощает программирование. Однако все реальные потребности могут быть покрыты применением отрезков целого типа.
Пример
Type Ar1=array [1..20] of real;
Ar2=array ['a'..'z'] of integer;
Ar3=array [1..10,1..5] of integer;
Ar4=array [1..10] of ar1;
Приведенный пример описывает типы одномерных массивов Ar1, Ar2, двумерный массив Ar3 и массив Ar4, компонентами которого являются одномерные массивы типа Ar1.
Описание переменных имеющих тип массив может выглядеть следующим образом:
Var A:ar1;
B:ar4;
C:ar3;
Доступ к компонентам массивов производится указанием в квадратных скобках выражений, определяющих значение индекса. Для приведенного выше примера описания переменных возможны следующие способы указания индексов.
1. A[1]:=3.5;
2. B[6]:=A;
3. B[5][4]:=A[3];
4. C[2,4]:=10;
Для массива массивов возможны присваивания, приведенные во втором примере.
Для массива имеющего в качестве базового сложный тип (B типа Ar4) обращение к компонентам вложенного типа производится путем приписывание справа дополнительных скобок с указанием индекса.
Пример
Program NF3;
Type Ar=array[1..20] of real;
Var N, m:integer;
A:Ar;
Function nff1(k:integer):real;
Var
I:integer;
X:real;
Begin
X:=1;
For I:=1 to k do
X:=X*I;
nff1:=X
end;
Begin
Write('N=');
Readln(N);
For m:=1 to N do
Begin
A[m]:=nff1(m);
Writeln(A[m])
end
End.
Приведенный выше пример программы формирует и распечатывает массив значений факториала.
Записи
Запись является сложной переменной, представляющей собой связанный общим именем набор элементов различных базовых типов - полей, доступ к компонентам которой производится с использованием имени поля.
Описание типа запись производится в разделе описаний и имеет следующий формат.
Type
<имя типа>=record
<имя поля1>:<имя базового типа1>;
<имя поля2>:<имя базового типа2>;
<имя поля3>:<имя базового типа3>;
……………
end;
Правила выбора имени поля такие же, что для всех остальных идентификаторов.
Приведем пример описания типа запись и переменных такого типа, а так же доступа к их компонентам.
Program prim;
Type
Anket=record
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
