16-11-2012, 03:36 PM
Basic Data Structures and Algorithms
Basic Data Structures.pdf (Size: 353.38 KB / Downloads: 363)
INTRODUCTION
In this tutorial, we will look at several applications of the C language that we will find
useful in designing and developing embedded systems. These applications will comprise
three fundamental data structures, the linked list, the queue, and the stack, and four algorithms,
linear search, binary search, selection sort, and quicksort. Each of these should be
a basic tool in every embedded developer’s tool box.
The data structures that we will develop fall into the general category of what we call
containers. We use these to hold all different kinds of data both within a process and as
shared variables between processes.
Array Based Containers
The array, which often underlies the data type we call a buffer, is a very convenient
data structure to use as a container. It is efficient and supports fast, random access. For certain
kinds of applications it works very well. However, arrays are not without problems.
First, they are not particularly flexible. When their size must be changed, we must allocate
new memory, copy the old array into the new location, and then delete the old array. This
is generally not feasible in the firmware environment that we typically find in an embedded
application. Arrays can also be the source of many hard to find errors if one does not
carefully manage the boundaries of the structure when defining or accessing it.
Lists and List Based Containers
As one alternative to the array, we introduce a container called a list. In its generic
sense, the list is something that we probably use every day. On reflection, we can ask,
what exactly is a list? We can begin with a list of names, groceries, numbers, girlfriends,
boyfriends, cousins, nieces, Sherpa guides to the Himalayas….even this collection of
things. More formally, we see, then, that a list is a finite sequence of elements. We recognize
that a list may be empty. The list of all my wealthy and famous friends, for example.
Up to this point, we’ve been simply naming
collections of things. We’ve said nothing about the
structure of the list or the order of its elements.
Let’s think about building a list…in an abstract
sense. What features and characteristics do we
expect to see? These are our use cases; our outside
view.
Linked Lists
We can see that a list type container offers a powerful alternative to the array. A data
structure that can begin to give the capabilities that we’re looking for is called a linked list.
The linked list is structured much like a chain. If we want to make the chain longer, we
add a link. If we want it shorter, we remove a link. It’s easy to add or to remove links at
either end of the chain; we can add or remove elements of linked list in a similar way. For
the chain and the linked list, adding or removing elements in middle of the structure is
more difficult.
Designing a Linked List
As we examine the linked list in greater detail, we will also be illustrating some of the
thought process that one goes through in executing the design of any software or hardware
module. As a way to manage the complexity of a new design, we begin by looking for
related concepts that we may already understand. While the linked list is not a particularly
complex design, the steps we use remain appropriate for those designs that are.
In the opening discussion on lists, we've identified some of the desirable high level
requirements. Let's now begin to formalize the design. The first steps involve taking a
look at the design from the outside, that is, we take an external view. Such a view reflects
how our clients will use our system. We then move to the inside as we begin to develop the
system that will give rise to the required features and capabilities. We start by specifying
the interface and then proceed to the implementation. We first ask what then follow with
how. The use cases for the list that we identified earlier give the first cut at our external
interface - the what part.
The Linked List
Combining collections of nodes in an organized way gives a schematic picture of the
evolving linked list concept in Figure 3.3. The first element or node is called the head. The
last is called the tail. We say that the tail is grounded (NULL) to identify the end of the
list. We can see that we can move through the linked list by following the next reference
from one node to next. When we reach a node whose next reference is NULL, we know
that we have reached the end of the list. When the head has a NULL value, we know that
the list is empty, it contains no elements.