"Снова ССЗБ" или "Как сбросить пароль в навигаторе"

Описана процедура снятия известного заранее пароля с устройств Windows CE.

У меня есть навигатор. Prestigio GeoVision 4300. Используется с разными целями. Незадолго до его приобретения мне один знакомый показал одну фишку -- на навигаторах, говорит, стоит обычный Windows CE, это почти что Windows Mobile, и есть Total Commander для него. И показал. Рабочий стол показал, меню пуск. Ярлычки. Почти что обычная винда. Я был немного удивлён. Кстати, разговор этот начался с того, что я спросил его -- что, рынок КПК и Windows Mobile умер? Он сказал -- КПК, да, сейчас сплошь смартфоны, а Windows Mobile -- вот.

И вот решил я посмотреть, можно ли на моём навигаторе так же сделать.

(читать дальше)

Покопался по меню, нашёл загадочное "Путь навигации". Там можно было указать путь к произвольному экзешнику из внутренней памяти или с карточки. Карточки у меня тогда ещё не было. Во внутренней памяти был только Navitel. Ставим ActiveSync, копируем tc.exe во внутреннюю флешечку. Указываем его как "Путь навигации". Ничего не происходит. Жмём в меню навигатора "Навигация" и получаем Total Commander. Далее техника проста. Запускаме explorer.exe и получаем рабочий стол. Эта процедура на форумах называется "разлочка". Почему -- мне неведомо, т.к. разлочка подразумевает раскрытие хитрым способом недоступных ранее возможностей, а тут всё есть изначально, только путь укажи. Как это надо делать, я прочитал позже, но сделал я всё правильно, короче. Это было месяца джва назад.

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

Однажды (это было вчера), я задался вопросом -- а можно ли запаролить включение навигатора? В панели управления, традиционной для всех систем семейства Windows, обнаружилась иконка Password, рядом была Owner Info (информация о пользователе), я её нажал. Можно было указать имя-фамилию, телефон и кое-что ещё. Я подумал, что было бы неплохо, чтобы если я его потеряю, нашедший знал кому возвращать, и указал свои данные. Я сделал Suspend (неполное выключение), после него при включении показалось диалоговое окошко со сведениями, которое можно было закрыть. Я это сделал. Потом я перешёл к иконке Password. Там надо было ввести пароль (я написал "12345"), подтверждение. Также я поставил галочки "спрашивать пароль при старте" и "при скринсейвере тоже". Сделал Suspend и включил. Показалось то же окошко со сведениями, но ещё было поле редактирования для ввода пароля. Я жму на виртуальной клавиатуре "1" и вижу, что в поле появилось ДВА символа. Ну, бывает, тапнул два раза. Выделяю стилусом всё, жму Backspace, пробую ещё раз. Опять два символа. проверяю другие кнопки, оказывается все, кроме этого самого Backspace генерируют по два символа, а он удаляет таки по одному. Ну ладно, мало ли. Пробую ввести "12345", забив на два символа. Пишет -- пароль неверный. Ок, пойдём длинным путём. 1 БЭКСПЕЙС 2 БЭКСПЕЙС 3 БЭКСПЕЙС 4 БЭКСПЕЙС 5 БЭКСПЕЙС. Победа. Пароль подходит. В этот момент я ехал в метро. Я подумал -- о, как хорошо! Никто же не догадается, как пароль вводить надо!

Потом я решил, что надо посмотреть, будет ли пароль при полной перезагрузке. Дело в том, что не все настройки сохраняются при полной перезагрузке. Например, все ярлыки на программы из меню пропадают. Шрифты установленные тоже пропадают. Жесть короче. Выключаю навигатор полностью, после включения лицезрею ту же картинку, но виртуальной клавиатуры нет. Пароль-то я введу, я его знаю, но через что?! Я понял, что я напоролся. Я попробовал долго удерживать ресет, вдруг получится жёсткая перезагрузка? Нет. Я отложил это дело до приезда домой.

Дома я стал читать форумы. Одно из первых, на что я наткнулся, было следующее:

После Разлочки Навигатора, ни в коем случае не ставте на него пароль!!!
Но мы же русские, сначала делаем, а потом читаем И так, пароль поставлен, что делать?!
Ну для начала, наверное задать себе вопрос, нахрена я его туда ставил?!

(авторский стиль сохранён)

Это вызвало дикий ржач, но скорее со слезами.

Дальнейшее чтение привело к скачиванию некоего архива (с файл-хостинга; на том форуме нужна была регистрация для скачивания файлов), в котором было два файла -- YFAutoRun.inf и TipsApp.exe. Что это, было понятно. Первый файл указывает, что при старте надо запускать что-то, а второй этим что-то и является -- он открывает экранную клавиатуру для ввода пароля. Я подключил навигатор к компу и ActiveSync мне написал, что навигатор под паролем и для доступа его надо ввести. Пароль я знал. Я его на навигаторе ввести не мог! Но на компьютере клава есть, вводим пароль, получаем доступ. Согласно рекомендации, файлы надо было скопировать на карточку. Я так и сделал (к тому моменту карточка уже была). Перезапускаю -- эффекта нет. Тогда я скопировал их ещё и во внутреннюю память, с таким же результатом, правда. Почему -- я узнал позднее. У меня была другая оболочка, не YF.

Рекомендации делились на несколько типов -- 1) шаманство с автозагрузкой и файлами настроек -- мне не подходило, т.к. всё шаманство надо было делать в настройках, которые лежат в файле в ResidentFlash2, доступа в который из ActiveSync нет, да и оболочка у меня другая. 2) правка реестра -- признаться, эту-то возможность я и не изучил как следует, но она чревата серьёзными проблемами 3) перепрошивка устровйства; последнего делать мне не хотелось, однако примечательно, что для странных проблем у WinCE то же решение, что и у обычной винды -- переустановка (тут, правда, своя специфика).

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

Потом я подумал, может подключить USB-клавиатуру? Однако, мало того, что её у меня не было, так ещё и включение USB-хоста в навигаторах является процедурой нетривиальной и редко рабочей. Опять индивидуальный подход, перепайка платы, левые спец. драйверы. И после этого у кого-то только флешки работают, у кого-то только клавиатура...

Потом нашёл упоминание некоей проги -- Remote Control CE. Она запускается на большом компьютере и позволяет через интерфейсы ActiveSync запускать программы на устройстве. Чудесно, это то, что мне нужно. Но опять просят зарегистрироваться, чёрт возьми. Как и с TipsApp.exe я пошёл в гугл. Там была ещё одна ссылка на эту прогу, но на другом форуме тоже нужна была регистрация. А прога была самописная, автор был на обоих форумах. Ну, делать нечего, регистрируюсь. Тут я понял, что запрет на скачивание файлов господам без регистрации реально увеличивает число регистраций. Кстати вот один из форумов, где она есть -- 4pna.com/showthread.php?p=202395

Программа запустилась и подключилась к устройству на ура, но карты памяти в списке папок не было. Были только стандартные и внутренняя флешка. Но я же уже скопировал TipsApp.exe на внутреннюю флешку! Нажимаю на него правой кнопкой и выбираю Run. На экране навигатора появляется клавиатура! 1 БЭКСПЕЙС 2 БЭКСПЕЙС 3 БЭКСПЕЙС 4 БЭКСПЕЙС 5 БЭКСПЕЙС. ЙЕС, это победа! Срочно иду в панель управления выключать пароль обратно.

Вот так. Не ставьте пароль.

Если же вам досталось устройство с неизвестным паролем, боюсь, единственный выход -- действительно перепрошивка.

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

---

Об обратной совместимости

В винде есть баг. Его многие замечали, наверное. Если программа, имеющая иконку в трее, падает, иконка продолжает висеть, пока не наведёшь на неё мышку. Этот баг прошёл красной нитью со времён Windows 95 и сохранился даже в семёрке.

Только что я узнал, что в Windows CE 5.0 он тоже есть.

---

Метромузыка

Сегодня на ст. м. Чертановская в 22:04 в вестибюле станции из динамиков вместо рекламы играли Emmanuelle Song. Я не спорю, песня хорошая, но для метро это слишком.

---

Что такое мэдскиллз?

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

Отвечу на него таки. Мэдскиллз -- это картинка, нарисованная врукопашную или обработанная при помощи программы уровня MS Paint (раньше она называлась Paintbrush). Как правило, отличается невысокими художественными качествами. В качестве примера продемонстрирую мэдскиллз, нарисованный мной при помощи пэйнта и тачпада джва года назад:

Lurkmore считает немного по-другому.

---

Рекомендованные видео на я-трубе

Захожу я на я-трубу. А там...

Recommended videos
Машина для сдачи спермы
Because you watched
Люди превращаются в героев аниме

.
.
.

---

Перекрытие метро

Уж открывать что-то наши люди умеют плохо, а закрывать -- просто замечательно.
После ремонта и открытия Большого Театра внезапно выяснилось, что вибрации в подвале слишком сильны от метро, поэтому решили установить виброзащитные шпалы или что-то в этом роде. Напомню, что ещё виброзащитные шпалы стоят под библиотекой имени Ленина (и там строже скоростной режим), однако будут ставить на зелёной ветке такие же шпалы или что-то ещё -- я не знаю.

В связи с установкой этого безобразия кусок зелёной ветки в середине закрывают ПОЛНОСТЬЮ. На два дня. А потом ещё на два дня. Две недели по выходным -- суббота и воскресенье. Закрыли Маяковскую, Тверскую, Театральную. Поезда ходят до Белорусской и до Новокузнецкой, а потом обратно.

Имел счастье и необходимость ехать сегодня по зелёной ветке и об'езжать этот кусок. Организовали об'езд хорошо. Как можно догадаться, все пассажиры решили объехать через кольцевую линию. Она не предназначена для таких нагрузок, несмотря на субботу (особо не предназначены пересадки). На Павелецкой ситуация была лучше, т.к. переход полностью пешеходный без применения эскалаторов. На Белорусской эскалатора на пересадке три и один включали по очереди то туда, то сюда. Помогало это слабо, толпа была с обоих сторон.

На платформах в ту сторону, куда поезда не ехали, каждые 5 метров стоял милиполиционерейский или сотрудник метро и отвечал на вопросы граждан. Схема метро превратилась в фетиш. Идут люди, держат в руках схемы схемы схемы, на стенах Белорусской и Новокузнецкой каждые 10 метров схемы схемы схемы. На Павелецкой ещё в мегафон об'являли, а по поездному радио и громокоговорителях на остальных станциях -- ещё дополнительно.

Все же знали, что движения не будет, всех ещё за две недели предупредили, почему же никто не знает, как ему ехать? Откуда эти толпы у карт?

Табло о том, сколько времени прошло с последнего поезда, функционировало очень интересно. В ту сторону, куда поезда не ходили, оно показывало просто точку (" .  "). В другую сторону показывало время, но очень странно. На Новокузнецкой таймер обнулялся при в'езде поезда на станцию (об этом см. ниже) и при отходе, а на Белорусской только при отходе, но не после того, как 0.8 первого вагона в'ехало в туннель (как обычно), а когда в'ехало ТРИ вагона. Может вообще вручную кнопочку жмут.

Далее про систему подачи поездов. Как знают некоторые, оборотный тупик на Белорусской есть, но не в ту сторону. А на Новокузнецкой только соединительная ветка, но тоже не в ту сторону. Что же делать? Применили извращение. Приведу пример для Новокузнецкой, для Белорусской система та же. Поезд приезжает, высаживает пассажиров и сдаёт задом в соединительную ветку (1). Дальше он опять передом выезжает оттуда на соседний путь (2), после чего трогается по второму пути в обратном направлении (3). Итого: 3 раза поменять направление движение, чтобы обернуть состав.

Хорошо хоть на зелёной ветке два депо, так что не надо было заботиться о том, чтобы к началу рабочего дня и до его конца поезда непрерывно находились на линии (если бы депо было только одно, поезда на одной из половин было бы просто некуда складывать).

Обратно я решил не ехать тупо ко кольцевой. Неинтересно. Я проехал сначала по оранжевой (2 перегона), потом по салатовой (1 перегон), потом по серой (1 перегон), потом по коричневой (1 перегон) и вот я снова на зелёной!

Пойду искать у себя в коробках Densha de GO!

---

Загадка

Сделал говнокод. Функционирует так, как мне надо. Попробуйте угадать, что он делает.

sFmt.Format(_T("%%.%de"),nDigits-1);
sBuf.Format(_T(sFmt), fValue);
sscanf(sBuf,"%lf",&fValue);
// шаманим-шаманим
sFmt.Format(
	_T("%%.%df\t"),
		(int)(fabs(fValue)>=pow((double)10,(int)(nDigits-1))?0:
			(FLT_MIN>-1+nDigits-floor(fabs(fValue)?-1+nDigits:
				log10(fabs(fValue))))));
sBuf.Format(_T(sFmt),fValue);
sItem += sBuf;

Типы переменных:
sItem, sBuf, sFmt -- CString
fValue -- float
nDigits -- int

В принципе, этот кусок выполняется в цикле и на самом деле nDigits выбираются из массива типа aDigits[ix], а fValue в каждой итерации разный, потому что тоже выбран из массива, но это неважно.

Форматирование такое, потому что не хотел, чтобы за конец строки вылезало. Считайте меня Маяковским.

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

(показать ответ)

Ответ:
Код добавляет (конкатенирует) к sItem число с заданным количеством значащих цифр, а вместо нуля добавляет "0". Исходное число содержится в sBuf, где оно и приводится к необходимому виду.

Можно ли было сделать проще?

---

CEdit 3d-look / Трёхмерный CEdit

How to make 3D-look for dynamically created CEdit?
Как сделать трёхмерный CEdit, когда он создаётся динамически?

Read in English a little below.
В соответствии с тем, что я писал несколько постов назад, стараюсь донести до других частичку своего опыта. То, на что я убил несколько часов. Ввиду особой важности (куча народа ищет ответ по интернетам), привожу опыт сразу на двух языках. Сначала на английском.

EN:

(read in English)

Before you begin reading, you need to know, that every control in Windows is a window.

I was using MFC (waratte mo ii yo) and I had to make some CEdit edit-fields at runtime, create it dynamically. I wrote:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

where:
ix -- loop variable;
dlg_data[ix] -- structure with some data;
dlg_data[ix].m_edtField -- pointer to CEdit control;
bVis -- boolean, true if CEdit must be created visible;
rRect -- calculated coordinates of control in CRect;
this -- pointer to class-variable, derieved from CWnd;
dlg_data[ix].m_nedtFieldID -- ID for control, generated at runtime.

This sentence, as I thought, created CEdit for me, but it was without border, like this:

I read some documentation and decided to use WS_BORDER, so I modified sentense:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_BORDER,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

The border appeared, but it was plain, like this:

I wanted 3D-looking border. I read a little more, and understood, that I need to set the so-called "extended window style". The value must be WS_EX_CLIENTEDGE. I replaced WS_BORDER with this:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_EX_CLIENTEDGE,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

This had no effect. It was really stupid decision, as I figured out later. I continued to read. I switched to Google and forums.

I learned, that extended window style can be set only in special parameter by using CerateEx(...), not usual Create(...). So I wrote:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"WCLASS_EDIT1",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

This obviously won't work, because I didn't register WCLASS_EDIT1 windows class. I tried to register it, then I tried NULL and then I tried the standard "edit" class (I must begin with it =( ):

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

The result was the same: window creation failed. GetLastError returned 0x00000579 (0x0579, 0x579, 1041): "Invalid menu handle". Why? I have no menu in this dialog!

Then I thought that control's parent window is not my dialog and tried to set the parent window explicitly (using SetParent(...)). But I was wrong, the parent window was correct.

I gave up with CreateEx, and returned to usual Create, because I learned the great function ModifyStyleEx. This function modifies extended style on-the-fly! I decided to use it. So I wrote:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);
dlg_data[ix].m_edtField->ModifyStyleEx(0,WS_EX_CLIENTEDGE);

This compiled and ran normally, but the control has no border. Why? I explicitly set the border. I continued to read.

I learned, that border style cannot be modified with ModifyStyleEx. It can be set only on creation. The reason is unknown.

So I MUST use CreateEx(...). But windows creation fails. Why? I read forums a little more and thank godness! I found the reason. Only in one place this was described.

CreateEx need explicitly set window style WS_CHILD. The reason is unknown.
Notice, that usual Create can be successfully called without WS_CHILD. So, the final version was:

dlg_data[ix].m_edtField->CreateEx(
WS_EX_CLIENTEDGE,
"edit",
"PREFIX_EDIT1",
(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_CHILD,
rRect,
this,
dlg_data[ix].m_nedtFieldID);

This works:

RU:

(читать на русском)

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

Вы будете смеяться, но мне приходится использовать MFC (2011 год на дворе!). Задача была в том, чтобы создать на лету несколько CEdit. Я написал:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

где:
ix -- переменная цикла;
dlg_data[ix] -- структура с данными динамических контролов;
dlg_data[ix].m_edtField -- указатель на CEdit;
bVis -- флаг видимости CEdit, если истина, создаём видимым;
rRect -- расчитанные координаты контрола, запиханные в CRect;
this -- указатель на переменную-класс, класс наследник CWnd;
dlg_data[ix].m_nedtFieldID -- ID контрола, сгенерированный специально для этого.

Как я и думал, эта строчка вывела CEdit, но без рамки, вот так:

Я почитал документацию и решил использовать WS_BORDER, получилось вот что:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_BORDER,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Рамка появилась, но была плоской, вот такой:

Я же хотел обычную трёхмерную. Я почитал ещё немного и понял, что мне нужно установить так называемый "расширенный стиль окна" ("extended window style"). Установить его надо в WS_EX_CLIENTEDGE. Я заменил WS_BORDER:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_EX_CLIENTEDGE,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Ничего не изменилось. Делать так было глупо, как я понял позднее. Я продолжил чтение, переключившись с документаци на гугл и форумы.

Я узнал, что расширенный стиль окна может быть установлен, но не в том же параметре, где обычный стиль, а в другом, специальном и использовать надо CerateEx(...), а не обычный Create(...). Так что я написал:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"WCLASS_EDIT1",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Очевидно, это не заработало, ведь я не зарегистрировал класс окна WCLASS_EDIT1. Я попробовал его зарегистрировать, потом написать NULL, а потом я попробовал стандартный класс окна "edit" (с этого надо было начинать =( ):

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Результат был тот же: окно не создавалось. GetLastError вовзращал 0x00000579 (0x0579, 0x579, 1041): "Неверный дескриптор меню" ("Invalid menu handle"). С какого хрена? У меня в диалоге нет меню!

Потом я подумал, может быть родительское окно у контрола установлено неверно? Я попробовал назначить его явно с помощью SetParent(...). Я ошибался, родительское окно было установлено верно.

Я плюнул на CreateEx, и вернулся к обычному Create, ведь я узнал о замечательной функции ModifyStyleEx. Она позволяет менять расширенный стиль прямо на лету! Я решил использовать её. Я написал:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);
dlg_data[ix].m_edtField->ModifyStyleEx(0,WS_EX_CLIENTEDGE);

Это компилировалось и работало без ошибок, однако у контрола рамки по-прежнему не было. Почему? Я же явно указал стиль рамки. Я продолжил чтение.

Я выяснил, что стиль рамки по неизвестной причине не может быть изменён на лету с помощью ModifyStyleEx. Его можно установить только при создании с помощью CreateEx.

Таким образом, мне ПРИДЁТСЯ использовать CreateEx(...). Но создать окно не удаётся. Почему? Я ещё немного почитал форумы и слава богам выяснил причину. Правда написано это было только в одном месте.

CreateEx трубует явного указания обычного стиля как WS_CHILD. Почему -- неизвестно.
Заметьте, что обычный Create может быть успешно вызван и без WS_CHILD. Итак, финальная версия:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_CHILD,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Это работает:

---

Untitled [010]

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

---

Квадратная дата

В этот день джва года назад я получил водительское удостоверение.
Да, я получил его в пятницу, 13-е.

---

Untitled [009]

Вытаскивая звуковой усилитель из розетки, поймал себя на мысли, что я его не извлёк перед этим безопасно (Safely Remove Hardware).

---

Робот-зазнайка

Honda обновила своего знаменитого робота: ASIMO научился открывать пиво...

---

Класс-самоубийца и Павлик Морозов

Есть такой антипаттерн -- Паблик Морозов.
Заключается он в том, что вокруг класса с закрытыми членами делается обёртка-наследник, выдающая данные закрытых членов. Юмор в данном случае понятен -- согласно известной истории, Павлик Морозов заложил своего отца. И класс-наследник закладывает своего наследодателя.

А сегодня я имел честь видеть класс-самоубийцу (все названия изменены):

class jisatsu
	{
		private:
			float* m_fData; // тут будет храниться массив с данными
		//...
		public:
			float* GetData() { return m_fData; }
		//...
	};

Автор: А.

---

Негр и They need more money

Перевод английских реплик появится позже.

Ехал я домой. А мне для того чтобы домой попасть подходят две станции. Ехать надо было с пересадкой и я выбрал некоторую из них. Выхожу на станции (время -- 22:30), чувствую, меня кто-то хватает за рукав и что-то говорит.
Я думаю... кто там... МИЛИЦИЯ?!
Оборачиваюсь -- там стоит НЕГР.

(читать дальше)

Негр: Do you speak Enlish?
Я туплю. Он повторяет вопрос.
В голове вертится только "хай, сукоси".
На третий раз я наконец ответил.
Я: Yes.
Он: (неразборчиво)
Я: Repeat please.
Он: (неразборчиво)
Я: I don't understand.
На третий раз он сказал понятно.
Он: What is the name of this metro station?
Я туплю.
Он: %STATION_NAME%, right?
Я: Yes!
Он: I need help. The police got my friend.
Я:
.
.
.

Я: I Understand.
Он: Sit down please.
Я присаживаюсь на лавочку, он рядом.
Он: The police got my friend. This is the immigration police. They need money. I have money, but the need more. I don't know what to do.
Мимо проезжает состав. Я начинаю себя чувствовать персонажем Макс Пейн.
Я: Where did they got him?
Он: Yaroslavskoye (далее неразборчиво)
Я: Yaroslavskoye WHAT?
Он: Yaroslavskoye shosse (Что он тут-то делал? Это довольно далеко отсюда).
Я: What they say?
Он: They need money. I have money, but they need more.
Я: (господи, у меня 7к с собой!) I... have no money.
Он: But you have card.
Я: What?
Он: Card!
Я: (да он проницательный... у меня их даже две) I have no card.
Он: No way! (разочарованно)
Он: Do you live far from here?
Я -- (долгая пауза, а ведь совсем рядом!) Yes, far... (долгая пауза)
Он: I don't know what to do.
Я: Excuse me, I can't help.

И огородами, огородами.

Это был не конец. Дальше был подземный переход. Там играли на гитаре. Один играл. Вокруг него стояли ещё двое и третья с шляпой. Загораживают проход, трясут шляпой. Я мотаю головой обхожу и иду дальше.

И это ещё не всё. Стою на пешеходном переходе, жду зелёный. Тут останавливается тонированная иномарка и у неё начинает открываться окно пассажира переднего ряда. Я думаю ДА НЕ НУ НАХРЕН, ЩАС СО МНОЙ ГОВОРИТЬ БУДУТ. Быстренько её обхожу и пытаюсь перейти дорогу. Но там едет другая машина, кидаться не могу. Правда эта передумала и поехала дальше. Дальше я уже до дому почти бежал.

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

По поводу этого инцидента хотел бы прокомментировать следующее:
1. Как хорошо, что я сегодня зарплату не стал получать! (пистолета не было, решил в другой день)
2. Позже я подумал, что надо было его отправить в посольство, либо сдать в милициюполицию. Но я не знал, как будет "посольство" (.
3. Я подумал, как жаль, что я не бандит. А то бы ему сказал "а пошли ко мне домой, за деньгами", повязал бы там его, забрал бы его деньги...
4. Даже если это был развод (а это, скорее всего, он и был), то очень эстетичный. Спасибо тебе, негр!
5. Слово "посольство" гораздо важнее, чем я думал.
6. У меня есть принцип -- НЕ ПОДАВАТЬ. В общем случае это значит -- "не одалживать и не дарить денег незнакомцам, а знакомцам -- только с возвратом".

---

О стратегии именования абстрактных об'ектов

Описаны методики и приёмы именования абстрактных объектов на примере файлов.

Когда нам приходится работать с большим числом более-менее однородных об'ектов, неизбежно возникает необходимость как-то ориентироваться во всём этом барахле. На помощь приходит именование. Это очень древняя система. В современном обществе имя есть практически у каждого человека (в отличие от фамилии -- у членов японской императорской семьи, например, фамилии нет, только имя). Тут следует сделать замечание, что есть две совершенно разные категории именования -- именование различных об'ектов и именование различных версий одного об'екта. Поскольку то, о чём я напишу ниже, работает для любых типов об'ектов, без ограничения общности будем считать, что речь идёт про файлы. С одной стороны, они являются более-менее однородными об'ектами (файлами (= ), с другой стороны, их содержимое может быть совершенно различным как по структуре (форматы), так и по смыслу, в случае одинаковой структуры. А ещё у всех файлов есть имя. Также речь пойдёт только о ситуациях, когда именовать вы имеете право. Если имена даны свыше (или другими существами), вы ничего с этим сделать не можете, это неинтересно.
Ниже я опишу основные способы именования, которыми я или не я пользовался или пользуюсь по сей день.

(читать далее)

Первое: именование различных об'ектов

Итак, различные об'екты должны именоваться различно -- К.О. Если в жизни различные об'екты могут иметь два полностью одинаковых имени, то в случае с файлами это невозможно. Даже если у вас есть возможность так сделать (названия заметок в KeepNote, например), лучше от этого воздержаться. Причина проста и очевидна -- об'екты с одинаковым именем можно различить только путём непосредственной проверки содержимого, что означает необходимость дополнительных проверок (потеря времени), причём неопределённого (с какой попытки вы угадаете?).
Если необходимо всё-таки именовать одинаково, лучше ввести какой-либо различитель -- постфикс к имени, вид иконки или что-либо ещё. Однако, введение постфикса к имени автоматом делает имена различными. Пример различителей из реальной жизни -- именование королей ("Людовик XVI" -- отделение имени от различителя логическое, так как и "Людовик" и "шестнадцать" являются отдельными словами и по другому разбить полное имя нельзя, про разделитель см. ниже).

Как сделать правильный различитель? Он должен легко отделяться от основного имени и предоставлять широкие возможности.
Про лёгкое отделение -- тут всё понятно. Нужен символ-разделитель. Или несколько. Например:
Черчение-1.wav -- тут всё понятно, разделитель -- дефис;
Черчение[1].wav -- тут тоже всё понятно, разделитель -- квадратные скобки.
Ещё возможно разделение по признаку принадлежности к другой категории символов, например:
черчениеА.wav -- заглавные против строчных;
2черчение.wav -- цифры против букв.
Для всех об'ектов разделитель должен быть одним и тем же. Почему? При сортировке (о сортировке -- ниже) всё будет по порядку.
Это всё -- если различитель расположен в имени файла. Если различитель где-то ещё, разделитель возникает естественным образом. Лучше, чтобы различитель был в имени -- он будет виден при любом отображении списка файлов (на самом деле, не любом; можно заставить Проводник отображать только "ноготки", без имён). Также это поможет при сортировке.

Отступление: сортировка
Тут следует сделать замечание про сортировку. Любые именованные об'екты принято сортировать, для быстрого поиска. Сортировка производится, как правило, в алфавитном порядке. В случае файлов на компьютере, порядок определяется кодировкой, однако принцип алфавитности обычно соблюдается. Единственное, чем плох алфавитный порядок -- расположение букв в таком порядке не об'ясняется логически, только исторически. Другими словами, алфавит придётся выучить. "Определяется кодировкой" означает, что цифры и спец. знаки тоже включены, цифры идут ДО букв, русские буквы идут после латинских, строчные после заглавных. Эти правила общие для почти всех кодировок.

Про широкие возможности -- тут сложнее. Надо ответить на следующие вопросы --
1) Где расположить различитель?
2) Какие значения может принимать различитель?
3) Как оформить различитель?

Где расположить различитель?

Я не знаю, может быть вы сможете придумать причину, чтобы располагать его в середине имени, но я придумать такую не могу.
Различитель имеет смысл располагать либо в начале имени файла, либо в конце (про расширение речи нет). Как правило, в конце. В начале можно располагать в том случае, если различители с одинаковыми значениями могут служить для классификации об'ектов с разными именами, но одинаковыми различителями. Пример:
[красный]куб
[красный]шар
[красный]додэкаэдр
[зелёный]куб
[зелёный]шар
[жёлтый]куб
При сортировке появятся сначала жёлтые об'екты, потом зелёные, потом красные. Это может быть полезно.
Другой случай, когда различитель является надкатегорией над об'ектами. Тогда тоже можно располагать различитель в начале имени, однако в таком случае лучше все об'екты переместить в эту самую надкатегорию (создать для них папку и положить их туда безо всяких различителей).

Однако чаще проще и лучше размещать различитель в конце:
Летит-1.doc
Летит-2.doc
Летит-3.doc

Какие значения может принимать различитель?

Это тяжёлый вопрос. Если есть у об'ектов недублирующиеся характеристики, лучше, конечно, использовать их. Когда круг об'ектов известен заранее, можно найти такой признак, например, цвет. Когда круг неизвестен, вряд ли удастся.
Другой распространённый способ -- различать по номеру.

Отступление: нумерация.
Нумерация -- частный случай именования, когда вместо символов имени используются только цифры.
Нумерация может быть сквозная или категоризированная. И ту и другую можно наблюдать в нумерации помещений в школах, институтах и других учреждениях.
При сквозной нумерации числа, характеризующие об'екты (помещения), идут подряд.
При категоризированной, некоторые условные признаки позволяют узнать по номеру что-то ещё, что может облегчить поиск, например. В случае с помещениями, как правило, первая цифра означает номер этажа. Например -- 209 -- 9-я комната на 2-м этаже. И можно не обходить все кабинеты, а сразу на 2-й этаж. Если этажей 3 и более, это существенно сокращает время поиска.
Другой пример категоризированной нумерации -- нумерация домов на улице. Как правило (но не всегда!) с одной стороны улицы только чётные дома, с другой только нечётные. Каких-то домов может не быть.

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

Как оформить различитель?

Тут остаётся рассмотреть два небольших вопроса.
Первое -- каким выбрать разделитель? Правильный ответ -- любой (даже пустой, пример ниже), но он должен быть одинаковым. Если у одних файлов "_", а у других "-" -- это приведёт к тому, что при сортировке сначала будут выводиться одни ("-"), потом другие ("_"). Желательно, конечно, чтобы он был легко отличим (т.е., например, если в основном имени используются буквы, он не должен быть буквой).
Второе -- какова должна быть длина различителя? Правильный ответ -- лучше, чтобы она была одинаковой и не слишком большой. Не слишком большой -- для простоты восприятия, а желательность одинаковой длины опять связана с поиском и сортировкой. Если не дописывать, например, ведущий нолик к числам, сортировка по имени даст следующий результат:
имя1
имя10
имя11
...
имя19
имя2
имя20

Поняли, да? Надо-то было:
имя01
имя02
...
имя09
имя10
имя11
...

Сколько нулей писать, зависит от числа об'ектов, но надо брать "на вырост". После появления нового знака (такое бывает), ко всем старым об'ектам надо дописать ещё один нолик. Как можно быстрее.

Различные об'екты следует именовать различно, с этим разобрались, но как?
Тут всё зависит от того, что вы называете. Желательно, чтобы имя файла отражало его суть (: лучше не сохранять порнорассказы в файл доклад.doc, потом можно запутаться (=.
Название должно быть информативным, как правило, это значит, что по названию должно быть понятно:
1) Каков тип об'екта? (сервер? кинофильм?) -- эту функцию успешно выполняет т.н. "расширение" файла.
2) Что в этом об'екте? -- либо это название, данное логическому содержимому до нас (например, название фильма), либо категория, к которой его можно отнести (например, "Отчёт").
3) Какими характерными признаками оно обладает? -- для отчётов это либо тема отчёта, либо автор, либо и то и другое (например: отчёт сидоров.doc), для других файлов может либо отсутствовать, либо показывать какие-то характеристики (см. 2-й пример хорошего имени).
Примеры хороших имён:
Отчёт по экологии 2011 сидоров.doc
[Leopard-Raws] Kuragehime - 07 RAW (CX 1280x720 x264 AAC).mp4
Пример плохих имени:
Какая-то хрень.doc
Отчёт.doc
Последнее допустимо, если название папки даёт дополнительные сведения.



Второе: именование версий одного об'екта

Итак, вы не хотите или не можете использовать систему контроля версий, а ваши файлы всё-таки имеют много версий. Например, у вас есть листинги вашей программы в нескольких файлах.

Отступление: много файлов в об'екте
Также, если ваши логические об'екты состоят из нескольких файлов, для хранения версий рекомендую делать тарбол (для виндузятников: архив, для продвинутых виндузятников: архив без сжатия, если разные версии приходится использовать часто) и именовать уже его. Или, что проще, организовывать для каждого об'екта отдельную папку. Но это хуже, т.к. файлов остаётся много, хотя логически об'ект один. Держите в папке только текущую версию, остальные в архивах.

Ключ к лёгкой ориентации в ваших файлах -- в грамотном именовании, опять-таки.
Коренного отличия между именованием разных версий одного об'екта и разных об'ектов с одним именем для машины нет. Для человека разница в том, что версии могут по внешнему виду слабо отличаться и поиск отличий может занять длительное время.
Тут работает другое правило -- одинаковые об'екты должны называться одинаково -- К.О. В счёт не идёт различитель, разумеется.

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

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

Дата
Да-да, именно дата (или дата/время) изменения -- главный различитель разных версий. Как его записать? Тут срабатывает правило про надкатегорию, по аналогии с разлечителем перед основным именем. Сначала пишут большие промежутки времени, потом меньшие. Год-месяц-день, как в Японии. Пример:
20111108154744
11 нобяря 2011 года, 15:47 и 44 секунды.
Можно и с внутренними разделителями:
2011_11_08_15_47_44
Можно и с двоеточием и слэшем, но понадобится извратиться: придётся использовать ШИРОКИЕ двоеточия и слэши. В отличие от обычных, они разрешены к использованию в именах файлов. Кто не знает, что такое широкие, ищет в гугле.

Нумерация внутри одной даты
Тут работает обычное правило с различителями. Например ДАТА-01, ДАТА-02. Если версии не бывают чаще раза в час, можно просто подключить два разряда времени.

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

Полный пример:

super_program_2011_11_08-01-VASYA.rar

Вместо даты и кода сегодняшней версии, разумеется, можно использовать сквозной номер:
super_program_0167-VASYA.rar

Десерт: тэгирование
Эта система нашла широкое применение. Заключается она во включение в имя (или не в имя) файла дополнительных сведений о возможных категоризациях об'екта. О тэгах шары можно долго петь песню, но об этом в другой раз. Применяется тэгирование и для разных об'ектов и для версий одного об'екта и для всего чего угодно. Разделяются тэги квадратными скобками, как правило.
Главное требование, которое я советую соблюдать -- вписывать тэги в имя файла по алфавиту, чтобы при поиске можно было сразу указывать маску и не думать над порядком. Или надо установить жёсткий порядок обязательных тегов.

Пример:
Есть файлы версий одной программы, обеспечивающей работу некоего научного (или ненаучного) прибора. Называется программа, допустим, KILL_THEM_ALL. Программа бывает двух модификаций -- профессиональная и любительская. Есть три разновидности прибора -- A, B, C, для каждого используются немножко другие функции. Программа бывает в виде бета-версии и в виде финальной версии. И есть специальные признаки -- для внутреннего пользования, нерабочая, версия для слепых.
Классификации:
Классификация 1, по возможностям: профессиональная [PRO], любительская [AMA] (amateur).
Классификация 2, по разновидности прибора: A, B, C, соответственно, [A], [B], [C].
Классификация 3, по завершённости: beta -- [beta], final -- [final].
Это будут обязательные тэги.
Признаки:
Внутреннего пользования: [IN] (internal).
Нерабочая: [NW] (not-work).
Версия для слепых: [BL] (blind).
Это будут необязательные теги.

Обязательные теги в указанном порядке пишем, необазательные в алфавитном.
[PRO][B][FINAL]KILL_THEM_ALL-1.2.3[BL][NW]

Если мы хотим найти все версии для прибора B, маска поиска будет *[B]*, если беты для профессионалов -- [PRO]*[BETA]* (располагаем в оговоренном порядке).
Если хотим найти версию для слепых для внутреннего пользования -- маска будет *[BL]*[IN]* (тэги в алфавитном порядке).
Линуксоидам проще, у них регулярные выражения.

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

Пожалуйста, ознакомьтесь с комментариями!

---

Titled

Поздравляю всех с Днём Великой Октябрьской Социалистической Революции!

---

Boku wa Tomodachi ga Sukunai 01-05

Только бы 26, только бы 26...

>>

---

Untitled [008]

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

---

О поиске, часть 1

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

Тяжело искать чёрную кошку в тёмной комнате, особенно если её там нет.
>>

---

XOR-связный список

Описано создание XOR-связного списка и его принципы работы. Описаны принципы работы динамических структур данных -- списков и деревьев (на примере двоичных деревьев).

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

(читать дальше)

1 Введение
1.1 Что такое динамические структуры данных?
При работе с самыми различным данными программисты часто сталкиваются с тем, что на момент компиляции программы неизвестно, с каким объёмом данных предстоит работать. Придётся обработать нам всего один байт или пять мегабайт? Нет ответа.
Хорошо, если данные хранятся в файле, их можно считывать кусками и нам пофиг, какого файл размера, лишь бы стандартные функции с ним работали. Иногда же приходится держать данные прямо в памяти. Однако многие компилируемые языки программирования не поддерживают возможность "на лету" изменять размеры массивов и подобных структур. Тут на помощь приходит динамическая память -- операционная система выдаёт куски памяти по запросу. Это является хорошим (и стандартным) решением, когда в определённый момент выполнения программы мы узнаём, сколько памяти нам нужно, и в дальнейшем этот объём не меняется.
Так тоже бывает не всегда. Зачастую объём хранимых данных меняется прямо во время выполнения программы. Что же делать? Один из способов -- выделить новую память, переписать туда новую версию данных, удалить старую память. Пока данных мало, всё хорошо, но как только их становится много, операции копирования начинают занимать слишком много времени.
Для работы с изменяющимся объёмами данных в памяти были придуманы так называемые "динамические структуры данных", позволяющие перемещаться по данным любого объёма, а также динамически менять общий объём данных не занимая полным копированием. Как этого можно достичь?
Допустим, все данные разбиты на некоторые логические куски -- "элементы". Они могут быть разного размера, однако по смыслу они должны быть одним и тем же. Например, целые числа, строки, картинки. Хороший и достаточно общий пример элемента -- экземпляр какого-либо класса.
Если мы для каждого элемента будем выделять память и складывать его туда, а при удалении освобождать память, которую он занимает, задача хранения данных будет решена (:, но непонятно, как по этим данным перемещаться. Можно, конечно, хранить указатели на каждый элемент в месте использования, ибо копировать-выделять массив указателей быстрее, чем совокупность всех элементов, но хотелось бы от этого копирования-выделения избавиться. Ключ к перемещению без полного копирования прост -- необходимо в каждом элементе хранить ссылки на ещё какие-то элементы (или на пустое место, если связи нет).
Типичные динамические структуры данных -- списки и деревья.
1.2 Что такое списки и деревья?
Поскольку основная часть посвящена спискам, начнём с деревьев, чтобы после списков перейти к основной теме.
1.2.1 Дерево

(показать про дерево; это оффтопик фактически, так что скрываю)

Оно называется дерево и имеет с ним некоторую аналогию. Дерево представляет собой ациклический граф. Подробнее об этом можно почитать в вики. Понятно, что дерево может быть n-ричным, но применительно к динамическим структурам данных будем рассматривать только двоичное дерево, как имеющее наибольшую практическую ценность. Не будем углубляться в математику, посмотрим просто как это работает. Забегая вперёд, скажу, что деревья очень хороши для поиска.

Обязательными полями для элемента двоичного дерева являются две ссылки на нижележащие элементы (будем называть их "левый" и "правый", хотя как называния, так и способ применения (см. ниже) не принципиальны, главное применять единообразно), а также так называемый "счётчик", на случай, если у нас будут несколько одинаковых элементов. Также необходимо придумать метод сравнения элементов, который должен отвечать следующим требованиям:
1. Если взять два произвольных элемента, один из них будет либо больше другого, либо меньше, либо равен.
2. Если два элемента по этому методу равны, то элементы являются полностью эквивалентными друг другу.
Другими словами, сравнение двух элементов "по размеру" не подходит, так как могут быть несколько элементов не эквивалентных друг другу, но имеющих одинаковый размер. Гораздо лучше сравнение по какому-либо хэшу (например, md5), но у элементов и хэши могут совпасть! (хотя это уже вряд ли). Тут уже надо кропотливо думать. Сравнивать числа и строки, правда, очень просто.
Признак, по которому мы сравниваем два элемента иногда называют "ключом" элемента.
Есть другой метод. Можно ввести только операцию "меньше", тогда элементы с повторным ключом будут неотличимы от элементов, которые больше. Это необходимо, если возможны различные элементы с одинаковыми ключами. Если такое невозможно (т.к. ключи всегда различны для различных элементов), то у нас будет потенциальное дублирование данных.

1.2.1.1 Заполнение дерева
Итак, в месте использования мы храним ровно один указатель на элемент, называемый "корнем дерева". Этот элемент либо есть, либо его нет. Если его нет, дерево пустое. Если мы добавляем элемент в пустое дерево, он становится корнем. Хотим добавить ещё один элемент и тут понимаем, что непонятно, как это следует сделать. Поскольку дерево двоичное, каждый элемент имеет по ДВА указателя на следующие элементы. Куда пихать? А если сделать так? Если новый элемент БОЛЬШЕ корневого, будем сохранять указатель на него СПРАВА (новый > старого, галочка смотрит вправо), а если МЕНЬШЕ -- СЛЕВА, а? Если место с этой стороны уже занято, перейдём по указателю и повторим процедуру с элементом ниже по уровню, пока не найдём пустое место. Если наткнёмся на элемент, который равен текущему, то останется только увеличить счётчик вхождений такого элемента на единицу.
Приведу пример заполнения.

Пример 1.
Итак, есть числа 7, 4, 9, 5, 2, 4, 3.

1. 7 -- идёт в корень.
Уровень 0.          7
2. 4<7. Кладём слева.
Уровень 0.          7
                   /
Уровень 1.        4
3. 9>7. Кладём справа.
Уровень 0.          7
                   / \
Уровень 1.        4   9
4. 5<7, но то место уже занято! Спускаемся к 4. 5>4 -- кладём справа от 4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                  \
Уровень 2.         5
5. 2<7, 2<4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                / \
Уровень 2.     2   5
5. 4<7, 4=4. Увеличиваем ссылку
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
6. 3<7, 3<4, 3>2.
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
                \
Уровень 3.       3

Как заполнять дерево, вроде понятно. А как удалять?
1.2.1.2 Удаление элемента из дерева
а) если счётчик больше 1, просто уменьшаем его
б) Если мы хотим удалить элемент, у которого нет ссылок на более нижние уровни, всё понятно -- данные удаляются, ссылка, которая ссылалась на него, устанавливается в значение "пусто".
в) Если только с одной стороны есть более нижние уровни, элемент удаляем, единственный из двух возможных более нижних элементов, прицепляем вместо удалённого, чтобы верхний ссылался на него.
г) Если есть оба более нижних элемента, всё становится печально. Надо найти им новый родительский элемент, при этом следует учесть, что нельзя нарушить порядка больше-меньше, иначе дерево потеряет смысл (о смысле см. далее). Кто же подойдёт на эту роль? Элемент должен быть меньше любого элемента справа, но больше любого элемента слева! Найдём самый левый элемент правого поддерева. Это -- его наименьший элемент. Если его удалить по вышеописанному алгоритму (тут понятно, что один из пунктов "б","в" сработает, ибо "г" бы означал, что это не самый левый элемент, про пункт "а" см. далее)), спрятав данные у себя, то он станет меньше любого элемента в правом поддерева. А то, что он больше любого элемента левого поддерева и так понятно, ведь иначе бы он в нём и находился! Следует учесть, что забирать данные надо вместе со счётчиком а удалять надо все экземпляры (поэтому удаление по пункту "а" никогда не будет), ибо если перенести только один экземлпяр, у нас будет несколько равных элементов в разных местах, этого быть не должно. Данные удаляемого элемента удаляем, а спрятанные пишем вместо них. Вуаля.
Пример 2.

Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7
Хотим удалить корень дерева.
1. Придётся работать по пункту "г". В правом поддереве самый левый элемент это 6, копируем к себе (6) и удаляем (работает пункт "в").
Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
2. Удаляем данные корня, вместо них пишем то, что было в загашнике.
Уровень 0.         6
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
Как видно, порядок больше-меньше не нарушился.

Очевидно, что в случае "г" можно переносить на место удаляемого не только самый левый элемент из правого поддерева, но и самый правый элемент из левого поддерева.
1.2.1.3 Зачем всё это нужно. Поиск и обход дерева
Так как мы уже при заполнении определили, кто больше, а кто меньше, поиск превращается в тривиальную задачу, при которой, в добавок, не нужно осматривать все элементы.

Пример 3.
Допустим, в дереве из предыдущего примера (до удаления) хотим найти 7.

Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7

1. 7>5, перешли вправо.
2. 7<8, перешли влево.
3. 7>6, перешли вправо. Вот оно! Конец.
Разумеется, в нашем примере такой поиск бессмысленен и беспощаден, поскольку наши данные и есть ключ. Если же к нашему числу прилеплено ещё пять мегабайт фигни, смысл очень большой:
1. Мы сравниваем данные только по ключам, а не целиком.
2. Мы просматриваем только часть данных (3 проверки при 6 элементах).
Если надо пробежать по всем элементам, делается это следующим образом.
1. Сначала обрабатываем всё, что слева, потом себя, потом всё, что справа.
2. Спустившись на уровень ниже, повторяем пункт 1.
Понятно, что мы имеем дело с рекурсией и понятно, что мы обработаем данные в порядке возрастания. Аналогично можно придумать обработку и в порядке убывания.
Менее кустарно об этом можно прочитать тут.

