ПРОГРАММА И УЧЕБНЫЕ МАТЕРИАЛЫ ЭЛЕКТИВНОГО КУРСА по ИНФОРМАТИКЕ для учащихся 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
Name:string;
Rost:integer;
Date:integer
End;
Mass=array [1..20] of anket;
Var
A:anket;
D:mass;
Begin
…………………..
a. name:='Сидоров';
d[8].rost:=123;
d[3]:=a;
a. date:=12;
…………………..
end.
В приведенном примере описана запись, содержащая 3 поля и массив, состоящий из таких же записей. Показаны правила обращения к компонентам массива записей и записи.
Способы адресации данных
В электронных вычислительных машинах данные хранятся в памяти. Есть различные виды памяти: постоянная (ПЗУ) и оперативная (ОЗУ), внутренняя и внешняя, есть собственная память процессоров – регистры, кроме того, в архитектуре современных процессоров присутствует КЭШ-память, используемая для оптимизации выполнения вычислительных процессов. Существуют также и разные способы обращения к данным, хранящимся в памяти: последовательный и произвольный. Программисты, решая задачи, используют для размещения данных те ресурсы, которые необходимы в каждом конкретном случае. Однако в любой программе, есть данные, размещаемые в ОЗУ, такими данными являются переменные и константы.
Мы не будем рассматривать вопросы организации размещения в памяти констант и доступа к ним, поскольку эти процессы определяются разработчиками трансляторов, а не программистами. Рассмотрим, как организуется работа с переменными.
В программах на языке программирования Паскаль переменные подлежат обязательному описанию, при этом определяются имя (идентификатор) и тип каждой переменной. В некоторых других языках программирования такое описание (или декларирование) не являются обязательными, переменная может быть введена в программу по мере необходимости, а тип ей либо будет назначен по умолчанию, либо уточнен с помощью суффикса, приписанного после имени, либо определен другим способом. Таким образом, любая переменная будут иметь имя и тип.
Прямая адресация
Рассмотрим случай, когда переменная имеет простой тип. Тогда при трансляции с именем переменной можно связать определенный адрес оперативной памяти компьютера, а от ее типа будет зависеть, сколько ячеек памяти нужно зарезервировать для размещения значения данных.
В этом случае для работы с данными можно использовать команды процессора поддерживающие прямую адресацию памяти.
Например, скопировать слово, хранящееся по адресу памяти, указанному в регистре (1) процессора в область с адресом, указанным в регистре (2) процессора[2].
Заметим также, что этот способ можно применять и для оперирования с переменными сложных (структурных) типов, размещаемых в памяти в тех случаях, когда нужно оперировать всей сложной переменной, а не ее отдельными компонентами. Таким образом, в Паскале, например, можно передать массив в качестве аргумента процедуры или функции.
Итак, прямая адресация является самым простым и распространенным способом организации доступа к данным в оперативной памяти компьютера.
Индексная адресация
Рассмотрим другой распространенный случай – необходимо организовать доступ к компонентам переменной сложного (структурного) типа. К таким переменным в Паскале относятся массивы и записи. Компоненты сложных переменных размещаются в смежных областях памяти. С именем сложной переменной можно связать начало области размещения компонентов – базовый адрес. Место размещения конкретного компонента сложной переменной (элемента массива или поля записи) можно определить, указав для него индексное смещение от базового адреса. В этом случае можно использовать соответствующие инструкции (команды) процессора, реализующие индексную адресацию.
Например, считать в регистр (1) процессора слово, расположенное по адресу, вычисляемому по значению, указанному в регистре (2) процессора, с учетом индексного смещения указанного в инструкции.
Приведенная ниже таблица иллюстрирует размещение в памяти массива A, состоящего из элементов некоторого базового типа и записи Z, состоящей из полей N, R, K.
Элемент | Смещение | Адрес памяти |
A[1] | 0*(длина базового типа) | Начальный адрес A+0 |
A[2] | 1*(длина базового типа) | Начальный адрес A+длина базового типа |
A[3] | 2*(длина базового типа) | Начальный адрес A+2*(длина базового типа) |
…………… | …………………………. | ……………………………. |
Z. N | 0 | Начальный адрес Z+0 |
Z. R | длина N | Начальный адрес Z+длина N |
Z. K | длина N+длина R | Начальный адрес Z+длина N+длина R |
Косвенная адресация
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
