【轉載】動態空間分配

來源

動態空間分配

所謂動態空間分配指的是,在執行期間由程式向作業系統或程式庫要求後才分配的空間,這塊記憶體區域稱為Heap(堆積)。C語言的動態空間分配主要透過malloc和free兩函數來處理。這兩個函數的宣告如下:

void *malloc(size_t size);
void free(void *ptr);

透過malloc()所分配出來的空間必須由使用者呼叫free()才能歸還給系統。初學者常犯的錯誤之一,就是忘了用free()歸還空間,這會造成程 式佔用太多記憶體,此現象稱為memory leakage。相反的,如果空間已用free()歸還了,卻還試著去使用那塊記憶體,則會發生Segmentation Fault (core dumped)的錯誤。 Linked Stack

typedef struct items {
    int data;
    struct items *link;
} ITEM;

typedef struct stack {
    ITEM *top;
} STACK;

void initStack(STACK *s) {
    s->top = NULL;
}

void pushStack(STACK *s, int y) {
    ITEM *x; // x will point to the new ITEM
    x = (ITEM *) malloc(sizeof(ITEM)); // allocate memory for the new ITEM
    x->data = y; // store data
    x->link = s->top; // x->link points to where s->top points
    s->top = x; // stack's top points to x
}

int popStack(STACK *s) {
    ITEM * x = s->top;
 int d = x->data;
    s->top = s->top->link;
    free(x);
    return d;
}
int stackIsEmpty(STACK *s) {
    return s->top == NULL;
}
void main() {
    STACK s;
    int i;
    initStack(&s);
    for (i = 1; i < 10; i++) {
        pushStack(&s, i);
    }
    while (!stackIsEmpty(&s)) {
        printf("%d\n", popStack(&s));
    }
}

Linked Queue

typedef struct items {
    int data;
    struct items *link; // points to next element
} ITEM;

typedef struct queue {
    int size;
    ITEM *front, *rear;
} QUEUE;

void initQueue(QUEUE *q) {
    q->size = 0;
    q->front = q->rear = NULL;
}
int queueIsEmpty(QUEUE *q) {
    return q->front == NULL;
}
int queueLength(QUEUE *q) {
    return q->size;
}
void addQueue(QUEUE *q, int y) {
    ITEM * x = (ITEM *) malloc(sizeof(ITEM));
    x->data = y;
 x->link = NULL;
    if (q->front == NULL)
        q->front = x;
    else
        q->rear->link = x;
    q->rear = x;
    q->size++;
}
int deleteQueue(QUEUE *q) {
    ITEM * x = q->front;
    int rel = x->data;
    q->front = x->link;
    if (q->front == NULL)
        q->rear = NULL;
    q->size--;
    free(x);
    return rel;
}
void main() {
    QUEUE q;
    int i;
    initQueue(&q);
    for (i = 1; i < 10; i++) {
        addQueue(&q, i);
    }
    while (!queueIsEmpty(&q)) {
        printf("%d\n", deleteQueue(&q));
    }
}