Hashing is a very common technique for storing data in such a way that the data can be inserted and retrieved very quickly. Hashing uses a data structure called a hash table. Although hash tables provide fast insertion, deletion, and retrieval, they perform poorly for operations that involve searching, such as finding the minimum or maximum value. For these types of operations, other data structures are preferred (see, for example, Chapter 14 on binary search trees).

The.NET Framework library provides a very useful class for working with hash tables, the Hashtable class. We will examine this class in this chapter, but we will also discuss how to implement a custom hash table. Building hash tables is not very difficult and the programming techniques used are well worth knowing.

AN OVERVIEW OF HASHING

A hash table data structure is designed around an array. The array consists of elements 0 through some predetermined size, though we can increase the size later if necessary. Each data item is stored in the array based on some piece of the data, called the key. To store an element in the hash table, the key is mapped into a number in the range of 0 to the hash table size using a function called a hash function.

Ideally, the hash function stores each key in its own cell in the array.

The two most common operations performed on data stored in a computer are sorting and searching. This has been true since the beginning of the computing industry, which means that sorting and searching are also two of the most studied operations in computer science. Many of the data structures discussed in this book are designed primarily to make sorting and/or searching easier and more efficient on the data stored in the structure.

This chapter introduces you to the fundamental algorithms for sorting and searching data. These algorithms depend only on the array as a data structure and the only “advanced” programming technique used is recursion. This chapter also introduces you to the techniques we'll use throughout the book to informally analyze different algorithms for speed and efficiency.

SORTING ALGORITHMS

Most of the data we work with in our day-to-day lives is sorted. We look up definitions in a dictionary by searching alphabetically. We look up a phone number by moving through the last names in the book alphabetically. The post office sorts mail in several ways—by zip code, then by street address, and then by name.Sorting is a fundamental process in working with data and deserves close study.

Although researchers have developed some very sophisticated sorting algorithms, there are also several simple sorting algorithms you should study first. These sorting algorithms are the insertion sort, the bubble sort, and the selection sort. Each of these algorithms is easy to understand and easy to implement.

Trees constitute a very common data structure in computer science. A tree is a nonlinear data structure that is used to store data in a hierarchical manner. We examine one primary tree structure in this chapter, the binary tree, along with one implementation of the binary tree, the binary search tree. Binary trees are often chosen over more fundamental structures, such as arrays and linked lists, because you can search a binary tree quickly (as opposed to a linked list) and you can quickly insert data and delete data from a binary tree (as opposed to an array).

DEFINITION OF A TREE

Before we examine the structure and behavior of the binary tree, we need to define what we mean by a tree. A tree is a set of nodes connected by edges. An example of a tree is a company's organization chart (see Figure 12.1).

The purpose of an organization chart is to communicate to the viewer the structure of the organization. In Figure 12.1, each box is a node and the lines connecting the boxes are the edges. The nodes, obviously, represent the entities (people) that make up an organization. The edges represent relationships among the entities. For example, the CIO (Chief Information Officer) reports directly to the CEO (Chief Executive Officer), so there is an edge between these two nodes. The Development Manager reports to the CIO, so there is an edge connecting them.

Whereas the String and StringBuilder classes provide a set of methods that can be used to process string-based data, the RegEx and its supporting classes provide much more power for string-processing tasks. String processing mostly involves looking for patterns in strings (pattern matching) and it is performed via a special language called a regular expression. In this chapter we look at how to form regular expressions and how to use them to solve common text-processing tasks.

REGULAR EXPRESSIONS

A regular expression is a language that describes patterns of characters in strings, along with descriptors for repeating characters, alternatives, and groupings of characters. Regular expressions can be used to both perform searches in strings and perform substitutions in strings.

A regular expression itself consists of just a string of characters that define a pattern you want to search for in another string. Generally, the characters in a regular expression match themselves, so that the regular expression “the” matches that sequence of characters wherever they are found in a string.

A regular expression can also include special characters called metacharacters. Metacharacters are used to signify repetition, alternation, or grouping. We will examine how these metacharacters are used later in the chapter.

Most experienced computer users have used regular expressions in their work, even if they weren't aware they were doing so at the time. Whenever you type the following command at a command prompt:

1. C:\>dir myfile.exe

you are using the regular expression “myfile.exe”.

A set is a collection of unique elements. The elements of a set are called members. The two most important properties of sets are that the members of a set are unordered and that no member can occur in a set more than once. Sets play a very important role in computer science but are not included as a data structure in VB.NET.

This chapter discusses the development of a Set class. Rather than provide just one implementation, however, we provide two. For nonnumeric items, we provide a fairly simple implementation using a hash table as the underlying data structureThe problem with this implementation is its efficiency. A more efficient Set class for numeric values utilizes a bit array as its data store. This forms the basis of our second implementation.

