0

我明天有一个作业，并被要求制作一个动态（可调整大小）堆栈，以节省字符。

这件事一直让我发疯，整天都在做这件事。我使用标准库完成了它，它完成了。但似乎无法弄清楚如何在没有 malloc 的情况下分配内存 .. 帮助将不胜感激。这些是我使用过的一些代码片段（使用 stdlib）：

    struct STACK
    {
        int size;
        int capacity;
        char *memory;
        int folder_number;
    };
typedef struct STACK stack;

我的主要开始是这样的：

int main()
{
    stack mystack;
    stack_init(&mystack);

初始化栈函数：

void stack_init(stack *s)
{
    s->size=1;
    s->capacity=INITIAL_CAPACITY;
    s->memory=malloc(s->capacity);
    s->memory[0]='\0';
    s->folder_number=1;
}

我的程序有各种功能，当我将新字符插入堆栈时，我检查是否已达到最大容量，如果是，我调用以下函数：

void double_memory(stack* s)
{
    char *tmp = malloc((s->capacity)*2);

    for (int i=0; i<(s->capacity); i++)
        tmp[i]=s->memory[i];
    free(s->memory);
    s->capacity *= 2;
    s->memory=tmp;
}

现在，我已经连续尝试了至少 6 个小时，试图找出其他方法（不使用 stdlib.h），在谷歌上搜索了很多，但没有成功。任何帮助或建议都是真的！赞赏。

非常感谢您提前。

编辑：我大约 2 个月前开始上大学，我不了解平台..等等，我们学到的最后两件事是指针，以及关于 malloc 的小信息，b4 我们只是了解了函数 hhh ......，在此之前，非常基本的编码..

4

2 回答 2

2

使用文件：

#include <stdio.h>

struct stack {
        FILE * fp;
        } stack = {NULL} ;
#define ZENAME "zestack"

void stack_init (struct stack *sp);
void stack_exit (struct stack *sp);
void stack_push (struct stack *sp, int ch);
int stack_pop (struct stack *sp);

void stack_init (struct stack *sp)
{
if (sp->fp) fclose(sp->fp);
sp->fp = fopen(ZENAME , "wb+" );
if (!sp->fp) fprintf(stderr, "Fopen(%s) failed\n", ZENAME  );
}

void stack_exit (struct stack *sp)
{
if (sp->fp) fclose(sp->fp);
sp->fp = NULL;
}

void stack_push (struct stack *sp, int ch)
{
fputc(ch, sp->fp);
}

int stack_pop (struct stack *sp)
{
int ch;
long int oldpos, newpos;

if (!sp->fp) return -1;
oldpos = fseek(sp->fp, -1, SEEK_CUR);
if (oldpos < 0) { stack_exit (sp); return EOF; }

ch = fgetc(sp->fp);
newpos = fseek(sp->fp, -1, SEEK_CUR);
fprintf(stderr, "Oldpos = %ld Newpos = %ld\n", oldpos, newpos );
return ch;
}
int main(void)
{

int ch;
stack_init ( & stack);
stack_push ( & stack, '1');
stack_push ( & stack, '2');
stack_push ( & stack, '3');
stack_push ( & stack, '4');

while(1) {

        ch = stack_pop( &stack);
        fprintf(stdout, "Pop = '%c' (0x%x)\n" , ch, (unsigned) ch) ;
        if (ch < 0) break;
        }
return 0;
}
于 2012-12-29T19:30:22.050 回答
1

malloc在大多数符合 POSIX 的平台上，只需在后台使用mmap匿名映射......因此您可以调用该函数，而不是使用该MAP_ANONYMOUS标志将内存分配到内存池中以供您的堆栈实现使用。这是 LINUX 手册页的链接：http mmap: //www.kernel.org/doc/man-pages/online/pages/man2/mmap.2.html

为了有效地使用您分配的内存池，我建议设置某种类型的简单链表内存管理器......换句话说，您想调用mmap一次来分配一大块内存，然后使用您自己的用户定义malloc并free调用管理内存池。

更新：根据您的评论，您现在说您不能使用任何外部库。因此，您唯一的其他选择是为您的内存池指定一个静态数组，因为在运行时从堆中动态分配内存需要操作系统的干预，而这在没有系统调用的情况下无法完成。

这是一个您可以使用的简单链表内存管理器系统（注意：我还没有调试它，但因为它是家庭作业，那是你的工作:-)

static unsigned char heap[MEMORY_POOL_SIZE];

typedef struct memory_block
{
    unsigned long size_bytes;
    unsigned char block[];
} memory_block;

typedef struct free_block
{
    unsigned long size_bytes;
    struct free_block* next;
} free_block;

//initialize our memory pool free-store
static char free_list_initialized = 0;
static free_block* free_list_head = NULL;

void* malloc(unsigned long size_bytes)
{
    //initialize the free-store if it's never been used before
    if (!free_list_initialized)
    {
        free_list_head = (free_block*)&heap[0];
        free_list_head->size_bytes = MEMORY_POOL_SIZE - sizeof(memory_block);
        free_list_head->next = NULL;
        free_list_initialized = 1;
    }

    //search the free-list for a memory block that is at least size_bytes
    free_block* current = free_list_head;
    free_block* prev = NULL;

    while (current != NULL)
    {
        if (current->size_bytes >= (size_bytes + sizeof(free_block)))
            break;

        prev = current;
        current = current->next;
    }

    //did we reach the end of the list without finding anything?
    if (current == NULL)
        return NULL;  //out-of-memory!

    memory_block* temp = NULL;

    //trim the block of memory if the one we found is larger than the requested size
    if (current->size_bytes > (size_bytes + sizeof(free_block)))
    {
        temp = (memory_block*)current;
        current = (free_block*)((unsigned char*)current + size_bytes + sizeof(memory_block));

        current->size_bytes = current->size_bytes - (size_bytes + sizeof(memory_block));
        temp->size_bytes = size_bytes;

        if (prev != NULL)
            prev->next = current;
    }
    else
    {
        prev->next = current->next;
        temp = (memory_block*)current;
    }

    return (void*)&temp->block;
}

void free(void* ptr)
{
    free_block* temp = (free_block*)((unsigned char*)ptr - sizeof(unsigned long));
    temp->next = free_list_head;
    free_list_head = temp;

    return;
}
于 2012-12-29T18:46:59.530 回答