40гг первые цифровые компьютеры программирование путем коммутации проводов

Вид материала

Содержание

Пример добавления элемента в массив.
Вставка элемента в список
Реализация списка с помощью структур С++
LIST_ELEMENT *p = first_element_of_list
LIST_ELEMENT *new_elt =
Понятие абстрактного типа данных
Понятие инкапсуляции
Преимущества инкапсуляции
Пример использования структуры для реализации понятия даты

Подобный материал:

1 2 3 4 5 6 7 8 9 ... 12

FILE *out = fopen("test.txt","wt");

fputs("Hello, World!", out);

fclose(out);

Пример чтения из файла

FILE *in = fopen("test.txt","rb");

while(!feof(in)){

char c = fgetc(in);

printf(“Прочитан символ с кодом %i \n", (int)c);

}

fclose(in);

Математические функции

Описаны в файле math.h
Они позволяют получить

абсолютное значение (abs, fabs),
округленное число (ceil, floor),
квадратный корень (sqrt),
степень (pow),
значения тригонометрических функций (sin, cos, tan, sinh, cosh, tanh, asin, acos, atan, atan2),
экспоненту (ехр),
логарифм (log, log10),
дробную и целую части числа (modf),
остаток от деления (fmod)
и другие (см. help)

Функции работы со строками

Заголовочный файл string.h
Библиотека С содержит функции

копирования строк (strcpy, strncpy),
сравнения (strcmp, strncmp),
объединения строк (strcat, strncat),
поиска подстроки (strstr),
поиска вхождения символа (strchr, strrchr. strpbrk),
определения длины строки (strlen)
и другие (см help).

Динамические структуры данных

Во время выполнения программы количество данных может существенно изменяться.
Задачи:

вставка и удаление элементов
доступ к произвольному элементу

Работа с массивами. Доступ к произвольному элементу.

Элементы массива располагаются в памяти последовательно.
Зная размер элемента и адрес начала массива можем получить адрес элемента одним выражением.

Добавление элемента в массив

Последовательность действий

Выделить память для нового массива
Переписать старый массив
Добавить новый элемент
Освободить память от старого массива

Аналогичные действия потребуется выполнить если количество элементов уменьшилось.
При вставке элемента в середину массива алгоритм усложняется.
Большие временные затраты. При больших размерах массива держать в памяти сразу два массива может быть затруднительно.

Пример добавления элемента в массив.

int n = 10; // Количество элементов в массиве

int *m = new int[n]; // Сам массив

// Работа с массивом из 10 элементов

…

// потребовалось хранить 11 элементов

int m1 = new int[n+1];

for(int i=0;i

m1[n] = новый элемент;

delete[] m;

m = m1;

n++;

// Работаем дальше с массивом из 11 элементов

Структуры.

Понятие структуры в С++ эквивалентно понятию записи.

Перед использованием структура должна быть объявлена.

Элементами структуры могут быть данные любых типов.

Объявление структуры

struct имя_структуры {

тип_элемента название;

тип_элемента название;

…

тип_элемента название;

};

Примеры объявления структур

struct S1{

int a;

int b;

};

struct S2{

char *s;

int mas[100];

};

struct S3{

S1 simple_struct;

S2 big_struct;

S3 *next_element_in_list;

};

Обращение к элементам структур

Если переменная является структурой, то для обращения к элементу структуры используется операция “.”

Например:

S1 ss;

ss.a = 5;

ss.b = 10;

int tmp = ss.a + ss.b;

Обращение к элементам структур через указатели

Если переменная является указателем на структуру, то доступ к элементам структуры можно получить разыменовав указатель:

S1 * ss = new S1;

(*ss).a = 5;

(*ss).b = 10;

int tmp = (*ss).a + (*ss).b;

delete ss;

Упростить доступ можно с помощью специальной операции “->”.

S1 * ss = new S1;

ss->a = 5;

ss->b = 10;

int tmp = ss->a + ss->b;

delete ss;

Понятие списка

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

Как правило, в С++ элементами списка являются структуры одного типа, а связь элементов осуществляется с помощью указателей.

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

Односвязный линейный список

Двусвязный линейный список

Доступ к элементам односвязного списка

Необходимо хранить адрес первого элемента списка.

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

Признак достижения последнего элемента – отсутствие указателя на следующий элемент.

Вставка элемента в список

Удаление элемента из списка

Реализация списка с помощью структур С++

struct LIST_ELEMENT{

int a;

char s[10];

LIST_ELEMENT *next_element_of_list;

};

LIST_ELEMENT * first_element_of_list = NULL;

Поиск нужного элемента

Предположим, требуется найти элемент с номером K. Будем считать, что элементы списка нумеруются с нуля.

LIST_ELEMENT *p = first_element_of_list;

for(int i = 0; i

if(p == NULL){

// Ошибка! Элемент не найден.

}

p = p->next_element_of_list;

}

// в этой точке программы p указывает на //элемент списка с номером K

Добавление элемента в начало списка

LIST_ELEMENT *new_elt =

new LIST_ELEMENT;

new_elt->a = 10;

strcpy(new_elt->s,”Новый”);

new_elt->next_element_of_list = first_element_of_list;

Добавление элемента в конец списка

LIST_ELEMENT *new_elt = new LIST_ELEMENT;

new_elt->a = 10;

strcpy(new_elt->s,”Новый”);

new_elt->next_element_of_list = NULL;

LIST_ELEMENT *p = first_element_of_list;

if(p == NULL)

first_element_of_list = new_elt;

else{

while(p->next_element_of_list != NULL)

p = p->next_element_of_list;

p->next_element_of_list = new_elt;

}

Удаление первого элемента списка

if(first_element_of_list != NULL){

LIST_ELEMENT *tmp = first_element_of_list;

first_element_of_list =

first_element_of_list->next_element_of_list;

delete tmp;

}

Виды структур данных

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

Пользователю предоставляется некоторый набор функций для работы со списком.

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

Список

Очередь

Стек

и т.д.

Абстрактные типы данных

Основные вопросы

Определение типа и поколения языков программирования

Понятия абстракции и абстрактного типа данных

Понятие инкапсуляции и ее преимущества

Спецификация и реализация абстрактного типа данных

Реализация абстрактных типов в С++

Определение типа

Тип данных - множество с операциями (алгебра), учитывающая следующее:

если дан новый тип, то можно описывать и инициализировать переменные этого типа;

если дана переменная некоторого типа, то можно определить и изменить ее текущее значение;

если даны два значения определенного типа, то можно сравнить их, по крайней мере на равенство или неравенство;

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

Если два типа отличаются по любым из перечисленных факторов, то такие типы считаются разными

Поколения языков

Первое поколение - языки с минимальными возможностями типизации

Предоставляют лишь средства для описания переменных простых типов и массивов; никаких новых типов вводить нельзя.

Фортран, Алгол-60.

Второе поколение – языки, предоставляющие программисту основные конструкторы типов: массивы, записи, объединения

ПЛ/1, Алгол-68, Паскаль, С

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

Все операции над типами данных предопределенные — определяемые языком, а не программистом.

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

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

С++, C#, Java

Типы понимаются как множества с операциями.

Понятие абстракции

Абстракция — это суждение или представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте.

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

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

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

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

Понятие абстрактного типа данных

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

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

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

Определение абстрактного типа данных

Абстрактный тип данных — это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями.

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

Например:

определение понятия стека в терминах операций " втолкнуть элемент в стек", " создать новый стек", "выдать верхний элемент" и т.д.

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

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

Понятие инкапсуляции

Инкапсуляция — это способ объединения в единое целое подпрограмм и данных, которые они обрабатывают.

Инкапсуляция предшествует абстрактным типам данных и поддерживает их.

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

Преимущества инкапсуляции

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

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

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

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

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

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

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

Защита страхует также от возможных ошибок и попыток незаконно использовать внутренние представления данных.

Упрощение процесса отладки.

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

Упрощение модификации программы.

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

Спецификация и реализация

Объявление абстрактного типа данных состоит из двух частей

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

Реализация – раскрывает семантику операций, инкапсулируя ее от внешней среды.

Критерии, которым должны удовлетворять спецификации

Точность

Понятность

Конструктивность

Мощность

Минимальность

Модифицируемость

Реализация абстрактного типа данных

Включает в себя конкретное описание объектов определяемого типа и реализацию операций этого типа.

Объекты описываются в терминах простых или составных типов или ранее определенных абстрактных типов.

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

Абстрактные типы данных в С++

Абстрактные типы данных в С++ создаются с помощи синтаксической конструкции называемой «классом».

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

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

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

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

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

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

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

Состав класса

Внутренние переменные класса называются атрибутами.

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

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

Метод может быть специальным образом описан для "очистки" каждого классового объекта при его уничтожении. Такой метод называется деструктором.

Пример использования структуры для реализации понятия даты

struct date {

int month;

int day;

int year;

};

date today;

void set_date(date*, int, int, int);

void next_date(date*);

void print_date(date*);

// ...

Спецификация класса в С++

class имя_класса{

модификатор_доступа:

[атрибуты]

[методы]

модификатор_доступа:

[атрибуты]

[методы]

…

};

Пример использования класса для реализации понятия даты

class date{

private:

int month, day, year;

public:

void set(int, int, int);

void get(int*, int*, int*);

void next();

void print();

};

Модификаторы доступа

private

public

protected

Работа с классом

date d1;

data *d2 = new date;

d1.set(5,5,2005);

d2->set(6,6,2006);

d1.next();

d2->print();

d1.year = 2007; // ошибка

delete d2;

Реализация класса

void date::print()

{

printf(“%i.%i.%i”,day,month,year);

}

Разделение спецификации и реализации

date.h

class date{

private:

Blog

40гг первые цифровые компьютеры программирование путем коммутации проводов

Содержание