Причем:
- элемент стека – произвольная структура;
- операции над стеком позволяют организовать в программе произвольное число стеков.
Файл 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