русс | укр

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

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

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

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


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

Линейный односвязный список


Дата добавления: 2013-12-23; просмотров: 2647; Нарушение авторских прав


 

Линейный односвязный список является самым простым видом связных списков. Такой список можно определить с помощью описаний типов (см. пример 1).

Процедуры работы с линейным односвязным списком на языке Паскаль

Type

rel1=^elem; (* Указатель на запись *)

elem=record

next:rel1;

data:<Тип хранимых данных> (* Любой допустимый тип данных *)

end;

var

L1:rel1;

Для того, чтобы такие операции, как добавление или удаление звена, выполнялись одинаково, независимо от места их выполнения в списке, удобно использовать ведущее или заглавное звено - самое первое звено списка, в котором не обязаны храниться полезные данные. Его создание для односвязного списка можно осуществить следующим образом:

 

var a, L1:list1;

begin

...

new(L1);

L1^.next:=nil;

a:=L1;

...

 

Указатель на начало списка L1, значением которого является адрес ведущего звена, представляет список как единый программный объект.

 

Указатель на следующий элемент в последнем звене списка имеет значение nil (NULL или просто 0 в Си/Си++), что является признаком линейного списка.

 

procedure insert1(link:rel1;info:<Тип>);

var q:rel1;

begin

new(q);

q^.data:=info;

q^.next:=link^.next;

link^.next:=q

end;

 

procedure delete1(link:rel1);

var q:rel1;

begin

if link^.next<>nil then

begin

q:=link^.next;

link^.next:=link^.next^.next;

dispose(q);

end

end;

 

function search1(l:rel1;info:<Тип>;var r:rel1):boolean;

var q:rel1;

begin

search1:=false;

r:=nil;

q:=l^.next;

while (q<>nil) and (r<>nil) do

begin

if q^.data=info then

begin

search:=true;

r:=q

end;

q:=q^.next

end

end;

 

Процедуры добавления и удаления звеньев являются критическими с точки зрения сохранения целостности списка. При неправильном выполнении этих процедур (т.е. при неправильной очерёдности выполнения операций присваивания) возможны 2 ошибочные ситуации:



 

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

 

