1.5Fundamentals of Data Structures

1.5FUNDAMENTALS OF DATA STRUCTURES

Since most of the algorithms operate on the data ,particular ways of arranging the data play a critical role in the design & analysis of algorithms.A data structure can be defined as a particular way of arrangement of data. The expression ``data structure'', however, is usually used to refer to more complex ways of storing and manipulating data, such as arrays, stacks, queues etc. We begin by discussing the simplest, but one of the most useful data structures, namely the array.

ARRAY

Recall that an array is a named collection of homogeneous items An item’s place within the collection is called an index. The index is an integer between 0 & 1.If there is no ordering on the items in the container, we call the container unsorted,If there is an ordering, we call the container sorted.The size of the array is given by max length.Every item in the array can be accessed in the same constant amount of time.

Fig 1.b.

Linked list:

A linked list consists of headnode,A node consists of two fields.datapointer.The pointer points to the next data .The time to acces any data is variable & is dependent on the position of the data in the list.

Fig 1.c.

Stacks:

Stacks are known as LIFO (Last In, First Out) lists. The last element inserted will be the first to be retrieved, using Push and Pop

Push

–Add an element to thetop of the stack

Pop

–Remove the element at thetop of the stack

Fig 1.d

QUEUES: Accessing the elements of queues follows a FIFO (First In, First Out) order

The first element inserted will be the first to be retrieved, using Enqueue and Dequeue

•Enqueue :Add an element after the rear of the queue

•Dequeue Remove the element at the front of the queue

Fig 1.e.

Fig1.f.Stack and queue visualized as linked structures

Graphs

A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other.Undirected graph A graph in which the edges have no direction Directed graph (Digraph) A graph in which each edge is directed from one vertex to another (or the same) vertex. An undirected graphG is a pair (V,E), where V is a finite set of points called vertices and E is a finite set of edges.

An edge e ∈ E is an unordered pair (u,v), where u,v∈ V.

In a directed graph, the edge e is an ordered pair (u,v). An edge (u,v) is incident from vertex u and is incident to vertex v.

A path from a vertex v to a vertex u is a sequence <v0,v1,v2,…,vk of vertices where v0

= v, vk = u, and (vi, vi+1) ∈ E for I = 0, 1,…, k-1.

The length of a path is defined as the number of edges in the path

Fig1.g. A directed undirected graph.

Graph Properties -- Acyclicity

Cycle

–A simple path of a positive length that starts and ends a the same vertex.

Acyclic graph

–A graph without cycles

–DAG (Directed Acyclic Graph)

•Paths and ConnectivityPaths

–A path from vertex u to v of a graph G is defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v.

Simple paths: All edges of a path are distinct.

Path lengths: the number of edges, or the number of vertices – 1.

Connected graphs

–A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.

Connected component

-The maximum connected subgraph of a given graph

Graph Representation :A graph is represented by

•Adjacency matrix

-- n x n boolean matrix if |V| is n.

–The element on the ith row and jth column is 1 if there’s an edge from ith vertex to the jth vertex; otherwise 0.

–The adjacency matrix of an undirected graph is symmetric.

•Adjacency linked lists

A collection of linked lists, one for each vertex, that contain all the vertices adjacent to the

Fig1.h.Graph representation.