Лекции Булатицкий Дмитрий Иванович (во многом по материалам Прасолова А. Н.)
 Скачать 319.62 Kb.
|
Классификация ДСДПо способу обхода (доступа) можно выделить следующие виды ДСД: Список; Стек; Очередь; Очередь с приоритетом; Кольцевая очередь; Ассоциативный массив; По количеству связей элементов с «соседними» элементами: Односвязные; Двухсвязные; Многосвязные; По характеру связи: Линейные. В линейной динамической структуре данные связываются в цепочку. К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Нелинейные (деревья, графы). Из всего многообразия ДСД в рамках данной лекции рассмотрим только наиболее распространённые из них. CпискиСписком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных. Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем – NULL (nul, nil). Двусвязный список характеризуется наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий. Очевидный плюс тут в том, что от данного элемента структуры мы можем пойти в обе стороны. Таким образом упрощаются многие операции. Однако на указатели тратится дополнительная память. Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются. При работе с такими списками несколько упрощаются некоторые процедуры. Однако, при просмотре такого списка следует принять некоторых мер предосторожности, чтобы не попасть в бесконечный цикл. Cтек (LIFO)Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов. Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать). Полезными могут быть также вспомогательные операции: определение текущего числа элементов в стеке; очистка стека; неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций. Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению. Очередь (Queue, FIFO)Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO. Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение. Дек (DEQ)Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце. Операции над деком: включение элемента справа; включение элемента слева; исключение элемента справа; исключение элемента слева; определение размера; очистка. Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек. ДеревьяКаждая вершина дерева представляет собой структуру, имеющую информационное поле и указатели поддеревья, исходящие из этой вершины. Максимальное количество поддеревьев, сходящихся в одной вершине, называется порядком дерева. Если порядок дерева равен двум, то. Дерево называется бинарным. Интерфейс и реализация ДСД «Стек»Интерфейс ДСД «Стек»Как было показано ранее, основными операциями со над стеком являются вставка в стек и извлечение из него. К вспомогательным операциям относят: определение текущего числа элементов в стеке или проверка наличия елементов в стеке; очистку стека и неразрушающее чтение элемента из вершины стека; печать стека. С учётом необходимости управления динамической памятью необходимо также добавить следующие служебные операции: инициализация и уничтожение стека. Следует так проектировать интерфейс, чтобы избавить пользователя от ненужных ему подробностей внутреннего устройства разрабатываемой динамической структуры данных (как, впрочем, и других типов). Рассмотрим описание интерфейса стека на примере стека для хранения вещественных чисел. Тип хранимых элементов в дальнейшем может быть адаптирован для других практических задач. Поместим описание интерфейса стека в заголовочный файл «StackA.h»: #ifndef _STACK_A_H #define _STACK_A_H typedef struct { double *A; int l; int top; } StackA; int Push(StackA *s, double v); double Pop(StackA *s); double Peek(StackA const *s); int IsEmptyStack(StackA const *s); void Clear(StackA *s); void InitStack(StackA *s, int l); void PrintStack(StackA const *s); void Destruct(StackA *s); #endif Для предотвращения ошибки повторного определения типов при многократном (прямом или опосредованном) включении заголовочного файла обрамим его содержимое директивами условной компиляции. Реализация стека в массивеРассмотренный в предыдущем пункте интерфейс может быть реализован таким образом, что элементы стека будут храниться в динамическом массиве. Предложенная реализация показана в следующем листинге (поместим его в файл «StackA.c»): #include "stackA.h" void InitStack(StackA *s, int l) { if(s->A=(double *)malloc(sizeof(double)*l)) { s->l=l; } else s->l=-1; s->top=-1; } void PrintStack(StackA const *s) { int i; for(i=0; i<= s->top; i++) printf ("%-7.3lf ", (s->A)[i]); } void Destruct(StackA *s) { if(s->A) free(s->A); s->l=-1; s->top=-1; } int Push(StackA *s, double v) { if(s->top>=s->l-1) return 0; s->top++; s->A[s->top]=v; return 1; } double Pop(StackA *s) { if(s->top>=0) return s->A[s->top--]; else return 1e300; } double Peek(StackA const *s) { if(s->top>=0) return s->A[s->top]; else return 1e300; } void Clear(StackA *s) { s->top=-1; } int IsEmptyStack(StackA const *s) { if(s->top <0) return 1; else return 0; } Реализация ДСД «Стек» в виде связного спискаИногда удобнее представить список в виде связной структуры. Для возможности в программе одновременно работать со списками различной реализации, переопределим также и интерфейс с другим идентификатором типа. Поместим описание интерфейса стека в заголовочный файл «StackL.h»: #ifndef _STACK_L_H #define _STACK_L_H struct LE { double v; struct LE *next; }; typedef struct { struct LE *top; } StackL; int Push(StackL *s, double v); double Pop(StackL *s); double Peek(StackL const *s); int IsEmptyStack(StackL const *s); void Clear(StackL *s); void InitStack(StackL *s); void PrintStack(StackL const *s); void Destruct(StackL *s); #endif Реализацию поместим его в файл «StackL.c»: #include #include "StackL.h" void InitStack(StackL *s) { s->top=NULL; } int Push(StackL *s, double v) { struct LE *p=(struct LE *)malloc(sizeof(struct LE)); if(!p) return 0; p->next=s->top; p->v=v; s->top=p; return 1; } double Pop(StackL *s) { struct LE *p; double x=1e300; if(s->top) { p=s->top; s->top=s->top->next; x=p->v; free(p); } return x; } double Peek(StackL const *s) { if(s->top) return s->top->v; } int IsEmptyStack(StackL const *s) { return s->top==NULL; } void Clear(StackL *s) { while(!IsEmptyStack(s)) Pop(s); } void PrintStack(StackL const *s) { struct LE *p; for(p=s->top; p; p=p->next) printf("%-7.3lf ", p->v); } void Destruct(StackL *s) { Clear(s); } Пример работы со стеком: #include #include #include "stackL.h" int main(int argc, char *argv[]) { StackL a, b; int i; double x; InitStack(&a); Push(&a, 1.1); Push(&a, 2.2); printf ("Enter value to push: "); scanf("%lf", &x); Push(&a, x); PrintStack(&a); for (i=0; i<5; i++) printf("\n Extracted %-7.3lf\n", Pop(&a)); PrintStack(&a); Destruct(&a); system("PAUSE"); return 0; } Замечание: для оптимизации работы с памятью и упрощения примера интерфейс стека в массиве рассмотренный ранее при инициализации предполагает дополнительный по сравнению с предложенным в данном примере интерфейсом стека в связном списке. Тем не менее этого можно избежать, выделяя при инициализации стека массив из какого-то предопределённого числа элементов. В дальнейшем, если такой длины будет недостаточно, память можно выделить повторно с помощью realloc, увеличив её объём. ЗаключениеОсновные направления и тенденции развития языков программирования и технологии конструирования программПотребность в решении более сложных и разнообразных задач. Первые ЭВМ имели ограниченные возможности, следовательно, и программы были простыми. В процессе эволюции вычислительной техники от нее требовалось решение все более сложных и разнообразных задач. Следовательно, язык программирования должен был позволять писать программы для решения этих новых задач. Это способствовало появлению и развитию в языках программирования различных новых технологий. Например, пользуется широкой популярностью технология объектно-ориентированного программирования. Программы становились сложнее и больше по объему. Появилось стремление к повышению эффективности процесса создания программ. Поэтому существует тенденция в развитии языков программирования к быстрому написанию программ. Здесь также следует отметить появление множества систем визуального программирования, в какой-то степени облегчающие труд программиста. Желание, чтобы программы работали на разных платформах, привело к развитию независимости от ЭВМ языков системного программирования. Языки системного программирования, на которых создаются операционные системы, трансляторы и другие системные программы, развиваются в направлении независимости от ЭВМ. Так, например, большая часть операционных систем написана на языке C, а не на ассемблере. Например, операционная система Unix практически полностью написана на C. Большие проекты предусматривают совместный труд множества программистов. В возможности легкой командной работы хорошо себя зарекомендовала технология объектно-ориентированного программирования. Поэтому большинство современных языков программирования поддерживают ООП. В общем, языки программирования развиваются в сторону все большей абстракции от реальных машинных команд. И самым очевидным преимуществом здесь является увеличение скорости разработки программы. Также повышению скорости разработки программ способствует автоматизация написания программ. Среди подходов к автоматизации создания программ можно выделить наиболее распространённый – визуальное программирование. Суть визуального программирования заключается в том, что среда разработки берет на себя большую часть рутинной работы по организации инфраструктуры программы для взаимодействия её частей, оставляя программисту работу по визуальному конструированию диалоговых окон и заполнению функций обработки предопределённых событий. Получающиеся приложения являются интерактивными системами, в которых для организации взаимодействия между пользователем и программой используются методы (подпрограммы), управляемые событиями. Объектно-ориентированное программирование — это методология программирования, которая основана на представлении программы в виде совокупности объектов, каждый из которых является реализацией определенного класса (типа особого вида), а классы образуют иерархию, основанную на принципах наследуемости. При этом объект характеризуется как совокупностью всех своих свойств и их текущих значений, так и совокупностью допустимых для данного объекта действий. Несмотря на то что в различных источниках делается акцент на те или иные особенности внедрения и применения ООП, три основных (базовых) понятия ООП остаются неизменными. К ним относятся: • наследование (Inheritance); • инкапсуляция (Encapsulation); • полиморфизм (Polymorphism). Эти понятия как три кита лежат в основе ООП. При процедурном подходе требуется описать каждый шаг, каждое действие алгоритма для достижения конечного результата. В отличие от него объектно-ориентированный подход оставляет за объектом право решать, как отреагировать и что сделать в ответ на поступивший вызов. |