Структурированные ТД

Чаще всего, из структурированных типов данных встречается массив.

Массив это упорядоченный набор данных одного типа.Для хранения данных, например, чисел, используются переменные. Каждая переменная должна иметь собственное имя. Если данных немного, проблем нет. Но если потребуется хранить сотню чисел, попробуйте не заблудиться среди сотни имен. Использование массива дает всем числам одно имя, отличаются числа друг от друга по индексу – номеру.

Способ представления (хранения) массива требует уточнений. Каждый раз, когда мы собираемся использовать массив, нужно указывать: тип элементов (что храним в массиве); размерность (сколько индексов выделяют один элемент массива); величина (диапазон изменения каждого индекса).

Определяя массив в языке BASIC, пишем служебное слово dim, после которого указываем имя массива. Тип элементов указывается значком %,!, #, $. Размерность определяет количество чисел в скобках. Сами числа – это наибольшее значение индекса. Начальное значение индекса – 0. Наибольшая размерность массивов – 2. По умолчанию, элементы массива – действительные числа.Следует отметить, что если массив одномерный и в нем не больше 10 элементов, то его объявление не обязательно. То есть использование команды DIM не требуется.

BASIC

dim <имя><тип элементов>(<дополнительная информация>)

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

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

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

PASCAL

<имя>:array[<дополнительная информация>] of <тип элементов>

Ввод и вывод массивов обычно происходит поэлементно.

Основные операции – это обращение по индексам для запоминания или считывания значений элементов.

В языке Pascal можно выполнять оператор присваивания с массивами и задать константу-массив.

Обобщения массива.

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

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

В записях требует уточнений: количество и тип полей.

Как это оформляется в языке pascal показано ниже.

Структурированные типы данных - запись

PASCAL <имя записи>:record

<имя поля>:<тип поля>;

<имя поля>:<тип поля>;

...

end;

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

Основной операцией при работе с записями является обращение по именам к значениям полей для запоминания или считывания.При оформлении, после имени самой записи ставится точка, затем имя поля.PASCAL <имя записи>.<имя поля>Элементы записи могут быть любого типа (кроме файлового), в том числе и массивы, и другие записи.Оформление в языке программирования PASCAL:

Пусть имеем перечислимый тип t1.

Тогда <имя типа> = set of t1; определяет множество.

* Способ образования.Элементы нового типа - группы выбранных элементов (в том числе и пустое множество) типа t1..Операции над множествами в языке PASCAL

пересечение множеств a и b a*b

объединение множеств a и b a+b

разность множеств a и b a-b

Для множеств возможны:

Проверка на равенство множеств a и b a=b

Проверка на неравенство множеств a и b a<>b

Проверка, является ли a подмножеством от b a<=b, b>=a

Проверка на принадлежность элемента e множеству a e in a

Все проверки дают результат логического типа.

Динамические ТД

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

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (NIL).Чтобы список существовал, надо определить указатель на его начало. Опишем переменные:

Var и, х: EXS;

Создадим первый элемент:

New(u); {выделим место в памяти для переменной типа S}

u^.next:=nil; {указатель пуст} и^.data:=3; {информационное поле первого элемента}

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

х:=и; {Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом.}

New(x^.Next)•, {выделим область памяти для следующего элемента списка}

x:=x^.Next; {переменная х принимает значение адреса выделенной области памяти}

x^.Data:=5; {определим значение этого элемента списка} x^.Next.=Nil:

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

Procedure Init(Var u: Exs); {создание списка}
Var х, у: Exs; Digit: Integer; {значение информационной части элемента списка}
Begin
Writeln('Введите список '); u:=Nil; {список пуст}
WriteLn('Bводите элементы списка. Конец ввода 0);
Read(Digit);
While Digit<>0 Do
Begin
New(y); {формирование элемента списка} y^.Nexf:=Nil; y^.Data:=Digit;
If u=nil Then u:=y {вставляем первый элемент списка}
Else x^.Next:=y; {вставляем элемент в конец списка}
х:=у; {переносим значение указателя на последний элемент списка}
Read(Digit);
End;
Writein;
End;
Итак, мы построили список добавлением элементов в конец списка. Вставим элемент со значением 7 в начало списка.

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

Напишем фрагмент программы:

х:=и; {запомним адрес первого элемента списка}
u:=u^.next; {теперь и указывает на второй элемент списка}
Dispose(x); {освободим память, занятую переменной х^}

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

Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним. х:=и; {переменная х для хранения адреса удаляемого элемента}

{найдем адреса нужных элементов списка }
While (x<>Nil) And (x^.Data<>Digit) Do Begin dx:=x; x:=x^.Next End;

dx^.Next:=x^.Next; Dispose(x);

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

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

{найдем предпоследний элемент} х:=и; ах:=и;

While x^.Next<>NIL Do Begin dx:=x; x:=x^.Next; End;

{удаляем элемент х^ из списка и освобождаем занимаемую им память} dx^.Next:= Nil; Dispose(x);

Стек

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

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

Основные операции со стеками

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

Дадим новое определение стека. Стек — это список, в котором добавление новых элементов и извлечение имеющихся происходит с начала (или конца) списка.

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

Таким образом, описать стек можно следующим образом:

Type EXST=^ST;

ST=Record Data: Integer; Next: EXST; End;

Var Stack: EXST; {текущая переменная}

Тогда, если стек пуст, то значением указателя равно NIL.

Занесение в стек

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

Занесение в стек производится аналогично вставке нового элемента в начало списка:

Procedure WriteStack (Var ir.EXST; digit: Integer);
{запись в стек} Var x:.EXST;
Begin
New(x); {создание нового элемента стека} x^.Data:=diglt; х^.Nехt:=u
{созданный элемент определить как вершину стека} u:=х;
End;
Основная программа формирования стека будет иметь вид:
Var Stack: EXST; {текущая переменная} digit: Integer;
Begin
Stack:=Nil;
WriteLn(¹'Введите элементы стека. Окончание ввода — О'); Read(Digit);
While Digit<>O Do Begin WriteStack(Stack, digit); Read(digit); End
End.

Извлечение элемента из стека.

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

Procedure ReadStack(Var u-.EXST; Var i-.Integer); Var x: EXST;
Begin
i:u^.Data; x:=u; u:=u^.Next; Dlspose(x);
End;

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека. function Free(u:EXST):Boolean;

Очереди

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

Очередь является динамической структурой — с течением времени изменяется и ее длина, и набор составляющих ее элементов. Поэтому удобно представить ее в виде списка.

Описание очереди на языке программирования:

Type ЕХО=^О; O =Record Data: Integer; Next: EXO; End;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

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

Var xl, х2: EXO;

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

Поскольку очередь представлена списком, занесение элемента в очередь соответствует занесению элемента в конец списка.

Procedure WriteO (Var xl,x2: EXO; с: Integer); Var и: EXO;
Begin
New(u); u^.data:=c; u^.nexf:=^NIL;
If xl=NIL Then xl:=u {если очередь пуста}
Else x2^.next:=u; {заносим элемент в конец списка} х2:=u;
End;

Основная программа, создающая очередь, может быть такой:

Begin
xl:=NIL; x2:=NIL;
Write Ln('Введите элементы очереди. Конец ввода — О'); Read(Digit);
While Digit<>O Do Begin WriteO(xl,x2,Digit); Read(Digit); End
End.

Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка.

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

Procedure Reado(Var xl,x2:EXO; Var c:Integer); Var u:ЕХО;
Function Nul (xl: ЕХО): Boolean; Begin Nul:=(xl=Nil); End;
Begin
If Nul(xl) Then Writeln(‘0чepeдь пуста') Else
Begin c:=xl^.Data; u:=xl; xl:=xl^.Next; Dispose(u); End;
End;

Деревья

Введение основных понятий

Граф — это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.

Если на каждом ребре задать направление, то граф будет ориентированный.

Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем. Замкнутый путь, состоящий из различных ребер, называется циклом.Граф называется связным, если любые две его вершины соединены путём. Связный граф без циклов называется деревом. На рис. 54 изображено дерево, в узлах которого располагаются символы.

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

Для дальнейшей работы с деревьями необходимо определить ряд понятий.

• Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.

• Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.

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

• Степенью дерева называется максимальная степень всех вершин. Например:

• вершины F, D, Е являются непосредственными потомками вершины В;

• вершины F, D, Е являются листьями;

• вершины С, G, Н — внутренние;

• степень вершины В — 3, а вершины Н — 1;

• степень дерева равна 3.

Двоичное дерево — это дерево, в котором из каждой вершины исходит не более двух ребер.

6.2. Представление деревьев

Дерево — это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

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

Type TreeLink =^Tree;

Tree=Record

Data: <mun данных>;

Left, Right: TreeLink;

End;

Корень дерева опишем в разделе описания переменных:

Var kd: TreeLink;

6.3. Основные операции над деревом

К основным операциям над деревьями относятся:

• занесение элемента в дерево;

• обход дерева;

• удаление элемента из дерева. Рассмотрим вставку и обход дерева на примере следующей задачи.

6.5. Удаление из дерева

Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной (рис. 55) или из нее выходит только одно ребро (рис. 56). Для этого нужно изменить соответствующую ссылку у предшествующей вершины.

Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины (рис. 57). Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая:

• удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка);

• удаляемая вершина имеет не более одного поддерева (0 или 1);

• удаляемой вершины в дереве нет. Ниже приведена рекурсивная процедура deltree, решающая поставленную задачу. Она отыскивает элемент с заданным ключом и удаляет его.

В процедуре deltree описана вспомогательная процедура dl, которая работает только в первом из трех перечисленных случаев.Вспомогательная процедура dl "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.

19.

20.Дисциплина программирования, структурный подход программирования. Возникновение объектно –ориентированного программирования. Цели структурного программирования:1)Обеспечение дисциплины программирования (“Структурное программирование-это дисциплина, которую программист навязывает сам себе”- Э. Дейкстра); 2)Повышение эффективности (например, разбиение на относительно независимые модули);3)Повышение надежности (облегчение тестирования и отладки);4)Уменьшение времени и стоимости (повышение производительности программистов); 5)Улучшение читабельности программы Основные принципы структурного подхода:1)Принцип абстракции позволяет рассматривать программу по уровням. Верхний уровень показывает детали реализации (например, восходящее и нисходящие стратегии программирования).2)Разделение программы на отдельные фрагменты (методы), которые просты по управлению и допускают независимую откладку и тестирование 3)Строгий методический подход (принцип формальности) позволяет изучать программы (алгоритмы) как математические объекты, ускорить принятия решений, избежать ошибок Структурный подход включает в себя три основные составные части:1)Нисходящее проектирование;2)Структурное программирование;3)Сквозной структурный контроль. Объе́ктно-ориенти́рованное программи́рование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов (либо, в менее известном варианте языков с прототипированием — прототипов). Класс — это тип, описывающий устройство объектов — экземпляров. Класс можно сравнить с чертежом, согласно которому создаются объекты. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.Прототип — это образцовый объект, по образу и подобию которого создаются другие объекты.Объектное и объектно-ориентированное программирование (ООП) возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в современном объектно-ориентированном программировании часто большое значение имеют понятия события (так называемое событийно-ориентированное программирование) и компонента (компонентное программирование).Объектно-ориентированное программирование в настоящее время является абсолютным лидером в области прикладного программирования (языки Java, C#, C++, JavaScript, ActionScript и др.). В то же время в области системного программирования до сих пор лидирует парадигма процедурного программирования, и основным языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние стали оказывать языки объектно-ориентированного программирования. Исторически сложилось так, что программирование возникло и развивалось как процедурное программирование, которое предполагает, что основой программы является алгоритм, процедура обработки данных. Объектно-ориентированное программирование - это методика разработки программ, в основе которой лежит понятие объекта как некоторой структуры, описывающей объект реального мира, его поведение. Задача, решаемая с использованием методики объектно-ориентированного программирования, описывается в терминах объектов и операций над ними, а программа при таком подходе представляет собой набор объектов и связей между ними. Другими словами можно сказать, что объектно-ориентированное программирование представляет собой метод программирования, который весьма близко напоминает наше поведение. Оно является естественной эволюцией более ранних нововведений в разработке языков программирования. Объектно-ориентированное программирование является более структурным, чем все предыдущие разработки, касающиеся структурного программирования. Оно также является более модульным и более абстрактным, чем предыдущие попытки абстрагирования данных и переноса деталей программирования на внутренний уровень.

21. Классификация программного обеспечения.Языки программирования и их классификация. Метаязыки. Парадигмы и технологии программирования. Трансляторы и их виды. Программное обеспечение-это совокупность программ, выполненных вычислительной системой. К программному обеспечению (ПО) относится также вся область деятельности по проектированию и разработке (ПО): технология проектирования программ (нисходящее проектирование, структурное программирование и др.); методы тестирования программ; методы доказательства правильности программ; анализ качества работы программ и др.

Программное обеспечение - неотъемлемая часть ЭВМ. Оно является логическим продолжением технических средств ЭВМ, расширяющие их возможности и сферу использования.

Классификация программного обеспечения: -системное програмное обеспечение; -прикладное програмное обеспечение;-инструментарий программирования. Существует три категории: 1) Прикладные программы, непосредственно обеспечивающие выполнение необходимых пользователям работ.2) Системные программы: управление ресурсами ЭВМ;создание копий используемой информации; проверку работоспособности устройств компьютера;выдачу справочной информации о компьютере и др.. 3) Инструментальные программные системы, облегчающие процесс создания новых программ для компьютера. Более или менее определенно сложились следующие группы программного обеспечения: операционные системы. системы программирования, инструментальные системы, интегрированные пакеты,динамические электронные таблицы,системы машинной графики,системы управления базами данных (СУБД),прикладное программное обеспечение.