Refer to UNSW COMP9024
Base conversion
typedef long STACK_ITEM_T;
void PrintInteger(STACK_ITEM_T x, int base) {
struct Stack *pStack = CreateStack();
int r;
x = (x >= 0 ? x : -x);
base = (base >= 0 ? base: -base);
printf("------------- x = %ld, base = %d -------------\n\n", (long) x, base);
// push the remainders onto the stack
do {
r = x % base;
x = x / base;
printf("push %d\n", r);
StackPush(pStack, r);
} while (x != 0);
printf("\n\nAfter popping (First In Last Out):\n\n");
PrintPrefix(base);
// output the remainders in the FILO order
while(!StackIsEmpty(pStack)) {
r = StackPop(pStack);
// see https://www.asciitable.com/
// IF-ELSE just want to output A==10, B==11, ... F==15
// LIFO is OK, Last digit put into the stack is the highest digit of other Base.
if (r <= 9) {
// 1 --> '1' (0x31, 49); ...
// 1 + 48 == 49
printf("%c", r + 48);
} else if (r <= 15) {
// 10 --> 'A' (0x41, 65); 11 --> 'B', ...
// 10 + 55 == 65
printf("%c", r + 55);
} else {
// unknown base
printf("?");
}
}
ReleaseStack(pStack);
printf("\n");
}
Week3$ make
Week3$ ./main
------------- x = 20249024, base = 10 -------------
push 4
push 2
push 0
push 9
push 4
push 2
push 0
push 2
After popping (First In Last Out):
20249024
------------- x = 20249024, base = 16 -------------
push 0
push 12
push 9
push 15
push 4
push 3
push 1
After popping (First In Last Out):
0x134F9C0
------------- x = 20249024, base = 8 -------------
push 0
push 0
push 7
push 4
push 7
push 1
push 5
push 1
push 1
After popping (First In Last Out):
0o115174700
------------- x = 20249024, base = 2 -------------
push 0
push 0
push 0
push 0
push 0
push 0
push 1
push 1
push 1
push 0
push 0
push 1
push 1
push 1
push 1
push 1
push 0
push 0
push 1
push 0
push 1
push 1
push 0
push 0
push 1
After popping (First In Last Out):
0b1001101001111100111000000
Enlarge the size
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "Stack.h"
// number of items, not in bytes
#define INITIAL_STACK_SIZE 64
// the top position when a stack is empty
#define TOP_POS_FOR_EMPTY_STACK -1
// The type defintion of our Stack
struct Stack {
// the current capacity size of a stack, in the number of items, not in bytes
long size;
// the stack top position
long top;
// pItems points to an array dynamically allocated in heap
STACK_ITEM_T *pItems;
};
// Test whether the stack is full
static int StackIsFull(struct Stack *pStack) {
return pStack->top == pStack->size - 1;
}
// Test whether the stack is empty
int StackIsEmpty(struct Stack *pStack) {
return pStack->top == TOP_POS_FOR_EMPTY_STACK;
}
// Create a stack
struct Stack *CreateStack(void) {
struct Stack *pStack;
STACK_ITEM_T *pItems;
//printf("sizeof(STACK_ITEM_T) == %ld\n", sizeof(STACK_ITEM_T));
pStack = (struct Stack *) malloc(sizeof(struct Stack));
pItems = (STACK_ITEM_T *) malloc(sizeof(STACK_ITEM_T) * INITIAL_STACK_SIZE);
assert(pStack && pItems);
pStack->size = INITIAL_STACK_SIZE;
pStack->top = TOP_POS_FOR_EMPTY_STACK;
pStack->pItems = pItems;
return pStack;
}
// Release the heap space
void ReleaseStack(struct Stack *pStack) {
if (pStack) {
free(pStack->pItems);
free(pStack);
}
}
// Push an item onto/at the top of the stack
void StackPush(struct Stack *pStack, STACK_ITEM_T item) {
if (StackIsFull(pStack)) {
// if the Stack is not enough, it would increase its size automatically
/*
Please complete the following code in Q1-Q5.
Q1. call malloc() to allocate enough bytes of heap memory,
and save the return value in a pointer variable named as newItems
Q2. call memcpy() to copy the items pointed to by pStack->pItems
to the heap memory pointed to by newItems
For help, please type 'man memcpy' in the command line.
$ man memcpy
Q3. call free() to release the unused heap memory
Q4. double the capacity size of the stack
Q5. let pStack->pItems point to the heap space allocated in Q1
You need to echo these questions in our weekly Quiz.
Our tutors will NOT answer these questions in the tutorial.
To test the code you have completed, you can set INITIAL_STACK_SIZE to be 2 (line 8 in Stack.c)
*/
// Double the capacity of the stack
// Q1. ___________________
STACK_ITEM_T *newItems = (STACK_ITEM_T *) malloc(pStack->size * 2 * sizeof(STACK_ITEM_T));
// Q2. ___________________
memcpy(newIte)
// Q3. ___________________
// Q4. ___________________
// Q5. ___________________
// Q1. Allocate memory for the new stack items array with double the size
long newSize = pStack->size * 2; // Double the current size
STACK_ITEM_T *newItems = (STACK_ITEM_T *)malloc(sizeof(STACK_ITEM_T) * newSize);
assert(newItems); // Ensure memory allocation was successful
// Q2. Copy the old items to the new items array
// memcpy would copy the second parameter context into the parameter
memcpy(newItems, pStack->pItems, sizeof(STACK_ITEM_T) * pStack->size);
// Q3. Free the old items array
free(pStack->pItems);
// Q4. Update the stack's size to the new size
pStack->size *=2;
// Q5. Point to the new items array
pStack->pItems = newItems;
}
// Now the stack is not full. Let us do the push operation.
pStack->top++;
pStack->pItems[pStack->top] = item;
}
// Pop the top item from the stack
STACK_ITEM_T StackPop(struct Stack *pStack) {
assert(!StackIsEmpty(pStack));
STACK_ITEM_T item = pStack->pItems[pStack->top];
pStack->top--;
return item;
}
// Peek the top item without popping
STACK_ITEM_T StackPeek(struct Stack *pStack) {
assert(!StackIsEmpty(pStack));
STACK_ITEM_T item = pStack->pItems[pStack->top];
return item;
}
Welcome to point out the mistakes and faults!