|
Лабиринт часть 2 |
Все обучалки раздела |
Очереди
Описание
|
Дается определение стека, а также его реализация.
Программа создает стек, заполняет его числами, поочередно выводит их и освобождает память.
Скачать обучалку (Visual C++ 6)
|
|
|
Исходный код
Файл main.c
// Done by TheTutor -- 06/09/01
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
#include <stdio.h>
#include "stack.h"
// Мы просто проделаем с нашим стеком пару тестов --
// Все основное объяснение находится в файлах "stack.h" и "stack.c"
int main()
{
// Создадим стек -- Всегда полезно инициализировать переменные,
// присваивая им известные величины
STACK stack = {0};
int counter = 0; // Счетчик для циклов for
InitStack(&stack,10);
// Заполним стек числами 0 - 9
// Когда окончится этот цикл for, стек будет полон
for(counter = 0; counter < 10; counter++)
Push(&stack,counter);
if(Push(&stack,22))
printf("This is we bad! We just pushed an element onto a full stack.\n\n");
// (сообщение - "Это плохо. Мы поместили элемент в полный стек")
else
printf("This is good! We were denied while trying to \"push\" onto a full stack.\n\n");
// (сообщение - "Это хорошо. Нам было отказано в помещении элемента в полный стек")
// Напечатаем числа - Вы увидите их в порядке LIFO (последнее, которое мы поместили в стек,
// будет первым, которое мы извлечем)
for(counter = 0; counter < 10; counter++)
printf("We just popped off #%d\n",Pop(&stack));
if(FreeStack(&stack))
printf("\nYeah the memory was freed successfully!\n\n");
else
printf("\nOh NO! An error occurred while trying to free the memory");
return 0;
}
/* Примечание
Что произойдет, если мы не извлечем функцией Pop() все элементы из стека, и попробуем
освободить его? Я знаю, что вы думаете. Вы думаете "Все равно, вся память будет освобождена."
И это ПРАВИЛЬНО! Вся память все равно освободится.
*/
// © 2001 GameTutorials
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
|
Файл stack.h
#ifndef STACK_H
#define STACK_H
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
#include <memory.h> // Используется для memset()
#include <stdlib.h> // Стандартная библиотека
// К сожалению, в языке С нет типа "bool". Мне нравится этот тип, поэтому
// я определяю свой собственный - теперь мы можем использовать "bool" также,
// как и в С++
typedef unsigned char bool;
#define true 1
#define false 0
/* Прежде всего, что такое стек? Стек, это "контейнер", построенный по принципу
LIFO. Но что же это значит?
LIFO означает Last In First Out (последним пришел, первым вышел). Поэтому стек
это ничего большего, чем "что-то", имеющее это свойство.
Идеальным примером является стопка тарелок.
plate5 Пятая тарелка (plate5) была добавлена последней в стопку тарелок.
plate4 Когда придет время мыть тарелки, пятая тарелка будет первой, которую
plate3 вымоют (удалят из стопки). Когда plate5 будет удалена, четвертая (plate4)
plate2 получит статус "последней тарелки в стопке", и ее будут мыть следующей, и т.д.
plate1
Становится понятно? Возвращаясь к программированию, стек это данные (переменные),
упорядоченые по принципу LIFO.
Есть много способов реализовать стек, но мы собираемся использовать для этого массив.
*/
// Вот как будет выглядеть наш стек -
// Это будет стек целых чисел, имеющий динамический размер, который будет задаваться
// при создании стека (объявлении переменной типа STACK)
typedef struct _STACK
{
int *array; // Указатель на место, где будет храниться наш динамический стек
int max_elements; // Переменная, содержащая данные о максимальном количестве
// целых чисел, которое сможет хранить стек
int index; // Всегда будет соответствовать первому пустому месту в стеке,
// что означает, что вершина стека всегда будет (index - 1)
} STACK;
// Это функции, которые будут использоваться для доступа к стеку
// Эту функцию необходимо вызвать, прежде чем мы сможем использовать наш стек. Она установит
// максимальный размер стека и выделит для него память. Возвращает true если все прошло
// успешно, false в обратном случае
bool InitStack(STACK *stack, int size);
// Эта функция берет число "num" и помещает его в стек (добавляет его на вершину стека).
// Если все прошло успешно, она возвращает true, в другом случае возвращает false
bool Push(STACK *stack, int num);
// Pop() возвращает верхний элемент стека и удалает его из стека (т.е. мы сможем заполнить
// его чем-либо еще). Если в стеке нет элементов, по умолчанию Pop() возвращает 0.
int Pop(STACK *stack);
// Освобождает всю память, относящуюся к стеку - возвращает true в случае успеха, false в обратном.
bool FreeStack(STACK *stack);
/* Это все, что нам нужно - Теперь, для безопасности, возможно будет хорошей идеей
заменить int Pop(STACK *stack) на bool Pop(STACK *stack int *top);
Тогда Pop() возвратит true в случае успешного выполнения и заполнит переменную "top"
верхним элементом стека. В другом случае возвратится false и "top" останется без изменений.
Но, хотя это и необязательно необходимо, нет никакого способа кому-либо еще, вызывающему
функцию, узнать, успешно ли выполнилась Pop() или нет, так как 0 может быть действительно
элементом стека.
*/
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
#endif
|
Файл stack.c
#include "stack.h"
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
// Самое интересное - Реализация нашего стека!
bool InitStack(STACK *stack, int size)
{
// Мы не можем создать стек отрицательного или нулевого размера
if(size <= 0)
return false;
// Создадим массив целых чисел, величиной равной передаваемому размеру ("size")
stack->array = (int*)malloc(size * sizeof(int));
// Проверка на ошибку - malloc возвращает NULL, если функция не смогла
// выделить запрашиваемую нами память
if(stack->array == NULL)
return false;
// В другом случае, все создалось успешно, поэтому задаем значения двум другим
// переменным и возвращаем true
stack->max_elements = size;
stack->index = 0; // В стеке ничего нет
return true;
} // конец InitStack(STACK *stack, int size)
bool Push(STACK *stack, int num)
{
// Если стек полон - мы НЕ можем ничего поместить в него
if(stack->index == stack->max_elements)
return false;
// Заполняем стек переданным числом "num"
stack->array[stack->index] = num;
// Двигаемся к следующему пустому месту стека
stack->index++;
return true;
}
// Возвращает верхний элемент стека и удаляет его из стека
int Pop(STACK *stack)
{
// Если стек пустой - мы не можем ничего извлечь из него, поэтому
// по умолчанию мы возвращаем ноль
if(!stack->index)
return 0;
// В другом случае мы возвращаем верхний элемент стека и удаляем его из стека
stack->index--; // Двигаемся к верхнему элементу, также индекс теперь
// будет верно соответствовать следующему пустому месту в стеке
return stack->array[stack->index]; // Вершина стека
}
// И наконец, так как мы хорошие программисты, мы освобождаем всю память
bool FreeStack(STACK *stack)
{
// Не можем освободить стек, который ни на что не указывает (не связанный с областью памяти)
if(!stack)
return false;
// Та же идея - если переменная "array" стека не ссылается ни на какую память,
// мы не можем освободить ее
if(!stack->array)
return false;
free(stack->array);
memset(stack,0,sizeof(STACK)); // Обнуляем стек
return true; // Мы освободили память!
}
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
|
Скачать обучалку (Visual C++ 6)
Лабиринт часть 2 |
Все обучалки раздела |
Очереди
|
|
