Список в связанной памяти

Связанные списки


Все начинающие программисты рано или поздно сталкиваются с проблемами, которые решить можно только при помощи связанных списков. Но о их существовании эти программисты не знают, и поэтому часами, а то и сутками ломают себе голову, как же им выкрутиться. В этом топике я подробно опишу то, когда нам нужны связанные списки, и как ими пользоваться.
Прежде чем прочесть эту тему вам следует знать (ну, или хотя бы иметь представление) что такое:
  • Массивы: одномерные(их ещё называют векторами) и двумерные (их еще называют матрицами)
  • Указатели (Pointers). Важно знать про Типизированные указатели.
    Динамическая память (Dynamic memory или Heap Memory)
  • Тип данных - Запись (Record)

Рассмотрим реальный случай из жизни:
Допустим вам нужно написать простой текстовый редактор, который бы загружал текстовый файл в память, и потом позволял бы изменять текст, загруженный в память.
И вы решили организовать это так:
Завести большой массив из строк. Каждая строка с 1 по N-ную в этом массиве будет содержать соответствующую строку из файла. И все бы хорошо, и можно было бы такой массив сделать, но как же быть.. Ведь мы в начале не знаем, сколько строк будет в файле, и не знаем, сколько элементов объявить в массиве.
Как обычно новички поступают в таком случае? Они создают массив по принципу "ШОБ ХВАТИЛО" скажем из 500 элементов:
CollapsedExpandedWrap enabledWrap disabled

var dat: array[1 .. 500] of string[80]

, и таким образом получается, что наша программа сможет редактировать файлы из пятисот строк. Но, скажу я вам, это ламерский способ! %) Настоящий программист никогда не позволит себе такой вольности: выделять заранее оговоренное количество строк, и тем самым ограничивать пользователя. Настоящий программист непременно воспользуется связанным списком.
Связанный список представляет собой подобие массива. Но этот массив объявлять не приходится. Нет одной переменной, которая бы олицетворяла весь массив, и нет у такого "массива" названия. Но есть его подобие. А именно: Каждый элемент связанного списка на самом деле - независимый участок памяти. Каждый элемент сам по себе. Но они все связаны. Все эти кусочки памяти связаны друг меж другом.
Давайте рассмотрим такую аналогию: Представьте себе толпу людей. Пусть это будет куча элементов с данными в памяти. В толпе людей все люди стоят перемешано, как и элементы в памяти. Один там, другой тут ... А теперь представьте себе, что каждый человек указывает пальцем на какого либо другого человека в этой толпе. Тогда Я могу сказать, что эти люди образуют друг между другом связь.
Представьте себе: один человек в толпе указывает на другого. Тот в свою очередь указывает на еще кого-то, тот еще на кого-то, и так до какого либо человека, который ни на кого не указывает. Вот точно так же в памяти устроены связанные списки. Каждый элемент в памяти кроме своего значения еще "знает", где в памяти находится элемент, следующий за ним. А самый последний элемент в последовательности "знает", что за ним никого нет.
Теперь на секундочку допустим, что все люди знают по одной строке... ну ... стиха "Буревестник" %) Ну там (буря мглою небо кроет... бла-бла-бла). Но только по одной. Так вот тот человек, который знает первую строку стиха указывает пальцем на человека, который знает вторую строку. Тот в свою очередь указывает на человека, который знает 3 строку. И так до человека, который знает самую последнюю ... как ее там "Пусть сильнее грянет буря!.. ". А этот самый последний уже не указывает ни на кого, давая нам понять, что цепочка людей закончилась.
Так вот точно так же работают связанные списки.
Вернемся к нашей задаче о строках в файле.
Когда у нас есть связанный список, то в первом элементе этого списка нужно поместить первую строку файла, и так-же указать им на второй, чтобы было понятно, где находится следующая строка. Во втором элементе - вторая строка файла, и информация о том, где находится третий элемент. И так далее. Последний элемент не указывает ни на что. Осмыслите как следует и переварите эту информацию, потому что я дальше покажу, как реализуется такой связанный список на Pascal'е.
Каждый элемент связанного списка принято называть нодой (Node).
На Паскале каждый элемент мы создаем динамически, и размещаем в динамической памяти ( а я ведь говорил, что нужно знать о динамической памяти :D ). Каждый элемент списка мы описываем как тип данных Record, в котором два поля - значение самого элемента (ну там число, строка или что угодно) и указатель, где в памяти находится следующий после него элемент. Указатель этот должен быть (для удобства) типизированным. Определим два новых типа:
CollapsedExpandedWrap enabledWrap disabled

