ассивы структурРассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива строк и счетчики ключевых слов в виде массива целых. Один из возможных вариантов - это иметь два параллельных массива: char *keyword[NKEYS]; int keycount[NKEYS]; Однако именно тот факт, что они параллельны, подсказывает нам другую организацию хранения - через массив структур. Каждое ключевое слово можно описать парой характеристик char *word; int count; Такие пары составляют массив. Объявление struct key { char *word; int count; } keytab[NKEYS]; объявляет структуру типа key и определяет массив keytab, каждый элемент которого является структурой этого типа и которому где-то будет выделена память. Это же можно записать и по-другому: struct key { char *word; int count; }; key keytab[NKEYS]; Так как keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения. Инициализация структур аналогична ранее демонстрировавшимся инициализациям - за определением следует список инициализаторов, заключенный в фигурные скобки: struct key { char *word; int count; } keytab[] = { "auto", 0, "break", 0, "case", 0, "char", 0, "const", 0, "continue", 0, "default", 0, /*...*/ "unsigned", 0, "void", 0, "volatile", 0, "while", 0 }; Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры. Строго говоря, пару инициализаторов для каждой отдельной структуры следовало бы заключить в фигурные скобки, как, например, в { "auto", 0 }, { "break", 0 }, { "case", 0 }, ... Однако когда инициализаторы - простые константы или строки символов и все они имеются в наличии, во внутренних скобках нет необходимости. Число элементов массива keytab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квадратных скобок "[]" ничего не задано. Программа подсчета ключевых слов начинается с определения keytab. Программа main читает ввод, многократно обращаясь к функции getword и получая на каждом ее вызове очередное слово. Каждое слово ищется в keytab. Для этого используется функция бинарного поиска. Список ключевых слов должен быть упорядочен в алфавитном порядке. #include <stdio.h> #include <ctype.h> #include <string.h> #define MAXWORD 100 int getword(char *, int); int binsearch(char *, struct key *, int); /* подсчет ключевых слов Си */ main() { int n; char word[MAXWORD]; while(getword(word, MAXWORD) != EOF) if (isalpha(word[0])) if ((n=binsearch(word, keytab, NKEYS))>=0) keytab[n].count++; for (n = 0; n < NKEYS; n++) if (keytab[n].count > 0) printf("%4d%s\n",keytab[n].count, keytab[n].word); return 0; } /* binsearch: найти слово в tab[0]...tab[n-1] */ int binsearch(char *word, struct key tab[], int n) { int cond; int low, high, mid; low = 0; high = n-1; while (low <= high) { mid = (low + high)/2; if ((cond = strcmp(word, tab[mid].word)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return mid; } return -1; } Чуть позже мы рассмотрим функцию getword, а сейчас нам достаточно знать, что при каждом ее вызове получается очередное слово, которое запоминается в массиве, заданном первым аргументом. NKEYS - количество ключевых слов в keytab. Хотя мы могли бы подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений -- поместить в конец списка инициализаторов пустой указатель (NULL) и затем перебирать в цикле элементы keytab, пока не встретится концевой элемент. Но возможно и более простое решение. Поскольку размер массива полностью определен во время компиляции и равен произведению количества элементов массива на размер его отдельного элемента, число элементов массива можно вычислить по формуле размер keytab / размер struct key В Си имеется унарная операция sizeof, которая работает во время компиляции. Его можно применять для вычисления размера любого объекта. Выражения sizeof объект и sizeof (имя типа) выдают целые значения, равные размеру указанного объекта или типа в байтах. (Строго говоря, sizeof выдает беззнаковое целое, тип которого size_t определена заголовочном файле <stddef.h>.) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа (int, double ...) или имя производного типа, например структуры или указателя. В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисление используется в инструкции #define для установки значения NKEYS: #define NKEYS (sizeof keytab / sizeof(struct key)) Этот же результат можно получить другим способом - поделить размер массива на размер какого-то его конкретного элемента: #define NKEYS (sizeof keytab / sizeof keytab[0]) Преимущество такого рода записей в том, что их не надо коppектировать при изменении типа. Поскольку препроцессор не обращает внимания на имена типов, оператор sizeof нельзя применять в #if. Но в #define выражение препроцессором не вычисляется, так что предложенная нами запись допустима. Теперь поговорим о функции getword. Мы написали getword в несколько более общем виде, чем требуется для нашей программы, но она от этого не стала заметно сложнее. Функция getword берет из входного потока следующее "слово". Под словом понимается цепочка букв-цифр, начинающаяся с буквы, или отдельный символ, отличный от символа-разделителя. В случае конца файла функция возвращает EOF, в остальных случаях ее значением является код первого символа слова или сам символ, если это не буква. /* getword: принимает следующее слово или символ из ввода */ int getword (char *word, int lim) { int c, getch(void); void ungetch(int); char *w = word; while (isspace(c = getch())) ; if (c != EOF) *w++ = c; if (!isalpha(c)) { *w = '\0'; return c; } for ( ; --lim > 0; w++) if (!isalnum(*w = getch())) { ungetch(*w); break; } *w = '\0'; return word[0]; } Функция getword обращается к getch и ungetch. По завершении набора букв-цифр оказывается, что getword взяла лишний символ. Обращение к ungetch позволяет вернуть его назад во входной поток. В getword используются также isspace - для пропуска символов-разделителей, isalpha - для идентификации букв и isalnum - для распознавания букв-цифр. Все они описаны в стандартном заголовочном файле <ctype.h>. 2. ОбъединенияОбъединение - это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале. Объединения похожи на структуры, но выполняют несколько иные функции. В объединении все переменные начинаются с одного адреса, они совмещены в памяти, что позволяет интерпретировать одну и ту же область памяти, как данные разного типа. Размер объединения определяется максимальным размером переменной.Формат объединения отличается от структуры только служебным словом union:union имя { тип1 имя переменной 1; тип2 имя переменной 2; … }; Объединение, как и структура, определяет новый тип данных и описывается, как правило, вне описания функции, а переменные описываются, используя его имя как имя нового типа. Точка с запятой в конце описания объединения должна обязательно присутствовать. Доступ к элементам объединения осуществляется так же, как к элементам структуры - через точку для имени объединения, или по стрелке для обращения через указатель. Пример 1. Например, имеется 4 флага, и мы хотели бы сократить время для операций с несколькими флагами сразу. Для простоты рассмотрим, как можно обнулить все флаги одной операцией: union Flag{ long g; char ch[4]; }; void main() { Flag fl; fl.ch[0] = 1; fl.ch[1] = 2; fl.ch[2] = 4; fl.ch[3] = 8; printf("Flag = %x\n",fl.g); fl.g = 0; //Все флаги равны 0 printf("Flag = NULL\n"); for (int i = 0; i < 4; i++) printf("%d\n",(int)fl.ch[i]); } Мы описали объединение, как переменную типа long и, одновременно, в виде массива типа char. Теперь, для переменной типа Flag, мы можем работать с каждым флагом независимо, или, используя операцию с переменной типа long, обнулить все флаги простой операцией присваивания fl.g = 0;. В следующем операторе вывода мы хотели вывести каждый символ в виде целого числа, поэтому мы поставили оператор явного преобразования типа: (int)fl.ch[i]. 3. Практические заданияЗадание 3.1 Рассмотреть пример однонаправленного списка, построенного на структуре List. Измените структуру так, чтобы получить возможность передвигаться по списку не только вперед, но и назад (двунаправленный список).Задание 3.2. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить элемент с заданным номером.Задание 3.3. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным номером.4. Лабораторные заданияНаписать программу, в которой необходимо объявить структуру данных в соответствии с вариантом. Написать все необходимые функции для работы со структурой:- функцию, которая размещает структуру в памяти и возвращает указатель на нее; - функцию, удаляющую структуру из памяти; - функцию для установки полей структуры, например: - функции, возвращающие значения полей, например: - функцию для просмотра структуры (вывода значений ее полей). Разместить структуры в динамической памяти, объединив их в список. Написать все необходимые функции для работы со списком: - функцию, добавляющую структуру в список; - функцию, удаляющую структуру из списка; - функцию, возвращающую количество элементов в списке. Написать функцию, выполняющую запрос (пример запроса для каждого варианта приведен в таблице). Сохранить список в файле. Таблица. Примеры вариантов |
Вариант | Структура | Поля структуры | Пример запроса | | 1 | СТУДЕНТ | имя char* | Имена студентов указанного курса | | | | курс int | | | | | пол bool | | | 2 | СЛУЖАЩИЙ | имя char* | Количество служащих со стажем не меньше заданного | | | | профессия char* | | | | | рабочий стаж int | | | 3. | АВТОМОБИЛЬ | марка - char* | Марки автомобилей мощностью не более заданной | | | | мощность - int | | | | | стоимость - float | | | 4 | КАДРЫ | имя char* | Имена рабочих заданного разряда | | | | номер цеха int | | | | | разряд int | | | 5 | ЦЕХ | имя char* | Наименование продукции, количество которой не менее заданного | | | | начальник char* | | | | | кол-во рабочих int | | | 6 | ИЗДЕЛИЕ | наименование char* | Наименования изделий, количество которых не более заданного | | | | шифр char* | | | | | количество int | | | 7 | БИБЛИОТЕКА | имя char* | Количество книг указанного автора | | | | автор char* | | | | | стоимость real | | | 8 | ЭКЗАМЕН | имя студента char* | Имена студентов, сдававших экзамен в заданный день | | | | дата int | | | | | оценка int | | | 9 | АДРЕС | имя char* | Имена живущих на четной стороне заданной улицы | | | | улица char* | | | | | номер дома int | | | 10 | ТОВАР | имя char* | Наименование товара, стоимостью не выше заданной | | | | количество int | | | | | стоимость real | | | 11 | КВИТАНЦИЯ | номер int | Общая сумма всех квитанций указанной даты | | | | дата int | | | | | сумма real | | | 12 | СТРАНА | название char* | Название стран, площадью не меньше заданной | | | | денежная единица char* | | | | | площадь float | | | 13 | ПОЕЗД | номер char* | Номера всех поездов указанного типа | | | | тип char* | | | | | кол-во вагонов int | | | 14 | ИГРА | наименование char* | Наименование игры указанного типа и со стоимостью не выше заданной | | | | тип char* | | | | | стоимость float | | | 15 | ПЛАНЕТА | имя char* | Имя планет с расстоянием от Земли не больше заданной | | | | размер real | | | | | расстояние от Земли real | | | 16 | ЖИВОТНОЕ | имя char* класс char* средний вес float | Имена всех животных заданного класса | | 17 | ФОТОАППАРАТ | модель char* | Модели фотоаппаратов с размером матрицы не меньше заданной | | | | изготовитель char* | | | | | размер матрицы int | | | 18 | КОРАБЛЬ | имя char* | Среднее водоизмещение кораблей заданного типа | | | | тип char* | | | | | водоизмещение int | | | 19 | РЕКА | имя char* | Среднюю длину реки на указанном континенте | | | | континент char* | | | | | длина float | | | 20 | БЛЮДО | название char* | Общую стоимость заказа | | | | тип char* | | | | | стоимость float | | | | 5. Дополнительные заданияЗадание 5.1. Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке. Задание 5.2. Напишите программу печати таблицы "перекрестных ссылок", которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать "шумовые" слова, такие как "и", "или" и пр. Задание 5.3. Напишите программу, которая печатает весь набор различных слов, образующих входной поток, в порядке возрастания частоты их встречаемости. Перед каждым словом должно быть указано число вхождений. Библиографический список1. Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си. М.: Финансы и статистика, 1985. - 192с. 2. Керниган Б., Ритчи Д. Язык программирования Си. М.:Финансы и статистика, 1992. - 272с. 3. Подбельский В. В., Фомин С. С. Программирование на языке Си. Учеб.пособие. М.: Финансы и статистика, 2004. 600 с.
Страницы: 1, 2
|