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

Задача

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

Рішення

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

    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 елементи з якими можна порівнювати. І так далі…

    1. void RemoveDups(list* head)
    2. {
    3.    if (head == NULL) return;
    4.    list* prev = head;
    5.    list* cur = prev->next;
    6.    while (cur)
    7.    {
    8.      for (list *run = head; run != cur; run = run->next)
    9.     {
    10.       if (run->data == cur->data)
    11.       {
    12.         // remove current item
    13.         list *tmp = cur->next;
    14.         prev->next = tmp;
    15.         delete cur;
    16.         cur = tmp;
    17.       }
    18.     }
    19.     if (run == cur)
    20.     {
    21.       prev = cur;
    22.       cur = cur->next;
    23.     }
    24.   }
    25. }

 

* This source code was highlighted with Source Code Highlighter.

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

Visual Studio: Watch Window Pseudo registers

Watch Window Pseudo registers

Pseudo register

Description

@ERR

Last error value (GetLastError result)

@TIB

Thread information block for current thread

@CLK

Clock register

Trick: enter @CLK and @CLK=0.the second zeroes out the timer after continuing debugging.

@EAX, @EBX, @ECX, @EDX, @ESI, @EDI, @EIP, @ESP, @EBP, @EFL

CPU registers

@CS, @DS, @ES, @SS, @FS, @GS

CPU segment registers

@ST0, @ST1, @ST2, @ST3, @ST4, @ST5, @ST6, @ST7

CPU floating-point registers

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

Задача

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

Рішення

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

 
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 (Порт тіней)

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