Ю.Н. Пронкин - Лекции по ЭВМ (2-3 семестры) (972268), страница 8
Текст из файла (страница 8)
Методы – те же самые функции. Классы – те же самые структуры, только в них можно вкладыватьфункции.Структуры непрерывного хранения1. Последовательность ( Какие-то элементы приходят один за другим. Мы не знаем сколько их придет).Т.о. приводит к понятию однопроходного алгоритма. (Этим мы занимались к начале I семестра)Предназначение:а) Инициализацияб) Обработать очередной элементв) Пропустить очередной элементг) Конец последовательности? (да/нет)д) Закрытие2. Стек (Принцип LIFO – Last Input First Out)рис.23.5.а) Инициализацияб) Добавить элемент на вершинув) Взять элемент с вершиныг) Стек пуст? (да/нет)д) Удалить вершинуе) ЗакрытьПример:Stack htypedef Struct {double *Buffer;int Depth;int sp;} STACK;Процедуры:STACK *StackInit (int Debth); - создать стэк – знать указатель на него;int StackPoint (STACK *sptr, double Value); – 0, если все хорошо, отриц.
– ошибка;int StackPop (STACK *Sptr, double *Value); – извлечение из стека;int StackClose (STACK **Sptr); - завершение. Двойной указатель – чтобы могли изменять адрес.3. Очередь (Принцип FIFO – First In First Out)Рис.23.6. Head – головапоказывает на первыйзаполненный слой,который будетобслуживаться. Tail – напервый пустой. (Длясимметризации)а) Инициализацияб) Добавить элемент в конецв) Взять элемент из началаг) Удалить элемент в начале очередид) Очередь пуста (да/нет)е) ЗакрытьПример:typedef Struct {double *Buffer;int Lenght;int Head, Tail;} QUEUE;Ссылочные реализации4.Список.Рис.23.7Рис.23.8.Есть однонаправленные(L1) и двунаправленные(L2) списки. В нашем случае L2.а) Инициализация.б) Добавление элемент в конец списка.в) Установить указатель в позицию k.г) Добавить элемент до/после указателя.д) Удалить элемент по указателю.е) Закрыть (Удалить память).Пример.typedef Struct LIST {char Str[256];Struct LIST *Next;;Struct LIST *Prev;} LIST;Рис.
23.9Процедуры:STACK *StackInit (int Debth); - создать стэк – знать укзатель на него;int StackPoint (STACK *sptr, double Value); – 0, если все хорошо, отриц. – ошибка;int StackPop (STACK *Sptr, double *Value); – извлечение из стэка;int StackClose (STACK **Sptr); - завершение.
Двойной указатель – чтобы могли изменять адрес.Дерево у нас состоится из вершин и ребер. Причем продолжать можем и верх и вниз. Т.е. имея два дерева,мы можем объединить их в одно.Лекция №2418.12.20105.ДеревьяДеревья выросли из списка, когда количество ссылок больше одной.
Две соседние вершинысоединяются ребрами. Расстояние между вершинами – все ребра между ними.Рис.24.1.Мы будем рассматривать определенные случаи, упорядоченных древ.Пример.typedef Struct TNODE {double Value;Struct TNODE *Prev;Struct TNODE *Next[k];} TNODE;Чаще всего мы хотим иметь дело со случаями да/нет, больше/меньше.
Т.е. не более двух ответов.Рассмотрим бинарное дерево.Бинарное дерево (общийслучай)Рис.24.2.а.Бинарное дерево(сбалансированное, т.е.разница двух вершин неболее 1.)Рис.24.2.б.Пример:typedef Struct TNODE {double Value;Struct TNODE *Prev;Struct TNODE *Left, Right;} TNODE;Этот тип является и последним и не последним в каком-то смысле, в зависимости от средыпрограммирования. Рекурсивность и пр. Если язык сам обладает рекурсивной природой, тообратный маршрут он будет запоминать автоматически.
Если дерево имеет очень большую глубину,то рекурсивность может переполнять память и становится невыполнимой. Если мы используемрекурсивность древа и языка, то родитель нам не нужен (стираем Struct TNODE *Prev;).Сейчас мы снова вернемся к общим деревьям и наложим новые условия.Рассмотрим пример.Рис.24.3.Вообще этот рисунок можно посмотреть в книге [1]; Хотим обходить дерево с поискоммаксимального значения лежащего в вершина.Возможные стратегии:- сверху - вниз- слева - направо- снизу – вверх1) void UpDown (TNODE *Pos, double *Max){if(!Pos)return ;if (*Max<Pos->Value)*Max=Pos->Value;UpDown (Pos->Left, Max);UpDown(Pos->Right, Max);}ABDHIECFJKLG2) void LeftRight (TNODE *Pos, double *Max){if(!Pos)return ;LeftRight(Pos->Left, Max)if (*Max<Pos->Value)*Max=Pos->Value;LeftRight (Pos->Right, Max);}HDIBEAJFKLCGДерево поискаPos->Left->Value≤Pos->Value<Pos->Right->Value; (*)Дерево поиска – бинарное дерево, для каждой вершины которого верно (*);Рис.24.4.В этом дереве мы явно видим усиление бинарного дерева.typedef Struct TNODE {double Value;Struct TNODE *Down, *Next;} TNODE;Мы получили дерево эффективности как бинарное.
К нему верны все бинарные алгоритмы, т.к. мыобрубили ветви (пунктиром помечены на рисунке).6.МножестваПоиск (основная операция)1.Линейный поиск2.Двоичный поиск3.Битовая реализация4.Хеширование множествЛинейный поискРис.24.5а.Вообще линейный поиск не очень эффективен.Бинарный поискРис.24.5.б.Есть затраты на сортировку. Но если отсортировано – то все хорошо, смотри предыдущие разговор. Получимбольшую эффективность. Область применения сильно лимитирована, как ив прошлом случае.Битовая реализацияРис.24.5.в.Хеширование множествЭто обособленная часть по факту, хоть и является одним из поисков. Вообще является комбинациейпредыдущих, так как мы хотим большую эффективность.Проблема коллизийРис.24.6.Вместо того, чтобы заполнить память, мы переполнили его часть.
Какой же выход из такой ситуации?Разрешение коллизийРис. 24.71.Использование списков2.Метод пробИспользование списковИмеем некоторые элементы x. Вычисляем функцию хеширование и получаем значение k. k⋳Экзаменационные билеты на 2010 год.(ходят достоверные слухи, что они же будут и в 2011)Билет 11. Общая архитектура микропроцессорных вычислительных систем.
Функциональная схемакомпьютера. Типы и характеристики микропроцессоров (разрядность, частота синхронизации,организация системы команд). Сравнение CISC и RISC архитектур.2. Написать программу загрузки из текстового файла последовательности целых чисел,игнорирующую все элементы исходной последовательности, равные среднему арифметическомусвоих соседей. Напечатать загруженные элементы в порядке их возрастания.Билет 21.
Типы и характеристики запоминающих устройств. Организация основной памяти компьютера. Понятиеадресного пространства. Реальные и виртуальные адреса. Прямой доступ к основной памяти.2. Написать программу, отыскивающую во входном файле целых чисел такие, у которых старший байтих внутреннего машинного представления является «зеркальным отражением» младшего байта(например, 01010100.00101010). Напечатать найденные числа в порядке возрастания ихабсолютной величины.Билет 31. Многоуровневая организация памяти.
Ассоциативная кэш-память. Размещение, поиск и замещение блоков.Стратегии записи. Многоуровневая кэш-память.2. Выполнить программную реализацию объекта «Стек двухкомпонентных векторов». Максимальнаяглубина стека задается динамически при инициализации объекта.Билет 41. Организация системной шины персональных компьютеров семейства IBM PC.
Взаимодействие основныхаппаратных модулей. Управление доступом к основной памяти и подсистеме ввода/вывода. Адресация портовввода/вывода.2. Написать программу, загружающую из файла последовательность символьных строк ограниченнойдлины и располагающую их в элементах динамически создаваемого связного списка. Напечататьзагруженные строки в лексико-графическом порядке. Для сравнения строк воспользоватьсяфункцией strcmp().Билет 51. Архитектура микропроцессоров Intel x86.
Управление потоком команд. Базирование ииндексирование памяти. Управление стеком. Сегментная организация памяти. Формированиеисполнительного адреса. Битовые флаги состояния и управления.2. Написать программу сортировки последовательности целых чисел произвольным методом, принимая за ключсортировки сумму всех цифр десятичной записи числа. Последовательность загрузить из файла, память дляхранения выделить динамически. Напечатать отсортированную последовательность.Билет 61. Представление данных в ЭВМ. Машинная арифметика. Погрешность представления чисел сплавающей точкой и ее влияние на точность вычислений.2. Числовую матрицу с заданным количеством колонок и заранее неизвестным количеством строкзагрузить из файла, выделяя память динамически под каждую ее строку.
Написать функцию,печатающую элемент матрицы по его линейному индексу в предположении, что нумерацияэлементов матрицы ведется по колонкам, начиная с нуля.Билет 71. Организация работыс подпрограммами в режиме реального адреса микропроцессоров Intel x86.Рекурсивные вызовы. Вызовы с параметрами. Механизмы передачи параметров.2. Написать программу подсчета количества слов в произвольном текстовом файле, принимая заразделители слов любой из символов введенной с клавиатуры цепочки.
Определить количествосимволов в самом длинном слове. Результаты напечатать.Билет 81. Прерыванияипрограммыобработкипрерываний.Классификацияпрерываний.Зарезервированные вектора прерываний режима реального адреса микропроцессоров Intel x86.Последовательность прерывания.2. Выполнить программную реализацию объекта «Очередь строк фиксированной длины» на базекольцевого вектора. Максимальная длина очереди задается динамически при инициализацииобъекта.Билет 91. Обработкавнешних аппаратных прерываний.Последовательность аппаратного прерывания.Назначениеиработаконтроллерапрерываний.2. Написать программу сортировки последовательности целых чисел методом Quick Sort, принимая заключ сортировки количество единиц в машинном представлении каждого числа.Последовательность загрузить из файла, память для хранения выделить динамически.Билет 101.
Работа микропроцессоров Intel x86 в защищенном режиме. Общая схема формированияисполнительного адреса. Кольца защиты. Организация дескрипторных таблиц. Адресноепространство задачи.2. Написать программу, загружающую из файла последовательность символьных строк ограниченнойдлины с динамическим выделением памяти для хранения символов каждой строки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
