2 Replies - 2822 Views - Last Post: 22 September 2009 - 11:30 PM Rate Topic: -----

#1 popapez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 22-September 09

C: stack and queue implemented w linked list of structs

Posted 22 September 2009 - 08:23 PM

Hi, I am taking a beginner's C programming course, although I am very fluent in java so I understand the concepts, etc.

I am implementing a stack and a queue with nodes of structs using linked lists. Every method that is unrelated to stacks and queues work fine (eg. tokenize, etc). I am having some issues though:
- stack:
+ it seems to be pushing correctly, but right now trying to pop puts us in an infinite loop. I have looked over and over this code and I don't think it should be doing this....

- queue:
+ enqueueing the first node works, but the second attempt creates a bus error. I have changed this code many times, and previously it was always enqueueing the last line of my file, instead of going line by line. I am sure it is just one stupid pointer issue or something that is messing it all up, but I'm pulling my hair out trying to find it!!


Sorry for the long post! Thanks so much!!! Here is my code:



* NOTE- I only print the f1 field out as a test to see if I have the correct node. The other fields of the struct should work as well.

Also, I made a lot of variables global for ease of testing, which is obviously not ideal but it's how my code is set up currently.


EDIT: if someone wants the entire code, with the other subroutines, to test on their own machine, I can easily provide that :)


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>		// for random numbers

struct node				// node for linked list
	{
	int f1;
	float f2;
	char f3;		
	struct node *next;		// PTR to next node
	};
	
struct node *start, *end;		// first and last nodes in linked list
struct node *new, *TEMP, *p;									
char RandomName(char randomNAME);
struct node tokenize(char line[]);
int runs = 1;				// tracks runs, 1st run							

// for stack:
void push(void), pop(void);

// for queue:
void dequeue(void), add(void), enqueue();


int main(int argc, char*argv[])
	{	
	char runagain = 'Y';
	while (runagain == 'Y')	// entire program in loop
		{
	 	new = (struct node*)malloc(sizeof(struct node)); 
		start = NULL;
		end = NULL;
		int whileloop = 1;
		srand((unsigned)(time(NULL)));					
		int j = 0;
		int random = 0;			// random number
		char *file = argv[1];		// file name is entered from command line
		FILE *data;										
		char decision[10];			// will be either stack(S) or queue(Q)
		char line[100];			// hold the line
		int lcount = 0;		// initialize line count
		int i = 1;
		char input[10];		// holds the action for the queue/stack
		register int t;									

// make a file
		data = fopen(file, "w");	// open for writing
		if (data == NULL)
			{
			printf("Cannot open %s\n", data);
			exit(0);
			}

		for (j=0; j<10; j++)		// write 10 random structs to file
			{
			new->next = NULL;		

			new->f1 = rand()%90+10;					// random integer
			new->f2 = (rand()%100)/9.9;					// random float
			new->f3 = RandomName(new->f3);			// random name
			fprintf(data, "%d %g %c\n", new->f1, new->f2, new->f3);
			}			// print each data field of new to file

		fclose(data);		// close file

		printf("Create a stack(S) or a queue(Q):  ");	// get decision
		scanf("%c", decision);
		if (runs > 1)
			scanf("%c", decision);						

		*decision = toupper(*decision);					// converts to uppercase always
		data = fopen(file, "r");						// open file for reading

// queue:
		if (*decision == 'Q')
			{
			while(whileloop == 1) 						// will execute until quit
				{
				printf("Choose an action- Enqueue(E), Print(P), Dequeue(D), Quit(Q):  ");
				if (i==1)
					gets(input);						// have to gets() twice the first run, 
				gets(input);							// or will print above line twice.
				*input = toupper(*input);				// converts to an uppercase char

				switch(*input) 							// will go to one of 3 methods, or exit
					{
					case 'E':
						if (fgets(line, sizeof(line), data) != NULL) 
							{
							lcount++;
							printf("%d. %s", lcount, line);	  // print line # and data
							}
						*new = tokenize(line);
						enqueue();
						break;
					case 'P':
//						print(idkyet, idk);
						break;
					case 'D':
						dequeue();
						printf("Struct dequeued was %d  \n", start->f1);
						break;
					case 'Q':
						whileloop = 0;
						break;
					default:
						printf("Please enter an A, P, D or Q.\n");	// if none are entered				
					}
				i++;									// now only one gets()	
				}
			}
		
// stack:		
		else if (*decision == 'S')
			{
			int i = 1;
			while(whileloop == 1) 
				{
				printf("Choose an action- PUSH(U), POP(O), Quit(Q):  ");
				if (i==1)
					gets(input);			// have to gets() twice the first run, 
				gets(input);							
				*input = toupper(*input);				// converts to an uppercase char
	
				switch(*input) 				// will go to one of 3 methods, or exit
					{
					case 'U':
						if (fgets(line, sizeof(line), data) != NULL) 
							{
							lcount++;
							printf("%d. %s", lcount, line);	  // print line # and data
							}
						*new = tokenize(line);	
		 				push();
						break;
					case 'O':
						pop();
						break;
					case 'Q':
						whileloop = 0;
						break;
					default:
						printf("Please enter a U, O or Q.\n");	// if none are entered
					}
				i++;									// now only one gets()	
				}
			}
		else
			printf("Error: please enter 'Q' or 'S' only! \n");
		
		fclose(data);									// close file

		printf("Would you like to create another data structure: Y or N?  ");
		scanf("%s", &runagain);							// will run again if 'y'
			
		runagain = toupper(runagain);					// always convert to uppercase
		runs++;							// increase # of runs
		}
	printf("BYE!!\n\n");	
	return 0;
	}



