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

    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 {

  struct Link lnk; /* структура Link нужна для выполнения ее операций */

  char* p;         /* строка имен */

};

До сих пор все было хорошо, хотя остается загадкой, как мы можем использовать этот член Link? Но поскольку мы знаем, что структура List хранит узлы Link в свободной памяти, то написали функцию, создающую объекты структуры Name в свободной памяти.

struct Name* make_name(char* n)

{

  struct Name* p = (struct Name*)malloc(sizeof(struct Name));

  p–>p = n;

  return p;

}

Эту ситуацию можно проиллюстрировать следующим образом:

Попробуем использовать эти структуры.

int main

{

  int count = 0;

  struct List names; /* создает список */

  struct List* curr;

  init(&names);

  /* создаем несколько объектов Names и добавляем их в список: */

  push_back(&names,(struct Link*)make_name("Norah"));

  push_back(&names,(struct Link*)make_name("Annemarie"));

  push_back(&names,(struct Link*)make_name("Kris"));

  /* удаляем второе имя (с индексом 1): */

  erase(&names,advance(names.first,1));

  curr = names.first; /* выписываем все имена */

  for (; curr!=0; curr=curr–>suc) {

    count++;

    printf("element %d: %s\n", count, ((struct Name*)curr)–>p);

  }

}

Итак, мы смошенничали. Мы использовали приведение типа, чтобы работать с указателем типа Name* как с указателем типа Link*. Благодаря этому пользователь знает о библиотечной структуре Link. Тем не менее библиотека не знает о прикладном типе Name. Это допустимо? Да, допустимо: в языке C (и C++) можно интерпретировать указатель на структуру как указатель на ее первый элемент, и наоборот.

Очевидно, что этот пример можно также скомпилировать с помощью компилятора языка С++.

ПОПРОБУЙТЕ