Динамическая структура: линейный односвязный список с заглавным звеном

Главное меню статьи

Что такое "Список" и что такое "Список с заглавным звеном"?
Указатель на начало списка
Вспомогательные инструменты для проведения операций над списком
Добавление элемента в начало списка
Добавление элемента в конец списка
Добавление элемента перед заданным элементом списка
Добавление элемента после заданного элемента списка
Удаление первого элемента из списка
Удаление последнего элемента из списка
Печать элементов списка на экран из начала в конец
Реализация списка с заглавным звеном на языке программирования Turbo Pascal (ПРОГРАММА)

Для лучшего понимания данного материала ознакомьтесь с кратким очерком о классификации динамических структур данных.

Линейный односвязный список с заглавным звеном

Что такое "Список" и что такое "Список с заглавным звеном"?

Что же такое "Список" и его разновидность "Линейный односвязный список с заглавным звеном"?

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

  1. Добавление элемента в любое место списка.

  2. Удаление элемента из любой позиции списка.

Линейный односвязный список с заглавным звеном - тот же самый линейный односвязный список (ЛОС), но в дополнении имеющий специальный элемент, называемый заглавное звено, которое никогда не исключается из списка и служит для хранения вспомогательной информации о самом списке, например, о количестве элементов списка. Зачастую, заглавный элемент совсем не используются в программе и выполняют чисто формальную роль. Фундаментальные операции допустимые над списком с заглавным звеном совпадают с фундаментальными операциями над простым ЛОС.

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

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

Фундаментальные операции допустимые над списком с заглавным звеном совпадают с фундаментальными операциями над простым ЛОС.

Указатель на начало линейного односвязного списка

head - указатель на заглавный элемент списка

Для корректной обработки линейного односвязного списка вводят понятие - указатель на начало списка. Как правило, именуется в программе подобный указатель словом head (в переводе с английского означает - голова). Данный указатель обязан указывать или ссылаться только на заглавный элемент списка, иначе список будет находиться в несогласованном состоянии. Надо понимать, что структурно заглавный элемент ничем не отличается от простого элемента списка и исполняет роль лишь служебного элемента, но заглавный элемент является обязательной частью линейного односвязного списка с заглавным звеном.

Информационное поле заглавного элемента очень часто выступает в роли хранителя общего количества элементов в текущем списке. Это облегчает проведения некоторых операций над списком, особенно когда требуется знать общее количество элементов. Иногда, заглавный элемент выступает в роли "мебели", то есть не выполняет никакой функциональности, кроме как ссылки на действительный первый элемент списка.

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

Абсолютно во всех операциях, производимых над списком, требуется вспомогательный указатель, помимо указателя head, ссылающегося на заглавный элемент односвязного линейного списка. Во всех программах и фрагментах программного кода, представленных ниже, будем обозначать вспомогательный указатель идентификатором p (почему "p"? потому что с английского слово pointer переводится на русский как указатель).

Если требуется несколько вспомогательных указателей, то будем именовать их по принципу p1, p2, p3 и т. д.

Что же такое "NIL"?

NIL - специальный зарезервированный участок памяти, служащий "бухтой" для динамических переменных-указателей. Чтобы указатели "не болтались" в памяти, их обычно "привязывают" к NIL.

Добавление элемента в начало линейного односвязного списка

Линейный односвязный список обладает широкими возможностями вставки новых элементов, а именно:

  • добавление элемента в начало списка;

  • добавление элемента в конец списка;

  • добавление элемента перед заданным элементом;

  • добавление элемента после заданного элемента.

По сути, вставку можно произвести абсолютно в любую позицию существующего списка. Рассмотрим более детально вставку нового элемента в начало списка. Допустим, список является пустым, то есть заглавный элемент указывает в NIL.

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

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

И указатель head, и указатель add имеют одинаковую "анатомию", но в программе у них различная логическая роль. Как правило, в программах по формированию линеного односвязного списка, имеется функция, отвечающая за выделение памяти под добавляемый элемент.

 

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

То есть происходит перемещение указателя, который ссылался в NIL, на добавляемый элемент, то есть на тот участок памяти, куда ссылается указатель add.

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

Также, как видно из картинки, представленной слева, информационное поле заглавного звена принимает значение равное 1, т к был добавлен первый элемент в линейный односвязный список.

 

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

В приведенном примере, список содержит три элемента. Напомню, что информационное поле заглавного звена отвечает за текущее количество элементов в списке.

Как мы ранее и договаривались, указатель, ссылающийся на добавляемый элемент будет называться add, а линковочное поле добавляемого элемента находится в согласованном состоянии, так как "смотрит" в NIL.

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

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

Таким образом уже образуется кое-какая взаимосвязь между добавляемым элементом и первым элементом списка.

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

Другими словами, линковочное поле заглавного звена стало указывать на новоиспеченный элемент, именуемый add.

Список находится в согласованном состоянии.

В итоге увеличиваем общее количество элементов данного списка на один и производим визуализацию конечного состояние списка.

Линейный односвязный список с заглавным звеном пребывает в согласованном состоянии, так как линковочное поле заглавного элемента ссылается на "новый" первый элемент, а линковочное поле замыкающего элементы ссылается в NIL.

Добавление элемента в конец Списка

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

Предположим, что в данном континууме существует список с заглавным звеном, состоящий из двух элементов. Кстати, информационное поле заглавного элемента хранит значение равное 2, что говорит нам о том, что в данный момент времени список состоит из двух реляционных элементов.

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

Для продолжения проведения операции добавления элемента в конец линейного односвязного списка с заглавным звеном, потребуется вспомогательный указатель р, который необходимо установить на заглавный элемент данного ЛОС.

Сейчас нашей целью является достижения данным указателем р самого крайнего с конца элемента списка. Для этого потребуется циклически смещаться по одному элементу.

На первой итерации происходит позиционирование указателя р на второй элемент списка.

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

Итак, вспомогательный указатель p достиг последнего элемента линейного односвязного списка.

Переставляем линковочное поле последнего элемента списка на добавляемый элемент. И в принципе на этом операция добавления элемента в конец линейного односвязного списка с заглавным элементом считается проведенной.

Список находится в согласованном состоянии, связь между элементами "не порвана", линковочное поле последнего элемента списка ссылается в NIL.

Увеличиваем количество элементов списка на единицу. Теперь текущее количество составляет три.

Список находится в абсолютно согласованном состоянии, так как указатель на заглавный элемент ссылается на заглавное звено, а последний элемент списка указывает в NIL.

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

Добавление элемента перед заданным элементом

Допустим, существует линейный односвязный список с заглавным звеном, состоящий из 5 элементов.

Указатель head ссылается на элемент, называемый заглавное звено.

Линковочное поле заглавного элемента ссылается на первый элемент данного односвязного списка.

Список находится в согласованном состоянии.

add - название указательной переменной, которая ссылается на добавляемый элемент

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

Потребуется вспомогательный указатель р, ссылающийся на заглавное звено всего списка.

В качестве примера выбран список, состоящий из 5 элементов.

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

На первой итерации смещаем указатель р на первый элемент списка.

Напомню, что заглавный элемент и первый элемент списка - различные узлы.

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

Как видно из рисунка, "красный" элемент имеет номер 3, а указатель p достиг уже элемента под номером 2.

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

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

Но это только первая операция.

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

Для этого перемещаем линковочное поле 2-го элемента на добавляемый элемент.

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

В итоге список находится в абсолютно согласованном состоянии, так как указатель head указывает на заглавное звено, а завершающий элемент списка ссылается в NIL.

Также количество элементов списка увеличиваем на единицу.

Вывод: операция добавления элемента в список с заглавным звеном перед заданным элементом успешно проведена.

Добавление элемента после заданного элемента

Покажем лишь непосредственно схемы добавления элемента. Граница заданного элемента помечена красным цветом. Также, для проведения данной операции требуется вспомогательный указатель р. Читать схему следует построчно слева направо.

Вывод: операция добавления элемента после заданного элемента списка с заглавным звеном успешно проведена

Удаление первого элемента из списка

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

Рассмотрим удаление первого элемента из списка с заглавным звеном, состоящего из трех элементов.

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

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

Установим идентификатор р на первый или удаляемый узел линейного односвязного списка. Также отметим каемку удаляемого элемента красным цветом.

Наша задача - уничтожение "красного" элемента из данного списка, при этом сам список должен остаться в согласованном состоянии.

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

Для этого переставляем линковочное поле заглавного элемента на второй элемент списка.

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

Данную операцию можно провести абсолютно безболезненно, так как на второй элемент списка ссылается линковочное поле заглавного элемента

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

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

В различных языках программирования, команда, отвечающая за уничтожение ранее распределенной памяти, называется по-разному. В языке программирования Pascal, для высвобождения памяти необходимо использовать процедуру Dispose, в языке программирования "чистый" С необходимо вызвать функцию free.

Уменьшаем количество элементов списка на единицу. Теперь список состоит из двух полноценных динамических элементов.

