C++ Standard Template Libraries

Many people are surprised to realize that they do not always have to write all the code for everything they are trying to do. Many data structures and commonly used functions are already written and stored in templates online. Those for C++ can be found here. The templates on the website contain the basic codes for common data structures like lists, vectors, stacks, queues and several other basic structures. The codes are categorized and easy to locate. The codes provided are the basics for the particular data structure and can then be modified to accomplish what it is that you need the code to do in particular. It is a very useful resource which allows to drastically cut down programming time. Most other computer programming languages have similar sites which contain codes for structures in those languages.

Queues

Another ADT is the queue. The queue is the opposite of a stack in that it is known as first in and first out data structure. All data insertions in a queue come in at one end of the list and all the deletions will come at the other end of the list. It can be thought of like the line at the supermarket. A person enters at one end is exits at the other end. There are several ways to implement a queue . The first is a pointer based implementation. The pointer based implementation is essential the same as a linked list with two extra pointers to track the first and last data elements in the queue. The second implementation is done through and array. The array is implemented by setting the max size and when it is completely filled the array dumps the data that was in the last element of the array and shifts all the other elements down to the next element. One of the common uses of queues are when a certain resource is needed by more than one part of the computer. This can commonly be found in the use of a printer since only one item can be printed at a time queues are often used to delegate the sequence of documents printed.

Stacks

There are several different types of processing data in a computer. One ways is known as a stack. A stack is like a list in that it has a set of functions and set of data. A stack can be thought of as a last in first out data structure. When I was taught about stacks I was told to think of it like a game of cards in which you add a card to the top and the next person can either add a card to the top of the deck or take the card that is on the top of the deck. The same thing happens with stacks of data. When data is placed on the stack it is known as pushing data onto the stack, and when data is removed from the stack it is known as popping the stack. The stack also can inherit all of the same functions of the linked list and then additionally requires a push function, pop function, display and top functions. The display function will be used to display all the elements of the stack. The top function reads the top of the data. One of the limitations of stacks are that you can only access the top element on the stack.

Linked Lists

A linked list is a specially designed class that allows for a set of objects to be grouped together with a set of operations. Lists can be used for many different computer science implementations. List usually contain a specific set of functions. The essential functions are the constructor, retrieve, insert, remove, isEmpty, make empty, printList, and search. Each of these have a specific function to keep the list properly linked. A linked list is implemented by creating a member of a specific data type. The member is then placed into a node. The node is then linked to the next node in the list. It works so that everytime a new node is added to the data structure a link is then placed between the previous node in the list. The functions in the linked list allow for it to be maintained and allow for data to be placed into specific place within the list. Linked lists come in several types, a single linked list is only linked once and is created using only two pointers. A double linked list is linked twice and require more pointers. There is also circulatory lists which are list which link the last node back to the first node.

Recursion

Recursion is a function that that either directly or indirectly makes a call to itself. The idea behind recursion is that you can break down a large problem into smaller problems until it is finally just a simple problem to solve. Recursive solutions are somewhat difficult to create because they must be made very carefully. The idea of the solution is for each successive call of the function should bring you closer and closer to an easily solved solution. The easily solved solution is known as the base case. Every recursive case is required to have at least one base case. It also must have at least one general case. The general case is any of the recursive steps that you take in order to get to the base case. A common way to look at a recursive case is by examining a function that computes the Fibonacci number.

int Fibonacci(int n){

if (n == 0)

return 0; // base case

if (n == 1)

return 1; // base case

return Fibonacci(n – 1) + Fibonacci(n– 2); // recursion}

One problem with recursion is that many times you can create an infinite recursion which is similar to an infinite loop. It is a fatal error that will cause the program to never stop running because it cannot get out of infinite recursion. However, recursion can sometimes be the best solution to a problem.

Algorithm Analysis

Algorithm Analysis is another essential part of the computer programming process. Algorithm analysis is analyzing the algorithm that you have created for efficiency and running time. There are different ways to solve programming problems and many times one way is way more efficient than another. In algorithm analysis you are presented with ways to decide how long a certain algorithm will take to run. There are several different types of analysis that can be done. The type of analysis I will focus on is asymptotic analysis. Asymptotic analysis is a technique of graphing different scenarios in different types of notation to get a picture of what the running time would be. Big Oh notation is one of the types of asymptotic analysis. This analysis allows you to find the worst case scenario of an algorithm and ensure that the algorithm is running below that time. Big omega is analysis which finds the best case scenario and theta notation which finds the average case scenario. Using these notations you can analyze the algorithm to get a picture of the running time of a program and then compare which algorithms are more efficient than others.

Pointers in C++

Pointers are a key feature within the C++ programming language. Pointers are variable used to point to different data within a program. An analogy used to describe pointers is that your address is a pointer to your home. The pointer has its own memory address. Pointers must be initialized to a specific data type. A pointer of type int can only point to int data, while a pointer of type string can only point to data of type string. Pointers are used for many different uses within C++.

One of the most essential uses of a pointer is to use it to point to the different elements of an array of dynamic memory. Dynamic memory is memory created with the new operator which enables you to easily remove the memory after it is no longer necessary for to the program. This is necessary in C++ because it does not have garbage collection. This makes the pointer essential to programming in C++. Once memory is dynamically allocated you can reference it using the pointer. The use of the pointer to reference the memory saves memory space and allows the programmer to function at a higher efficiency than if programmed without the use of the pointer and dynamic memory allocation.