Статические и динамические структуры данных

Структура данных

Методические указания к лабораторной работе № 6
по курсам «Информатика», «Алгоритмические языки
и программирование»

 

Ростов-на-Дону 2009

Составители: Е.Н. Ладоша, О.В. Яценко, Д.С. Гирш

 

Программирование в Delphi: структура данных: метод. указания и задания к выполнению лабораторной работе №6. Ростов-на-Дону: Издательский центр ДГТУ, 2009. 20 с.

 

 

Описаны приемы и средства организации нестандартных информационных структур в Object Pascal. Целью работы ставится освоение студентами технологии структурирования данных с использованием среды Delphi. Предназначена для студентов всех специальностей факультета «Информатика и вычислительная техника».

 

Рецензент: к.т.н., доцент Долгов В.В.

 

ã Е.Н. Ладоша, О.В. Яценко, Д.С. Гирш

ã Издательский центр ДГТУ, 2009

 

 

Цель работы

Цели работы – изучить приемы и средства структурирования данных. Отдельно рассмотрены статические и динамические структуры, массивы однородных данных, а также способы их сортировки.

Структура данных

Как видно из названия, структура данных – это некая структура, содержащая данные. В области компьютерного программирования структурам данных и методам их построения посвящено много книг. В лабораторной работе рассматривается большинство таких структур.

Статические и динамические структуры данных

Статическая структура данных имеет фиксированный тип и размер. Для ее изменения программист должен изменить исходный код программы. В то же время размер (иногда и тип) динамической структуры данных может изменяться в процессе выполнения программы.

Структура данных может быть статической или динамической. Тип и размер статической структуры данных фиксированы, изменить их можно только путем изменения исходного кода. В то же время размер и тип динамической структуры данных может изменяться при выполнении программы, т.е. динамически. Одни структуры данных могут быть только динамическими, так как создаются во время выполнения. Другие могут быть объявлены как статические или как динамические.

Перечислимые типы и множества

Допустим, переменной schoolYear нужно присваивать значения, определяющие этап обучения некоего студента. В США для студентов колледжей принята следующая градация: freshman (первокурсник), sophomore (второкурсник), junior (младший) и senior (старший). Во многих компьютерных языках для присвоения таких значений необходимо или применить их нумерацию (т.е. условиться, что 1 – это freshman, 2 – это sophomore и т.д.), или объявить переменную как строковую и присваивать ей значения freshman, sophomore и т.д. Оба способа имеют существенные недостатки. Нумерация усложняет использование программы, так как человек плохо запоминает числа, а при использовании строковых переменных возникают проблемы неоднозначного написания и недопустимых значений. Object Pascal предоставляет программисту лучший способ решения этой задачи: перечислимые типы.

Перечислимый тип является упорядоченным набором значений, определенных программистом. Эти значения можно представить себе, как последовательность натуральных чисел (начиная с единицы), каждому из которых присвоено определенное название. Таким образом, перечислимый тип является пользовательским типом данных (т.е. созданным программистом, как пользователем языка).

В Object Pascal типы данных определяются с помощью ключевого слова type. Для определения перечислимого типа используется следующий синтаксис:

type имя_типа = (значение 1,..., значение N);

Входящие в синтаксис имя _ типа, значение 1... значение N должны быть правильными идентификаторами. Например, оператор

Type

Year = (Freshman, Sophomore, Junior, Senior);

определяет перечислимый тип Year, значениями которого являются элементы Freshman, Sophomore, Junior и Senior.

В определении перечислимого типа значения от значение 1 до значение N являются константами типа имя _ типа. Если эти идентификаторы в этой же области видимости используются для других целей, то возникнет конфликт имен.

Перечислимый тип можно объявить и без ключевого слова type:

Var

year1, year2:(Freshman, Sophomore, Junior, Senior);

При попытке объявить эти переменные отдельно

var yearl: (Freshman, Sophomore, Junior, Senior);

var year2: (Freshman, Sophomore, Junior, Senior);

компилятор вернет сообщение об ошибке вследствие конфликта имен.

