двумерный динамический массив.

// объявление двумерного динамического массива на 10 элементов:

float **ptrarray = new float* [2]; // две строки в массиве

for (int count = 0; count < 2; count++)

ptrarray[count] = new float [5]; // и пять столбцов

// где ptrarray – массив указателей на выделенный участок памяти под массив вещественных чисел типа float

Сначала объявляется указатель второго порядка float **ptrarray, который ссылается на массив указателей float* [2],где размер массива равен двум.После чего в циклеforкаждой строке массива объявленного встроке 2выделяется память под пять элементов. В результате получается двумерный динамический массив ptrarray[2][5].Рассмотрим пример высвобождения памяти отводимой под двумерный динамический массив.

// высвобождение памяти отводимой под двумерный динамический массив:

for (int count = 0; count < 2; count++)

delete [] ptrarray[count];

// где 2 – количество строк в массиве

Пример:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
void main()
{

int *a; // указатель на массив

int i, j, n, m;

system("chcp 1251");

system("cls");

printf("Введите количество строк: ");

scanf("%d", &n);

printf("Введите количество столбцов: ");

scanf("%d", &m);

// Выделение памяти

a = (int*) malloc(n*m*sizeof(int));

// Ввод элементов массива

for(i=0; i<n; i++) // цикл по строкам

{

for(j=0; j<m; j++) // цикл по столбцам

{

printf("a[%d][%d] = ", i, j);

scanf("%d", (a+i*m+j));

}

}

// Вывод элементов массива

for(i=0; i<n; i++) // цикл по строкам

{

for(j=0; j<m; j++) // цикл по столбцам

{

printf("%5d ", *(a+i*m+j)); // 5 знакомест под элемент массива

}

printf("\n");

}

free(a);

getchar(); getchar();
}

Результат выполнения

Введите количество строк: 3

Введите количество столбцов: 4

a[0][0]=1

a[0][1]=2

a[0][2]=3

a[0][3]=4

a[1][0]=5

a[1][1]=6

a[1][2]=7

a[1][3]=8

a[2][0]=9

a[2][1]=10

a[2][2]=11

a[2][3]=12

1 2 3 4

5 6 7 8

9 10 11 12

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

Функция malloc() – возвращает указатель на первый байт области памяти размером size, которая была выделена из динамически распределяемой области памяти. Если в динамической области памяти не хватает памяти, то возвращается нулевой указатель.

Пример:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
void main()
{

int **a; // указатель на указатель на строку

int i, j, n, m;

system("chcp 1251");

system("cls");

printf("Введите количество строк: ");

scanf("%d", &n);

printf("Введите количество столбцов: ");

scanf("%d", &m);

// Выделение памяти под указатели на строки

a = (int**)malloc(n*sizeof(int*));

// Ввод элементов массива

for(i=0; i<n; i++) // цикл по строкам

{

// Выделение памяти под хранение строк

a[i] = (int*)malloc(m*sizeof(int));

for(j=0; j<m; j++) // цикл по столбцам

{

printf("a[%d][%d] = ", i, j);

scanf("%d", &a[i][j]);

}

}

// Вывод элементов массива

for(i=0; i<n; i++) // цикл по строкам

{

for(j=0; j<m; j++) // цикл по столбцам

{

printf("%5d ", a[i][j]); // 5 знакомест под элемент массива

}

printf("\n");

free(a[i]); // освобождение памяти под строку

}

free(a);

getchar(); getchar();
}

Результат выполнения программы аналогичен предыдущему случаю.

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

Указатели.

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

По типу данных в СИ указатели делятся на:

Типизированный указатель – указатель, содержащий адрес данных определенного типа (системного или пользовательского).

Не типизированный указатель – указатель, содержащий адрес данных неопределенного типа (просто адрес).

 

объявление указателя;

установка указателя;

обращение к значению, расположенному по указателю. Объявление (описание) указателя в языке СИ имеет следующий вид:

тип [near|far] *имя [=значение];

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

•нулевое значение (идентификатор NULL);

•другой указатель;

•адрес переменной (через операцию взятия адреса);

•выражение, представляющее собой арифметику указателей;

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

Пример:

#include <stdio.h>

int main()

{

int var; // обычная целочисленная переменная

int *ptrVar; // целочисленный указатель (ptrVar должен быть типа int, так как он будет ссылаться на переменную типа int)

 

ptrVar = &var; // присвоили указателю адрес ячейки в памяти, где лежит значение переменной var

scanf( "%d", &var ); // в переменную var положили значение, введенное с клавиатуры

printf( "%d\n", *ptrVar ); // вывод значения через указатель

getchar();

}

Результат выполнения: 6 6

Лекция №3.

Функции.

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

Описание функции на языке СИ осуществляется в любом месте программы вне описания других функций и состоит из трех элементов:

1. прототип функции;

2. заголовок функции;

3. тело функции.

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

тип имя(список типов формальных параметров);

Параметры функции – значения, передаваемые в функцию при ее вызове.

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

тип имя(список формальных параметров)

Примеры заголовков функций:

int func(int i, double x, double y)

void func(int ind, char *string)

double func(void)

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

 

Пример:

Реализация функции на СИ для вычисления факториала числа.

double factorial(unsigned);

...

double factorial(unsigned num)

{

double fact = 1.0;

for(unsigned i=1;i<=num;i++)

fact *= (double)i;

return fact;

}

Структуры.

Структура – это сложный тип данных представляющий собой упорядоченное в памяти множество элементов различного типа. Каждый элемент в структуре имеет свое имя и называется полем.

Объявление в СИ структуры имеет вид:

struct [имя типа]

{

поле_1;

поле_2;

...

поле_N;

} [список переменных];

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

Файлы.

Файл – это именованная область данных на каком-либо носителе информации. Типы файлов (относительно языка «СИ»):
текстовые;
бинарные.
Основные операции производимые над файлами:
1.Открытие файлов.
2.Чтение и запись данных.
3.Закрытие файлов.

Дополнительные операции:
1.Навигация по файлу.
2.Обработка ошибок работы с файлами.
3.Удаление и переименование файлов.
4.Описание переменной

Режимы открытия файлов с СИ

 

r	только чтение
w	Только запись. Если файл существовал, то он переписывается.
a	Добавление: открытие файла для записи в конец, или создание файла.
r+	Открывает файл для обновления (чтение и запись).
w+	Открывает файл для обновления (чтение и запись), переписывая файл, если он существует.
a+	Открывает файл для записи в конец файла или для чтения.

 

Перенаправление потоков
FILE * freopen(const char *filename, const char *mode, FILE *stream);

Функция возвращает:
Указатель на файл – все нормально,
NULL – ошибка переопределения.

 

Закрытие файла
int fclose(FILE *stream);
stream - указатель на открытый файл.

Функция возвращает:
0 – файл успешно закрыт.
1 – произошла ошибка закрытия файла.

Проверка на достижение конца файла
int feof(FILE *stream);
stream - указатель на открытый файл.

Функция возвращает:
0 – если конец файла еще не достигнут.
!0 – достигнут конец файла.

 

Открытие текстовых файлов
Во втором параметре дополнительно указывается символ t (необязательно):
rt, wt, at, rt+, wt+, at+

Чтение из текстового файла

Форматированное чтение
int fscanf(FILE *stream, const char * format, [arg] ...);

Функция возвращает:
>0 – число успешно прочитанных переменных,
0 – ни одна из переменных не была успешно прочитана,
EOF – ошибка или достигнут конец файла.
Чтение строки
char * fgets(char * buffer, int maxlen, FILE *stream);

Функция возвращает:
buffer – все нормально,
NULL – ошибка или достигнут конец файла.
Чтение строки
char * fgets(char * buffer, int maxlen, FILE *stream);

Функция возвращает:
buffer – все нормально,
NULL – ошибка или достигнут конец файла.
Чтение символа
int fgetc(FILE *stream);
Функция возвращает:
код символа – если все нормально,
EOF – если ошибка или достигнут конец файла.
Помещение символа обратно в поток
int ungetc(int c, FILE *stream);
Функция возвращает:
код символа – если все успешно,
EOF – произошла ошибка.

Запись в текстовый файл в СИ

