使用双链表进行堆栈模拟

Question

我正在尝试创建一个模拟堆栈的程序。的要求是：

被叫节点结构
命名的整数数据
相同类型节点命名下和以前
空隙推（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

做这样的...这是满足你的要求......

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 2

你最好保存链表的头部，那么你的push_front/pop_front操作会简单得多。

Answer 3

你或许应该检查是否CUR为NULL你之前取消对它的引用在该行

cur->prev = NULL; 

而且我觉得在某处你的推送功能，你应该做一个新的节点。真正让你需要做的是这样一个新的节点：

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

这实际上在堆上创建空间，你把你的新节点。注意我推到堆栈的开头，所以你不必搜索整个事情。不管怎样，malloc行都是一样的。

Answer 4

您只需要一个单链表，并且需要为其分配内存。 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