documentation:data
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
documentation:data [2011/10/05 11:00] – Editorial mcooper6 | documentation:data [2012/11/02 15:02] (current) – [Doubly Linked Lists] mcooper6 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | <WRAP left 40%> | ||
+ | ~~TOC~~ | ||
+ | </ | ||
+ | // | ||
+ | // | ||
+ | <WRAP centeralign 100% bigger> | ||
+ | <WRAP bigger fgred> | ||
+ | <WRAP muchbigger> | ||
+ | Observations | ||
+ | </ | ||
+ | <WRAP left 40%> | ||
+ | <WRAP right bgwhite> | ||
+ | </ | ||
+ | </ | ||
+ | <WRAP clear></ | ||
+ | |||
+ | =====Data Types===== | ||
+ | <WRAP bigger fgred> | ||
+ | |||
+ | While the basic components of data structures are the stacks, linkages and sorted piles of these built-in storage spaces, it is the algorithms that are used to implement and traverse these structures that make the topic so special to computer scientists around the world. | ||
+ | |||
+ | <WRAP bigger fgred>A known amount of storage space with known characteristics.</ | ||
+ | |||
+ | |||
+ | |||
+ | While the concept of a data type is usually applied to programming languages, the idea comes from the way humans commonly interact with data. We are able to apply certain lessons (I.E. common sense) to the information we receive, and therefore make decisions on how we manipulate it. However, one of the primary pitfalls of modern computing is that that computers do not have common sense. | ||
+ | |||
+ | ====Problem 1: Interchangability==== | ||
+ | |||
+ | Given a number (use 4), a letter (use R) and a 3rd grade education, it should be immediately apparent that these two pieces of data are not necessarily interchangable. | ||
+ | |||
+ | By assigning a type to the data, common interactions are made more predictable. | ||
+ | |||
+ | <WRAP info round> | ||
+ | Data types are everywhere: | ||
+ | |||
+ | The scream of a $1 million lottery winner is quite different from that of a person who is running from an axe murderer. | ||
+ | </ | ||
+ | |||
+ | |||
+ | ====Problem 2: Storage Space==== | ||
+ | |||
+ | Just like a storage facility owner, a computer assigns memory in the order that requests are received, based upon the expected size of the data. However, the key difference between the storage facility and the computer lies in the way they each deal with overflow. | ||
+ | |||
+ | The most common of the simple types are: | ||
+ | |||
+ | *Integer data type (int); typically used to store values between -2, | ||
+ | *Character data type (char); used to store single characters of data | ||
+ | *Boolean data type (bool); used to store a single bit, true or false | ||
+ | |||
+ | Each simple data type has a domain of possible values (certainly finite), and is assigned a finite amount of space (in memory) that it may occupy. | ||
+ | |||
+ | =====Pointers===== | ||
+ | |||
+ | The pointer data type is slightly different than typical simple data types, in that the domain of the pointer data type is the the list of all the memory addresses in the computer. | ||
+ | |||
+ | < | ||
+ | // Create a pointer to a memory location large enough | ||
+ | // to store an integer value | ||
+ | |||
+ | int i; | ||
+ | int *intPtr; | ||
+ | |||
+ | // pointer is created, but is not pointing to a memory location yet | ||
+ | |||
+ | intPtr = i; | ||
+ | |||
+ | // intPtr is now pointing to the memory location where i resides | ||
+ | |||
+ | char *charPtr; | ||
+ | charPtr = (char *) malloc(sizeof(char)*100); | ||
+ | |||
+ | // charPtr points to a memory block that is the size of 100 characters | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | This relationship between the pointer and its pointee is the key characteristic that makes pointers a valuable programming tool across multiple implementations. | ||
+ | |||
+ | ====Reference & Dereference==== | ||
+ | |||
+ | A major problem with pointers arises when a value is extracted from a pointer variable, that is, the pointer variable contains a memory address, not the value stored at the memory address ... (I’d say, if we can’t ever get the value, this whole exercise is useless). | ||
+ | |||
+ | ====Memory Allocation==== | ||
+ | |||
+ | The concept of a pointer is to place a known marker at the beginning of a given storage space, and from there, calculate the end location based upon the type of the data placed there. | ||
+ | For example, the following C code creates a new pointer to the beginning of a character, and then allocates the amount of memory required by the input from the command line: | ||
+ | < | ||
+ | |||
+ | char *str; | ||
+ | str= (char*) malloc(sizeof(char)*strlen(argv[i])); | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====Side Note: Buffer Overflows==== | ||
+ | |||
+ | C and C++ are high level languages that assume that the programmer is in control of data, both in the form of variables, and user generated input. | ||
+ | |||
+ | < | ||
+ | |||
+ | #include < | ||
+ | |||
+ | int main(int argc, char *argv[]) { | ||
+ | |||
+ | char str1[8]; | ||
+ | int buffer=0; | ||
+ | |||
+ | if(argc < 2){ | ||
+ | printf(" | ||
+ | exit(1); | ||
+ | } | ||
+ | |||
+ | strcpy(str1, | ||
+ | |||
+ | printf(" | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | |||
+ | The above code creates a char array of size 8, which is allocated one byte for each element in the array, or 8 bytes. | ||
+ | <cli> | ||
+ | :~$ g++ -o char_array char_array.c | ||
+ | :~$ ./ | ||
+ | str1 contains 12345678 and buffer contains 0 | ||
+ | </ | ||
+ | |||
+ | Everything seems to be in order. | ||
+ | |||
+ | <cli> | ||
+ | :~$ ./ | ||
+ | str1 contains 12345678 and buffer contains 57 | ||
+ | |||
+ | :~$ ./ | ||
+ | str1 contains 12345678 and buffer contains 12345 | ||
+ | </ | ||
+ | |||
+ | This is an example of a buffer overflow. | ||
+ | |||
+ | =====Records & Structs===== | ||
+ | |||
+ | <WRAP bigger fgred>A series of known amounts of storage space.</ | ||
+ | |||
+ | If primitive data types can be likened to building out, then records and structs may be likened to building up. Simple data types take care of some very broad problems in computing, and most computational problems can be solved by simply instantiating and initializing one piece of data at a time. However, this method is not practical in every situation, specifically when vast quantities are required. | ||
+ | |||
+ | A record (implemented as a struct in C programming) allows an entirely new data type to be created based upon other, “smaller”, | ||
+ | |||
+ | ====The Basics==== | ||
+ | **A struct representing a major city might look like this:** | ||
+ | |||
+ | < | ||
+ | |||
+ | struct city { | ||
+ | |||
+ | int population; | ||
+ | char *name; | ||
+ | char *county; | ||
+ | char *state; | ||
+ | |||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | Now a single call reserves a memory location big enough to store an integer and three character pointers. | ||
+ | For example, creating a structure for 3 cities: | ||
+ | |||
+ | < | ||
+ | |||
+ | // instantiate a copy of the data type for each city | ||
+ | |||
+ | struct city Cleveland; | ||
+ | struct city Boston; | ||
+ | struct city Ithaca; | ||
+ | </ | ||
+ | |||
+ | A struct containing two different types of data, (this example contains both pointer and integer data) demonstrates the differences between the simple data types and the more complex types like pointers and structs. | ||
+ | |||
+ | < | ||
+ | |||
+ | Cleveland.population = 444,313; | ||
+ | Boston.population = 590,763; | ||
+ | Ithaca.population = 28,829; | ||
+ | |||
+ | </ | ||
+ | |||
+ | However, since each character pointer is simply a memory location, a known amount of storage space must be reserved before assigning values: | ||
+ | |||
+ | < | ||
+ | |||
+ | // Allocate enough memory to store 50 characters each | ||
+ | |||
+ | Cleveland.name | ||
+ | Boston.name = (char) malloc(sizeof(char)*50); | ||
+ | Ithaca.name = (char) malloc(sizeof(char)*50); | ||
+ | |||
+ | Cleveland.county = (char) malloc(sizeof(char)*50); | ||
+ | Boston.county = (char) malloc(sizeof(char)*50); | ||
+ | Ithaca.county = (char) malloc(sizeof(char)*50); | ||
+ | |||
+ | // Allocate enough memory to store 2 characters each | ||
+ | |||
+ | Cleveland.state = (char) malloc(sizeof(char)*2); | ||
+ | Boston.state = (char) malloc(sizeof(char)*2); | ||
+ | Ithaca.state = (char) malloc(sizeof(char)*2); | ||
+ | |||
+ | </ | ||
+ | |||
+ | Now that a storage space has been carved out, values may be assigned to each member: | ||
+ | |||
+ | < | ||
+ | // Assign values to each member field | ||
+ | |||
+ | Cleveland.county = “Cuyahoga”; | ||
+ | Cleveland.state = “OH”; | ||
+ | |||
+ | Boston.county = “Cuyahoga”; | ||
+ | Boston.state = “MA”; | ||
+ | |||
+ | Ithaca.county = “Tompkins”; | ||
+ | Ithaca.state = “NY”; | ||
+ | </ | ||
+ | |||
+ | Members are accessed via extended dot notation, in the same manner that values are assigned: | ||
+ | < | ||
+ | |||
+ | // print out some info | ||
+ | |||
+ | printf(“ %s has %d people.”, Cleveland.name , Cleveland.population); | ||
+ | printf(“ %s has %d people.”, Boston.name , Boston.population); | ||
+ | printf(“ %s has %d people.”, Ithaca.name , Ithaca.population); | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====Pointers to Structs==== | ||
+ | As previously mentioned, pointers do not contain a data value, instead they contain memory addresses. | ||
+ | |||
+ | < | ||
+ | |||
+ | struct city* Buffalo; | ||
+ | |||
+ | // dereference the pointer to the struct | ||
+ | // access members via extended dot notation | ||
+ | |||
+ | (*Buffalo).population = 276059 | ||
+ | |||
+ | |||
+ | // Allocate enough memory to store characters | ||
+ | (Buffalo).name | ||
+ | |||
+ | // shorthand access using -> | ||
+ | Buffalo -> county = (char) malloc(sizeof(char)*50); | ||
+ | Buffalo -> state = (char) malloc(sizeof(char)*2); | ||
+ | |||
+ | </ | ||
+ | |||
+ | =====Linked Lists===== | ||
+ | <WRAP bigger fgred> | ||
+ | Cleverly aligned structs | ||
+ | </ | ||
+ | |||
+ | Pointing to the memory location of a struct is clever, and greatly enhances a programmer’s ability create new data types. | ||
+ | |||
+ | In contrast, consider a dynamic list with the capability of inserting values into, and removing values from the list at a given point. | ||
+ | |||
+ | Consider the definition of a “node” struct that includes a pointer to another instance of the struct: | ||
+ | |||
+ | < | ||
+ | |||
+ | struct node{ | ||
+ | |||
+ | int val; | ||
+ | struct node *next; | ||
+ | |||
+ | }; | ||
+ | |||
+ | typedef struct node Node; | ||
+ | |||
+ | // define a new “name” for the node for easier implementation | ||
+ | // instantiate new nodes with Node *start = (*Node) malloc(sizeof(*Node) | ||
+ | |||
+ | </ | ||
+ | |||
+ | Defining a struct in this manner, provides each list element with a member which consists of a pointer to the location of the next element in the list. Further, since it is possible to dynamically allocate memory on the fly, this implementation may be extended to hold any number of elements. | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start; | ||
+ | |||
+ | start = (*Node) malloc(sizeof(*Node)); | ||
+ | start -> val = 10; | ||
+ | |||
+ | start -> next = (*Node) malloc(sizeof(*Node)); | ||
+ | start -> next -> val = 11; //second element in the list | ||
+ | |||
+ | start -> next -> next = (*Node) malloc(sizeof(*Node)); | ||
+ | start -> next -> next -> val = 12; // third element in the list | ||
+ | |||
+ | // make the fourth element empty | ||
+ | start -> next -> next -> next = null; | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====Iteration==== | ||
+ | The previous lines instantiate a new linked list with three elements. | ||
+ | |||
+ | |||
+ | An iteration structure is needed to traverse the list to get to the '' | ||
+ | |||
+ | < | ||
+ | |||
+ | start = start -> next; // error | ||
+ | |||
+ | // oops! pointed start to the next element in the list | ||
+ | // first element is lost forever... not good, not good at all | ||
+ | |||
+ | </ | ||
+ | |||
+ | Therefore, another temporary pointer is needed to iterate through the list, pointing at each consecutive element at the list is traversed: | ||
+ | |||
+ | < | ||
+ | |||
+ | int i; | ||
+ | *Node tmp; | ||
+ | |||
+ | tmp = start; // point tmp to the beginning of the list | ||
+ | |||
+ | for(i = 0; i < 2; i++){ | ||
+ | |||
+ | // loop to get the third element | ||
+ | tmp = tmp -> next; | ||
+ | |||
+ | } | ||
+ | |||
+ | // prints 12 | ||
+ | |||
+ | printf(“The 3rd element is %d”, tmp -> val); | ||
+ | |||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | Iterating through the list in this manner keeps the initial pointer ('' | ||
+ | |||
+ | <WRAP help round bggrey> | ||
+ | Only loop twice? | ||
+ | </ | ||
+ | |||
+ | While this example is limited to getting a predefined value from a predefined struct, this concept may be extended to dynamically create lists based upon user input, allowing a user to choose a selected value to return. | ||
+ | |||
+ | ====Create==== | ||
+ | |||
+ | A new linked list may be created by adding elements to the end of the list as they are provided by a user or possibly from file input. | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start, *tmp; | ||
+ | |||
+ | int input = 0; | ||
+ | |||
+ | start = tmp = NULL; | ||
+ | |||
+ | do { | ||
+ | printf(" | ||
+ | scanf(" | ||
+ | |||
+ | if ((start == NULL) && (input != -1)) | ||
+ | { | ||
+ | start = (Node *) malloc (sizeof(Node)); | ||
+ | tmp = start; | ||
+ | tmp -> value = input; | ||
+ | tmp -> next = NULL; | ||
+ | } | ||
+ | else if (input != -1) | ||
+ | { | ||
+ | tmp -> next = (Node *) malloc (sizeof(Node)); | ||
+ | tmp = tmp -> next; | ||
+ | tmp -> value = input; | ||
+ | tmp -> next = NULL; | ||
+ | } | ||
+ | } while (input != -1); | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | In the previous C code snippit, '' | ||
+ | |||
+ | ====Insert==== | ||
+ | |||
+ | Once the list is built, the method for inserting values into a list differs slightly depending on the way the you turn your paradigm. | ||
+ | |||
+ | Inserting a value into a linked list before a selected index involves iterating through the list to find the target node one spot before the selected index. | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start, *tmp, *tmp2; | ||
+ | |||
+ | // ... create a list from start using previous method | ||
+ | |||
+ | int i = 0, input = 0; | ||
+ | |||
+ | tmp = start; | ||
+ | |||
+ | printf(" | ||
+ | scanf(" | ||
+ | |||
+ | for (i = 0; i < (input - 1); i++){ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> next; | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | if (input == 1){ | ||
+ | |||
+ | i++; | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | printf(" | ||
+ | scanf(" | ||
+ | |||
+ | // Create new node | ||
+ | tmp2 = (Node *) malloc (sizeof(Node)); | ||
+ | tmp2 -> value = input; | ||
+ | |||
+ | |||
+ | if (i != 0){ // anything but the first | ||
+ | |||
+ | tmp2 -> next = tmp -> next; | ||
+ | tmp -> next = tmp2; | ||
+ | |||
+ | }else{ // the first node | ||
+ | |||
+ | tmp2 -> next = result; | ||
+ | start = tmp2; | ||
+ | } | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | Inserting a value after a selected index requires one more iteration to find the target node at the selected index, and therefore doesn’t require a check for input of one or zero. | ||
+ | |||
+ | ====Delete==== | ||
+ | |||
+ | Remove an item from a linked list by iterating a temporary pointer to the memory location prior to the target node, setting it’s ‘‘next’’ pointer to the pointer after it’s current next pointer (in other words, ‘’tmp -> next -> next’’). | ||
+ | |||
+ | < | ||
+ | Node *start, *tmp, *tmp2; | ||
+ | |||
+ | int i = 0, input = 0; | ||
+ | |||
+ | start = malloc(sizeof(Node)); | ||
+ | |||
+ | // .. add elements to the list | ||
+ | |||
+ | tmp = start; | ||
+ | |||
+ | printf(" | ||
+ | scanf(" | ||
+ | |||
+ | for (i = 0; i < (input - 1); i++){ | ||
+ | tmp = tmp -> next; | ||
+ | } | ||
+ | |||
+ | if(input ==1){ | ||
+ | |||
+ | i++; | ||
+ | |||
+ | } | ||
+ | |||
+ | if (i != 0){ // anything but the first | ||
+ | |||
+ | tmp2 = tmp -> next; | ||
+ | tmp -> next = tmp2 -> next; | ||
+ | |||
+ | }else{ // the first node | ||
+ | |||
+ | tmp2 = start; | ||
+ | start = start -> next; | ||
+ | } | ||
+ | |||
+ | tmp2 -> next = NULL; | ||
+ | free(tmp2l); | ||
+ | |||
+ | </ | ||
+ | |||
+ | =====Doubly Linked Lists===== | ||
+ | <WRAP fgred bigger> | ||
+ | Once the linked list concept has been fully explored, a new limitation may be discovered. | ||
+ | |||
+ | < | ||
+ | |||
+ | struct node { | ||
+ | int value; | ||
+ | struct node *prev; | ||
+ | struct node *next; | ||
+ | }; | ||
+ | typedef struct node Node; | ||
+ | </ | ||
+ | |||
+ | The addition of a pointer to the previous element allows the program to now start at the beginning of a list and iterate toward the end, or start at the end and iterate toward the beginning (more interestingly, | ||
+ | |||
+ | ====Create==== | ||
+ | |||
+ | Further, only small modifications are needed to make the previous insert algorithm work with doubly linked lists : | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start, *tmp; | ||
+ | |||
+ | int input = 0; | ||
+ | |||
+ | start = tmp = NULL; | ||
+ | |||
+ | do { | ||
+ | printf(" | ||
+ | scanf(" | ||
+ | |||
+ | if ((start == NULL) && (input != -1)) { | ||
+ | |||
+ | start = (Node *) malloc (sizeof(Node)); | ||
+ | tmp = start; | ||
+ | tmp -> value = input; | ||
+ | tmp -> next = NULL; | ||
+ | tmp -> prev = START; | ||
+ | |||
+ | } else if (input != -1) { | ||
+ | |||
+ | tmp -> next = (Node *) malloc (sizeof(Node)); | ||
+ | tmp -> value = input; | ||
+ | tmp -> next -> next = NULL; | ||
+ | tmp -> next -> prev = tmp; | ||
+ | |||
+ | } | ||
+ | } while (input != -1); | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | The previous C code snippet creates subsequent nodes, linking each to their next and previous neighbors in the list. Additionally, | ||
+ | |||
+ | ====Delete==== | ||
+ | |||
+ | Removing an element from a doubly linked list is only slightly different than dealing with singly linked lists. | ||
+ | |||
+ | < | ||
+ | |||
+ | target -> prev -> next = target -> next; | ||
+ | target -> next -> prev = target -> prev; | ||
+ | |||
+ | free(target); | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | =====Stacks & Queues===== | ||
+ | <WRAP bigger fgred>A whole new concept</ | ||
+ | |||
+ | |||
+ | The concept of stacks and queues are implemented in the same manner as a linked list. Each element in the list (I.E. each struct) contains a pointer to the next element in the list (each may also contain a ‘‘prev’’ pointer). | ||
+ | |||
+ | Consider the concept of the inbox on a receptionist’s desk. The bin may start the day empty, and as new jobs are added to the receptionist’s list, a decision must be made as to the priority given to each task. In many cases, this is a decision that may be made via algorithm. | ||
+ | |||
+ | ====FIFO==== | ||
+ | |||
+ | <WRAP fgred bigger> | ||
+ | |||
+ | The receptionist may choose to accomplish tasks in the bin in the order that they are received. | ||
+ | |||
+ | <WRAP info round bggrey> | ||
+ | The concept of a queue may be more easily associated with the common sense of a dispenser, in that items placed in the top are dispensed at the bottom. | ||
+ | </ | ||
+ | |||
+ | Inserting nodes into a queue requires iteration to the end of the list. Setting the end node’s next value to the newly created node. | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start, *tmp; | ||
+ | |||
+ | // .. malloc start ... create first node | ||
+ | |||
+ | tmp = start; | ||
+ | |||
+ | while( tmp -> next != NULL){ | ||
+ | |||
+ | tmp = tmp -> next; | ||
+ | |||
+ | } | ||
+ | |||
+ | // tmp is now pointing to the end of the list | ||
+ | |||
+ | tmp -> next = malloc(sizeof(Node)); | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | In this regard, adding elements to the end of a stack can be made cheaper by adding a second node, and pointing it at the last element in the list. | ||
+ | |||
+ | Removing nodes from the list requires removing the ‘‘start’’ pointer, and pointing the start pointer to the next element in the list all at the same time: | ||
+ | |||
+ | < | ||
+ | |||
+ | Node *start, *tmp; | ||
+ | //.. create the queue and fill it with values | ||
+ | tmp = start; | ||
+ | start = start -> next; | ||
+ | tmp -> next = NULL; | ||
+ | free(tmp) | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====LIFO==== | ||
+ | <WRAP fgred bigger> | ||
+ | In contrast to //first in, first out//, the receptionist may choose a new job directly from the top of the pile, or, let’s call it a **// | ||
+ | |||
+ | <WRAP info round bggrey> | ||
+ | **push() and pop()**: Tradition dictates that names like push and pop are used to describe the process of adding an element to the stack (push) and removing and element from the stack (pop). | ||
+ | </ | ||
+ | |||
+ | ====Implementation==== | ||
+ | |||
+ | In the most practical sense, stacks and queues differ from linked lists only in their precise control over adding new nodes to the list and removing nodes from the list. However, consider that the implementation must choose which end is up is up. For example, a stack can have items added to, and removed from it’s beginning. | ||
+ | |||
+ | =====Trees===== | ||
+ | |||
+ | <WRAP fgred bigger> | ||
+ | |||
+ | Stacks and queues are perfect for many implementations, | ||
+ | |||
+ | An example tree node might look like this: | ||
+ | |||
+ | < | ||
+ | |||
+ | struct tnode { | ||
+ | int value; | ||
+ | struct tnode *right; | ||
+ | struct tnode *left; | ||
+ | }; | ||
+ | typedef struct node TNode; | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | This type of relationship could be implemented in a way that is similar to using the '' | ||
+ | The tree data structure instead contains member pointers labeled '' | ||
+ | |||
+ | <WRAP help bggrey round> | ||
+ | Why Binary Trees? | ||
+ | |||
+ | When searching for values in a long list, binary trees quickly reduce the data set. Consider a list containing 150,000 numbers. | ||
+ | </ | ||
+ | |||
+ | |||
+ | ====Insert==== | ||
+ | In the number example, if a value is less than the root node’s value it is placed to the left. If the new value is greater, it is placed to the right. | ||
+ | |||
+ | < | ||
+ | |||
+ | TNode *root, *tmp; | ||
+ | |||
+ | // a root node with a value of 75000 | ||
+ | |||
+ | root = malloc(sizeof(TNode)); | ||
+ | root -> right = NULL; | ||
+ | root -> left = NULL; | ||
+ | root -> value = 75000; | ||
+ | |||
+ | while(tmp -> right != NULL && tmp -> left != NULL){ | ||
+ | |||
+ | if(v > tmp -> value){ | ||
+ | |||
+ | if( tmp -> right != NULL){ | ||
+ | |||
+ | //go right | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | } | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | if( tmp -> left != NULL){ | ||
+ | |||
+ | //go left | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | // tmp is pointing to the correct position | ||
+ | // set the new value | ||
+ | |||
+ | if(v > tmp -> value){ | ||
+ | |||
+ | tmp -> right = malloc(sizeof(TNode)); | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | tmp -> left = malloc(sizeof(TNode)); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====Delete==== | ||
+ | |||
+ | Removing values is a little more complex: | ||
+ | |||
+ | < | ||
+ | |||
+ | TNode *root, *tmp; | ||
+ | |||
+ | // ..insert values into the list | ||
+ | |||
+ | tmp = root; | ||
+ | |||
+ | while(tmp -> right != NULL && tmp -> left != NULL){ | ||
+ | |||
+ | if(v > tmp -> value){ | ||
+ | |||
+ | if( tmp -> right != NULL){ | ||
+ | |||
+ | //go right | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | } | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | if( tmp -> left != NULL){ | ||
+ | |||
+ | //go left | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | //tmp is pointing to the target to be removed | ||
+ | |||
+ | if(tmp -> left == NULL && tmp -> right == NULL){ | ||
+ | |||
+ | /* | ||
+ | This is the case of the end of a tree branch | ||
+ | check here to find if the parent’s value is greater | ||
+ | or less than the value of the temporary pointer | ||
+ | |||
+ | if true, iterate to the parent and set it’s left to NULL | ||
+ | if false, iterate to the parent and set it’s right to NULL | ||
+ | */ | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | |||
+ | /* | ||
+ | |||
+ | this is the case of a value with one or more | ||
+ | nodes left or right of it in the list | ||
+ | |||
+ | if the parent node of tmp is greater than tmp -> value | ||
+ | then iterate to the parent’s extreme left and set that | ||
+ | left side node to tmp -> right and then tmp -> right to tmp -> left | ||
+ | |||
+ | else iterate to the parents extreme right and set that left side | ||
+ | to tmp -> right and tmp -> right -> left to tmp -> left | ||
+ | */ | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | ====Search==== | ||
+ | As you can see, iterating through the list is pretty much the same every time. Therefore, a simple search algorithm is born: | ||
+ | |||
+ | < | ||
+ | tmp = root; | ||
+ | |||
+ | while(tmp -> right != NULL && tmp -> left != NULL){ | ||
+ | |||
+ | if(v > tmp -> value){ | ||
+ | |||
+ | if( tmp -> right != NULL){ | ||
+ | |||
+ | //go right | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> right; | ||
+ | |||
+ | } | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | if( tmp -> left != NULL){ | ||
+ | |||
+ | //go left | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | }else{ | ||
+ | |||
+ | // | ||
+ | tmp = tmp -> left; | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | //tmp is pointing to the target | ||
+ | |||
+ | </ |