Pascal/С

Размещено на http://www.allbest.ru/

Оглавление

Введение

Основные понятия и определения

Лабораторная работа №1. Встроенные структуры данных (Pascal/С)

Лабораторная работа №2. Производные структуры данных. Структура данных «строка» (Pascal/С)

Лабораторная работа №3. Сравнительный анализ методов сортировки (Pascal/С)

Лабораторная работа №4. Сравнительный анализ алгоритмов поиска (Pascal/С)

Лабораторная работа №5. Структуры данных «линейные списки» (Pascal/С)

Лабораторная работа №6. Структуры данных «стек» и «очередь» (Pascal/С)

Лабораторная работа №7. Структуры данных «дерево» (Pascal/С)

Лабораторная работа №8. Структуры данных «таблица» (Pascal/С)

Библиографический список

сортировка алгоритм pascal строка



Введение

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

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

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

Лабораторная работа №1 посвященна изучению встроенным структурам данных языков программирования Pascal и C. Особое внимание уделяется изучению физического уровня представления этих структур.

Тематика лабораторной работы №2 связана с производными структурами данных, то есть такими структурами, которые реализует сам программист. Ему предлагается создать собственную структуру строкового типа, в соответствии с вариантом задания, и, используя ее, решить указанную задачу.

В лабораторной работе №3 изучаются базовые и улучшенные методы сортировки в основной памяти. Для сравнительного анализа алгоритмов сортировки необходимо реализовать вычислительный эксперимент для построения функции временной сложности и уметь сделать выбор для этих алгоритмов вид порядка функции временной сложности.

Лабораторная работа №4 посвящена сравнительному анализу функции временной сложности и ее порядка алгоритмов поиска.

В лабораторной работе №5 изучается производная структура данных «односвязный линейный список». Созданная студентом эта структура данных используется для решения задачи в соответствии с вариантом.

Лабораторная работа №6 посвящена классическим структурам данных «стек» и «очередь». Они реализуются студентом, причем как отображение на массив, либо как отображение на односвязный линейный список, и затем используются для моделирования модельной вычислительной системы согласно варианту.

В лабораторной работе №7 изучается нелинейная структура данных «бинарное дерево». Эта структура реализуется как в последовательной, так и в связной памяти. Затем она используется для решения задачи, которая указана в варианте заданий.

Лабораторная работа №8 посвящена широко используемой структуре данных «таблица». Эта структура данных реализуется как в линейном, так и в нелинейном варианте. С помощью созданной структуры данных также решается конкретная задача.

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

Алгоритм = метод + структуры данных

Термин «метод» будет обозначать множество алгоритмов, объединенных главной идеей. Появление нового метода - это событие и событие крайне редкое, ведущее обычно к радикальному ускорению обработки данных. Внедрение новых композиций структур данных, напротив, ярким событием не является, но зачастую в несколько раз уменьшает время обработки данных без изменения метода.

Основные понятия и определения

Структура данных (СД) -- общее свойство информационного объекта, с которым взаимодействует та или иная программа. Это общее свойство характеризуется:

множеством допустимых значений данной структуры;

набором допустимых операций;

характером организованности.

Различают следующие уровни описания СД:

абстрактный (математический) уровень;

логический уровень;

физический уровень.

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

Основные типы СД:

Множество (рис.1) -- совокупность независимых элементов, отношения между которыми не заданы.

Рис. 1. СД типа «множество»

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



Рис. 2. СД типа «последовательность»

Дерево (рис.3) -- множество элементов, над которыми определены отношения иерархического порядка, т.е. «один ко многим».

Рис.3. СД типа «дерево»

Граф (рис.4) -- множество элементов, на которых определены отношения бинарного порядка, т.е. “многие ко многим”.

Рис.4. СД типа «граф»

Важным свойством СД является ее изменчивость во время выполнения программы. Если количество элементов и/или отношения между ними изменяются, то такие СД называют динамическими, иначе -- статическими.

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

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

Физический уровень -- отображение на память ЭВМ информационного объекта в соответствии с логическим описанием. На этом уровне определяются область и объем памяти, необходимый для хранения экземпляра СД, форматы и интерпретация внутреннего представления. На физическом уровне, в памяти ЭВМ, СД могут иметь последовательную (прямоугольную) или связанную схему хранения, располагаться в статической или динамической памяти. При последовательной схеме хранения данные располагаются в соседних, последовательно расположенных ячейках памяти. Физический порядок следования данных полностью соответствует логическому. При связной схеме хранения каждый элемент СД имеет ссылку на другой (другие) элементы. Физический порядок следования данных может не соответствовать логическому.

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

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

Объем памяти, занимаемый экземпляром СД, зависит от объема памяти, занимаемой одним элементом, и характера изменчивости СД. Объем памяти, занимаемый экземпляром статической СД (массив, запись) не изменяется в процессе выполнения программы. Объем памяти, занимаемый экземпляром динамической СД может быть постоянным в процессе выполнения программы (например СД типа «строка» или динамические СД, реализованные на основе массива), или изменяться в соответствии с количеством элементов СД, если при включении/исключении элемента выделяется/освобождается достаточный для его хранения объем динамической памяти.

Память (статическая или динамическая), используемая для хранения экземпляра СД, и схема хранения СД определяется реализацией СД и не является свойством СД.

Лабораторная работа №1. Встроенные структуры данных(Pascal/С)

Цель работы: изучение базовых типов данных языка Pascal/C как структур данных (СД).

Задание

1. Для типов данных (см. Варианты заданий в таблицах 1,2) определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1.3. Логический уровень представления СД.

Способ описания СД и экземпляра СД на языке программирования.

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

3. Преобразовать значения в двоичный код.

4. Преобразовать двоичный код в значение.

5. Разработать и отладить программу, выдающую двоичное представление значений заданных СД.

В программе использовать процедуры PrintByte и PrintVar.

Спецификация процедуры PrintByte:

1. Заголовок: procedure PrintByte(a:byte)/void PrintByte(unsigned char a).

2. Назначение: выводит на экран монитора двоичное представление переменной a типа byte/unsigned char.

3. Входные параметры: a.

4. Выходные параметры: нет.

Рекомендации: использовать побитовые операции сдвига и логического умножения.

Спецификация процедуры PrintVar:

1. Заголовок: procedure PrintVar(var a; size:word)/ void PrintVar(void a, unsigned int size).

2. Назначение: выводит на экран монитора двоичное представление переменной a произвольного типа размером size байт.

3. Входные параметры: a -- переменная произвольного типа, значение которой выводится на экран в двоичном представлении (нетипизованный параметр); size -- объем памяти (в байтах) занимаемый переменной a.

4. Выходные параметры: нет.

Рекомендации: нетипизованную переменную a привести к типу «массив байт», значение каждого элемента которого выводить на экран в двоичном представлении процедурой PrintByte.

6. Обработать программой значения, полученные в результате выполнения пункта 3 задания. Сделать выводы.

7. Разработать и отладить программу, определяющую значение переменной по ее двоичному представлению по следующему алгоритму:

1. Ввести двоичный код в переменную S строкового типа.

2. Преобразовать S в вектор B типа «массив байт».

3. Привести B к заданному типу. Вывести значение.

4. Конец.

8. Обработать программой значения, полученные в результате выполнения пункта 4 задания. Сделать выводы.

Таблица 1 - Варианты индивидуальных заданий на Pascal

номер варианта	тип 1	тип 2	тип 3
1	integer	real	(red, yellow, green)
2	longint	real	массив [1..3,1..3] char
3	word	double	set of byte
4	byte	single	1000..2000
5	integer	extended	'A'..'Z'
6	shortint	single	массив [1..5] real
7	longint	comp	(cat, dog,mouse,tiger)
8	byte	real	-300..300
9	word	double	(winter,spring,summer,autumn)
10	shortint	real	set of 'a'..'h'
11	byte	single	-1..1
12	word	comp	1..256
13	integer	double	set of 50..100
14	byte	extended	'a'..'h'
15	longint	double	-256..-1
16	shortint	extended	(one,two,three,four,five,six)
17	word	real	256..511
18	integer	single	1..50
19	longint	extended	(a, b, c, d, e, f, g, h)
20	byte	double	массив [1..8] char
21	shortint	comp	-10..10
22	word	single	запись
23	integer	extended	массив [1..6] boolean
24	byte	comp	(winter,spring,summer,autumn)
25	longint	double	35000..35001
26	shortint	real	set of 200..250
27	word	extended	запись
28	integer	comp	1..256
29	byte	single	массив [1..2,1..4] integer
30	shortint	double	(day, night)

Таблица 2 - Варианты индивидуальных заданий на C

номер варианта	тип 1	тип 2	тип 3
1	int	float	{red, yellow, green}colors
2	longint	float	char массив[3][3]
3	unsigned short	double	{winter,spring, summer,autumn}seeson
4	byte	float	float массив[10][10]
5	int	long double	структура
6	signed char	float	float массив[5]
7	longint	comp	{cat, dog,mouse,tiger}animal
8	byte	float	{a, b, c, d, e, f, g, h}lettre
9	unsigned short	double	{winter,spring,summer,autumn}seeson
10	signed char	float	{red, yellow, green}colors
11	byte	float	char массив[3][3]
12	unsigned short	comp	{winter,spring,summer,autumn}seeson
13	int	double	double массив[3][3][3]
14	byte	long double	int массив [5][5]
15	longint	double	структура
16	signed char	long double	{one,two,three,four,five,six}number
17	unsigned short	float	{cat, dog,mouse,tiger}animal
18	int	float	char Массив [4][4]
19	longint	long double	{a, b, c, d, e, f, g, h}lettre
20	byte	double	char массив [8]
21	signed char	comp	float массив[3]
22	unsigned short	float	структура
23	int	long double	int массив [6]
24	byte	comp	{winter,spring,summer,autumn}seeson
25	longint	double	структура
26	signed char	float	float массив[10]
27	unsigned short	long double	структура
28	int	comp	{winter,spring,summer,autumn}seeson
29	byte	float	int массив[2][4]
30	signed char	double	{red, yellow, green}colors

