This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
user:jr018429:portfolio:stack [2011/10/14 23:54] – [Reflection] jr018429 | user:jr018429:portfolio:stack [2011/11/04 15:07] (current) – [Execution] jr018429 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | <WRAP centeralign round graybg box 96%> | ||
+ | <WRAP muchbigger> | ||
+ | <WRAP bigger> | ||
+ | <WRAP bigger> | ||
+ | </ | ||
+ | ======Objectives====== | ||
+ | My stack library is available for download from: My library is available at: | ||
+ | http:// | ||
+ | \\ | ||
+ | The main objectives of this project are to learn about stack data structures, and create a functioning stack library in C. What are stack data structures used for and how are they implemented? | ||
+ | ======Prerequisites====== | ||
+ | In order to successfully accomplish/ | ||
+ | * understand and use the C/C++ programming language | ||
+ | * understand and use functions | ||
+ | * understand and use pointers in general | ||
+ | * understand and use pointers to pointers | ||
+ | * understand and use structs | ||
+ | * understand and use pointers (referencing and dereferencing) to structures | ||
+ | * understand and use pointer to pointers (refeencing and dereferencing) to structures | ||
+ | * understand and use malloc() to dynamically allocate memory | ||
+ | * understand and use free() to deallocate memory | ||
+ | * understand the linked data structure (singly and doubly linked stacks) in general | ||
+ | * know how to create and use a static library | ||
+ | * know how to build a doubly linked stack library using the items listed above | ||
+ | |||
+ | ======Background====== | ||
+ | A data structure holds data and provides operations to the user that can be performed on the data it contains. A stack is a one type of data structure; it is a (LIFO) last in, first out data structure. Spring-loaded plate dispensers used in some restaurants are used to illustrate how the stack data structure operates. | ||
+ | ======Scope====== | ||
+ | Stack Library implementation | ||
+ | Linked Lists provide a foundation for dynamic structures. Further exploring Data Structures, we find that particular manipulations of these structures enable interesting possibilities for computing. Stacks are one such iteration of these Data Structures we are exploring this semester. | ||
+ | |||
+ | An excellent exploration with Stacks would be to extend your Linked List Library with Stack Functionality (or to create a new Stack library that depends on the Linked List library). | ||
+ | |||
+ | To create a Stack library, you may want to have the following functions: | ||
+ | |||
+ | * create: generate a new stack | ||
+ | * push: add a new node to the top of the stack | ||
+ | * pop: remove the node from the top of the stack and return it | ||
+ | * peek: retrieve the node from the top of the stack but do not remove it | ||
+ | * isEmpty: is the stack in an empty condition? | ||
+ | * delete: delete and de-allocate the stack | ||
+ | * copy: duplicate the existing stack | ||
+ | A stack can be relatively infinite (so long as available resources are present for allocation) or fixed in size. | ||
+ | |||
+ | Your stack implementation should be able to handle/ | ||
+ | |||
+ | * unlimited stack size | ||
+ | * fixed stack size | ||
+ | * stack overflow | ||
+ | * stack underflow | ||
+ | Implementing this functionality into a library will enable you to utilize it in additional projects. | ||
+ | |||
+ | The Stack Library project scope is available at:\\ | ||
+ | http:// | ||
+ | ======Attributes====== | ||
+ | The course requirement for Data Structures projects are listed at:\\ | ||
+ | http:// | ||
+ | This project has the following project attributes described on that page: | ||
+ | ^Attribute^Qty Needed^Description^ | ||
+ | |Pointers|8|Indirection/ | ||
+ | |malloc/ | ||
+ | |Stack|4|Implementation/ | ||
+ | |Libraries|4|Implementation/ | ||
+ | \\ | ||
+ | This project, therefore, is eligible for 20 attributes total, however, only 6 of these are achieveable per project, so project far exceeds the minimum attribute requirements. | ||
+ | ======Code====== | ||
+ | My library is composed of the following files and functions: | ||
+ | **all.h**\\ | ||
+ | all.h is the header file for the stack library. It should be included in any .c library files whose function prototypes have been added to it. Also, it must be added to any programs utilizing the library' | ||
+ | Example code:\\ | ||
+ | |||
+ | <file h all.h> | ||
+ | //all.h | ||
+ | //John T. Rine | ||
+ | //October 13, 2011 | ||
+ | |||
+ | #ifndef _ALL_H | ||
+ | #define _ALL_H | ||
+ | # | ||
+ | # | ||
+ | |||
+ | struct Node | ||
+ | { | ||
+ | int data; | ||
+ | struct Node * prev; | ||
+ | struct Node * next; | ||
+ | }; | ||
+ | |||
+ | typedef struct Node node; | ||
+ | |||
+ | int isEmpty(node *); | ||
+ | |||
+ | void push(node **, node **, /*int position,*/ int); | ||
+ | |||
+ | int pop(node **head, node **tail); | ||
+ | |||
+ | int peek(node *); | ||
+ | |||
+ | int listStackSizeHead(node *); | ||
+ | |||
+ | int listStackSizeTail(node *); | ||
+ | |||
+ | void destroyFixedStackHead(node **, node **); | ||
+ | |||
+ | void destroyFixedStackTail(node **, node **); | ||
+ | |||
+ | void createFixedStack(node **, node **, int); | ||
+ | |||
+ | void copyStack(node *, node **, node **); | ||
+ | |||
+ | #endif | ||
+ | </ | ||
+ | \\ | ||
+ | **copyStack.c**\\ | ||
+ | copyStack.c contains only one function, copyStack. copyStack takes as its parameters head, the head of the stack to be copied, copyHead and copyTail; | ||
+ | <file c copyStack.c> | ||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 13, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | void copyStack(node *head, node **copyHead, node **copyTail) | ||
+ | { | ||
+ | node *new, *temp; | ||
+ | new = *copyHead = *copyTail = temp = NULL; | ||
+ | temp = head; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | if (*copyHead == NULL) | ||
+ | { | ||
+ | *copyHead = (node *) malloc(sizeof(node)); | ||
+ | *copyTail = *copyHead; | ||
+ | (*copyHead)-> | ||
+ | (*copyHead)-> | ||
+ | (*copyHead)-> | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | new = (node *) malloc(sizeof(node)); | ||
+ | new-> | ||
+ | new-> | ||
+ | (*copyTail)-> | ||
+ | *copyTail = new; | ||
+ | (*copyTail)-> | ||
+ | } | ||
+ | temp = temp-> | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **createFixedStack.c**\\ | ||
+ | createFixedStack.c contains one function, createFixedStack. The function takes three parameters; head, tail, and elements. head and tail become the head and the tail of the new stack, whereas elements is the size of the new stack.\\ | ||
+ | <file c createFixedStack.c> | ||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | void createFixedStack(node **head, node **tail, int elements) | ||
+ | { | ||
+ | int i; | ||
+ | node *new; | ||
+ | new = NULL; | ||
+ | *head = *tail = NULL; | ||
+ | |||
+ | for(i = 1; i< | ||
+ | { | ||
+ | if (*head == NULL) | ||
+ | { | ||
+ | *head = (node *) malloc(sizeof(node)); | ||
+ | *tail = *head; | ||
+ | (*head)-> | ||
+ | (*head)-> | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | new = (node *) malloc(sizeof(node)); | ||
+ | new-> | ||
+ | new-> | ||
+ | (*tail)-> | ||
+ | *tail = new; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **destroyFixedStack.c**\\ | ||
+ | destroyFixedStack.c contains two functions for destroying a stack. destroyFixedStackHead destroys a stack from its head; destroyFixedStackTail destroys a stack from its tail.\\ | ||
+ | <file c destroyFixedStack.c> | ||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | void destroyFixedStackHead(node **head, node **tail) | ||
+ | { | ||
+ | node *temp; | ||
+ | node *temp2; | ||
+ | temp = NULL; | ||
+ | temp2 = NULL; | ||
+ | temp = *head; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | temp2 = temp-> | ||
+ | if (temp-> | ||
+ | if (temp-> | ||
+ | free(temp); | ||
+ | temp = temp2; | ||
+ | } | ||
+ | *head = *tail = NULL; | ||
+ | } | ||
+ | |||
+ | void destroyFixedStackTail(node **head, node **tail) | ||
+ | { | ||
+ | node *temp; | ||
+ | node *temp2; | ||
+ | temp = NULL; | ||
+ | temp2 = NULL; | ||
+ | temp = *tail; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | temp2 = temp-> | ||
+ | if (temp-> | ||
+ | if (temp-> | ||
+ | free(temp); | ||
+ | temp = temp2; | ||
+ | } | ||
+ | *head = *tail = NULL; | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **isEmpty.c**\\ | ||
+ | isEmpty.c contains one function, isEmpty, to test a stack for to see if it is empty. If the stack is empty, it returns true, otherwise it returns false.\\ | ||
+ | <file c isEmpty.c> | ||
+ | //isEmpty.c | ||
+ | //John T. Rine | ||
+ | //October 13, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int isEmpty(node *tail) | ||
+ | { | ||
+ | if (tail == NULL) return 1; | ||
+ | else return 0; | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **listStackSize.c**\\ | ||
+ | listStackSize.c contains two functions for returning the size of a stack. listStackSizeHead takes head as its parameter; listStackSizeTail takes tail as its parameter.\\ | ||
+ | <file c listStackSize.c> | ||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int listStackSizeHead(node *head) | ||
+ | { | ||
+ | int size = 0; | ||
+ | while (head != NULL) | ||
+ | { | ||
+ | head = head-> | ||
+ | size++; | ||
+ | } | ||
+ | return size; | ||
+ | } | ||
+ | |||
+ | int listStackSizeTail(node *tail) | ||
+ | { | ||
+ | int size = 0; | ||
+ | while (tail != NULL) | ||
+ | { | ||
+ | tail = tail-> | ||
+ | size++; | ||
+ | } | ||
+ | return size; | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **peek.c**\\ | ||
+ | peek.c contains one function for peeking, returning the value, at the top of the stack. Since it is peeking, it will not destroy the node as does the pop function.\\ | ||
+ | <file c peek.c> | ||
+ | //peek.c | ||
+ | //John T. Rine | ||
+ | //October 13, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int peek(node *tail) | ||
+ | { | ||
+ | if (tail == NULL) | ||
+ | { | ||
+ | printf(" | ||
+ | exit(1); | ||
+ | } | ||
+ | return tail-> | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **pop.c**\\ | ||
+ | pop.c contains one function for popping data from the top of a stack.\\ | ||
+ | <file c pop.c> | ||
+ | //pop.c | ||
+ | //John T. Rine | ||
+ | //October 13, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int pop(node **head, node **tail) | ||
+ | { | ||
+ | int data = 0; | ||
+ | node *temp = NULL; | ||
+ | temp = *tail; | ||
+ | if(*head != NULL && *tail != NULL) | ||
+ | { | ||
+ | if (temp == *head) | ||
+ | { | ||
+ | temp-> | ||
+ | data = temp-> | ||
+ | free(temp); | ||
+ | *head = *tail = NULL; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | temp-> | ||
+ | *tail = temp-> | ||
+ | temp-> | ||
+ | data = temp-> | ||
+ | free(temp); | ||
+ | } | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | printf(" | ||
+ | exit(1); | ||
+ | } | ||
+ | return data; | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **push.c**\\ | ||
+ | push.c contains one function for pushing data onto a stack.\\ | ||
+ | <file c push.c> | ||
+ | //push.c | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | void push(node **head, node **tail, /*int position,*/ int data) | ||
+ | { | ||
+ | int i; | ||
+ | node *temp, *temp2; | ||
+ | temp = temp2 = NULL; | ||
+ | |||
+ | temp = *head; | ||
+ | //for(i = 0; i < position; i++) | ||
+ | //{ | ||
+ | // temp = temp -> next; | ||
+ | //} | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | temp = temp-> | ||
+ | } | ||
+ | |||
+ | if (*head == NULL) | ||
+ | { | ||
+ | *head = (node *) malloc(sizeof(node)); | ||
+ | *tail = *head; | ||
+ | (*head)-> | ||
+ | (*head)-> | ||
+ | (*head)-> | ||
+ | } | ||
+ | else// if (*tail == temp) | ||
+ | { | ||
+ | temp2 = (node *) malloc (sizeof(node)); | ||
+ | temp2-> | ||
+ | temp2-> | ||
+ | (*tail)-> | ||
+ | *tail = temp2; | ||
+ | (*tail)-> | ||
+ | } | ||
+ | //else | ||
+ | //{ | ||
+ | //temp2 = (node *) malloc (sizeof(node)); | ||
+ | // | ||
+ | // | ||
+ | // | ||
+ | // | ||
+ | // | ||
+ | |||
+ | //} | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **stackTest.c**\\ | ||
+ | stackTest.c is a program used to test the stack library.\\ | ||
+ | <file c stackTest.c> | ||
+ | // | ||
+ | //Author: John T. Rine | ||
+ | //Date: October 12, 2011 | ||
+ | |||
+ | |||
+ | # | ||
+ | |||
+ | int main(int argc, char **argv) | ||
+ | { | ||
+ | int i, data; | ||
+ | node *head, *tail, *temp, *copyHead, *copyTail; | ||
+ | head = tail = temp = copyHead = copyTail = NULL; | ||
+ | |||
+ | printf(" | ||
+ | printf(" | ||
+ | createFixedStack(& | ||
+ | printf(" | ||
+ | printf(" | ||
+ | |||
+ | i = 10; | ||
+ | temp = tail; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | temp-> | ||
+ | i--; | ||
+ | temp = temp-> | ||
+ | } | ||
+ | printf(" | ||
+ | printf(" | ||
+ | if(isEmpty(tail)) printf(" | ||
+ | else printf(" | ||
+ | |||
+ | temp = tail; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | printf(" | ||
+ | temp = temp-> | ||
+ | } | ||
+ | printf(" | ||
+ | copyStack(head, | ||
+ | printf(" | ||
+ | destroyFixedStackTail(& | ||
+ | if(isEmpty(tail)) printf(" | ||
+ | else printf(" | ||
+ | printf(" | ||
+ | printf(" | ||
+ | temp = copyTail; | ||
+ | while(temp != NULL) | ||
+ | { | ||
+ | printf(" | ||
+ | temp = temp-> | ||
+ | } | ||
+ | if(isEmpty(copyTail)) printf(" | ||
+ | else printf(" | ||
+ | printf(" | ||
+ | destroyFixedStackTail(& | ||
+ | if(isEmpty(copyTail)) printf(" | ||
+ | else printf(" | ||
+ | printf(" | ||
+ | printf(" | ||
+ | scanf(" | ||
+ | head = tail = NULL; | ||
+ | for(;i > 0; i--) | ||
+ | { | ||
+ | printf(" | ||
+ | scanf(" | ||
+ | push(& | ||
+ | } | ||
+ | printf(" | ||
+ | printf(" | ||
+ | printf(" | ||
+ | scanf(" | ||
+ | for (;i > 0; i--) | ||
+ | { | ||
+ | printf(" | ||
+ | } | ||
+ | printf(" | ||
+ | printf(" | ||
+ | getchar(); | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | **makeStack.bat**\\ | ||
+ | The Windows batch file makeStack.bat automates, manufacture of all of the .o files, the creation of the static library file, compiling, linking, and execution of stackTest, the test file.\\ | ||
+ | Example code:\\ | ||
+ | <file bat makeStack.bat> | ||
+ | REM cd c: | ||
+ | |||
+ | del *.o | ||
+ | del *.exe | ||
+ | del *.a | ||
+ | |||
+ | gcc -c createFixedStack.c -o createFixedStack.o | ||
+ | rem pause | ||
+ | gcc -c destroyFixedStack.c -o destroyFixedStack.o | ||
+ | rem pause | ||
+ | gcc -c push.c -o push.o | ||
+ | rem pause | ||
+ | gcc -c pop.c -o pop.o | ||
+ | rem pause | ||
+ | gcc -c listStackSize.c -o listStackSize.o | ||
+ | rem pause | ||
+ | gcc -c isEmpty.c -o isEmpty.o | ||
+ | rem pause | ||
+ | gcc -c peek.c -o peek.o | ||
+ | rem pause | ||
+ | gcc -c copyStack.c -o copyStack.o | ||
+ | rem pause | ||
+ | ar rcs libdll.a *.o | ||
+ | rem pause | ||
+ | gcc -I. stackTest.c -o stackTest libdll.a | ||
+ | rem pause | ||
+ | stackTest | ||
+ | pause | ||
+ | </ | ||
+ | \\ | ||
+ | **makeStack.sh**\\ | ||
+ | The bash shell script file makeStack.sh automates the manufacture of all of the .o files, the creation of the static library file, compiling, linking and execution of stackTest, the test file.\\ | ||
+ | Example code:\\ | ||
+ | <file sh makeStack.sh> | ||
+ | #!/bin/bash | ||
+ | |||
+ | rm *.o | ||
+ | rm stackTest | ||
+ | |||
+ | gcc -c createFixedStack.c -o createFixedStack.o | ||
+ | gcc -c destroyFixedStack.c -o destroyFixedStack.o | ||
+ | gcc -c push.c -o push.o | ||
+ | gcc -c pop.c -o pop.o | ||
+ | gcc -c listStackSize.c -o listStackSize.o | ||
+ | gcc -c isEmpty.c -o isEmpty.o | ||
+ | gcc -c peek.c -o peek.o | ||
+ | gcc -c copyStack.c -o copyStack.o | ||
+ | |||
+ | ar rcs libdll.a *.o | ||
+ | gcc -I. stackTest.c -o stackTest libdll.a | ||
+ | |||
+ | ./stackTest | ||
+ | </ | ||
+ | ======Execution====== | ||
+ | ** Execution of makeStack.bat (compilation, | ||
+ | <cli> | ||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | |||
+ | C: | ||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | Creating a fixed size stack of 10 nodes... | ||
+ | |||
+ | Head is = 0x3e2470; Tail is = 0x3e2548 | ||
+ | |||
+ | Size of the list is: 10 | ||
+ | |||
+ | Peeking at data in tail... | ||
+ | |||
+ | The value in top of stack is 10 | ||
+ | |||
+ | Stack is not empty! | ||
+ | |||
+ | This node contains 10 | ||
+ | |||
+ | This node contains 9 | ||
+ | |||
+ | This node contains 8 | ||
+ | |||
+ | This node contains 7 | ||
+ | |||
+ | This node contains 6 | ||
+ | |||
+ | This node contains 5 | ||
+ | |||
+ | This node contains 4 | ||
+ | |||
+ | This node contains 3 | ||
+ | |||
+ | This node contains 2 | ||
+ | |||
+ | This node contains 1 | ||
+ | |||
+ | Making a copy of the stack... | ||
+ | |||
+ | Destroying the first Stack... | ||
+ | |||
+ | Stack is empty! | ||
+ | |||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | Printing values of copy of stack... | ||
+ | |||
+ | This node contains 10 | ||
+ | |||
+ | This node contains 9 | ||
+ | |||
+ | This node contains 8 | ||
+ | |||
+ | This node contains 7 | ||
+ | |||
+ | This node contains 6 | ||
+ | |||
+ | This node contains 5 | ||
+ | |||
+ | This node contains 4 | ||
+ | |||
+ | This node contains 3 | ||
+ | |||
+ | This node contains 2 | ||
+ | |||
+ | This node contains 1 | ||
+ | |||
+ | Copy of stack is not empty! | ||
+ | |||
+ | Destroying copy of the stack... | ||
+ | |||
+ | Copy of stack is empty! | ||
+ | |||
+ | Starting a new stack using push and a loop... | ||
+ | |||
+ | Enter the number of data to push onto the stack... | ||
+ | 3 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 1 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 2 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 3 | ||
+ | |||
+ | Head is = 0x3e2500; Tail is = 0x3e2530 | ||
+ | |||
+ | The size of the stack is: 3 | ||
+ | |||
+ | Enter the number of data to be popped off of the stack... | ||
+ | 3 | ||
+ | The value being popped off of the stack is 3 | ||
+ | The value being popped off of the stack is 2 | ||
+ | The value being popped off of the stack is 1 | ||
+ | |||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | The size of the stack is: 0 | ||
+ | |||
+ | C: | ||
+ | Press any key to continue . . . | ||
+ | </ | ||
+ | ** Execution of makeStack.sh (compilation, | ||
+ | <cli> | ||
+ | lab46: | ||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | Creating a fixed size stack of 10 nodes... | ||
+ | |||
+ | Head is = 0x22c9010; Tail is = 0x22c9130 | ||
+ | |||
+ | Size of the list is: 10 | ||
+ | |||
+ | Peeking at data in tail... | ||
+ | |||
+ | The value in top of stack is 10 | ||
+ | |||
+ | Stack is not empty! | ||
+ | |||
+ | This node contains 10 | ||
+ | |||
+ | This node contains 9 | ||
+ | |||
+ | This node contains 8 | ||
+ | |||
+ | This node contains 7 | ||
+ | |||
+ | This node contains 6 | ||
+ | |||
+ | This node contains 5 | ||
+ | |||
+ | This node contains 4 | ||
+ | |||
+ | This node contains 3 | ||
+ | |||
+ | This node contains 2 | ||
+ | |||
+ | This node contains 1 | ||
+ | |||
+ | Making a copy of the stack... | ||
+ | |||
+ | Destroying the first Stack... | ||
+ | |||
+ | Stack is empty! | ||
+ | |||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | Printing values of copy of stack... | ||
+ | |||
+ | This node contains 10 | ||
+ | |||
+ | This node contains 9 | ||
+ | |||
+ | This node contains 8 | ||
+ | |||
+ | This node contains 7 | ||
+ | |||
+ | This node contains 6 | ||
+ | |||
+ | This node contains 5 | ||
+ | |||
+ | This node contains 4 | ||
+ | |||
+ | This node contains 3 | ||
+ | |||
+ | This node contains 2 | ||
+ | |||
+ | This node contains 1 | ||
+ | |||
+ | Copy of stack is not empty! | ||
+ | |||
+ | Destroying copy of the stack... | ||
+ | |||
+ | Copy of stack is empty! | ||
+ | |||
+ | Starting a new stack using push and a loop... | ||
+ | |||
+ | Enter the number of data to push onto the stack... | ||
+ | 3 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 1 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 2 | ||
+ | |||
+ | Enter the value to be pushed onto the stack... | ||
+ | 3 | ||
+ | |||
+ | Head is = 0x22c9150; Tail is = 0x22c9190 | ||
+ | |||
+ | The size of the stack is: 3 | ||
+ | |||
+ | Enter the number of data to be popped off of the stack... | ||
+ | 3 | ||
+ | The value being popped off of the stack is 3 | ||
+ | The value being popped off of the stack is 2 | ||
+ | The value being popped off of the stack is 1 | ||
+ | |||
+ | Head is = 0x0; Tail is = 0x0 | ||
+ | |||
+ | The size of the stack is: 0 | ||
+ | lab46: | ||
+ | </ | ||
+ | \\ | ||
+ | **Addition of the stack library and test file to the Subversion repository.**\\ | ||
+ | <cli> | ||
+ | lab46: | ||
+ | A Stack | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A | ||
+ | A (bin) Stack/ | ||
+ | A | ||
+ | A | ||
+ | A (bin) Stack/ | ||
+ | lab46: | ||
+ | lab46: | ||
+ | A (bin) libdll.a | ||
+ | lab46: | ||
+ | A (bin) copyStack.o | ||
+ | A (bin) createFixedStack.o | ||
+ | A (bin) destroyFixedStack.o | ||
+ | A (bin) isEmpty.o | ||
+ | A (bin) listStackSize.o | ||
+ | A (bin) peek.o | ||
+ | A (bin) pop.o | ||
+ | A (bin) push.o | ||
+ | lab46: | ||
+ | svn: warning: ' | ||
+ | lab46: | ||
+ | </ | ||
+ | <cli> | ||
+ | **Comital of stack library and test file to the Subversion repository.**\\ | ||
+ | lab46: | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Adding | ||
+ | Transmitting file data ................................ | ||
+ | Committed revision 14. | ||
+ | lab46: | ||
+ | </ | ||
+ | **Added all.h to the Subversion repository** | ||
+ | <cli> | ||
+ | lab46: | ||
+ | </ | ||
+ | **Added all.h to the Subversion repository** | ||
+ | <cli> | ||
+ | lab46: | ||
+ | </ | ||
+ | **Added other files to the repository** | ||
+ | <cli> | ||
+ | lab46: | ||
+ | </ | ||
+ | <cli> | ||
+ | lab46:~$ svn commit -m " | ||
+ | </ | ||
+ | **Cleaned up stack library files** | ||
+ | <cli> | ||
+ | lab46: | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Sending | ||
+ | Transmitting file data .............. | ||
+ | Committed revision 22. | ||
+ | lab46: | ||
+ | </ | ||
+ | ======Reflection====== | ||
+ | I learned to use a single .h file to prototye all of my functions and the node structure for all of my library files. Below is a record of the steps I went through to get there.\\ | ||
+ | I successfully created and used a static linked list library, or so I thought, when I finalized my linked list project. However, when it came to implementing a static library of stack routines and associated data type, I had a horrible time. every library file wanted a node structure in it however when I linked the library files together, I got error messages! I had to figure out a way to have only one node struct reference that I could share with the library files. I appealed to the instructor for help! | ||
+ | <cli> | ||
+ | Date: Wed, 12 Oct 2011 19:54:26 -0400 (EDT) | ||
+ | From: John Rine < | ||
+ | To: wedge@lab46.corning-cc.edu, | ||
+ | Subject: static library HELP!!!!! | ||
+ | |||
+ | I am trying to finish my stack library and mange all the crap going on in my personal life and it ain't going very good. | ||
+ | I think I got lucky compiling and linking the linked List library. | ||
+ | I am having a time with the stack. I took a different approach with it. | ||
+ | I am having many library files with names describing the functions inside. | ||
+ | For example: | ||
+ | createFixedStack.c createFixedStack.h | ||
+ | listStackSize.c | ||
+ | listStackSize.h | ||
+ | destroyFixedStack.c | ||
+ | destroyFixedStack.h | ||
+ | |||
+ | I also have a test program named: | ||
+ | stackTest.c | ||
+ | |||
+ | please look closely at the #include " | ||
+ | What am I doing wrong????? | ||
+ | I can't find any good examples on the Internet. My issues are compounded by having a struct. please look closely at how the struct is included in the includes. | ||
+ | |||
+ | I took copious notes. From you class, I got: | ||
+ | main | ||
+ | #include " | ||
+ | how does " | ||
+ | I also got the following: | ||
+ | ar rcs libdll.a *.o | ||
+ | How does libdll relate to " | ||
+ | I am missing something!!!! | ||
+ | |||
+ | in stackTest.c I am declaring the individual .h files: | ||
+ | #include " | ||
+ | #include " | ||
+ | #include " | ||
+ | |||
+ | I successfully created .o files for these libraries using the following: | ||
+ | lab46: | ||
+ | lab46: | ||
+ | lab46: | ||
+ | |||
+ | Then I can successfully create a static library using: | ||
+ | lab46: | ||
+ | |||
+ | |||
+ | Code and includes | ||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | #ifndef _CREATEFIXEDSTACK_JR_H | ||
+ | #define _CREATEFIXEDSTACK_JR_H | ||
+ | |||
+ | # | ||
+ | # | ||
+ | |||
+ | struct Node | ||
+ | { | ||
+ | int data; | ||
+ | | ||
+ | | ||
+ | }; | ||
+ | |||
+ | typedef struct Node node; | ||
+ | |||
+ | |||
+ | void createFiixedStackList(node **, node **, int); | ||
+ | |||
+ | #endif | ||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | |||
+ | |||
+ | void createFixedStack(node **head, node **tail, int elements) | ||
+ | { | ||
+ | int i; | ||
+ | node *new; | ||
+ | new = NULL; | ||
+ | *head = *tail = NULL; | ||
+ | |||
+ | for(i = 1; i< | ||
+ | { | ||
+ | if (*head == NULL) | ||
+ | { | ||
+ | *head = (node *) malloc(sizeof(node)); | ||
+ | *tail = *head; | ||
+ | | ||
+ | | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | new = (node *) malloc(sizeof(node)); | ||
+ | | ||
+ | | ||
+ | | ||
+ | *tail = new; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | #ifndef _DESTROYFIXEDSTACK_JR_H | ||
+ | #define _DESTROYFIXEDSTACK_JR_H | ||
+ | |||
+ | # | ||
+ | # | ||
+ | |||
+ | struct Node | ||
+ | { | ||
+ | int data; | ||
+ | | ||
+ | | ||
+ | }; | ||
+ | |||
+ | typedef struct Node node; | ||
+ | |||
+ | |||
+ | void destroyFixedStackHead(node *); | ||
+ | void destroyFixedStackTail(node *); | ||
+ | |||
+ | #endif | ||
+ | |||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | # | ||
+ | # | ||
+ | #include " | ||
+ | |||
+ | void destroyFixedStackHead(node *head) | ||
+ | { | ||
+ | node *temp; | ||
+ | node *temp2; | ||
+ | temp = NULL; | ||
+ | temp2 = NULL; | ||
+ | temp = head; | ||
+ | | ||
+ | { | ||
+ | temp2 = temp-> | ||
+ | if (temp-> | ||
+ | if (temp-> | ||
+ | | ||
+ | temp = temp2; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void destroyFixedStackTail(node *tail) | ||
+ | { | ||
+ | node *temp; | ||
+ | node *temp2; | ||
+ | temp = NULL; | ||
+ | temp2 = NULL; | ||
+ | temp = tail; | ||
+ | | ||
+ | { | ||
+ | temp2 = temp-> | ||
+ | if (temp-> | ||
+ | if (temp-> | ||
+ | | ||
+ | temp = temp2; | ||
+ | |||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | #ifndef _LISTSTACKSIZE_JR_H | ||
+ | #define _LISTSTACKSIZE_JR_H | ||
+ | |||
+ | # | ||
+ | # | ||
+ | |||
+ | struct Node | ||
+ | { | ||
+ | int data; | ||
+ | | ||
+ | | ||
+ | }; | ||
+ | |||
+ | typedef struct Node node; | ||
+ | |||
+ | int listStackSizeHead(node *); | ||
+ | int listStackSizeTail(node *); | ||
+ | |||
+ | #endif | ||
+ | |||
+ | |||
+ | // | ||
+ | //John T. Rine | ||
+ | //October 12, 2011 | ||
+ | |||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int listStackSizeHead(node *head) | ||
+ | { | ||
+ | int size = 0; | ||
+ | while (head != NULL) | ||
+ | { | ||
+ | head = head-> | ||
+ | | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | |||
+ | int listStackSizeTail(node *tail) | ||
+ | { | ||
+ | int size = 0; | ||
+ | while (tail != NULL) | ||
+ | { | ||
+ | tail = tail-> | ||
+ | | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | // | ||
+ | //Author: John T. Rine | ||
+ | //Date: October 12, 2011 | ||
+ | |||
+ | |||
+ | #include " | ||
+ | #include " | ||
+ | #include " | ||
+ | |||
+ | int main(int argc, char **argv) | ||
+ | { | ||
+ | |||
+ | node *head, *tail; | ||
+ | head = tail = NULL; | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | However when I try to create the test executable, it bombs-HELP!!! | ||
+ | |||
+ | John T. Rine | ||
+ | |||
+ | Graduate Electrical Technology-Electronics | ||
+ | Graduate General Studies | ||
+ | --- | ||
+ | | ||
+ | </ | ||
+ | I finally figured that I could create a struct .h file to define the node structure and then include that .h file in my lother library files. Sure enough, it worked! | ||
+ | <cli> | ||
+ | Date: Thu, 13 Oct 2011 10:40:10 -0400 | ||
+ | From: Matthew Haas < | ||
+ | To: John Rine < | ||
+ | Subject: Re: static library HELP!!!!! (fwd) | ||
+ | On Oct 12, 2011, at 11:34 PM, John Rine wrote: | ||
+ | |||
+ | |||
+ | I got it. | ||
+ | The issue is that the structure used as a node is shared throughout all of the functions. When you break them up, you can't include the structure in | ||
+ | every .h file, so what you do is to creat e a structure.h file and include that in the broken up files. Its seems you also need it in the test file as | ||
+ | well. Man did that was driving me crazy.</ | ||
+ | </ | ||
+ | My instructor pointed out, however, that I could have simply made one .h file for all of my library files! Why didn't I think of that? | ||
+ | <cli> | ||
+ | Date: Thu, 13 Oct 2011 10:40:10 -0400 | ||
+ | From: Matthew Haas < | ||
+ | To: John Rine < | ||
+ | Subject: Re: static library HELP!!!!! (fwd) | ||
+ | Parts/ | ||
+ | | ||
+ | 2 Shown ~62 lines Text | ||
+ | ---------------------------------------- | ||
+ | |||
+ | |||
+ | On Oct 12, 2011, at 11:34 PM, John Rine wrote: | ||
+ | |||
+ | |||
+ | I got it. | ||
+ | The issue is that the structure used as a node is shared throughout all of the functions. When you break them up, you can't include the structure in | ||
+ | every .h file, so what you do is to creat e a structure.h file and include that in the broken up files. Its seems you also need it in the test file as | ||
+ | well. Man did that was driving me crazy. | ||
+ | |||
+ | |||
+ | John, | ||
+ | |||
+ | You may have appeared to resolve the issue, but I think the situation is still inordinately complex and can be simplified. | ||
+ | |||
+ | For your stack library, you should be able to get away with just 1 header file, let's call it: stack.h | ||
+ | |||
+ | stack.h can look as follows: | ||
+ | |||
+ | ------------------------------------- | ||
+ | #ifndef _STACK_H | ||
+ | #define _STACK_H | ||
+ | |||
+ | #include " | ||
+ | |||
+ | struct stack { | ||
+ | struct list *data; | ||
+ | struct node *top; | ||
+ | }; | ||
+ | typedef struct stack Stack; | ||
+ | |||
+ | Node *pop(Stack *); | ||
+ | int push(Stack *, Node *); | ||
+ | Node *peek(Stack *); | ||
+ | int isEmpty(Stack *); | ||
+ | |||
+ | #endif | ||
+ | ------------------------------------- | ||
+ | |||
+ | All your .c files can just #include " | ||
+ | you (the linkedlist.h file will similarly have #ifndef _LINKED_LIST_H guards). | ||
+ | |||
+ | With so many header files, the way you seem to be approaching it might be creating a lot more managerial work for yourself... let the preprocessor take care of it | ||
+ | for you. | ||
+ | |||
+ | Is this code on Lab46? I took a quick peek and couldn' | ||
+ | |||
+ | -Matthew | ||
+ | -- | ||
+ | Matthew Haas | ||
+ | Lab46 System Administrator | ||
+ | Instructor of Computer & Information Science | ||
+ | http:// | ||
+ | </ | ||
+ | ======References====== | ||
+ | In performing this project, the following resources were referenced: | ||
+ | |||
+ | * < | ||
+ | * < | ||
+ | * < | ||
+ | Copyright © 1993-2000 by Robert I. Pitts</ | ||
+ | * < | ||
+ | |||
+ | |