type

  pNode=^TNode; {Типизированный указатель - указатель на данные типа TNode}

  TNode=record

    Value:/тип данных/; {значение элемента}

    Next:PNode; {Указатель на следующий элемент}

  end;


Надеюсь вы понимаете, что это только описание типов данных. Самих данных на самом деле еще нет.
Так вот. Теперь о том что я говорил - а я говорил, что связанный список нельзя описать как массив данных, одной переменной. Зато можно в одной из переменных содержать адрес, где будет находиться самый первый элемент последовательности (ну списка, список еще называют последовательностью). И тогда, зная адрес первого элемента последовательности, можно найти, где находится второй элемент, и потом где находится 3 элемент, и так далее.
Вот пример:
CollapsedExpandedWrap enabledWrap disabled

... объявление типов (Смотри выше)

var

  First:pnode; {Указатель на место в памяти, где находится первый элемент последовательности}

Тут следует сказать, что последний элемент не должен ни на что не указывать. Как это делается на Паскале? Так как указываем на следующий элемент мы при помощи указателей, то указатель, который ни на что не указывает всегда равен NIL. И следовательно если в элементе поле Next=NIL, то это последний элемент в цепочке.
Ну хорошо. Примерно уяснили, как следует описывать элементы списка. А как его вообще создать?
Для того чтобы создать связанный список мы должны в памяти выделять память под динамические ячейки, и для каждого элемента списка настроить значения параметра Next так, чтобы там действительно адрес следующей ячейки, либо же значение NIL (пусто) если это последняя ячейка в последовательности.
Вот простейшая реализация такого связанного списка:
CollapsedExpandedWrap enabledWrap disabled

type

  pNode=^TNode; {Типизированный указатель - указатель на данные типа TNode}

  TNode=record

    Value:integer; {значение элемента}

    Next:PNode; {Указатель на следующий элемент}

  end;

var

  First:pnode;

  Temp:pnode; {временный указатель на ячейку. Понадобится для построения связанного списка}

begin

  {Создадим список из 4 элементов с разными числами}

  New(Temp); {Создали в памяти новый элемент. На него указывает указатель Temp}

  First:=Temp; {Это и будет первый элемент последовательности.

 Поэтому в указатель First мы занесем его адрес}

  Temp^.Value:=10; {Задаем значение для 1 элемента}

  New(Temp^.Next); {Создали новый (2) элемент в памяти. На него указывает указатель Temp^.Next}

  Temp:=Temp^.Next; {Теперь Temp - это указатель на новый (2) элемент.

 Причём в предыдущем (1) элементе Next указывает именно на него, как нам и нужно}

  Temp^.Value:=20;  {Задаем значение для 2 элемента}

  New(Temp^.Next); {Создали новый (3) элемент в памяти. На него указывает указатель Temp^.Next}

  Temp:=Temp^.Next; {Теперь Temp - это указатель на новый (3) элемент.

 Причём в предыдущем (2) элементе Next указывает именно на него, как нам и нужно}

  Temp^.Value:=30;  {Задаем значение для 3 элемента}

  New(Temp^.Next); {Создали новый элемент в памяти. На него указывает указатель Temp^.Next}

  Temp:=Temp^.Next; {Теперь Temp - это указатель на новый (4) элемент.

 Причём в предыдущем (3) элементе Next указывает именно на него, как нам и нужно}

  Temp^.Value:=40;  {Задаем значение для 4 элемента}

  Temp^.Next:=NIL; {Последний (4) элемент не должен указывать ни на какой.

 Поэтому у него Next должно быть NIL}

end.


