Join 149,556 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,613 people online right now. Registration is fast and FREE... Join Now!
K, so I am doing a programming project, requiring multiple functions and implementations. I've made push, pop, and top functions for this, but I need some others, firstly printStack as the topic says. I'm guessing the other functions will be constructed similar to it. I am hoping there is a simpler way to do printStack other than to make a secondary list and then to print off that. Here's the code for my printstack function, which doesn't work:
CODE
int PrintStack(Node *head, Node **head){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. Node *tail = (Node*)malloc(sizeof(Node)); // head for second list called tail. while(*head != NULL){ *head->ptr = node; // Head's pointed-at node (second node) is now the first thing of this second list node->ptr = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. Node *temp = *head; // make a temp node and it equals head now. *head = temp->ptr; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done being used.
Here's the rest of my junk. I look forward to a reply.
typedef struct Node // new struct, linked list node { int value; // holds a value struct Node *ptr; // also holds a pointer to next node }Node; // for recursive reference.
Node *head;
/*
//This function is optional. It creates an empty node at the head of an empty list.
void create(Node **head){ // void returns nothing, name = create, takes in Node head. if(*head == NULL){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = NULL; // Inserts a value into the current node *head = node; // Head is the front of the list, so any newly created node is the head. }else{ printf("Head = Null\n"); } };
// This function is more trouble than its worth. */
//This makes a new node, and inserts on the head of the list. Can be done whether or not there is a list.
void push(int val, Node **head){ // void type returns nothing. name is push. it takes in a user value and a Node. Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = val; // Passes val, the user's input, to value, node's value slot. node->ptr = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. }
//Deletes the top node...
int pop(int **head){ // So its int, dunno why it isnt void if(*head == NULL){ // catches if head is null. if it is, its the beginning of the list, so we can't delete. printf("Head = Null\n"); // does something to notify the user they are trying to do something bad. }else{ // if *head is anything but null. Node *temp = *head; // make a temp node and it equals head now. *head = temp->ptr; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done neing used. } }
//Prints the top node's value.
int top(Node *head){ // this just takes in a *ptr rather than **ptr, dunno why though. if(head == NULL){ // if head is null, its the beginning of the list. printf("Head = Null\n"); // prints this }else if(head->value == NULL){ // this is if head's value = null. this shouldnt happen but its possible. printf("value = Null\n"); // prints an error }else{ // otherwise printf("%d\n", head->value); // print head's value. } } /* int empty(){ int x = StackTop; StackTop = 0; while(StackTop != x){ array[StackTop] = 0; StackTop++; } } */
int PrintStack(Node *head, Node **head){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. Node *tail = (Node*)malloc(sizeof(Node)); // head for second list called tail. while(*head != NULL){ *head->ptr = node; // Head's pointed-at node (second node) is now the first thing of this second list node->ptr = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. Node *temp = *head; // make a temp node and it equals head now. *head = temp->ptr; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done neing used.
} }
/* int FindMax(){ int x = StackTop; StackTop = 0; int y = array[StackTop]; int max = array[StackTop]; while(StackTop != x){ int place = array[StackTop]; if(max<y){ max = y; StackTop++; }else{ StackTop++; }
y = array[StackTop]; } printf("%d\n", max); }
int FindMin(){ int x = StackTop; StackTop = 0; int y = array[StackTop]; int min = array[StackTop]; while(StackTop != x){ int place = array[StackTop]; if(min>y){ min = y; StackTop++; }else{ StackTop++; }
y = array[StackTop]; } printf("%d\n", min); }
*/
int main(){ head = NULL; int choice = 0; while(choice != 9){
printf("Pick a choice.\n"); printf(" 1) Create new stack\n"); printf(" 2) Push on the stack\n"); printf(" 3) Print the top value\n"); printf(" 4) Print the stack\n"); printf(" 5) Print max value in stack\n"); printf(" 6) Print min value in stack\n"); printf(" 7) Pop on the stack\n"); printf(" 8) Empty the stack\n"); printf(" 9) Quit\n");
I changed the code for the printStack function. I'm still getting errors. Here's the update:
CODE
int PrintStack(Node **head){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. Node *tail = (Node*)malloc(sizeof(Node)); // head for second list called tail. while(*head != NULL){ *head->ptr = node; // Head's pointed-at node (second node) is now the first thing of this second list node = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. tail->value = head->value; // Head's parameters now = node's parameters I guess. printf(%d, tail->value); tail->ptr = head->ptr; // make a temp node and it equals head now. free(temp); // free up temp, its done being used. } }
By the way, those comments are potentially wrong and meaningless...
int PrintStack(Node *head){ Node *bla = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. Node *tail = (Node*)malloc(sizeof(Node)); // head for second list called tail. do while(head->ptr != NULL){ head = bla; // Head's pointed-at node (second node) is now the first thing of this second list free(bla); tail->value = head->value; // Head's parameters now = node's parameters I guess. printf("%d\n", tail->value); tail->ptr = head->ptr; // make a temp node and it equals head now. free(tail); // free up temp, its done being used. } }
I'm getting a syntax error now, at the end bracket (the outside one). This code's goal is to navigate the list and print it...
int PrintStack(Node *head){ Node *bla = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. // Node *tail = (Node*)malloc(sizeof(Node)); // head for second list called tail. bla = head->ptr; do while(head->ptr != NULL){ printf("%d\n", bla->value); // Head's pointed-at node (second node) is now the first thing of this second list bla = bla->ptr; } free(bla); // free up temp, its done being used. }
I am still getting a syntax error in front of free(). Dunno whats the problem, hope someone can help, thanks.
You honestly should be able to find thousands of examples of a linked list, in this case a basic stack, in C. Here's a few hints. The only function that's calling malloc is push; nothing else needs to grab memory. The only method that releases that is pop.
There reason for this exercise to to realise the power and frustration of pointers. Here's my simple version of your code:
CODE
typedef struct Node { // new struct, linked list node int value; // holds a value struct Node *next; // also holds a pointer to next node ( use next, makes reading the rest easier) } Node;
Node *head = NULL; // This is a delclaration of the first node in our list
// We are not going to pass head, it is implict to our list // If we ever move to C++, it will be part of our class // The theory here is that pointers to pointers ( e.g. **head ) cause brain damage
// I should also be noted the user of these functions is unware that our list uses struct Node or pointers // They're just doing operations on an integer stack
// push a value onto the stack void push(int value) { Node *newNode = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. newNode->value = value; newNode->next = head; // make the next node for this new node the current head head = newNode; // the new node is now the head node, our list grows by one }
void printStack(){ Node *currentNode = head; // point to the top of the stack while(currentNode != NULL) { // while the current node is not the end, keep going printf("%d\n", currentNode->value); // show the value
// move on to the next // since we change our current pointer to the next, this is why we declare a local current pointer // to not mess up the head value currentNode = currentNode->next;
} }
// Test it. Don't do the user input thing first, get some examples working, then play with others. int main(int argc, char** argv) { push(5); push(4); push(3); printStack(); }
Thanks for the help baavgai. I am still getting errors, though now they are SegFaults at runtime:
CODE
int PrintStack(Node *head){ Node *bla = head; bla = head->next; while(bla->next != NULL){ //SegFault occurs here. printf("%d\n", bla->value); // print current value bla = bla->next; //go to current's next node. } return(0); }
Not sure why this is happening. Do you have some ideas?
This code will actually loose you the first and last node! Here it is with comments:
CODE
int PrintStack(Node *head){ Node *bla = head; // fine bla = head->next; // huh? You've just skipped the first node. Also, if the list is empty, this will fail because you have a pointer to null while(bla->next != NULL){ //assuming you get this far, you're now checking the node after the current one. If this is the last node, then next will be null here you dropt the last node. Also, if bla is null, you fail. You'll get a seg fault here is your list has one value. printf("%d\n", bla->value); // print current value bla = bla->next; //go to current's next node. } return(0); // not sure why you return zero? }
Given what you have, try this:
CODE
void PrintStack(Node *head){ Node *bla = head; while(bla != NULL) { printf("%d\n", bla->value); // print current value bla = bla->next; //go to current's next node. } }
Yeah, funny thing, right as you posted I found that my node was accessing null illegally. But your snippet helped get me somewhere, except that code only returns a memory address. So thanks. However...
Am I going about printing the list wrong? Since head = the top node, there really is no way to traverse backwards (unless I doubly link this list, which I don't think I'm supposed to do). I haven't ever done this much in terms of linked lists in C, and I've only done some linked lists in Java, though I don't remember the projects.
Anyway, I am now officially stuck. The only other way to maneuver through the list (that I know) is to have some variable, and index it when a new node is created, and somehow assign node numbers.. except that's an array.
So.. can someone steer me in the right direction here?
Your two methods, beyond the print, are push and pop. This implies a stack. A stack follows the rule of LIFO, last in, first out. Simply, the last element you enter is the top. So, if you push 1,2,3,4, when you pop you're supposed to get 4,3,2,1. This is functioning as intended.
If you want the direction maintained, you must do extra work. When you add a node, you traverse the nodes until you get to the last one, the one with a next of null. You then make the new node the next of the last one. Depending on the implementation, you're making a queue at that point. I takes a little more work and because it's such a pain as the list get large, a second pointer is often maintained for the last node, as well as the first.
Actually, making a Queue is part of my project, but a later part. Also, I don't see how the above code is working to print the list... when I push 1 and call PrintStack, it prints 4007136. When I push 2 onto this, I get 4007448. I've confused myself now. How can you reassign things with pointers going only one direction? The head points to Null, not the last node.. or do I have that confused?
Somehow I messed up my pop function as well. I'm going to post the program again...
typedef struct Node // new struct, linked list node { int value; // holds a value struct Node *next; // also holds a pointer to next node }Node; // for recursive reference.
Node *head;
/*
//This function is optional. It creates an empty node at the head of an empty list.
void create(Node **head){ // void returns nothing, name = create, takes in Node head. if(*head == NULL){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = NULL; // Inserts a value into the current node *head = node; // Head is the front of the list, so any newly created node is the head. }else{ printf("Head = Null\n"); } };
// This function is more trouble than its worth. */
//This makes a new node, and inserts on the head of the list. Can be done whether or not there is a list.
void push(int val, Node **head){ // void type returns nothing. name is push. it takes in a user value and a Node. Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = val; // Passes val, the user's input, to value, node's value slot. node->next = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. }
//Deletes the top node...
void pop(int **head){ // So its int, dunno why it isnt void if(*head == NULL){ // catches if head is null. if it is, its the beginning of the list, so we can't delete. printf("Head = Null\n"); // does something to notify the user they are trying to do something bad. }else{ // if *head is anything but null. Node *temp = *head; // make a temp node and it equals head now. *head = temp->next; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done being used. } }
//Prints the top node's value.
void top(Node *head){ // this just takes in a *pointer rather than **pointer, dunno why though. if(head == NULL){ // if head is null, its the beginning of the list. printf("Head = Null\n"); // prints this }else if(head->value == NULL){ // this is if head's value = null. this shouldnt happen but its possible. printf("value = Null\n"); // prints an error }else{ // otherwise printf("%d\n", head->value); // print head's value. } }
//Prints everything on the stack
void PrintStack(Node *head){ Node *bla = head; // Allocates memory for Node *node. while(bla != NULL){ printf("%d\n", bla->value); // Head's pointed-at node (second node) is now the first thing of this second list bla = bla->next; } }
int main(){ head = NULL; int choice = 0; while(choice != 9){
printf("Pick a choice.\n"); printf(" 1) Create new stack\n"); printf(" 2) Push on the stack\n"); printf(" 3) Print the top value\n"); printf(" 4) Print the stack\n"); printf(" 5) Print max value in stack\n"); printf(" 6) Print min value in stack\n"); printf(" 7) Pop on the stack\n"); printf(" 8) Empty the stack\n"); printf(" 9) Quit\n");
Your push and print code looks fine. However, you may have issues with just having a Node *head; out there as a global. If you're not setting the value, it could start as anything. Also, to avoid confusion, I'd declare the node in main, just to make sure you're passing what you think you're passing.
Your pop is confused. You need to return the top value and shorten the list by a node. I included a pop.
typedef struct Node // new struct, linked list node { int value; // holds a value struct Node *next; // also holds a pointer to next node }Node; // for recursive reference.
void push(int val, Node **head){ // void type returns nothing. name is push. it takes in a user value and a Node. Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = val; // Passes val, the user's input, to value, node's value slot. node->next = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. }
// pop removes, and returns, the top value off the stack int pop(Node **head){ // So its int, dunno why it isnt void int returnValue = -1; // value defaults to -1 if empty; something must be returned. if(*head == NULL) { // catches if head is null. if it is, its the beginning of the list, so we can't delete. printf("Head = Null\n"); // does something to notify the user they are trying to do something bad. } else { // if *head is anything but null. Node *temp = *head; // make a temp node and it equals head now. returnValue = temp->value; // set return value *head = temp->next; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done being used. } return returnValue; // no matter what, user gets return value }
void PrintStack(Node *head) { Node *bla = head; // Allocates memory for Node *node. while(bla != NULL){ printf("%d\n", bla->value); // Head's pointed-at node (second node) is now the first thing of this second list bla = bla->next; } }
