Differences

This shows you the differences between two versions of the page.

--- user:tgalpin2:portfolio:libdll [2011/12/16 03:43] – [Code] tgalpin2
+++ user:tgalpin2:portfolio:libdll [2011/12/16 18:29] (current) – [Execution] tgalpin2
@@ Line 1: / Line 1: @@
+======Project: Doubly Linked List Library Implementation======
+A project for Matt Haas' Fall 2011 Data Structures class.
+This project was done over the month of October, but was worked on for about a week in terms of days in which programming this implementation.
+=====Objectives=====
+The purpose of this lab is to create linked list manipulating functions, make a library from these functions, then write a program that implements this library.
+=====Prerequisites=====
+In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:
+  * understand functions
+  * understand pointers
+  * understand structs
+  * understand malloc()
+  * ability to create a linked data structure
+=====Background=====
+As previously stated, I am trying to make a linked list library implementation. In doing so, I will have gained an understanding of a linked list, which is our basis for learning about data structures. This lets one create a list of data that can be accessed by moving back and forth.
+=====Scope=====
+To better utilize the functionality of the doubly linked list we've been studying in class, a personal implementation for use as a library will be undertaken for use in other projects and activities this semester.
+Working from the class example, a library implementation will be created which has the following functions:
+  * **create**: generate a new node
+  * **append**: add a new node to the list after a given node
+  * **remove**: remove a node from the list
+  * **search**: find if a node exists (likely search by value)
+  * **insert**: add a new node to the list before a given node
+  * **copy**: duplicate an existing node
+  * **copy list**: duplicate the current list of nodes
+  * **display**: display current list
+Creating a header file will be in order, which will contain the function prototypes of all of the above. The code will be implemented across several files .
+There will also be a sample implementation (ie a file with a **main()**) that will include the header file and demonstrate this library being created (it will link against it to compile).
+=====Attributes=====
+  * pointers: pointers are at the heart of dynamic structures.
+  * malloc/new: dynamic memory allocation.
+  * linked lists: this code is going to implement linked lists.
+  * doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
+  * libraries: this code will be part of a library that can be reused in other projects
+  * file I/O: The manager in the main function uses the library to take input and give output.
+=====Code=====
+===main.c===
+<code c>
+/*
+ * Doubly Linked List Library - a doubly linked list implementation
+ *
+ * Fall2011 Data Structures
+ */
+// Include files
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+unsigned int makeChoice();
+// main function
+int main()
+{
+	// initialize variables
+	start = end = tmp = tmp2 = NULL;
+	unsigned int choice, created=0;
+	system("clear");
+	printf("Welcome to Linked List Manager!\n\n");
+	while(created == 0)
+	{
+		create();
+		if(start != NULL)
+		{
+			created=1;
+		}
+		else
+		{
+			printf("Please create a list.\n");
+		}
+	}
+	system("clear");
+	choice=makeChoice();
+	system("clear");
+	while(choice != 0)
+	{
+		system("clear");
+		if(choice==1)
+		{
+			displayList();
+		}
+		else if(choice==2)
+		{
+			append();
+		}
+		else if(choice==3)
+		{
+			insert();
+		}
+		else if(choice==4)
+		{
+			removeNode();
+		}
+		else if(choice==5)
+		{
+			copy();
+		}
+		else if(choice==6)
+		{
+			copyList();
+		}
+		if (start == NULL)
+		{
+			choice=0;
+		}
+		else
+		{
+			printf("\n\n");
+			choice=makeChoice();
+		}
+		system("clear");
+	}
+	return(0);
+}
+unsigned int makeChoice()
+{
+	unsigned int choice=-1;
+	while ((choice < 0)  || (choice > 6))
+	{
+		printf(" =============================================================");
+		printf("\n|| Choose a function to execute (0 to quit):                 ||\n");
+		printf(" =============================================================\n");
+		printf("|| (1: Display list) || (2: Append node) || (3: Insert node) ||\n");
+		printf("|| (4: Remove node)  || (5: Copy node)   || (6: Copy list)   ||\n");
+		printf(" =============================================================\n\nInput: ");
+		scanf("%d", &choice);
+		if ((choice < 0) || (choice > 6))
+		{
+			printf("\n!!ERROR!! Please enter a valid value.\n");
+		}
+	}
+	return(choice);
+}
+</code>
+===dlllib.h===
+<code c>
+/*
+ * Doubly Linked List Library - a doubly linked list implementation
+ *
+ * Fall2011 Data Structures
+ */
+#ifndef _DLLLIB_H
+#define _DLLLIB_H
+#include <stdio.h>
+#include <stdlib.h>
+// Create our node structure
+struct node {
+	int value;
+	struct node *next;
+	struct node *prev;
+};
+typedef struct node Node;
+int create();
+int append();
+int removeNode();
+int search();
+int insert();
+int deleteList();
+int copyList();
+int copy();
+int displayList();
+int input, input2;
+Node *start, *end, *tmp, *tmp2;
+#endif
+</code>
+===create.c===
+<code c>
+#include<stdio.h>
+#include<stdlib.h>
+#include "dlllib.h"
+int create()
+{
+	// initialize variables
+	start = end = tmp = tmp2 = NULL;
+	printf("Enter a value (-1 to quit): ");
+	scanf("%d", &input);
+	// build our list
+	while (input != -1)
+	{
+		if (start == NULL) // we have an empty list
+		{
+			start = (Node *) malloc (sizeof(Node));
+			end = start; // only one node, start and end are same
+			start -> next = NULL; // nothing after
+			start -> prev = NULL; // nothing before
+			tmp = start; // tmp points to beginning of list
+			start -> value = input; // enter value into node
+		}
+		else // there is something in our list
+		{
+			tmp = (Node *) malloc (sizeof(Node));
+			end -> next = tmp; // tack new node onto end of list
+			tmp -> prev = end; // new node points to current end
+			end = end -> next; // advance end to new end
+			end -> value = input; // put input in node
+			end -> next = NULL; // nothing beyond end
+		}
+		printf("Enter a value (-1 to quit): ");
+		scanf("%d", &input);
+	}
+	return(0);
+}
+</code>
+===append.c===
+<code c>
+#include<stdio.h>
+#include<stdlib.h>
+#include "dlllib.h"
+int append()
+{
+	//Append
+	tmp=start;
+	int i=0;
+	while(tmp != NULL)
+	{
+		i++;
+		tmp=tmp->next;
+	}
+	printf("Enter a value for the appended node: ");
+	scanf("%d", &input);
+	tmp = (Node *) malloc (sizeof(Node));
+	end -> next = tmp; // tack new node onto end of list
+	tmp -> prev = end; // new node points to current end
+	end = end -> next; // advance end to new end
+	end -> value = input; // put input in node
+	end -> next = NULL; // nothing beyond end
+	return(0);
+}
+</code>
+===insert.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int insert()
+{
+	// Insert a new node
+	int i=0;
+	printf("Enter node position to insert before: ");
+	scanf("%d", &input);
+	tmp = start;
+	for(i=0; i<input; i++) //position tmp at node to insert before
+	{
+		tmp = tmp -> next;
+	}
+	printf("Enter a value for new node: ");
+	scanf("%d", &input2);
+	if (start == NULL) // if our list is empty
+	{
+		start = (Node *) malloc (sizeof(Node));
+		end = tmp = start;
+		start -> prev = NULL;
+		end -> prev = NULL;
+		start -> value = input2;
+	}
+	else if (start == tmp) // we're inserting before start of list
+	{
+		tmp2 = (Node *) malloc (sizeof(Node));
+		tmp2 -> next = start; // point new node's next at start
+		start -> prev = tmp2; // point start's prev at tmp2
+		start = start -> prev; // move start to new node
+		start -> value = input2; // put value in node
+	}
+	else // we're inserting before a node in the list
+	{
+		tmp2 = (Node *) malloc (sizeof(Node));
+		tmp2 -> next = tmp; // point new node's next at tmp
+		tmp2 -> prev = tmp -> prev; // point new node's prev at tmp's prev
+		tmp -> prev -> next = tmp2; // tmp's previous next is new node
+		tmp -> prev = tmp2; // tmp's prev is new node
+		tmp2 -> value = input2; // put value in node
+	}
+	return(0);
+}
+</code>
+===copy.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int copy()
+{
+	//Copy
+	int i;
+	printf("Enter node # to copy: ");
+	scanf("%d", &input);
+	// Move tmp to exact node we wish to copy
+	tmp=start;
+	for(i=0; i<input; i++)
+	{
+		tmp = tmp -> next;
+	}
+	tmp2 = (Node *) malloc (sizeof(Node));
+	end -> next = tmp2; // tack new node onto end of list
+	tmp2 -> prev = end; // new node points to current end
+	end = end -> next; // advance end to new end
+	end -> value = tmp-> value; // put value of copied node in node
+	end -> next = NULL; // nothing beyond end
+	return(0);
+}
+</code>
+===search.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int search()
+{
+	//Find if node exists (search by value)
+	printf("Enter a value to search for: ");
+	scanf("%d", &input);
+	tmp=start;
+	int i = 0;
+	int found=0; //if found = 0, then no node matches the search.
+	while (tmp != NULL)
+	{
+		if(tmp->value == input)
+		{
+			printf("Node at position [%d] matches the search value.\n", i);
+			printf("Node [%d]: %d\nSearch value: %d\n\n", i, tmp->value, input);
+			found=1;
+		}
+		i++;
+		tmp = tmp -> next;
+	}
+	if (found == 0)
+	{
+		printf("No node matches the search value.\n");
+	}
+	return(0);
+}
+</code>
+===copyList.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int copyList()
+{
+	//Copy entire list.
+	tmp=start;
+	int i=0;
+	int copyFor;
+	while (tmp != NULL)
+	{
+		i++;
+		tmp = tmp->next;
+	}
+	tmp=start;
+	for(copyFor=0;copyFor<i;copyFor++)
+	{
+	tmp2 = (Node *) malloc (sizeof(Node));
+	end -> next = tmp2; // tack new node onto end of list
+	tmp2 -> prev = end; // new node points to current end
+	end = end -> next; // advance end to new end
+	end -> value = tmp-> value; // put value of copied node in node
+	end->next=NULL;
+	tmp=tmp->next;
+	}
+	return(0);
+}
+</code>
+===displayList.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int displayList()
+{
+	// Display our linked list
+	int i = 0;
+	tmp = start;
+	while (tmp != NULL)
+	{
+		printf("[%d] value: %d\n", i, tmp -> value);
+		i++;
+		tmp = tmp -> next;
+	}
+	return(0);
+}
+</code>
+===removeNode.c===
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dlllib.h"
+int removeNode()
+{
+	// Remove a node from the list
+	tmp = start;
+	int i=0;
+	printf("Enter node # to delete: ");
+	scanf("%d", &input);
+	// Move tmp to exact node we wish to delete
+	for(i=0; i<input; i++)
+	{
+		tmp = tmp -> next;
+	}
+	if ((tmp != start) && (tmp != end))
+	{
+		tmp -> next -> prev = tmp -> prev;
+		// The node after points to the node before tmp
+		tmp -> prev -> next = tmp -> next;
+		// Now, the now before points to the node after tmp
+		tmp -> prev = NULL;
+		tmp -> next = NULL;
+		// tmp is now disconnected from the list
+		free (tmp); // deallocate the node tmp is pointing to
+	}
+	else if (start == end) // list is only a single node
+	{
+		free(start);
+		start=end=tmp=NULL;
+	}
+	else if (tmp == start)
+	{
+		tmp -> next -> prev = NULL;
+		// The node following tmp is no longer pointing to us
+		start = start -> next;
+		// Adjust start to point to the new start of the list
+		tmp -> next = NULL; // Disconnect tmp from the list
+		free(tmp); // deallocate the node tmp is pointing to
+	}
+	else // tmp is equal to end
+	{
+		tmp -> prev -> next = NULL;
+		// The node preceding tmp is no longer pointing to us
+		end = end -> prev;
+		// Adjust end to point to the new end of the list
+		tmp -> prev = NULL; // Disconnect tmp from the list
+		free(tmp); // deallocate the node tmp is pointing to
+	}
+	return(0);
+}
+</code>
+=====Execution=====
+This is how to compile and execute:
+<cli>
+lab46:~/src/data/dlllib$ ar rcs libdll.a *.o
+lab46:~/src/data/dlllib$ gcc -o testimple main.c -L. -ldll
+lab46:~/src/data/dlllib$ ./testimple
+</cli>
+=====Reflection=====
+I had some problems with my node removing function. Rather than having a function that removes a list, I settled for a single node deleting function that can be run until the list is gone. Overall, this is a very important project, because it lays the foundation for the rest of the class, really. It is a big hurdle to get over, but once you do, there is a lot to be learned from going back and using this project.
+=====References=====
+In performing this project, the following resources were referenced:
+  * Matt Haas
+  * Fellow classmates (simple discussion about the aspects of our personal implementations)
+  * C Programming Language O'Reilly Pocket Reference

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools