Указатель настолько запутанный: стек с односвязным списком в C - PullRequest
Новая
       2

Указатель настолько запутанный: стек с односвязным списком в C

0 голосов
/ 11 декабря 2018

Я учащийся, реализующий стек с односвязным списком, использующим C, следуя книге под названием Основы структур данных в C .

Проблема в том, что я надеюсь, что результат этого кода будет<5,3> и <9,6> НО консоль показывает только <5,3> и <9,3>.

На самом деле, я не уверен, является ли указатель, который я использую,источник проблемы.

Может кто-нибудь объяснить мне, почему я получаю этот результат?

Полный код ниже: 

typedef struct {
int edge[1]; //edge array for saving 2 node's data
} element;

typedef struct stack *stackPointer;
typedef struct stack {
element data;
stackPointer link;
} stack;
stackPointer top[MAX_STACKS];

void initStack();
void push(int i, element item);
element pop(int i);

int top_counter = -1;

int main()
{
    int x, y;

    initStack();

    element *data = malloc(sizeof(element));


    top_counter++;
    data->edge[0] = 9;
    data->edge[1] = 6;

    push(top_counter, *data);


    top_counter++;
    data->edge[0] = 5;
    data->edge[1] = 3;

    push(top_counter, *data);

    *data = pop(top_counter);
    x = data->edge[0];
    y = data->edge[1];
    printf("<%d,%d>\n", x, y);
    top_counter--;

    *data = pop(top_counter);
    x = data->edge[0];
    y = data->edge[1];
    printf("<%d,%d>\n", x, y);
    top_counter--;

    // result of this code
    // <5, 3>
    // <9, 3>
    // WHY?!?!?!?!??!

}


void initStack() {
    for (int i = 0; i < MAX_STACKS; i++) {
        top[i] = NULL;
    }

}

void push(int i, element item) {
    // push item to top[i]
    stackPointer temp;
    temp = (stackPointer)malloc(sizeof(*temp));
    temp->data = item;
    temp->link = top[i];
    top[i] = temp;

}

element pop(int i) {
    stackPointer temp = top[i];
    element item;
    if (!temp) printf("\nStack Empty\n");
    item = temp->data;
    top[i] = temp->link;
    free(temp);
    return item;
}

Ответы [ 2 ]

0 голосов
/ 11 декабря 2018

Как отметил Jaybird в комментарии к вопросу, проблема заключалась в том, что тип элемента содержал только одно целое, а не два.

Однако этот код слишком сложен для примера, потому что он не делаетреализовать один стек, но MAX_STACKS стеки.Вот почему код выглядит так странно, а не то, что вы, вероятно, видите в реальном коде.

Рассмотрим следующий контрпример: 

#include <stdlib.h>
#include <stdio.h>

struct node {
    struct node *next;
    int          data[2];
};

struct node *new_node(const int data0, const int data1)
{
    struct node *n;

    n = malloc(sizeof *n);
    if (!n) {
        fprintf(stderr, "new_node(): Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    n->next = NULL;
    n->data[0] = data0;
    n->data[1] = data1;

    return n;
}

void free_node(struct node *n)
{
    if (n) {
        /* Poison the node, so we can more easily
           detect use-after-free bugs. */
        n->next    = NULL;
        n->data[0] = -1;
        n->data[1] = -1;

        free(n);
    }
}

Чтобы подтолкнуть (добавить) один узел ксвязанный список, 

void push_node(struct node **listptr, struct node *n)
{
    if (!listptr) {
        fprintf(stderr, "push_node(): No linked list (listptr is NULL).\n");
        exit(EXIT_FAILURE);
    } else
    if (!n) {
        fprintf(stderr, "push_node(): No node to push (n is NULL).\n");
        exit(EXIT_FAILURE);
    }

    n->next = *listptr;
    *listptr = n;
}

Чтобы извлечь первый узел из связанного списка, 

struct node *pop_node(struct node **listptr)
{
    if (!listptr) {
        fprintf(stderr, "pop_node(): No linked list specified (listptr is NULL).\n");
        exit(EXIT_FAILURE);

    } else
    if (!*listptr) {
        /* Linked list is empty, return NULL. */
        return NULL;

    } else {
        struct node *n;

        n = *listptr;
        *listptr = n->next;
        n->next = NULL;

        return n;
    }
}

Для отладки мы можем использовать подпрограмму, которая печатает содержимое стека: 

void show_list(struct node *first, FILE *out)
{
    if (out) {
        fputs("[", out);
        while (first) {
           fprintf(out, " <%d,%d>", first->data[0], first->data[1]);
           first = first->next;
        }
        fputs(" ]\n", out);
    }
}

Чтобы проверить, мы напишем маленькую main(): 

int main(void)
{
    struct node *odds = NULL;
    struct node *evens = NULL;
    struct node *n;

    /* Push <1,3> and <5,7> to odds. */
    push_node(&odds, new_node(1, 3));
    push_node(&odds, new_node(5, 7));

    /* Push <2,2>, <4,2>, and <6,8> to evens. */
    push_node(&evens, new_node(2,2));
    push_node(&evens, new_node(4,2));
    push_node(&evens, new_node(6,8));

    /* Push <3,3> to odds. */
    push_node(&odds, new_node(3,3));

    /* Show the two stacks. */
    printf("odds stack after the pushes: ");
    show_list(odds, stdout);
    printf("evens stack after the pushes: ");
    show_list(evens, stdout);

    /* Pop each node off from the odds stack,
       and push them into the evens stack. */
    while ((n = pop_node(&odds)))
        push_node(&evens, n);

    /* Show the stacks again. */
    printf("odds stack after the while loop: ");
    show_list(odds, stdout);
    printf("evens stack after the while loop: ");
    show_list(evens, stdout);

    /* Pop each node from evens stack, and display it. */
    while ((n = pop_node(&evens))) {
        printf("<%d, %d>\n", n->data[0], n->data[1]);
        free_node(n);
    }

    printf("All done.\n");
    return EXIT_SUCCESS;
}

Если вы скомпилируете и запустите вышеприведенное, он выведет 

odds stack after the pushes: [ <3,3> <5,7> <1,3> ]
evens stack after the pushes: [ <6,8> <4,2> <2,2> ]
odds stack after the while loop: [ ]
evens stack after the while loop: [ <1,3> <5,7> <3,3> <6,8> <4,2> <2,2> ]
<1, 3>
<5, 7>
<3, 3>
<6, 8>
<4, 2>
<2, 2>
All done.

Пара синтаксическихдетали:

  • Операции push и pop изменяют указатель на первый узел в списке.Если вы передадите только сам указатель, эта модификация не будет видна вызывающей стороне.Вот почему указатель на указатель **listptr используется в качестве параметра, а *listptr используется в функции при обращении к указателю на первый узел в списке.

  • if (out) эквивалентно if (out != NULL), когда out является указателем.

  • while ((n = pop_node(&odds))) { ... } эквивалентно while ((n = pop_node(&odds)) != NULL) { ... }.Другой способ записать цикл - это 

        while (1) {

        n = pop_node(&odds);
        if (n == NULL)
            break;

        ...

    }

    , т.е. сначала присваивается n, а затем сравнивается с NULL.Это очень распространенная форма сокращения.

    • if (!listptr) эквивалентно if (listptr == NULL).

    Один из способов запомнить это различие заключается в чтении оператора not,!, вслух как "нет" или "нет".Таким образом, if (!listptr) читается как «если нет listptr».

Рассмотрим, что происходит, когда вы вытаскиваете предметы из одного стека и переносите их в другой.Их порядок меняется на противоположный.Понимание того, как это работает с тремя стеками, делает Ханойскую башню / Башню Брахмы / Башню Лукаса такой интересной.

В этом примерене является «стековым» абстрактным типом данных вообщеДескриптор стека для операций push и pop - это просто указатель на указатель на первый элемент.Если вы хотите реализовать стеки и очереди, используя один и тот же дескриптор для связанного списка, вы можете использовать 

typedef struct {
    struct node *newest; /* or first in list */
    struct node *oldest; /* or last in list */
} storq;
#define  STORQ_INIT  { NULL, NULL }

, чтобы можно было объявить пустой стек или очередь, используя 

storq  stuff = STORQ_INIT;

безнеобходимость вызывать некоторую функцию storq_init(&stuff);, чтобы инициализировать ее в известное (пустое) состояние, готовое к использованию.

Вышеприведенное не является идеально симметричным, поскольку допускает постоянное время ( O (1) сложность времени) операции storq_push() (push или prepend), storq_pop() и storq_unshift() (как push, но на противоположном конце очереди / стека), тогда как storq_shift() (как pop, но напротивоположный конец очереди / стека) будет «медленным» ( O ( N ) временным усложнением, где N - количество узлов в очереди /стек).

Для полноты, операции, пропускающие проверки ошибок: 

void storq_push(storq *sq, struct node *n)
{
    n->next = sq->newest;
    sq->newest = n;
    if (!sq->oldest)
        sq->oldest = n;
}

void storq_unshift(storq *sq, struct node *n)
{
    n->next = NULL;
    if (sq->oldest) {
        sq->oldest->next = n;
    } else {
        sq->newest = n;
        sq->oldest = n;
    }
}

struct node *storq_pop(storq *sq)
{
    if (sq->newest) {
        struct node *n;

        n = sq->newest;
        if (n->next) {
            sq->newest = n->next;
        } else {
            sq->newest = NULL;
            sq->oldest = NULL;
        }

        n->next = NULL;

        return n;

    } else {
        return NULL;
    }
}

Чтобы понять, как это работает, я рекомендую рисовать диаграммы, где каждый узел представлен овалом, а стрелка представляетгде член next указывает на.Дескриптор storq представляет собой поле с двумя стрелками, одна из которых указывает на первый / самый новый элемент в списке, а другая - на последний / самый старый элемент в списке.

Для каждой операции (push,unshift, pop), нужно рассмотреть три случая: когда список пуст, когда в списке только один элемент и когда в списке много элементов.Если вы проследите все девять, вы поймете, как работают вышеуказанные функции, и почему они делают то, что делают.

0 голосов
/ 11 декабря 2018

Измените int edge[1] на int edge[2], и оно должно работать.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...