Содержание отчета

1. Тема лабораторной работы.

2. Цель работы.

3. Индивидуальное задание.

4. Характеристика каждого заданного типа данных как СД в соответствии с пунктом 1 задания.

5. Набор значений заданных типов, порядок их преобразования в двоичное представление, двоичное представление значений.

6. Набор двоичных векторов, порядок их преобразования в значения заданных типов, значения заданных типов.

7. Спецификация алгоритма, текст программы, результаты работы программы, выводы (пункты 5, 6 задания).

8. Спецификация алгоритма, текст программы, результаты работы программы, выводы (пункты 7, 8 задания).

Теоретические сведения

Простые типы данных в Pascal

Целые типы

Диапазон возможных значений целых типов зависит от их внутреннего представления. В таблице 3 приводится название целых типов, длина их внутреннего представления в байтах и диапазон возможных значений.

Таблица 3 - Целые типы языка Pascal

Название типа	Диапазон значений	Длина, байт
shortint	-128..127	1
integer	-32768..32767	2
longint	-2147483648..2147483647	4
byte	0..255	1
word	0..65535	2

В первом байте типа integer, word располагается младшая часть числа, во втором -- старшая.

Символьный тип(char)

Диапазон возможных значений этого типа представляет собой множество всех символов. Каждому символу приписывается целое число от 0 до 255. Для кодировки используют код ASCII. Символьный тип занимает в памяти один байт.

Логический тип(boolean)

Множество значений: true(1) и false(0). Логический тип занимает в

памяти один байт. Тип упорядочен.

Перечисляемый тип

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

type

colors = (red, yellow, green);

Соответствие между значениями перечисляемого типа и порядковыми номерами этих значений устанавливается порядком перечисления: первое значение в списке получает порядковый номер 0, второе -- 1 и т.д. Максимальная мощность перечисляемого типа составляет 65536 значений, поэтому фактически перечисляемый тип является подмножеством целого типа word.

Тип-диапазон

Тип-диапазон есть подмножество своего базового типа, в качестве которого может выступать любой порядковый тип, кроме типа-диапазона. Он задается границами своего базового типа, например:

type

date=1..31;

month=1..12;

Вещественные типы

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

Таблица 4 - Вещественные типы языка Pascal

Название типа	Диапазон значений	Длина, байт
Real	2.9e-39..1.7e+38	6
single	1.5e-45..3.4e+38	4
double	5.0e-324..1.7e+308	8
extended	3.4e-4932..1.1e+4932	10

Внутримашинное представление вещественных типов.

Real

Формат: 

Где s -- знак, m -- мантисса, e -- порядок числа.

Формула для вычисления значения, хранящегося в памяти:

v=(-1)s2e-1291.m, если 0 < е 255 или v = 0, если e = 0.

Точность 11 -- 12 знаков.

Single

Формат:

Формула для вычисления значения, хранящегося в памяти:

v = (-1)s2e-1271.m, если 0 < e < 255

v = (-1)s21260.m, если e = 0 и m >0

v = (-1)s, если e = 0 и m = 0

v = (-1)sInf, если e = 255 и m = 0

v = NaN, если e = 255 и m 0

Точность 7 -- 8 знаков.

Double

Формат:

Формула для вычисления значения, хранящегося в памяти:

v = (-1)s2e-10231.m, если 0 < e < 2047

v = (-1)s210220.m, если e = 0 и m 0

v = (-1)s, если e = 0 и m = 0

v = (-1)sInf, если e = 2047 и m = 0

v = NaN, если e = 2047 и m 0

Точность 15 -- 16 знаков.

Extended

Формат:

Формула для вычисления значения, хранящегося в памяти:

v =(-1)s2e-163831.m, если 0 < e < 32767

v = (-1)s2163820.m, если e = 0 и m 0

v = (-1)s, если e = 0 и m = 0

v = (-1)sInf, если e = 32767 и m = 0

v = NaN, если e = 32767 и m 0

Точность 19 -- 20 знаков.

Сложный тип

Comp

Формат:

Значение v = NaN, если s = 1 и d = 0, иначе v представляет собой 64-битовое значение, являющееся дополнением до двух.

Простые типы данных в С

Целые типы

Диапазон возможных значений целых типов зависит от их внутреннего представления. В таблице 5 приводится название основных целых типов, длина их внутреннего представления в байтах и диапазон возможных значений.

Таблица 5 - Целые типы языка C

