![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Причем:
- элемент стека – произвольная структура;
- операции над стеком позволяют организовать в программе произвольное число стеков.
Файл 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. Укажите способ "потери" выделенной в "куче" памяти.
Дата публикования: 2014-11-02; Прочитано: 296 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!