Дисциплина “Информатика” Язык программирования Си (стр. 7 )

#ifdef имя (если имя определено, то истина)

.

.

.

#else

.

.

.

#endif

#ifndef имя (если имя не определено)

.

.

.

#else

.

.

.

#endif

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

#ifndef COLORS

enum COLORS {BLACK, ...};

#endif

22.  Условное выражение.

Эта конструкция языка C в некоторых случаях позволяет заменить оператор if и сократить запись программы.

условное выр = выр0 "?" выр1 ":" выр2

Значение условного выражения равно выр1, если выр0 не равно 0 и выр2 впротивном случае.

Пример:

a = b>c? b:c; тоже самое, что

if (b>c) a=b; else a = c;

С помощью условного выражения можно, например, определить макросы max и min:

#define max(x, y) ((x)>(y) ? (x):(y))

#define min(x, y) ((x)<(y) ? (x):(y))

При этом макросы max и min будут работать для любых типов арифметических данных.

Например:

a = max(b, c);

22.1.  Приоритеты и направления операций.

---

| | |

|------|-----|

| () вызов функции | |

| [] выделение элемента массива | |

| . выделение элементов структуры или объеди - | -> |

| нения | |

| -> выделения элементов структуры или объеди- | |

| нения | |

|------|-----|

| ! логическое отрицание | |

| ~ побитовое отрицание | |

| - изменение знака | |

| ++ увеличение на единицу | |

| -- уменьшение на единицу | <- |

| & определение адреса | |

| * обращение по адресу | |

| (тип) преобразование типа | |

| sizeof определение размера в байтах | |

|------|-----|

| * умножение | |

| / деление | -> |

| % остаток от деления | |

|------|-----|

| + сложение | |

| - вычитание | -> |

|------|-----|

| << сдвиг влево | |

| >> сдвиг вправо | -> |

|------|-----|

| < меньше | |

| <= меньше или равно | |

| > больше | |

| >= больше или равно | |

|------|-----|

| == равно | |

| != не равно | -> |

|------|-----|

| & побитовое и | -> |

|------|-----|

| ^ побитовое исключающее или | -> |

|------|-----|

| | побитовое или | -> |

|------|-----|

| && логическое и | -> |

|------|-----|

| || логическое или | -> |

|------|-----|

| ? : условная операция | -> |

|------|-----|

| = присваивание | |

| *= /= %= += -= | <- |

| <<= >>= &= ^= |= | |

|------|-----|

| , операция запятая | -> |

|__________________________________________________|_____|

23.  Динамические данные.

23.1.  Линейные списки.

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

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

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

...................

: : : : : : : : : : : : : :NULL:

...................

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

Рассмотрим, например, как можно было бы организовать хранение информации о товарах для программы "магазин".

typedef struct _GOODS{

char name[21];

int number;

float price;

struct _GOODS *next;

} GOODS;

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

..........

TOP : : : : : : : : : : :NULL:

..........

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

GOODS *new_GOODS ( void)

{

GOODS *p;

p = (GOODS* ) malloc( sizeof(GOODS) );

if (p==NULL) {printf("Недостаточно памяти\n");

exit(1);}

return p;

}

GOODS *in_goods( void )

{

GOODS *top, *q;

printf("Введите характеристики товаров в виде:\n" \

"наименование количество цена\n" \

"-------окончание ввода \"end\"-------\n");

top = NULL;

while (1)

{

q = new_GOODS(); if( !in_goods1(q) ) { free(q);

return top; }

q->next = top; top = q;

}

}

Обращение к этой программе будет выглядеть так:

top = in_goods();

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

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

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

void out_goods( GOODS *top)

{

printf("*-----*\n");

printf("| Наименование | Кол-во | Цена |\n");

printf("||||\n");

while( top!= NULL )

{

printf( "| %20s | %10.2f |\n",

top->name, top->number, top->price );

top = top->next;

}

printf("*-----*\n");

}

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

void main( void )

{

GOODS *top;

top = in_goods();

out_goods ( top );

}

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

Рассмотрим вспомогательную задачу: необходимо вставить запись, на которую указывает указатель g в список за записью, на которую указывает указатель p.

g .........

: :. :

......|..

2 ^ | 1

| V

TOP..................

: : : : : p : : : : : : : : :NULL:

....................

p

g->next = p->next; 1

p->next = g; 2

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

GOODS *in_goods( void )

{

GOODS *top, *q, *p;

printf("Введите характеристики товаров в виде:\n" \

"наименование количество цена\n" \

"-------окончание ввода \"end\"-------\n");

/* Получение списка из двух элементов */

top = NULL;

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

q->next = NULL; top = q;

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

if(q->price < top->price ) { q->next = top; top = q; }

else { q->next = NULL; top->next = q; }

/* Получение списка из остальных элементов */

while( 1 )

{

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

if(q->price < top->price )

{ q->next = top; top = q; }

else

{

p = top;

while(p->next && (q->price > p->next->price)) p=p->next;

q->next = p->next; p->next = q;

}

}

}

