В операционной среде, обеспечивающей поддержку Си, имеется возможность передать аргументы или параметры запускаемой программе при помощи командной строки. В момент вызова main получает два аргумента. В первом, обычно называемом argc (argument count), стоит количество аргументов, задаваемых в командной строке. Второй, argv (argument vector), являются указателем на массив литерных стрингов, содержащих сами аргументы. Для работы с этими стрингами обычно используются указатели нескольких уровней.

Простейший пример-программа с именем echo (эхо), которая печатает аргументы своей командной строки в одной строке, отделяя их друг от друга пробелами. Так команда

Echo Здравствуй, мир!

Напечатает Здравствуй, мир!

# include <stdio.h>

main (int argc, char*argv [])

{int i;

for (i=1; i<argc; i++)

printf ("% s % s", argv [i], (i<argc-1)? " ": " ");

printf ("\n");

return 0 ;

}

По соглашению argv [0] есть имя вызываемой программы, так что значение argc никогда не бывает меньше 1. Если argc=1, то в командной строке после имени программы никаких аргументов нет. В нашем примере argc равен 3, и соответственно argv [0]= "echo"; argv [1]= "Здравствуй ,", argv [2]= "мир!". Стандарт требует, чтобы argv [argc] всегда был пустым указателем.

Так как argv есть указатель на массив указателей, мы можем работать с ним как с указателем, а не как с индексируемым массивом. Приведем вторую версию программы echo, использующую понятие указатель на указатель, а также префиксные операторы.

# include <stdio.h>

main (int argc, char * argv [])

{while (--argc >0)

printf ("% s % s",*++ argv,(argc>1)?'':'');

printf ("\n");

return 0 ;

}

Указатели на функции

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

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

Сортировка, как правило, распадается на три части:

- на сравнение, определяющее упорядоченность пары объектов;

- перестановку, меняющую порядок пары объектов на обратный;

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

Отметим, что алгоритм сортировки не зависит от операций сравнения и перестановки, так что, передавая ему различные функции сравнения и перестановки в качестве параметров, алгоритм можно настроить на различные критерии сортировки (линейные выбор, стандартный обмен, челночная сортировка, сортировка Шелла и т.д.)

#include <stdio.h>

#include <string.h>

#define MAXLINES 500 \\ максим.. Число строк

char *lineptr [MAXLINES]; \\ массив указателей на строки

int readlines (char *lineptr[ ], int nlines);

void writelines (char *lineptr[ ], int nlines);

void qsort (void* lineptr[ ], int left, int right, int (*comp)(void*, void*));

int numcmp(char*,char*);

\\ сортировка строк

main (int argc, char*argv[ ])

{int nlines;\\ кол-во прочитанных строк

int numeric=0; \\ 1, если сортировка по числовому значению

if (argc>1 && strcmp(argv[1],"-n")= =0)

numeric=1;

if(( nlines=readlines(lineptr,MAXLINES))>=0)

{qsort((void**) lineptr, 0, nlines-1,

(int (*)(void*,void*))(numeric?numcmp:strcmp));

writelines(lineptr,nlines);

return 0;

}

else

{printf("введено слишком много строк \n");

return 1;

}

}

В обращениях к функциям qsort,strcmp и numcmp их имена трактуются как адреса этих функций. Поэтому оператор & перед ними не нужен, как он не был нужен и перед именем массива (имя массива и имя функции - это указатели).

Функция qsort может обрабатывать данные любого типа, а не только стринги. Как видно из прототипа, функция qsort в качестве своих аргументов ожидает: массив ссылок, два целых значения и функцию с двумя аргументами - указателями. В качестве указателей - аргументов заданы указатели обобщенного типа void*. Любой указатель можно привести к типу void* и обратно без потери информации. Поэтому мы можем обратиться к qsort, предварительно преобразовав аргументы в void*. Внутри функции сравнения ее аргументы будут приведены к нужному ей типу. На самом деле эти преобразования никакого влияния на представления аргументов не оказывают, они лишь обеспечивают согласованность типов для компилятора.

\\ qsort - сортирует v[left]…v[right] по возрастанию

void qsort (void*v[ ],int left,int right, int (*comp)(void*, void *))