Имя типа	Диапазон значений	Размер, байт
Char	0...255	1
Int	-32768...32767	2 (или 4)

В языке C/C++ существует возможность использовать модификаторы short и long. Целью этих модификаторов было разграничить длины двух типов целых чисел для практических потребностей.

Модификаторы signed (знаковый) и unsigned (без знака) применимы к любым целым типам.

Диапазоны значений целых типов языка С приведены в таблице 6:

Таблица 6 - Диапазоны значений целых типов языка C

Имя типа	Диапазон значений	Размер, байт
Long int	-2147483648...2147483647	4
Signed char	-128...127	1
Unsigned char	0...255	1
Short int	-32768...32767	2
Unsigned int	0...65535	2
Unsigned long int	0...4294967295	4
Unsigned short int	0...65535	2

Используя модификаторы short, long, unsigned со спецификатором int, спецификатор int может быть опущен, тогда модификаторы рассматриваются как спецификаторы:

Unsigned int = unsigned

Long int = long

Short int = short

Символьный тип

Диапазоном возможных значений этого типа является множество всех символов. Каждому символу приписывается целое число от 0..255. Для кодировки используют код ASCII. Символьный тип занимает в памяти один байт.

Перечисляемый тип

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

Typedef enum {red, yellow, green}colors;

Соответствие между значениями перечисляемого типа и порядковыми номерами этих значений устанавливается порядком перечисления: первое значение в списке получает порядковый номер 0, второе -- 1 и т.д.

Вещественные типы

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

Таблица 7 - Вещественные типы языка C

Имя типа	Диапазон значений	Размер, байт
Float	1.1754943E-38...1.175494E+38	4
Double	2.22507E-308... 2.225E+308	8
Long double (в некоторых реализациях языка СИ отсутствует)	3.4Е-4932…3.4Е+4932	10

Внутримашинное представление вещественных типов:

Float

Формат:



Формула для вычисления значения, хранящегося в памяти:

v = (-1)s2e-1271.m, если 0 < e < 255

v = (-1)s21260.m, если e = 0 и m 0

v = (-1)s, если e = 0 и m = 0

v = (-1)sInf, если e = 255 и m = 0

v = NaN, если e = 255 и m 0

Точность 6 -- 7 знаков.

Double

Формат:

Формула для вычисления значения, хранящегося в памяти:

v = (-1)s2e-10231.m, если 0 < e < 2047

v = (-1)s210220.m, если e = 0 и m 0

v = (-1)s, если e = 0 и m = 0

v=(-1)sInf, если e = 2047 и m = 0

v = NaN, если e = 2047 и m 0

Точность 15-16 знаков.

Структурированные типы данных в Pascal

Массив

Массив -- последовательность элементов одного типа, называемого базовым.

На абстрактном уровне массив представляет собой линейную структуру. На физическом уровне массив реализован последовательной (прямоугольной) схемой хранения. Располагаться он может в статической или динамической памяти. Размер памяти, выделяемый под массив, зависит от базового типа элемента массива и от количества элементов в массиве и определяется формулой ; где Vмас -- объем памяти для массива, Vэл -- объем памяти одного элемента (слот), k -- количество элементов.

На логическом уровне СД типа массив можно описать следующим образом:

1. Type T_ar = array [T1] of T2; {T1 -- тип индекса }

Var Ar : T_ar; {T2 -- тип элемента}

Массив Ar типа T_ar располагается в статической памяти.

2. Type TP_ar = ^T_ar;

Var P_ar : TP_ar;

Массив типа T_ar будет располагаться в динамической памяти после обращения к процедуре new(P_ar). Адрес массива запишется в переменную P_ar.

Массив -- это статическая структура. В процессе выполнения программы количество элементов массива не изменяется. Доступ к элементу массива прямой, осуществляется через индекс элемента, например Ar[i] или P_ar^[i].

Кардинальное число для массива T_ar:

Car(T_ar) = [Car(T2)] Car(T1)

Набор допустимых операций для СД типа массив:

1. Операция доступа (доступ к элементам массива -- прямой; от размера структуры время выполнения операции не зависит).

2. Операция присваивания.

Структура данных типа «запись»

Запись -- это последовательность элементов (полей), которые могут быть различных типов.

На абстрактном уровне запись представляет собой линейную структуру.

На физическом уровне запись реализована последовательной схемой хранения. Располагаться она может в статической или в динамической памяти. Размер памяти, выделяемый под запись, зависит от типов полей и от их количества и определяется формулой Vзап = Vii=1,k ; где Vзап -- объем памяти для записи, k -- количество полей, Vi -- объем памяти для i-го поля. На логическом уровне СД типа запись можно записать следующим образом:

Type Т_rec = Record

S1: T1;

S2: T2;

……..

Sn: Tn;

End;

Var Rec: T_rec;

Здесь: S1, …, Sn -- идентификаторы полей; Т1, …, Tn -- типы полей;

Rec -- идентификатор записи; T_rec -- тип записи.

Если DT1 -- множество значений элементов типа Т1, DТ2 -- множество значений элементов типа Т2, … , DТn -- множество значений элементов типа Тn, то DTrec -- множество значений элементов типа Т_rec будет определяться с помощью прямого декартова произведения:

.

Кардинальное число для записи T_rec:

Сar(T_rec) = П Car(Ti) | i = 1, n

Допустимые операции для СД типа запись аналогичны операциям для СД типа массив.

По характеру изменчивости запись -- это статическая структура. Доступ к элементам записи прямой, осуществляется по имени поля.

Структура данных типа «множество»

Множество на физическом уровне -- это массив битов, в котором каждый бит указывает, является ли элемент принадлежащим множеству или нет. Максимальное число элементов множества -- 256, так что множество никогда не может занимать более 32 байтов.

Число байтов, занимаемых отдельным множеством, вычисляется как ByteSize = (Max div 8) - (Min div 8) + 1, где Min и Max -- нижняя и верхняя граница базового типа этого множества.

Номер байта для конкретного элемента E вычисляется по формуле Byte Number = (E div 8) - (Min div 8), а номер бита внутри этого байта -- по формуле BitNumber = E mod 8.

На логическом уровне множество можно описать так:

Type T_set = set of T; {T -- базовый тип множества}

Значениями типа множество являются все подмножества базового типа. Мощность множественного типа T_set (кардинальное число) равна Car(T_set) = 2Car(T). Число элементов базового типа ограничено и не должно превышать 256. Базовый тип является перечисляемым типом или поддиапазоном перечисляемого типа. Кроме того, объем памяти, занимаемый значением базового типа -- один байт.

Допустимыми операциями для множества являются:

1. Пересечение (*).

2. Объединение (+).

3. Вычитание (-).

4. Операции отношения:

4.1. Равенство множеств (=).

4.2. Неравенство множеств (<>).

4.3. Левый операнд -- подмножество правого (<=).

4.4. Правый операнд -- подмножество левого (>=).

4.5. Принадлежность элемента множеству (in).

Структурированные типы данных в C

Структура данных типа «массив»

Массив -- последовательность элементов одного типа, называемого базовым. На абстрактном уровне массив представляет собой линейную структуру.

На физическом уровне массив реализован последовательной (прямоугольной) схемой хранения. Располагаться он может в статической или динамической памяти. Размер памяти, выделяемый под массив, зависит от базового типа элемента массива и от количества элементов в массиве и определяется формулой Vмас = Vэл * k, где Vмас -- объем памяти для массива, Vэл -- объем памяти одного элемента (слот), k -- количество элементов.

На логическом уровне СД типа массив можно описать следующим образом:

typedef T2 t_arr[T1], где T1 -- тип индекса, T2 -- тип элемента.

t_arr ar;

Массив ar типа t_arr располагается в статической памяти.

typedef t_arr *tp_ar;

tp_ar p_ar;

Массив типа tp_ar будет располагаться в динамической памяти после обращения к одной из функций выделения памяти (calloc(), malloc()).

Адрес массива запишется в переменную p_ar.

Массив -- это статическая структура. В процессе выполнения программы количество элементов массива не изменяется. Доступ к элементу массива прямой, осуществляется через индекс элемента,

например Ar[i] или *P_ar[i].

Кардинальное число для массива T_ar:

Car(T_ar) = [Car(T2)] Car(T1).

Набор допустимых операций для СД типа массив:

1. Операция доступа (доступ к элементам массива -- прямой, от размера структуры время выполнения операции не зависит).

2. Операция присваивания.

Структура данных типа «структура»

Структура -- это последовательность элементов (полей), которые могут быть различных типов (аналогом в языке Pascal является запись).

На абстрактном уровне структура представляет собой линейную структуру.

На физическом уровне структура может быть реализована последовательной схемой хранения. Располагаться она может в статической или в динамической памяти. Размер памяти, выделяемый под структуру, зависит от типов полей и от их количества и определяется формулой Vстр = Vii=1,k , где Vстр -- объем памяти для структуры, k -- количество полей, Vi -- объем памяти для i-го поля.

На логическом уровне СД типа структура можно записать следующим образом:

typedef struct t_struct {S1: T1;

S2: T2;

……..

Sn: Tn;

};

t_struct str;

Здесь: S1, …, Sn -- идентификаторы полей; Т1, …, Tn -- типы полей; str -- идентификатор записи; t_struct -- тип записи.

Если DT1 -- множество значений элементов типа Т1, DТ2 -- множество значений элементов типа Т2, … , DТn -- множество значений элементов типа Тn, то Dt_str -- множество значений элементов типа t_str будет определяться с помощью прямого декартова произведения:

.

Кардинальное число для структуры t_str:

Car(t_str) = П Car(Ti) | i=1,n.

