Учитывая ваши структуры данных, представляющие узел в стеке, и собственно сам стек:
typedef struct node {
void *dataptr;
struct node *link;
} NODE;
typedef struct {
int count;
NODE *top;
} STACK;
вы бы инициализировать стек следующим образом:
STACK myStack;
myStack.count = 0;
myStack.top = NULL;
Это в основном дает пустой стек. Я собираюсь использовать top
, чтобы решить, пуст ли пуст - вы можете использовать либо count
, либо top
(как 0
или NULL
соответственно), чтобы выполнить эту работу, но это хорошая идея, чтобы выбрать ее и придерживаться ее в случае, если вы когда-либо писали некоторые ошибки кода в будущем, где кэшируется подсчет и фактический отсчет выйти из шага :-)
протолкнуть узел в стек, это простая операция:
- выделить новый узел и установить полезная нагрузка (1).
- укажите ссылку нового узла на текущую головку.
- направьте головку на новый узел (3).
- увеличить счетчик (4).
Следующий код показывает, как вы можете это сделать:
/* 1 */ NODE *newNode = malloc (sizeof (NODE)); // should check for failure.
newNode->dataptr = NULL;
/* 2 */ newNode->link = myStack.top;
/* 3 */ myStack.top = newNode;
/* 4 */ myStack.count++;
Это будет толкать на любой пустой стек или населенной один. Краевой случай пустого стека увидит, что newNode.link
установлен на NULL
, затем myStack.top
установлен на newNode
, что является правильным поведением.
Чтобы выскочить узел из стека:
- сохранить нынешний глава (1).
- Если текущая головка не равна NULL, продвиньте головку к ее ссылке (и уменьшите счет).
- вернуть сохраненную текущую головку (3).
, что в переводе с кодом, является:
/* 1 */ NODE *popNode = myStack.top;
/* 2 */ if (myStack.top != NULL) {
myStack.top = myStack.top->link;
myStack.count--;
}
/* 3 */ return popNode;
Это возвращает либо адрес хлопнутого узла или NULL
, если стек был пуст.
Весь набор операций может быть инкапсулирован следующим образом. Надеемся, что комментарии сделают это самоочевидным в сочетании с комментариями выше, но не стесняйтесь поднимать любые проблемы, и я буду обращаться к ним с помощью редактирования.
// Error codes (probably should be enums).
#define STACK_ERR_OKAY 0
#define STACK_ERR_NOTEMPTY 1
#define STACK_ERR_NOPAYLOAD 2
#define STACK_ERR_NOMEMORY 3
// Structures.
typedef struct sNode {
void *data; // Payload pointer.
struct sNode *next; // Link to next node.
} tNode;
typedef struct {
int count; // Count for fast sizing.
NODE *top; // First node.
} tStack;
// Make a new stack returning its pointer or NULL on failure.
tStack *stackNew (void) {
tStack stack = malloc (sizeof (tStack));
if (stack != NULL) {
stack->count = 0;
stack->top = NULL;
}
return stack;
}
// Delete a current stack, must be empty first.
int stackDel (tStack *stack) {
if (stack->top != NULL)
return STACK_ERR_NOT_EMPTY;
free (stack);
return STACK_ERR_OK;
}
// Push a pointer payload (no NULLs allowed) onto the stack.
int stackPush (tStack *stack, void *payload) {
if (payload == NULL)
return STACK_ERR_NOPAYLOAD;
tNode *node = malloc (sizeof (tNode));
if (node == NULL)
return STACK_ERR_NOMEMORY;
node->data = payload;
node->next = stack->top;
stack->top = node;
stack->count++;
return STACK_ERR_OK;
}
// Pop a pointer payload from the stack. Returns NULL if stack was empty.
int stackPop (tStack *stack) {
tNode *node = stack->top;
if (node == NULL) {
return NULL;
stack->top = node->next;
stack->count--;
return node->data;
}
// Get stack size.
int stackSize (tStack *stack) {
return stack->count;
}
Причина я настаивал на том, что стек должен быть пуст перед удалением потому, что код не знает точно, что полезная нагрузка.Это может быть простым указатель на блок памяти (мелкий), в этом случае вы могли бы просто использовать:
void stackDel (tStack *stack) {
tNode *node = stackPop (stack);
while (node != NULL) {
free (node);
node = stackPop (stack);
}
free (stack);
}
, но, если это указатель на память держит другие указатели на память, это более проблематично автоматически освободить (это, вероятно, лучше всего сделать в качестве обратного вызова вызывающему API, поскольку это будет единственный зверь, который точно знал, как правильно освободить память). Намного проще сделать это предварительным условием для вызывающего абонента.
Можете ли вы разместить код? –
Для таких стеков: 'typedef struct node { void dataptr; struct node * link; } STRUCT_NODE typedef struct { int count; STACK_NODE * сверху; } STACK; ' Как изменить ссылку, чтобы указать на новые данные, наложенные на стек. Также я не знаю – shinjuo
Также не знаю, как поместить вещи в код? Может кто-то сказать мне, как это сделать. Извините, что я очень новичок на этом сайте – shinjuo