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

# define DEEP 20 // Максимальная глубина стека

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

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

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

short stack[DEEP][3],

i; // Индикатор уровня стека

bool fl; // false – стек пуст. Конец вычислений

fl = true ;

i = -1;

while (fl){

if (n > 1){ // Заполнение стека

i++;

stack[ i ][0] = a;

stack[ i ][1] = b;

stack[ i ][2] = n;

// Подготовить первое обращение

b = 6-a-b;

n--;

} else {

if (i > = 0){ // Стек не пуст

// Печать вершины уровня 1

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

// Извлечь данные из стека

a = stack[ i ][0];

b = stack[ i ][1];

n = stack[ i ][2];

// Печать " корня"

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

// Подготовить второе обращение

a = 6-a-b;

n--;

// Убрать вершину из стека

i--;

} else { // Стек пуст

fl = 0;

}

}

} // End while

// Печать последней вершины

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

} // End hanoi

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

Причем:

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

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

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

# include < stdio.h>

# include < stdlib.h>

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

int main( ){

short n;

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

printf(" \n\nЧисло дисков: " ); scanf(" %hd", & 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; // Указатель на содержимое. Помещается в стек

bool fl = true ; // false – конец вычислений

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

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

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

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

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

}

while (fl){

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

cont= new Cont; // Размещение содержимого

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

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

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

}

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

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

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

if (push((CTRL*)ident, cont)){

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

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

}

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

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

n--;

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

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

// Получить указатель на элемент " вершины"

cont = (CONT*)top((CTRL*)ident);

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

fl = 0;

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

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

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

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

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

n--;

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

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

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

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

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

}

}

}

} // End while

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

} // End hanoi

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

// stek.h

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

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

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

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

};

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

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

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

};

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

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

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

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

// элемент

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

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

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

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

// stek.cpp

# include " stek.h"

# include < stdlib.h>

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

void* init( ){

Ctrl* ident;

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

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

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

}

return ident;

} // End init

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

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

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

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

returntrue ;

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

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

ident-> prev = ident-> tek;

return false;

}

} // End push

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

void * top(Ctrl* ident){

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

return NULL;

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

return ident-> tek-> cont;

}

} // End top

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

bool pop(Ctrl* ident){

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

return true;

} else {

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

ident-> tek = ident-> prev; return false;

}

} // End pop

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

void finish(Ctrl* ident){

if (ident! = NULL){

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

ident-> prev = ident-> tek-> prev; delete ident-> tek;

ident-> tek = ident-> prev;

}

delete ident;

}

} // End finish

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

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

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

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

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

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

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

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

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

8. Для чего служит оператор delete?

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

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

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

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

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

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

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

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

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

7. Чем отличаются записи delete и delete [ ]?

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

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

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

 

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

В этом разделе излагаются средства языка C, позволяющие расширить приведенные ранее возможности консольных приложений в части работы с экраном в текстовом режиме.

Для простоты изложения будем считать, что окно консоли имеет 25 строк и 80 позиций в строке. Всего 2000 ячеек.

Замечание. Как задать указанные размеры окна консоли, можно прочесть в Приложении 1 «Среда разработки MinGW C/C++ ».

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

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

Координаты верхнего левого угла экрана в текстовом режиме: 1, 1.

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

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

Для заданий цвета используют символические константы, определенные в файле coniow.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 белый

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

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться: