我的主程序在用户输入要推送的号码后卡住了。
我正在尝试创建一个模拟堆栈的程序。要求如下:
一个名为node的结构
一个名为data的整数
两个相同类型的节点指针命名为next和previous
Void push(int)原型Int pop() prototype
#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 integern"
"2) Pop integern"
"3) Exitn");
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.nn");
}
else {
printf("Integer %d is popped.nn", number);
}
}
printf("Enter your choice: n"
"1) Push integern"
"2) Pop integern"
"3) Exitn");
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;
}
}
这个看起来可以吗?
这样做…这是符合您的要求的…
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;
}
}
在
行中取消对它的引用之前，您可能应该检查cur是否为NULLcur->prev = NULL;
我也认为在你的推函数的某个地方，你应该做一个新的节点。要实际创建一个新节点，您需要执行以下操作:
struct node * cur = malloc(sizeof(struct node));
cur->data = number;
cur->prev = NULL;
cur->next = first;
first = cur;
这实际上会在堆上为您创建放置新节点的空间。注意，我把它压到堆栈的开头，所以你不必遍历整个堆栈。
您最好保存链表的头部，然后您的push_front/pop_front操作将会简单得多。
您只需要一个单链表，并且您需要为它分配内存。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
#In Python
class Node():
"""Defining a Node for Doubly linked List"""
def __init__(self,value):
self.value=value
self.prev_node=None
self.next_node=None
class DoubleLinkedList():
""" A class and object Pointing to Doubly linked List"""
def __init__(self):
self.head=None
#Adding Element in Doubly linked List in the tail of head
def add_element(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while crnt_node.next_node is not None:
crnt_node=crnt_node.next_node
node.prev_node=crnt_node
crnt_node.next_node=node
#Adding a New Head in Doubly linked List
def add_head_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while crnt_node.next_node is not None:
break
crnt_node.prev_node=node
vnode=crnt_node
node.next_node=vnode
crnt_node=node
self.head=crnt_node
#Adding a New tail in Doubly linked List
def add_tail_node(self,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while True:
if crnt_node.next_node is None:
break
crnt_node=crnt_node.next_node
node.prev_node=crnt_node
crnt_node.next_node=node
#Adding a New node in between in Doubly linked List
def add_bw_node(self,aftr_node_value,value):
node=Node(value)
if self.head is None:
self.head=node
return
crnt_node=self.head
while True:
if crnt_node.value==aftr_node_value:
half_node=crnt_node.next_node
break
crnt_node=crnt_node.next_node
node.prev_node=crnt_node
half_node.prev_node=node
node.next_node=half_node
crnt_node.next_node=node
#Deleting a Head node in Doubly linked List
def del_head_node(self):
if self.head is None:
print('Empty Double Linked List')
return
crnt_node=self.head
while True:
if crnt_node.next_node is not None:
half_node=crnt_node.next_node
break
crnt_node=crnt_node.next_node
#crnt_node.prev_node=None
crnt_node.next_node=half_node
half_node.prev_node=None
self.head=crnt_node.next_node
#Deleting a tail node in Doubly linked List
def del_tail_node(self):
if self.head is None:
print('Empty Double Linked List')
return
crnt_node=self.head
while True:
if crnt_node.next_node.next_node is None:
crnt_node.next_node=None
break
crnt_node=crnt_node.next_node
#Deleting a in between node in Doubly linked List
def del_inbw_node(self,inbw_node_value):
if self.head is None:
print('Empty Double Linked List')
return
crnt_node=self.head
while True:
if crnt_node.next_node.value==inbw_node_value:
half_node=crnt_node.next_node.next_node
break
crnt_node=crnt_node.next_node
half_node.prev_node=crnt_node
crnt_node.next_node=half_node
#Traversing node to node in Doubly linked List
def print_dllist(self):
crnt_node=self.head
while True:
print(crnt_node.value,end='->')
if crnt_node.next_node is None:
break
crnt_node=crnt_node.next_node
print('None')
#Traversing previous nodes in Doubly linked List
def print_previous_node(self):
crnt_node=self.head
while crnt_node.next_node is not None:
if crnt_node.prev_node is None:
print(f'{crnt_node.prev_node}<-',end='')
else:
print(f'{crnt_node.prev_node.value}<-',end='')
crnt_node=crnt_node.next_node
print(crnt_node.prev_node.value)
dllist=DoubleLinkedList()
dllist.add_element(10)
dllist.print_dllist()
dllist.add_element(20)
dllist.print_dllist()
dllist.add_element(30)
dllist.print_dllist()
dllist.add_element(40)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_head_node(5)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_tail_node(50)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_bw_node(40,45)
dllist.print_dllist()
dllist.del_head_node()
dllist.print_dllist()
#dllist.print_previous_node()
dllist.del_tail_node()
dllist.print_dllist()
#dllist.print_previous_node()
dllist.del_inbw_node(30)
dllist.print_dllist()
dllist.print_previous_node()