Задачи на собеседованиях: опять односвязные списки

Еще одна задача в продолжение задачи об односвязных списках.

Дано: односвязный список N₁->N₂->N₃->... и указатель на его голову N₁. Существует вероятность, что список зациклен, и узел N_n указывает на любой из узлов списка. Например, так N₁->N₂->N₃->N₄->...->N_n->N₃->N₄->... .

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

Сортировка указателей

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

Ubuntu и g++ 3.4

У меня стоит Ubuntu 9. Понадобился компилятор g++ 3.4. А его нет на Ubuntu. gcc 3.4 — есть, а g++ — нет. Нет, и не будет.

В том же форуме предлагают способ — скачать дебиановские пакеты и установить. Но обнаружилось две проблемы. Первая — эти пакеты старые и их установка сносит крышу убунтовскому менеджеру обновлений. Чтобы восстановить его работоспособность, эти пакеты нужно удалить. Вторая — компилятор-то установился. Но то ли из-за несовместимости версий пакетов, то ли еще из-за чего, но мои сборки рушатся и падают, если я использую g++ 3.4.

В конце концов мне это надоело, я удалил все неродные пакеты и скачал отсюда два архива с исходниками — gcc-core-3.4.6.tar.bz2 и gcc-g++-3.4.6.tar.bz2. Всё собралось на ура и отлично работает. Единственное "но" — собирать нужно c помощью gcc-3.4 (он-то в системе уже есть).

Предупреждения GCC ч.2

Наткнулся тут в тексте статьи на Хабре:

...посмотрим внимательно на вывод компилятора при максимально включенных предупреждениях

$ g++ -W -Wall test.cpp

К самой статье это отношения не имеет, но хочется заметить, что заблуждение насчет максимально включенных предупреждений компилятора встречается довольно часто — -Wall и -Wextra (-W) это еще не все предупреждения. К сожалению, путаница по большей части возникает из-за разработчиков GCC. Начать с того, что имя опции -Wall само по себе вводит в заблуждение, так они еще добавляют или удаляют предупреждения от версии к версии, или вообще меняют их смысл, чем лично меня иногда просто ставят в тупик. Но надо отдать им должное — компилятор все-таки развивается, и сейчас с помощью предупреждений можно узнать гораздо больше, чем в более ранних версиях.

Например, в последней версии GCC (4.4) есть полезные предупреждения, которые нужно включать самостоятельно:

• -Wcast-qual
  Предупреждает о преобразованиях типа "из const char * в char *".
• -Wconversion
  Предупреждает, если при преобразовании типов может произойти потеря данных. Например, при преобразовании из long в short.
• -Wredundant-decls
  Предупреждает об повторном объявлении чего-нибудь в той же области видимости, даже если это ни на что не влияет.
• -Wshadow
  Предупреждает, если объявление переменной перекрывает объявленную ранее переменную с таким же именем.
• -Wsign-conversion
  Предупреждает, если результат выражения может изменить знак. Например, при преобразовании из int в unsigned int.
• -Wunreachable-code
  Предупреждает, если какой-то фрагмент кода никогда не будет выполнен. Например, если перед этим фрагментом стоит return. Этот флаг специально не был включен в группу -Wall для того, чтобы можно было разделять сборки debug и release.

И еще некоторые другие:

• -Wcast-align
• -Wformat-nonliteral
• -Wformat-security
• -Wformat-y2k
• -Winit-self
• -Wlogical-op
• -Wmissing-format-attribute
• -Wmissing-include-dirs
• -Woverlength-strings

Отключение спикера на Ubuntu

Оказывается всё довольно просто. Чтобы отключить PC speaker на Ubuntu, нужно открыть файл /etc/modprobe.d/blacklist и добавить в него строку:

blacklist pcspkr

После этого нужно перезагрузиться.

Источник: ubuntuforums.org

Цитата: Хайнлайн

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

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

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

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

Фразу: «Я (мы, ты) просто должен…» — следует понимать в том смысле, что делать этого не нужно. Слова: «Это понятно каждому» — предупреждают о возможных сложностях. Если слышишь: «Конечно» — лучше проверить все самому. Эти маленькие клише и прочие им подобные, если уметь правильно читать их, позволяют хорошо ориентироваться.

Роберт Хайнлайн,
"Достаточно времени для любви,
или Жизни Лазаруса Лонга"