Основы программирования

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

#include <stdio.h>

#include <string.h>

#include <math.h>

typedef struct {

char name[21];

int number;

float price;

} GOODS;

void in_goods ( GOODS gs[], int *n );

int in_goods1 ( GOODS *g );

void out_goods ( GOODS gs[], int n );

void sort_goods ( GOODS gs[], int n);

void main( void )

{

int n; GOODS goods[100];

in_goods ( goods, &n );

sort_goods ( goods, n );

out_goods ( goods, n );

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

}

void in_goods( GOODS gs[], int *n)

{

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

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

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

*n=0;

while( in_goods1(&gs[*n]) ) (*n)++;

}

int in_goods1( GOODS *g )

{

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

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

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

return 1;

}

void out_goods( GOODS gs[], int n )

{

int i;

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

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

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

for( i=0; i<n; i++)

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

gs[i].name, gs[i].number, gs[i].price );

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

}

void sort_goods( GOODS gs[], int n )

{

int i, j, GOODS r;

for (i=0; i<n-1; i++)

for(j=i+1; j<n; j++)

if( gs[i].price )

{ r=gs[j]; gs[j]=gs[i]; gs[i]=r; }

}



15. Объединения

Объединяются ключевым словом union. Способы описания такие же, как и в случае структур, только вместо слова struct используется слово union.

union {int a; long b;} pr;

Для переменной pr выделяется память, достаточная для хранения самого длинного элемента объединения, т. е. в нашем примере - 4 байта.

Если использовать pr.a, то выделенная память будет использоваться как int, в случае pr.b как long. Однако, участок памяти один и тот же. Поэтому одновременно существовать pr.a и pr.b не могут. Ответственность за некорректное использование памяти лежит на программисте. Объединения используются для экономии памяти:

union {int bc[100]; double kk[20];} cc;

На все отводится 200 байт.

int bc[100] 200 байт

______________________________

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

double kk[20] (160 байт)

Одновременно работать с массивом cc.bc и cc.kk нельзя.

Объединения нельзя инициализировать.



16 Дополнительные сведения о препроцессоре языка C

Препроцессор обрабатывает текст программы перед компиляцией.

1. Включение файлов (рассмотрено ранее):

#include <conio.h> - файл из специального каталога;

#include "d:\\user\\ff.h" - файл ищется по правилам MS DOS.

2. Текстовые подстановки (рассматривалось ранее):

#define N 21

#define ABC (a*b*c+\

d*sin(x))

\ - переход на следующую строку.

3. Создание макросов.

#define SQR(x) ((x)*(x))

В результирующую строку подставляется фактическая строка x. Например, если в тексте программы встречается SQR(y), то после макрораскрутки получим ((y)*(y)). Скобки нужны для того, чтобы не получилось недоразумений, например

#define SQR(x) x*x

SQR(y+2); превратится в

y+2*y+2;

Конечно, это не то, что хотелось.

4. Отмена ранее созданного имени:

#undef SQR.

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

#if константное выражение

строки программы

#else

строки программы

#endif

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

Пример:

#define DEBUG 1

#if DEBUG

printf("%d", x);

#endif

Можно проверить наличие или отсутствие какого-либо имени:

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

#else

#endif

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

#else

#endif

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

#ifndef COLORS

enum COLORS {BLACK, ...};

#endif



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

Эта конструкция языка 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);



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

18.1 Линейные списки

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

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

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

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

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

typedef struct _GOODS{

char name[21];

int number;

float price;

struct _GOODS *next;

} GOODS;

Очевидно, программа должна иметь переменную - указатель на первый элемент списка. Последний элемент списка отличается тем, что в поле next имеет константу 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.

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

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");

}

18.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 */

}

}

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

head 3

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

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

FIFO (FIRST IN FIRST OUT).

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

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

LIST *head = NULL, *tail = NULL;

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

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

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

typedef struct _NODE {

info_t info;

struct _NODE*left;

struct _NODE*right;

} NODE;

NODE *tree = NULL;

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



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

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

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

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

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

19.1 Открытие потока

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

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

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

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

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

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

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

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

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

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

19.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);

}

19.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)

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

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

19.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.

Размещено на Allbest.ru