русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Односвязные и двусвязные списки.

Список – это совокупность объектов или элементов списка, в котором каждый объект содержит информацию о местоположении связанного с ним объекта. Если список располагается в оперативной памяти, то, как правило, информация для поиска следующего объекта – это указатель, адрес памяти. Если связанный список хранится на диске в файле, то информация о следующем элементе может включать смещение элемента от начала файла, положению указателя записи или считывание файла, ключ записи и любую другую информацию, позволяющую однозначно отыскать следующий элемент списка.

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

 
 

Рис. Односвязного списка.

Элемент односвязного списка включает только указатель на следующий элемент.

typedef struct {

char name [20];//автор книги

char title [44];//наименование

int year;//год издания

float price;//цена

}book;

struct list {

struct list *next;//указатель на следующий элемент

book info;//информационные поля

};

Предполагается, что память, отводимая под элемент списка, выделяется динамически, поэтому при реализации списков памяти его длина ограничивается только доступным объёмом памяти. Информационное поле представляет собой структурную переменную по шаблону book. Признаком последующего элемента списка является равенство на NULL поля next. Реализация односвязного списка требует наличия операций add() – добавление элементов в список, detach() – удаление элемента из списка, destroy() – освобождение памяти, занятой элементом списка. Помимо этих основных операций могут реализовываться и другие операции:

Display( ) вывод по порядку всех элементов списка

PrintOn( ) вывод заданного элемента списка

HasMember( ) определение того содержится ли в списке элемент

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

 
 

Пример.

Альтернативой односвязному списку является двунаправленный (двусвязный) список, позволяющий выполнять «движение» от элемента к элементу в обоих направлениях. В этом случае элемент включает 2 указателя: на предыдущий и следующий элементы списка.

А так как список имеет и начало, и конец, описываются 2 указателя головы и хвоста списка. Элемент двусвязного списка содержит 2 указателя и информационные поля.

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

 
 

struct dlist{

struct dlist *next; //указатель на следующий элемент

BOOK *info; //информационные поля

struct dlist *prev; //указатель на предыдущий элемент

};

struct dlist *heed; //указатель на 1 элемент списка

struct dlist *tail; //указатель на последний элемент

Признаком на 1 элемент могут служить равенство на NULL указателя prev. Признаком последнего элемента является next=NULL. Число операций, определяемых для двусвязного списка, значительно больше, чем для односвязного, может включать:

add( ) – добавление нового элемента к списку. По умолчанию принимают, что добавление применяется в начало списка;

addAtHead ( ) – добавление элемента в начало списка;

addAtTail ( ) – добавление элемента в конец списка;

AestroyFromHead () – освобождение памяти, выделенной для данного элемента, поиск которого выполняется от начала;

AestroyFromTeil () – освобождение с поиском конца;

detach ( ) – удаление данного элемента из списка. По умолчанию обычно принимают, что поиск элемента от начала списка;

detachFromHead () – удаление элемента из списка с поиском от начала списка;

detachFromTail () – удаление элемента из списка с поиском от конца списка.

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

Просмотров: 1378


Вернуться в оглавление



Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.