DS chapter 1.ppt.................................

ppt

1. Introduction to Data Structures
•Problem solving with a computer means processing data.
•To process data, we need to define the data type and the
operation to be performed on the data.
•The definition of the data type and the definition of the
operation to be applied to the data is part of the idea behind an
abstract data type (ADT).
•In other words, the user of an ADT needs only to know that a
set of operations are available for the data type, but does not
need to know how they are applied.

2. Introduction to Data Structures
•Many programming languages already define some simple
ADTs as integral parts of the language.
•For example, the C language defines a simple ADT as an
integer. The type of this ADT is an integer with predefined
ranges. C also defines several operations that can be applied to
this data type (addition, subtraction, multiplication, division and
so on).
•C explicitly defines these operations on integers and what we
expect as the results. A programmer who writes a C program to
add two integers should know about the integer ADT and the
operations that can be applied to it.

3. Complex ADTs
Although several simple ADTs, such as integer, real, character,
pointer and so on, have been implemented and are available for use
in most languages, many useful complex ADTs are not.
As we will see in this chapter, we need a list ADT, a stack ADT, a
queue ADT and so on.
To be efficient, these ADTs should be created and stored in the
library of the computer to be used.

4. Definition
An abstract data type is a data type packaged with the operations
that are meaningful for the data type.
We then encapsulate the data and the operations on the data and
hide them from the user.
Abstract data type:
1. Definition of data.
2. Definition of operations.
3. Encapsulation of data and operation.

5. Stacks
5
Definition

“A set of data values and associated operations
that are precisely specified independent of any
particular implementation”.

“In computing, an abstract data type (ADT) is a
specification of a set of data and the set of
operations that can be performed on the data”.

” A unique data type that is defined by the
programmer. It may refer to an object class in
object-oriented programming or to a special data
type created in traditional, non-OOP languages”

6. 6
ADTs Example
An abstract data
type (ADT) is an
abstraction of a
data structure
An ADT specifies:

Data stored

Operations on
the data

Error conditions
associated with
operations

Example: ADT modeling a
simple stock trading system

The data stored are buy/sell
orders

The operations supported are

order buy(stock, shares, price)

order sell(stock, shares, price)

void cancel(order)

Error conditions:

Buy/sell a nonexistent stock

Cancel a nonexistent order

7. Introduction to Pointers
•A pointer is a constant or variable that contains an address that can
be used to access data. Pointers are built on the basic concept of
pointer constants.
•Consider the declaration,
int i = 3 ;
•This declaration tells the C compiler to:
(a) Reserve space in memory to hold the integer value.
(b) Associate the name i with this memory location.
(c) Store the value 3 at this location.
•We may represent i’s location in memory by the following memory
map.
i ----------- Variable
----------- Value

65524 ------------ Address
3

8. Introduction to Pointers
We can print this address and number through the following program:
main( )
{
int i = 3 ;
printf ( "\nAddress of i = %u", &i ) ;
printf ( "\nValue of i = %d", i ) ;
}
The output of the above program would be:
Address ofi = 65524
Value of i = 3

9. Introduction to Pointers
•Look at the first printf( ) statement carefully. ‘&’ used in this statement
is C’s ‘address of’ operator.
•The expression &i returns the address of the variable i, which in this
case happens to be 65524.
•Since 65524 represents an address, there is no question of a sign being
associated with it.
•Hence it is printed out using %u, which is a format specifier for
printing an unsigned integer.
•We have been using the ‘&’ operator all the time in the scanf( )
statement.

10. Introduction to Pointers
•The other pointer operator available in C is ‘*’, called ‘value at
address’ operator.
•It gives the value stored at a particular address. The ‘value at address’
operator is also called ‘indirection’ operator.
•Observe carefully the output of the following program:
main( )
{
int i = 3 ;
printf ( "\nAddress of i = %u", &i ) ;
printf ( "\nValue of i = %d", i ) ;
printf ( "\nValue of i = %d", *( &i ) ) ;
}

