Нерекурсивное решение. Стек в виде списка

Причем:

- элемент стека – произвольная структура;

- операции над стеком позволяют организовать в программе произвольное число стеков.

Файл hanoi.c. Главная процедура и процедура решения "ханойской башни".

# include <stdio.h>

# include <stdlib.h>

# include <alloc.h>

# include "stek.h" // Заголовочный файл для операций над стеком

void main(void){

short n;

void hanoi(short, short, short); // Прототип функции hanoi

printf("\n\nЧисло дисков:");

scanf("%d", &n);

printf("\nПерестановки\n");

hanoi(1, 2, n);

}// End main

/* Ханойская башня */

void hanoi( short a, // Исходная площадка

short b, // Площадка - цель

short n){ // Число дисков

typedef struct { // Содержимое элемента стека. В стек не помещается

short a, b, n;

} Cont;

Cont *cont; // Указатель на содержимое. Помещается в стек

short fl = 1; // 0 – конец вычислений

void *ident; // Идентификатор стека

ident = init(); // Операция размещения стека

if (ident == NULL){ // Нет памяти под управляющие элементы стека

printf("\n\nНет памяти под стек \"Ханой\"\n\n");

exit(0); // Выход из программы. Это обработка ошибки

}

while (fl){

if (n > 1){ // Помещение в стек

cont=(Cont*)malloc(sizeof (Cont));// Размещение содержимого

if (cont == NULL){ // Нет памяти под содержимое элемента

printf("\n\nНет памяти под элемент стека \"Ханой\"\n\n");

exit(0);// Тоже обработка ошибки

}

/* Заполнение содержимого элемента стека */

cont->a = a; cont->b = b; cont->n = n;

if (push(ident, cont)){ //Поместить указатель на элемент в стек

printf("\n\nНет памяти под стек \"Ханой\"\n\n");

exit(0); // Обработка ошибки

}

/* Опуститься на 1 уровень */

b = 6-a-b; // Подготовка следующего содержимого элемента

n--;

} else { // Печать переноса диска и извлечение из стека

printf(" %2d %2d\n", a, b);

cont = top(ident); // Получить указатель на элемент "вершины"

if (cont == NULL){ // Стек пуст

fl = 0;

} else { // Извлечение содержимого и печать переноса диска

a = cont->a; b = cont->b; n = cont->n;

printf(" %2d %2d\n", a, b);

/* Опуститься на 1 уровень */

a = 6-a-b; // Подготовка следующего элемента

n--;

free(cont);// Освободить память "верхнего" элемента

/* Извлечь "вершину" стека. Освободить память

if (pop(ident)){ // Ошибка при извлечении

printf("\n\nОшибка при извлечении из стека

\"Ханой\"\n\n");

exit(0); // Обработка ошибки

}

}

}

} // End while

finish(ident); // Освободить память из под стека

} // End hanoi

Файлы stek.h и stek.c. Операции над стеком.

/* stek.h */

/* Типы данных */

typedef struct stek{ // Стек указателей на элементы

struct stek *prev; // Указатель на предыдущий элемент стека

void *cont; // Указатель на содержимое элемента

} Stek;

typedef struct { // Управляющие переменные

Stek *tek, // Указатель на текущий элемент стека

*prev; // Указатель на предыдущий элемент стека

} Ctrl;

/* Прототипы функций */

void * init(void); // Разместить и инициализировать управляющие

// переменные

short push(Ctrl *ident, void *cont) // Поместить в стек указатель на элемент

void * top(Ctrl *ident); // Прочесть информацию "вершины" стека

short pop(Ctrl *ident); // Удалить "вершину" стека

void finish(Ctrl *ident); // Очистить стек и освободить память под

// управляющие переменные

/* stek.c */

# include <alloc.h>

# include "stek.h"

/* Инициализация стека */

void* init(void){

Ctrl *ident;

ident = malloc(sizeof (Ctrl)); // Размещение управляющих переменных

if (ident!= NULL){ // Проверка выделения памяти

ident->prev = ident->tek = NULL;

}

return ident;

} // End init

/* Поместить указатель на элемент в стек */

short push(Ctrl *ident, void *cont){

ident->tek = (Stek *)malloc(sizeof (Stek));// Выделение памяти под указатель

if (ident->tek == NULL){ // Проверка выделения памяти

return 1;

} else { // Включение элемента в список

ident->tek->prev = ident->prev; ident->tek->cont = cont; ident->prev = ident->tek;

return 0;

}

} // End push

/* Прочесть "вершину" стека */

void *top(Ctrl *ident){

if (ident->tek == NULL){ // Стек пуст. Ошибка!

return NULL;

} else { // Возврат указателя на содержимое элемента

return ident->tek->cont;

}

} // End top

/* Удалить "вершину" стека */

short pop(Ctrl *ident){

if (ident->tek == NULL){ // Стек пуст. Ошибка!

return 1;

} else {

ident->prev = ident->tek->prev; free(ident->tek); ident->tek = ident->prev;

return 0;

}

} // End pop

/* Освободить память под стек и управляющие переменные */

void finish(Ctrl *ident){

if (ident!= NULL){

while (ident->tek!= NULL){ //

ident->prev = ident->tek->prev; free(ident->tek); ident->tek = ident->prev;

}

free(ident);

}

} // End finish

Вопросы для самопроверки и контроля

Вопросы для самопроверки

1. Что означают операторы * и & при работе с указателями?

2. Что означает запись *(p + i), где p – указатель?

3. Есть ли понятие указатель в языке Basic?

4. Различается ли запись литералов типа string в языках Basic и C?

5. Укажите средство для сравнения строк в языке C.

6. Что делает функция gets?

7. Укажите средства для сцепления строк в языках C и Basic.

8. Для чего служит функция free?

9. Дайте определение рекурсивной процедуры.

10. С помощью какой структуры данных реализуется рекурсия?

Контрольные вопросы

1. Можно ли менять начальный адрес массива во время выполнения программы?

2. Эквивалентны ли записи a[ i ] и *(a+i), если a – имя массива?

3. В каком из изучаемых языков отсутствуют переменные предопределенного типа string?

4. Укажите средство для сравнения строк в языке Basic.

5. Можно ли задать значение одной строки другой в языке C оператором присваивания?

6. Чем отличаются результаты выполнения функций lset и rset?

7. Чем отличаются функции malloc и calloc?

8. Как освобождается память, выделенная в "куче"?

9. Что такое стек?

10. Укажите способ "потери" выделенной в "куче" памяти.

 

РАБОТА С ЭКРАHОМ

В этом и последующих разделах излагаются средства языка C, точнее средства, входящие в среду разработки Borland 3.1 C++, работающей под управлением операционной системы MS DOS.

Различают текстовый и графический режимы(mode).

В текстовом режиме экран делится на 25 строк и 80 позиций или 43 строки и 80 позиций в зависимости от настройки среды. Каждая ячейка имеет байт символа и байт атрибута. Символ выводится на экран, а атрибут показывает, как он представлен на экране(цвет символа и фона, интенсивность и т.п.).

В графическом режиме экран делится на элементы разложения(пиксели). Каждый пиксель выглядит точкой на экране. Число строк и пикселей в строке зависит от настроек монитора и видеоадаптера.

Координаты ячейки или элемента задаются парой чисел: № позиции в строке, № строки.

Координаты верхнего левого угла экрана:

в текстовом режиме: 1, 1;

в графическом: 0, 0.

Окно – это прямоугольный участок, определенный на экране при работе в текстовом режиме. При работе вывод программы ограничен активным окном, остальной экран неизменен. По умолчанию окном является весь экран от ячейки с координатами (1, 1) до ячейки с координатами (80, 25). В графическом режиме такой же прямоугольный участок называют областью представления (view port). Для работы с экраном используются видеофункции, прототипы которых находятся в: для текстового режима в заголовочном файле conio.h, для графики - graphics.h. Большинство видеофункций работают в относительных координатах в пределах активного окна. Координаты отсчитываются относительно координат левого верхнего угла окна.

Текстовый режим(textmode)

Определены следующие видеорежимы:

BW40 0 черно-белый, 40 позиций в строке;

C40 1 16 цветов, 40 позиций в строке;

BW80 2 черно-белый, 80 позиций в строке;

C80 3 16 цветов, 80 позиций в строке;

MONO 7 монохромный, 80 позиций в строке.

Режимы представляют собой символические константы, определенные в файле conio.h. В программе они используются в качестве аргумента функции textmode. Для современных мониторов следует использовать только режим C80.

Информация для каждой ячейки занимает в памяти 2 байта: первый содержит значение выводимого символа, второй – атрибут. Атрибут определяет цвет выводимого символа (foreground) и цвет фона ячейки(background).

Для заданий цвета используют символические константы, определенные в файле conio.h.

BLACK 0 черный

BLUE 1 синий

GREEN 2 зеленый

CYAN 3 бежевый цвета символов и фона

RED 4 красный

MAGENTA 5 сиреневый

BROWN 6 коричневый

LIGHTGRAY 7 светлосерый

DARKGRAY 8 темносерый

LIGHTBLUE 9 голубой

LIGHTGREEN 10 светлозеленый

LIGHTCYAN 11 светлобежевый

LIGHTRED 12 светлокрасный только цвета символов

LIGHTMAGENTA 13 светлосиреневый

YELLOW 14 желтый

WHITE 15 белый

BLINK 128 мерцание

 

Различают 4 группы видеофункций.