Данные статической структуры

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

Данные статической структуры

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

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

Н. Вирт определил понятие программы следующим образом:

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

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

Что же характеризует данные более содержательно, чем значения? В 1973 г. Н. Виртом была опубликована статья "Типы данных -- это не значения". С его точки зрения тип данных -- это множество значений. В статье говорилось также, что данные прежде всего характеризуются набором операций, которые можно выполнять над этими данными, множеством значений. Этот взгляд и дал миру впоследствии некоторые очень полезные идеи. Главная формула, которой стали придерживаться:

ТИП ДАННЫХ = МНОЖЕСТВО ЗНАЧЕНИЙ + НАБОР ОПЕРАЦИЙ

Важно понять, что понятия данных и операций очень взаимосвязаны. Пусть есть некоторая структура данных, для которой существует операция Length, которая возвращает длину этой структуры в некоторых единицах. Возникает вопрос: есть ли где-то данные, называющиеся длиной, или нет. С содержательной точки зрения это совершенно неважно. Если эта операция применяется к строкам, признак конца которых ноль (null terminated string), то вычисление длины -- это, действительно, операция, требующая вычислений. Если эта операция применяется к строкам, первый байт которых означает длину строки, а дальше идет сама строка (как в Turbo Pascal), то здесь происходит просто взятие данных из памяти, т. е. длина может быть операцией, а может быть данными, хотя это и неважно для программиста.

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

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

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

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

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

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

Структура данных относится по существу к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы -- он служит рецептом расчета.

Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.

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

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

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

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

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

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

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

Строки, операции над строками.

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

var s: string[n];

var s: string;

n - максимально возможная длина строки - целое число в диапазоне 1..255. Если этот параметр опущен, то по умолчанию он принимается равным 255.

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

Пример:

'Текстовая строка'

#54#32#61

'abcde'^A^M

Пустой символ обозначается двумя подряд стоящими апострофами. Если апостроф входит в строку как литера, то при записи он удваивается.

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

Выражения типа char можно присваивать любым строковым переменным.

В Турбо Паскаль имеется простой доступ к отдельным символам строковой переменной: i-й символ переменной st записывается как st[i]. Например, если st - это 'Строка', то st[1] - это 'С', st[2] - это 'т', st[3] - 'р' и так далее.

Над строковыми данными определена операция слияния (конкантенации), обозначаемая знаком +. Например:

a := 'Turbo';

b := 'Pascal';

c := a + b;

В этом примере переменная c приобретет значение 'TurboPascal'.

Кроме слияния над строками определены операции сравнения <,>,=,<>,<=,>=. Две строки сравниваются посимвольно, слева направо, по кодам символов. Если одна строка меньше другой по длине, недостающие символы короткой строки заменяются символом с кодом 0.

Процедуры и функции для работы со строками

В системе Turbo Pascal имеется несколько полезных стандартных процедур и функций, ориентированных на работу со строками. Ниже приводится список этих процедур и функций с краткими пояснениями.

Length(s:string):integer

Функция возвращает в качестве результата значение текущей длины строки-параметра

Пример.

n := length('Pascal'); {n будет равно 6}

Concat(s1,[s2,...,sn]:string):string

Функция выполняет слияние строк-параметров, которых может быть произвольное количество. Каждый параметр является выражением строкового типа. Если длина строки-результата превышает 255 символов, то она усекается до 255 символов. Данная функция эквивалентна операции конкатенации "+" и работает немного менее эффективно, чем эта операция.

Copy(s:string; index:integer; count:integer):string

Функция возвращает подстроку, выделенную из исходной строки s, длиной count символов, начиная с символа под номером index.

Пример.

s := 'Система Turbo Pascal';

s2 := copy(s, 1, 7); {s2 будет равно 'Система'}

s3 := copy(s, 9, 5); {s3 будет равно 'Turbo'}

s4 := copy(s, 15, 6); {s4 будет равно 'Pascal'}

Delete(var s:string; index,count:integer)

Процедура удаляет из строки-параметра s подстроку длиной count символов, начиная с символа под номером index. Пример.

s := 'Система Turbo Pascal';

delete(s,8,6); {s будет равно 'Система Pascal'}

Insert(source:string; var s:string;index:integer)

Процедура предназначена для вставки строки source в строку s, начиная с символа index этой строки.

Пример.

s := 'Система Pascal';

insert('Turbo ',s,9); {s будет равно 'Система Turbo Pascal'}

Pos(substr,s:string):byte

Функция производит поиск в строке s подстроки substr. Результатом функции является номер первой позиции подстроки в исходной строке. Если подстрока не найдена, то функция возвращает 0.

Пример.

s := 'Система Turbo Pascal';

x1 := pos('Pascal', s); {x1 будет равно 15}

x2 := pos('Basic', s); {x2 будет равно 0}

Str(X: арифметическое выражение; var st: string)

Процедура преобразует численное выражение X в его строковое представление и помещает результат в st.

Val(st: string; x: числовая переменная; var code: integer)

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

В дополнение приведем некоторые функции, связанные с типом char, но которые тем не менее часто используются при работе со строками.

Chr(n: byte): char

Функция возвращает символ по коду, равному значению выражения n. Если n можно представить как числовую константу, то можно также пользоваться записью #n.

Ord(ch: char): byte;

В данном случае функция возвращает код символа ch.

UpCase(c: char): char;

Если c - строчная латинская буква, то функция возвращает соответствующую прописную латинскую букву, в противном случае символ c возвращается без изменения.

Размещено на Allbest.ru