Chapter 13: Basic Data Structures and Algorithms

Download CD Content

The first 12 chapters of this book have focused on acquainting you with the language of C++. You have explored the syntax, structure, and techniques of this programming language. However, you should be aware that this is only part of the process of programming. Simply understanding language syntax is not enough. One of the fundamental cornerstones of computer science is the study of data structures and algorithms. In this chapter, you will be introduced to both of these topics.

Data Structures

The first order of business is to define exactly what a data structure is. A data structure is an organized way of storing data that also defines how the data will be processed. Structured ways of storing data are quite commonly used—you have already encountered them without knowing it. For example, when you send documents to a networked printer, you are sending them to a queue, a data structure. A queue is, in fact, one of the most commonly encountered data structures. Let’s start with examining queues in more detail.

In a queue, data is entered in sequence from the beginning to the end. The queue is usually represented by an array. The pointer that shows where the last element was added is called the head. The pointer that shows where the last element was removed and processed is called the tail. Figure 13.1 illustrates this.

Figure 13.1: Structure of a queue.

When you use a network printer, each element of the queue array is a document (or, more likely, a fixed amount of memory). The head represents the last place that a document was added to the print queue. After an item is added, the head moves forward one space. The tail represents the processing end of the queue. Once an item is processed (i.e., printed) it is removed from the queue and the tail is advanced. When the head reaches the end of the queue, it starts back over at the beginning, and that is what is referred to as a circular queue. Let’s look at an example using a simple queue of integers.

Example 13.1

Step 1: Enter the following code into your favorite text editor.

#include <iostream> using namespace std;   int queue[10]; // both the head and the tail will start // out pointing to the first element in // the array int *phead = &queue[0]; int *ptail = &queue[0]; int main( ) {      int i;      for( i= 0;i<10;i++)      {      cout << "Please enter an integer. \n";      cin >> queue[i];      // increment the head pointer so that      // it points to the next element of the array      phead++;      }    for(i=0;i<10;i++)        {      ptail++;      cout << queue[i] << endl;        }        return 0; }

Step 2: Compile and execute that code. You should see something much like what is depicted in Figure 13.2.

Figure 13.2: Circular queue demonstration.

You should notice that, in this example, the pointer’s head and tail are only being used to keep the place of where we are currently. In some cases, programmers will use a plain integer in this case rather than a pointer to an integer. The real problem occurs when your are processing items out, slower than entering them in. You see if the head catches the tail, it will start overwriting things you have not yet processed! Normally, you would check to see if the head is the same value as the tail. If it is, then you tell the user “queue is full” and you don’t take any more input until your processing can catch up.

Another popular data structure is the stack. Whereas a queue processes items on a first-in, first-out basis (FIFO), the stack does its processing on a last-in, first-out basis (LIFO). A stack gets its name from the way it processes data, much like a stack of plates. If you stack up 10 plates, you will have to remove the last one you placed on the stack before you remove any others (unless, of course, you are a magician)). Figure 13.3 illustrates the way a stack works.

Figure 13.3: The stack.

The registers on your computer’s central processing unit (CPU) use stacks. Items are pushed onto the stack and popped off. If you worked with an Assembly programming language, you would become intimately familiar with the stack. However, for our purposes, it is enough that you know what a stack is.

The stack and the queue are just two examples of data structures. There are many more to choose from. It is beyond the scope of this book to examine all these data structures. However, you should be at least aware of what some of these data structures are. You can then use some of the resources listed in the back of this book to learn more if you so desire. In addition to stacks and queues, you may wish to acquaint yourself with the linked list, double linked list, and binary tree.

One more commonly encountered data structure is the linked list. A linked list consists of a series of nodes (made either with structures or classes) that have linked to the next node in the series. The link to the next node is usually accomplished with a pointer to another node. The following is an example of a node.

struct node {  int data; // data can be of any type at all.  node *nextnode; } 

Each node can then be included in a class. The class must have at least two methods. The first method is a push method to add new nodes to the linked list. The second method is a pop to remove nodes from the linked list. Because of the push and pop methods, a linked list is capable of dynamic sizing. That means that it can grow larger or smaller. This is in direct contrast to an array, which cannot change its size. The next step is to build a class to house the nodes, as well as the push and pop functions. The following example shows you how to create and use a linked list.

Example 13.2

Step 1: Place the following code into your favorite text editor and save it as linkedlist.h.

struct node {  int data; // data can be of any type at all.  node *nextnode;      node *prevnode; }; class linkedlist { private:   node base;   // This is the base node      // from which other nodes will   // spring.   node *curnode;// A pointer to the current node. public:    void push(int item);    int pop(); }; void linkedlist::push(int item) {      // This function basically creates a new node and        // places it at the top of the linked list. The node       // currently at the top is moved down.  node *temp=curnode;        // Temporary node  curnode->nextnode=new node;// Create new node  curnode=curnode->nextnode; // Assign current to                              // new top node curnode->data=item;   // Assign the data  curnode->prevnode=temp;// Set previous     // pointer }  int linkedlist::pop() {      // This function pulls the data off the current   // node,then      // moves the node preceding the current node into the   // front      // of the linked list.  int temp;  temp=curnode->data;      // if the previous node is somehow already gone, then  // skip      // the rest.  if (curnode->prevnode == NULL)      return temp;   curnode=curnode->prevnode;       // delete the node we just popped off   delete curnode->nextnode;   return temp; }

Step 2: Write the following code into your favorite text editor and save it as 13_02.cpp.

#include "linkedlist.h" #include <iostream> using namespace std;       int main() {      linkedlist mylist;      int data;      cout << "Enter your data, and enter -1 to exit \n";      while(data != -1)      {  cout << "Enter your next number \n";       cin>> data;       mylist.push(data);      }      return 0; }// end main 

This data structure undoubtedly appears much more complicated than the queue. There are extensive comments in the source code to aid in your understanding. However, let’s take a moment to review the highlights. To begin with, the core of the linked list is the node structure. It holds the data. Now, in our case, the data is an integer; however, it could be any data type at all, including another structure or class.

This structure is encapsulated in a class. We have a pointer that tells us the current node and the next node. We then have two functions that allow us to add new nodes or remove old ones.

Hint!

A doubly linked list is a linked list with pointers to the next node and the previous node.