2. Список так же "рвётся" по месту вставки или удаления звена, но указатель в звене, ставшем последним, получает какое-то произвольное значение, которое трактуется как адрес следующего звена (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес, и так далее, до тех пор, пока случайно не попадётся блок данных, для которого указатель next не будет равен нулю. При попытке просмотра списка на дисплей сначала выводятся правильные данные, а затем случайный набор символов.

 

В обоих случаях к звеньям в "оторвавшейся" части ("хвосте") списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.

 

Для предотвращения возникновения таких ошибок следует соблюдать правильный порядок проведения связей (т.е. присваивания указателей) при вставке нового звена и удалении существующего (очерёдность операций указана):

 

Добавление звена в произвольную позицию за ведущим звеном:

 

struct Link1

{

int data;

Link1* next;

};

 

void Insert1(Link1* link,int data) // link - звено, за которым вставляется новое

{

Link1* q=new Link1; // 1 Выделение памяти под новое звено

q->data=data; // 2 Ввод данных

q->next=link->next; // 3 Проведение связи от нового звена к следующему

link->next=q; // 4 Проведение связи от "старого" звена у новому

}

 

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

 

Удаление звена из любого места списка за ведущим звеном:

 

void Delete1(Link1* link) // link - звено, предшествующее удаляемому

{

Link1* q;

if(link->next) // Проверка на наличие звена, следующего за link

{

q=link->next; // 1 Запоминание удаляемого звена для операции delete

link->next=q->next; // 2 Проведение новой связи в обход удаляемого звена

delete q; // 3 Очистка памяти

}

}

Одной из наиболее простых операций со всеми типами списков является их прохождение, т.е. поочерёдное получение доступа ко всем элементам. Приведём процедуру, реализующую эту операцию для просмотра списка (другие варианты использования прохождения - поиск данных и сохранение списка в файл). В случае перемещения по 2-связному списку в "прямом" направлении эта процедура является одинаковой для 1- и 2-связного линейных списков.

 

Просмотр 1-связного линейного списка

 

void Show(Link1* link)

{

Link1 *q=link->next; // Учитывается наличие "пустого" ведущего звена

while(q) // или while(q!=NULL)

{

cout<<q->data<<' '; // или другая операция

q=q->next; // Переход по списку

}

cout<<endl;

}

 

Поиск в списке является вариантом операции просмотра и отличается тем, что:

1. вместо операции вывода на экран (cout<<q->data) используется операция сравнения искомых данных с хранящимися в звеньях списка;

2. если искомые данные найдены, нет необходимости перемещаться по списку дальше.

 

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

 

Универсальная процедура поиска (находит звено с ключом поиска и предшествующее ему)

 

int Search(Link1* Start, // Точка начала поиска

Link1*& Find, // Указатель для звена с искомыми данными

Link1*& Pred, // Указатель для предыдущего звена

int Key) // Ключ поиска

{

Link1* Cur=Start->next; // Текущее звено

Pred=Start; // Предыдущее звено ("отстаёт" на 1 шаг от текущего)

int Success=0; // Признак успеха поиска (установлен в 0)

while(Cur && !Success) // Операция логическое "И"

{

if(Cur->data == Key) // нашли

{

Find=Cur; // Запоминание найденного звена

Success=1; // Установка в 1 признака успеха

break; // Выход из цикла при удачном поиске

}

Pred=Cur; // Перемещение предыдущего звена

Cur=Cur->next; // Переход по списку вперёд

}

return Success;

}

 

Следует отметить, что возможны разные (в том числе более короткие) варианты реализации такого алгоритма, например, без переменной Success (вместо неё используется указатель Find, который до начала поиска должен получить значение NULL и сохранить его при неудачном поиске).

 

Процедура, которая находит только искомое звено, является более простой, - в ней не нужен указатель Pred и все операторы, в которых он используется.

 

Похожая процедура применяется для 1-связного кольцевого списка. Отличие её от рассмотренного примера заключается в условии продолжения цикла в операторе while:

while(Cur!=Start && !Success) // Для кольцевого списка

 

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

 

Link1 *L1 = new Link1; // Выделение памяти под звено

 

L1->next = NULL; // Ведущее звено одновременно является последним

 

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

 

Занесение в очередь и извлечение из очереди, построенной на основе 2-связного списка

 

void queue_in(Link2*& q, // "Голова" очереди

Link2*& e, // "Хвост" очереди

int k) // Вводимые данные

{

Link2* n=new node; // Новый узел

n->data=k;

n->next=q;

if(q)

q->prev=n;

else

e=n;

n->prev=0;

q=n;

}

 

int queue_out(Link2*& q, Link2*& e)

{

int k=e->data;

Link2* d=e;

e=d->prev;

if(e)

e->next=0;

else

q=e;

delete d;

return k;

}

 

Для упрощения обработки "головы" и "хвоста" очереди использован 2-связный список.

 

В остальных случаях (т.е. для обычных списков) использование ведущего звена является предпочтительным, т.к. позволяет избежать проверок при добавлении и удалении звеньев.

 

Недостатки односвязного списка заключаются в следующем:

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

2. Наличие только одной связи снижает надёжность хранения данных в 1-связном списке.

3. Следствием первого недостатка является усложнение взаимодействия операций поиска и удаления.

 

Достоинствами этого списка являются меньший расход памяти по сравнению с другими связными динамическими структурами данных (всего 1 указатель) и простота операций.

 



<== предыдущая лекция | следующая лекция ==>
Связные списки | Линейный двусвязный список


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


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

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

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


 


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

 
 

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

Генерация страницы за: 0.009 сек.