Моделирование стека с двойным списком

Question

Я пытаюсь создать программу, которая имитирует стек. Требования:

структура с именем узел
целое число с именем данные
два указателя одного типа узел с именем следующий и предыдущий
void push (int) прототип int pop () прототип

Я создал свою функцию push () следующим образом:

#include <stdio.h>

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

struct node *first = NULL;
void push(int number);
int pop();

int main() {
int choice = 0, number;

printf("Enter your choice: \n"
    "1) Push integer\n"
    "2) Pop integer\n"
    "3) Exit\n");
scanf("%d", &choice);

while (choice != 3) {
    if (choice == 1) {
        printf("Enter Integer: ");
        scanf("%d", &number);
        printf("\n");
        push(number);
    }
    if (choice == 2) {
        number = pop();
        if (number == -1) {
            printf("Error: Stack empty.\n\n");
        }
        else {
            printf("Integer %d is popped.\n\n", number);
        }
    }

    printf("Enter your choice: \n"
        "1) Push integer\n"
        "2) Pop integer\n"
        "3) Exit\n");
    scanf("%d", &choice);
}
}


void push(int number)
{
 struct node *cur;
 cur = first;

 if (cur == NULL) {
     cur = (struct node *) malloc(sizeof(struct node));
     cur->data = number;
     cur->next = NULL;
     cur->prev = cur;
     first = cur;
     return;
 }

 if (cur != NULL) {
     while (cur->next != NULL) {
         cur = cur->next;
     }
     (cur->next) = (struct node *) malloc(sizeof(struct node));
     (cur->next)->data = number;
     (cur->next)->next = NULL;
     (cur->next)->prev = cur;
 }
}    

int pop() {
int number;

if (first == NULL) {
    return -1;
}
else {
    struct node *cur, *prev;
    cur = first;
    prev = NULL;

    while (cur->next != NULL) {
        prev = cur;
        cur = cur->next;
    }

    number = cur->data;

    if (prev == NULL) {
        first = NULL;
    }
    else {
        prev->next = cur->next;
    }

    return number;
}
}

Это выглядит хорошо? Моя основная программа зависает после того, как пользователь вводит номер для нажатия.

Answer 1

Вам, вероятно, следует проверить, имеет ли cur значение NULL, прежде чем разыменовывать его в строке

cur->prev = NULL;

Также я думаю, что где-то в вашей функции push вы должны создать новый узел. Чтобы создать новый узел, вам нужно сделать что-то вроде:

struct node * cur = malloc(sizeof(struct node));
cur->data = number;
cur->prev = NULL;
cur->next = first;
first = cur;

Это фактически создаст пространство в куче для вас, чтобы вы могли разместить новый узел. Заметьте, я выдвинул начало стека, так что вам не нужно искать все это. Линия malloc будет одинаковой независимо.

Answer 2

Делай как это ... Это соответствует твоим требованиям ...

 void push(int number)
 {
    struct node *cur;
    cur = first;
    if(cur == NULL)  //if it is first node
     {
    cur = (struct node*) malloc(sizeof(struct node));
    cur->data = number;
    cur->next = NULL;
    cur->prev = cur;
    first = cur;
    return;
     }

    //note here Iam running the loop till cur->next!=NULL and not till cur != NULL. cur!=NULL makes the cur to act as head of a yet another new Linked List.

    while (cur->next != NULL)
    cur = cur->next;

    (cur->next) = (struct node*) malloc(sizeof(struct node));
    (cur->next)->data = number;
    (cur->next)->next = NULL;
    (cur->next)->prev = cur;
}    

Или вы хотите сделать свою реализацию .... Тогда ...

void push(int number)
{
 struct node *cur;
 cur = first;

 if (cur != NULL) {
     while (cur->next != NULL) {
         cur = cur->next;
     }
     (cur->next) = (struct node *) malloc(sizeof(struct node));
     (cur->next)->data = number;
     (cur->next)->next = NULL;
     (cur->next)->prev = cur;
 }
 else {/*Take action if it is a first node (if cur is NULL)*/}
}  

Факты о вашем старом коде ..

void push(int number) {
struct node *cur;
cur = first;

if (cur != NULL) {
    cur->prev = NULL;//no need. cur->prev must be NULL,already. since cur points to first.
                     //dont change cur->prev=someAddress it will change your head node
}


while (cur != NULL) {//flaw: run till cur->next!= NULL.Dont make cur NULL.
        cur->prev = cur; //during iteration to last element no need of prev.
        cur = cur->next;
    }

//Do memory allocation,for cur->next and not for cur after this loop

cur->data = number; // change this to cur->next->data = number.
//initialize cur->next->prev,cur->next->next


if (cur->prev == NULL) {
    first = cur;
}
//I can get your idea. But if you want to do this way,
//you have to use additional pointer like temp.

else {
    cur->prev->next = cur;
}

}

Answer 3

Вам нужен только односвязный список, и вам нужно выделить для него память. struct node *node; выделяет место только для указателя на узел , но не для фактического узла. Вот полное приложение, которое выполняет некоторые основные операции со стеком:

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

struct node {
  struct node *next;
  int data;
};

struct node *push(struct node *head, int num) {
  struct node *newNode = malloc(sizeof(*head));
  newNode->next = head;
  newNode->data = num;
  return newNode;
}

int pop(struct node **headPtr) {
  struct node *top = *headPtr;
  int data = top->data;
  *headPtr = top->next;
  free(top);
  return data;
}


int main(int argc, char **argv) {
  struct node *head = NULL;
  int i;
  for (i = 1; i < argc; i++) {
    head = push(head, atoi(argv[i]));
  }

  while (head) {
    int x = pop(&head);
    printf("%d ", x);
  }

  return 0;
}

$ make tmp
cc     tmp.c   -o tmp

$ ./tmp 1 4 9
9 4 1 

Answer 4

Вам лучше сохранить заголовок связанного списка, тогда операция push_front / pop_front будет намного проще.