11. Introduction to Pointers
•Look at the following declarations,
int *alpha ;
char *ch ;
float *s ;
•Here, alpha, ch and s are declared as pointer variables, i.e. variables
capable of holding addresses.
•Remember that, addresses (location nos.) are always going to be
whole numbers, therefore pointers always contain whole numbers.
•Now we can put these two facts together and say —pointers are
variables that contain addresses, and since addresses are always whole
numbers, pointers would always contain whole numbers.

12. Introduction to Pointers
•The declaration float *s does not mean that s is going to contain a
floating-point value.
•What it means is, s is going to contain the address of a floating-point
value.
•Similarly, char *ch means that ch is going to contain the address of a
char value. Or in other words, the value at address stored in ch is going
to be a char.

13. DATA STRUCTURES
“The logical & Mathematical representation of data in
computer memory is called as Data Structure”.
OR
“A data structure is a method of storing data in a
computer so that it can be used efficiently”.

14. DATA STRUCTURES
The Data Structures mainly deal with:
•The study of how the data is organized in the memory.
•How efficiently the data can be stored in the memory.
•How efficiently the data can be retrieved &
manipulated.

15. DATA STRUCTURES
The Data Structure can be divided into
 

Primitive
The Primitive Data Structures are data structures that can be
manipulated directly by machine instructions.
Ex: int, float, char, double.
Non-Primitive
Non-primitive data structures cannot be manipulated directly by
machine instructions.
Ex: linear and Non linear

16. DATA STRUCTURES
Linear Data Structures :
A data structure is said to be linear if its elements form
a sequence, or, in other words, a linear list.
Example : Arrays, Stacks, Quees, lists
Non linear Data Structures :
A data structure is said to be non linear if its elements
are stored randomly in memory.
Example : Graphs, Trees, Files

17. Arrays
•It is a linear data structure
•A data structure is said to be linear if its elements form a sequence, or
in other words, a linear list.
•There are two basic ways of representing such linear structures in
memory.
•One way is to have the linear relationship b/w the elements represented
by means of sequential memory locations.
E.g. Arrays

18. Arrays
•The other way is to have the linear relationship b/w the elements
represented by means of pointers or links.
E.g. Linked lists
•The following operations normally performs on linear
structure:
Traversal , Search , Insertion , Deletion , Sorting , Merging

19. LINEAR ARRAYS:
•A Linear array is a list of finite number n of homogeneous data
elements, which is stored in contiguous memory locations.
•Each array element shares the same name as the array name, but
distinguishes itself from other elements in the array using a subscript,
or an index.
•The subscript, or the index of each array element is determined based
on the number of offset positions it is from the starting position.
 
Syntax:
A[1], A[2], A[3],……….,A[n].

20. E.g. A[n] where n = 5. 10,50,32,48,100
  A[1] = 10, A[2] = 50, A[3] = 32, A[4] = 48, A[5] = 100.
Data-type array-name [expression];
int a[10];
The declaration int a[10]; defines an array a of size 10, as a
block of 10 contiguous elements in memory.

a
The amount of storage required to hold an array is directly
related to integer type & size.
a[0]a[1
]
a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]

21. Arrays and Pointers
•The name of an array is a pointer constant to the first
element.
•Because the array’s name is a pointer constant, its value
cannot be changed.
•Since the array name is a pointer constant to the first
element, the address of the first element and the name of
the array both represent the same location in memory..

22. Pointers to Arrays

23. same
a &a[0]
a is a pointer only to the first element—
not the whole array.
NoteNote

24. Dereference of Array Name

25. Array Names as Pointers

26. Pointer Arithmetic and Arrays
•Besides indexing, programmers use another powerful method
of moving through an array: pointer arithmetic.
•Pointer arithmetic offers a restricted set of arithmetic operators
for manipulating the addresses in pointers.

27. Pointer Arithmetic

28. Character Arrays:
•  To define a character array for storing a string of n characters,
we would need to define a character array of size n+1 characters.
• This is because all character arrays are terminated by a NULL
character (‘\0’).
• To define a character array called name for storing a ten-
character name, we will define the array as:
Char name[11];
where name[0] through name[9] will contain the characters comprising
the name, and name[10] will store the NULL character.

29. Representation of a Character Array :
name[0]name[1]name[2]name[3]name[4] name[6]name[5] name[7] name[9]name[10]name[8]
name
a b c d e f g h i j
\0