Differences

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

--- blog:fall2015:cmille52:journal [2015/10/22 14:22] – [Oct. 22nd 2015] cmille52
+++ blog:fall2015:cmille52:journal [2015/12/03 15:29] (current) – [Dec. 3rd 2015] cmille52
@@ Line 215: / Line 215: @@
 Working on swapnode:
-      Use cpnode,obtain and insert to control the two nodes that you want to swap...
-      By making a copy of item1 and setting it to a tmp pointer we can insert tmp into into the place of item1. Next by taking the address of item1 and will insert item1 into the place of item 2. Now, taking the address of item2 we will put item2 where the tmp variable is...successfully swapping the two nodes.
+Use cpnode,obtain and insert to control the two nodes that you want to swap...
+By making a copy of item1 and setting it to a tmp pointer we can insert tmp into into the place of item1. Next by taking the address of item1 and will insert item1 into the place of item 2. Now, taking the address of item2 we will put item2 where the tmp variable is...successfully swapping the two nodes.
 Working on sort list:
-      For sort list, we want to cycle through the list evaluating the 'info' contained in every node. Once we arrive on node 'info' that is smaller than the first node 'info' in the list we will swap that node with the first node...This would place the smaller 'info' in order to the first node. This can be set up into a loop until the entire list has gone through and the search arrives at NULL. I must check for empty list, NULL list and if there are two of the same nodes in the list which would be an obvious issue...
+For sort list, we want to cycle through the list evaluating the 'info' contained in every node. Once we arrive on node 'info' that is smaller than the first node 'info' in the list we will swap that node with the first node...This would place the smaller 'info' in order to the first node. This can be set up into a loop until the entire list has gone through and the search arrives at NULL. I must check for empty list, NULL list and if there are two of the same nodes in the list which would be an obvious issue...
+===Oct. 27th 2015===
+Sll3 and Sll4 coming due!
+New update for SLL3
+Insert-append and attain are either adding or subtracting a node list.
+Introduction to new project list: Moving on from singly linked lists
+-Cant go back through list with singly list
+-With doubly you can simply go back
+-Involves re-use of previous functions
+Node now has prior and after arrow
+     ex. myList
+        [first]
+        [     ]
+        [last]
+Data in node is now called "VALUE"
+Each list type has their best used scenario in the real world.
+*DLLN0 Project*
+-No code from previous projects will migrate over
+-Upgrade at any time
+-Similar to SLN0
+-Similar file structure from what we've been using
+. Under inc dir.
+    a)Node.h
+.Payload
+.Including data.h
+.Node declartation
+.Function prototypes at the bottom
+.Difference from singly linked projects. Types of status codes...
+.This project is too different to use any previously written code.
+    b)Data.h
+. Includes stdlib.h
+.union becomes payload...union contains char(value),struct (node * data), void (*other)
+              -Exposing yourself to union will help in future code.
+              -Union has the same structure as a struct
+              -Only allocates memory for the max size of struct contents
+              -Only one member should be used at any given time
+              -Mostly will only be using the value element
+              -Struct value allows usual data to be put in nodes
+              -Struct data allows you to point a node at another node
+              -Struct void allows you to point nodes at all types of thing...they become a structuring element per say.
+.Define statements allow for easier use of value, data and other
+.NULL is the number 0, however, NULL has to be a raw collection of zeroes, or a raw memory zero.
+              -Has a different signature than an int, because it is a memory zero
+.typedef make our code easier to write.
+.Status codes
+               -unique codes for various situations
+               -8 hex values for the 8 different codes
+               -You will want to or the the lists of binary in order to return more than one status code
+     c)support.h
+. Allows you to not have all the list functions online when you are doing unit tests. Turns the status codes into english statements.
+     d)cp.c
+.You aren't duplicating the node, you are copying the pointers and pointing them to what the original node was pointing at.
+     e)rm.c
+.
+* DLL0 Project *
+Turning your doubly node linked list into a doubly linked list
+Need to finish dln0 first
+Find function replaces search.
+New list struct in list.h
+Also, there is a set of new status codes in list.h for the doubly linked list
+Display function must be able to handle all 4 of the modes.
+wemux === Oct. 29th 2015 ===
+Doubly linked Lists:
+->Difference from singly; we have a prior place (no get pos, set pos, no counting other than in display); Payload, a union or struct that takes up less memory. Has several modes such as value (unsigned char), data (Node *) and other (void *); Value stores number, and payload can store node pointer.  Prior, after and payload are all 8 bytes. Struct is the sum total of all the pieces...
+If we had a node * and allocated it, a node would exist, tmp would point to it, prior and after would point towards NULL. The "." allows you access sub members. Ex. tmp -> payload.value
+But thanks to us deserving nice things we can just type tmp -> VALUE.
+->DLL0: List struct,first and last node pointers, and need to be mindful of the after and prior pointers. Set of 6 operations:
+-Insert: Manipulate the pointers so that prior and after are always pointing to the right places.
+-Append: goes after stated node, the node you are inserting must be on it's own.  Use isolated nodes...
+-Mk list
+-Find
+-Display: Use logic to your advantage
+ DLN0 and DLL0 are due the same week
+=== Oct. 3 2015 ===
+DLL1 project coming due in one week
+-The re-iteration of SLL2 per function creation.
+-Taking stuff out
+-Change to data.h, new status codes
+-New functions:In order of implementation
+->Obtain, takes and isolates indicated node out of list. Many new status codes. Opposite of insert and append...When we dereference something such as a tmp variable, we are going into the address of that given location and getting the value. Passing by address and passing by address are different...passing by value copies the value used, where as passing by address passes an address. Essentially all we are doing is passing our pointer by address...we are adding a layer of "pointerness". If all else fails remember to put single * before subject. Be careful to use parenthesis correctly when applying pointer to something...it will glue the pointer to the right part of your statement.
+-> Obtain example code: for taking a node from the middle of the list.
+: tmp -> prior -> after = tmp -> after;
+: tmp -> after -> prior = tmp -> prior;
+: tmp -> prior = tmp -> after = NULL;
+Example of successful disconnection of node from list.
+-Empty function: Clears existing list of all nodes and is in an empty state after function is used
+-Rmlist function: Deallocates the list. Do not malloc anything in the rm function...don't just say (*oldlist) = NULL
+-Compare function: Need obtain, empty and rmlist for compare. Works largely the same as compare from singly...
+-Swap function: Similar to swap, we arranging the node in the list.
+-sortlist function: sort existing list based on specific modes.
+Extra credit opportunity: Palindrome
+=== Nov 5th 2015 ===
+The last single digit class of November :O
+Work should be started on DLL1...
+Dll2 & DLS0 are coming...Dll2 is similar to SLL3 and DLS0 adds to the previously made functions.
+Currently working on DLN0 and DLL0...getting use to using a prior node to go through list inserting,obtaining, adding, and deleting nodes as required.Using the status codes to show different states of the code is proving difficult with one return statement.
+Info on using a double pointer:
+What can pointers point to? Ints, chars, addresses, other pointers...
+A simple declaration of a pointer to a pointer might be int **tmp...this says that there are two levels of pointers present.However in the DLL projects we only need to use one * thanks to the node.h stuct definition. In order to get the data at a given pointer address we would need to use &. For example:
+       int a = 5, b = 6; c = 7;
+       int **tmp;
+       int *tm1 = &i; tmp = &tm1; Gets the value at address
+Double pointers are best used in linked lists!
+To jump ahead a little, what is a stack:
+=== Nov. 10th 2015 ===
+DLL2 and SLL3 share some similarities...Both have you adding a quantity to your list structure.
+Must modify insert, append and obtain to work with a quantity.
+Also, there will be an upgrade to issue to the display function...adding four additional modes through two different toggles.
+These two items are the work that needs to be done on DLL2
+Paired with Dll2 is DLS0
+End of course experience( should be several small projects, likely 3 ) which will come due 3 weeks after break week...
+DLS0: Doubly linked stacks...
+What are stacks? A data structure where the data put into it last will be the first to come out...Filo(First in last out) or Lifo(Last in first out). A stack naturally reverses the list based on original stack input. When you call a function, the computer puts the address of the program counter in a stack and then moves back through the counter addresses to get back to first function call.
+A stack can be described as a restricted linked list.
+One reason we use stacks: Computers can only process one thing at a time...the computer uses stacks to pile up all of the work to be done and go through the stack in an ordered fashion...which is why we use stacks when the order matters to us.
+Stacks have two core operations: Push items on, and pop items off.
+Empty stack, stack of one, stack of two. Push will adjust the top pointer to make sure it's on the list first.
+Peak or is empty are often associated with a stack. "Peak" just checks the list contents. "Is empty" checks the stack for being empty.
+There are two conditions associated with a stack that are different than a list: Bounded stack (put a limit on the elements in the stack that you can push)if you try to push more than the stack will allow you have a "stack overflow". An unbounded stack (No limit on elements you can push)or a stack set to 0. If you have an empty stack you cannot pop any of the elements(a stack underflow).
+Since we are adding this on top of the singly linked list we don't need to implement a huge amount of code.
+"Advantages come with limitation" Haas quote of the day
+=== Nov. 12th 2015 ===
+Indenting? Be sure to have a standard way that YOU indent throughout your programs. Improper indentation can get in the way and cause errors...Indenting makes the code more readable for reviewing and finding the errors in your code. Common thing to be seeing in this class was tmp=cplist(tmp2); which essentially ruins whatever process that was taking place.
+Week 11 is upon us...
+Stack will be the first in-all use of our singly linked list programs. Should be shorter because we aren't building the list but rather letting stack manage the list. This goes for cue as well...both should be a break kinda situation...shorter code.
+Test-reference will be provided so we can focus solely on the new code at hand.
+Dll2 and Dls0 are coming due in one week.
+=== Nov. 17th 2015 ===
+Dll2 and Dls0 are in progress...due before tomorrow is no longer tomorrow.
+Last weekly project DlQ0: Focuses on a popular data structure known as a cue. Cues and stacks will be found everywhere...the best algorithms come from nature, stacks represent one way things happen. Good example of a stack is memory in how we retrieve memories based on the date on which we remembered, such as last in first out. Cues are the opposite of this, last in first out. Also known as FIFO...A stop light is a cue...when you are waiting at a given road signal, you are in a cue. We don't ever lose our place at a given cue point, the order is preserved. Same application for standing in line at a given convenience store...in computing, a queue is a list of data items that is retrievable based on order of insertion. A buffer is another identical definition for a queue...queues are built on top of lists which are built on nodes. The queue project and stack project should seem familiar. Both involve placing restrictions on the stack and queue...in a stack we remove them from the front of the stack. For a queue we remove data items from the back of the queue. Queues may offer better performance because you don't need to check for as much.
+There is a back and front to a queue...a pointer for each position that changes based on the removal of data items from the queue. Responsibilities to keep track of front and back of queue. To put something on the cue we en-queue it, to remove something we de-queue it.
+In DLQ0:
+queue.h, similar abilities to a stack just built for removing data items from the back of queue instead of front of stack.
+data.h, set of dlq status codes are new.
+mkqueue, deals with allocating and creating a new queue
+copyqueue, copy stack is same concept
+rmqueue, deallocate the queue. Helper function is purge
+purgequeue, empties an existing queue.
+enqueue, add new node onto the queue from the back. Should be using list operations...
+dequeue, takes off node from the front of queue.
+dll2 is fairly simple because you have a large amount of time to mess around with display. There is a logical way to come up with Dll2. Extra credit opportunity...
+Dls0 should be less complex. Extra credit opportunity
+=== Nov. 19th 2015 ===
+DLS0 due date has been delayed till after break week...
+A few significant notices:
+What do the stack and queue systems look like? A list of sorts
+In the stack there are three pointers...top, data, and size.
+Top is the first and last of a stack...we are responsible to set top to the right position in the list. Data will point to a list struct {first, last, qty). Size and qty differ...think of a fuel tank and fuel in that tank. We typically visualize stacks as being vertical.
+For queues, there is a 'front' and a 'back' that work like first and last...'data' is the the list that we have attached to the que.'Buffer' is the space we are giving the que for the qty in our list.
+Is it possible to point to a list of lists? Yes, we have a void pointer in a node that allows us to point the list to anything we want, lists, a que, stack? you name it.
+Example of the craziness that can be done by using the void pointers: MyQue -> data -> last -> prior -> (List *) other -> first -> (stack *)OTHER -> top -> VALUE.
+To best solve What are some other data structures?any given problem we have, we should learn to be well versed in using advanced data structures.
+More info on what enqueue is in QUEUE: Enqueue determines the amount of space that is available in a given que for adding an element...if there is space enqueue will add and increment the appropriate pointers into the (which can be circular or horizontal.
+Dequeue  returns the current element from the head indexed pointer and increments the top pointer. With a cueue we aren't allowed to view values in the list out of order, everything is done in order. Some real world examples that use queues might be; a print queue, web server or instant messaging system. These all revolve around the data being received based on proper and chronological order.
+For a stack: First come, last served...
+The use of pop and push, push is used to add the passed in value to the start of the stack. Pop removes the top of the stack and increments the top pointer to the correct position based on the removal or addition of an element to the stack.
+A stack is best visualized in a vertical fashion...because of pop and push being typically associated with an upright object. An example of a stack being used would be, the stack call in C sharp.
+=== Dec. 1st 2015 ===
+End of course experience rules:
+Keep up with writing during progress...more possibility for success
+Implement stuff under your own supervision...your work...your success
+This is technically an evaluation of what I have learned so far
+Edit the EOCE wiki page, worth 24% of overall grade...
+broken up into 4 - 8% sections
+Submit by Dec. Thursday the 13th at 1:59 59 pm
+EOCE proper:
+The code will be done in EOCE.c project
+x0-Exercise in finding out what you, yourself believe concerning data structures and it's apparent influence on the universe.
+x1-Building a tree, add node function. There will be a test reference for everything but what we are building.
+x2-Traversing a tree. Traverse_S is the function we are implementing.Traverse I and Traverse R will be extra credit for EOCE
+x3-Doesn't have to be done after any of the other projects. Data processing, write program that takes the status code grade numbers to calculate an overall grade for the semester. Three categories of linked lists...certain status numbers indicate the end of data streams involving different types of grade data.
+x4-Re-implementation of code in C++. Re-writing singly linked node functions.
+x5-in person knowledge assessment, no structured schedule. Will be available any time the lab is open...8 question thingy thing...smaller things...deploying concepts of things you understand. Not a test of your code writing but rather a look at how well you understand the concepts that we have gone over.
+x6-personal input on the course.
+x7-personal assessment, personal outlook on how well you did in this course...
+Don't forget to submit either project...
+Current state of the EOCE project:
+To get started you want to be in dlq0, then make upgrade to eoce0.
+What is a tree? Well it's very similar to a linked list but not so linear in fashion. We take a node adn point to a node as a multiple of two below itself. This would be a binary tree, or binary search tree. Not implementing a balanced tree...The root is at the top in computer science. ordered in the value that each number is in the list.Based on the number being greater than or less. Allows for easy and ordered traversal of a given list based on the number values of every element of the list. We get to write the function that adds a node into the tree...automatic sorting of tree by building it. There are three essential search modes for a tree: In order, pre-order, post order. So a pre-order traversal is going to find the left child first and go to the parent and to the right, to the left, to the right, to the left, no parent...continue until we encounter the  greatest value with no child element. Pre-order is least to greatest, post-order is greatest to least. If order matters we want pre or post
+=== Dec. 3rd 2015 ===
+EOCE1: C++ rendition of the linked list
+Object orientated structure of header files
+node.h: There is a class node. Class is a struct that you can put functions in. Public members inside of node class...No need for rm node or mk node. Value is in private, we can not manipulate the value without nodes permission. Remember PIE acronym, polymorphism, inheritance, encapsulation. Setting a member or virtual function to 0 in a public class, means we cannot instantiate it. Different classes for singlylinked, doublylinked, ?. The different classes vary the ability to access certain parts of the code. C++ is code management in laments terms...
+List.h: Containment of more than one node. There is a protected class, that allows usage only to the list class.
+ListofSLN: Inherits from list.h.
+ListofDLN: Inherits from SLLN.
+In C++ there is a 'new' keyword that allows for the allocation of memory. There is also a 'delete' keyword which de-allocates memory.
+Node list constructor initiates a value. :: says, node class...the thing to the right is what it is defining.
+List is provided for us...might make doubly a little more spelled out.
+There aren't any unit tests, it is advised we write our own tests to evaluate their functionality.
+|MORE ON TREES|
+We have a list of values to add to the tree...
+Words to remember: balanced, binary, search.

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools