В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

1Краткий конспект курса лекций«Работа на ЭВМ и программирование»2 курс, лектор В.Д. ВалединскийКонспект составил Озеров Сергей, 208 группа @ 2002/03 годОгромное спасибо Даниле Мусатову за исправление в этом конспектемассы ошибок и добавления раздела про компиляцию.Замечания / ошибки / исправления / вопросы / предложения?Пишите: ozerovsergey@freemail.ruЖелательно – с указанием номера страницы и приведением хотя бы абзаца текстаВторое издание.Посвящается Наташе (Коту)Некоторые замечания по структуре конспектаВ конспекте используются некоторые общеупотребительные термины и сокращения.Движение влево по массиву означает движение в сторону уменьшения индексовэлементов массива.

Движение вправо, соответственно – в сторону увеличения.К-ч дерево = красно-черное деревоCPU = Central Processing Unit = процессорОЗУ = Оперативное Запоминающее Устройство = оперативная памятьHDD = Hard Disk Drive – жесткий дискОС = Операционная СистемаПО = Программное Обеспечение = программаВезде, где упоминается сравнение элементов имеется в виду не арифметическоесравнение, а некоторая операция порядка, введенная на множестве доступных элементов.Главы конспекта пронумерованы в соответствии с программой экзамена по ЭВМ,поэтому их структура и порядок следования информации может несколько отличаться отпорядка в прочитанных лекциях.

Некоторый материал дан в сокращенном виде, некоторыйрасписан более подробно. Жирным шрифтом выделены ключевые понятия,упоминающиеся в программе экзамена, в тех местах, где дается их определение. Курсивомприводятся комментарии и примечания.1. Структуры представления и хранения данных.1.1. Стек, дек, очередь. Непрерывные реализацииСтек (Stack) – структура данных, пояснить которую можно следующей схемой:данныевершина (top) стека- своеобразной «трубой», открытой с одного конца и закрытой с другого, в которую мыможем закладывать и извлекать какие-то данные. Закладываем мы данные по одному и,соответственно, в каждый момент времени имеем доступ только к элементу, положенномупоследним.

Например, добавив в стек по очереди числа 1, 2, 3 мы извлечем их затем вобратной последовательности: 3, 2, 1. В английской литературе это называется принципомLIFO (Last In First Out) – последний добавленный элемент извлекается первым.Очередь (Queue) – структура данных, пояснить которую можно следующей схемой:Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год2голова (head) очередихвост (tail) очереди- «трубой», открытой с обоих сторон, но добавлять данные в которую мы можем толькос одной стороны, а извлекать – только с другой. Положив с одного конца по очереди числа 1,2, 3 с другого мы извлечем ту же последовательность – 1, 2, 3.

Такая схема обозначаетсяFIFO (First In First Out) – первый добавленный элемент извлекается первым.Объединение этих структур (стека и очереди) дает дек (Double-Ended Queue, deq) –открытую с обеих сторон очередь.И добавлять, и извлекать данные дека мы можем с обеих сторон, так что очевидно, чтодек реализует все свойства и стека и очереди.Простейшие реализации стека очевидны – заводим в памяти массив данных некоторойфиксированной длины и указатель на вершину стека. При добавлении элемента запишем егов массив сразу за вершиной и переставим указатель на вершину на вновь добавленныйэлемент. При извлечении элемента – вернем текущую вершину и переставим указатель напредыдущий элемент.

Проверка на пустоту стека – сравнение адресов начала выделенногоучастка памяти и адреса вершины стека; на полноту – сравнение адресов конца выделенногоучастка и адреса вершиныЧуть сложнее линейная реализация очереди и дека – в них аналогичный способмалоприменим, поскольку очередь будет «ползти» по памяти при добавлении и удаленииэлементов. Здесь рассматривают «циклическую» реализацию, «склеивая» конец и началовыделенного куска памяти. Например, если у нас массив mem[100], то при необходимостиобратиться к 145 элементу мы обратимся к mem[145%100] = mem[45] элементу. Этопозволяет гарантировать, что можно создать очередь той длины, которую мы укажем присоздании очереди.

При этом нам приходится хранить не только указатели на начало/конецвыделенного участка памяти и голову очереди, но еще и указатель на ее хвост. Реализациидека и очереди различаются только возможностями по добавлению/извлечению элементов.(пропущен фрагмент, посвященный ООП)Рассмотрим теперь общую концепцию ООП. Введем вначале понятие объектаОчевидно, объект, например, хранящий в себе какие-то данные, определяетсяследующим набором известных для него методов:1. Создание/уничтожение объекта2. Добавление/удаление элемента данных в объект3. Права доступа к заложенным в объект данным4. Опрос состояния объектаЛюбому, использующему данный объект, безразлично внутреннее устройство объекта –его интересуют прежде всего указанные свойства объекта.

Поэтому объект разделяют на 2части –1. Интерфейс (), т.е. внешнее описание объекта, доступное любому2. и собственно внутреннюю реализацию объекта, доступную только самому объекту.Например, интерфейс стека будет состоять из примерно следующего набора команд:1. Создать стек2. Уничтожить стек3. Добавить элемент4. Удалить элемент5. Получить элемент (прочитать элемент стека и удалить его)6. Доступ к вершине (не удаляя элемент из стека прочитать/изменить его)7. Стек пуст?8. Стек полон?Лекции по ЭВМ. Конспект.

Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год3На языкеint St_Init(int maxsize);void St_Term();int St_Push(int x);int St_Del();int St_Pop(int *val);int St_Get(int *val);int St_Set(int val);int St_Empty();int St_Room();class Stack{int St_Init(int maxsize);void St_Term();int St_Push(int x);int St_Del();int St_Pop(int *val);int St_Get(int *val);int St_Set(int val);int St_Empty();int St_Room();};class Stack{private:int *mem, *top, *endmem;public:int St_Init(int maxsize);void St_Term();int St_Push(int x);int St_Del();int St_Pop(int *val);int St_Get(int *val);int St_Set(int val);int St_Empty();int St_Room();};(конец фрагмента)1.2.

Списки. Списочные реализацииОднонаправленный список.Структура данных, для каждого элемента которой (кроме одного, называемого концомсписка) определен следующий элемент и для всех элементов, кроме одного (начала списка)существует элемент, для которого текущий является следующим, называетсяоднонаправленным списком:началоспискаконецспискаАналогично определяется двунаправленный список, здесь для каждого элементаопределен еще и предыдущий элемент, причем если у нас есть элемент A, то предыдущийЛекции по ЭВМ. Конспект.

Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год4элемент следующего за A элемента – это тоже A и следующий за предыдущим перед Aэлемент – тоже A:началоспискаконецспискаСклеив начало и конец списка получаем кольцевой список (он может быть какоднонаправленным, так и двунаправленным).Как правило, реализуют список с помощью ссылочной реализации. Для каждогоэлемента данных заводим указатели на следующий (и на предыдущий длядвунаправленных) элемент списка:NULLprevprevprevdatanextdatanextdatanextNULLКонцы списка либо закрывают указателями на ноль (NULL, как в данном примере),либо замыкают список в кольцо специальным выделенным элементом base, ничего нехранящим, но позволяющим упростить добавление/удаление элементов данных. Указателина base приравниваются в этом случае к указателям NULLПри добавлении/удалении элемента в такой список используется простая перестановкачасти указателей спискаПрименяются списки в тех случаях, когда необходимо хранить заранее неизвестноеколичество данных.

В частности, однонаправленного списка достаточно для реализациистека и очереди произвольной длины, а двунаправленный список легко реализует дек.1.3. ДеревьяДеревом называется структура данных, для каждого элемента которой (т.н. вершиныдерева) могут быть определены потомки (child). Если потомков у элемента нет, то элементназывается концевой вершиной. Кроме того, для всех вершин дерева, кроме одной («корня»(root) дерева) существует вершина, потомком которой является текущая вершина.Если у каждой вершины дерева не более 2х потомков, то дерево называется бинарным.В противном случае дерево называют произвольным.Используются деревья главным образом для ускорения операций поиска элемента.Реализация бинарного дерева очевидна – для каждого элемента дерева помимо данныхэтого элемента сохраняем указатели на «левого» и «правого» потомков, а также на«родителя» текущего элемента.Сложнее реализация произвольного дерева – в ней в каждом элементе дерева заводитсясписок указателей на потомков текущего элемента и указатель на родителя текущегоэлемента.Лекции по ЭВМ.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций