Работа с символьними строками
жүктеу/скачать 112.3 Kb.
|
|
Лабораторная работа N 1 РАБОТА С СИМВОЛЬНИМИ СТРОКАМИ 1. Цель работы Закрепление практических навыков в работе с массивами и указателями языка C, обеспечении функциональной модульности 2. Темы для предварительного изучения Указатели в языке C. Представление строк. Функции и передача параметров. 3. Постановка задачи По индивидуальному заданию создать функцию для обработки символьных строк. За образец брать библиотечные функции обработки строк языка C, но не применять их в своей функции. Предусмотреть обработку ошибок в задании параметров и особые случаи. Разработать два варианта заданной функции - используя традиционную обработку массивов и используя адресную арифметику. 4. Индивидуальные задания ╪п.п Вариант 1 Функция - Copies(s,s1,n). Назначение - копирование строки s в строку s1 n раз 2 Функция - Words(s). Назначение - подсчет слов в строке s 3 Функция - Concat(s1,s2). Назначение - конкатенация строк s1 и s2 (аналогичная библиотечная функция C - strcat) 4 Функция - Parse(s,t). Назначение - разделение строки s на две части: до первого вхождения символа t и после него 5 Функция - Center(s1,s2,l). Назначение - центрирование - размещение строки s1 в середине строки s2 длиной l 6 Функция - Delete(s,n,l). Назначение - удаление из строки s подстроки, начиная с позиции n, длиной l (аналогичная библиотечная Функция есть в Pascal). 7 Функция - Left(s,l). Назначение - выравнивание строки s по левому краю до длины l. 8 Функция - Right(s,l) Назначение - выравнивание строки s по правому краю до длины l. 9 Функция - Insert(s,s1,n). Назначение - вставка в строку s подстроки s1, начиная с позиции n (аналогичная библиотечная функция есть в Pascal). 10 Функция - Reverse(s). Назначение - изменение порядка символов в строке s на противоположный. 11 Функция - Pos(s,s1). Назначение - поиск первого вхождения подстроки s1 в строку s (аналогичная функция C - strstr). 12 Функция - LastPos(s,s1). Назначение - поиск последнего вхождения подстроки s1 в строку s. 13 Функция - WordIndex(s,n). Назначение - определение позиции начала в строке s слова с номером n. 14 Функция - WordLength(s,n). Назначение - определение длины слова с номером n в строке s. 15 Функция - SubWord(s,n,l). Назначение - выделение из строки s l слов, начиная со слова с номером n. 16 Функция - WordCmp(s1,s2). Назначение - сравнение строк (с игнорированием множественных пробелов). 17 Функция - StrSpn(s,s1). Назначение - определение длины той части строки s, которая содержит только символы из строки s1. 18 Функция - StrCSpn(s,s1). Назначение - определение длины той части строки s, которая не содержит символы из строки s1. 19 Функция - Overlay(s,s1,n). Назначение - перекрытие части строки s, начиная с позиции n, строкой s1. 20 Функция - Replace(s,s1,s2). Назначение - замена в строке s комбинации символов s1 на s2. 21 Функция - Compress(s,t). Назначение - замена в строке s множественных вхождений символа t на одно. 22 Функция - Trim(s). Назначение - удаление начальных и конечных пробелов в строке s. 23 Функция - StrSet(s,n,l,t). Назначение - установка l символов строки s, начиная с позиции n, в значение t. 23 Функция - Space(s,l). Назначение - доведение строки s до длины l путем вставки пробелов между словами. 24 Функция - Findwords(s,s1). Назначение - поиск вхождения в строку s заданной фразы (последовательности слов) s1. 25 Функция - StrType(s). Назначение - определение типа строки s (возможные типы - строка букв, десятичное число, 16-ричное число, двоичное число и т.д.). 26 Функция - Compul(s1,s2). Назначение - сравнение строк s1 и та s2 с игнорированием различий в регистрах. 27 Функция - Translate(s,s1,s2). Назначение - перевод в строке s символов, которые входят в алфавит s1, в символы, которые входят в алфавит s2. 28 Функция - Word(s). Назначение - выделение первого слова из строки s. Примечание: под "словом" везде понимается последовательность символов, которая не содержит пробелов. 5. Пример решения задачи 5.1. Индивидуальное задание: Функция - substr(s,n,l). Назначение - выделение из строки s подстроки, начиная с позиции n, длиной l. 5.2. Описание метода решения 5.2.1. Символьная строка в языке C представляется в памяти как массив символов, в конце которого находится байт с кодом 0 - признак конца строки. Строку, как и любой другой массив можно обрабатывать либо традиционным методом - как массив, с использованием операции индексации, либо через указатели, с использованием операций адресной арифметики. При работе со строкой как с массивом нужно иметь в виду, что длина строки заранее неизвестна, так что циклы должны быть организованы не со счетчиком, а до появления признака конца строки. 5.2.2. Функция должна реализовывать поставленную задачу - и ничего более. Это означает, что функцию можно будет, например, перенести без изменений в любую другую программу, если спецификации функции удовлетворяют условиям задачи. Это также означает, что при ошибочном задании параметров или при каких-то особых случаях в их значениях функция не должна аварийно завершать программу или выводить какие-то сообщения на экран, но должна возвращать какое-то прогнозируемое значение, по которому та функция, которая вызвала нашу, может сделать вывод об ошибке или об особом случае. Определим состав параметров функции: int substr (src, dest, num, len); где src - строка, с которой выбираются символы; dest - строка, в которую записываются символы; num - номер первого символа в строке src, с которого начинается подстрока (нумерация символов ведется с 0); len - длина выходной строки. Возможные возвращаемые значения функции установим: 1 (задание параметров правильное) и 0 (задание не правильное). Эти значения при обращениях к функции можно будет интерпретировать как "истина" или "ложь". Обозначим через Lsrc длину строки src. Тогда возможны такие варианты при задании параметров: num+len <= Lsrc - полностью правильное задание; num+len > Lsrc; num < Lsrc - правильное задание, но длина выходной строки буде меньше, чем len; num >= Lsrc - неправильное задание, выходная строка будет пустой; num < 0 или len <= 0 - неправильное задание, выходная строка будет пустой. Заметим, что интерпретация конфигурации параметров как правильная / неправильная и выбор реакции на неправильное задание - дело исполнителя. Но исполнитель должен строго выполнять принятые правила. Возможен также случай, когда выходная строка выйдет большей длины, чем для нее отведено места в памяти. Однако, поскольку нашей функции неизвестен размер памяти, отведенный для строки, функция не может распознать и обработать этот случай - так же ведут себя и библиотечные функции языка C. 5.3. Описание логической структуры 5.3.1. Программа состоит из одного программного модуля - файл LAB1.C. В состав модуля входят три функции - main, substr_mas и subs_ptr. Общих переменных в программе нет. Макроконстантой N определена максимальная длина строки - 80. 5.3.2. Функция main является главной функцией программы, она предназначена для ввода исходных данных, вызова других функций и вывода результатов. В функции определены переменные: ss и dd - входная и выходная строки соответственно; n - номер символа, с которого должна начинаться выходная строка; l - длина выходной строки. Функция запрашивает и вводит значение входной строки, номера символа и длины. Далее функция вызывает функцию substr_mas, передавая ей как параметры введенные значения. Если функция substr_mas возвращает 1, выводится на экран входная и выходная строки, если 0 - выводится сообщение об ошибке и входная строка. Потом входная строка делается пустой и то же самое выполняется для функции substr_ptr. 5.3.3. Функция substr_mas выполняет поставленное задание методом массивов. Ее параметры: - src и dest - входная и выходная строки соответственно, представленные в виде массивов неопределенного размера; num и len. Внутренние переменные i и j используются как индексы в массивах. Функция проверяет значения параметров в соответствии со случаем 4, если условия этого случая обнаружены, в первый элемент массива dest записывается признак конца строки и функция возвращает 0. Если случай 4 не выявлен, функция просматривает num первых символов входной строки. Если при этом будет найден признак конца строки, это - случай 3, при этом в первый элемент массива dest записывается признак конца строки и функция возвращает 0. Если признак конца в первых num символах не найден, выполняется цикл, в котором индекс входного массива начинает меняться от 1, а индекс выходного - от 0. В каждой итерации этого цикла один элемент входного массива пересылается в выходной. Если пересланный элемент является признаком конца строки (случай 2), то функция немедленно заканчивается, возвращая 1. Если в цикле не встретится конец строки, цикл завершится после len итераций. В этом случае в конец выходной строки записывается признак конца и Функция возвращает 1. 5.3.4. Функция substr_ptr выполняет поставленное задание методом указателей. Ее параметры: - src и dest - входная и выходная строки соответственно, представленные в виде указателей на начала строк; num и len. Функция проверяет значения параметров в соответствии со случаем 4, если условия этого случая выявлены, по адресу, который задает dest, записывается признак конца строки и функция возвращает 0, эти действия выполняются одним оператором. Если случай 4 не обнаружен, функция пропускает num первых символов входной строки. Это сделано циклом while, условием выхода из которого является уменьшение счетчика num до 0 или появление признака конца входной строки. Важно четко представлять порядок операций, которые выполняются в этом цикле: выбирается счетчик num; счетчик num уменьшается на 1; если выбранное значение счетчика было 0 - цикл завершается; если выбранное значение было не 0 - выбирается символ, на который указывает указатель src; указатель src увеличивается на 1; если выбранное значение символа было 0, т.е., признак конца строки, цикл завершается, иначе - повторяется. После выхода из цикла проверяется значение счетчика num: если оно не 0, это означает, что выход из цикла произошел по признаку конца строки (случай 3), по адресу, который задает dest, записывается признак конца строки и функция возвращает 0. Если признак конца не найден, выполняется цикл, подобный первому циклу while, но по счетчику len. В каждой итерации этого цикла символ, на который показывает src переписывается по адресу, задаваемому dest, после чего оба указателя увеличиваются на 1. Цикл закончится, когда будет переписано len символов или встретится признак конца строки. В любом варианте завершения цикла по текущему адресу, который содержится в указателе dest, записывается признак конца строки и функция завершается, возвращая 1. 5.4. Данные для тестирования Тестирование должно обеспечить проверку работоспособности функций для всех вариантов входных данных. Входные данные, на которых должно проводиться тестирование, сведены в таблицу: вариант src num len dest 1 012345 2 2 23 012345 0 1 0 012345 0 6 012345 2 012345 5 3 5 012345 2 6 2345 012345 0 7 012345 3 012345 8 2 пусто 4 012345 -1 2 пусто 012345 5 0 пусто 012345 5 -1 пусто 5.5. Текст программы /***************************************************************/ /*********************** Файл LAB1.C **************************/ #include #define N 80 /***************************************************************/ /* Функция выделения подстроки (массивы) */ /***************************************************************/ int substr_mas(char src[N],char dest[N],int num,int len){ int i, j; /* проверка случая 4 */ if ( (num<0)||(len<=0) ) { dest[0]=0; return 0; } /* выход на num-ый символ */ for (i=0; i<=num; i++) /* проверка случая 3 */ if ( src[i]=='\0') { dest[0]=0; return 0; } /* перезапись символов */ for (i--, j=0; j /* проверка случая 2 */ if ( dest[j]=='\0') return 1; } /* запись признака конца в выходную строку */ dest[j]='\0'; return 1; } /***************************************************************/ /* Функция выделение подстроки (адресная арифметика) */ /***************************************************************/ int substr_ptr(char *src, char *dest, int num, int len) { /* проверка случая 4 */ if ( (num<0)||(len<=0) ) return dest[0]=0; /* выход на num-ый символ или на конец строки */ while ( num-- && *src++ ); /* проверка случая 3 */ if ( !num ) return dest[0]=0; /* перезапись символов */ while ( len-- && *src ) *dest++=*src++; /* запись признака конца в выходную строку */ *dest=0; return 1; } /***************************************************************/ main() { char ss[N], dd[N]; int n, l; clrscr(); printf("Вводите строку:\n"); gets(ss); printf("начало="); scanf("%d",&n); printf("длина="); scanf("%d",&l); printf("Массивы:\n"); if (substr_mas(ss,dd,n,l)) printf(">>%s<<\n>>%s<<\n",ss,dd); else printf("Ошибка! >>%s<<\n",dd); dd[0]='\0'; printf("Адресная арифметика:\n"); if (substr_ptr(ss,dd,n,l)) printf(">>%s<<\n>>%s<<\n",ss,dd); else printf("Ошибка! >>%s<<\n",dd); getch(); } Лабораторная работа N 2 ПРЕДСТАВЛЕНИЕ В ПАМЯТИ МАССИВОВ И МАТРИЦ 1. Цель работы Получение практических навыков в использовании указателей и динамических объектов в языке C, создание модульных программ и обеспечение инкапсуляции. 2. Темы для предварительного изучения Указатели в языке C. Модульная структура программы. Области действия имен. 3. Постановка задачи Для разряженной матрицы целых чисел в соответствии с индивидуальным заданием создать модуль доступа к ней, у котором обеспечить экономию памяти при размещении данных. 4. Порядок выполнения Порядок выполнения работы и содержание отчета определены в общих указаниях. 5. Индивидуальные задания ╪п/п Вид матрицы 1 все нулевые элементы размещены в левой части матрицы 2 все нулевые элементы размещены в правой части матрицы 3 все нулевые элементы размещены выше главной диагонали 4 все нулевые элементы размещены в верхней части матрицы 5 все нулевые элементы размещены в нижней части матрицы 6 все элементы нечетных строк - нулевые 7 все элементы четных строк - нулевые 8 все элементы нечетных столбцов - нулевые 9 все элементы четных столбцов - нулевые 10 все нулевые элементы размещены в шахматном порядке, начиная с 1-го элемента 1-й строки 11 все нулевые элементы размещены в шахматном порядке, начиная со-2го элемента 1-й строки 12 все нулевые элементы размещены на местах с четными индексами строк и столбцов 13 все нулевые элементы размещены на местах с нечетными индексами строк и столбцов 14 все нулевые элементы размещены выше главной диагонали на нечетных строках и ниже главной диагонали - на четных 15 все нулевые элементы размещены ниже главной диагонали на нечетных строках и выше главной диагонали - на четных 16 все нулевые элементы размещены на главной диагонали, в первых 3 строках выше диагонали и в последних 3 строках ниже диагонали 17 все нулевые элементы размещены на главной диагонали и в верхней половине участка выше диагонали 18 все нулевые элементы размещены на главной диагонали и в нижней половине участка ниже диагонали 19 все нулевые элементы размещены в верхней и нижней четвертях матрицы (главная и побочная диагонали делят матрицу на четверти) 20 все нулевые элементы размещены в левой и правой четвертях матрицы (главная и побочная диагонали делят матрицу на четверти) 21 все нулевые элементы размещены в левой и верхней четвертях матрицы (главная и побочная диагонали делят матрицу на четверти) 22 все нулевые элементы размещены на строках, индексы которых кратны 3 23 все нулевые элементы размещены на столбцах, индексы которых кратны 3 24 все нулевые элементы размещены на строках, индексы которых кратны 4 25 все нулевые элементы размещены на столбцах, индексы которых кратны 4 26 все нулевые элементы размещены попарно в шахматном порядке (сначала 2 нулевых) 27 матрица поделена диагоналями на 4 треугольники, элементы верхнего и нижнего треугольников нулевые 28 матрица поделена диагоналями на 4 треугольники, элементы левого и правого треугольников нулевые 29 матрица поделена диагоналями на 4 треугольника, элементы правого и нижнего треугольников нулевые 30 все нулевые элементы размещены квадратами 2х2 в шахматном порядке Исполнителю самому надлежит выбрать, будут ли начинаться индексы в матрице с 0 или с 1. 6. Пример решения задачи 6.1. Индивидуальное задание: матрица содержит нули ниже главной диагонали; индексация начинается с 0. 6.2. Описание методов решения 6.2.1. Представление в памяти Экономное использование памяти предусматривает, что для тех элементов матрицы, в которых наверняка содержатся нули, память выделяться не будет. Поскольку при этом нарушается двумерная структура матрицы, она может быть представлена в памяти как одномерный массив, но при обращении к элементам матрицы пользователь имеет возможность обращаться к элементу по двум индексам. 6.2.2. Модульная структура программного изделия Программное изделие должно быть отдельным модулем, файл LAB2.C, в котором должны размещаться как данные (матрица и вспомогательная информация), так и функции, которые обеспечивают доступ. Внешний доступ к программам и данным модуля возможен только через вызов функций чтения и записи элементов матрицы. Доступные извне элементы программного модуля должны быть описаны в отдельном файле LAB2.H, который может включаться в программу пользователя оператором препроцессора: #include "lab2.h" Пользователю должен поставляться результат компиляции - файл LAB2.OBJ и файл LAB2.H. 6.2.3. Преобразование 2-компонентного адреса элемента матрицы, которую задает пользователь, в 1-компонентную должно выполняться отдельной функцией (так называемой, функцией линеаризации), вызов которой возможен только из функций модуля. Возможны три метода преобразования адреса: при создании матрицы для нее создается также и дескриптор D[N] - отдельный массив, каждый элемент которого соответствует одной строке матрицы; дескриптор заполняется значениями, подобранными так, чтобы: n = D[x] + y, где x, y - координаты пользователя (строка, столбец), n - линейная координата; линейная координата подсчитывается методом итерации як сумма полезных длин всех строк, предшествующих строке x, и к ней прибавляется смещение y-го полезного элемента относительно начала строки; для преобразования подбирается единое арифметическое выражение, которой реализует функцию: n = f(x,y). Первый вариант обеспечивает быстрейший доступ к элементу матрицы, ибо требует наименьших расчетов при каждом доступе, но плата за это - дополнительные затраты памяти на дескриптор. Второй вариант - наихудший по всем показателям, ибо каждый доступ требует выполнения оператора цикла, а это и медленно, и занимает память. Третий вариант может быть компромиссом, он не требует дополнительной памяти и работает быстрее, чем второй. Но выражение для линеаризации тут будет сложнее, чем первом варианте, следовательно, и вычисляться будет медленнее. В программном примере, который мы приводим ниже, полностью реализован именно третий вариант, но далее мы показываем и существенные фрагменты программного кода для реализации и двух других. 6.3. Описание логической структуры 6.3.1. Общие переменные В файле LAB2.C описаны такие статические переменные: int NN - размерность матрицы; int SIZE - количество ненулевых элементов в матрице; int *m_addr - адрес сжатой матрицы в памяти, начальное значение этой переменной - NULL - признак того, что память не выделена; int L2_RESULT - общий флаг ошибки, если после выполнения любой функции он равен -1, то произошла ошибка. Переменные SIZE и m_addr описаны вне функций с квалификатором static, это означает, что вони доступны для всех функций в этом модуле, но недоступны для внешних модулей. Переменная L2_RESULT также описана вне всех функций, не без явного квалификатора. Эта переменная доступна не только для этого модуля, но и для всех внешних модулей, если она в них буде описана с квалификатором extern. Такое описание имеется в файле LAB2.H. 6.3.2. Функция creat_matr Функция creat_matr предназначена для выделения в динамической памяти места для размещения сжатой матрицы. Прототип функции: int creat_matr ( int N ); где N - размерность матрицы. Функция сохраняет значение параметра в собственной статической переменной и подсчитывает необходимый размер памяти для размещения ненулевых элементов матрицы. Для выделения памяти используется библиотечная функция C malloc. Функция возвращает -1, если при выделении произошла ошибка, или 0, если выделение прошло нормально. При этом переменной L2_RESULT также присваивается значение 0 или -1. 6.3.3. Функция close_matr Функция close_matr предназначена для освобождения памяти при завершении работы с матрицей, Прототип функции: int close_matr ( void ); Функция возвращает 0 при успешном освобождении, -1 - при попытке освободить невыделенную память. Если адрес матрицы в памяти имеет значения NULL, это признак того, что память не выделялась, тогда функция возвращает -1, иначе - освобождает память при помощи библиотечной функции free и записывает адрес матрицы - NULL. Соответственно функция также устанавливает глобальный признак ошибки - L2_RESULT. 6.3.4. Функция read_matr Функция read_matr предназначена для чтения элемента матрицы. Прототип функции: int read_matr(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает значение соответствующего элемента матрицы. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении. Проверка корректности задания координат выполняется обращением к функции ch_coord, если эта последняя возвращает ненулевое значение, выполнение read_matr на этом и заканчивается. Если же координаты заданы верно, то проверяется попадание заданного элемента в нулевой или ненулевой участок. Элемент находится в нулевом участке, если для него номер строки больше, чем номер столбца. Если элемент в нулевом участке, функция просто возвращает 0, иначе - вызывает функцию линеаризации lin и использует значение, которое возвращает lin, как индекс в массиве m_addr, по которому и выбирает то значения, которое возвращается. 6.3.5. Функция write_matr Функция write_matr предназначена для записи элемента в матрицу. Прототип функции: int write_matr(int x, int y, int value); где x и y - координаты (строка и столбец), value - то значение, которое нужно записать. Функция возвращает значение параметра value, или 0 - если была попытка записи в нулевой участок. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении. Выполнение функции подобно функции read_matr с тем отличием, что, если координаты указывают на ненулевой участок, то функция записывает value в массив m_addr. 6.3.6. Функция ch_coord Функция ch_coord предназначена для проверки корректности задания координат. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции: static char ch_coord(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает 0, если координаты верные, -1 - если неверные. Соответственно, функция также устанавливает значение глобальной переменной L2_RESULT. Выполнение функции собственно состоит из проверки трех условий: адрес матрицы не должен быть NULL, т.е., матрица должна уже находиться в памяти; ни одна из координат не может быть меньше 0; ни одна из координат не может быть больше NN. Если хотя бы одно из этих условий не выполняется, функция устанавливает признак ошибки. 6.3.7. Функция lin Функция lin предназначена для преобразования двумерных координат в индекс в одномерном массиве. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции: static int lin(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает координату в массиве m_addr. Выражение, значение которого вычисляет и возвращает функция, подобрано вот из каких соображений. Пусть мы имеет такую матрицу, как показано ниже, и нам нужно найти линейную координату элемента, обозначенного буквой A с координатами (x,y): x x x x x x 0 x x x x x 0 0 x x A x 0 0 0 x x x 0 0 0 0 x x 0 0 0 0 0 x Координату элемента можно определить как: n = SIZE - sizeX +offY, где SIZE - общее количество элементов в матрице (см. creat_matr), SIZE = NN * (NN - 1) / 2 + NN; sizeX - количество ненулевых элементов, которые содержатся в строке x и ниже, sizeX = (NN - x) * (NN - x - 1) / 2 + (NN - x); offY - смещение нужного элемента от начала строки x, offY = y - x. 6.4. Программа пользователя Для проверки функционирования нашего модуля создается программный модуль, который имитирует программу пользователя. Этот модуль обращается к функции creat_matr для создания матрицы нужного размера, заполняет ненулевую ее часть последовательно увеличивающимися числами, используя для этого функцию write_matr, и выводит матрицу на экран, используя для выборки ее элементов функцию read_matr. Далее в диалоговом режиме программа вводит запрос на свои действия и читает/пишет элементы матрицы с заданными координатами, обращаясь к функциям read_matr/write_matr. Если пользователь захотел закончить работу, программа вызывает функцию close_matr. 6.5. Тексты программных модулей /********************** Файл LAB2.H *************************/ /* Описание функций и внешних переменных файла LAB2.C */ extern int L2_RESULT; /* Глобальна переменна - флаг ошибки */ /***** Выделение памяти под матрицу */ int creat_matr ( int N ); /***** Чтение элемента матрицы по заданным координатам */ int read_matr ( int x, int y ); /***** Запись элемент в матрицу по заданным координатам */ int write_matr ( int x, int y, int value ); /***** Уничтожение матрицы */ int close_matr ( void ); /***************** Конец файла LAB2.H *************************/ /************************* Файл LAB2.C *************************/ /* В этом файле определены функции и переменные для обработки матрицы, заполненной нулями ниже главной диагонали */ #include static int NN; /* Размерность матрицы */ static int SIZE; /* Размер памяти */ static int *m_addr=NULL; /* Адрес сжатой матрицы */ static int lin(int, int); /* Описание функции линеаризации */ static char ch_coord(int, int); /* Описание функции проверки */ int L2_RESULT; /* Внешняя переменная, флаг ошибки */ /*********************************************************/ /* Выделение памяти под сжатую матрицу */ int creat_matr ( int N ) { /* N - размер матрицы */ NN=N; SIZE=N*(N-1)/2+N; if ((m_addr=(int *)malloc(SIZE*sizeof(int))) == NULL ) return L2_RESULT=-1; else return L2_RESULT=0; /* Возвращает 0, если выделение прошло успешно, иначе -1 */ } /**************************************************************/ /* Уничтожение матрицы (освобождение памяти) */ int close_matr(void) { if ( m_addr!=NULL ) { free(m_addr); m_addr=NULL; return L2_RESULT=0; } else return L2_RESULT=-1; /* Возвращает 0, если освобождение пршло успешно, иначе - -1 */ } /***********************************************************/ /* Чтение элемента матрицы по заданным координатам */ int read_matr(int x, int y) { /* x, y -координати (строка, столбец) */ if ( ch_coord(x,y) ) return 0; /* Если координаты попадают в нулевой участок - возвращается 0, иначе - применяется функция линеаризации */ return (x > y) ? 0 : m_addr[lin(x,y)]; /* Проверка успешности чтения - по переменной L2_RESULT: 0 - без ошибок, -1 - была ошибка */ } /*************************************************************/ /* Запись элемента матрицы по заданным координатам */ int write_matr(int x, int y, int value) { /* x, y -координати, value - записываемое значение */ if ( chcoord(x,y) ) return; /* Если координаты попадают в нулевой участок - записи нет, иначе - применяется функция линеаризации */ if ( x > y ) return 0; else return m_addr[lin(x,y)]=value; /* Проверка успешности записи - по L2_RESULT */ } /************************************************************/ /* Преобразование 2-мерних координат в линейную */ /* (вариант 3) */ static int lin(int x, int y) { int n; n=NN-x; return SIZE-n*(n-1)/2-n+y-x; } /***************************************************************/ /* Проверка корректности обращения */ static char ch_coord(int x, int y) { if ( ( m_addr==NULL ) || ( x>SIZE ) || ( y>SIZE ) || ( x<0 ) || ( y<0 ) ) /* Если матрица не размещена в памяти, или заданные координаты выходят за пределы матрицы */ return L2_RESULT=-1; return L2_RESULT=0; } /*********************Конец файла LAB2.C ***********************/ /************************ Файл MAIN2.C **************************/ /* "Программа пользователя" */ #include "lab2.h" main(){ int R; /* размерность */ int i, j; /* номера строки и столбца */ int m; /* значения элемента */ int op; /* операция */ clrscr(); printf('Введите размерность матрицы >'); scanf("%d",R); /* создание матрицы */ if ( creat_matr (R) ) { printf("Ошибка создания матрицы\n"); exit(0); } /* заполнение матрицы */ for ( m=j=0; j while(1) { /* вывод матрицы на экран */ clrscr(); for (j=0; j printf("\n"); } printf("0 - выход\n1 - чтение\n2 - запись\n>") scanf("%d",&op); switch(op) { case 0: if (close_matr()) printf("Ошибка при уничтожении\n"); else printf("Матрица уничтожена\n"); exit(0); case 1: case 2: printf("Введите номер строки >"); scanf("%d",&j); printf("Введите номер столбца >"); scanf("%d",&i); if (op==2) { printf("Введите значение элемента >"); scanf("%d",&m); write_matr(j,i,m); if (L2_RESULT<0) pritnf("Ошибка записи\n"); } else { m=read_matr(j,i); if (L2_RESULT<0) pritnf("Ошибка считывания\n"); else printf("Считано: %d\n",m); } printf("Нажмите клавишу\n"); getch(); break; } } } /********************Конец файла MAIN2.C **********************/ 6.6. Варианты. Ниже приведены фрагменты программных кодов, которые отличают варианты, рассмотренные в 6.2.3. Вариант 1 требует: добавления к общим статическим переменным еще переменной: static int *D; /* адрес дескриптора */ добавления такого блока в функцию creat_matr: { int i, s; D=(int *)malloc(N*sizeof(int)); for (D[0]=0,s=NN-1,i=1; i } изменения функции lin на: static int lin(int x, int y) { return D[x]+y; } Вариант 2 требует: изменения функции lin на: static int lin(int x, int y) { int s; for (s=j=0; j Закрепление практических навыков в работе со структурами и указателями языка C, обеспечении функциональной модульности 3. Постановка задачи Для заданной прикладной области разработать описание объектов этой области. Разработать процедуры, реализующие базовые операции над этими объектами, в том числе: 3. Варианты индивидуальных заданий Для каждой области перечислены параметры объекта. Среди параметров обязательно есть ключевое алфавитное поле (например, фамилия), которое идентифицирует объект, у каждого объекта имеется также одно или несколько числовых полей, по которым вероятны обращения к объекту. Набор характеристик может быть расширен и усложнен по усмотрению исполнителя.Nпп Прикладная область Атрибуты информации 1 Отдел кадров фамилия сотрудника, имя, отчество, должность, стаж работы, оклад 2 Красная книга вид животного, род, семейство, место обитания, численность популяции 3 Производство обозначение изделия, группа к которой оно относится, год выпуска, объем выпуска, расход металла 4 Персональные ЭВМ фирма-изготовитель, тип процессора, тактовая частота, емкость ОЗУ, емкость жесткого диска 5 Библиотека автор книги, название, год издания, код УДК, цена, количество в библиотеке 6 Спутники планет название, название планеты-хозяина, год открытия, диаметр, период обращения 7 Радиодетали обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя 8 Текстовые редакторы наименование, фирма-изготовитель, количество окон, количество шрифтов, стоимость 9 Телефонная станция номер абонента, фамилия, адрес, наличие блокиратора, задолженность 10 Быт студентов фамилия студента, имя, отчество, факультет, размер стипендии, число членов семьи 11 Спортивные соревнования фамилия спортсмена, имя, команда, вид спорта, зачетный результат, штрафные очки 12 Соревнование факультетов по успеваемости факультет,количество студентов, средний балл по факультету, число отличников, число двоечников 13 С/х работы фамилия студента, имя, отчество, факультет, вид работ, заработок 14 Сельхозработы наименование с/х предприятия, вид собственности, число работающих, основной вид продукции, прибыль 15 Сведения о семье фамилия студента, имя, отчество, факультет, специальность отца, специальность матери, количество братьев и сестер 16 Скотоводство вид животных, количество особей в стаде в возрасте до 1 года, количество особей 1 - 3 лет, свыше 3 лет, смертность в каждой группе, рождаемость 17 Микросхемы памяти обозначение, разрядность, емкость, время доступа, количество на схеме, стоимость 18 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина строрны, радиус и т.п.). 19 Лесное хозяйство наименование зеленого массива, площадь, основная порода, средний возраст, плотность деревьев на кв.км 20 Городской транспорт вид транспорта, номер маршрута, начальная остановка, конечная остановка, время в пути 6. Пример решения задачи Прикладная область - кафедра. Атрибуты: "База данных" в оперативной памяти представляется в виде однонаправленного линейного списка. Структура элемента списка содержит четыре поля: Для сокращения записи мы определяем текст struct _emlp как _emlp: 6.2.2. Модульная структура программного изделия Программное изделие выполняется в виде одного программного модуля, файла LAB3.C, в котором размещаются данные, функция main и вспомогательные функции. 6.3.1. Общие переменные Общими переменными программы являются: 6.3.2.Функция main В функции main введена дополнительная структура, которая описывает меню. Ее полями являются: Основой функции main является цикл for в котором и осуществляется работа с базой данных. Сначала вертикально выводятся пункты меню, затем пользователю предлагается ввести код операции,которую он хочет проделать над базой. После чего производится вызов соответствующей функции обработки. Рассмотрим подробнее эту операцию.В цикле перебираются все возможные значения номера меню (их всего 10) и идет сравнение ранее введенного номера с текущим,если они совпали, то по адресу, записанному в поле *(opf) элемента массива структуры меню с текущим номером,вызывается функция обработки: По завершению работы функции производится выход из внутреннего цикла for и вся последовательность действий повторяется заново. Выход из внешнего цикла и соответственно из программы осуществляется при выборе последнего пункта меню с помощью функции exit. 6.3.3.Функция печати списка Функция печати списка f_print производит форматированный вывод всех элементов базы данных на экран.Если их количество превышает 20, то после вывода 20-ти элементов ( когда заполнен весь экран ) работа функции приостанавливается до нажатия любой клавиши. 6.3.4.Функция ввода списка Функция ввода списка f_input осуществляет ввод элементов базы. Ввод производится с помощью функции добавления элемента f_add. Конец ввода - при вводе вместо Ф.И.О. символа '*'. 6.3.5.Функция добавления элемента в список Функция добавления элемента f_add вносит новый элемент в базу. 6.3.6.Функция уничтожения элемента списка Уничтожение элемента списка производится с помощью функции f_delete, в которой происходит переприсваивание указателей и освобождение памяти, которую занимал удаленный элемент. 6.3.7.Функция изменения значения полей элемента списка Изменение значения полей элемента списка производит функция f_change. При изменении выводятся старые значения полей и предлагается ввести новые на место старых. 6.3.8.Функция сортировки списка Функция сортировки списка f_sort реализована по методу "пузырька", который рассматривался в курсе "Структура и организация данных". 6.3.9.Функция сохранения списка на диске Функция сохранения списка на диске f_save записывает все элементы базы данных в файл "D_STRUCT.DAT".Запись осуществляется полями. 6.3.10.Перезапись списка из файла в оперативную память Перезапись списка из файла в оперативную память производит функция f_restore. Она читает из файла "D_STRUCT.DAT" поля записей в поля элементов списка. /********************* Файл LAB3.C ****************************/ #include int f_add() { int get_ln () { Получение практических навыков в определении конфигурации и основных характеристик ПЭВМ. Конфигурация ПЭВМ. Для компьютера на своем рабочем месте определить: Порядок выполнения работы и содержание отчета определены в общих указаниях. Программа использует, так называемый, список оборудования - 2-байтное слово в области данных BIOS по адресу 0040:0010. Назначение разрядов списка оборудования такое: 5.2. Структура программы Программа состоит только из основной функции main(). Выделения фрагментов программы в отдельные процедуры не требуется, потому что нет таких операций, которые во время работы программы выполняются многократно. Переменные, применяемые в программе: Алгоритм основной программы может быть разбито на 5 частей. Часть 1 предназначена для определения типа компьютера. Для этого прочитаем байт, записанный в ПЗУ BIOS по адресу FF00:0FFE. В зависимости от значения этого байта сделаем вывод о типе ПЭВМ. Так, например, компьютеру типа AT соответствует код 0xFC. Часть 2 предназначена для определения конфигурации ПЭВМ. Для этого прочитаем из области данных BIOS список оборудования. Для определения количества дисководов (если бит 0 установлен в 1) необходимо выделить биты 6 и 7 (маска 00C0h) и сместить их вправо на 6 разрядов, а потом добавить 1. Для определения количества 16-Кбайтних блоков ОЗУ на системной плате необходимо выделить биты 2 и 3 с помощью маски 000Ch, сместить вправо на 2 разряды и добавить 1. Для определения количества последовательных портов RS-232 выделить с помощью маски 0Eh биты 9-11 и сместить вправо на 9 разрядов. Для определения наличия математического сопроцессора - проверить установку бита 1 маской 0002h. Для определения наличия джойстика - бита 12 с помощью маски 1000h. Определить количество параллельных принтеров можно, выделив биты 14 и 15 маской C000h и сместив их вправо на 14 разрядов. Поскольку список оборудования содержит недостаточно информации про дисплейный адаптер, то для уточнения типа адаптера выполним дополнительные действия. Видеоадаптер обслуживается прерыванием BIOS 10h. Для новых типов адаптеров список его функций расширяется. Эти новые функции и используются для определения типу адаптера. Функция 1Ah доступна только при наличии расширения BIOS, ориентированного на обслуживание VGA. В этом случае функция возвращает в регистре AL код 1Ah - свою "визитную карточку", а в BL - код активного видеоадаптера. В случае, если функция 1Ah поддерживается, обратимся еще к функции 1Bh - последняя заполняет 70-байтний блок информации про состояние, из которого мы выбираемо объем видеопамяти. Если 1Ah не поддерживается, это означает, что VGA у нас нет, в этом случае можно обратиться к функции 12h - получение информации про EGA. При наличии расширения, ориентированного на EGA, эта функция изменяет содержимое BL (перед обращением он должен быть 10h) на 0 (цветной режим) или на 1 (монохромный режим) а в BH возвращает объем видеопамяти. Если же ни 1Ah, ни 12 не поддерживаются, то список оборудования BIOS содержит достаточную информацию про видеоадаптер и, выделивши биты 4, 5 мы можем сделать окончательный вывод про тип адаптера, который у нас есть. В третьей части программы определим объем оперативной памяти, наличие и объем extended-памяти. Объем оперативной памяти для AT может быть прочитан из регистров 15h (младший байт) и 16h (старший байт) CMOS-памяти или из области памяти BIOS по адресу 0040:0013 (2-байтное слово). Кроме того, в ПЭВМ может быть еще и дополнительная (expanded) память свыше 1 Мбайту. Ее объем можно получит из регистров 17h (младший байт) и 18h (старший байт) CMOS-памяти. Для чтения регистра CMOS-памяти необходимо видать в порт 70h байт номера регистра, а потом из порта 71h прочитать байт содержимого этого регистра. В следующей части программы определим наличие и объем дополнительных ПЗУ. В адресному пространстве от C000:0000 по F600:0000 размещаются расширения ПЗУ (эта память не обязательно присутствует в ПЭВМ). Для определения наличия дополнительного ПЗУ будем читать первое слово из каждых 2 Кбайт, начиная с адреса C000:0000 в поисках маркера расширения ПЗУ: 55AAh. Если такой маркер найден, то следующий байт содержит длину модуля ПЗУ. В заключительной части программы определим версию DOS, установленную на ПЭВМ. Для этого воспользуемся функцией DOS 30h, которая возвращает в регистре AL старшее число номера версии, а в регистре AH - младшее число. /* Подключение стандартных заголовков */ /*--------------------------------------------------------*/ textbackground(0); /* Определения типа компьютера */ /* Конфигурация*/ /* Количество дисководов */ textattr(0x0e); /* Определение активного адаптера */ if(j>0 && j<12) /* Количество последовательных портов RS-232 */ cprintf(" Портов RS232: "); /* Наличие джойстика */ /* Количество параллельних принтеров */ /* Объем оперативной памяти */ textattr(0x0e); /* Наличие и объем extended-памяти */ cprintf(" байт\n\r",peekb(seg,2)); /* Определение версии операцийной системы */ intdos(&rr,&rr); textattr(0x0a); В процессе работы программы на экран была выведена такая информация: Тип компьютера: AT Первичный блок памяти: 16 Кбайт Объем оперативной памяти: 639 Кбайт Адрес ПЗУ = c000. Длина модуля = 24576 байт Версия MS-DOS 6.20 |