A project for Data Structures by Tyler Galpin during the Fall 2011.

This project was started in early December and was not completed.

The point of this project is to make a usable tree library that can be used not only in a test implementation, but can be applied to any program that may make use of a tree comprised of a linked list. Through this, a greater understanding of what a tree is should be attained.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• Understanding of linked list
• Understanding of doubly linked list
• Basic understanding of what a tree is
• Understanding of pointers

As previously stated, a working tree library is the goal. It should be able to manipulate the data in the tree however we need it to. As is such,the following functions must be in it:

• Push–Add a node, FILO style
• Pop– Remove a node, FILO style
• Display– Display tree, make note of where top and bottom is

The implementation is relatively straightforward. I just need it to demonstrate that the logic of a tree is present. For this, a menu is included in the main part of the program to let you choose which function you'd like to test.

• linked list: The tree is based off of a linked list
• doubly linked list: The tree uses a doubly linked list.
• pointers: make up the backbone of the data structure
• malloc: needed in the creation of new trees/nodes
• tree: …Hey, this is a tree, isn't it?
• library: That is what is being made/used!
• File I/O: Used in main.c for test implementation
• sorts: Trees depend upon a sorting algorithm.

/*
 * Tree implimentation -- main
 *
 * Fall2011 Data Structures
 */
 
// Include files
#include <stdio.h>
#include <stdlib.h>
 
// Create our node structure
struct node {
	int value;
	struct node *next;
	struct node *prev;
};
typedef struct node Node;
 
Node *start, *tmp, *tmp2;
 
void addNode(int);
void deleteNode(int);
void displayTree();
void searchTree(int, int);//Send a value and a decision value
//int isEmpty();
 
// main function
int main()
{
	int i, input, choice;
	puts("Please enter a value (-1 to stop:): ");
	scanf("%d", &input);
	while(input != -1)
	{
		addNode(input);
		puts("Please enter a value (-1 to stop:): ");
		scanf("%d", &input);
	}
	puts("Please choose a function: [1: Enqueue][2: Dequeue][3: Display][4: Search][0: Quit]");
	scanf("%d", &choice);
	while (choice != 0)
	{
		if (choice == 1)
		{
			input=0;			
			puts("Please enter a value (-1 to stop:): ");
			scanf("%d", &input);
			while(input != -1)
			{
				addNode(input);
				puts("Please enter a value (-1 to stop:): ");
				scanf("%d", &input);
			}
			input=0;
		}
		else if (choice == 2)
		{
			deleteNode();
		}
		else if (choice == 3)
		{
			displayTree();
		}	
		else if (choice == 4)
		{
			searchTree();
		}
		puts("Please choose a function: [1: Enqueue][2: Dequeue][3: Display][4: Search][0: Quit]");
		scanf("%d", &choice);
	}
/*
	while((tmp=pop())!=NULL)
	{
		printf("value: %d\n", tmp->value);
		free(tmp);
	}
*/
	return(0);
}
 
void addNode(int value)
{
	if (start==NULL)//No values in the tree yet
	{
		start = (Node *) malloc(sizeof(Node));//Initialize head (first) node
		start->next=NULL;//Nothing greater in list
		start->prev=NULL;//Nothing lesser in list
		tmp=start;//Make tmp have the same value as start node up until now
		start->value=value;//Give input value to start
	}
	searchNode(value, 1);
	tmp=(Node *) malloc(sizeof(Node));
	tmp->value=value;
	if (tmp->value > tmp2->value)
	{
		tmp2->next=tmp;//Node is greater than tmp2, it gets placed on the "greater node" path
		tmp2->next->next=NULL;//Nothing after this node is currently greater 
		tmp2->next->prev=NULL;//Nothing after is less
	} //Node gets placed to the "right"
	else //if node is equal to or less than, it gets placed to "left"
	{
		tmp2->prev=tmp;//Node is less than tmp2, it gets placed on the "lesser node" path
		tmp2->prev->next=NULL;//Nothing after this node is currently greater 
		tmp2->prev->prev=NULL;//Nothing after is less
	}
	free(tmp);
}
 
void searchTree(int value, int type)
{
	tmp2=start;
	int i=0;
	while(((tmp2->next != NULL) && (value <= tmp2->value))||((tmp2->prev != NULL) && (value > tmp2->value)))
	/*
		While there is something greater than the current node and value is less than or equal
		to the current node's value, OR while there is something lesser than the current node 
		and value is greater than the current node's value, execute loop.
 
		This is saying-- If there is nothing greater/less than current node, 
		and the given value is greater/lesser, stop! ~Tyler
	*/
	{
 
 
		if (type == 2) 
		//Sending an int value of 2 to the function indicates a search for a specific node value.
		//1 Simply indicates a search for the place to insert the new node.
		{
			if(value == tmp2->value)
			{
				i++;
				printf("\nNode match! Search value: [%d] | Current node: [%d] | Number of matches: [%d]\n", value, tmp2->value, i);
			}
		}
		if (value > tmp2->value)//if value is greater
		{
			tmp2=tmp2->next;//Move tmp2 to the next greater node (next)
		}
		else //if value is lesser or equal
		{
			tmp2=tmp2->prev; //move tmp2 to next lesser node (prev)
		}
	}
}
 
void deleteNode(int value)
{
	No
}
 
void displayQueue()
{
	int n=0;
	tmp=head;
	printf("\n[Front of queue]\n");
	while(tmp != NULL)
	{
		printf("[%d]: %d\n", n+1,tmp->value);
		n++;
		tmp=tmp->prev;
	}
	printf("[End of queue]\n");
}
/*
int isEmpty()
{
	int status=0;
	if(top==1)
	{
		status=1;
	}
	return(status);
}
*/

This is how you would compile and execute, had the project been completed:

lab46:~/src/data/tree$ ar rcs libdll.a *.o
lab46:~/src/data/tree$ gcc -o testimple main.c -L. -ldll
lab46:~/src/data/tree$ ./testimple

This was one of the more interesting librarys to work on, and I just wish that I had finished it before the semester had ended. Luckily, I wasn't the only one who didn't get a tree library up and running, so it doesn't count against me too much.

In performing this project, the following resources were referenced:

• Matt Haas + Class lecture
• Fellow classmates (simple discussion about the aspects of our personal implementations)
• C Programming Language O'Reilly Pocket Reference