Различные структуры данных. Реализация

SashaMercury
Дата: 20.01.2015 03:37:56
Здравствуйте.
Сегодня проектировал стек LIFO, вот что получилось

stack.h

#include <stdio.h>
#include <stdlib.h>

#define SEMPTY -1

struct Stack
{
	size_t max_size;
	size_t cur;//позиция для записи следующего элемента
	int (*push)(int el, struct Stack*);
	int (*pop)(struct Stack*);
	int* buffer;
};

struct Stack* createStack(size_t maxsize);



stack.c

#include "stack.h"

int push(int el, struct Stack* s)
{
	if (s->cur == s->max_size)
	{
		printf("stack is full.\n");
		return -1;
	}
	else
	{
		s->buffer[s->cur++] = s->cur;
		return 0;
	}
}

int pop(struct Stack* s)
{
	if (s->cur == 0)
	{
		printf("stack is empty.\n");
		return SEMPTY;
	}
	else
	{
		return *(s->buffer + --s->cur);
	}
}

struct Stack* createStack(size_t maxsize)
{
	struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack));
	s->max_size = maxsize;
	s->cur = 0;
	s->push = push( );
	s->pop = pop(s);
        s->buffer = NULL;
	s->buffer = (int*)malloc(sizeof(int)*s->max_size);
	return s;
}


Подскажите пожалуйста, как правильно реализовать функцию createStack() ? Мне не нравится использование SEMPTY, но пока не придумал как от этого избавиться. Как бы вы поступили ?
RWolf
Дата: 20.01.2015 10:54:57
SashaMercury
Мне не нравится использование SEMPTY, но пока не придумал как от этого избавиться. Как бы вы поступили ?

bool pop(struct Stack* s, int* result)
MasterZiv
Дата: 20.01.2015 11:27:48
Еще лучше кидать исключение, но их нет в С.

Можно их имитировать через setjump/longjump.
Аноним123
Дата: 20.01.2015 12:53:47
Считаю, что C-style стек должен выглядеть как-то так:

stack.h
#ifndef STACK_H
#define STACK_H

#include <stddef.h> // size_t

struct Stack;

/**
 * @brief StackCreate - создает новый стек
 * @param max_size - максимально возможное число элементов в стеке
 * @return указатель на созданный стек или NULL, в слечае неудачи
 */
struct Stack* StackCreate(size_t max_size);

/**
 * @brief StackPush - добавляет новый элемент в стек
 * @param s - валидный указатель на стек
 * @param val - новый элемент
 * @return число вставленных элементов
 */
int StackPush(struct Stack* s, int val);

/**
 * @brief StackPop - извлекает элемент из стека
 * @param s - валидный указатель на стек
 * @param result - результат
 * @return число извлеченных элементов
 */
int StackPop(struct Stack* s, int* result);

#endif



stack.c
#include "stack.h"

#include <assert.h>
#include <stdlib.h> // malloc

struct Stack
    {
    size_t max_size;
    size_t cur_size;
    int* buffer;
    };

struct Stack* StackCreate(size_t max_size)
    {
    struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack));
    if (s != NULL)
        {
        s->max_size = max_size;
        s->cur_size = 0;
        s->buffer = (int*)malloc(sizeof(int) * max_size);
        if (s->buffer == NULL)
            {
            free(s);
            s = NULL;
            }
        }
    return s;
    }

int StackPush(struct Stack* s, int val)
    {
    assert(s != NULL);
    if (s->cur_size == s->max_size)
        {
        return 0;
        }
    s->buffer[s->cur_size] = val;
    ++s->cur_size;
    return 1;
    }

int StackPop(struct Stack* s, int* result)
    {
    assert(s != NULL);
    if (s->cur_size == 0)
        {
        return 0;
        }
    --s->cur_size;
    *result = s->buffer[s->cur_size];
    return 1;
    }

Dimitry Sibiryakov
Дата: 20.01.2015 13:17:35

SashaMercury
Сегодня проектировал стек LIFO, вот что получилось

Если ты идёшь по пути чистого С, то один malloc лишний: гораздо удобнее работать со
структурой переменного размера, поскольку память не фрагментируется. Указывать
максимальный размер стека при создании, возможно, соответствует техзаданию, но тоже
абсолютно излишне.

Posted via ActualForum NNTP Server 1.5

SashaMercury
Дата: 20.01.2015 13:33:45
Аноним123,
хочу реализовать стек как один объект
SashaMercury
Дата: 20.01.2015 13:39:11
Dimitry Sibiryakov
SashaMercury
Сегодня проектировал стек LIFO, вот что получилось

Если ты идёшь по пути чистого С, то один malloc лишний: гораздо удобнее работать со
структурой переменного размера, поскольку память не фрагментируется. Указывать
максимальный размер стека при создании, возможно, соответствует техзаданию, но тоже
абсолютно излишне.


Вы предлагаете реаллоцировать при добавлении элемента? Если я вас правильно понял, то думаю что это спорный момент. Реаллоцирование тратит много времени. Максимальный размер стека необходим для безопасной работы программы
Dimitry Sibiryakov
Дата: 20.01.2015 13:47:36

SashaMercury
Вы предлагаете реаллоцировать при добавлении элемента?

Нет, я предлагаю использовать связанный список буферов. Возможно, заранее
предопределённого размера.

Posted via ActualForum NNTP Server 1.5

mayton
Дата: 20.01.2015 14:14:57
Сейчас коллеги мы дойдем до формулы расчёта

INITIAL_EXTENT=
NEXT_EXTENT=
MasterZiv
Дата: 20.01.2015 14:52:53
Dimitry Sibiryakov
SashaMercury
Вы предлагаете реаллоцировать при добавлении элемента?

Нет, я предлагаю использовать связанный список буферов. Возможно, заранее
предопределённого размера.


Связанный список и надо использовать. Т.е. что значит -- надо ? Обычно так делают.

SashaMercury, у тебя это даже не совсем стек. Т.е. стек, но на базе массива.
А обычно делают стек на базе связного/двусвязного списка.
Хотя, конечно, и такой стек имеет право на существование, у обоих есть свои преимущества и недостатки.