FUNDAMENTAL SET DEFINITIONS, OPERATIONS, AND PROPERTIES

A set is defined as an unordered collection of related members in which no member occurs more than once. A set is written as a list of members surrounded by curly braces, such as {0,1,2,3,4,5,6,7,8,9}. We can write a set in any order, so the previous set can be written as {9,8,7,6,5,4,3,2,1,0} or any other combination of the members such that all members are written just once.

Set Definitions

Here are some definitions you need to know to work with sets:

1. A set that contains no members is called the empty set. The universe is the set of all possible members.

2. Two sets are considered equal if they contain exactly the same members.

3. A set is considered a subset of another set if all the members of the first set are contained in the second set.

In this chapter, we present a set of advanced data structures and algorithms for performing searching. The data structures we cover include the red–black tree, the splay tree, and the skip list. AVL trees and red–black trees are two solutions to the problem of handling unbalanced binary search trees. The skip list is an alternative to using a treelike data structure that foregoes the complexity of the red–black and splay trees.

AVL Trees

Named for the two computer scientists who discovered this data structure—G. M. Adelson-Velskii and E. M. Landis—in 1962, AVL trees provide another solution to maintaining balanced binary trees. The defining characteristic of an AVL tree is that the difference between the height of the right and left subtrees can never be more than one.

AVL Tree Fundamentals

To guarantee that the tree always stays “in balance,” the AVL tree continually compares the heights of the left and right subtrees. AVL trees utilize a technique, called a rotation, to keep them in balance.

To understand how a rotation works, let's look at a simple example that builds a binary tree of integers. Starting with the tree shown in Figure 15.1, if we insert the value 10 into the tree, the tree becomes unbalanced, as shown in Figure 15.2. The left subtree now has a height of 2, but the right subtree has a height of 0, violating the rule for AVL trees.

For many applications, data are best stored as lists, and lists occur naturally in day-to-day life—to-do lists, grocery lists, and top-ten lists. In this chapter we explore one particular type of list, the linked list. Although the.NET Framework class library contains several list-based collection classes, the linked list is not among them. The chapter starts with an explanation of why we need linked lists, then we explore two different implementations of the data structure—object-based linked lists and array-based linked lists. The chapter finishes up with several examples of how linked lists can be used for solving computer programming problems you may run across.

SHORTCOMINGS OF ARRAYS

The array is the natural data structure to use when working with lists. Arrays provide fast access to stored items and are easy to loop through. And, of course, the array is already part of the language and you don't have to use extra memory and processing time using a user-defined data structure.

However, as we've seen, the array is not the perfect data structure. Searching for an item in an unordered array can be slow because you might have to visit every element in the array before finding the element you're searching for. Ordered (sorted) arrays are much more efficient for searching, but insertions and deletions take extra time because you have to shift the elements up or down to either make space for an insertion or remove space with a deletion.

In this preliminary chapter, we introduce a couple of topics we'll be using throughout the book. First, we discuss how to use classes and object-oriented programming (OOP) to aid in the development of data structures and algorithms. Using OOP techniques will make our algorithms and data structures more general and easier to modify, not to mention easier to understand.

The second part of this Introduction familiarizes the reader with techniques for performing timing tests on data structures and, most importantly, the different algorithms examined in this book. Running timing tests (also called benchmarking) is notoriously difficult to get exactly right, and in the.NET environment, it is even more complex than in other environments. We develop a Timing class that makes it easy to test the efficiency of an algorithm (or a data structure when appropriate) without obscuring the code for the algorithm or data structures.

DEVELOPING CLASSES

This section provides the reader with a quick overview of developing classes in VB. NET. The rationale for using classes and for OOP in general is not discussed here. For a more thorough discussion of OOP in VB. NET, see McMillan (2004).

One of the primary uses of OOP is to develop user-defined data types. To aid our discussion, and to illustrate some of the fundamental principles of OOP, we will develop two classes for describing one or two features of a geometric data processing system: the Point class and the Circle class.

We organized the chapters in this book to be read in sequence. However, each chapter begins with a clear statement of what we assume you know before reading the chapter, so you can jump around a little bit, depending on your background and experience. You can use the book as a reference and jump in anywhere once you have the fundamentals.

Chapter 1 presents reasons why you should learn Java and describes the many similarities between COBOL and Java.

Chapter 2 explains what OO is, and what it is not. OO terms and concepts are described using several everyday examples.

Chapter 3 describes the overall structure and format of a Java program. Several small programs are developed to show you how to create objects and call methods.

Chapter 4 shows you how to define Java data items and use them in a program. Java data definition is somewhat different than COBOL and these differences are clearly explained and demonstrated in the program examples.

Chapter 5 introduces Java computation and, again, several small programs are written to illustrate the ideas and concepts present. You will see that some Java computation is nearly identical to COBOL.

Chapter 6 illustrates how to use the Java decision-making statements.

OBJECTIVES

In this chapter you will study:

• Java program structure;

• Writing class programs;

• Writing Java comments;

• Naming rules & conventions;

• Calling methods;

• Creating objects; and

• Working with subclasses.

The purpose of this chapter is to introduce you to the structure of Java programs. You will see how to write and execute simple Java programs. By working with real functioning programs, instead of just code segments, you will quickly learn the major structural differences between COBOL and Java.

This chapter begins with a program that models the Customer class from the Community National Bank system introduced in Chapter 2. This program is used to illustrate Java program structure.

We will show you how to write Java comments and review the simple rules for naming variables, methods, classes, and programs. We will also explain the Java coding conventions and style guidelines that will greatly improve the readability of your programs.

We will then execute methods in the customer class program to show how objects are created and to demonstrate calling methods. We will conclude the chapter by developing programs for the account and checking account classes to illustrate working with subclasses.

This chapter assumes you understand the following:

COBOL:

COBOL program structure

Column restrictions—area A and B

Continuation column 7

Comments and remarks

Uses of periods, commas, parentheses, spaces

Scope terminators

Rules for programmer-supplied names

Java:

OO concepts (Chapter 2)

A CLASS PROGRAM

Chapter 2 introduced object-oriented concepts and described classes and objects.

OBJECTIVES

In this chapter you will study:

• OO development;

• OO analysis and design issues; and

• Technology architecture issues.

This chapter provides an overview of OO development and some of the issues you should consider when developing OO systems. Whereas the previous chapters introduced specific programming topics, this chapter will pull together several of those topics and present them in terms of software development. As you will see, OO development is much more than writing Java programs. The successful software developer must become familiar with, and apply, OO development techniques. OO requires more attention to analysis and design than traditional development; however, the payoff is software that is developed quicker and is easier to maintain. The chapter begins with an overview of OO development followed by a brief introduction to current OO systems development methodologies. Next, activities commonly associated with analysis are presented. Then, various aspects of design necessary for understanding OO development and successful Java programming are discussed. Java examples are provided to enable you to compare and contrast some of the basic philosophical differences between OO and traditional development approaches.

This chapter assumes you understand the following:

Java:

OO concepts (Chapter 2)

Java program structure (Chapter 3)

Defining data (Chapter 4)

Arithmetic (Chapter 5)

Decision making (Chapter 6)

Looping (Chapter 7)

Arrays (Chapter 8)

Data access (Chapter 9)

Graphical User Interfaces (Chapter 10)

DEVELOPING OBJECT-ORIENTED SYSTEMS

Programming is not a stand-alone process, although that has been the focus so far in this book.

OBJECTIVES

In this chapter you will study:

• Defining Java data;

• Java data types;

• Variable scope;

• Using literals;

• Defining constants;

• Changing data types; and

• Using Java's String class.

In this chapter you will learn how to define data using Java. We will write data definition statements for alphanumeric, numeric, and boolean data (arrays are described and illustrated in Chapter 8). You will also see how to use a supplied Java class named String to simplify the definition and manipulation of alphanumeric data. You will also learn about the scope of variables. Scope determines which parts of your program can access a variable or method.

At the end of the chapter we will develop the complete data definition statements for the attributes of the Community National Bank classes developed in the previous chapter.

NOTES

1. COBOL uses the term data item or field.

2. Java uses the term variable.

3. In keeping with the spirit of Java, here we will use variable.

This chapter assumes you know about:

COBOL

Data division code

Picture clauses

Usage clause

Bits and bytes

Java

Object-oriented concepts (Chapter 2)

Java program structure (Chapter 3)

COBOL PICTURE CLAUSE

Those of us who write COBOL programs are accustomed to using the PICTURE clause to describe data items.

If you are like most other programmers, you have probably been thinking about updating your technical skills. You have been hearing a lot about Java, object-oriented development, and Internet applications. These topics have been getting a tremendous amount of press lately. In the fanfare, you may have heard someone suggest that COBOL programmers will be obsolete and can't possibly make the switch to OO. Can this possibly be true? We don't think so.

We wrote this book because we believe it is important that you learn Java and OO development. Although we don't claim learning a new programming language is a trivial task, the fact that you already know COBOL gives you a head start on learning Java. Don't let what others say bother you.

We work with COBOL as consultants for industry, in our classrooms, and as authors. However, we also work with Java and object-oriented development. From our perspective, we believe COBOL and Java are highly complementary development tools in the evolving computing environment. COBOL does a great job of processing and maintaining a firm's data. Java plays an equally important role of capturing and reporting data by connecting clients to the server across a variety of networked computers, with little concern about the specific hardware and operating systems involved.