лекция 9 (1161104)
Текст из файла
Языки программирования. Лекция 9
Составные ТД( продолжение)
Массивы
Основные отличия в реализации массивов – насколько могут быть динамичными:
- базовые типы элементов ( связываются с объектом данных в объявлении во всех яп)
- границы диапазона
- длина
В языке Ада есть понятие "динамический" массива (на самом деле он квазистатический, т.е. он не является неограниченным, но у него границы - динамические атрибуты) . Объекты данных могут появляться только внутри блоков.
X:A range 0..20
Т.о. можно написать
PROCEDURE P(N:INTEGER)
X: array (1..N) of Real;
....
begin
end P;
Менять свои размеры внутри функции массив X не может, но он переменный (зависит от параметра функции).
В современных языках массивы:
-
границы от 0 и являются неотрицательными индексами;
-
длина- исключительно динамическая;
-
переменная типа массив- динамическая;
Ссылки
В языке Java все тд делятся на:
- Простые
- Референциальные (доступ к ним осуществляется только по ссылке) - это массивы, классы и интерфейсы .
В С# тоже самое + структурные типы данных( кроме простых).
Для референциальных тд (Cи#, Java, Delphi и т.д.):
- объекты отводятся только в куче
-имя для объектов является ссылкой: если в
X:I - I - объект, то Х - ссылка на такой объект.
Массивы:
C x;
int [] a;
a = new int [10];
Присваивание:
T[] a;
T[] b;
b = new T [100];
a = b; // копирование ссылок, а не массивов!
Длина- динамический атрибут.
Для изменения длины массива используется метод a.SetLength().
С точки зрения производительности: реализация таких массивов немного менее эффективна, но, т.к. все объекты находятся в ОП, накладными расходами можно пренебречь.
Вопрос вырезки из массивов (получения подмножества элементов массива).
В языке фортран 90 самые “ богатые” вырезки.
A[50][50];
A[1][*]; - Первая строка матрицы
A[*][3]; - Третий столбец матрицы
А[3][5..10]- вырезка
Таким образом, мы можем получить произвольный прямоугольник матрицы.
Из относительно современных ЯП такое понятие вырезки есть только языке Ада:
array (1..20, 1..30) of T
A(2..6, 3..4)- только смежные вырезки!
В современных языках понятие вырезки отсутствует из-за неэффективности,
В С++ перенесено в библиотеку STL- ValArray. Тенденция оформлять технологические конструкции, полезные ограниченной группе пользователей , в стандартные библиотеки.
Многомерные массивы
Многомерный массив в конечном итоге сводится к одномерному вектору
A[50][60]
Быстрее меняется правый индекс (если вытянуть этот массив в строчку).
C#, Java:
int [ , ] a; - двумерный массив ( границы –динамические атрибуты)
a = new int [3][4]; - инициализация массива.
int[] b = {1, 2, 3};- одномерный массив( отведение памяти)
int[,] c = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}}; -двумерный массив ( отведение памяти)
Причем массив только прямоугольный.
В языке C# появился новый тип массивов - Jagged-массивы ("ступенчатые массивы" - вектора из указателей на другие массивы).
Пример:
int [][] a;- двумерный ступенчатый массив
Инициализация
a = new int[][4];- память под 4 элемента
a[0] = new int [3];
a[1] = new int [8];
a[2] = new int [0];- ссылка на массив длины 0!
Подмассивы имеют произвольную длину.
Можно моделировать треугольные массивы, разреженные матрицы и т.д.
Jagged-массивы делают реализацию подобных массивов наиболее эффективно.
В С++ можно воспользоваться классами для реализации подобных массивов.
Записи
Запись - агрегат из разнотипных записей.
T1xT2x...xTn
Для записей применим операция точка - доступ к полям записи.
R.имя_поля
Если бы операцию точка можно было бы перекрыть в С, то она возвращала бы ссылку.
Какое связывание у этой операции: статическое или динамическое?
Статическое - .имя_поля в языке ассемблера транслируется в смещение адреса.
В языке JavaScript подобного рода операция имеет динамическое связывание! Поскольку каждый объект данных в нём имеет тип класса, у которого есть свойства, т.о. если при выполнении операции R.имя_поля имени поля нет, то оно создаётся, если существует - то вычисляем доступ.
Т.о. точка:
-
доступ
-
создание свойства
5.new_prop = 1 - добавляем к целому типу данных новое свойство.
Запись вида R.имя тождественна R["имя"]
-
можно вычислять адреса полей,
-
разница между массивом и записью пропадает (можно добавлять свойства)
Такое осуществляется при существенной потери эффективности, которая JavaScript и не нужна.
Из соображений эффективности в современных языках операция точка - статическая.
В остальном записи в современных ЯП замещены понятием класса.
Структуры
Чем структура Си отличается от структуры Си++?
Тэги:
struct S {...};
union S;-объединение
enum S;- перечисление
Характеризуются
-имя подчиняется общим правилам идентификаторов
-образуют собственное пространство имен(Общие правила видимости и доступа не распространяются на них )
Пример:
struct S{
{
int a, b;//- у а область видимости struct S
} x;
int a;//-область видимости struct S
} s;
Ведено два типа: struct S и struct C.
int a; -глобальная переменная
struct S x;
x.a;- переменная из S
x.x.a;- переменная из С
Все имена тэгов собраны в единое пространство имен (неструктурированное), никакого отношения к обычным именам не имеют.
Пример:
struct time{...}// системное время
struct time time(...) - независимость пространства тегов и пространства имён ( название функции совпадает с именем структуры). Этим активно пользовались программисты на UNIX'ах.
Отличие:
struct C{}
В Си - только имя структуры struct C s;.
В Си++ struct C- имя типа C s; ( но если тег конфликтует с другим именем, то
struct C s;.)
В Си++ структура и класс отличаются только умолчанием прав доступа: в структурах по умолчанию public, а в классах - private.
Умолчание работает при:
-объявлении членов;
-наследование;
В остальном отличий нет!
В Java понятие структуры нет, его обобщает понятие класса.
В языке С# тоже есть понятие структуры, но оно уже очень сильно отличается от понятия класса. Структура - это урезанный класс.
Все типы Cи# делятся на:
1) значащие типы (типа значения; простые типы данных и структуры);
Выделение памяти- непосредственно при объявлении.
Если объект значащего блока внутри функции - выделение памяти в стеке. Если внутри класса - выделение памяти будет в куче.
Точно так же вместо объявления класса может стоять имя структуры. Увидев имя структуры, компилятор сразу будет выделять под неё память (а не создавать ссылку, как для классов).
Ограничения на структуры:
-Структура не может наследоваться и не может быть унаследована ни от чего (кроме типа Object).
-В структуре нельзя явно определять конструктор умолчания.( все объекты инициализируются неопределенным значением- любой доступ к ним ошибочен. NULL не является неопределенным значением!!! Автоматически генерируемый конструктор класса как раз и присваивает полям эти неопределённые значения.
Перекрывая конструктор умолчания, мы не гарантируем, что все поля будут инициализированы из соображений надежности и эффективности нельзя явно определять конструктор умолчания.)
2)референциальные (классы, массивы и интерфейсы)(располагаются в куче)
Момент размещения объекта в памяти выбирает сам программист при помощи операции new (за одним исключением - при инициализации массивов int []х={1,2,3} – new вызывается неявно) имя – ссылка.
Рразрешены только операции: точка и присваивание;
Опрация присвивания только копирует ссылки. И в таких ЯП должна быть операция для копирования объектов - операция типа Clone().
Пример:
Class T{
X a;
}
Если Х- класс, то а –ссылка на какой-то другой объект, который должен появиться с помощью оператора new.
Если Х- структура, то по объект а выделяется память:
Причины:
C# сгенерирован так, чтобы он претендовал на тотальный ЯП. Структуры в него введены только с целью эффективности. Разработчиками приводился пример, явно ссылающийся на язык Java для класса точки Point( некоторая структура с полями x,y и кучей методов, наследовать от Point не надо):
Point Java:
Point[] p = new Point[1000];- 1000 ссылок;
Инициализация:
p[i] = new Point(); - создаём 1000 объектов + 1000 указателей - большая неэффективность.
Уничтожение: 1001раз освободить.
С#:
P[I]=new Point();
Уничтожение: освободить кусок памяти.
Но появляется проблема, возникающая и с простыми типами данных:
Нам необходим специальный механизм - boxing и unboxing - для простого типа данных существует аналогичный класс (Integer, Int32 для int, Boolean для bool и т.д.). Эти классы-обертки наследуются от Object.
object []p; - массив, который может держать в себе любой объект языка, возможно при помощи ф-ий boxing и unboxing, преобразующих значащие типы в объектные.
Пример:
p[0] = 3 - обёртка объекта 3 в класс (С # производится новый объект типа Int32 и ссылка на этот объект кладётся в массив [0]).
x- имя структуры.
p[0] = x;- упаковка структуры в специальный тд, образуется специальный объект и ссылка кладется в массив.
x = p[0]; // ошибка, производному присвоить базовый нельзя!!!
x = (X) p[0]; // правильно, приведение типа.
х - не объект, это структура.
Обёртка происходит, и когда мы передаём объекты как параметры функции.
void f(Object o);
Параметр- любой тд языка.
Объединения
В записи мы указываем несколько вариантов структуры, располагающихся в одном месте памяти.
Это:
- union (Си)
- записи с вариантами (Паскаль)
В современных ЯП записей с вариантами нет:
Запись с вариантами - постоянная часть и вариантная часть.
Объединения :
-
размеченные (в постоянной части выделяется поле - дискриминант, в зависимости от значения которого выбирается вариант, по какому варианту отведена память)
-
неразмеченные (поле-дискриминант отсутствует, память может отведена по короткому варианту, а мы считаем, что по самому длинному залезаем в чужую память ). Существенно понижают надежность.
Паскаль и Модула-2 допускают оба типа, язык Ада - только размеченные( значение дискриминанта меняться не может).
В современных ЯП нет объединений - всё реализуется при помощи наследования:
class P;- постоянная часть
class T1:P; - вариант Т1
class T2:P; - вариант Т2
.......
class T4:P; - вариант Т4
Множества
Множество – контейнер, у которого есть базовый тип Т.
Над множеством определены операции:
- принадлежности,
- добавления,
- исключения,
- объединения,
- вычитания.
Впервые появились в языке Паскаль.
Решето Эратосфена (алгоритм определения простых чисел) - помещаем в решето 1000 чисел (от 0 до 1000) и постепенно выкидываем числа (берём меньшее и выкидываем числа, которые делятся на это меньшее).
X: set of T;
S := S + [x]; - включение в мн-во incl
S := S - [x]; иcключение excl
X in S –принадлежность.
В большинстве реализаций Паскаля множества ограничены размерами 16, 32, 64 (разрядность) в большинстве реализаций задача работать не будет.
Реализация множеств в Паскале:
Тип Т- дискретный, мощность варьируется 16, 32, 64. тип данных Т сводится в диапазон :
T => 0.. N-1 (любой дискретный тип можно свести)
N - разрядность максимальной ячейки памяти, адресуемой на данной машине.
0 бит –0 элемент…N-1бит - N-1 элемент
-
элемент присутствует
-
нет
0 i N-1
| 1 | 0 | 0 |
+- побитовое “или”
В связи с простотой подобной реализации операции с множествами сводятся к одной машинной операции ( +- побитовое “или”).
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