{int i, last;

void (swap (void *v[ ], int, int);

if (left>=right) //ничего не делается, если в массиве менее двух элементов

return;

swap (v, left,(left+right)/2);

last=left;

for (i=left+1; i<=right; i++)

if ((*comp)(v[i],v[left])<0)

swap(v, ++last, i);

swap (v, left, last);

qsort (v, left, last-1, comp);

qsort (v,last+1, right, comp);

}

Обратите внимание на четвертый параметр функции qsort

int (*comp)(void*, void*)

Этот параметр сообщает, что comp есть указатель на функцию, которая имеет два аргумента - указателя и выдает результат типа int. Таким образом, так как comp есть указатель на функцию, *comp - есть функция, то выражение (*comp) (v[i], v[left]) - обращение (вызов) к ней!

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

#include <stdlib.h>

\\ numcmp: сравнивает s1 и s2 как числа

int numcmp (char *s1, char *s2)

{double v1, v2;

v1=atof(s1); v2=atof(s2);

if (v1<v2) return -1;

else if (v1>v2) return 1;

else return 0;

}

Сложные декларации. Преобразование указателей.

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

Проблему иллюстрирует различие следующих двух деклараций:

int * f(); // f возвращает указатель на int

int ( * pf)(); // pf - указатель на функцию, которая возвращает int

В силу того, что приоритет префиксного оператора * ниже, чем приоритет оператора ( ), поэтому во втором случае скобки обязательны.

Рассмотрим следующие декларации и их словесные описания:

char ** argv , argv - указатель на указатель на char;

int (*array) [13] , array - указатель на массив [13] из int;

void* comp () , comp - функция возвращающая укзатель на void;

void ( * comp) ( ) , comp - указатель на функцию возвращающую void;

char ( *(*f())[]() , f - функция возвращающая указатель на массив [] из указателей на функцию возвращающую char;

char ( *(*ar[3])()) [5] , ar - массив [3] из указателей на функцию возвращающую указатель на массив [5] из char;

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

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

Указатель при объявлении всегда ассоциируется с некоторым типом. В частности это может быть тип void. Указатель на void можно преобразовывать к указателю на любой тип, и обратно.

Указатели на любые типы могут быть преобразованы к указателям на функции, и обратно.

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

- принятому по умолчанию размеру указателя для действующей модели памяти;

- размеру типа аргумента.

Если задан прототип функции ( предварительное объявление функции), в котором указан явно тип аргумента - указателя, в т.ч. с модификатором near, far, huge, то будет преобразование именно к этому типу.

Если объявлен указатель на функцию, то в приведении его типа можно задавать другие типы аргументов. Например,

int (*p) (long); // объявление указателя на функцию, которая ожидает

// значение типа long, и возвращает int

(*(int(*)(int))p)(0); - вызов функции по указателю.

Основная литература - 1[112-124], 2[346-370].

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

1. В чем суть инициализации массива указателей?

2. В чем разница между двумерным массивом и массивом указателей?

3. Каким образом происходит вычисление смещения элемента двумерного массива от его начала?

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

сhar*name [] = {"Неправильный месяц", "январь", "февраль", "март"};

С определением двумерного массива:

char*aname [] [15]= {"Неправильный месяц", "январь", "февраль", "март"};

5. Для определений п.4 сделайте соответствующие рисунки.

6. Какие операции допустимы над указателями на функции?

7. Каким образом трактуются имена функций?

8. В декларации (*comp) (void*, void*) скобки нужны, что обеспечивает правильную трактовку указателя на функцию. Что будет описывать декларация без скобок: *comp (void*, void*)?

9. Разберите алгоритм функции atof - перевода стринга в числовое значение.

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

11. В чем суть операторов () и [] ? Каков их приоритет в выражении?

12. Что представляет собой декларация

13. (*pfa[])()?

14. В каких четырех случаях происходит преобразование типов?

15. Могут ли указатели на любые типы данных преобразованы к указателям на функции, и наоборот?

16. По каким правилам возможно преобразование указателя к значению целого типа, и наоборот?

Лекция 11. Структуры данных. Описание структур. Указатели и структуры данных.

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

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

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

Декларация структуры "точка" будет выглядеть следующим образом

struct point

{int x;\\ в фигурных скобках список деклараций

int y;

};

point - это тег (имя) структуры (tag - ярлык, этикетка).

Тег дает название структуре данного вида и далее служит кратким обозначением той части декларации, которая заключена в фигурные скобки.

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

Декларация структуры - это тип. Запись

struct {…}x,y,z;

означает описание трех переменных структурного типа.

Декларация структуры, не содержащей списка переменных, не резервирует памяти: она просто описывает шаблон, или образец структуры. Если структура имеет тег, то этим тегом далее можно пользоваться при определении структурных объектов. Например, декларация

struct point pt;

определяет структурную переменную pt типа struct point.

Структурную переменную при ее определении можно инициализировать:

struct point maxpt = {320, 200};

Инициализировать автоматические структуры (структуры класса памяти auto) можно также присваиванием или обращением к функции, возвращающей результат в виде структуры соответствующего типа.

Доступ к отдельному члену структуры осуществляется посредством конструкции вида:

имя_структуры.член

Например, печать координат точки pt можно осуществить следующим образом:

printf ("%d,%d", pt.x, pt.y);

Структуры могут быть вложены друг в друга.

Структуры и функции. Массивы структур.

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

Существует три подхода для передачи функциям структурных объектов:

- передавать компоненты (члены) по отдельности;

- передавать всю структуру целиком;

- передавать указатель на структуру.

Если функции передается большая структура, то, чем копировать ее целиком, эффективнее передать указатель на нее.

Декларация

struct point *pp;

сообщает, что рр есть указатель на структуру типа struct point. Если рр ссылается (имеет адрес) на структуру point, то *рр есть сама структура, а (*рр).х и (*рр).у - члены структуры point. Используя указатель рр, можно написать

struct point origin, *pp;

pp=&origin;

printf ("origin:(%d,%d)\n",(*pp).x,(*pp).y);

Скобки в (*рр).х необходимы, поскольку приоритет оператора. выше чем приоритет оператора *.

В связи с понятием "указатель на структуру" была введена еще одна, более короткая форма записи для доступа к ее членам. Если р -указатель на структуру, то

p->член_структуры

есть ее отдельный член. Поэтому printf можно переписать в виде

printf("origin:(%d,%d)\n",pp->x,pp->y);

Оба оператора . и -> выполняются слева направо.

Операторы доступа к членам структуры . и -> вместе с операторами вызова функции ( ) и индексации массива [ ] занимают самое высокое положение в иерархии приоритетов и выполняются раньше любых других операторов.

Например, если задана декларация

struct

{int len;

char*str;

}*p;

то ++р -> len увеличит на 1 значение члена структуры len, а не сам указатель, поскольку в этом выражении как бы неявно присутствуют скобки:

++(р->len).

Для изменения порядка выполнения операций нужны явные скобки. Так, в (++р)->len, прежде чем взять значение len, программа продвинет указатель р.

Массивы структур

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

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;

};

struct key keytab[NKEYS];

Так как массив keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения:

struct key{

char *word;

int count;

} keytab[ ]={"auto",0,"break",0,/*…*/"while",0};

Число элементов массива keytab будет вычислено по количеству инициализаторов.

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

Sizeof объект и sizeof (имя типа)

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

Указатели на структуры

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword (char*, int);

struct key * binsearch (char*, struct key *, int);

\\ подсчет ключевых слов Си

main ( )

{char word [MAXWORD];

struct key *p;

while (getword (word, MAXWORD)!=EOF)

if (isalpha(word[0]))

if ((p=binsearch(word, keytab, NKEYS))!=NULL)

p->count++;

for (p=keytab; p<keytab+NKEYS; p++)

if (p->count > 0)

printf ("%4d%s\n",p->count, p->word);

return 0;

}

// binsearch: найти слово в tab[0]…tab[n-1]

struct key * binsearch (char *word, struct key *tab, int n)

{int cond;

struct key *low=&tab[0];

struct key * high = &tab[n];

struct key *mid;

while (low<high);

{mid=low+(high - low)/2;

if ((cond=strcmp (word,mid->word))<0)

high=mid;

else if (cond > 0)

low=mid+1;

else

return mid;

}

return NULL;

}

Если функция binsearch находит ключевое слово, то она выдает указатель на него, в противном случае она возвращает NULL. К элементам массива keytab доступ осуществляется через указатель. Инициализаторами для low и high служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы

mid = (low +high)/2

не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high-low есть число элементов, присваивание

mid = low + ( high - low )/2

установит в mid указатель на элемент, лежащий посередине между low и high.

В цикле for оператор p++ увеличит р на такую величину, чтобы выйти на следующий структурный элемент массива. Не следует полагать, что размер структуры равен сумме размеров ее членов. Оператор sizeof возвращает правильное значение. Функция 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];

}