Наиболее предпочтительным способом объявления является создание (т.е. определение) пользовательского типа.

Type

Year = (Freshman, Sophomore, Junior, Senior);

Var

year1, year2: Year;

Поэтому, всегда создавайте перечислимые типы (как и другие пользовательские типы данных) с помощью ключевого слова type. Это обеспечит совместимость типов переменных и предотвратит ошибки компиляции.

Понятия множества в Object Pascal и в математике довольно похожи. Множество состоит из группы значений одного и того же порядкового типа данных. Значения в множестве не упорядочены, и ни одно значение не может входить в множество более одного раза.

Как и перечислимый тип, множество является пользовательским типом данных.

В Object Pascal множество определяется с помощью ключевых слов set of.

Type

имя_множества = set of имя_базового_типа;

Имя_множества должно быть правильным идентификатором Object Pascal. Диапазон допустимых значений элементов множества совпадает со всеми допустимыми значениями базового типа, который должен быть порядковым типом данных. Базовый тип может быть также пользовательским типом данных, например перечислимым. Множество может содержать любые значения базового типа. Оно может быть также пустым множеством, обозначаемым в Object Pascal как [ ]. Кроме того, в Object Pascal на размер множеств наложен следующее ограничение: оно не может содержать более 256 значений. Поэтому порядковые значения базового типа должны находиться в диапазоне от 0 до 255.

В связи с этим ограничением множества иногда определяются с помощью поддиапазонов, обозначаемых двумя точками (..).

Например, оператор

Type

LowercaseSet = set of 'a'..'z';

определяет тип множества с именем LowercaseSet, значениями которого являются буквы английского алфавита от а до z в нижнем регистре. Тип данных можно также присвоить поддиапазону, т.е. определить поддиапазон как тип с указанным именем.

Type

LowercaseLetters = 'а'.. 'z';

LowercaseSet = set of LowercaseLetters;

Эти два объявления типа множества LowercaseSet эквивалентны.

Множество чисел можно объявить так:

Type

numberSet = 0..255;

numbers = set of numberSet;

Определив, таким образом, тип, можно объявлять переменные, являющиеся множествами этого типа, а затем присваивать этим переменным значения множеств. В Object Pascal значение множества записывается как заключенный в квадратные скобки список его элементов, разделенных запятыми.

[ значение 1, значение 2,..., значение N]

Значения элементов множества, естественно, должны входить в определенный поддиапазон базового типа. Не путайте значения множества и значения элементов множества! Значение множества – это некоторый набор элементов. В следующем фрагменте кода объявляется и создается множество, содержащее буквы а, b, с, m, n, х, у и z (тип LowercaseSet считается предварительно определенным):

Var

myLetters: LowercaseSet;

Begin

...

myLetters:= ['a'..'c1, 'm', 'n1, 'x'..'z'];

...

end;

Подобно тому как числовые переменные ассоциированы с арифметическими операциями, множества ассоциированы с набором операций над множествами, перечисленными в табл. 1. Например, оператор in проверяет вхождение элемента в множество: значение выражения ' a ' in myLetters равно True, если элемент ' а ' входит в множество myLetters, в противном случае оно равно False.

Таблица 1

Операции над множествами

Оператор	Операция	Типы операндов	Тип результата	Пример
+	Объединение	Множество	Множество	set1+set2
-	Разность	Множество	Множество	set1-set2
*	Пересечение	Множество	Множество	set1*set2
<=	Подмножество	Множество	Boolean	subSet<=set1
>=	Надмножество	Множество	Boolean	superSet>=set1
=	Равенство	Множество	Boolean	set1 =set2
<>	Неравенство	Множество	Boolean	set1<>set2
in	Вхождение	Множество, порядковый тип	Boolean	value in set

Операторы +, - и * подчиняются следующим правилам:

· Порядковое значение X входит в множество set1+set2, если и только если X входит в set1 или в set2 (или в оба эти множества). Значение X входит в set1-set2, если и только если X входит в set1, но не входит в set2. Значение X входит в set1 *set2, если и только если X входит как в set1, так и в set2.