Таким вот образом мы вручную создали связанный список из 4 элементов. Фактически его можно использовать как массив.
Но для доступа к определенному элементу уже нельзя будет использовать его порядковый номер. Нужно будет последовательно начиная с элемента, на который указывает переменная First искать нужный нам.
Зато такой связанный список может содержать в себе сколько угодно (а точнее на сколько хватит памяти) элементов.
А давай-те ка я это продемонстрирую. Автоматизируем процесс. Позволим пользователю вводить сколько угодно элементов, а потом все их выведем на экран:
CollapsedExpandedWrap enabledWrap disabled

type

  pNode=^TNode; {Типизированный указатель - указатель на данные типа TNode}

  TNode=record

    Value:integer; {значение элемента}

    Next:PNode; {Указатель на следующий элемент}

  end;

var

  First:pnode;

  Temp:pnode; {временный указатель на ячейку. Понадобится для построения связанного списка}

  v:integer;

begin

  First:=nil; {В начале у нас First не указывает ни на что}

  repeat

    write('Введите значение нового элемента (0 для выхода):');

    readln(v);

    if v=0 then break; {Если ввели 0, то окончим ввод элементов}

    if First=NIL then {Если First=NIL, то сейчас мы создадим первый элемент}

    begin

      new(Temp); {Создали первый элемент. Его адрес в Temp}

      First:=Temp; {Так как элемент первый, запомним его адрес}

    end else {Иначе это уже не первый элемент}

    begin

      New(Temp^.Next); {Создаем на основе предыдущего, чтобы сохранилась связь между элементами}

      Temp:=Temp^.Next; {Текущий элемент теперь тот, который мы только что создали.

                         И предыдущий указывает на него}

    end;

    Temp^.Value:=v; {Зададим значение текущего элемента}

    

  until false; {Бесконечный цикл. Прервется только если пользователь введет 0}

  {Всё у нас хорошо. Только вот в последнем элементе параметр Next не определен. Непорядок}

  Temp^.Next:=NIL; {Ну вот теперь то лучше}

  {Заметьте, что даже если пользователь сразу введет 0, то в переменной First будет NIL,

 что значит - пустой список}

 

  {Теперь выведем наш связанный список. Адрес его первого элемента находится в переменной First,

 и это хорошо %)}

  Temp:=First; {Укажем переменной Temp на первый элемент последовательности}

  while Temp<>NIL do {Пока текущий элемент существует}

  begin

    writeln(Temp^.Value); {Выводим текущий элемент}

    Temp:=Temp^.Next; {Переходим к следующему}

    {Обратите внимание, что если следующий элемент не существует,

     то в Temp попадет значение NIL, и цикл прекратится}

  end;

end.


Только что мы рассмотрели принцип создания простого связанного списка. Но я ничего не сказал об удалении. Хотя компилятор Borland Pascal вставляет в код программы автоматически код, который высвобождает всю память, которая была отведена командой New под новые элементы, но все же хорошим тоном считается удалить все элементы из памяти.
Поэтому нам нужно реализовать цикл, подобный тому, когда мы выводили элементы на экран, но при этом мы должны удалять элементы командой Dispose.
Вот так:
CollapsedExpandedWrap enabledWrap disabled

  while First<>NIL do {Пока текущий элемент существует}

  begin

    Temp:=First;

    First:=First^.Next; {Переходим к следующему}

    Dispose(Temp); {Теперь удаляем элемент, который был}

    {Важно не перепутать две предыдущие строчки местами. сначала мы переходим к следующему элементу,

     а потом высвобождаем память от уже ненужного элемента}

  end;


Ну что ж. Основные сведения я уже изложил.
Теперь основные прикладные функции. Их 3: Поиск элемента в списке по значению, Вставка нового элемента, Удаление существующего элемента.
Поиск элемента в списке по значению
Вернёмся к нашей аналогии с толпой людей. Как бы мы искали в толпе людей, знающих по одной строчке из стиха определенного человека, который знает определенную строчку?
Мы бы подошли к первому , узнали, какую строчку он знает. Если это не та, которая нам нужна, то узнали бы, куда он показывает, и пошли бы к тому человеку. После чего повторили бы действия. И повторяли бы их до тех пор, пока не нашли человека, знающего нужную нам строчку. Так в чем же проблема? реализуем этот принцип на Паскале ! %)
...Задание переменных и создание связанного списка в памяти...
...В переменной v находится число, с значением которого мы хотим найти элемент...
CollapsedExpandedWrap enabledWrap disabled

  Temp:=First;

  while Temp<>NIL do {Пока элемент существует}

  begin

    if Temp^.Value=v then break; {Если нашелся элемент с нужным нам значением, то прервем цикл}

    Temp:=Temp^.Next; {Переходим к следующему элементу}

  end;

  {По окончании этого цикла указатель Temp будет указывать на элемент с искомым значением}

  {Заметьте, что если значение не найдено в списке, то в Temp окажется NIL, что вполне нам подходит}


Эти же действия удобно оформить в виде функции:
CollapsedExpandedWrap enabledWrap disabled

function FindElement(FirstNode:PNode,Value:Integer):PNode;

var Temp:PNode;

begin

  Temp:=FirstNode;

  while Temp<>NIL do {Пока элемент существует}

  begin

    if Temp^.Value=Value then break; {Если нашелся элемент с нужным нам значением, то прервем цикл}

    Temp:=Temp^.Next; {Переходим к следующему элементу}

  end;

  FindElement:=Temp;

end;


Должен отметить, что результатом поиска будет не значение, а указатель на элемент с искомым значением.
Вставка нового элемента в список
По уже отработанному принципу переносим воображение на толпу людей. Как мы добавим нового человека, который бы знал новую строку стиха?
Для начала мы должны определиться, после какой строки будем вставлять новую строку. Логично? Потом мы по принципу поиска найдем человека, который знает ту строку, после которой мы будем вставлять нового человека. Потом мы возьмем нового человека, скажем ему строку. Затем мы узнаем, на какого человека указывает найденный нами. И скажем новому человеку, чтобы он тоже на него указывал. И в конце концов мы скажем найденному нами человеку, чтобы он указывал на нового человека.
Я понимаю что это запутано, но возможно в реализации будет проще понять. Обдумайте сами представив алгоритм в голове, по ходу дела сравнивая с вот таким кодом:
...Задали связаный список, хотим вставить строку NewStr после строки PrevStr. Тип данных в списке - String...
CollapsedExpandedWrap enabledWrap disabled

  {Cначала найдем элемент, после которого будем вставлять}

  Temp:=FindElement(First,PrevStr);

  {Cоздадим новый элемент}

  New(Temp2);

  Temp2^.Value:=NewStr; {Зададим значение для него}

  Temp2^.Next:=Temp^.Next; {Сделаем так, чтобы он указывал на ту же строку,

                            на которую указывал элемент с PrevStr}

  Temp^.Next:=Temp2; {И наконец укажем элементом с PrevStr на наш новый элемент}


Таким образом мы ИМЕННО ВСТАВЛЯЕМ между двумя элементами Temp и Temp^.Next новый элемент Temp2, и подправляем указатели, чтобы они составляли правильную последовательность.
Тут нужно отметить то, что если строка PrevStr была в самом последнем элементе, то в списке появится новый элемент, который будет корректно последним. То есть предпоследний будет указывать на него, а новый последний элемент будет будет указывать на "ничто" (Next=NIL).
Естественно и эти действия удобно организовать в отдельную процедуру:
CollapsedExpandedWrap enabledWrap disabled

Procedure InsertElement(First:PNode;PrevStr,NewStr:string);

var

  Temp,Temp2:PNode;

begin

  Temp:=FindElement(First, PrevStr);

  New(Temp2); { Cоздаем новый элемент}

  Temp2^.Value:=NewStr; {Зададим значение для него}

  Temp2^.Next:=Temp^.Next; {Сделаем так, чтобы он указывал на ту же строку,

                            на которую указывал элемент с PrevStr}

  Temp^.Next:=Temp2; {И наконец укажем элементом с PrevStr на наш новый элемент}

end;


При вставке нового элемента часто бывает удобно вставлять не после определенного значения элемента, а явно указывать, после какого элемента вставлять:
CollapsedExpandedWrap enabledWrap disabled

Procedure InsertElement2(PrevElement:PNode;NewStr:string);

var Temp:PNode;

