Вилучити елемент зі списку за вказівником на нього

Задача

Написати функцію яка приймає вказівник на елемент і вилучає цей елемент зі списку.

Рішення

Скопіювати значення з наступного елемента у поточний, модифікувати вказівник на наступний елемент і видалити наступний елемент.

    1. void RemoveItem(list* item)
    2. {
    3.   if (!item ||!item->next) return;
    4.   list *next = item->next;
    5.   item->data = next->data;
    6.   item->next = next->next;
    7. }

 

* This source code was highlighted with Source Code Highlighter.

Зауваження

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

Dead Man (1995)

Фільм у своєму темпі, який він швидко починає диктувати глядачеві, говорить про те що всі ми з народження мерці які ненадовго випали з іншого світу і повертаємося в нього, кожен своїм шляхом.

Так само подорож головного героя з такою простою і зрозумілою метою на самому початку поступово перетворюється у плутанину і питання “чи живий я”, “чи живі всі люди навколо”, “чи не є це вже царство мертвих”?

http://www.imdb.com/title/tt0112817/

 

Повернути N-тий елемент з кінця списку

Задачу можна розв’язати рекурсивно, але можна і за допомогою наступного простого алгоритму:

  1. Всановлюємо вказівника р1 та р2 на початок списку.
  2. Переміщуєма р2 на Н-1 позицій вперед.
  3. Переміщуємо обидва вказівника на одну позицію вперед.
  4. Якщо р2 не досягнув кінця списку то йдемо до кроку 3.
  5. р1 містить результат.
    1. list* NthToLastelement(list* head, int n)
    2. {
    3.   if (head == NULL || n < 1) return NULL;
    4.   list *p1 = head, *p2 = head;
    5.   for (int i = 0; i < n - 1 && p2; ++i, p2 = p2->next);
    6.   if (p2 == NULL) retun NULL;
    7.   for (; p2->next; p1 = p1->next, p2 = p2->next);
    8.   return p1;
    9. }

 

* This source code was highlighted with Source Code Highlighter.

The Blind Swordsman: Zatoichi (2003)

Особисто у мене склалося таке враження що Такєши Кітано у цьому фільмі жорстоко стьобає з голівудських бойовиків.

Особливо це видно у фінальних сценах, де навіть незацікавлені у кіно люди мають відчути що “щось тут не так” Smile

І тим не менше це кльовий, хоча і мало правдоподібний екшн.

http://www.imdb.com/title/tt0363226/

[youtube=http://www.youtube.com/watch?v=_3WNmW5X8dI&fs=1&hl=en_US]

Вилучення дублікатів з невідсортованого списку

Задача

Вилучити елементи що повторюються з невідсортованого списку. Як це можна зробити якщо нема пам’яті для додаткового буфера?

Рішення з додатковим буфером

Достатньо просто зберігати елементи в хеш-таблиці і прибирати дублікати якщо елемент з поточним значенням вже є у хешу.

Рішення без додаткового буфера

У цьому випадку можна працювати з двома вказівниками: одни вказує на поточний елемент що ми його перевіряємо, другий – для порівняння з усіма попкркдніми елементами.

В списку з одного елемента всі елементи унікальні, тому перевірку можна почати з другого елемента. Якщо другий елемент є унікальним то тепер у нас 2 елементи з якими можна порівнювати. І так далі…

void RemoveDups(list* head)
{
    if (head == NULL) return;
    list* prev = head;
    list* cur = prev->next;
    while (cur)
    {
	for (list *run = head; run != cur; run = run->next)
	{
  		if (run->data == cur->data)
		{
			// remove current item
			list *tmp = cur->next;
			prev->next = tmp;
			delete cur;
			cur = tmp;
                }
	}
		 
	if (run == cur)
	{
	    prev = cur;
	    cur = cur->next;
	}
    }
}

Також дивись Як прибрати символи-дублікати з С-рядка

Чи є один рядок здвинутим іншим рядком

Задача

Треба визначити для двох рядків чи є один з них результатом циклічного зсуву символів іншого рядка.

Рішення

Якщо додати до першого рядка його копію то другий рядок має бути підрядком сумарного рядка, якщо звісно це ті ж самі рядки.

 
bool IsRotation(char *s1, char *s2)
{
    bool result = false;
    int l1 = strlen(s1), l2 = strlen(s2);
    if (l1 == l2 && l1 > 0)
    {
        char *s = new char[l1 * 2 + 1];

        strcpy(s, s1); // concat strings
        strcpy(s + l1, s1)

        result = strstr(s, s2) != NULL;
        delete []s;
    }

    return result;
}

Встановлення колонок і рядків в 0

Задача

Для масиву розміром MxN якщо будь-який елемент дорівнює 0 встановити всі елементи його рядка і колонки в 0.

Рішення

Головна проблема полягає в тому щоб при встановленні елементів у 0 не враховувати їх при подальшому пошуку. Інакше змінені елементи будуть можуть бути просканованим пізніше і призведуть до встановлення в 0 нових елементів.
Найпростішим рішенням буде створити копію матриці в якій і міняти елементи, а сканування проводити лише на оригінальній матриці.
Але насправді немає необхідності  у всих MxN елементах – нам достатньо лише знати в яких рядках та стовпцях зустрівся хоча б один 0.
    1. void SetZeroes(int* a, int n, int m)
    2. {
    3.     int *row = new int[m];
    4.     int *col = new int[n];
    5.     // scan elements
    6.     for (int i = 0; i < n; ++i)
    7.     {
    8.         for (int j = 0; j < m; ++j)
    9.         {
    10.             if (a[i][j] == 0)
    11.             {
    12.                 row[i] = 1;
    13.                 col[j] = 1;
    14.             }
    15.         }
    16.     }
    17.     // set elements
    18.     for (int i = 0; i < n; ++i)
    19.     {
    20.         for (int j = 0; j < m; ++j)
    21.         {
    22.             if (row[i] == 1 || col[j] == 1)
    23.             {
    24.                 a[i][j] = 0;
    25.             }
    26.         }
    27.     }
    28.     delete [] row;
    29.     delete [] col;
    30. }

* This source code was highlighted with Source Code Highlighter.

Glen Cook. The Black Company / Глен Кук. Чорний загін (1984-…)

Це найцікавіше і найкраще фентазі яке я будь-коли читав. Усі 10 томів (автор працює ще над двома) пролітають як мить. Є активні/бойові, є загадкові, є інтриги, є розбудовування армії (ледь не стратегічна гра), є тягучі і “заумні”…

Причому свого часу я почав читати з 4го тому і мене настільки затягнуло що поїхав у Дніпро і докупив інші що були. Також хочу зауважити на диво підходяще оформлення для усієї серії.

Власне переказувати щось детально зовсім не варто, краще читайте – не пошкодуєте.

Усі герої живі, з нелогічною і недалекоглядною поведінкою, вибриками і характерами. Нічого шаблонного нема, навіть не дивлячись на те що це фентезі.

І оскільки дії відбуваються на протязі кількох десятків років то не дивно що герої помирають, зникають, з’являються нові.

The Black Company / Чорний Загін (1984)

Загін найманців з давньою історію змінює платника і втягується в якусь авантюру з могутніми чаклунами і воїтелями на півночі.

Shadows Linger / Тіні згущуються (1984)

Сучасні колдуни і правителі виявляються усього лише прислужниками та жалюгідними слабаками у порівнянні з давніми злодіями. А ті, хоч і мертві давно, намагаються прорватися назад у світ живих.

The White Rose / Была Троянда (1985)

У головної злодійки з’явилася противага. Дії відбуваються у дивному місці з участю богів і істот з паралельного світу (мало їм було місцевих чаклунів та потвор).

Shadow Games / Гра Тіней (1989)

Загін мандрує, влазить у місцеву полдітику інших країн і зустрічає старих ворогів і знайомих що свого часу тікали від них.

The Silver Spike / Срібний клин (1989)

“Побічний” роман герої якого з часом вливаються в основний серіал.

Культ смерті виховує втілення богині смерті. Не дивно що вона є давно померлим близнюком головної злодійки і її з найголовнішим ворогом.

Dreams of Steel / Сталеві сни (1990)

Тепер головний ворог і злодійка керує загоном. Осада міста, стратегічна гра (:

Black Seasons / Суворі часи (1996)

Війна, осада, захоплення територій, повномасштабні бойові дії, походи, нальоти і всяке геройство.

She Is the Darkness / Темрява (1997)

Усе погано. Чаклуни слабіші і воюють між собою, але в той же час вони підступніші і здається скоро усьому світу прийде капець.

Water Sleps / Води сплять (1999)

Основні діючі герої сплять у пастці між світами, їхні нащадки діють як підпілля у місті яким колись керували.

Soldiers Live / Солдати живуть (2000)

Нарешті щось прояснюється щодо походження Чорного Загону, його місії та і будови світу взагалі. Дії відбуваються між паралельними реальностями.

Що далі?

В даний час автор працює над двома новими книгами:

  • A Pitiless Rain (Безжальний дощ), та
  • Port of Shadows (Порт тіней)

Ну що ж, чекаємо…

Kreator–2005–Enemy of God

Соковитий та “правильний” thrash, класика від першої до останньої ноти.

Якби цей диск зєявився років 20 тому, можливо він був би найпопулярнішим за всю історію комерційної музики :)

А пісня Impossible Brutality взагалі тепер є моєю найулюбленішою у команди.

[youtube=http://www.youtube.com/watch?v=HElwDmEjcgc&fs=1&hl=en_US]