0

明日の宿題があり、文字を節約する動的な（サイズ変更可能な）スタックを作成するように求められます。

このことは私を夢中にさせ、一日中それを続けてきました。stdlibを使用して実行しました。しかし、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;
}

私は自分のプログラムにあらゆる種類の関数を持っており、スタックに新しいcharを挿入するときに、最大容量に達しているかどうかを確認します。最大容量に達している場合は、次の関数を呼び出します。

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か月前に大学に入学しましたが、プラットフォームなどについてはわかりません。最後に学んだ2つのことは、ポインターと、関数について単に学んだmalloc、b4に関する小さな情報です。その前に、VERRYの基本的なコーディング。

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 マンページへのリンクは次のmmapとおりです。 http://www.kernel.org/doc/man-pages/online/pages/man2/mmap.2.html

割り当てられたメモリ プールを効率的に使用するために、単純なリンク リスト メモリ マネージャをセットアップすることをお勧めします。つまり、mmap一度呼び出して大量のメモリを割り当ててから、独自のユーザー定義のmallocおよびfreeメモリプールを管理するための呼び出し。

更新:あなたのコメントから、外部ライブラリを使用できないと言っています。したがって、実行時にヒープからメモリを動的に割り当てるにはOSからの介入が必要であり、システムコールなしでは実行できないため、他の唯一のオプションはメモリプールに静的配列を指定することです。

これは、使用できる単純なリンクリストメモリマネージャーシステムです（注：デバッグはしていませんが、宿題なので、それはあなたの仕事です:-)

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 に答える