The first official class of the 2nd best course ever. Welcome to data structures…Today I experiences such things as nodes, linked lists and pointers on pointers, a little introduction for future projects. We discussed what project number one is going to consist of, (Display,insert, append,obtain,clear,quit). This should be done through the manipulation of an array for now, however, upon future dates we will explore further into the world of nodes and how to work with them. It is still going to takes some time for me to become completely comfortable with pointers, but I'm nearing enlightenment. There is always a start and an end to any list of nodes as well as “next” or “after” pointers that chain the list together. If this chain ever breaks the node list will be lost…ill be sure to keep a tight reign on my node list.

Today, in the 2nd installment of the 2nd best class ever, we delved into single and double pointers and their application in code. There is always an associated name,address, and content list for every pointer. All pointers should point to the same data type. Discussion also arose of structs and struct node. These handy things allow you to store any number of different variables…I can see that coming in handy. Inside of every node there is what is called a bucket which “holds” the data stored there. We are also advised to review the fundamentals of binary bases, they could pounce on us at any moment so knowing how to work with them should be of priority.

The official due date for the first project has been officially stated (09/9/2015).

Review of .hg functions and setting up an operating .hg repo were explained in detail.

It is advised to review the basics of a C++ development cycle in preparation for project 1.

First project involves manipulating an array in c. While it may seem simple at first, having not programmed for quite sometime will make this program challenging. Back to square one? Hello World!

How do we maintain contact with a node in a list? Use pointers. These pointers keep track of the address location of every node in a list.

Ex. Start → 1 → 2 → 3 → 4 → NULL: Start is the list struct pointer that needs to maintain contact with the starting node of the list at all times so we don't lose parts of the list. The arrows can be called anything but are usually designated as either after or next. The creation of tmp variables and after pointers needs to be based on what your program requires. For every node in the list it should be possible to; create, copy, and remove. Ex. Struct list

struct list { struct list *start;creates something that designates start of list struct list *end;creates something that designates end of list };

More structure examples.

    Mylist        tmp
   [start ]-> 2 -> 3 -> 4 -> NULL 
   [end   ]-------------^
   

Debugging = 'gdb' Exploring what a seg. fault really is

1. Accessing unavailable memory
2. Using example to illustrate how to use GDB to find reason for seg. fault error.

ex. gcc -o “filename” -g In order to use gdb we must have a program that compiles successfully

1. If you are ever building a production program don't compile with -g
2. To debug, “./debug-“FILENAME”
3. Use “help” command to locate helpful functions on how to effectively use GDB
4. Can use “list” to list certain parts of your code in gdb, which is helpful for quickly checking on your code.
5. “Run” command works through the program until the error is found.
6. “BT” gives function call stacks
   1. Aids in

As we continue on through linked lists of nodes the depth of every project increases bringing forth the need to create 'blueprints' of the logic at hand. Slm0 helps to initiate this thought process of plotting out your work on paper before jumping into the actual programming. Through pseudo code and visual diagrams of nodes and node lists we will plot out a variety of linked list functions and processes. Such as, build list, display list, copy list and append to list…Using many tmp variables we to track locations in list we can start to work with the node list. DSI0 review:Not advised to use “goto” statements in code because it makes code very difficult to understand. Be sure to always think about whether or not your code is as efficient as it could be…can something be optimized? Shoot for simplicity. SLM1 unveiling: Keep name of program dir the same. Make help command gives you a list of helpful items to aid in the developement and debugging of your program.

As an aid, feel free to use the following questions to help you generate content for your entries:

• What action or concept of significance, as related to the course, did you experience on this date?
• Why was this significant?
• What concepts are you dealing with that may not make perfect sense?
• What challenges are you facing with respect to the course?

Continuing work on SLN1

Remember to continue to use diagrams to keep track of where you are in the program. Importance of committing and pushing on a regular basis during the dev. of a project. -SLN1- Deals with nodes rather than an actual list For ex. cpnode will not know there is a list, so should only copy a single node. Also, copy doesn't simply involve pointing a to a node but rather creating a new node and assigning the 'info' to that node under a new pointer name. No need to use loops in these functions considering there is no list. Be sure to set all aspects to appropriate places..ex. NULL Keep track of updates for each project, use “make update” to update program files. Be sure to include all necessary header files to insure proper function of the program you are working on. SLN1 carries the same fundamental framework that much larger more complex programs do.

Importance of being able to work with existing programs and functions to create new stuff not only in this course but in other areas of development. SLL0: Using the nodelibrary functions is essential to proper development and implementation.

1. Future programs will be using functions built in SLL0
2. Become comfortable with the process of planning, building and testing.
3. This project involves a singly linked list of nodes
4. Creation of list struct which will hold managerial/administrative data about list.

Ex. of Struct list{

            Struct node * first;  //Fixed points
            Struct node * last;   //fixed
            }; typdef struct list List;
            Important to make sure first and last point to the right place, keep the program updated based on where first and last should be pointing.
     

*Projects under review* *Bonus points awarded to early submissions* *Attendance days are tracked by actual number of day in year. Ex. 242,244…* *Keep up with commenting in code* *Keep up with indenting in code*

Restructuring copy node function to simplify and save memory. *Make sure to free(node) after you check it for NULL in remove node* “Free” function can take more or less time to free memory for specified node space

-Release of SLL1- Five more functions Make upgrade Same header file (few more type defs) Specific return codes for compare function in Sll1 header file Don't make any modifications to header file Adapt code to header file

In src list:

Append: Works opposite of insert
       -Involves putting a node after a desired node
Copy List: Copy entire list. Malloc isn't needed in cp list
Display B: Show list contents, just backwards.
Search: Locates node in existing list with value it contains. Returns pointer to the first     node that has the matching value. Getpos/setpos are concerned with the nodes in list not info.
Compare: Compares to lists and returns result indicting equality or lack there of. Pos will be unsigned long long int, or the number of the position. Don't assign any values to pos. Or both lists so that no data is lost, keeps both values in one. Comparison of value in node of difference determines which list is greater/less or equal.

On projects page, Metrix link, there will be a set of graphs that visualize the dev. efforts for a given project. We will be able to visualize our personal standings in the course in our own WIKI page… SLL1 picks up where SLL0 left off… Inserting into empty list vs inserting in NULL list vs inserting into list of one, all are very different and require specific planning (aka drawing).

Break week approaching, we have two weeks to complete next project. Null list vs empty list: List *myList = NULL Initialize variables, do not “int a = NULL” always use zero Make sure you set start and end nodes-initialize When list exists and has start and end yet is set to NULL it is an empty list, nothing in the list. When the list only points to NULL it is a NULL list. Ex. We have two list pointers, one being myList, the other being myList2. myList=myList2; sets both lists to Null since myList has been untouched and remains at NULL.

[SLL2 Introduction]

• Effectively completes our implementation of singly linked lists…all these projects have had to do with the basic list functions.
• New functions:
• Obtain: Involves isolating node, but not deleting it. It merely disconnects the node. If you want to delete the node use rmnode function. Use of a double pointer, passing the address of the pointers address. Passing a pointer by address…dereference tmp var so we have access to its after element. ex. (*thatNode) → after, dereference it once to get back to the single pointer.
• Clear List: Empties existing list, doesn't deallocate list. Should end up with an empty list, with no nodes but the list struct still remains.
• Rm list: Use append to help remove list. Many opportunities to reuse something…
• Swap Node: We identify two nodes then obtain them for reinsertion into the list…
• Sort List: A three different modes. Takes myList pointer and mode. Mode 0 instructs sort to sort list from least to greatest. Mode 1 sorts list from greatest to lease. Figure out how to sort first…conceptualize the idea.

SLL2 coming due in 19 days.

!SLL3 and SLL4 introductions!

SLL3: Transitional project preparing previous builds for sll4.

1. Second chance at getting any incomplete functions working
2. Change in list struct, 'after' now is added to list struct so we can point to other lists.
3. Update insert, append and attain to know quantity of list.
4. Only 4 tests!

SLL4: MIND BLOWING NEWS

1. New header file “group.h”
2. New struct “group of lists”
   1. Contains 'first' and 'last' as list pointers
   2. First is now first list which has a first node in the first group of lists.
3. Will be writing 8 functions. Mkgroup will make a group of lists, rmgroup will clear or deallocate the group, linsert, lattain,lappend….
4. Project carries huge amount of similar logic compared to previously built projects.

SLN1,SLL1,2,3,4 make up our first big build for the semester. Keep up Monday oct. 19- RICHARD STALLMAN

SLL2 due wednesday More about obtain function in SLL2:

• You want to disconnect node from list.
• Do not delete or deallocate the node, you want it saved in memory for use.
• In order to use obtain you need to pass it a tmp pointer that is pointing to the node you want to obtain.

ex.

     
     That node
     -----------tmp  
     Mylist      |
    [ start]----NODE---NODE---NULL
    [ end  ]-------------------|

Now you would move start after to the 2nd NODE to keep start pointing to the first node in the list. Next, you want to take the 1st NODE's after and remove it, successfully removing the node from the list without deleting it.

Also, to point 'That node' to the tmp pointer you want to give it two pointers, so (* thatnode)—>info

Other functions:

• empty: Turns list into empty list
• rmlist:Removes the list from memory, you may want to use empty list to make sure list is in simplest form for removal.
• sort:

    ----> These functions provide additional useful capabilities

• Swap:

Be constantly conscious of code you have already made and how you can continue to use them in your code. Work smarter! NOT harder…

Additional help:

• Leave Sort as last function, swap will come in very handy in creating sort. Although, keep in mind there are many ways to sort.
• What if the list is NULL or Empty?? You can't very well use swap if you're trying to sort.
• SLL2 is the 3rd to last singly linked list project.
• SLL3 and SLL4 are due next week.
• SLL4 explores lists of lists….Fun right?? Play around with this idea through pictures to better understand it.
• Sll4 uses a count unlike nothing before it…this will still work with an endless amount of nodes.

SLL3 is a small project that basically involves re-working some previously made functions to allow a count. Sll4 Llist: 1 means everything is ok. 0 means it is an empty list

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.

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…

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 1. Under inc dir.

  a)Node.h
        1.Payload
        2.Including data.h
        3.Node declartation 
        4.Function prototypes at the bottom
        5.Difference from singly linked projects. Types of status codes...
        6.This project is too different to use any previously written code.
  b)Data.h
        1. Includes stdlib.h
        2.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.
        3.Define statements allow for easier use of value, data and other
        4.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
        5.typedef make our code easier to write.
        6.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 
        1. 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
        1.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
        1.

* 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

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

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

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:

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

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.

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

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.

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 0x0-Exercise in finding out what you, yourself believe concerning data structures and it's apparent influence on the universe. 0x1-Building a tree, add node function. There will be a test reference for everything but what we are building. 0x2-Traversing a tree. Traverse_S is the function we are implementing.Traverse I and Traverse R will be extra credit for EOCE 0x3-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. 0x4-Re-implementation of code in C++. Re-writing singly linked node functions. 0x5-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. 0x6-personal input on the course. 0x7-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

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.

We have a list of values to add to the tree… Words to remember: balanced, binary, search.