Лекция 5-1 2017 Файлы, случайные числа, списки (Лекции (2017)), страница 2

НГУ, ФФ, 2017Лысаков К.Ф.Полезные опции: fseek и ftellint fseek(FILE *f, long offset, int flag);// Для файлов, которые открыты на чтениеFILE *flong offsetint flag- файл, в котором передвигаемся;- количество байтов для отступа,отступ производится в соответствии с 3-м параметром;- позиция, от которой будет совершен отступ;в стандартной библиотеке C для этого параметра определены 3 константы:• SEEK_SET -- начало файла;• SEEK_CUR -- текущас позиция;• SEEK_END -- конец файла;int fseek() - возвращает ноль, если операция прошло успешно, иначе возвращаетсяненулевое значение.long int ftell(FILE *f);// определение текущего положение в файле// Для файлов, которые открыты на чтениеКурс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.Работа с файлами в СиFILE *f = fopen("file1.txt", "r");fscanf(f, "%s", str);fprintf(f, "%d\n", a);int N = atoi(string);Курс «Основы программирования». НГУ, ФФ, 2017???Лысаков К.Ф.«Случайные» числа в Си#include <stdio.h>#include <stdlib.h>void main(){int i, r;for (i = 0; i < 10; i++){r = rand();printf("%d\n", r);}}#include <stdlib.h>int rand( void );Функция RAND() генерирует положительное целое число от0 до RAND_MAXКурс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Случайные числаПсевдослучайные числа«особенные алгоритмы»Никакой детерминированный алгоритм неможет генерировать полностью случайныечисла, он может только аппроксимироватьнекоторые их свойства.Использование надёжных источниковэнтропии, таких, как тепловойшум, дробовой шум, фотоэлектрическийэффект, квантовые явления и т.

д.«Всякий, кто питает слабость карифметическим методам полученияслучайных чисел, грешен вне всякихсомнений» - Джон фон НейманЕсли в качестве источника энтропии использовать текущее время, то дляполучения целого числа от 0 до N достаточно вычислить остаток отделения текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧявляется то, что в течение одной миллисекунды он выдает одно и то же число.Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Инициализация генератора «случайных» чисел в Си#include <stdlib.h>void srand( unsigned int seed );Функция srand выполняет инициализацию генератора случайных чисел rand.Генератор псевдо-случайных чисел инициализируется с помощью аргумента seed.#include <time.h>Тип данных time_tЭтот тип данных используется для представления целого числа — количества секунд,прошедших после полуночи 00:00 , 1 января 1970 года в формате GMT. Это обусловленоисторическими причинами, связанными со становлением платформы UNIX.#include <time.h>time_t time( time_t * timeptr );time_t time( );Функция возвращает текущее календарное значение времени в секундах.

Если аргументне является нулевым указателем, ей передается значение времени типа time_t.Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.«Случайные» числа в Си#include <stdio.h>#include <time.h>#include <stdlib.h>void main(){int i, r;srand(time(NULL));for (i = 0; i < 10; i++){r = rand();printf("%d\n", r);}}Курс «Основы программирования». НГУ, ФФ, 2017???Лысаков К.Ф.Связные списки данных• динамическая структура данных в информатике• состоит из узлов• каждый узел содержит• собственно данные• одну или две ссылки («связки») на следующий и/илипредыдущий узел спискаПринципиальные преимущества перед массивом:1. структурная гибкость: порядок элементовсвязного списка может не совпадать спорядком расположения элементов данных впамяти компьютера2.

порядок обхода списка всегда явно задаётсяего внутренними связями.Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Виды связных списковЛинейный однонаправленный списокДвунаправленный связный списокКольцевой связный списокНедостатки:Достоинства:1. Сложность прямого доступа к элементу1. Эффективное (за константноеопределение физического адреса по его индексувремя) добавление и удаление2.

