Назначение процедур и функций в модулях реализации СД типа «строка» в C

1. void InputStr(string1 s). Ввод строки s с клавиатуры.

2. void OutputStr(string1 s). Вывод строки s на экран монитора.

3. void InitStr(string1 *s, unsigned n). Выделение динамической памяти под строку st, содержащую от 0 до n символов. Значением n определяется максимальное количество символов, которое может вместить строка (зависит от кол-ва выделенной памяти). Динамическая длина строки есть ее текущая длина.

4. void WriteToStr(string1 st, char *s). Запись данных в строку st из строки s. Строка s заканчивается нулевым символом '\0'.

5. void WriteFromStr(char *s, string1 st). Запись данных в строку s из строки st. Строка s заканчивается нулевым символом '\0'.

6. int Comp(string1 s1, string1 s2). Сравнивает строки s1 и s2. Возвращает 0 если s1 = s2; 1, если s1 > s2; -1, если s1 < s2.

7. void Delete(string1 s, unsigned Index, unsigned Count). Удаляет Count символов из строки s, начиная с позиции Index.

8. void Insert(string1 Subs, string1 s, unsigned Index). Вставляет подстроку SubS в строку s, начиная с позиции Index.

9. void Concat(string1 s1, string1 s2, string1 srez). Выполняет конкатенацию строк s1 и s2. Результат помещает в srez.

10. void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs). Записывает Count символов в строку Subs из строки s, начиная с позиции Index.

11. unsigned Length(string1 s). Возвращает текущую длину строки S.

12. unsigned Pos(string1 SubS, string1 s).Возвращает позицию, начиная с которой в строке s располагается подстрока SubS.

void DoneStr(string1 s). Удаляет строку s из динамической памяти.

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

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

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

3. Характеристика СД «строка» (пункт 1 задания).

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

5. Тексты модулей для реализации СД типа «строка», тексты программ для отладки модулей, тестовые данные, результаты работы программ.

6. Тексты программ для решения задачи с использованием модуля, тестовые данные, результаты работы программ.

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

Строкой называется последовательность символов.

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

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

Vстр = K + 1, где K — максимальное количество символов в строке.

Строка — это динамическая структура. В процессе выполнения программы количество элементов может изменяться от нуля до K, но размер памяти, выделенный под строку, не меняется. Практически, строка представляет собой массив символов из K + 1 элементов типа char. Нумеруются элементы от нуля до K. В Pascal в нулевом элементе хранится символ с кодом, равным динамической длине строки, т.е. количеству элементов в строке в текущий момент времени. Если там находится символ с кодом 0, то строка не содержит ни одного символа и называется пустой. Элементы, начиная с первого содержат символы строки, количество которых совпадает с динамической длиной строки. В С во внутреннем представлении этот массив (строка) заканчивается нулевым символом '\0', по которому программа может найти конец, т.е. элемент с индексом K равен нулю как признак конца строки. Доступ к элементам строки, также как и к элементам массива — прямой.

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

В языке Pascal:

1. Var s1: string;

Экземпляр СД типа строка (string) s1 располагается в статической памяти и занимает 256 байт, количество элементов строки может быть в пределах от 0 до 255.

2. Type T_str10 = string[10];

Var s2: T_str10;

Экземпляр СД типа строка (T_str10) s2 располагается в статической памяти и занимает 11 байт, количество элементов строки может быть в пределах от 0 до 10.

3. Type P_str = ^string;

Var ps3: P_str;

Строка будет располагаться в динамической памяти после обращения к процедуре new(ps3). Строка будет занимать в памяти 256 байт, адрес которой запишется в переменную ps3. Количество символов в строке может быть в пределах от 0 до 255.

Type T_str10 = string[10];

P_str10 = ^T_str10;

Var ps4: P_str10;

Строка будет располагаться в динамической памяти после обращения к процедуре new(ps4). Строка будет занимать в памяти 11 байт, адрес которой запишется в переменную ps4. Количество символов в строке может быть в пределах от 0 до 10.

В языке C:

1. #define STRLENGTH...// Значение

...

char s[STRLENGTH];

Экземпляр СД типа строка располагается в статической памяти и занимает STRLENGTH байт, количество элементов строки (символов) может быть в пределах от 0 до STRLENGTH – 1.

2. typedef char t_str10[10];

...

t_str10 s;

Экземпляр СД типа строка (t_str10) s располагается в статической памяти и занимает 10 байт, количество элементов строки может быть в пределах от 0 до 9.

3. typedef char* p_str;

...

p_str ps;

Строка будет располагаться в динамической памяти после обращения к процедуре выделения памяти (malloc или calloc). Адрес начала строки запишется в переменную ps.

4. typedef char t_str10[10]:

typedef t_str10* p_str10;

...

p_str10 ps;

Строка будет располагаться в динамической памяти после обращения:

ps = (p_str10) new p_str10;

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

Количество допустимых значений СД типа «строка»:

СAR(string) = 1 + 256 + 256² +... + 256^K,

где K — максимальное количество элементов в строке.

Операции над строками:

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

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

то перед присваиванием происходит усечение присваиваемого значения.

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

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

больше (по ASCII-коду). Иначе они равны.

3. Операция конкатенация.

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

операнда второго операнда.

В Pascal определены следующие стандартные процедуры и функции над строками:

1. Procedure Delete(var S:String; Index,Count:Integer)

Удаляет Count символов из строки S,начиная с позиции Index.

2. Procedure Insert(Subs:String;var S:String; Index:Integer)

Вставляет подстроку SubS в строку S,начиная с позиции Index.

3. Procedure Str(X:real; var S:String)

Преобразует численное значение X в его строковое представление S.

4. Procedure Val(S:String; var X;var Code:Integer)

Преобразует строковое значение S в его численное представление X. Параметр Code содержит признак ошибки преобразования (0 — нет ошибки).

5. Function Concat(S1[,S2,..,SN]:string):string

Выполняет конкатенацию последовательности строк.

6. Function Copy(S: String; Index, Count: Integer):string

Возвращает подстроку из строки S,начиная с позиции Index и длиной Count символов.

7. Function Length(S: String): byte

Возвращает текущую длину строки S.

8. Function Pos(SubS, S: String): Byte

Возвращает позицию, начиная с которой в строке S располагается

подстрока SubS (0 — S не содержит SubS).

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

char str[64] = "Символьные строки";

Следует отметить, что в языке C автоматически добавляется NULL к строковым константам.

В модуле string.h предусмотрен следующий ряд функций для работы со строками:

1. int strcmp(const char *s1, const char*s2);

Сравнивает s1 и s2 и возвращает отрицательное число, если s1 < s2; ноль, если s1 = s2; или положительное, если s1 > s2.

2. char *strcat(char *dest, const char *src);

Выполняет конкатенацию строк (копирует строку с начальным адресом srcв конец строки с адресом dest). Возвращает указатель на результирующую строку.

3. size_t strlen(const char *s);

Возвращает длину строки s.

4. char *strcpy(char *dest, const char *src);

Копирует строку src в dest, дополняя последнюю символом '\0'.

5. char *strncpy(char *dest, const char *src, size_t len);

Копирует не более len символов из строкиsrc в dest. Дополняет результат символом '\0', если символов в src меньше len. Возвращает указатель на результирующую строку.

6. char *strstr(const char *s1, const char *s2);

Возвращает указатель на первое вхождение s2 в s1 или, если такового не оказалось, NULL.

7. int sprintf (char *s, const char *format [,argument,...]);

Действует так же, как и printf, только вывод осуществляет в строку s, завершая ее символом '\0'. Строка s должна быть достаточно большой, чтобы вмещать результат вывода. Возвращает количество записанных символов, в число которых символ '\0' не входит. Функция располагается в модуле string.h.

Следующие три функции, описанные в stdlib.h, предназначены для перевода строки s в числовое значение:

double atof(const char *s);

int atoi(const char *s);

long atol(const char *s);

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

1. Какие структуры данных называются встроенными, а какие — производными?

2. Что представляет собой структура данных «строка» на абстрактном уровне?

3. Каков характер изменчивости встроенной структуры данных «строка» в языке Pascal?

4. На каких уровнях представления структур данных различаются встроенные структуры данных «строка» в языках Pascal и С?

5. Как реализованы операции над строками в языках Pascal и С?

Л а б о р а т о р н а я р а б о т а № 3