Задача: после игры в домино остался ряд камней. Используя двунаправленный список, определить, правильно ли расположены камни домино.
Алгоритм решения:
1. Формируем двунаправленный список (каждый элемент будет содержать два поля со значениями на камне и указатели на следующий и предыдущий элементы). В результате у нас окажется последний элемент списка.
2. Начиная с последнего элемента, спускаемся по ссылкам к предыдущим и сравниваем значения на камнях.
3. При первом несовпадение выводим "NO" и завершаем программу, в противном случае, выводим "YES".
Примечание: значения на камнях генерируются случайным образом.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
struct list
{
int leftVal;
int rightVal;
list *next; // ссылка на следующий элемент
list *prev; // ссылка на предыдущий
};
// Начальный элемент списка
list *cur;
// Формируем двунаправленный список
void initgame ()
{
int i;
cur = new list;
cur->prev = cur->next = NULL;
for (i=0; i<MAX; i++)
{
list *tmp;
tmp=new list;
tmp->leftVal =rand() % 6;
tmp->rightVal =rand() % 6;
tmp->next=cur->next;
tmp->prev=cur->prev;
cur->next=tmp;
cur->next->prev=cur;
cur=tmp;
cur->next->prev=cur;
}
return;
}
// Правильно ли расположены камни домино?
int victory ()
{
list *tmp;
tmp = cur;
while (tmp->prev != NULL)
{
if (tmp->leftVal != tmp->prev->rightVal) return 0;
tmp=tmp->prev;
}
return 1;
}
int main ()
{
initgame();
if (victory() == 1) printf("YES\n");
else printf("NO\n");
return 0;
}