Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Нерекурсивное решение. Стек в виде массива
# 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 группы видеофункций. |
Последнее изменение этой страницы: 2017-04-12; Просмотров: 368; Нарушение авторского права страницы