/* Пример использования списка # 1 */

#include <stdio. h>

#include <stdlib. h>

#include <string. h>

#include <alloc. h>

#include <math. h>

typedef struct _GOODS{

char name[21];

int number;

float price;

struct _GOODS *next;

} GOODS;

GOODS in_goods ( void );

GOODS new_goods ( void );

int in_goods1 ( GOODS *g );

void out_goods (GOODS *top );

void main( void )

{

GOODS *top;

top = in_goods();

out_goods ( top );

{ float f=0; sin(f); }

}

GOODS *new_GOODS ( void )

{

GOODS *p;

p = (GOODS*) malloc( sizeof(GOODS) );

if (p==NULL) {printf("Недостаточно памяти\n");

exit(1);}

return p;

}

GOODS *in_goods( void )

{

GOODS *top, *q;

printf("Введите характеристики товаров в виде:\n" \

"наименование количество цена\n" \

"-------окончание ввода \"end\"-------\n");

top = NULL;

while (1)

{

q = new_GOODS(); if( !in_goods1(q) ) { free(q);

return top; }

q->next = top; top = q;

}

}

int in_goods1( GOODS *g )

{

scanf( "%s", q->name );

if ( strcmp(g->name, "end")== ) return 0;

scanf( "%d%f", &g->number, &g->price );

return 1;

}

void out_goods( GOODS *top)

{

printf("*-----*\n");

printf("| Наименование | Кол-во | Цена |\n");

printf("||||\n");

while( top!= NULL )

{

printf( "| %20s | %10.2f |\n",

top->name, top->number, top->price );

top = top->next;

}

printf("*-----*\n");

}

/* Пример использования списка с сортировкой */

#include <stdio. h>

#include <stdlib. h>

#include <string. h>

#include <alloc. h>

#include <math. h>

typedef struct _GOODS{

char name[21];

int number;

float price;

struct _GOODS *next;

} GOODS;

GOODS in_goods ( void );

GOODS new_goods ( void );

int in_goods1 ( GOODS *g );

void out_goods (GOODS *top );

void main( void )

{

GOODS *top;

top = in_goods();

out_goods ( top );

{ float f=0; sin(f); }

}

GOODS *new_GOODS ( void )

{

GOODS *p;

p = (GOODS*) malloc( sizeof(GOODS) );

if (p==NULL) {printf("Недостаточно памяти\n");

exit(1);}

return p;

}

GOODS *in_goods( void )

{

GOODS *top, *q, *p;

printf("Введите характеристики товаров в виде:\n" \

"наименование количество цена\n" \

"-------окончание ввода \"end\"-------\n");

/* Получение списка из двух элементов */

top = NULL;

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

q->next = NULL; top = q;

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

if(q->price < top->price ) { q->next = top; top = q; }

else { q->next = NULL; top->next = q; }

/* Получение списка из остальных элементов */

while( 1 )

{

q=new_GOODS(); if(!in_goods1(q)) {free(q); return top;}

if(q->price < top->price )

{ q->next = top; top = q; }

else

{

p = top;

while(p->next && (q->price > p->next->price)) p=p->next;

q->next = p->next; p->next = q;

}

}

}

int in_goods1( GOODS *g )

{

scanf( "%s", q->name );

if ( strcmp(g->name, "end")== ) return 0;

scanf( "%d%f", &g->number, &g->price );

return 1;

}

void out_goods( GOODS *top)

{

printf("*-----*\n");

printf("| Наименование | Кол-во | Цена |\n");

printf("||||\n");

while( top!= NULL )

{

printf( "| %20s | %10.2f |\n",

top->name, top->number, top->price );

top = top->next;

}

printf("*-----*\n");

}

23.2.  Организация данных в виде стека.

Понятие стека ("магазина"): первый пришел, последний ушел.

LIFO (LAST IN FIRST OUT)

Описание стека как списка:

typedef struct _LIST {

info_t info; /* тип данных для информации */

struct _LIST *next;

} LIST;

В вызывающей функции стек должен быть описан так:

LIST *head = NULL; /* голова списка */

Действия со стеком определяется несколькими функциями:

1.  Помещение элемента в стек (в голову списка)

void add_head (LIST *head, info_t a)

{

LIST *t;

if (t=(LIST*) malloc (sizeof (LIST)))

{

t->info = a; /* 1 */

t->next = (*head); /* 2 */

(*head) = t; /* 3 */

}

}

t.......... 2

: 1 a : :

..........

..............

3 : : : : : : : :NULL:

..............

head 3

2.  Извлечение из стека (из головы списка)

info_t get_head (LIST *head)

{

LIST *t; info_t a;

if ( *head)

{

a = (*head)->info; /* 1 */

t = (*head); /* 2 */

(*head) = (*head)->next; /* 3 */

free (t);

}

return a;

}