char RandomName(char randomNAME)
	{
	...
	return randomNAME;	
	}

struct node tokenize(char line[])
{
struct node *new;
new = (struct node*)malloc(sizeof(struct node));

.....................

new->f1 = (tempINT[0]*10 + tempINT[1]);
new->f2 = (tempFLOAT[0] + tempFLOAT[1]/10.0);
new->f3 = tempSTRING;

return *new;
}					// new is now updated with values in the line of the file


// ********** STACK METHODS: ***********

void push(void)							// pushes number onto stack
	{
	new->next = NULL;
	if (start == NULL)
		start = new;
	else
		{
		p = start; 
		while (p->next != NULL)			// traverses to last node
			p = p->next;
		p->next = new;					// assigns last node's pointer to new node
		}	
	}

void pop(void)								// pops node from stack
	{
	if (start == NULL)						// no nodes in list
		printf("Stack is empty!\n");
	else if (start->next == NULL)			// only one node in list
		{
		printf("Deleted node was start node %d\n", start->f1);
		free(start);
		start = NULL;
		}
	else
		{
		p = start;
		while (p->next != NULL)
			{
			TEMP = p;
			p = p->next;					// traverse to last node
			}
		printf("Deleted node was %d\n", p->f1);
		TEMP->next = NULL;					// new last node points to NULL
		free(p);							// free deleted node's memory space
		}
	}
	
// ********** QUEUE METHODS: ***********

void enqueue(void)						// add number to queue
	{
	new->next = NULL;
	if (start == NULL)
		start = new;
	else	
		{
		end->next = new;
		end = new;
		printf("end is %d\n", end->f1);		
		}
	}

void dequeue(void)							// delete number from queue
	{	
	struct node *temp1, *temp2;
	if (start == NULL)
		{
		printf("Empty: cannot delete!.\n");
		exit(1);
		}
	else
		{
		p = start;
		printf("Deleted int is %d \n", p->f1);
		start = start->next;
		free(p);			// free the memory allocated to del
		}
	}
	
	


This post has been edited by popapez: 22 September 2009 - 08:42 PM


Is This A Good Question/Topic? 0
  • +

Replies To: C: stack and queue implemented w linked list of structs

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: C: stack and queue implemented w linked list of structs

Posted 22 September 2009 - 10:43 PM

First of all... I hate to be harsh -- but your code is a MESS! you have global variables, can't tell where things are declared/defined/used etc. (surprised the compiler can).

It is MUCH easier to work with clean code!

Secondly -- I need to check: you seem to be implementing the stack sort of backwards -- the newest node (the one just pushed) is at the END of the linked list? (normally stacks have the newest node be the start of the linked list so that it can be pushed/poped in O(1))

you pop does look a little complicated for a simple bit of logic... but you know I don't really see a problem with it... you could try adding a message inside of the loop in the pop() function to see what is going on there...
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: C: stack and queue implemented w linked list of structs

Posted 22 September 2009 - 11:30 PM

Here is a really simple version of a stack in C -- I hope that this will help you understand some of the features of a stack as well as how to avoid using all of those global values.
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;
	struct node *next;
} SSNode;

typedef struct {
	SSNode *top;
} SimpleStack;

void push(SimpleStack *stack, int value);
int pop(SimpleStack *stack);
int stackSize(SimpleStack *stack); 

int main() {
	int val;
	SimpleStack ss;
	ss.top = NULL; // have to initialize the stack...
	puts("pushing: 3, 1, 4, 1, 5, 9");
	//lets push some values... note that we have to pass the stack by-reference, this is so that our changes
	// take affect. (if we passed by value we could not really push or pop, but we could peek).
	push(&ss, 3);
	push(&ss, 1);
	push(&ss, 4);
	push(&ss, 1);
	push(&ss, 5);
	push(&ss, 9);
	printf("Number of items on the stack: %d\n", stackSize(&ss));
	printf("poping values: ");
	// empty the stack...
	while(ss.top) {
		val = pop(&ss);
		printf("%d, ", val);
	}
	puts("Did it work?");
	printf("Number of items on the stack: %d\n", stackSize(&ss));
	
	
	return 0;
}


void push(SimpleStack *stack, int value) {
	SSNode *newNode;
	//lets make our node:
	newNode = (SSNode *)malloc(sizeof(SSNode));
	if (!newNode) {			 // allocation failed...
		exit(1);
	}
	newNode->value = value;	 //copy our value into the new element...
	newNode->next = NULL;	   //make sure we initialize our next pointer
	if(stack->top==NULL) {	  //out stack turns out to empty...
		stack->top = newNode;   //all we have to do is assign our new node.
	} else {
		newNode->next = stack->top; //push the top to down to "next"
		stack->top = newNode;   //put the new node on top!
	}
	return;
}

int pop(SimpleStack *stack) {
	int retVal;
	SSNode *ptr;				//a temp value so that we can edit the top pointer before we free the node's memory.
	if(stack->top == NULL) {	//nothing in our list to return!
		retVal = 0; exit(1);
	} else {
		retVal = stack->top->value; //grab the top value...
		ptr = stack->top;	   // grab the top node in a temp ptr.
		stack->top = stack->top->next; //pop the next value up to top..
		free(ptr);			  // free our memory...
	}
	return retVal;
}

int stackSize(SimpleStack *stack) {
	int count = 0;
	SSNode *ptr = stack->top;
	while(ptr) { count++; ptr = ptr->next; }
	return count;
}

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1