begin

  New(Temp); {Cоздадим новый элемент}

  Temp^.Value:=NewStr; {Зададим значение для него}

  Temp^.Next:=PrevElement^.Next; {Сделаем так, чтобы он указывал на тот же элемент,

 на какой указывал PrevElement}

  PrevElement^.Next:=Temp; {И наконец укажем элементом PrevElement на наш новый элемент}

end;


Удаление существующего элемента из списка
Принцип: Ищем в списке элемент с заданным значением. После чего удаляем его, корректируя ссылку предыдущего элемента, чтобы он ссылался не на удаляемый элемент, а на следующий после удаляемого.
Вот реализация:
CollapsedExpandedWrap enabledWrap disabled

Procedure DeleteElement(var First:PNode; ValueToDelete:/Тип данных/);

{First должна быть именно var на случай, если удаляемый элемент - самый первый}

var Temp,Temp2:PNode;

begin

  If First^.Value=ValueToDelete then {Если удаляемый элемент - первый, то это частный случай.

                                      Обработаем отдельно}

  begin

    Temp:=First; {Сохраним указатель на него}

    First:=First^.Next; {Сделаем так, чтобы первым элементом теперь стал следующий}

    Dispose(Temp); {Удалим из памяти теперь уже бывший первый элемент}

    Break; {Окончим выполнение процедуры}

  end;

  {Иначе мы будем искать элемент с значением ValueToDelete, но будем запоминать указатель на

 предыдущий элемент}

  {Это нужно для того, чтобы исправить потом указатель, чтобы он не указывал на удаленный элемент}

  Temp:=First;

  while Temp^.Next<>NIL do {Пока у элемента есть следующий, продолжаем}

  begin

    if Temp^.Next^.Value=ValueToDelete then {Если значение следующего элемента - искомое то}

    begin

      Temp2:=temp^.Next; {Поместим в Temp2 указатель на удаляемый элемент}

      Temp^.Next:=Temp2^.Next; {Сделаем так, чтобы элемент перед удаляемым указывал на элемент

                                после удаляемого}

      Dispose(Temp2); {И наконец удалим из памяти удаляемый элемент}

      {Получится что предыдущий элемент указывает на следующий, а сам удаляемый элемент уже не существует}

      Break; {Прервём цикл, так как мы уже нашли удаляемый элемент}

    end;

    Temp:=Temp^.Next; {Перейдем к следующему элементу}

  end;

end;


Так же приведу текст функции, которая удаляет элемент из списка не по значению, а по указателю на него:
CollapsedExpandedWrap enabledWrap disabled

Procedure DeleteElement2(var First:PNode; ElementToDelete:PNode);

var Temp,Temp2:PNode;

begin

  If First=ElementToDelete then {Если удаляемый элемент - первый, то это частный случай.

                                 Обработаем отдельно}

  begin

    Temp:=First; {Сохраним указатель на него}

    First:=First^.Next; {Сделаем так, чтобы первым элементом теперь стал следующий}

    Dispose(Temp); {Удалим из памяти теперь уже бывший первый элемент}

    Break; {Окончим выполнение процедуры}

  end;

  {Иначе мы будем искать элемент ElementToDelete, но будем запоминать указатель на предыдущий

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

   элемент}

  Temp:=First;

  while Temp^.Next<>NIL do {Пока у элемента есть следующий продолжаем}

  begin

    if Temp^.Next=ElementToDelete then {Если следующий элемент - искомый}

    begin

      Temp2:=temp^.Next; {Поместим в Temp2 указатель на удаляемый элемент}

      Temp^.Next:=Temp2^.Next; {Сделаем так, чтобы элемент перед удаляемым указывал на элемент

                                после удаляемого}

      Dispose(Temp2); {И наконец удалим из памяти удаляемый элемент}

      {Получится что предыдущий элемент указывает на следующий, а сам удаляемый элемент уже не существует}

      Break; {Прервём цикл, так как мы уже нашли удаляемый элемент}

    end;

    Temp:=Temp^.Next; {Перейдём к следующему элементу}

  end;

end;