Обращение к ungetch позволяет вернуть лишнюю литеру во входной поток.В getword используются также isspace - для пропуска пробельных литер, isalpha - для идентификации букв и isalnum - для распознавания букв - цифр. Все они описаны в стандартном головном файле <ctype.h>. Как работают функции getch и ungetch?

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

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

Структуры со ссылками на себя

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

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

В дереве на каждое отдельное слово предусмотрен "узел", который содержит:

- указатель на текст слова

- счетчик числа встречаемости

- указатель на левый сыновний узел

- указатель на правый сыновний узел

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

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

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

struct tnode //узел дерева

{char *word;//указатель на текст

int count;//число вхождений

struct tnode*left;//левый сын

struct tnode*right;// правый сын

};

Структура не может включать саму себя, но ведь struct tnode*left; определяет left как указатель на узел tnode, а не сам tnode.

Иногда возникает потребность во взаимоссылающихся структурах: двух структурах, ссылающихся друг на друга.

Прием, позволяющий справляться с этой задачей, демонстрирует следующий фрагмент:

struct t

{…

struct s *p; // p указывает на s

};

struct s

{…

struct t *q; // q указывает на t

};

Главная программа нашей задачи читает слова с помощью функции getword и вставляет их в дерево посредством функции addtree.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

struct tnode * addtree (struct tnode *, char *);

void treeprint (struct tnode *);

int getword (char * , int);

// подсчет частоты встречаемости слов

main ()

{ struct tnode * root; // указатель на корневой узел

char word [MAXWORD];

root = NULL;

while (getword(word, MAXWORD)!=EOF)

if (isalpha (word[0]))

root = addtree(root,word);

treeprint(root);

return 0;

}

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

struct tnode * talloc (void);

char * strdup (char *);

// addtree: добавляет узел со словом w в p или ниже него

struct tnode * addtree ( struct tnode *p, char * w)

{int cond;

if ( p= = NULL)//слово встречается впервые

{ p=talloc(); // создается новый узел

p->word = strdup (w);

p->count =1;

p->left = p-> right = NULL;

}

else if (( cond = strcmp( w,p->word))= = 0)

p->count + + ; // это слово уже встречалось

else if ( cond<0) // корня < левого поддерева

p->eft=addtree( p->left,w);

else

p->right=addtree( p->right,w);

return p;

}

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

# include <stdlib.h>

// talloc: создает tnode

struct tnode * talloc (void)

{return (struct tnode *) malloc (sizeof (struct tnode));

}

// strdup: копирует стринг, указанный в аргументе,

//в место, полученное с помощью malloc

char * strdup (char*s)

{char *p;

p=(char*) malloc (strlen (s) + 1); // +1для `\0'

if (p!=NULL) // если память выделена

strcpy (p,s);

return p;

}

Функция treeprint печатает дерево в лексикографическом порядке; для каждого узла она печатает его левое поддерево (все слова, которые меньше слова данного узла), затем само слово и, наконец, правое поддерево (все слова, которые больше слова данного узла).

// treeprint: упорядоченная печать дерева p

void treeprint (struct tnode * p)

{if (p!=NULL) //в дереве имеется хотя бы один узел

{treeprint ( p->left);

printf ("%4d%s\n", p->count, p->word);

treeprint (p->right);

}

}

Просмотр таблиц

Для иллюстрации новых аспектов применения структур, приведем ядро пакета программ, осуществляющих вставку элементов в таблицы и их поиск внутри таблиц. Этот пакет - типичный набор программ, с помощью которых работают с таблицами имен в любом макропроцессоре или компиляторе. Рассмотрим, например, инструкцию #define. Когда встречается строка вида

#define IN 1

имя IN и замещающий его текст 1 должны запоминаться в таблице. Если затем это имя IN встретится в инструкции, например, в state=IN; оно должно быть заменено на единицу.

Существуют две программы, манипулирующие с именами и замещающими их текстами. Это install (s,t), которая записывает имя s и замещающий его текст t в таблицу (s и t - стринги), и lookup(s), осуществляющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, либо NULL - если s в таблице не оказалось.

Алгоритм основан на "хэшировании" (функции расстановки): поступающее имя свертывается в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного ссылками списка блоков, описывающих имена с данным хэш-кодом. Если элемент массива содержит NULL, это значит, что среди имен не встретилось ни одного с соответствующим хэш-кодом.

Блок в списке - это структура, содержащая указатели на имя, на замещающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка.

struct nlist\\ элемент таблицы

{struct nlist * next;\\ указатель на следующий блок списка

char * name;\\ определяемое имя

char * defn;\\ замещающий текст

};

А вот как записывается определение массива указателей:

#define HASHSIZE 101

static struct nlist *hashtab[HASHSIZE];\\ таблица указателей

\\ hash: получает хэш-код по стрингу s

unsigned hash (char * s)

{unsigned hashval;

for (hashval=0; *s!='\0'; s++)

hashval = *s+31*hashval;

return hashval %HASHSIZE;

}

\\ lookup: поиск элемента с s

struct nlist * lookup (char * s)

{struct nlist *np;

for (np = hashtab [hash(s)]; np!=NULL; np=np->next)

if (strcmp (s,np->name)= =0)

return np;\\ нашли вставляемый стринг

return NULL;\\ не нашли

}

Функция install обращается к lookup, чтобы определить, имеется ли в наличии вставляемый стринг. Если это так, то старое определение будет заменено новым. В противном случае будет образован новый элемент.

struct nlist * lookup (char *);

char * strdup (char *);

\\ install: заносит (name, defn) в таблицу

struct nlist * install ( char * name, char * defn)

{struct nlist * np;

unsigned hashval;

if (( np=(lookup (name))= =NULL) \\ не найден

{np =(struct nlist*) malloc(sizeof(*np));

if (np = =NULL || (np -> name =strdup(name))= =NULL)

return NULL;

hashval = hash (name);

np -> next = hashtab [hashval];

hashtab [hashval] = np;

}

else\\ уже имеется

free ((void *) np-> defn);\\ освобождаем прежний defn

if (( np -> defn = strdup (defn)) = =NULL)

return NULL;

return np;

}

Основная литература - 1[125-142], 2[406-436].

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

1. Дайте определение структуры и приведите аналог этого типа в языке Паскаль.

2. Что будет являться множеством значений данного типа?

3. Какие операции допустимы над структурами?

4. Почему допускается совпадение имен членов разных структур, а также совпадение имен тегов, членов и структурных объектов в одной декларации?

5. Учитывая возможность вложения структур приведите декларацию прямоугольника с использованием структуры point.

6. Перечислите единственно возможные операции над структурами.

7. Каким образом можно выполнить динамическую инициализацию любой структуры, любо формировать структурные аргументы для той или иной функции?

8. Каким образом передаются структурные параметры в функцию?

9. Объясните результат выполнения операций

*p->strи*p->str++,

где str - указатель на стринг из декларации структуры, приведенной в лекции.

Что произойдет после следующих операций:

(*p -> str ) + +, *p + + -> str.

10. Что возвращает результатом функция binsearch?

11. Каков механизм передачи параметров в функцию binsearch?

12. Почему вычисление положения среднего элемента с помощью формулы

mid = (low + high)/2 не верно, и каким образом правильно вычислить?

13. Если структура содержит разнотипные члены, то размер структуры будет равен сумме размеров ее членов?

14. Если функция возвращает значение сложного вида, то каким образом лучше представить формат программы?

Лекция 12. Доступ к файлам

Во всех предыдущих примерах мы имели дело со стандартным вводом и стандартным выводом, которые для программы автоматически предопределены операционной системой конкретной машины.

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

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

Этот указатель, называемый указателем файла, ссылается на структуру, содержащую информацию о файле (адрес буфера, положение текущей литеры в буфере, открыт файл для чтения или на запись, были ли ошибки при работе с файлом и встретился ли конец файла). Пользователю не надо знать подробности, поскольку определения, полученные из <stdio.h>, включают описание такой структуры, называемой FILE. Единственное, что требуется для определения указателя файла, - это задать декларацию вида:

FILE * fp;

FILE * fopen(char*name, char* mode);

Из этой записи следует, что fp есть указатель на FILE, а fopen возвращает указатель на FILE. Необходимо заметить, что FILE есть имя типа, а не тег структуры.

Обращение к fopen в программе может выглядеть в программе следующим образом:

fp= fopen (name, mode);

Первый аргумент - стринг, содержит имя файла, второй - несет информацию о режиме.

Это тоже стринг: в нем указывается, каким образом пользователь намерен использовать файл.

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

Существует несколько способов чтения из файлов и записи в файл. Самый простой это воспользоваться функциями getc и putc. Функция

int getc (FILE*fp)

возвращает следующую литеру из потока, на который ссылаются при помощи *fp; в случае исчерпания файла или ошибки функция возвращает EOF.

Функция

int putc ( intc, FILE*fp)

записывает литеру с в файл fp и возвращает записанную литеру или EOF, в случае ошибки.

При запуске Си - программы операционная системы всегда открывает три файла и обеспечивает три файловые ссылки на них. Этими файлами являются: стандартный ввод, стандартный вывод, и стандартный файл ошибок; соответствующие им указатели называются stdin,stdout и stderr; они описаны в < stdio.h>.

Форматный ввод-вывод файлов можно построить на функциях fscanf и fprintf. Они идентичны scanf и printf с той лишь разницей, что первым их аргументом является указатель на файл.

int fscanf( FILE*fp, char * format,…)

int fprintf( FILE*fp, char * format,…)

В качестве примера, рассмотрим программу конкатенации файлов. Если в командной строке присутствуют аргументы, они рассматриваются как имена файлов для конкатенации, если же аргументов нет, то обработке подвергается стандартный ввод.

# include <stdio.h>

main (int argc,char*argv[])

{FILE *fp;

void filecopy ( FILE*,FILE*);

if (argc= = 1) // нет аргументов, копируется стандартный ввод

filecopy (stdin, stdout);

else

while ( - -argc >0)

if (( fp = fopen( * + + argv, "r"))= = NULL)

{ printf ("cat : не могу открыть файл % s\n",*argv);

return 1;

}

else

{filecopy ( fp,stdout);

fclose(fp);

}

return 0;

}

//filecopy : копирует файл ifp в файл ofp

void filecopy (FILE*ifp, FILE*ofp)

{int c;

while (( c=getc ( ifp))!=EOF)

putc (c,ofp);

}

Файловые указатели stdio и stdout представляют собой объекты типа FILE*. Это константы, а не переменные, следовательно им нельзя ничего присваивать.

Функция int fclose (FILE*fp) - обратная по отношению к fopen; она разрывает связь между файловым указателем и внешним именем.

Основная литература - 1[155-159], 2[437-458]

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

1. Какую информацию содержит структура, на которую ссылается указатель файла?

2. Что собой представляет FILE?

3. Перечислите возможные режимы и их обозначения использования файла.

4. Какие три файла открывает операционная система при запуске Си- программы? Их назначения.

5. Укажите причины применения fclose к открытым файлам, в том числе и к файлу вывода.

Управление ошибками. Ввод-вывод строк.

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

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

Перепишем программу конкатенации так, чтобы сообщения об ошибках отправлялись в stderr.

# include < stdio.h>

// конкатенация файлов

main ( int argc, char * argv[])

{FILE * fp;

void filecopy ( FILE*, FILE*);

char * prog = argv[0]; // имя программы

if (argc= =1) // нет аргументов; копируется стандартный ввод

filecopy ( stdin, stdout);

else

while ( - - argc > 0)

if ((fp=fopen (* + + argv,"r")) = = NULL)

{ fprintf ( stderr, "%s: не могу открыть файл %s\n", prog,* argv);

exit(1) ;

}

else { filecopy ( fp, stdout);

fclose( fp);

}

if ( ferror ( stdout))

{ fprintf ( stderr, ":%s: ошибка записи в stdout\n",prog);

exit (2);

}

exit (0);

}

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

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

Чтобы опустошить буфера, накопившие информацию для всех открытых файлов вывода, функция exit вызывает fclose.

Инструкция return (выражение) в главной программе эквивалентна обращению к функции exit (выражение).

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

Функция

int ferror ( FILE*fp)

выдает ненулевое значение, если в файле fp была обнаружена ошибка.

Функция

int feof (FILE*)

возвращает ненулевое значение, если встретился конец указанного в аргументе файла.

Лекция 13. Объединения

Объединение - это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.

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

union u_tag

{int ival;

float fval;

char * sval;

}r;

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

Синтаксис доступа к членам объединения следующий:

имя_объединения.член

или

указатель_на_объединение -> член

т.е. в точности такой, как в структурах.

Объединения могут входить в структуры и массивы и наоборот. Например, в массиве структур

struct

{char *name;

int flags;

union

{int ival;

float fval;

char * sval;

} r;

}symtab [NSYM];

на ival ссылаются следующим образом

symtab[i].r.ival

а к первой литере стринга sval можно обратиться любым из следующих двух способов:

* symtab [i].r.sval

symtab [i].r.sval[o].

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

Инициализировать объединение можно только значением, имеющим тип его первого члена.

Интерфейс ввода-вывода.

Стандартный ввод-вывод. Форматный вывод.

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

Библиотечные функции ввода-вывода точно определяются стандартом ANSI, так что они совместимы на любых установках, где поддерживается Си. Эти функции реализуют простую модель текстового ввода-вывода. Текстовый поток состоит из последовательности строк; каждая строка заканчивается литерой новая строка.

Простейший механизм ввода - чтение одной литеры функцией getchar:

int getchar (void)

которая возвращает следующую литеру потока или, если обнаружен конец файла, EOF. Обычно значение EOF = -1.

Функция

int putchar (int)

используется для вывода: putchar (c) отправляем литеру с в стандартной вывод (экран). Функция putchar в качестве результата возвращает посланную литеру или, в случае ошибки , EOF.

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

В качестве примера рассмотрим программу lower, переводящую свой ввод на нижний регистр;

#include<stdio.h>

#include<ctype.h>

main( )

{int c;

while (( c= getchar( )) ! = EOF)

putchar(tolower(c));

return 0;

}

Функция tolower определена в <ctype.h>. Она переводит буквы верхнего регистра в буквы нижнего, а остальные литеры возвращает без изменений.

Форматный вывод.

Функция printf переводит внутренние значения в текст.

int printf ( char*format, arg1, arg2,…)

Функция printf преобразует, форматирует и печатает свои аргументы в стандартном выводе под управлением формата (форматного стринга). Возвращает она количество напечатанных литер.

Форматный стринг содержит два вида объектов: обычные литеры, которые впрямую копируются в выходной поток, и спецификации преобразования, каждая из которых вызывает преобразование и печать очередного аргумента printf. Любая спецификация преобразования начинается знаком % и заканчивается литерой - спецификатором. Между % и литерой- спецификатором могут быть расположены такие элементы, как знак минус, число, точка, буква. Если за % не помещена литера - спецификатор, поведение функции printf будет не определено.

Функция sprintf выполняет те же преобразования, что и printf , но вывод запоминает в стринге

int sprintf ( char*string, char*format, arg1,arg2,…)

Списки аргументов переменной длины. Форматный ввод

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

Декларация стандартной функции printf выглядит так:

int printf (char*fmt,…),

где многоточие означает, что число и типы аргументов могут изменяться. Наша функция minpritnf декларируется как

void minprintf ( char * fmt,…)

поскольку она не будет выдавать число литер.

Вся сложность в том, каким образом minprintf будет продвигаться вдоль списка аргументом - ведь у этого списка нет даже имени. Стандартный головной файл <stdarg.h>содержит набор макроопределений (va_start, va_arg, va_end), которые определяют, как шагать по списку аргументов.

Перечисленные средства образуют основу упрощенной версии printf.

#include <stdarg.h>

// minprintf: версия printf с переменным числом аргументов

void minprintf ( char * fmt,…)

{va_list ap; //указатель на очередной безымянный аргумент, va_list - тип указателя

char *p, *sval;

int ival;

double dval;

va_start(ap,fmt); // макрос инициализирует ap первым безымянным аргументом

for(p=fmt; *p; p+ +)

{ if (*p!='%')

{ putchar (*p);

continue;

}

switch (*+ +p)

{ case `d': ival= va_arg( ap,int); // макрос выдает очередной аргумент,

// а ар передвигает на следующий

printf (" %d", ival);

break;

case`f':

dval=va_arg(ap,double); printf("%f",dval); break;

case`s': for ( sval=va_arg( ap,char*);* sval; sval+ +)

putchar( * sval) ;

break;

default: putchar (*p);

break;

}

} va_end(ap); // очистка, когда все сделано

} 13.5 Форматный ввод (scanf)

Декларация функции ввода имеет следующий вид:

int scanf (char * format, …);

Функция scanf читает литеры из стандартного входного потока, интерпретирует их согласно спецификациям стринга format и рассылает результаты в свои остальные аргументы, каждый из которых должен быть указателем. В качестве результата scanf возвращает количество успешно введенных элементов данных.

Существует также функция sscanf, которая читает из стринга ( а не из стандартного ввода ).

int sscanf ( char*string, char*format, arg1,arg2,…)

Функция sscanf просматривает string согласно формату format и рассылает полученные значения в arg1, arg2,и т.д. Последние должны быть указателями.

Для управления преобразованиями ввода формат обычно содержит такие спецификации, как: пробелы, обычные литеры, спецификации преобразования, знак *, число.

Предположим, что нам нужно прочитать строки ввода, содержащие данные вида:

1 сен 2004

Обращение к scanf выглядит следующим образом:

int day, year;

char monthname [20];

scanf ( "%d%s%d", &day, monthname, &year);

Знак & перед monthname не нужен, так как имя массива есть указатель, что соответствует типу аргументов функции.

Ввод-вывод строк.

В стандартной библиотеке есть функция ввода fgets

char * fgets (char*line, int maxline, FILE*fp),

которая читает следующую строку ввода (включая и литеру новая строка) из файла fp в массив литер line, причем она может прочитать не более maxline -1 литер. Переписанная строка дополняется литерой `\0'.

Функция вывода fputs пишет стринг (который может и не заканчиваться литерой новая строка) в файл.

int fputs ( char*line, FILE*fp).

Отличие библиотечных функций gets и puts от fgets и fputs в том, что они оперируют только стандартными файлами stdin и stdоut , и кроме того, gets выбрасывает последнюю литеру `\n', а puts ее добавляет.

Директивы препроцессора. Именованные константы и макроопределения.

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

Наиболее часто используются такие возможности языка Си как: #include, включающая файл во время компиляции, и # define, заменяющая одни текстовые цепочки на другие.

Средство # include позволяет, в частности, легко манипулировать наборами #define и деклараций. Любая строка вида

#include "имя-файла" или

# include <имя -файла>

заменяется содержимым файла с именем имя -файла. Если имя-файла заключено в двойные кавычки, то, как правило, файл ищется среди исходных файлов программы; если такового не оказалось или имя - файла заключено в угловые скобки <и >, то поиск осуществляется в системных библиотеках. Включаемый файл сам может содержать в себе строки #include.

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

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

# define имя замещающий-текст

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

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

#define max (A,B) ((A)>(B) ? (A):(B))

Обращения к max будут вызывать только текстовую замену.

Каждый формальный параметр будет заменяться соответствующим аргументом.

Так строка

x=max (p+q,r+s); будет заменена на строку

x=((p+q) > (r+s) ? ( p+q) : ( r+s));

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

Имена можно "скрыть" от препроцессора с помощью #undef.

#undef getchar

int getchar ( void) {…}

Как правило, это делается, чтобы макроопределение "перекрыть" настоящей функцией с тем же именем. Директива #undef обычно используется в паре с директивой #define.

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

Условная компиляция

Условная компиляция обеспечивается в языке Си набором команд условных инструкций, которые по существу управляют не компиляцией, а препроцессорной обработкой:

#if константное выражение // проверяемое условие

#ifdef идентификатор

# ifndef идентификатор

#else

#endif

#elif

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

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

#if … текст1

#else текст2