Также надо заметить тот факт, что список находится в согласованном состоянии, так как указатель head ссылается на заглавный элемент, который в свою очередь ссылается на первый элемент списка, а замыкающий элемент списка ссылается в NIL.

Вывод: операция удаления первого элемента из списка с заглавным звеном успешно проведена.

Удаление последнего элемента из списка

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

В итоге список состоит из двух элементов, причем находится список в согласованном состоянии, так как указатель head ссылается на заглавное звено, а завершающий узел списка указывает в NIL. Также внутренние связи остались в консистентном положении, то есть, неразрушенными.

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

Примечание: удалить заглавное звено из списка невозможно - противоречит определению односвязного списка с заглавным звеном

Печать элементов списка на экран (из начала в конец)

Под печатью списка понимают визуализацию значений информационных полей каждого из элементов списка.

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

Справа представлена итеративная схема, демонстрирующая, каким образом производится перебор элементов заданного списка.

Для корректной реализации данной процедуры требуется вспомогательный указатель р, стартующий с первого узла списка.

Желтыми областями помечено значение информационного поля печатаемого на дисплей пользователя элемента.

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

Примечание: существует также операция печати элементов линейного списка из конца в начало и реализуется рекурсивным способом

Реализация списка с заглавным звеном на языке программирования Turbo Pascal 7.0

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

Программа реализует следующие операции над списком:

  • добавление элемента в начало списка;

  • добавление элемента  в конец списка;

  • добавление элемента перед заданным элементом;

  • добавление элемента после заданного элемента;

  • удаление элемента из начала списка;

  • удаление элемента из конца списка;

  • удаление срединного элемента;

  • печать элементов списка на дисплее пользователя (от начала к концу);

  • получение общего количества элементов в списке;

  • удаление всех элементов из списка.

