ИГА. Понятие базы данных
 Скачать 0.77 Mb.
|
Линейные списки.Линейный список представляет собой способ организации данных в памяти, поэтому его определение достаточно широко: линейный список – это множество размером n≥0 узлов x[1], x[2], … x[n], структурные свойства которого ограничиваются одномерным относительным положением узлов, т.е. теми условиями, что если n > 0 , то x[1] является первым узлом; если 1 В общем определении, связный список - это набор данных, которые последовательно связаны между собой. Однако в практическом программировании элементы списка не представляют собой разнородные данные и всегда определены заранее. Пример реализации элемента на языке программирования «C»:   На рис 1 и 2 приведён пример реализации и схему связей частного случая связного списка «Односвязный список». Каждый элемент списка указывает на полезные данные (data) и на следующий элемент (next). Этот пример хорошо показывает, что, по сути, элементы одинаковы, поэтому мы склонны уточнить и дать следующее определение линейному списку: Линейный список – набор данных, состоящий из элементов одного типа, связанных между собой. В этой главе будут изучены три примера реализации связных списков: «Однонаправленный список», «Двунаправленный список» и «Замкнутый список». В этой главе приведены понятия, общие для этих реализаций. Преимущество списков над массивами в том, что они могут изменять свой размер (количество элементов) в процессе выполнения программы. К достоинствам списков относятся: [1][2] Лёгкость реализации добавления и удаления элементов Размер ограничен только параметрами компьютера (размер ОЗУ, разрядность) Относительная статичных массивов лёгкость реорганизации данных внутри списка Как видно из вышеприведённого примера реализации элемента, создание списка сопровождается дополнительными расходами ОЗУ для хранения указателей (в данном случае: указатель на следующий элемент). Более того, видно, что невозможно определить состав данных без непосредственного обращения к ним внутри элемента, что усложняет реализацию поиска и сортировки. Поэтому выделяются следующие недостатки связных списков [3][4][5]: Расход памяти на элементы-указатели. Для обращения к элементу списка по его номеру требуется пройти цепочку из предыдущих элементов Данные могут располагаться нелинейно, что приводит к фрагментации и может негативно отразиться на быстродействии программы Потенциальное обращение к разным страницам в памяти при прохождении списка. Исходя из вышесказанного, при разработке программ с использованием списков необходимо учитывать следующую особенность: в статической памяти расположен указатель на главное звено, а сам список расположен в динамически распределяемой памяти. Это важно учитывать, т.к. невозможно применить к спискам некоторые методы программирования. Например, язык «С» и его наследник «С++» гарантируют, что два массива одного размера [2][12], состоящий из данных одного размера, будут занимать в ОЗУ одинаковое количество памяти. Поэтому для копирования одного массива в другой можно избежать использования цикла прохождения по всему массиву с присваиванием и использовать функцию memcpy [12]. Функция скопирует память одного массива и наложит поверх другого. Результатом будут два одинаковых по содержанию массива. Этот метод невозможен со связными списками, т.к. данные расположены не в статической памяти, а в динамической памяти линейность их расположения не гарантируется. Для всех связных списков, игнорируя детали реализации, важно выделить следующие понятия: [1] Начальный элемент – элемент, на который указывает указатель начала списка Конечный элемент – элемент, который не указывает на следующий элемент списка1 Текущий элемент – элемент, на который указывает рабочий указатель. Единственно доступный к обработке элемент в текущий момент Для связных списков выделяются следующие, общие базовые для всех реализаций, операции: [1][2] Создание нулевого (пустого) списка Проверка на пустоту Проверка на существование следующего элемента Извлечение данных текущего элемента Удаление элемента и взятие следующего как текущего Вставка нового элемента после текущего Проход по списку Конкатенация и разбиение списка Очистка На основе базовых операций реализуются следующие операции2 [4][20]: Поиск элемента Перестановка элементов местами Реверсирование списка Сортировка Важно учесть, что не всегда статические массивы занимают меньше памяти, чем динамические структуры. В практике программирования встречаются случаи, когда программа не может полностью использовать выделенную ей память. Например: массив, который должен быть списком имён сотрудников (с заранее известным количеством элементов). Каждая ячейка массива – это строка размером 12 байт (по заранее известному самому длинному имени среди сотрудников). Здесь и возникает проблема: памяти выделено больше, чем нужно этому словарю, т.к. не все имена сотрудников занимают все 12 байт, поэтому получается большое количество памяти, которое фактически не используется, а могло бы содержать в себе указатель на следующий элемент, чтобы стать связным списком. В этом случае, связный список займёт меньше памяти [10]. Массивы так же имеют преимущества в скорости доступа к произвольным элементам, в то время как в случае связных списков необходимо двигаться последовательно. Однако, в случае, когда нет необходимости в постоянном обращении к произвольным участкам, связные списки могут оказаться эффективнее, т.к. в зависимости от реализации можно не проходить весь список, а запомнить позицию, которая нужна, и не проходить весь список с начала. Таким образом, на программиста ложится серьёзная задача по выбору методов организации данных программы. Нельзя дать универсального ответа, что лучше. Как это часто случается в программировании, всё зависит от деталей задачи. |