· Результаты операций +, - и * принадлежат множеству А..В, где А – элемент с наименьшим порядковым значением данного типа, а В – элемент с наибольшим порядковым значением.

Операторы <=, >=, = и <> подчиняются следующим правилам:

· Значение subSet<=set1 равно True, если каждый элемент множества subSet является элементом множества set1. Значение superSet>=set1 эквивалентно значению выражения set1<=superSet. Значение set1=set2 равно True, если множества set1 и set2 содержат одни и те же элементы, в противном случае истинно значение выражения set1<>set2.

· Значение X in set1 равно True, если элемент X входит в множество set1.

 

Выполните следующий пример.

Необходимо составит программу для вычисления среднего балла, полученного абитуриентом на вступительных экзаменах по математике, физике и химии.

Решение.

Будем использовать тип-диапазон для контроля вводимых оценок.

Массивы

Массив представляет собой последовательность индексированных элементов одного и того же типа. Каждый элемент массива имеет уникальный индекс.

Массив с одним индексом называется одномерным. Математическим эквивалентом одномерного массива является вектор. Двухмерный массив имеет два индекса, его математический эквивалент – матрица. Существуют также многомерные массивы (n -мерные). Количество индексов многомерного массива больше двух. В большинстве языков программирования массивы записываются аналогично тому, как это принято в математике. Например, i -и элемент вектора х принято записывать как х_i, а i - й элемент массива х – как х [ i ]. Редактор кода Delphi использует стандартный набор символов ASCII, в который не входят нижние индексы, поэтому индекс вектора заменен выражением в квадратных скобках.

Статические массивы

В Object Pascal массивы объявляются с помощью ключевых слов array of. Синтаксис объявления N -мерного статического массива имеет вид

Var

имя массива: array[ тип_индекса 1,..., тип_индекса N] of базовый тип;

Обратите внимание: в этом синтаксисе квадратные скобки являются символами объявления массива, а не символами, обозначающими необязательную фразу синтаксиса.

Имя массива может быть любым правильным идентификатором. Базовый тип – это тип, назначаемый каждому элементу массива. Каждый индекс должен иметь порядковый тип. Общее количество элементов массива равно произведению количества элементов по каждому индексу. В качестве типа индекса чаще всего используется целый поддиапазон, однако типом индекса может быть также, например, перечислимый тип.

Для одномерного массива в объявлении используется только один тип индекса, поэтому синтаксис объявления одномерного массива имеет вид

Var

имя_одномерного_массива: array[ тип_индекса ] of базовый_тип;

Например, оператор

Var

sampleArray: array[1..10] of Integer;

объявляет массив sampleArray, содержащий 10 чисел типа Integer, причем значение индексов изменяется от 1 до 10.

В следующем фрагменте кода объявляются двухмерный и многомерный массивы:

Type

Year = (Freshman, Sophomore, Junior, Senior);

Var

smp2DArray: array[1..10, 1..5] of Integer;

smp4DArray: array[Year, 1..20, 'A'..'F', 1..3] of Char;

Двухмерный массив можно представить себе как массив массивов. Аналогично этому, многомерный массив – это массив массивов, имеющих размерность на единицу меньше (например, трехмерный массив – это массив массивов массивов). Поэтому следующие объявления эквивалентны предыдущему фрагменту кода:

Type

Year = (Freshman, Sophomore, Junior, Senior);

Var

smp2DArray: array[1..10] of array[1..5] of Integer;

smp4DArray: array[Year] of array[1..20] of

array['A'..'F'] of array[1..3] of Char;

В обоих случаях массив smp2DArray содержит 10x5=50 элементов типа Integer, a smp4DArray – 4x20x6x3=1440 элементов типа Char. Выбор способа объявления массива определяется стилем программирования. Однако помните: ваш стиль программирования должен быть неизменным на протяжении всего периода разработки программы.

Каждый элемент массива фактически является переменной базового типа. К этой переменной (т.е. к элементу массива) можно обращаться с помощью набора индексов. Для получения доступа к элементу массива можно использовать одну из следующих форм:

имя_массива [ значение_индекса 1,..., значение_индекса N]

или

имя_массива [ значение_индекса 1]... [ значение_индекса N]

Например, следующий оператор присваивает значение 10 пятому элементу массива sampleArray:

sampleArray[5]:= 10;

Как и в случае двух разных способов объявления массивов, операторы

smp2DArray[5, 2]:= 7;

smp4DArray[Junior, 10, 'А', 1]:= 'X';

эквивалентны операторам

smp2DArray[5][2]:= 7;

smp4DArray[Junior][10]['А'][1]:= 'X';

Если статический массив является формальным или фактическим параметром либо создается больше одного массива данного типа, то используйте для создания массива ключевое слово type. Проиллюстрируем это на примере. Приведем следующий фрагмент кода:

Var

intArrayl: array[1..10] of Integer;

intArray2: array[1..10] of Integer;

count: Integer;

Begin

for count:= 1 to 10 do begin

intArrayl [count]:= count;

end;

intArray2:= intArrayl;

end;

Для определения эквивалентности типов переменных компилятор Object Pascal использует имена типов. Поэтому типы массивов intArray1 и intArray2 несовместимы. Эти массивы имеют одинаковое физическое строение, но их типы разные. Поэтому компилятор сгенерирует ошибку несовместимости типов в операторе intArray2:= intArray1. Чтобы исправить ошибку, нужно записать этот фрагмент кода следующим образом:

Type

Tenlnts = array[1..10] of Integer;

Var

intArray1: Tenlnts;

intArray2: Tenlnts;

count: Integer;

Begin

for count:= 1 to 10 do begin

intArrayl[count]:= count;

end;

intArray2:= intArray1;

end;

Динамические массивы

Для объявления динамического массива используется оператор array of без задания индексов. Синтаксис объявления одномерного динамического массива имеет вид

Var

имя_динамического_массива: array of базовый_тип;

Задание размера массива и выделение для него памяти выполняется с помощью процедуры SetLength().

SetLength(имя_динамического_массива, длина);

В этом синтаксисе выражение длина должно быть целого типа. После выполнения такого оператора значение индекса динамического массива может изменяться от 0 до длина -1. Процедуру SetLength() в процессе выполнения программы можно вызывать произвольное количество раз. Каждый вызов приводит к изменению длины массива, причем содержимое массива сохраняется. Если при вызове SetLength() длина массива увеличивается, то добавленные элементы заполняются произвольными значениями, так называемым мусором. Если длина массива уменьшается, то содержимое отброшенных элементов теряется.

Динамические массивы являются динамическими структурами данных, поэтому по окончании работы с ними в программе должно быть предусмотрено их явное удаление из памяти компьютера. Процесс удаления ненужных динамических переменных из памяти компьютера иногда называют уборкой мусора. В Object Pascal программисту предоставлены три метода удаления динамических массивов.

1. Путем установки нулевой длины динамического массива: SetLength(имя_динамического_массива, 0);

2. Присвоением массиву (не его элементам, а индексной переменной, носящей имя массива) значения nil. В Object Pascal зарезервированное слово nil используется в качестве значения индексных (указательных) переменных. Если указательная переменная имеет значение nil, то она не указывает ни на какой объект. Таким образом, удалить динамический массив из памяти можно, воспользовавшись оператором – имя_динамического_массива:= nil;

3. С помощью встроенной процедуры Finalize(): Finalize(имя_динамического_массива);

Для работы с динамическими массивами Object Pascal предоставляет еще несколько полезных функций. Функция Сору() возвращает заданную часть динамического массива.

Сору (имя_динамического_массива, начальное_значение_индекса, количество_копируемых_элементов);

Функции High() и Low() возвращают наибольшее и наименьшее значения индексов динамического массива, т.е. High() возвращает значение длина -1, а Low() – значение 0. Если динамический массив имеет нулевую длину, то функция High() возвращает -1. Синтаксис этих функций имеет вид

High(имя_динамического_массива);

Low(имя_динамического_массива);