Скачать программу реализации динамического списка с заглавным звеном на языке программирования Turbo Pascal 7.0.

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

  1. {заголовок программы}
  2. program LIST_HEAD;
  3. {раздел подключения модулей}
  4. uses
  5. {подключаем модуль crt - console run time, чтобы можно было использовать
  6.  подпрограммы для работы с консолью}
  7.     crt;
  8. {раздел объявления пользовательских типов данных}
  9. type
  10. {указательный тип данных на элемент очереди}
  11.     Tptr = ^Telem;
  12. {запись, состоящая из двух полей, описывающая элемент очереди}
  13.     Telem = record
  14. {информационное поле элемента - хранит строковые значения}
  15.         inf  : string;
  16. {указательное поле на следующий элемент очереди}
  17.         link : Tptr;
  18. {конец описания записи}
  19.     end;
  20. {раздел декларации глобальных переменных}
  21. var
  22. {указатель на заглавный элемент линейного односвязного списка}
  23.     head : Tptr;
  24. {---------------------------------------------------------------------------}
  25. {Функция: получение количества элементов списка. В качестве ответа функция
  26.  возвращает количество элементов в списке}
  27. {---------------------------------------------------------------------------}
  28. function getCountElem : integer;
  29. var
  30. {переменная, хранящая количество элементов в списке. Причем данное значение
  31.  хранится в информационном поле заглавного элемента списка, причем в
  32.  строковом виде, то есть надо будет делать перевод из строки в число}
  33.     number    : integer;
  34. {хранит код ошибки, которая может возникнуть в процессе перевода из строки
  35.  в числовое значение}
  36.     errorCode : integer;
  37. {начало тела функции}
  38. begin
  39. {вызываем процедуру перевода из строки в число}
  40.     val(head^.inf, number, errorCode);
  41. {в качестве ответа функция возвращает количество элементов в списке}
  42.     getCountElem := number;
  43. {конец тела функции}
  44. end;
  45. {---------------------------------------------------------------------------}
  46. {Процедура: слежение за заглавным звеном.
  47.  Логический параметр pb работает следующим образом: если передается ИСТИНА,
  48.  то происходит увеличение количества элементов на 1, иначе уменьшение на 1}
  49. {---------------------------------------------------------------------------}
  50. procedure headElem(pb : boolean);
  51. var
  52. {переменная, хранящая количество элементов в списке. Причем данное значение
  53.  хранится в информационном поле заглавного элемента списка, причем в
  54.  строковом виде, то есть надо будет делать перевод из строки в число}
  55.     number    : integer;
  56. {хранит код ошибки, которая может возникнуть в процессе перевода из строки
  57.  в числовое значение}
  58.     errorCode : integer;
  59. {начало тела процедуры}
  60. begin
  61. {вызываем процедуру перевода из строки в число}
  62.     val(head^.inf, number, errorCode);
  63. {происходит увеличение количества элементов}
  64.     if(pb = TRUE) then
  65. {на единицу}
  66.         number := number + 1
  67. {иначе текущее количество элементов уменьшается на единицу}
  68.     else
  69.         number := number - 1;
  70. {используем процедуру для перевода значения из числа в строку, так как
  71.  информационное поле заглавного элемента способно хранить только текстовые
  72.  значения, а не числовые величины}
  73.     str(number, head^.inf);
  74. {конец тела процедуры}
  75. end;
  76. {---------------------------------------------------------------------------}
  77. {Функция: создание элемента списка.
  78.  В качестве ответа функция возвращает ссылку на сам объект / элемент}
  79. {---------------------------------------------------------------------------}
  80. function createElem : Tptr;
  81. var
  82. {указатель на только что созданный элемент в динамической памяти}
  83.     add : Tptr;
  84. {начало тела функции}
  85. begin
  86. {выделяем память под элемент}
  87.     new(add);
  88. {чтобы линковочное поле созданного элемента не "болталось" в памяти,
  89.  привязываем его к NIL}
  90.     add^.link := NIL;
  91. {диалог пользователю о предстоящем вводе}
  92.     write('Введите значение добавляемого элемента: ');
  93. {считывание значения вводом с клавиатуры}
  94.     readln(add^.inf);
  95. {в качестве ответа функция возвращает ссылку на созданный элемент}
  96.     createElem := add;
  97. {конец тела функции}
  98. end;
  99. {---------------------------------------------------------------------------}
  100. {Процедура: добавление элемента в начало списка с заглавным звеном}
  101. {---------------------------------------------------------------------------}
  102. procedure addElemToBegin;
  103. var
  104. {указатель на добавляемый элемент}
  105.     add : Tptr;
  106. {начало тела процедуры}
  107. begin
  108. {создание нового элемента}
  109.     add := createElem;
  110. {устанавливаем связь между только что созданным элементом и первым элементом
  111.  списка (не стоит путать ПЕРВЫЙ элемент и ЗАГЛАВНЫЙ элемент списка!)}
  112.     add^.link := head^.link;
  113. {поскольку добавился новый элемент в начало списка, то заглавный элемент
  114.  ссылается уже на второй, что неправильно, следовательно, связываем
  115.  заглавный элемент и только что добавленный новый элемент в списке}
  116.     head^.link := add;
  117. {увеличиваем общее количество элементов в списке на единицу}
  118.     headElem(TRUE);
  119. {конец тела процедуры}
  120. end;
  121. {---------------------------------------------------------------------------}
  122. {Процедура: добавление элемента в конец списка с заглавным звеном}
  123. {---------------------------------------------------------------------------}
  124. procedure addElemToEnd;
  125. var
  126. {указатель на добавляемый элемент}
  127.     add : Tptr;
  128. {вспомогательный указатель, требующийся для корректной работы}
  129.     p   : Tptr;
  130. {начало тела процедуры}
  131. begin
  132. {создание добавляемого элемента}
  133.     add := createElem;
  134. {позиционируем вспомогательный указатель на заглавный элемент}
  135.     p := head;
  136. {указатель р будет перемещаться по списку до тех пор, пока не выйдет
  137.  на последний элемент списка}
  138.     while(p^.link <> NIL) do
  139. {циклически переходим на следующий элемент списка}
  140.         p := p^.link;
  141. {устанавливаем связь между последним и добавляемым элементом}
  142.     p^.link := add;
  143. {увеличиваем общее количество элементов в списке на единицу}
  144.     headElem(TRUE);
  145. {конец тела процедуры}
  146. end;
  147. {---------------------------------------------------------------------------}
  148. {Процедура: добавление элемента перед заданным элементом}
  149. {---------------------------------------------------------------------------}
  150. procedure addElemBeforeTarget;
  151. var
  152. {добавляемый элемент в список}
  153.     add       : Tptr;
  154. {вспомогательный указатель для проведения операции добавления}
  155.     p         : Tptr;
  156. {хранит номер элемента перед которым будет производиться операция вставки}
  157.     index     : integer;
  158. {счетчик цикла}
  159.     i         : integer;
  160. {начало тела процедуры}
  161. begin
  162. {надо понимать следующее: если количество элементов в списке меньше двух, то
  163.  невозможно добавить элемент перед заданным, это уже будет операция,
  164.  равноценная операции добавления элемента в начало списка}
  165.     if(getCountElem <= 1) then
  166. {диалог пользователю о невозможности проведения операции добавления}
  167.         writeln('Список содержит недостаточное количество элементов для вставки!')
  168. {иначе}
  169.     else
  170.     begin
  171. {выпечатываем пользователю подсказку об общем количестве элементов списка
  172.  на данный момент}
  173.         writeln('На данный момент в списке элементов: ', getCountElem);
  174. {циклически запрашиваем номер элемента перед которым необходимо произвести
  175.  вставку. Также проверяем, чтобы введенный индекс находился в допустимых
  176.  диапазонах}
  177.         repeat
  178.             write('Введите номер элемента перед которым происходит вставка [2 ...', getCountElem, ']: ');
  179.             readln(index);
  180.         until((index >= 2) and (index <= getCountELem));
  181. {устанавливаем вспомогательный указатель на первый элемент списка}
  182.         p := head^.link;
  183. {необходимо "допрыгать" указателем р до элемента, стоящего перед элементом,
  184.  перед которым будет производится вставка нового элемента, поэтому в цикле
  185.  правая граница счетчика составляет значение index - 2}
  186.         for i := 1 to index - 2 do
  187. {переход на следующий элемент списка}
  188.             p := p^.link;
  189. {выделяем память под добавляемый элемент}
  190.         add := createElem;
  191. {устанавливаем связь между новым элементом и элементом перед которым данный
  192.  новый элемент будет вставлен}
  193.         add^.link := p^.link;
  194. {устанавливаем связь между новым элементом и элементом, стоящим перед элементом
  195.  перед которым производится вставка}
  196.         p^.link := add;
  197. {общее количество элементов списка увеличиваем на единицу}
  198.         headElem(TRUE);
  199. {диалог пользователю об успешно проведенной операции}
  200.         writeln('Элемент успешно добавлен перед заданным элементом!');
  201.     end;
  202. {конец тела процедуры}
  203. end;
  204. {---------------------------------------------------------------------------}
  205. {Процедура: добавление элемента после заданного элемента}
  206. {---------------------------------------------------------------------------}
  207. procedure addElemAfterTarget;
  208. var
  209. {указатель на добавляемый элемент}
  210.     add       : Tptr;
  211. {вспомогательный указатель для проведения операции вставки}
  212.     p         : Tptr;
  213. {номер элемента после которого планируется добавить новый элемент}
  214.     index     : integer;
  215. {счетчик цикла}
  216.     i         : integer;
  217. {хранит общее количество элементов в списке. Дело в том, что существует уже
  218.  специальная функция, определяющая общее количество элементов списка, но,
  219.  чтобы не тратить ресурсы программы на постоянные вызовы, лучше задействовать
  220.  специальную отдельную переменную}
  221.     number    : integer;
  222. {начало тела процедуры}
  223. begin
  224. {получаем общее количество элементов списка}
  225.     number := getCountElem;
  226. {надо понимать следующее: если количество элементов в списке меньше двух, то
  227.  невозможно добавить элемент после заданного элемента, это уже будет операция,
  228.  равноценная операции добавления элемента в конец списка}
  229.     if(number <= 1) then
  230. {диалог пользователю о том, что операцию добавления невозможно провести}
  231.         writeln('Список содержит недостаточное количество элементов для вставки!')
  232. {иначе}
  233.     else
  234.     begin
  235. {сообщаем пользователю общее количество элементов в списке на текущий момент}
  236.         writeln('На данный момент в списке элементов: ', number);
  237. {циклически запрашиваем номер элемента перед которым необходимо произвести
  238.  вставку. Также проверяем, чтобы введенный индекс находился в допустимых
  239.  диапазонах}
  240.         repeat
  241.             write('Введите номер элемента после которого происходит вставка [1 ...', number - 1, ']: ');
  242.             readln(index);
  243.         until((index >= 1) and (index <= number - 1));
  244. {устанавливаем указатель р на первый элемент списка (напомню, что первый
  245.  элемент и заглавный элемент списка - разные элементы!)}
  246.         p := head^.link;
  247. {необходимо "допрыгать" указателем р до элемента, после которого необходимо
  248.  произвести вставку нового элемента}
  249.         for i := 1 to index - 1 do
  250. {перемещаемся на следующий элемент списка}
  251.             p := p^.link;
  252. {выделяем память под добавляемый элемент}
  253.         add := createElem;
  254. {устанавливаем связь между добавляемым элементом и элементом, перед которым
  255.  добавляемый элемент будет вставлен}
  256.         add^.link := p^.link;
  257. {устанавливаем связь между добавляемым элементом и элементом, после которого
  258.  добавляемый элемент будет вставлен}
  259.         p^.link := add;
  260. {общее количество элементов списка увеличиваем на единицу}
  261.         headElem(TRUE);
  262. {диалог пользователю об успешном добавлении элемента}
  263.         writeln('Элемент успешно добавлен после заданного элемента!');
  264.     end;
  265. {конец тела процедуры}
  266. end;
  267. {---------------------------------------------------------------------------}
  268. {Процедура: удаление элемента из начала списка}
  269. {---------------------------------------------------------------------------}
  270. procedure delElemFromBegin;
  271. var
  272. {вспомогательный указатель, помогающий произвести операцию удаления}
  273.     p      : Tptr;
  274. {начало тела процедуры}
  275. begin
  276. {если в списке нет ни одного элемента, то удаление физически невозможно}
  277.     if(getCountElem < 1) then
  278.         writeln('В списке не обнаружено элементов! Удаление невозможно!')
  279. {иначе в списке имеется хотя бы один элемент и удаление физически возможно}
  280.     else
  281.     begin
  282. {устанавливаем вспомогательный указатель на первый элемент списка}
  283.         p := head^.link;
  284. {перемещаем заглавный элемент на второй элемент списка, то есть фактически
  285.  убираем заглавный элемент с первого элемента}
  286.         head^.link := p^.link;
  287. {полностью "отвязываем" первый элемент, чтобы он ни на что больше не ссылался}
  288.         p^.link := NIL;
  289. {удаляем первый элемент из списка}
  290.         dispose(p);
  291. {оповещаем пользователя об успешном удалении элемента}
  292.         writeln('Элемент успешно удален из начала списка!');
  293. {уменьшаем количество элементов в списке на единицу}
  294.         headElem(FALSe);
  295.     end;
  296. {конец тела процедуры}
  297. end;
  298. {---------------------------------------------------------------------------}
  299. {Процедура: удаление элемента из конца списка}
  300. {---------------------------------------------------------------------------}
  301. procedure delElemFromEnd;
  302. var
  303. {вспомогательный указатель, помогающий произвести удаление элемента}
  304.     p      : Tptr;
  305. {начало тела процедуры}
  306. begin
  307. {если в списке нет ни одного элемента, то удаление физически невозможно}
  308.     if(getCountElem < 1) then
  309.         writeln('В списке не обнаружено элементов! Удаление невозможно!')
  310. {иначе в списке имеется хотя бы один элемент и удаление физически возможно}
  311.     else
  312.     begin
  313. {устанавливаем вспомогательный указатель на заглавный элемент списка!
  314.  НАПОМНЮ, что заглавный и первый элемент списка - разные элементы}
  315.         p := head;
  316. {задача указателя р - достичь предпоследнего элемента списка, то есть
  317.  встать перед удаляемым элементом}
  318.         while(p^.link^.link <> NIL) do
  319. {переход на следующий элемент}
  320.             p := p^.link;
  321. {производим удаление последнего элемента из списка}
  322.         dispose(p^.link);
  323. {и чтобы список остался в согласованном состоянии, надо, чтобы последний
  324.  элемент (до удаления он являлся предпоследним) ссылался в NIL}
  325.         p^.link := NIL;
  326. {оповещение пользователя об успешном удалении элемента из списка}
  327.         writeln('Элемент успешно удален из конца списка!');
  328. {уменьшаем количество элементов на единицу}
  329.         headElem(FALSe);
  330.     end;
  331. {конец тела процедуры}
  332. end;
  333. {---------------------------------------------------------------------------}
  334. {Процедура: удаление срединного элемента}
  335. {---------------------------------------------------------------------------}
  336. procedure delCenterElem;
  337. var
  338. {вспомогательные указатели для удаления срединного элемента из списка}
  339.     p, p1  : Tptr;
  340. {отвечает за общее количество элементов в списке}
  341.     number : integer;
  342. {отвечает за номер удаляемого элемента}
  343.     index  : integer;
  344. {счетчик цикла}
  345.     i      : integer;
  346. {начало тела процедуры}
  347. begin
  348. {вычисляем общее количество элементов в списке}
  349.     number := getCountElem;
  350. {срединный элемент - это любой элемент в списке, не являющийся первым или
  351.  последним элементом, поэтому, если в списке меньше трех элементов, то
  352.  срединных элементов нет в списке и удалять нечего}
  353.     if(number <= 2) then
  354.         writeln('В списке нет срединных элементов!')
  355. {иначе в списке больше двух элементов}
  356.     else
  357.     begin
  358. {запрашиваем от пользователя номер удаляемого элемента, причем номер элемента
  359.  не должен быть первым или последним}
  360.         repeat
  361.             write('Введите номер удаляемого элемента [2 ...', number - 1, ']: ');
  362.             readln(index);
  363.         until((index >= 2) and (index <= number - 1));
  364. {устанавливаем вспомогательный указатель на первый элемент списка}
  365.         p := head^.link;
  366. {устанавливаем указатель р на элемент, стоящий перед удаляемым элементом}
  367.         for i := 1 to index - 2 do
  368.             p := p^.link;
  369. {устанавливаем вспомогательный указатель р1 на удаляемый элемент}
  370.         p1 := p^.link;
  371. {разрываем связь между удаляемым элементом и элементом, стоящим перед
  372.  удаляемым и связываем элементы перед удаляемым и после удаляемого}
  373.         p^.link := p1^.link;
  374. {разрываем связь между удаляемым элементом и элементом, стоящим после
  375.  удаляемого элемента}
  376.         p1^.link := NIL;
  377. {производим операцию удаления элемента}
  378.         dispose(p1);
  379. {оповещаем пользователя об успешном удалении}
  380.         writeln('Срединный элемент успешно удален из списка!');
  381. {уменьшаем количество элементов списка на единицу}
  382.         headElem(FALSE);
  383.     end;
  384. {конец тела процедуры}
  385. end;
  386. {---------------------------------------------------------------------------}
  387. {Процедура: удаление всех элементов из списка}
  388. {---------------------------------------------------------------------------}
  389. procedure delAllElem;
  390. var
  391. {вспомогательный указатель, помогающий удалить все списочные элементы}
  392.     p : Tptr;
  393. {начало тела процедуры}
  394. begin
  395. {устанавливаем вспомогательный указатель р на первый элемент списка}
  396.     p := head^.link;
  397. {пока в списке не останется элементов, то есть когда заглавный элемент списка
  398.  будет ссылаться в NIL, производим удаление элементов поштучно}
  399.     while(head^.link <> NIL) do
  400.     begin
  401. {перемещаем заглавный элемент на второй элемент списка}
  402.         head^.link := p^.link;
  403. {разрушаем связь между первым и вторым элементом списка, поскольку сейчас
  404.  первый элемент будет удален}
  405.         p^.link := NIL;
  406. {производим удаление первого элемента списка}
  407.         dispose(p);
  408. {вспомогательный указатель р устанавливаем на "новый" первый элемент списка}
  409.         p := head^.link;
  410.     end;
  411. {конец тела процедуры}
  412. end;
  413. {---------------------------------------------------------------------------}
  414. {Процедура: печать элементов списка из начала в конец}
  415. {---------------------------------------------------------------------------}
  416. procedure printListFromBeginToEnd;
  417. var
  418. {вспомогательный указатель, помогающий произвести операцию печати списка}
  419.     p : Tptr;
  420. {начало тела процедуры}
  421. begin
  422. {устанавливаем вспомогательный указатель на первый элемент списка, если
  423.  таковой имеется, иначе указатель начинает ссылаться в NIL}
  424.     p := head^.link;
  425. {обращаемся к заглавному элементу и получаем количество элементов списка.
  426.  Напомню, что информационное поле заглавного элемента хранит общее количество
  427.  элементов во всем списке}
  428.     writeln('Количество элементов в списке: ', head^.inf);
  429. {если в списке нет ни одного элемента, то оповещаем об этом пользователя}
  430.     if(head^.link = NIL) then
  431.         writeln('Печать невозможна, так как список не содержит элементов!')
  432. {иначе в списке имеется хотя бы один элемент}
  433.     else
  434.     begin
  435. {начинаем пробежку по списку и выпечатываем информационные поля элементов на
  436.  экран пользователю}
  437.         write('Список имеет вид: ');
  438.         while(p <> NIL) do
  439.         begin
  440. {печать значения элемента на экран пользователя}
  441.             write(p^.inf, ' ');
  442. {переход к следующему элементу списка}
  443.             p := p^.link;
  444.         end;
  445.     end;
  446. {конец тела процедуры}
  447. end;
  448. {---------------------------------------------------------------------------}
  449. {Функция: главное меню программы}
  450. {---------------------------------------------------------------------------}
  451. function mainMenu : integer;
  452. var
  453. {отвечает за номер пункта выбранного пользователем}
  454.     sel : integer;
  455. {начало тела функции}
  456. begin
  457. {циклически пользователю предлагается выбрать один из пунктов для совершения
  458.  соответствующей операции, причем, проверяется, чтобы его выбор был правилен}
  459.     repeat
  460.         clrscr;
  461.         writeln(' 1 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА В НАЧАЛО СПИСКА');
  462.         writeln(' 2 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА В КОНЕЦ СПИСКА');
  463.         writeln(' 3 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА ПЕРЕЗ ЗАДАННЫМ ЭЛЕМЕНТОМ');
  464.         writeln(' 4 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА ПОСЛЕ ЗАДАННОГО ЭЛЕМЕНТА');
  465.         writeln(' 5 - УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ НАЧАЛА СПИСКА');
  466.         writeln(' 6 - УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ КОНЦА СПИСКА');
  467.         writeln(' 7 - УДАЛЕНИЕ СРЕДИННОГО ЭЛЕМЕНТА');
  468.         writeln(' 8 - ПЕЧАТЬ ЭЛЕМЕНТОВ СПИСКА ИЗ НАЧАЛА В КОНЕЦ');
  469.         writeln(' 9 - ПОЛУЧИТЬ КОЛИЧЕСТВО ЭЛЕМЕНТОВ СПИСКА');
  470.         writeln('10 - УДАЛЕНИЕ ВСЕХ ЭЛЕМЕНТОВ ИЗ СПИСКА');
  471.         writeln('11 - ВЫХОД');
  472.         write('Выберите один из предложенных пунктов: ');
  473.         readln(sel);
  474.     until((sel >= 1) and (sel <= 11));
  475.     writeln;
  476. {в качестве ответа функция возвращает номер пункта меню}
  477.     mainMenu := sel;
  478. {конец тела функции}
  479. end;
  480. {---------------------------------------------------------------------------}
  481. {главный блок программы}
  482. {---------------------------------------------------------------------------}
  483. var
  484. {отвечает за пункт меню указанный пользователем}
  485.     sel : integer;
  486. begin
  487. {очистка экрана от прошлых выводов}
  488.     clrscr;
  489. {выделяем память под заглавный элемент списка, который является впоследствии
  490.  неудаляемым элементом}
  491.     new(head);
  492. {ссылается заглавный элемент в NIL}
  493.     head^.link := NIL;
  494. {поскольку список пуст, то присваиваем значение 0}
  495.     head^.inf := '0';
  496. {происходит циклическая визуализация меню для пользователя, до тех пор, пока
  497.  пользователь не выберет пункт, отвечающий за выход из программы}
  498.     repeat
  499.         sel := mainMenu;
  500.         case sel of
  501.             1:
  502.             begin
  503. {добавление элемента в начало списка}
  504.                 addElemToBegin;
  505.                 writeln('Элемент успешно добавлен в начало списка!');
  506.                 readkey;
  507.             end;
  508.             2:
  509.             begin
  510. {добавление элемента в конец списка}
  511.                 addElemToEnd;
  512.                 writeln('Элемент успешно добавлен в конец списка!');
  513.                 readkey;
  514.             end;
  515.             3:
  516.             begin
  517. {добавление элемента перед заданным элементом}
  518.                 addElemBeforeTarget;
  519.                 readkey;
  520.             end;
  521.             4:
  522.             begin
  523. {добавление элемента после заданного элемента}
  524.                 addElemAfterTarget;
  525.                 readkey;
  526.             end;
  527.             5:
  528.             begin
  529. {удаление элемента из начала списка}
  530.                 delElemFromBegin;
  531.                 readkey;
  532.             end;
  533.             6:
  534.             begin
  535. {удаление элемента из конца списка}
  536.                 delElemFromEnd;
  537.                 readkey;
  538.             end;
  539.             7:
  540.             begin
  541. {удаление срединного элемента из списка}
  542.                 delCenterElem;
  543.                 readkey;
  544.             end;
  545.             8:
  546.             begin
  547. {печать элементов списка из начала в конец}
  548.                 printListFromBeginToEnd;
  549.                 readkey;
  550.             end;
  551.             9:
  552.             begin
  553. {получение общего количества элементов списка}
  554.                 write('Количество элементов списка: ', getCountElem);
  555.                 readkey;
  556.             end;
  557.             10:
  558.             begin
  559. {удаление всех элементов из списка}
  560.                 delAllElem;
  561.                 writeln('Все элементы успешно удалены из списка!');
  562.                 readkey;
  563.             end;
  564.         end;
  565.     until(sel = 11);
  566. {перед тем как закрыть программу, необходимо позаботиться о том, чтобы
  567.  не было утечки памяти, поэтому, следует удалить все элементы из списка}
  568.     delAllElem;
  569. {завершающий оператор программы}
  570. end.

 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?
Занятия по информатике