1. Linear Data Structures
2. Graphs
3. Trees
4. Sets and Dictionaries

**Fundamental Data Structures**

*1.
Linear Data Structures*

*2.
Graphs*

*3. Trees*

*4. Sets
and Dictionaries*

Since the vast majority of algorithms of
interest operate on data, particular ways of organizing data play a critical
role in the design and analysis of algorithms. A *data*** structure **can be defined
as a particular scheme of organizing related data items.

**Linear Data Structures**

The two most important elementary data
structures are the array and the linked list. A (one-dimensional) ** array**
is a sequence of

In the majority of cases, the index is an
integer either between 0 and ** n** − 1 (as shown in Figure 1.3) or between 1 and

Each and every element of an array can be
accessed in the same constant amount of time regardless of where in the array
the element in question is located. This feature positively distinguishes
arrays from linked lists, discussed below.

Arrays are used for implementing a variety of
other data structures. Promi-nent among them is the ** string**, a sequence of
characters from an alphabet termi-nated by a special character indicating the
string’s end. Strings composed of zeros and ones are called

A ** linked list** is a sequence of zero or
more elements called

To access a particular node of a linked list, one starts with the
list’s first node and traverses the pointer chain until the particular node is
reached. Thus, the time needed to access an element of a singly linked list,
unlike that of an array, depends on where in the list the element is located.
On the positive side, linked lists do

not require any preliminary reservation of the
computer memory, and insertions and deletions can be made quite efficiently in
a linked list by reconnecting a few appropriate pointers.

We can exploit flexibility of the linked list
structure in a variety of ways. For example, it is often convenient to start a
linked list with a special node called the ** header**. This node may contain
information about the linked list itself, such as its

Another extension is the structure called the ** doubly
linked list**, in which every node, except the first and the last,
contains pointers to both its successor and its predecessor (Figure 1.5).

The array and linked list are two principal
choices in representing a more abstract data structure called a linear list or
simply a list. A ** list** is a finite sequence of data items, i.e., a collection of
data items arranged in a certain linear order. The basic operations performed
on this data structure are searching for, inserting, and deleting an element.

Two special types of lists, stacks and queues,
are particularly important. A ** stack **is a list in which insertions
and deletions can be done only at the end. This

A ** queue**, on the other hand, is a list
from which elements are deleted from one end of the structure, called the

*priority*** queue **is a collection of
data items from a totally ordered universe (most often, integer or real numbers).
The principal operations on a priority queue are find-ing its largest element,
deleting its largest element, and adding a new element. Of course, a priority
queue must be implemented so that the last two operations yield another
priority queue. Straightforward implementations of this data struc-ture can be
based on either an array or a sorted array, but neither of these options yields
the most efficient solution possible. A better implementation of a priority
queue is based on an ingenious data structure called the

**Graphs**

As we mentioned in the previous section, a
graph is informally thought of as a collection of points in the plane called
“vertices” or “nodes,” some of them connected by line segments called “edges”
or “arcs.” Formally, a *graph*** G** =

If a pair of vertices ** (u, v)** is not the same as the pair

It is normally convenient to label vertices of
a graph or a digraph with letters, integer numbers, or, if an application calls
for it, character strings (Figure 1.6). The graph depicted in Figure 1.6a has
six vertices and seven undirected edges:

