И снова возвращаемся к поиску потерянных ключей

Содержание

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

/* Найти ключи с помощью поиска в глубину. */
#include <stdio.h>
#include <string.h>

#define MAX 100

/* структура базы данных keys (ключи) */
struct FL {
  char from[20];
  char to[20];
  char skip;
};

struct FL keys[MAX];  /* массив структур БД */

int f_pos = 0;    /* количество комнат в доме */
int find_pos = 0; /* индекс для поиска в БД keys */

int tos = 0;      /* вершина стека */
struct stack {
  char from[20];
  char to[20];
} ;
struct stack bt_stack[MAX]; /* стек, используемый для поиска
                               с возвратом */

void setup(void), route(void);
void assert_keys(char *from, char *to);
void push(char *from, char *to);
void pop(char *from, char *to);
void iskeys(char *from, char *to);
int find(char *from, char *anywhere);
int match(char *from, char *to);

int main(void)
{
  char from[20] = "входная_дверь";
  char to[20] = "ключи";

  setup();
  iskeys(from, to);
  route();

  return 0;
}

/* Инициализация база данных. */
void setup(void)
{
  assert_keys("входная_дверь", "гостиная");
  assert_keys("гостиная", "ванная");
  assert_keys("гостиная", "холл");
  assert_keys("холл", "спальня1");
  assert_keys("холл", "спальня2");
  assert_keys("холл", "большая_спальня");
  assert_keys("гостиная", "кухня");
  assert_keys("кухня", "ключи");
}

/* Запомнить факты в базе данных. */
void assert_keys(char *from, char *to)
{
  if(f_pos < MAX) {
    strcpy(keys[f_pos].from, from);
    strcpy(keys[f_pos].to, to);
    keys[f_pos].skip = 0;
    f_pos++;
  }
  else printf("База данных keys заполнена.\n");
}

/* Показать путь к ключам. */
void route(void)
{
  int t;

  t = 0;
  while(t < tos) {
    printf("%s", bt_stack[t].from);
    t++;
    if(t < tos) printf(" - ");
  }
  printf("\n");
}

/* Посмотреть, есть ли ребро в графе. */
int match(char *from, char *to)
{
  register int t;

  for(t=f_pos-1; t > -1; t--)
    if(!strcmp(keys[t].from, from) &&
      !strcmp(keys[t].to, to)) return 1;

  return 0;  /* не найдено */
}

/* Зная откуда (from), попасть куда-нибудь (anywhere). */
int find(char *from, char *anywhere)
{ 
  find_pos = 0;

  while(find_pos < f_pos) {
    if(!strcmp(keys[find_pos].from, from) &&
      !keys[find_pos].skip) {
        strcpy(anywhere, keys[find_pos].to);
        keys[find_pos].skip = 1;
        return 1;
    }
    find_pos++;
  }
  return 0;
}

/*  Определить, имеется ли путь из from (из) в to (в). */
void iskeys(char *from, char *to)
{
  char anywhere[20];

  if(match(from, to)) {
    push(from, to); /* расстояние */
    return;
  }

  if(find(from, anywhere)) {
    push(from, to);
    iskeys(anywhere, to);
  }
  else if(tos > 0) {
    pop(from, to);
    iskeys(from, to);
  }
}

/* Подпрограммы обращения к стеку */
void push(char *from, char *to)
{
  if(tos < MAX) {
    strcpy(bt_stack[tos].from, from);
    strcpy(bt_stack[tos].to, to);
    tos++;
  }
  else printf("Стек заполнен.\n");
}

void pop(char *from, char *to)
{
  if(tos > 0) {
    tos--;
    strcpy(from, bt_stack[tos].from);
    strcpy(to, bt_stack[tos].to);
  }
  else printf("Стек пуст.\n");
}