Итак я рассмотрел простые связанные списки, и три основных операции с ними. Остальные операции могут быть сформированы на основе этих трех.
Теперь я не могу не сказать об теории списков более подробно, и не описать их классификации:
Рассмотренные мной списки называются односвязными. Название такое они получили, потому что связь между элементами таких списков является односторонней - один элемент указывает на следующей, тот в свою очередь на еще один и так далее. То есть каждый элемент указывает только в одном направлении (я принял за норму - указывать на следующий элемент).
Представьте себе список, в котором каждый элемент указывает не только на следующий за ним идущий, а еще и на тот, который был перед ним - на предыдущий. Если сравнивать с толпой людей, то каждый человеку указывает не на одного, а на двух сразу. Тогда одно направление указывания (последовательность людей, которые указывают друг на друга правой рукой) можно условно назвать "направление вперед". А другое направление (указываемое левой рукой) - "направление назад. Таким образом я смог бы перемещаться в последовательности людей не только вперед (как во всех вышеописанных примерах), а и назад. Поскольку каждый человек знает не только своего "потомка" но и "предка".
На самом деле эти направления (вперед/назад) - лишь названия, и ничего больше. Поскольку на самом деле все эти люди всего лишь куча людей. И то, в какой последовательности они друг на друга указывают руками просто определят, какого человека следует брать за каким.
Вот представьте себе, что у вас есть куча переменных, организованных как ячейка связанного списка в памяти. Они все находятся в ней хаотично и не связаны друг с другом. И допустим эти переменные числа. Тогда чисто теоретически их можно взять в такой последовательности, что каждое следующее значение будет больше предыдущего. И тогда такая последовательность будет представлять собой отсортированный по возрастанию массив. И в то же время это будут оставаться хаотичные данные в памяти.
А представьте себе, что у каждой из этих переменных не один параметр Next, а два. И допустим выстроены две цепочки (для одного Next и для другого) так, чтобы по одной цепочки брались элементы по возрастанию, а для другой - по убыванию. Тогда получится что у нас одни и те же данные отсортированы и по возрастанию и по убыванию. В зависимости от того, какое направление взять (Next1, или Next2). А ведь может быть и направление Next3, в котором они отсортированы в порядке их создания, и тогда для одних и тех же данных будет три направления последовательностей.
Поэтому можно утверждать, что списки могут быть не только однонаправленными, а и двунаправленными, трехнаправленными, словом N-направленными. Причем сколько бы не было направлений, все они будут сделаны для одних и тех же данных. Представьте себе, если бы вам нужно было отсортировать массив по возрастанию, и по убыванию, вам бы пришлось создать два массива - один с данными по возрастанию, а другой с данными по убыванию. А тут у вас получатся ЕДИНЫЕ данные, но с двумя направлениями сортировки. Это имеет большую перспективу в том случае, к примеру, если объем данных для каждого элемента последовательности - значительный, поскольку даст существенную экономию памяти.
Так-же списки бывают цикличными (замкнутыми). Это когда последний элемент списка указывает на первый элемент списка (а если список двунаправленный, то и первый может указывать на последний). У такого списка нет начала и конца, он замкнут как бы по кольцу. И по нему можно перемещаться в том или ином направлении до бесконечности, по кругу.
УУФФФФ.. ну вроде-бы все на данный момент.

Источник: http://forum.sources.ru/index.php?showtopic=69615


Закрыть ... [X]

Линейный список прямого доступа в связанной памяти - С для Резные панно из дерева своими руками

Список в связанной памяти Динамически распределяемая память - Реферат, страница 1
Список в связанной памяти Связанное распределение памяти Мегаобучалка
Список в связанной памяти Связанные списки - Форум на Исходниках. Ру
Список в связанной памяти ЛИНЕЙНЫЕ СПИСКИ - Адресные типы
Список в связанной памяти Связанный список Life-Prog
M - китайская торговая площадка с огромным Божественный крем для кожи вокруг глаз Иммортель Крем от ВАННБОК официальный сайт, Экраны для ванны, купить экран под Вросший волос в зоне бикини стал шишкой воспаление от вросшего Всё течёт, всё изменяется. Булат Буги, 58 лет Сеть знакомств Мамба Макияж под бежевое платье : цвета для вечернего make-up на выпускной для Мастер -класс по разделке рыбы видео приколы смотреть онлайн скачать видео Надувные лодки, купить лодку пвх гребную или моторную в Киеве Парафиновые ванночки для рук