Introduction to Data

Structures
DOCSE, SVNIT, Surat
Introduction to Data Structures
• In simple words, Data Structure is just a way to store and organize
data so that it can be used efficiently.
• It is a representation of the logical relationship existing between
individual element of data.
• DS deals with storage and Access of data in different way depending
on purpose and application.
• Some of the common Data Structures are Array, Structure, Linked List,
Stack, Queue, priority queues, Tree, Graph, etc.
Data Type
• The most basic and the most common classification of data helps
compiler to know the form or the type of information that will be
used throughout the code
• what type of data is to be stored?
• how much space is required in the memory?
• Some basic examples are int, char, float etc.
• It is the type of any variable used in the code.
Data Structure
• A Collection of different forms and different types of data with a set
of specific operations.
• A way of organizing the items in terms of memory and accessing each
item through some defined logic.
• Eg. stacks, Queues, Linked lists, Tree, Graph and many more.
• Study of DS focuses on operation like creation , insertion, deletion
and traversal.
Operations on Data Structure
1. Creation: Initialization of the beginning
2. Insertion : Adding new details or new node into the data structure.
3. Deletion: Removing a node from the data structure.
4. Traversal : Accessing each node exactly once so that the node of the
data structure can be processed. It is also called visiting.
5. Searching: Finding the location of node for a given key value.
6. Sorting: Arranging a data in a particular order
7. Merging : Joining two lists.
DATA TYPES DATA STRUCTURES
the collection of different kinds of data. That
entire data can be represented using an object
kind or form of a variable which is being used and can be used throughout the entire
throughout the program with assigned values program.
Implementation through Data Types is a form Implementation through Data Structures is
of abstract implementation called concrete implementation
Can hold different kind and types of data
Can hold values and not data, so it is data less within one single object
The data is assigned to the data structure
Values can directly be assigned to the data type object using some set of algorithms and
variables operations like push, pop and so on.
Time complexity comes into play when working
No problem of time complexity with data structures
Examples: int, float, double Examples: stacks, queues, tree
Data Structure categorization
Primitive and Non-Premitive
• Primitive Data Structures
• The data structure, that are directly operated upon by machine level
instructions.
• Different representations on different computers.
• E.g. Integers, Floating point numbers, Character constants, String
constants and Pointers
• Non-primitive Data Structures
• more complicated data structures, derived from primitive data structures.
• Group of same or different data items with relationship between each data
item.
• E.g. Arrays, Lists and File
Linear and Non-Linear
• Linear Data Structures
• Data are accessed in a sequential manner
• The elements can be stored in these data structures in any order.
• Eg. Array, Linked List, Stack, Queue, Hashing, etc.
• Non-Linear Data Structure
• Elements are not stored in linear manner
• The data elements have hierarchical relationship which involves the
relationship between the child, parent, and grandparent
• E.g. Trees, Binary Search Trees, Graphs, Heaps, Segment Tree etc.
Sequential and Non-Sequential
• Sequential Data Structure
• Storage of data is contiguous
• E.g. Array
• Non Sequential Data Structure
• Storage of data is Non contiguous
• E.g. Linked List
Homogenous and Non-Homogeneous
• Homogenous Data structure
• All the data elements are of same type.
• E.g. Array
• Non- Homogenous Data structure
• The elements may or may not be of the same type.
• E.g. Structures
Type Typical Bit Width Typical Range
Primitive char 1byte -127 to 127 or 0 to 255

Data unsigned char

signed char
1byte
1byte
0 to 255
-127 to 127
Structure int 4bytes -2147483648 to 2147483647
unsigned int 4bytes 0 to 4294967295
signed int 4bytes -2147483648 to 2147483647
short int 2bytes -32768 to 32767
unsigned short int 2bytes 0 to 65,535
signed short int 2bytes -32768 to 32767
long int 8bytes -2,147,483,648 to 2,147,483,647
signed long int 8bytes same as long int
unsigned long int 8bytes 0 to 4,294,967,295
long long int 8bytes -(2^63) to (2^63)-1
unsigned long long int 8bytes 0 to 18,446,744,073,709,551,615
float 4bytes
double 8bytes
long double 12bytes
Integer
• Integer
• Size 4 Byte
• Signed Integer and Unsigned Integer
Signed and Unsigned Int
• In Signed Int
• left most bit (MSB) is used to denote the sign (negative or Positive)
• The rest of the bits are then used to denote the value normally.
• MSB is used to denote whether it's positive (with a 0) or negative (with a 1).
• A sign bit of 0 denotes that the number is a non-negative.
• May be equal to the decimal zero or a positive number.
• The negative number is stored in 2’s Complement notation
Example
Assuming 8 bit storage : (-/+) 26 25 24 23 22 21 20
010011012 = +7710 0 1 0 0 1 1 0 1

Assuming 4 bit storage :

23 22 21 20
01012 = +510 0 1 0 1

Assuming 4 bit storage : (-/+) 22 21 20

10012 = -710 1 0 0 1

Assuming 4 bit storage :

(-/+) 22 21 20
00002 = +010 0 0 0 0
Assuming 4 bit storage :
(-/+) 22 21 20
10002 = -810 1 0 0 0
2’s complement
Character
• char is the most basic data type in C.
• It stores a single character and requires a single byte of memory in
almost all compilers.
• Now character datatype can be divided into 2 types:
• signed char
• unsigned char
Signed and Unsigned char
• Unsigned char is a character type where the variable consumes all the
8 bits of memory and there is no sign bit.
• unsigned char c=97
• ASCII value 97 will be converted to a character value, i.e. ‘a’ and it will be
inserted in unsigned char.
• unsigned char = -1 (Initializing with signed value)
• ASCII value -1 will be first converted to255
• this value will be converted to a character value, i.e. ‘ÿ’ and it will be inserted
in unsigned char.
Abstract Data Type
• ADT are like user defined data types which defines operations on
values using function without specifying what is there inside the
function and how the operation are performed.
• Ex: Stack ADT
• A stack consist of element of same type arranged in sequential order.
• ADT as a black box which hides the inner structure and design of the
data type from the user.
• There are multiple ways to implement an ADT.
• Ex: Stack ADT can be implemented using arrays or linked lists.
Internal Representation of Array
• All the elements are stored in contiguous memory locations.
• Address of the 1-D array can be calculated by: Address of A[i] = BA+
w * i.
• where i [ is a location (Indexing) of element] whose address is to be
found out. w (is the size of data type), BA is base address.
Internal Representation of Array
2D Array
• The computer memory is an one-dimensional sequence of bytes.
• C compiler stores the two-dimensional (multi dimension in general)
object in row-major order in the memory.
• Row major ordering assigns successive elements, moving across the
rows and then down the columns, to successive memory locations.
RMO: Address of A[i, j]th element in A[R, C] matrix

A[i, j] = BA + W * (C*i + j)

Where BA is the address of the first element in an array.

W= is the weight (size) of a data type.
C= is total No of Columns.
i= is the Row Number
j= is Column Number of an element whose address is to find out.
RMO: Address of A[i, j]th element in A[R, C] matrix
CMO: Address of A[i, j]th element in A[R, C] matrix
Introduction to String
• Strings are defined as an array of characters. The difference between
a character array and a string is the string is terminated with a special
character ‘\0’.
Read String from the user :
Read String from the user
• we have used fgets() function to read a string from the user.
fgets(name, sizeof(name), stdlin); // read string
• The sizeof(name) results to 30. Hence, we can take a maximum of 30
characters as input which is the size of the name string.
• To print the string, we have used puts(name);
• Note: The gets() function can also be used to take input from the user.
However, it is removed from the C standard.
• It's because gets() allows you to input any length of characters.
Hence, there might be a buffer overflow.
Representation of string in memory
• In the C programming language, strings are represented as arrays
of characters. Each character in the array corresponds to a
specific element in the string. The string is terminated by a null
character ('\0'), which indicates the end of the string.
• The characters are stored sequentially in memory, with each
character occupying one byte. The array is allocated a
contiguous block of memory, where each element represents a
character in the string.
• Let's consider the string "Hello". In memory, it would be
represented as an array of characters: ['H', 'e', 'l', 'l', 'o', '\0']. The
null character at the end indicates the termination of the string.
Structure:
• There is no class in C, but we may still want non-homogenous
structures
• So, we use the struct construct
• struct for structure
• A struct is a data structure that comprises multiple types, each known as a
member
• each member has its own unique name and a defined type
• Example:
• A student may have members: name (char[ ]), age (int), GPA (float or double), sex (char),
major (char[ ]), etc
• If we want to create a structure that can vary in size, we will allocate the
struct on demand and attach it to a previous struct through pointe
• struct is a keyword for defining a structured declaration
• Format:
struct name { name1 and name2
type1 name1; are members of name
type2 name2;
…
};
Accessing structs
• A struct is much like an array
• The structure stores multiple data
• You can access the individual data, or you can reference the entire structure
• To access a particular member, you use the . operator
• as in student.firstName or p1.x and p1.y
Memory allocation in Structure