** V **= {

The digraph depicted in Figure 1.6b has six
vertices and eight directed edges:

** V **= {

Our definition of a graph does not forbid ** loops**,
or edges connecting vertices to themselves. Unless explicitly stated otherwise,
we will consider graphs without loops. Since our definition disallows multiple
edges between the same vertices of an undirected graph, we have the following
inequality for the number of edges |

0 ≤ |** E**|
≤ |

(We get the largest number of edges in a graph
if there is an edge connecting each of its |** V** | vertices with all |

A graph with every pair of its vertices
connected by an edge is called ** complete**. A standard notation for
the complete graph with |

**Graph
Representations **Graphs
for computer algorithms are usually repre-sented in one of two ways: the adjacency
matrix and adjacency lists. The *adjacency*** matrix **of a graph with

Note that the adjacency matrix of an undirected
graph is always symmetric, i.e., ** A**[

The ** adjacency lists** of a graph or a
digraph is a collection of linked lists, one for each vertex, that contain all
the vertices adjacent to the list’s vertex (i.e., all the vertices connected to
it by an edge). Usually, such lists start with a header identifying a vertex
for which the list is compiled. For example, Figure 1.7b represents the graph
in Figure 1.6a via its adjacency lists. To put it another way,

adjacency lists indicate columns of the
adjacency matrix that, for a given vertex, contain 1’s.

If a graph is sparse, the adjacency list
representation may use less space than the corresponding adjacency matrix
despite the extra storage consumed by pointers of the linked lists; the
situation is exactly opposite for dense graphs. In general, which of the two
representations is more convenient depends on the nature of the problem, on the
algorithm used for solving it, and, possibly, on the type of input graph
(sparse or dense).

**Weighted
Graphs **A** weighted graph **(or
weighted digraph) is a graph (or di-graph) with numbers assigned to its edges.
These numbers are called

Both principal representations of a graph can
be easily adopted to accommo-date weighted graphs. If a weighted graph is represented
by its adjacency matrix, then its element ** A**[

**Paths
and Cycles **Among
the many properties of graphs, two are important for a** **great number of applications: ** connectivity** and

In the case of a directed graph, we are usually
interested in directed paths. A ** directed path** is a sequence of
vertices in which every consecutive pair of the vertices is connected by an
edge directed from the vertex listed first to the vertex listed next. For
example,

A graph is said to be ** connected** if for every
pair of its vertices

Graphs with several connected components do
happen in real-world appli-cations. A graph representing the Interstate highway
system of the United States would be an example (why?).

It is important to know for many applications
whether or not a graph under consideration has cycles. A ** cycle** is a path of a
positive length that starts and ends at the same vertex and does not traverse
the same edge more than once. For example,

**Trees**

A ** tree** (more accurately, a

Trees have several important properties other
graphs do not have. In par-ticular, the number of edges in a tree is always one
less than the number of its vertices:

|** E**| = |

As the graph in Figure 1.9 demonstrates, this
property is necessary but not suffi-cient for a graph to be a tree. However,
for connected graphs it is sufficient and hence provides a convenient way of
checking whether a connected graph has a cycle.

**Rooted
Trees **Another very important
property of trees is the fact that for every** **two vertices in a tree, there always exists exactly one simple
path from one of these vertices to the other. This property makes it possible
to select an arbitrary vertex in a free tree and consider it as the ** root**
of the so-called

Rooted trees play a very important role in
computer science, a much more important one than free trees do; in fact, for
the sake of brevity, they are often referred to as simply “trees.” An obvious
application of trees is for describing hierarchies, from file directories to
organizational charts of enterprises. There are many less obvious applications,
such as implementing dictionaries (see below), efficient access to very large
data sets (Section 7.4), and data encoding (Section 9.4). As we discuss in
Chapter 2, trees also are helpful in analysis of recursive algorithms. To
finish this far-from-complete list of tree applications, we should mention the
so-called ** state-space trees** that underline two important algorithm design
techniques: backtracking and branch-and-bound (Sections 12.1 and 12.2).

For any vertex ** v** in a tree

The ** depth** of a vertex

**Ordered
Trees **An** ordered tree **is a rooted
tree in which all the children of each

A ** binary tree** can be defined as an
ordered tree in which every vertex has no more than two children and each child
is designated as either a

In Figure 1.12b, some numbers are assigned to
vertices of the binary tree in Figure 1.12a. Note that a number assigned to
each parental vertex is larger than all the numbers in its left subtree and
smaller than all the numbers in its right subtree. Such trees are called ** binary
search trees**. Binary trees and binary search trees have a wide variety
of applications in computer science; you will encounter some of them throughout
the book. In particular, binary search trees can be generalized to more general
types of search trees called

As you will see later in the book, the
efficiency of most important algorithms for binary search trees and their
extensions depends on the tree’s height. There-fore, the following inequalities
for the height ** h** of a binary tree with

log_{2} ** n** ≤

A binary tree is usually implemented for
computing purposes by a collection of nodes corresponding to vertices of the
tree. Each node contains some informa-tion associated with the vertex (its name
or some value assigned to it) and two pointers to the nodes representing the
left child and right child of the vertex, re-spectively. Figure 1.13
illustrates such an implementation for the binary search tree in Figure 1.12b.

A computer representation of an arbitrary
ordered tree can be done by simply providing a parental vertex with the number
of pointers equal to the number of its children. This representation may prove
to be inconvenient if the number of children varies widely among the nodes. We
can avoid this inconvenience by using nodes with just two pointers, as we did
for binary trees. Here, however, the left pointer will point to the first child
of the vertex, and the right pointer will point to its next sibling.
Accordingly, this representation is called the *first child–next*** sibling
representation**. Thus, all the siblings of a vertex are linked via the
nodes’

**Sets and Dictionaries**

The notion of a set plays a central role in
mathematics. A ** set** can be described as an unordered collection (possibly
empty) of distinct items called

set. A specific set is defined either by an
explicit listing of its elements (e.g., ** S** = {2

Sets can be implemented in computer
applications in two ways. The first considers only sets that are subsets of
some large set ** U,** called the

The second and more common way to represent a
set for computing purposes is to use the list structure to indicate the set’s
elements. Of course, this option, too, is feasible only for finite sets;
fortunately, unlike mathematics, this is the kind of sets most computer
applications need. Note, however, the two principal points of distinction
between sets and lists. First, a set cannot contain identical elements; a list
can. This requirement for uniqueness is sometimes circumvented by the
introduction of a ** multiset**, or

In
computing, the operations we need to perform for a set or a multiset most often
are searching for a given item, adding a new item, and deleting an item from
the collection. A data structure that implements these three operations is
called the ** dictionary**. Note the relationship between this data structure
and the problem of searching mentioned in Section 1.3; obviously, we are
dealing here with searching in a dynamic context. Consequently, an efficient
implementation of a dictionary has to strike a compromise between the
efficiency of searching and the efficiencies of the other two operations. There
are quite a few ways a dictionary can be implemented. They range from an
unsophisticated use of arrays (sorted or not) to much more sophisticated
techniques such as hashing and balanced search trees, which we discuss later in
the book.

A number of applications in computing require a
dynamic partition of some ** n**-element set into a collection of disjoint
subsets. After being initialized as a

You may have noticed that in our review of
basic data structures we almost al-ways mentioned specific operations that are
typically performed for the structure in question. This intimate relationship
between the data and operations has been recognized by computer scientists for
a long time. It has led them in particular to the idea of an ** abstract
data type** (

**Exercises
1.4**

Describe
how one can implement each of the following operations on an array so that the
time it takes does not depend on the array’s size n.

Delete the ith element of an array (1 ≤
i ≤ n).

Delete the ith element of a sorted
array (the remaining array has to stay sorted, of course).

If
you have to solve the searching problem for a list of n numbers, how can you
take advantage of the fact that the list is known to be sorted? Give separate
answers for

lists represented as arrays.

lists represented as linked lists.

a.
Show the stack after each operation of the following sequence that starts with
the empty stack:

push(a), push(b), pop, push(c), push(d), pop

Show
the queue after each operation of the following sequence that starts with the
empty queue:

enqueue(a), enqueue(b), dequeue, enqueue(c),
enqueue(d), dequeue

a.
Let A be the adjacency matrix of an undirected graph. Explain what prop-erty of
the matrix indicates that

the
graph is complete.

the
graph has a loop, i.e., an edge connecting a vertex to itself.

the
graph has an isolated vertex, i.e., a vertex with no edges incident to it.

Answer
the same questions for the adjacency list representation.

Give a detailed description of an algorithm for
transforming a free tree into a tree rooted at a given vertex of the free tree.

6. Prove the inequalities that bracket the
height of a binary tree with n vertices:

log2 n ≤
h ≤ n − 1.

Indicate
how the ADT priority queue can be implemented as

an
(unsorted) array.

a
sorted array.

a
binary search tree.

How
would you implement a dictionary of a reasonably small size n if you knew that
all its elements are distinct (e.g., names of the 50 states of the United
States)? Specify an implementation of each dictionary operation.

For
each of the following applications, indicate the most appropriate data
structure:

answering
telephone calls in the order of their known priorities

sending
backlog orders to customers in the order they have been received

implementing
a calculator for computing simple arithmetical expressions

Anagram
checking Design an algorithm for checking whether two given words are anagrams,
i.e., whether one word can be obtained by permuting the letters of the other.
For example, the words tea and eat are anagrams.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Fundamental Data Structures |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.