Программирование. Принципы и практика использования C++ Исправленное издание

Функция create просто создает список List свободной памяти. Она напоминает комбинацию конструктора (функция init выполняет инициализацию) и оператора new (функция malloc выделяет память).

 struct List* create /* создает пустой список */
 {
  struct List* lst =
  (struct List*)malloc(sizeof(struct List));
  init(lst);
  return lst;
 }

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

 void clear(struct List* lst) /* удаляет все элементы списка lst */
 {
  assert(lst);
  {
  struct Link* curr = lst–>first;
  while(curr) {
  struct Link* next = curr–>suc;
  free(curr);
  curr = next;
  }
  lst–>first = lst–>last = 0;
  }
 }

Обратите внимание на способ, с помощью которого мы обходим список, используя член suc класса Link. Мы не можем получить безопасный доступ к члену объекта после его удаления с помощью функции free, поэтому ввели переменную next, с помощью которой храним информацию о своей позиции в контейнере List, одновременно удаляя объекты класса Link с помощью функции free.

Если не все объекты структуры Link находятся в свободной памяти, лучше не вызывать функцию clear, иначе она вызовет разрушение памяти.

Функция destroy, по существу, противоположна функции create, т.е. она представляет собой сочетание деструктора и оператора delete.

 void destroy(struct List* lst) /* удаляет все элементы списка lst;
  затем удаляет сам список lst */
 {
  assert(lst);
  clear(lst);
  free(lst);
 }

Обратите внимание на то, что перед вызовом функции очистки памяти (деструктора) мы не делаем никаких предположений об элементах, представленных в виде узлов списка. Эта схема не является полноценной имитацией методов языка С++ — она для этого не предназначена.

Функция push_back — добавление узла Link в конец списка — вполне очевидна.

 void push_back(struct List* lst, struct Link* p) /* добавляет элемент p
  в конец списка lst */
 {
  assert(lst);
  {
  struct Link* last = lst–>last;
  if (last) {
  last–>suc = p; /* добавляет узел p после узла last */
  p–>pre = last;
  }
  else {
lst–>first = p; /* p — первый элемент */
  p–>pre = 0;
  }
  lst–>last = p; /* p — новый последний элемент */
  p–>suc = 0;
  }
 }

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

Функцию erase можно было бы написать следующим образом:

 struct Link* erase(struct List* lst, struct Link* p)

/* удаляет узел p из списка lst;

  возвращает указатель на узел, расположенный после узла p
 */
 {
  assert(lst);
  if (p==0) return 0; /* OK для вызова erase(0) */
  if (p == lst–>first) {
  if (p–>suc) {

lst–>first = p–>suc; /* последователь становится первым */

  p–>suc–>pre = 0;
  return p–>suc;
  }
  else {

lst–>first = lst–>last = 0; /* список становится пустым */

  return 0;
  }
  }
  else if (p == lst–>last) {
  if (p–>pre) {

lst–>last = p–>pre; /* предшественник становится последним */

  p–>pre–>suc = 0;
  }
  else {

lst–>first = lst–>last = 0; /* список становится пустым */

  return 0;
  }
  }
  else {
  p–>suc–>pre = p–>pre;
  p–>pre–>suc = p–>suc;
  return p–>suc;
  }
 }

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

 struct Name {