[go: up one dir, main page]
Scribd
Upload
9 views20 pages

Data Structure Code Efficiency

The document covers various data structures including arrays, linked lists, queues, stacks, trees, and graphs, highlighting the differences between linear and non-linear data structures. It details basic operations on arrays such as reading, traversal, searching, sorting, and merging, along with their complexities. Additionally, it explains algorithms for bubble sort, linear search, and binary search, providing code examples and their respective time complexities.

Uploaded by

zubairabd38
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
9 views20 pages

Data Structure Code Efficiency

The document covers various data structures including arrays, linked lists, queues, stacks, trees, and graphs, highlighting the differences between linear and non-linear data structures. It details basic operations on arrays such as reading, traversal, searching, sorting, and merging, along with their complexities. Additionally, it explains algorithms for bubble sort, linear search, and binary search, providing code examples and their respective time complexities.

Uploaded by

zubairabd38
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 20

Lecture 3, 4

ADT, Arrays and Strings


Types of Data Structures
Types of Data Structures

array

Linked list

queue
tree stack
Linear vs Non Linear Data
Structures
• There is a concept of linearity b/w the components is
called linear data structure.
• The components exists in a certain sequence one after
another.
• They have some successor or predecessor
• Example, Arrays, Stack, Queues etc.
• The data structure in which the order of data structure does
not matter and is not fixed
• Example Tree, Graph etc
Array Basic Operations
 Reading
Traversal
Searching
Sorting
 Merging
Array Template
Type parameters can be used as
1. Data members of class.
2. Arguments of class functions.
3. Local variable in class functions.
4. Return type of class functions.
Array Template
Array Template
Function Implementation
Function Implementation
Function Implementation
Default value of Parameters
Array Reading
void read()
{
int num;
cout << “How many values you want to insert”;
cin >> num;
for (int i=0; i< num;i++)
{
cout << "Enter value ";
cin >>a[i];
}
n = num;
}
Complexity of reading: O(n)
Complexity of adding one element at end: O(1)
Array Traversal
1. for (j= 0, j<n, j++)
Apply process to a[j]
2. Exit

Complexity: O(n)

Exercise:
 Sum of all elements of array
 Average of all elements of array
 Find minimum
 Count all even numbers in array
Merging Two Arrays
void merge(Array a1, Array a2)
{
int i=0, j=0;
while (i< a1.n && j< a2.n )
{
if (a1.a[i] < a2.a[j])
{
a[n] = a1.a[i];
i++;
}
else
{
a[n] = a2.a[j];
j++;
}
n++;
}
Merging Two Arrays(Cont’d)
while (i < a1.n)
{
a[n] = a1.a[i];
i++; n++;
}
while (j < a2.n)
{
a[n] = a2.a[j];
j++; n++;
}
}
Complexity: O(m+n)
Bubble Sort
1. For (i= 0; i < n-1; i++)
2. For (j=0 ; j < n-i-1;j++ )
if (a[j+1] < a[j])
swap the two values
3. Exit

Complexity: O(n2)
Linear Search
1. Found = false
2. Read key
3. For (i= 0; i< n && !found; i++)
if (key == a[i])
found = true;
3. If (Found)
print (found)
else
print (not found) .
4. Exit

Complexity: O(n)
Binary Search
•You have a sorted list of numbers
•You need to search the list for the number
•If the number exists find its position.
•If the number does not exist you need to detect
that whether to change lower or upper bound.
Binary Search
1. Found = false, low=0, high = n-1.
2. Read key
3. while (low<= high && !found)
{
mid = (low + high)/2
if (key == a[mid])
found = true
else if (key <a[mid])
high = mid -1
else
low = mid + 1
}
3. If (Found)
print (found)
else
print (not found) .
4. Exit Complexity:
O(logn)

You might also like