Ряд операций со списками медленнее, чем сэлементовмассивами (произвольный доступ)2. Размер ограничен только объёмом3. Соседние элементы списка могут бытьпамяти компьютера ираспределены в памяти нелокально, что снизитэффективность кэширования данных в процессореразрядностью указателей4. Накладные расходы на перебор элементов3. динамическое добавление иснижают эффективность распараллеливанияудаление элементовКурс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Работа со списками в СиСписок — это упорядоченная последовательностьсвязанных данных, связанных между собой.Односвязный список характеризуется наличиемодной связи у соседних элементов. Другими словами,каждый элемент знает об одном соседе•передвигаться можно только последовательно в одномнаправлении: от начала к концуДвусвязный список отличается наличием двух связей укаждого элемента.

При этом организуетсядвунаправленность списка.• зная любой элемент списка, можно получитьинформацию как о следующем элементе списка, так и опредыдущемДля управления списком необходимознать только первый его элемент —начало списка. Последний элементопределяется по признаку того, чтоследующего за ним не существует, т. е.указатель равен NULLКурс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Работа со односвязным списком в Сиstruct Cell{int Val;struct Cell* pnext;};Каждый элемент списка содержит два поля:• собственно целочисленное число• указатель на следующий элемент списка:void main(){struct Cell* pBegin = NULL;pBegin = CreateList();PrintList(pBegin);pBegin = ClearList(pBegin);}Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.Работа со односвязным списком в Сиstruct Cell* CreateList(){struct Cell* pBegin;struct Cell* pNew1;struct Cell* pNew2;struct Cell* pNew3;pNew1 = malloc(sizeof(struct Cell));scanf("%d", &(pNew1->Val));pNew2 = malloc(sizeof(struct Cell));scanf("%d", &(pNew2->Val));pNew3 = malloc(sizeof(struct Cell));scanf("%d", &(pNew3->Val));pBegin = pNew1;pNew1->pnext = pNew2;pNew2->pnext = pNew3;pNew3->pnext = NULL;return pBegin;}Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.Работа со односвязным списком в Сиvoid PrintList(struct Cell* pBegin){struct Cell* pCur = NULL;if (pBegin == NULL){printf("No elements\n");return;}pCur = pBegin;do{printf("%d\n", pCur->Val);}while(pCur != NULL);}Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Работа со односвязным списком в Сиstruct Cell* ClearList(struct Cell* pBegin){struct Cell* pCur = NULL;if (pBegin == NULL)return NULL;do{pCur = pBegin;pBegin = pBegin->pnext;free(pCur);}while(pBegin != NULL);return NULL;}Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.ДеревьяДерево — это связный ациклический граф.• Связность - наличие путей между любой парой вершин• Ацикличность• отсутствие циклов• между парами вершин имеется только по одномупутиЛес — упорядоченное множество упорядоченных деревьев.Ориентированное (направленное) дерево — ацикличныйорграф (ориентированный граф, не содержащий циклов), вкотором только одна вершина имеет нулевую степень захода(в неё не ведут дуги), а все остальные вершины имеютстепень захода 1 (в них ведёт ровно по одной дуге).Вершина с нулевой степенью захода называется корнемдерева, вершины с нулевой степенью исхода (из которых неисходит ни одна дуга) называются концевыми вершинамиили листьямиКурс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.СтекСтек (англ. stack) — абстрактный тип данных, представляющий собой списокэлементов, организованных по принципу LIFO (англ. last in — first out, «последнимпришёл — первым вышел»).Принцип работы стека – «стопка тарелок»: чтобы взять вторую сверху, нужно снятьверхнюю.Понятие стека ввел в 1946 Алан ТьюрингВ 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга.Зачастую стек реализуется в виде однонаправленного списка.При организации стека в виде однонаправленного списка значением переменной стекаявляется указатель на его вершину — адрес вершины.Если стек пуст, то значение указателя равно NULL.Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф..