- •1. Основные операции языка Си.
- •3. Язык Си: указатели и массивы. Определения, примеры.
- •4. Язык Си: объявления функций, передача аргументов. Примеры.
- •5. Язык Си: строки и указатели. Определения, примеры.
- •8. Язык Си: структуры. Пример.
- •9 . Язык Си: битовые поля и объединения. Примеры.
- •10. Язык Си: оператор определения типа. Примеры.
- •11.Язык Си: препроцессор. Директивы препроцессора, примеры
- •12.Язык Си: программный стек. Пример работы стека.
- •13. Линейные списки. Операции с линейными списками.
- •14 Hash-таблицы
- •15 Двоичные деревья
- •17. Язык Си: ссылочные типы. Пример.
- •18. Язык Си: защита указателей и объектов, неявное изменение объектов.
- •19. Язык Си: организация ввода/вывода. Пример: слияние файлов. Организация ввода/вывода
- •Открытие файла
- •Закрытие файла
- •Ввод из файла
- •Вывод в файл
- •Особые ситуации
- •Пример: слияние файлов
- •20. Язык Си: произвольный доступ к файлам. Пример.
- •22. Язык Си: примеры реализаций функций ввода/вывода (getc,putc).
- •23. Язык Си: примеры реализаций функций ввода/вывода (fgets, fputs).
- •24. Язык Си: работа с файловой системой. Пример.
- •25. Основные понятия ооп: абстракция, инкапсуляция, наследование, полиморфизм.
- •27. Объекты классов: статические,автоматические, динамические. Примеры.
- •28. Управление доступом к элементам классов. Пример.
- •29. Шаблоны функций и шаблоны классов. Примеры.
- •30. Наследование. Пример.
- •31. Множественное наследование. Пример.
- •П оскольку классы-потомки наследуют все данные и методы классов-предков, в итоге имеем следующую картину:
- •32. Виртуальные функции. Раннее и позднее связывание.
- •33. Абстрактные классы. Их назначение, пример.
- •34. Полиморфный контейнер (пример).
- •36. Конструкторы, их виды, примеры. Вызов конструкторов при наследовании.
- •37. Деструкторы. Их назначение, примеры.
- •39. Перегруженные операции. Примеры.
- •40. Обработка нештатных ситуаций. Объекты-исключения. Примеры.
- •Вопрос 1: какова дальнейшая судьба этих ресурсов, будут ли они освобождены?
- •Вопрос 2: как распознавать подобные ситуации и корректно их обрабатывать?
- •41. Модели жизненного цикла программного обеспечения. Модели жизненного цикла по
- •Спиральная модель жизненного цикла по.
- •42. Проектирование программного обеспечения и uml.
- •Uml (основные понятия)
- •Канонические диаграммы языка uml 2.X
- •43. Диаграммы прецедентов. Нотация, семантика, примеры.
- •Основные обозначения на диаграммах прецедентов:
- •44. Сценарии выполнения прецедентов (пример).
- •45. Диаграммы классов. Нотация, семантика, отношения.
- •46. Атрибуты на диаграммах классов. Нотация и семантика. Примеры.
- •47. Операции на диаграммах классов. Нотация и семантика. Примеры.
- •48. Отношения ассоциации на диаграммах классов.
- •Отношения ассоциации
- •Предприятие
- •Сотрудник
- •Отношения обобщения
- •Отношения композиции
- •53. Язык c#: сборки, манифесты, домены, компоненты.
- •55. Java как язык ооп для машинно-независимых приложений.
- •56. Обзор Java-технологий NetBeans ide.
- •57. Компонентные технологии разработки программного обеспечения.
- •59.Обёртки в языках c# и Java.
- •60. Архитектурный паттерн mvc. Область применения, схема взаимодействия.
15 Двоичные деревья
1. Пустой граф и граф с одним узлом есть двоичное дерево.
2. Граф следующего вида есть двоичное дерево:
3. Двоичное дерево, левая и правая части которого есть двоичное дерево также есть двоичное дерево
Дерево - структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг) причем в каждый узел (кроме корневого) ведет ровно одна дуга
Корень – начальный узел дерева
Лист – узел, из которого не выходит ни одна дуга
Способы обходы дерева:
Head, left, right (hlr): 1 2 4 5 3 6 7
Left, head, right (lhr): 4 2 5 1 6 3 7
Left, right, head (lrh): 4 5 2 6 7 3 1
Код алгоритмов обхода:
Hlr:
Void hlr(Tp p){ //указатель на корень
If(p){
R(p->ptr); //обработка узла
hlr(p->left);
hlr(p->right);
}
}
Lhr
Void lhr(Tp p){ //указатель на корень
If(p){
lhr (p->left);
R(p->ptr); //обработка узла
lhr (p->right);
}
}
Lrh
Void lrh(Tp p){ //указатель на корень
If(p){
lrh (p->left);
lrh (p->right);
R(p->ptr); //обработка узла
}
}
Двоичные деревья полезны когда им присущ внутренний порядок
Пусть определена хэш функция h(<object>)
Рекурсивный поиск в сорт. Дерево с включением
Пусть задан некий <object> для поиска и/или вставки в дерево
Void locate(Tp p){ //з – указатель на корень дерева
If(!p){ p = new T; p->ptr=&<object>; p->left = p->right = NULL;}
else if(<object>!=*p->ptr)
if(h(<object>) < h(*p->ptr)) locate(p->left);
else locate(p->right);
}// в итоге р – указатель на найденный или созданный элемент
Е сли дерево построено при помощи алгоритма locate тогда сортировка есть просто lhr обход или rhl обход сортирующего дерева
Пример:
Пусть данные поступают в порядке: 4 5 2 7 3 6 1
Осуществим lhr обход и получим 1 2 3 4 5 6 7
Итеративный поиск
Пусть задан некий <object>
void search1 (Tp p){ // р – указатель на корень
while(p && (*p->ptr != <object>)
if(h(<object> < h(*p->ptr)) p = p->left;
else p = p->right;
} //в итоге р – указатель на найденный узел или NULL
Рекурсивный поиск в сортирующем дереве
Пусть задан некий <object>
void search2(Tp p){ // р – указатель на корень
if(p) if(<object> != *p -> ptr)
if(h(<object>) < h(*p->ptr) search2(p->left);
else search2(p->right);
} //в итоге р – указатель на найденный узел или NULL
16. Язык СИ: перегруженные функции. Пример.
Перегруженные функции
Можно иметь несколько вариантов одной и той же функции (перегрузка функции).
Сигнатура вариантов функции должна отличаться (количество и типы аргументов), имя функции остается неизменным.
Пример:
overload length; //функция с именем length будет перегружена
// функция length вычисляет длину вектора на плоскости, длину
// вектора в трехмерном пространстве и длину строки в байтах
float length (int x, int y){ return sqrt( x*x + y*y ); } //на плоскости
float length (int x, int y, int z){ return sqrt( x*x + y*y + z*z ); } //в пространстве
int length ( char *s ) { return charWidth * strlen( s ); } //длина строки в байтах
//вызов функции
length ( 1, 5 ); //на плоскости
length ( 1, 0, 3 ); //в пространстве
length ( name ); //длина строки в байтах