Pascal/С

Рассмотрение особенностей встроенных и производных структур данных. Сравнительный анализ методов сортировки, алгоритмов поиска в программе Pascal/С. Характеристика структуры данных "строка", "линейные списки", "стек" и "очередь", "дерево", "таблица".

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 27.09.2017
Размер файла 604,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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;{указатель на ст...


Подобные документы

  • Рассмотрение правил записи, способов ввода и вывода, использования функций обработки символьных данных в Pascal. Описание алгоритмизации и программирования файловых структур данных, проектирования структуры файла. Ознакомление с работой данных массива.

    курсовая работа [336,2 K], добавлен 27.06.2015

  • Средства создания динамических структур данных. Формат описания ссылочного типа. Структура памяти во время выполнения программы. Линейные списки, стек, очередь. Организация списков в динамической памяти. Пример создания списка в обратном порядке.

    лабораторная работа [788,2 K], добавлен 14.06.2009

  • Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.

    курсовая работа [359,0 K], добавлен 23.05.2012

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

    контрольная работа [290,6 K], добавлен 17.07.2012

  • Краткая характеристика интегрированной среды Turbo Pascal. Принципы программирования разветвляющихся алгоритмов, циклических структур, задач обработки символьных данных, множеств. Правила записи данных в текстовый файл. Понятие явной и косвенной рекурсии.

    учебное пособие [1,5 M], добавлен 10.12.2010

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

    курсовая работа [451,1 K], добавлен 19.10.2013

  • Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.

    курсовая работа [1,7 M], добавлен 16.04.2012

  • Разработка алгоритмов методом пошаговой детализации. Типы данных и операции в Turbo-Pascal. Организация работы с подпрограммами. Составление алгоритмов и программ задач с использованием конечных сумм. Организация работы с динамическими переменными.

    учебное пособие [1,4 M], добавлен 26.03.2014

  • Характеристика вычислительной системы и инструментов разработки. Программирование на языке Pascal в среде Turbo Pascal и на языке Object Pascal в среде Delphi. Использование процедур, функций, массивов, бинарного поиска. Создание базы данных в виде файла.

    отчет по практике [2,1 M], добавлен 02.05.2014

  • Изучение функций и возможностей среды разработки языка программирования Pascal. Рассмотрение работы с одномерными и двумерными массивами, со строками и числами. Математическая формулировка задач. Разработка алгоритмов, описание структуры программ.

    курсовая работа [879,8 K], добавлен 11.02.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.