t 2

...............

: 1 a : : : : : : :NULL:

...............

3

head 3

23.3.  Организация данных в виде очереди.

Понятие очереди: первый пришел, первый ушел.

FIFO (FIRST IN FIRST OUT).

Описание очереди: такое же, что и стека, но надо хранить и начало и хвост очереди.

...............

head : : : : : : : :NULL:

...............

tail

Тогда в вызывающей программе очередь описывается так:

LIST *head = NULL, *tail = NULL;

Помещение элемента в очередь (в хвост списка):

1-ый элемент: head

3 ..........

: :NULL:

5 ..........

tail t

Остальные: .............

: : : : : : : : :

.............

head 5 4

tail ...........

5 :1 a:NULL:

...........

t 2

void add_tail (LIST*head, LIST*tail, info_t a)

{

LIST*t;

if (t = (LIST*) malloc (sizeof (LIST)))

{

t->info = a; /* 1 */

t->next = NULL; /* 2 */

if (*head) == NULL) (*head) = t; /* 3 */

else (*tail)->next = t;/* 4 */

(*tail) = t; /* 5 */

}

}

23.4.  Организация данных в виде деревьев.

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

root.

. .

.

root

.....................

: : : :

.....................

...............

: : : : : : : :

...............

..............

: : :0: : :0:0: : :0:0: : :0:0:

..............

..............

: :0 :0 :

..............

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

Описать это дерево можно следующим образом:

typedef struct _NODE {

info_t info;

struct _NODE*left;

struct _NODE*right;

} NODE;

.

.

.

NODE *tree = NULL;

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

24.  Библиотека ввода-вывода языка C.

Прототипы функций описаны в файле <stdio. h>. Основные идеи:

1.  В C отсутствуют встроенные средства ввода-вывода. Весь ввод-вывод осуществляется через функции, находящеся в библиотеке и легко замещаемые.

2.  Каждый файл рассматривается как непрерывный поток байт (stream). Никакой внутренней структуры файла не поддерживается.

3.  Не делается никаких различий между файлами на дисках и на других внешних устройствах.

24.1.  Открытие потока.

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

FILE *fopen (const char *filename, const char *mode);

где, filename - строка символов, содержащая имя файла (полное или простое), записанное по правилам DOS;

mode - режим работы файла, тоже строка символов;

mode = "r" - открыть существующий файл для чтения;

"w" - создать файл для записи, информация из существующего файла теряется;

"a" - открытие для записи в конец существующего файла или создание для записи, если файла нет;

"r+" - открытие существующего файла для чтения и записи;

"w+" - создание нового файла для чтения и записи;

"a+" - откратие или создание для обновления в конец;

24.2.  Закрытие потока.

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

1.  если программа обрабатывает большое количество файлов, то в конце концов может не хватить на все системных ресурсов;

2.  незакрытый файл может в случае сбоя пропасть.

Файл закрывается функцией:

int fclose (FILE *stream);

где, stream - указатель потока.

Функция возвращает 0 в случае успеха и EOF - если нет. EOF - (End Of File) - специальная константа из <stdio. h>.

Функция fcloseall закрывает все потоки:

int fcloseall (void);

В случае успеха функция возвратит количество закрытых потоков, иначе - EOF.

Если программист забыл закрыть какие-либо потоки, то все равно они будут закрыты системой MS DOS по завершению работы программы.

Типичный пример работы с файлом:

<stdio. h>

.

.

.

void main (void)

{

FILE *my_file; static char *fn = "d:\\USER\\f. dat";

.

.

.

if ((my_file = fopen (fn, "r")) == NULL)

{ printf ("Не могу открыть файл %s\n", fn);

return; }

.

.

.

fclose (my_file);

}

24.3.  Предопределенные указатели потоков.

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

stdin - стандартный поток ввода;

stdout - стандартный поток вывода;

stdprn - стандартный поток вывода на печать;

stdaux - стандартный дополнительный поток;

stderr - стандартный вывод сообщений об ошибке.

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

Имеется целый ряд специальных функций работы со стандартными потоками ввода-вывода (в основном stdin и stdout). Мы их частично рассматривали (например, printf).

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

FILE *freopen (const char *fn, const char *mode, FILE *stream);

stream - указатель существующего потока, в том числе стандартного.

Функция возвращает stream в случае успеха, иначе - NULL.

Пример:

if (fopen ("d:\\a. std", "w", stdout) == NULL)

{ ... обработка ошибки открытия... }

/* переназначение стандартного вывода на диск */

if (freopen ("CON", "w", stdout) == NULL)

{ ... обработка ошибки переназначения... }

/* возврат стандартного вывода на консоль */

24.4.  Функции ввода-вывода.

--

Opens a stream

FILE *fopen(const char *filename, const char *mode);

Returns a pointer to the newly open stream if successful;

otherwise it returns NULL.

--