Форматированный вывод
int fprintf(FILE *stream, const char *format, [arg] ...);
Функция возвращает:
число записанных символов – если все нормально,
отрицательное значение – если ошибка.
Запись строки
int fputs(const char *string, FILE *stream);
Функция возвращает:
число записанных символов – все нормально,
EOF – произошла ошибка.
Запись символа
int fputc(int c, FILE *stream);
Функция возвращает:
код записанного символа – все нормально,
EOF – произошла ошибка.
Открытие бинарных файлов
Во втором параметре дополнительно указывается символ b (обязательно):rb, wb, ab, rb+, wb+, ab+
Чтение из бинарных файлов
size_t fread(void *buffer, size_t size, size_t num,FILE *stream);
Функция возвращает количество прочитанных блоков. Если оно меньше num, то произошла ошибка или достигнут
конец файла.

Запись в бинарный файл
size_t fwrite(const void *buffer, size_t size, size_t num, FILE *stream);
Функция возвращает количество записанных блоков. Если оно меньше num, то произошла ошибка.

Навигация по файлу

Чтение текущего смещения в файле:
long int ftell(FILE *stream);
Изменение текущего смещения в файле:
int fseek(FILE *stream, long int offset, int origin);

SEEK_SET (0) – от начала файла.
SEEK_CUR (1) – от текущей позиции.
SEEK_END (2) – от конца файла.
Функция возвращает:
0 – все нормально,
!0 – произошла ошибка.
Перемещение к началу файла:
void rewind(FILE *stream);
Чтение текущей позиции в файле:
int fgetpos(FILE *stream, fpos_t *pos);
Установка текущей позиции в файле:
int fsetpos(FILE *stream, const fpos_t *pos);
Функции возвращают:
0 – все успешно,
!0 – произошла ошибка.
Структура fpos_t:
typedef struct fpos_t {
long off;
mbstate_t wstate;
} fpos_t;

Получение признака ошибки:
int ferror(FILE *stream);
Функция возвращает ненулевое значение, если возникла ошибка.
Функция сброса ошибки:
void clearerr(FILE *stream);
Функция вывода сообщения об ошибке:
void perror(const char *string);

Буферизация

Функция очистки буфера:
int fflush(FILE *stream);
Функция возвращает:
0 – все нормально.
EOF – произошла ошибка.
Функция управления буфером:
void setbuf(FILE *stream, char * buffer);

Создает буфер размером BUFSIZ. Используется до ввода или вывода в поток.

Временные файлы

Функция создания временного файла:
FILE * tmpfile(void);
Создает временный файл в режиме wb+. После закрытия файла, последний автоматически удаляется.
Функция генерации имени временного файла:
char * tmpnam(char *buffer);

Удаление и переименование

Функция удаления файла:
int remove(const char *filename);
Функция переименования файла:
int rename(const char *fname, const char *nname);
Функции возвращают:
0 – в случае успеха,
!0 – в противном случае.

Лекция №4.

Стек.

Стек (stack) является как бы противоположностью очереди, поскольку он работает по принципу "последним пришел — первым вышел" (last-in, first-out, LIFO). Чтобы наглядно представить себе стек, вспомните стопку тарелок. Первая тарелка, стоящая на столе, будет использована последней, а последняя тарелка, положенная наверх — первой. Стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы.

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

int stack[MAX];

int tos=0; /* вершина стека */

 

/* Затолкать элемент в стек. */

void push(int i)

{

if(tos >= MAX) {

printf("Стак полон\n");

return;

}

stack[tos] = i;

tos++;

}

/* Получить верхний элемент стека. */

int pop(void)

{

tos--;

if(tos < 0) {

printf("Стек пуст\n");

return 0;

}

return stack[tos];

}

 

Переменная tos ("top of stack" — "вершина стека") содержит индекс вершины стека. При реализации данных функций необходимо учитывать случаи, когда стек заполнен или пуст. В нашем случае признаком пустого стека является равенство tos нулю, а признаком переполнения стека — такое увеличение tos, что его значение указывает куда-нибудь за пределы последней ячейки массива.

Пример работы со стеком.

Действие	Содержимое стека
push(A)	A
push(B)	В А
push(C)	C B A
рор() извлекает С	В А
push(F)	F В А
рор() извлекает F	В А
рор() извлекает В	А
рор() извлекает А	пусто

 

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

Пример:

/* Простой калькулятор с четырмя действиями. */

 

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

int *p; /* указатель на область свободной памяти */

int *tos; /* указатель на вершину стека */

int *bos; /* указатель на дно стека */

void push(int i);

int pop(void);

int main(void)

{

int a, b;

char s[80];

p = (int *) malloc(MAX*sizeof(int)); /* получить память для стека */

if(!p) {

printf("Ошибка при выделении памяти\n");

exit(1);

}

tos = p;

bos = p + MAX-1;

printf("Калькулятор с четырьмя действиями\n");

printf("Нажмите 'q' для выхода\n");

 

do {

printf(": ");

gets(s);

switch(*s) {

case '+':

a = pop();

b = pop();

printf("%d\n", a+b);

push(a+b);

break;

case '-':

a = pop();

b = pop();

printf("%d\n", b-a);

push(b-a);

break;

case '*':

a = pop();

b = pop();

printf("%d\n", b*a);

push(b*a);

break;

case '/':

a = pop();

b = pop();

if(a==0) {

printf("Деление на 0.\n");

break;

}

printf("%d\n", b/a);

push(b/a);

break;

case '.': /* показать содержимое вершины стека */

a = pop();

push(a);

printf("Текущее значение на вершине стека: %d\n", a);

break;

default:

push(atoi(s));

}

} while(*s != 'q');

 

return 0;

}

/* Занесение элемента в стек. */

void push(int i)

{

if(p > bos) {

printf("Стек полон\n");

return;

}

*p = i;

p++;

}

/* Получение верхнего элемента из стека. */

int pop(void)

{

p--;

if(p < tos) {

printf("Стек пуст\n");

return 0;

}

return *p;

}

Очередь.

Очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO. Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.

Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"— "сохранять", "retrieve" — "получать"). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В таблице показано действие последовательности таких операций.

Действие	Содержимое очереди
qstore(A)	A
qstore(B)	А В
qstore(C)	A B C
qretrieve() возвращает А	В С
qstore(D)	B C D
qretrieve() возвращает В	C D
qretrieve() возвращает С	D

 

Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста.

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

Пример:

/* Мини-планировщик событий */

 

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include <ctype.h>

#define MAX 100

char *p[MAX], *qretrieve(void);

int spos = 0;

int rpos = 0;

void enter(void), qstore(char *q), review(void), delete_ap(void);

int main(void)

{

char s[80];

register int t;

for(t=0; t < MAX; ++t) p[t] = NULL; /* иницилизировать массив

пустыми указателями */

 

for(;;) {

printf("Ввести (E), Список (L), Удалить (R), Выход (Q): ");

gets(s);

*s = toupper(*s);

 

switch(*s) {

case 'E':

enter();

break;

case 'L':

review();

break;

case 'R':

delete_ap();

break;

case 'Q':

exit(0);

}

}

return 0;

}

/* Вставка в очередь новой встречи. */

void enter(void)

{

char s[256], *p;

do {

printf("Введите встречу %d: ", spos+1);

gets(s);

if(*s==0) break; /* запись не была произведена */

p = (char *) malloc(strlen(s)+1);

if(!p) {

printf("Не хватает памяти.\n");

return;

}

strcpy(p, s);

if(*s) qstore(p);

} while(*s);

}

/* Просмотр содержимого очереди. */

void review(void)

{

register int t;

for(t=rpos; t < spos; ++t)

printf("%d. %s\n", t+1, p[t]);

}

/* Удаление встречи из очереди. */

void delete_ap(void)

{

char *p;

if((p=qretrieve())==NULL) return;

printf("%s\n", p);

}

/* Вставка встречи. */

void qstore(char *q)

{

if(spos==MAX) {

printf("List Full\n");

return;

}

p[spos] = q;

spos++;

}

/* Извлечение встречи. */

char *qretrieve(void)

{

if(rpos==spos) {

printf("Встречь больше нет.\n");

return NULL;

}

rpos++;

return p[rpos-1];

}

Список.

односвязный циклический список это рекурсивное объявление структур, точнее указателя на нее в самой структуре типа:

struct s{

int data;//поле данных

s *next;//следующий элемент

} *first,*curr;//первый и текущий элемент

Инициализация:

first=new s;

curr=new s;

first->next=curr;

чтобы получить первый элемент используй first->data

чтобы добавить новый элемент: curr->next=new s;

curr=curr->next;//переходишь к последнему

и чтобы получить например 50 элемент через цикл перебирай список:

curr=first;//переход к первому

for(int i=0;i<50;i++)

{

if(curr->next!=NULL)

{

curr=curr->next;

}

}