Мы рассмотрели создание и использование одномерного динамического массива. Но как создать многомерный динамический массив? Как вы помните, многомерный массив – это не что иное, как массив массивов. Поэтому синтаксис объявления массива с несколькими индексами имеет вид

Var

имя_многомерного_динамического_массива:

array of array of... array of базовый_тип;

Структуру многомерных динамических массивов чаще всего делают прямоугольной. Однако это совсем не обязательно. Например, для решения некоторых задач используются так называемые треугольные массивы, в которых один из индексов всегда равен или больше другого индекса. Если заранее известно, что в задаче используются только элементы, расположенные на диагонали или под диагональю массива, то нет никакого смысла расходовать память на элементы, расположенные над диагональю. На рис. 1 показана физическая структура такого массива. Обратите внимание: строки массива содержат разное количество элементов. Как видите, многомерные динамические массивы – довольно гибкие структуры данных. В приведенном ниже фрагменте кода создается двухмерный треугольный массив, структура которого показана на рис. 1.

Var

smp2DdynArray: array of array of Integer;

count: Integer;

Begin

SetLength(smp2DdynArray, 3);

for count = 1 to n do begin

SetLength(smp2DdynArray[count - 1], count * 2);

end;

{В этом месте массив smp2DdynArray можно использовать}

end;

	Второй индекс
Первый индекс

Рис. 1. Пример треугольного динамического массива

Имя динамического массива обозначает переменную, фактически являющуюся указателем. Это значит, что такая переменная содержит не данные, а адрес первого элемента массива. Говорят, что она указывает на первый элемент массива. Индексы определяют смещение требуемого элемента массива относительно первого. Рассмотрим следующий фрагмент кода:

Var

array1, array2: array of Integer;

check: Boolean;

Begin

SetLength(array1, 1);

SetLength(array2, 1);

array1[0]:= 5;

array2 [0]:= 5;

check:= (array1 = array2);

...

end;

Какое значение принимает переменная check? Если бы это был статический массив, то значение check было бы равно True, потому что массивы содержат одну и ту же информацию. Однако для динамических массивов (как в данном случае) значение check равно False, так как указатели array1 и аrrау2 ссылаются на разные области памяти. Значение указателя равно адресу первого по счету элемента массива, а поскольку эти массивы хранятся в разных местах, то, естественно, указатели имеют разное значение. Для сравнения динамических массивов необходимо сравнивать в цикле каждую пару элементов отдельно. Похожая проблема возникает и в следующем фрагменте кода. Можете ли вы обнаружить ее?

Var

array1, array2: array of Integer;

Begin

SetLength(array1, 1);

SetLength(array2, 1);

array1[0]:= 5;

array2:= array1;

array2[0]:= 10;

end;

Какие значения принимают элементы array1[0] и array2[0]? Обратите внимание: значение array1 присвоено array2. Другими словами, array2 теперь ссылается на туже область памяти, что и array1. Поэтому оба элемента array1[0] и array2[0] ссылаются на одну и ту же область памяти, содержащую значение 10 (присвоенное этой области последним оператором).

Задачи

1. Объявить массив из 10 целых чисел. Инициализировать массив значениями, введенными с клавиатуры. Найти в массиве первое отрицательное число и вывести его на экран. Отсортировать элементы массива любым из приведенных ниже способов. Вывести результат на экран. В программе должны быть использованы циклы всех 3-х типов.

2. С клавиатуры вводится строка. Напечатать по одному разу все буквы, входящие в эту строку. При решении задачи использовать множественный тип.

Контрольные вопросы

1. Чем отличаются статические структуры данных от динамических?

2. Что такое перечислимый тип? Приведите пример перечислимого типа.

3. Что такое множество в Object Pascal? Приведите пример множества.

4. Напишите операторы объявления одномерного, двухмерного, трехмерного и семимерного массивов.

5. Что является математическим эквивалентом одномерного массива? Двухмерного массива?

Задачи для самостоятельного выполнения

Циклы с условием (циклы ПОКА)

1. Проверить, есть ли в заданной целочисленной последовательности a₁ , a₂,..., a_N элементы, равные нулю. Если есть, найти номер первого из них, если нет – выдать соответствующий текст.

