Non-Linear Data Structures :: Binary Tree

The first non-linear data structure and most important to understand is the binary search tree. This structure consists of a main node which is called the root and sub nodes which are called children. Each parent node has children nodes starting at the root and going to the bottom of the tree. Binary Search trees work by having a left child and a right child pointer. This does not mean that every parent node will have 2 children. The number of children depend on the values of each node that are inserted into the tree. The first value that is inserted into the tree is the root. From the root each value inserted must be checked against it; if the value is greater than the root then it would become the right child if it were less than the root it would become the left child. This goes on through the entire tree. NO left child will ever be greater than or equal to its parent or sibling.

The following tree was created by inserting these values in order. (10,15,13,24,4,7,9,5,2)

Linear Data Structures :: Creating Queues

The concept of a queue is what every small child learns when they go to school. Wait your turn. The queue is used to create a FIFO list also known as first in first out. A queue is similar to a stack in that the top of the stack is like the front of the queue. However, the stack is created using Push at the Top while the queue is created by inserting the new node at the back of the queue.

STACK
The following image is an example of a stack. It shows the TOP of the stack equal to 3. The image demonstrates how the stack would push new nodes. Each new node would push down on the next creating what would look like a tower of blocks. The problem with a stack is that if data at the bottom of the stack needs to be popped off the stack it has to wait for everything else to go first. This is a problem in programs that create stacks of processes. Starvation is the term used for a process that does not get a chance to execute.


QUEUE
The image of the queue can be viewed as a line of people waiting at a bank. The first person in line would get to go first. After that person completes their transaction they can leave the queue and the next person can be in front of the line. A queue is a good way to ensure that everyone gets treated equally and prevents starvation from occuring.

Linear Data Structures :: Understanding Stacks

The concept of a stack is easy to understand. An example of a stack in the real world would be a stack of books or stack of papers etc. The idea of a stack in data structures is identical. There is a top and everything else is below the top. Creating a stack using a linked list is a good implementation because it allows for a stack of any size as long as resources such as memory permit. The main ideas of a stack are Top, Push and Pop. Top references the top of the stack. This is implemented using a pointer that will always be at the top of the stack. Push is refering to adding and item onto the stack. After each Push is completed the newest item added would then become the Top. Pop is used as a deletion method just as Push is used as an insertion. After each Pop is called the Top is removed from the list and the next node in that list becomes the new Top.

This code example shows the push and pop methonds.

Linear Data Structures :: Deleting from a Linked List

Since the previous post discussed inserting a node into a linked list it is necessary to also discuss the deletion of a node from the list. There are multiple cases that need to be taken into consideration. Removing a node from the beginning, end, and inbetween. The steps of deleting form the list consist of first finding the node, next removing the node and finally repairing the link between the list by linking the node previous to the deleted node and the node immediatly following the deleted node.

The following is an example of a linked list. Each square is a node with a structure of a data field and a next. In order to delete the second node we would traverse through the list until the specific data is found. The links must be changed in order to maintain the proper structure as was mentioned before. The first and third square would then be linked.

BEFORE DELETION

AFTER DELETION

Deleting from the beginning or end is similar to what was previously shown. Deleting from the beginning is nothing more than setting the initial pointer to another location. Removal from the end of the list is similar in that we change only one pointer. The previous node must be set to be the end of the list by setting next to NULL.

Deleting and Inserting are not the only functions of linked lists. Searching and Sorting can also be used, often within deletion and insertion algorithims.

Linear Data Structures :: Linked List

Usually the first data structure that is taught is the linked list. This is because it is simple and easy to implement. In order to create a linked list it is necessary to understand pointers. (The Pointers lesson is located in the archive) A linked list can be as large or small as the programmer wants it to be; of course memory size has to be taken into consideration. A linked list is individual nodes chained together by pointers. Each node can contain any number of fields of information depending on the structure. The following is an example of defining the structure of a linked list.



Adding a node to a list is easiest to do at the end of the list. Creating the new node can be done by using the following example.


This creates a new node and sets the values of each field in the node equal to a value that would be input from the terminal or from file. Traversing the list and deleting a node from the linked list is more difficult and will be discussed in later posts.

Introduction to Programming :: Pointers

Reference Operator

Pointers are exactly what the name suggests. They point at something else. The first topic of pointers that is necessary to understand is the reference operator. A reference operator points at a location in memory rather than the actual value stored within that location. Imagine a piece of memory (A) at location 1000 for example is holding a value of 50.

Input
A = 50;
B = A;
C = &A;

Output
B=50
C=1000

B is the value of A and C is the location of A.

Dereference Operator

The following dereference example consists of (A) once again at location 1000 with a stored value of 50.

Input
A= 1000(memory location) [50 is stored here]
B= *A

Output
B= Value of the location A is equivalent to. (50)

Introduction to Programming :: Input from File

The following code is an example of opening an input file and printing to the screen. Using input and output files can improve functionality of a user’s code by allowing for appending and truncating of files. Input files are often useful in programs that are not run by a user but rather predetermined information that needs to be accessed quickly. First use the #include statements and followed by using namespace std; .
Inside the main function declare a string and ifstream. In this if-else statement the file is checked, IF it is open a while loop executes. while(! InputFile.eof()) translates to while not end of input file get information from file and print to screen.

Introduction to Programming :: Output to File

In order for the following text to be legible, a screen shot had to be taken to ensure that example code would not be deleted when posted. Sorry for any inconvenience. Click on the images to enlarge them.

Introduction to Programming :: Input/Output

In order for the following text to be legible, a screen shot had to be taken to ensure that example code would not be deleted when posted. Sorry for any inconvenience. Click on the images to enlarge them.

Introduction to Programming :: Multidimensional Arrays

In the last post arrays were discussed and implemented. The next step to arrays is multidimensional arrays. Multidimentsional arrays can be as large as needed but they do use up more and more memory depending on the number of dimensions. Declaring multidimensional arrays is similar to what was previously discussed. A bidimensional array is declared as follows: int newArray [2] [4]; In order to reference a location, specify the name of the array and the locations as follows: newArray [1] [2]; . This may be hard to visualize but what this means is [row] [column]. By calling newArray[1][2]; the user is trying to reference row 1, column 2. Row 1 column 2 yields a value of 4. Remember that declaring a variable such as int newArray [2] [4]; is defining the dimensions of the array. If a reference to the location newArray[2] [4] was made; the program would not work. The correct way is to reference newArray [1] [3] instead.



The following code will fill the table above. This is controlled by two for loops. The first loop controls which row is being filled. The second for loop is computing inside the first loop in order to increment a counter and fill the columns in the row. Example: first row is filed 1,2,3,4; second row is filled 2,4,6,8.

Introduction to Programming :: Arrays

Cplusplus.com defines an array as: "An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier."

In order to intialize an array you simply declare it as follows: int newArray [10]; (type name [ size ];) This creates an array of integers and declares the name and size. There are many ways to fill an array. An example would be int newArray [3] = { 1, 2, 3,}. Arrays can consist of any data type and can also include records, meaning multiple fields per item. (this will be discussed in future posts.) Array data is accessed by looking at a memory location. (newArray[2];) Assuming we have an array of integers 1,2,3 array location [2] is equal to the integer 3. The first memory location in the array is referenced by newArray[0]. The following code is an example of initializing an array and using a for loop to print out the values of the entire array.




In the next post expect to see more about arrays and multidimensional arrays.

High School Programming, Good or Bad?

I recently read a blog that discussed the disadvantages of high school programming. Roman Zimine's perspective on the topic was that first year college computer science students are at a disadvantage if they had previously programmed in high school. The author stated that, "those who take programming courses in high school can find themselves at a disadvantage, as they have to unlearn bad programming habits while learning a new and very different language." While there are certainly cases of poor teaching and bad habits in some schools, this does not mean that all students will have the same problem.

I took programming courses in high school and I did not find myself any worse off than students who had not had programming prior to college; in fact I had a better understanding of basic concepts such as declaring variables and standard libraries. In no way was I disadvantaged by taking high school classes. The author had based his thoughts on his CS135 class in Scheme. This was the introduction language of choice for his university. Scheme is a functional language which is often very difficult to write in. Functional program languages often require a strong background in mathematics and recursion. Scheme would obviously be difficult for a freshman to comprehend having few if any mathematics courses.

Programming in high school can give an advantage to most students. It is of course possible to have a bad instructor which may lead to poor habits but most likely students will learn the basics of programming as well as using compilers. Although I disagree with the authors position of programming is bad in high school, I do agree with him that students often choose to go into the computer science field based on their grades in high school. He said, "They may think “Well, I’m getting 75% in English, 80% in Math, and 91% in Computer Science… I guess I’ll apply to a Computer Science program!" Grades in high school can be misleading; course difficulty in high school is much easier than any college course. High school can be a great opportunity to experience programming and other computer science topics as well as preparing you for college. The best way to ensure you are getting the most out of high school programming classes is to challenge yourself and practice programming outside of the classroom.

Introduction to Programming :: Using Functions

A function is a group of statements that is executed when it is called from some point of the program. The structure of a function call is as follows.


type name ( parameter1, parameter2, ...) { statements }

• type :is the data type specifier of the data returned by the function.


• name :is the identifier by which it will be possible to call the function.


• parameters :Each parameter consists of a data type specifier followed by an identifier, like any regular variable declaration and which acts within the function as a regular local variable. They allow to pass arguments to the function when it is called. The different parameters are separated by commas.


• statements is the function's body. It is a block of statements surrounded by braces { }.
  

In this small program the function subtraction() is being called by the main(). A serious of couts are being used to show different uses of the function call.

If a function does not return any value then the type would be void.

Introduction to Programming :: Switch Statements

The switch statement is a very useful structure in that it will allow for user input to control the flow of the program. In a switch statement there can be multiple cases. Each case can do a particular function. This is beneficial because a program may only need to do a certain operation every other run time. This example code below is from a binary tree program. This example shows a do-while loop controlling the menu and how long the switch statement will last. While the input from user is not 6, the loop will continue to print the menu to the screen and allow for another case to be selected. Much of the following code was left intact in order to show an example of a type of program all computer science majors should expect to see. The focal points of the program are the do-while loop and the switch statement within that loop.

Jailbreaking your iPhone

I recently came across an article online that discussed the legality of jail breaking your iPhone and whether or not Apple should have the right to protect its property. I look at this as a case of Apple being overzealous in regards to protecting their product. However, as far as consumers are concerned they bought a piece of hardware. It should be the consumer’s property and their right to do what they like with it. If similar applications are available for download for free from an open source, then why should the consumer pay more money for a program that is sub-par that Apple created? If Apple were to slap a label on their product saying, "pay more get less" then fine fair warning was given, but when you have to pay a ridiculous amount of money for a product that has shown to break within months, owners should have access to applications at a fair rate.
The bottom line is that if a customer buys any machine they should be allowed to modify it without being told otherwise. If the operating system for the iPhone isn't preferred or any phone for that matter, then why shouldn't owners be allowed to install an open source operating system. Modifying the type of operating system is not costing Apple anything, unless consumers are downloading pirated applications. As long as no illegal activity is being performed the consumer should have every right to change their property.

Introduction to Programming :: Even More Loops

Do-While Loop


Shown above is a simple do-while loop. The basic concept of a do-while is to do { a set of instructions } until a condition has been met in the while (). In the above example the user is prompted to enter a number. The do-while loop will continue until the user inputs the value of 0. This is a good form of controlling the flow of your program because it can be used to execute a set of instructions until the end of an input file for example.

For Loop


This block of code is a utilizing an import and very commonly used loop for beginner programmers. The for loop is commonly used to increment a set of instructions a specific amount of times. In the above code it states (int n=10; n>0; n--) what this is doing is declaring n=10 and then decrementing until n is no longer greater than zero. An easy way to look at a for loop is for(initialization, condition, increment) statement. Each time through the loop the value of n is show on the screen. At the end of the loop the word "FIRE!" is show on screen. Incrementing a counter is essential for most programs.

Introduction to Programming :: Conditional Statements and Loops

Conditional Statements are used to control the direction of you program. There are many strategies for controlling you program. Most commonly used are if statements. An if statement pseudo code would be; if (a){instructions}. The (a) is the condition that has to be met in order for the {instructions} to proceed. Often there are times when you need to designate what will happen if the conditions are not met by using else.

Another form of controlling the direction of a program would be loops. Loops are used to repeat a statement a specific number of times or until the condition is met. The next example shows a very simple while loop. The loop begins by prompting the user to input a starting number. The loop then compares the value of x with the conditional statement (x>0). While (x>0) the loop will continue and decrement the value of x each iteration.

The for loop and the do-while loop will be discussed in the next post.

Introduction to Programming :: Declaring Data Types

The syntax to declare a new variable is first write the desired data type and then the variable name.

Variable Names

-char
-short int
-int
-long int
-bool
-float
-double
-long double

The syntax to declare a new variable is first write the desired data type and then the variable name.
ex: int a;
float number;
string LastName
In cases of multiple variables of the same type its possible to declare them in one statement.
ex: int a, b, c;

Another aspect of declaring variables needs to be taken into account. The variables char, short, long and int can be either signed or unsigned, depending on the values that need to be represented.

Global variables can be referred from anywhere in the code, even inside functions, whenever it is after its declaration.

The scope of local variables is limited to the block enclosed in braces ({}) where they are declared

Introduction to Programming :: C++

Generally the first thing students will write in any programming language will be "Hello World." The way to begin a C++ program is to first set up the structure of the program by writing the #include statements. An example would be iostream. This is the basic input output library in C++. Following the include statements add using namespace std;. Every element of the standard C++ library is declared within a namespace. Next write the beginning of the executed code. int main() is recognized to be the beginning of the executable code. Now that everything is set up coding can begin on the "Hello World" program. This following code uses the items mentioned above and cout which will be explained more in depth in future blogs but for the time being it is a simple way to output to the screen.

#include
using namespace std;

int main()
{
cout<<"Hello World"<<endl;
return 0;
}

The program should look similar to this. The only thing that should be displayed on the screen is "Hello World." A good rule to follow when writing programs is always write comments using // " comment here " while working on the code. This will help keep the program organized and easy to understand for the user.

Introduction to Programming :: Getting Started

Incoming computer science majors will most likely be introduced to programming in Visual Basic, Java, or C++. Even if you aren't a CPSC major you will probably take a programming class as a general education. Many first time programmers will be overwhelmed if they do not allocate their time efficiently. Most errors occur in beginner programs because of a deadline being close and not enough time to really work out a problem. Some general tips that will help new programmers are...

• Always use your time efficiently
• Work out the problem on paper before trying to program
• Make sure you read the book or handouts given by the professor

Using your time efficiently is critical in any college level course. Students should not expect to just pick up on programming; it is a skill that is learned through hours of practice. Professors are hired for a good reason, use them and learn from them rather than just day dream in class. If you follow these tips you will have a better understanding of the topic and your programs will be much easier to build and debug.