Допустимые операции для СД типа структура аналогичны операциям для СД типа массив. По характеру изменчивости структура -- это статическая структура данных. Доступ к элементам структуры прямой, осуществляется по имени поля.

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

1. Что такое структура данных?

2. Приведите примеры различных уровней описания структур данных.

3. Приведите примеры структур данных с различным характером организованности.

4. Какие структуры данных называют динамическими, а какае -- статическими?

5. Чем различаются последовательная и связная схемы хранения данных.

6. От чего зависит диапазон значений целых типов.

7. Приведите примеры целых типов, имеющих различный диапазон значений и одинаковый объем памяти.

8. Чем определяется точность представления вещественных значений?

9. Приведите примеры форматов машинного представления вещественных значений.

10. Как определяется объем памяти, занимаемый множеством?

11. Сколько памяти занимает пустое множество?

12. Определите характер изменчивости массива.

13. Чем различаются структуры данных массив и запись на абстрактном уровне?

14. Как осуществляется доступ к элементам массива и элементам записи?

15. Определите множество значений структурированного типа данных.



Лабораторная работа №2. Производные структуры данных. Структура данных «строка» (Pascal/C)

Цель работы: изучение встроенной структуры данных типа «строка», разработка и использование производных структур данных строкового типа.

Задание

1. Для СД типа строка определить:

1.1. Абстрактный уровень представления СД:

1.1.1 Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1.3. Логический уровень представления СД.

Способ описания СД и экземпляра СД на языке программирования.

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

3. Разработать программы на языках Pascal и С для решения задачи в соответствии с вариантом индивидуального задания (см. табл.8) с использованием модулей, полученных в результате выполнения пункта 2.

Таблица 8 - Варианты индивидуальных заданий

Номер варианта	Номер формата	Задача
1	1	1
2	2	2
3	3	3
4	4	4
5	5	5
6	6	6
7	7	7
8	8	8
9	9	9
10	1	10
11	2	11
12	3	12
13	4	13
14	5	14
15	6	15
16	7	1
17	8	2
18	9	3
19	1	4
20	2	5
21	3	6
22	4	7
23	5	8
24	6	9
25	7	10
26	8	11
27	9	12
28	1	13
29	2	14
30	3	15

Варианты задач

Заголовок: procedure Copies(var s1,s2:string; n:byte)/ void Copies(string1 s1, string1 s2, int n).

Назначение: копирование строки s в строку s1 n раз.

Входные параметры: s1,n.

Выходные параметры: s2.

Заголовок: function Word(s:string):word/ unsigned Word(string1 s).

Назначение: подсчет числа слов в строке s.

Входные параметры: s.

Выходные параметры: нет.

Заголовок: procedure Center(s1,s2:string;l:word)/ void Center(string1 s1, string1 s2, unsigned l).

Назначение: центрирование расположения строки s1 в середине строки s2 длины l.

Входные параметры: s1,l.

Выходные параметры: s2.

Заголовок: function LastPost(s1,s2:string):word/ unsigned LastPost(string1 s1, string1 s2).

Назначение: поиск последнего вхождения подстроки s2 в строку s1.

Входные параметры: s1,s2.

Выходные параметры: нет.

Заголовок: function WordLength(s:string;n:word):word/ unsigned WordLength(string1 s, unsigned n).

Назначение: определение длины слова с номером n.

Входные параметры: s,n.

Выходные параметры: нет.

Заголовок: function WordIndex(s:string;n:word):word/ unsigned WordIndex(string1 s, unsigned n).

Назначение: возврат позиции начала в строке s слова с номером n.

Входные параметры: s,n.

Выходные параметры: нет.

Заголовок: function SudWord(s:string;n:word):string/ string1 *SudWord(char *s, unsigned n).

Назначение: выделение из строки s слов, начиная с номера n.

Входные параметры: s,n.

Выходные параметры: нет.

Заголовок: function WordCmp(s1,s2:string):boolean/ int WordCmp(string1 s1, string1 s2).

Назначение: сравнение строк(с игнорированием множественных пробелов).

Входные параметры: s1,s2.

Выходные параметры: нет.

Заголовок: function StrSpn(s1,s2:string):word/ unsigned StrSpn(string1 s1, string1 s2).

Назначение: нахождение длины той части строки s1, которая содержит только символы из строки s2.

Входные параметры: s1,s2.

Выходные параметры: нет.

Заголовок: function StrCSpn(s,s1:string):word/ unsigned StrCSpn(string1 s, string1 s1).

Назначение: нахождение длины той части строки s, которая не сoдержит символы из строки s1.

Входные параметры: s,s1.

Выходные параметры: нет.

Заголовок: procedure Overlay(var s,s1:string;n:word)/ void Overlay(string1 s, string1 s1, unsigned n).

Назначение: перекрытие части строки s, начиная с позиции n, строкой s1.

Входные параметры: s,s1,n.

Выходные параметры: s.

Заголовок: procedure Compress(var s:string;c:char)/ void Compress(string1 s, char c).

Назначение: замена в строке s множественных вхождений символа c на единственное.

Входные параметры: s,c.

Выходные параметры: s.

Заголовок: procedure Trail(var s:string)/ void Trail(string1 s).

Назначение: удаление головных и хвостовых пробелов.

Входные параметры: s.

Выходные параметры: s.

Заголовок: procedure SrtSet(var s:string;n,l:word;c:char)/ void SrtSet(string1 s, unsigned n, unsigned l, char c).

Назначение: установка l символов строки s, начиная с позиции n, в значение с.

Входные параметры: s,c,l,n.

Выходные параметры: s.

Заголовок: procedure Space(s:string;l:word)/ void Space(string1 s, unsigned l).

Назначение: доведение строки s до длины l путем вставки пробелов между словами.

Входные параметры: s,l.

Выходные параметры: s.

Варианты форматов

Формат 1

Спецификация СД на языке Pascal:

Unit form1;

Interface

Const {определение исключительных ситуаций}

Type string1=array[1..256] of char;

{признак конца строки-символ с кодом 0}

Procedure WriteToStr(var st:string1;s:string);

Procedure WriteFromStr(var s:string;st:string1);

Procedure InputStr(var st:string1);

Procedure OutputStr(const st:string1);

Function Comp(s1,s2:string1;var fl:shortint):boolean;

Procedure Delete(var S:String1;Index,Count:Word);

Procedure Insert(Subs:String1;var S:String1;Index:Word);

Procedure Concat( const S1, S2:string1;var srez: string1);

Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);

Function Length(S: String1): word;

Function Pos(SubS, S: String1): word;

Var StrError: {тип переменной ошибки}

Спецификация СД на языке C:

#if !defined(__FORM1_H)

#define __FORM1_H

const ...; // Определение исключительных ситуаций

typedef char string1[256];

// Признак конца строки - символ '\0'

void WriteToStr(string1 st, char *s);

void WriteFromStr(char *s, string1 st);

void InputStr(string1 s);

void OutputStr(string1 s);

int Comp(string1 s1, string1 s2);

void Delete(string1 s, unsigned Index, unsigned Count);

void Insert(string1 Subs, string1 s, unsigned Index);

void Concat(string1 s1, string1 s2, string1 srez);

void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);

unsigned Length(string1 s);

unsigned Pos(string1 SubS, string1 s);

int StrError; // Переменная ошибок

//...

#endif

Формат 2

Спецификация СД на языке Pascal:

Unit form2;

Interface

Const {определение исключительных ситуаций}

Type

str=array[1..65520] of char; {признак конца строки - символ с кодом 0}

p_str=^str;

string1=record

st:p_str;

n:word {количество символов в строке, определяется при инициализации}

end;

Procedure InitStr(var st:string1; n:word);

Procedure WriteToStr(var st:string1;s:string);

Procedure WriteFromStr(var s:string;st:string1);

Procedure InputStr(var st:string1);

Procedure OutputStr(const st:string1);

Function Comp(s1,s2:string1;var fl:shortint):boolean;

Procedure Delete(var S:String1;Index,Count:Word);

Procedure Insert(Subs:String1;var S:String1;Index:Word);

Procedure Concat( const S1, S2:string1;var srez:string1);

Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);

Function Length(S: String1): word;

Function Pos(SubS, S: String1): word;

Var StrError: {тип переменной ошибки}

Спецификация СД на языке C:

#if !defined(__FORM2_H)

#define __FORM2_H

const ...; // Определение исключительных ситуаций

typedef struct str

{

char* s; // Признак конца строки - символ '\0'

unsigned max; /* Максимальное количество символов в строке, определяющееся при инициализации */

};

typedef str *string1;

void InitStr(string1 st, unsigned n);

void WriteToStr(string1 st, char *s);

void WriteFromStr(char *s, string1 st);

void InputStr(string1 st);

void OutputStr(string1 st);

int Comp(string1 s1, string1 s2);

void Delete(string1 s, unsigned Index, unsigned Count);

void Insert(string1 Subs, string1 s, unsigned Index);

void Concat(string1 s1, string1 s2, string1 srez);

void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);

unsigned Length(string1 s);

unsigned Pos(string1 SubS, string1 s);

void DoneStr(string1 s)

int StrError; // Переменная ошибок

//...

#endif

Формат 3

Спецификация СД на языке Pascal:

Unit form3;

Interface

Const {определение исключительных ситуаций}

Type string1=array[-1..1024] of char;

{первые два байта содержат динамическую длину строки}

Procedure WriteToStr(var st:string1;s:string);

Procedure WriteFromStr(var s:string;st:string1);

Procedure InputStr(var st:string1);

Procedure OutputStr(const st:string1);

Function Comp(s1,s2:string1;var fl:shortint):boolean;

Procedure Delete(var S:String1;Index,Count:Word);

Procedure Insert(Subs:String1;var S:String1;Index:Word);

Procedure Concat( const S1, S2:string1;var srez:string1);

Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);

Function Length(S: String1): word;

Function Pos(SubS, S: String1): word;

Var StrError: {тип переменной ошибки}

Спецификация СД на языке C:

#if !defined(__FORM3_H)

#define __FORM3_H

const ...; // Определение исключительных ситуаций

typedef char string1[1024]; /* Первые два байта содержат динамическую длину строки */

void WriteToStr(string1 st, char *s);

void WriteFromStr(char *s, string1 st);

void InputStr(string1 st);

void OutputStr(string1 st);

int Comp(string1 s1, string1 s2);

void Delete(string1 s, unsigned Index, unsigned Count);

void Insert(string1 Subs, string1 s, unsigned Index);

void Concat(string1 s1, string1 s2, string1 srez);

void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);

unsigned Length(string1 s);

unsigned Pos(string1 SubS, string1 s);

int StrError; // Переменная ошибок

//...

#endif

Формат 4

Спецификация СД на языке Pascal:

Unit form4;

Interface

Const {определение исключительных ситуаций}

Type string1=record

St:array[1..1024] of char;

N:word{динамическая длина строки}

End;

Procedure WriteToStr(var st:string1;s:string);

Procedure WriteFromStr(var s:string;st:string1);

Procedure InputStr(var st:string1);

Procedure OutputStr(const st:string1);

Function Comp(s1,s2:string1;var fl:shortint):boolean;

Procedure Delete(var S:String1;Index,Count:word);

Procedure Insert(Subs:String1;var S:String1;Index:word);

Procedure Concat( const S1, S2:string1;var srez:string1);

Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);

Function Length(S: String1): word;

Function Pos(SubS, S: String1): word;

Var StrError: {тип переменной ошибки}

Спецификация СД на языке C:

#if !defined(__FORM4_H)

#define __FORM4_H

const ...; // Определение исключительных ситуаций

typedef struct str

{

char s[1024];

unsigned N; // Динамическая длина строки

};

typedef str *string1;

void WriteToStr(string1 st, char *s);

void WriteFromStr(char *s, string1 st);

void InputStr(string1 st);

void OutputStr(string1 st);

int Comp(string1 s1, string1 s2);

void Delete(string1 s, unsigned Index, unsigned Count);

void Insert(string1 Subs, string1 s, unsigned Index);

void Concat(string1 s1, string1 s2, string1 srez);

void Copy(string1 s, unsigned Index, unsigned Count,string1 Subs);

unsigned Length(string1 s);

unsigned Pos(string1 SubS, string1 s);

int StrError; // Переменная ошибок

//...

#endif

Формат 5

Спецификация СД на языке Pascal:

Unit form5;

Interface

Const {определение исключительных ситуаций}

Type St=array[1..65520] of char;

String1=record

p_st:^st;{указатель на строку}

max:word;{максимальное количество символов в строке, определяется при инициализации}

N:word {динамическая длина строки}

End;

Procedure InitStr(var st:string1; n:word);

Procedure WriteToStr(var st:string1;s:string);

Procedure WriteFromStr(var s:string;st:string1);

Procedure InputStr(var st:string1);

Procedure OutputStr(const st:string1);

Function Comp(s1,s2:string1;var fl:shortint):boolean;

Procedure Delete(var S:String1;Index,Count:word);

Procedure Insert(Subs:String1;var S:String1;Index:word);

Procedure Concat( const S1, S2:string1;var srez:string1);

Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);

Function Length(S: String1): word;

Function Pos(SubS, S: String1): word;

Var StrError: {тип переменной ошибки}

Спецификация СД на языке C:

#if !defined(__FORM5_H)

#define __FORM5_H

const ...; // Определение исключительных ситуаций

typedef struct str

{

char *s; // Указатель на строку

unsigned max; /* Максимальное количество символов в строке, определяющееся при инициализации*/

unsigned N; // Динамическая (текущая) длина строки

};

typedef str *string1;

void InitStr(string1 st, unsigned n);

void WriteToStr(string1 st, char *s);

void WriteFromStr(char *s, string1 st);

void InputStr(string1 st);

void OutputStr(string1 st);

int Comp(string1 s1, string1 s2);

void Delete(string1 s, unsigned Index, unsigned Count);

void Insert(string1 Subs, string1 s, unsigned Index);

void Concat(string1 s1, string1 s2, string1 srez);

void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);

unsigned Length(string1 s);

unsigned Pos(string1 SubS, string1 s);

void DoneStr(string1 s)

int StrError; // Переменная ошибок

//...

#endif

Формат 6

Спецификация СД на языке Pascal:

Unit form6;

Interface

Const {определение исключительных ситуаций}

Type St=array[1..65520] of char; {первые два байта содержат максимальную длину строки, которая определяется при инициализации}

String1=record

p_st:^st;{указатель на ст...