К достоинствам дерева можно отнести авто-упорядочивание и быстрый поиск.
К недостаткам относится наличие рекурсии (вы заметили? (: ), что ведёт к неконтролируемому использованию стека.
К потенциальным недостаткам можно отнести следующую ситуацию. При добавлении уже упорядоченных данных, они будут добавляться всё время с одной и той же стороны дерева, превращая её В СПИСОК (см. далее)! Это называется "разбалансировка", лечится "балансировкой". Короче, надо следить, чтобы дерево было сбалансированным, т.е. слева и справа примерно одинаковое число элементов.

1.2.2 Списки
Список -- это проще чем дерево. (: В списке все элементы хранятся последовательно, при этом в каждом есть одна или две ссылки на другие элементы.
По направленности списки делятся на:
-- однонаправленные;
-- двунаправленные.
По цикличности списки делятся на
-- циклические (циклические);
-- ациклические (= (линейные).
В однонаправленных ссылка одна и перемещаться можно только вперёд. Как акула. В месте использования надо хранить указатель на один из элементов, желательно первый (а если список ациклический, то обязательно на первый!).
В двунаправленных ссылки две -- на предыдущий и на следующий элемент.
В циклических списках последний элемент ссылается на первый, в ациклических у последнего в ссылке на следующий стоит "пусто" и у первого в ссылке на предыдущий (если она есть) стоит "пусто". Необходимость использования того или иного типа списка определяется формулировкой задачи.
Добавление элемента в список (в конец или в середину) заключается в следующем:
1. Указатель "следующий" старого-предыдущего (если он есть) элемента начинает указывать на новый;
2. Указатель "предыдущий" (если он есть) старого-следующего элемента (если он есть) начинает указывать на новый;
3. Указатели "следующий" и "предыдущий" (если они есть) нового начинают указывать на старый-следующий и старый-предыдущий соответственно.
Если следующего/предыдущего элемента нет, в соответствующие указатели нового элемента устанавливается "пусто".
Удаление происходит следующим образом.
1. Указатель "следующий" предыдущего элемента начинают указывать на следующий после удаляемого элемент (если он есть; иначе -- "пусто");
2. Указатель "предыдущий" (если он есть) следующего элемента (если он есть) начинает указывать на предыдущий перед удаляемым элемент (если он есть; иначе -- "пусто");
3. Удаляемый элемент удаляется и идёт лесом.
Перемещение по списку превращается в детскую забаву -- знай себе, переходи по указателю.
А поиск только последовательным просмотром. Такие дела.
2 XOR-связный список
2.1 Что такое XOR и с чем его едят
С давних времён в программировании и дискретной математике применяются логические (в том числе побитовые) операции. XOR ("исключающее или", "сложение по модулю два", "строгая дизъюнкция" -- одна из них, причём она обладает некоторыми интересным свойствами. Таблица истинности для неё выглядит следующим образом:

+-------+-------+-------+
| x1\x2 |Истина |Ложь   |
+-------+-------+-------+
|Истина |Ложь   |Истина |
+-------+-------+-------+
|Ложь   |Истина |Ложь   |
+-------+-------+-------+

Другими словами, для двух логических значений x1 и x2 на выходе "истина", если истенен только один из операндов. Если оба истинны или оба ложны, получается ложь.
2.2 Что такое побитовая операция
Операция с двумя операндами называется побитовой, если она проводится над соответствующими битами обоих операндов и записывается в бит с тем же самым номером на выход, при этом соседние биты не затрагиваются.
Пример 4.
Вычислим побитовое XOR двух двоичных чисел (8-битных байт):

01110010
11010001
-------
10100011

2.3 Области применения XOR
Ну, во первых, это несложное шифрование. Пусть есть сообщение A и ключ шифрования K такой же длины (в битах). Проведём XOR:
A XOR K =A1.
Очевидно, что если ключ ненулевой, то на выходе будет не то же, что на входе, т.е. данные изменились. Как их достать обратно? Проведём XOR тем же ключом ещё раз!
((A XOR K) XOR K) = A XOR (K XOR K) = A XOR 0 = A.
Получили исходное значение.
K XOR K = 0, поскольку одинаковые биты первого и второго операнда зануляются (таблица истинности, см. 2.1), а они все одинаковые, значит на выходе 0.
A XOR 0 = A, поскольку XOR и истины и лжи с ложью равен исходному значению по таблице истинности, а второе значение состоит целиком и лжи (нолики).
Пример 5.

01110010 -- сообщение
11010001 -- ключ
-------
10100011 -- зашифрованное сообщение
----------------------------------------------
10100011 -- зашифрованное сообщение
11010001 -- ключ
--------
01110010 -- исходное сообщение

Вторая область применения -- это зануление. Дело в том, что операция переноса данных в процессоре гораздо медленнее, чем логическая. Сделать же регистр равным нулю -- довольно распространённая задача. Если решать в лоб, то надо делать так:

MOV AX, 0

Если подумать, то быстрее делать так:

XOR AX, AX

Что исключающее или числа самого с собой равно нулю, мы выяснили выше.
Некоторые процессоры, однако, имеют встроенную команду зануления регистра.
Может быть можно ещё что-нибудь интересное придумать с XOR?
2.4 Применимость XOR к двунаправленным спискам.
Давайте возьмём случай с шифрованием, и рассмотрим один интересный момент:
если сделать XOR между исходным сообщением и зашифрованным, получается ключ! Смотрите:
A XOR A1= A XOR (A XOR K)= (A XOR A) XOR K = 0 XOR K = K.
Теперь давайте вместо A, A1, K писать C1, C2, U (соответственно). Получим:
C1 XOR C2 = U
U XOR C1 = C2
U XOR C2 = C1
Что же получается-то? Если у нас есть два абстрактных числа, то зная их XOR и одно из чисел, можно найти второе.

Если у нас есть двусвязный список, в нём хранятся адреса следующего и предыдущего элементов. Если хранить их XOR, то зная адрес следующего элемента, можно вычислить адрес предыдущего и наоборот. В дальнейшем XOR-псевдоадрес будем называть "ёж".

Итак, пусть у нас есть пять элементов, при этом их адреса будем обозначать A_i, а ежи -- U_i.
Жирным обозначено, когда связь переходит через конец списка, палочки обозначают XOR чего и чего в еже. Кружочки -- сами элементы.

     A1   A2   A3   A4   A5
   \ O / \O / \O / \O / \O /
     U1   U2   U3   U4   U5

Во избежание проблем будем считать список циклически. Тогда:
U1 = A5 XOR A2
U2 = A1 XOR A3
U3 = A2 XOR A4
U4 = A3 XOR A5
U5 = A4 XOR A1

Пусть нам известны адреса 3 и 4 элемента. Мы хотим узнать, что было до и после них.
До: берём ёж третьего элемента и делаем исключающее или с адресом четвёртого:
U3 XOR A4 = (A3 XOR A4) XOR A4 = A3 XOR (A4 XOR A4) = A3.
После: берём ёж четвёртого элемента и делаем исключающее или с адресом третьего:
U4 XOR A3 = (A3 XOR A5) XOR A3 = A5 XOR (A3 XOR A3) = A5.
Оно работает!
А как добавить элемент?
Хотим добавить элемент X после A2.
Ёж нового элемента -- это просто исключающее или его новых соседей. А вот их ежи придётся пересчитать:
UX= A2 XOR A3
U2'=A1 XOR AX
U3'=AX XOR A4

     A1   A2   AX   A3   A4   A5
   \ O / \O / \O / \O / \O / \O /
     U1   U2'  UX   U3'  U4   U5

Ещё тонкий момент -- удаление элемента. Удалим A2. Необходимо пересчитать ежи.
U1'=U5 XOR AX
UX'= U1 XOR A3

    A1   AX   A3   A4   A5
  \ O / \O / \O / \O / \O /
    U1'  UX'  U3'  U4   U5

Разумеется в программе всё чуть сложнее.

2.5 Ежиная арифметика
Адрес XOR Адрес = Ёж
Ёж XOR Адрес = Адрес
Адрес XOR Ёж = Адрес
Ёж XOR Ёж =? Не имеет смысла

2.6 Особенности XOR-связного списка
1. Поскольку надо знать сразу два элемента (последовательных), вместо одного указателя на текущий элемент списка, придётся хранить ещё указатель на следующий (предыдущий).
2. Усложнённая арифметика: навигация по списку становится дольше.
3. В каждом элементе хранится только один ёж, а не два адреса, поэтому можно экономить память. Нужна ли такая экономия -- зависит от формулировки задачи.

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

3 Заключение
XOR-связный список позволяет экономить память, однако из-за усложнённой арифметики переходы происходят дольше, что может быть неприемлемо для критичных к времени задач. Необходимость хранить для перемещения по списку адреса сразу двух элементов (текущего и соседнего с ним) может затруднять чтение листингов, однако если реализовать библиотеку или класс, предназначенные специально для работы с таким списком, работа с ним может быть абсолютно прозрачной и ничем не отличаться от работы с другими списками.

Приложение 1. Пример реализации класса XOR-связного списка на C++
pastebin (cpp)
mediafire (exe)

Статья написана по просьбе того, кто знает (:.