Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Читайте также:
  1. Ввод списка допустимых значений
  2. Выборка данных из списка
  3. Выполнить принятое решение.
  4. День 12: Составление списка шуток на выступление
  5. Доступ к элементам списка
  6. Заполнение списка конкретными данными
  7. Листинг 28. Добавление элемента в начало динамического списка
  8. Листинг 28. Добавление элемента в начало динамического списка
  9. Листинг 30. Удаление узла из списка
  10. Метод Гаусса. Однородные системы линейных уравнений и их решение.
  11. Модуль генерации запросов в базу данных и отображения выборки полей в виде списка с возможностью изменения количества записей, одновременно отображаемых на странице

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

Рекурсивное решение

void hanoi(short a, // № начальной площадки

short b, // № конечной площадки

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

if(n == 1){ // Конец рекурсии

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

return;

}

hanoi(a, 6-a-b, n-1);

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

hanoi(6-a-b, b, n-1);

} // End hanoi

При каждом рекурсивном вызове процедуры hanoi транслятор помещает значения аргументов a, b, n в так называемый стек вызова, т.е. программисту не надо вручную записывать операции помещения в стек и извлечения из стека.

В нерекурсивном решении возможны 2 варианта реализации стека: в виде массива и в виде списка.

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

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

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

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

short stack[DEEP][3],

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

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

fl = 1;

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(" %2d %2d\n", a, b);

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

a = stack[ i ][0];

b = stack[ i ][1];

n = stack[ i ][2];

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

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

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

a = 6-a-b;

n--;

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

i--;

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

fl = 0;

}

}

} // End while

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

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

} // End hanoi

Причем:

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

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

Файл 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





Дата добавления: 2014-12-27; Просмотров: 183; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:



studopedia.su - Студопедия (2013 - 2018) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление ip: 54.90.185.120
Генерация страницы за: 0.013 сек.