2. Выяснить, имеются ли в заданном векторе A(N) два подряд идущих нулевых элемента.

3. Выяснить, имеются ли в заданном целочисленном векторе A(N) три подряд идущих элемента одного знака.

4. Имеется последовательность чисел a₁, a₂,..., a_N . Найти сумму первых из них (считая слева направо), произведение которых не превышает заданного числа М.

5. Определить, имеются ли среди элементов побочной диагонали заданной целочисленной матрицы A(N,N) числа, равные нулю.

6. Если в заданном целочисленном векторе A(N) есть элементы со значением, равным заданному числу B, то переменной С присвоить значение, равное сумме всех элементов, предшествующих первому по порядку такому элементу; в противном случае вывести соответствующий текст.

7. Дана последовательность из N целых чисел. Определить, со скольких положительных чисел она начинается.

8. Дано натуральное N. Выяснить, сколько цифр оно содержит.

9. Найти сумму цифр заданного натурального числа.

10. Цифры заданного натурального числа записать в обратном порядке.

Вложенные циклы с условием (циклы ПОКА)

1. В заданной целочисленной матрице A(N,M) вывести на печать индексы первого положительного элемента, кратного заданному числу K. Если таких элементов в матрице нет, то вывести соответствующий текст.
Элементы матриц просматривать слева направо и сверху вниз.

2. В заданной целочисленной матрице A(N,M) заменить первый отрицательный элемент максимальным элементом матрицы. Если отрицательных элементов нет, то вывести соответствующий текст.

3. В заданной матрице A(N,N) обнулить строку, в которой находится первый отрицательный элемент. Элементы матриц просматривать слева направо и сверху вниз.

4. Из заданной матрицы A(N,N) удалить строку и столбец, в которых находится первый элемент, равный нулю. Полученную матрицу уплотнить. Элементы матриц просматривать слева направо и сверху вниз.

5. Если в заданной матрице A(N,N) есть хотя бы один элемент, больший ста, то элементы обеих диагоналей заменить нулями.

Приложение. Методы сортировки массивов

МЕТОД ПРЯМОГО ВКЛЮЧЕHИЯ

Идея алгоритма состоит в следующем. Элементы массива просматриваются по одному, и каждый следующий элемент из числа еще неупорядоченных вставляется в подходящее место среди ранее упорядоченных элементов. Очевидно, что на N-ом шаге упорядоченными окажутся ровно N элементов.

 

 

Пример.

Пусть задано 8 чисел: 27, 412, 71, 81, 59, 14, 273, 87. На каждом шаге берем очередной элемент и сравниваем его поочередно с ранее упорядоченными, пока не встретится больший данного. В таблице звездочкой отмечена граница упорядоченных элементов.

 

Итеpация	Массив
нач.сост.	027 412 071 081 059 014 273 087
	027* 412 071 081 059 014 273 087
	027 412* 071 081 059 014 273 087
	027 071 412* 081 059 014 273 087
	027 071 081 412* 059 014 273 087
	027 059 071 081 412* 014 273 087
	014 027 059 071 081 412* 273 087
	014 027 059 071 081 273 412* 087
	014 027 059 071 081 087 273 412*

 

МЕТОД ПУЗЫРЬКА (ПРЯМОГО ОБМЕHА)

Метод пузырька получил свое название благодаря тому, что на каждом шаге наименьший из неупорядоченных элемент "всплывает" к левому краю. Идея метода основана на том, что в упорядоченном массиве каждое значение находится в правильном положении относительно непосредственно следующего за ним. Этот факт является основой метода прямого обмена, основанного на сравнении соседних элементов.

 

Метод реализуется следующим алгоритмом:

а) На первом шаге все элементы массива, начиная с последнего, сравниваются с предшествующим. Если элемент a[j] оказывается меньше, чем элемент a[j-1], то элементы меняются местами. Далее элемент, стоящий теперь на (j-1)-ом месте, сравнивается с элементом a[j-2] и т.д. После завершения первого шага можно гарантировать, что наименьший элемент массива будет самым первым (помещен в самый левый край массива).

б) Далее выполняются те же действия, но процесс заканчивается перед первым (вторым, третьим и т.д.) элементом, который уже находится на своем месте. Таким образом, на каждом новом шаге наименьший из неотсортированных элементов попадает в самую левую позицию неотсортированной части массива. Процесс заканчивается, когда не будет зарегистрирован проход, на котором не было ни одной перестановки.

Пример.

При сортировке методом пузырька последовательность шагов будет следующей.

Итеpация	Массив
нач.сост.	27 412 71 81 59 14 273 87
	14* 27 412 71 81 59 87 273
	14 27* 59 412 71 81 87 273
	14 27 59* 71 412 81 87 273
	14 27 59 71* 81 412 87 273
	14 27 59 71 81* 87 412 273
	14 27 59 71 81 87* 273 412
	14 27 59 71 81 87 273* 412

 

На первом шаге последовательно выполняются следующие перестановки: 87<-->273, 14<-->59, 14<-->81, 14<-->71, 14<-->412, 14<-->27.

На втором шаге значение 59 последовательно меняется местами с 81, 71 и 412.

Метод прямого обмена по своей идее похож метод прямых вставок. Так как в нем акцент делается на поиске наименьших (наиболее "легких" элементов), то эти элементы всплывают значительно быстрее чем самые тяжелые опускаются на дно.

Метод прямого обмена работает тем эффективнее, чем правильней расположены элементы в исходном состоянии массива. Не существует способа, который бы позволил предсказать, за сколько проходов N элементов будут полностью отсортированы. Если массив упорядочен с самого начала, то потребуется всего один проход. Если элементы расположены в обратном порядке (по убыванию), то N проходов.

Список использованной литературы

1. Фаронов В.В. Delphi 3. Учебный курс. М.: «Нолидж», 1998. 400 с.

2. Галисеев Г.В. Программирование в среде Delphi 8 for.NET. М.: Издательский дом «Вильямс», 2004. 304 с.

3. Павловская Т.А. Паскаль. Программирование на языке высокого уровня. СПб.: Питер, 2003. 393 с.

4. Абрамов С.А. Задачи по программированию. М.: Наука, 1988. 224 с.

Структура данных

Методические указания к лабораторной работе № 6
по курсам «Информатика», «Алгоритмические языки
и программирование»

 

Ростов-на-Дону 2009

Составители: Е.Н. Ладоша, О.В. Яценко, Д.С. Гирш

 

Программирование в Delphi: структура данных: метод. указания и задания к выполнению лабораторной работе №6. Ростов-на-Дону: Издательский центр ДГТУ, 2009. 20 с.

 

 

Описаны приемы и средства организации нестандартных информационных структур в Object Pascal. Целью работы ставится освоение студентами технологии структурирования данных с использованием среды Delphi. Предназначена для студентов всех специальностей факультета «Информатика и вычислительная техника».

 

Рецензент: к.т.н., доцент Долгов В.В.

 

ã Е.Н. Ладоша, О.В. Яценко, Д.С. Гирш

ã Издательский центр ДГТУ, 2009

 

 

Цель работы

Цели работы – изучить приемы и средства структурирования данных. Отдельно рассмотрены статические и динамические структуры, массивы однородных данных, а также способы их сортировки.

Структура данных

Как видно из названия, структура данных – это некая структура, содержащая данные. В области компьютерного программирования структурам данных и методам их построения посвящено много книг. В лабораторной работе рассматривается большинство таких структур.

Статические и динамические структуры данных

Статическая структура данных имеет фиксированный тип и размер. Для ее изменения программист должен изменить исходный код программы. В то же время размер (иногда и тип) динамической структуры данных может изменяться в процессе выполнения программы.

Структура данных может быть статической или динамической. Тип и размер статической структуры данных фиксированы, изменить их можно только путем изменения исходного кода. В то же время размер и тип динамической структуры данных может изменяться при выполнении программы, т.е. динамически. Одни структуры данных могут быть только динамическими, так как создаются во время выполнения. Другие могут быть объявлены как статические или как динамические.