11.1
Object-Oriented Programming (OOP)
Object-Oriented Programming (OOP) is a programming paradigm based on the
concept of "objects", which can contain data in the form of fields
(also known as attributes or properties), and code, in the form of procedures
(also known as methods).
Features of OOP:
1. Class and Object:
o A class is a blueprint or template for creating objects.
o An object is an instance of a class.
2. Encapsulation:
o Wrapping data (variables) and code (methods) together as a single unit.
o Helps in data hiding and restricting direct access.
3. Abstraction:
o Hiding internal details and showing only essential features to the user.
o Reduces complexity.
4. Inheritance:
o Mechanism by which one class (child) inherits the properties and behaviors of another class (parent).
o Promotes code reuse.
5. Polymorphism:
o Ability to use a single interface to represent different data types or methods.
o Two types:
§ Compile-time (Function Overloading)
§ Run-time (Function Overriding)
C++ Language
C++ is a general-purpose, middle-level programming language that supports both
procedural and object-oriented programming. It was developed by Bjarne Stroustrup as an extension of
Basic Structure of a C++ Program:
#include <iostream>using namespace std; int main() { cout << "Hello, World!"; return 0;}C++ Language Elements:
1. Header Files:
o
#include <iostream>: Used for
input-output operations.
o
Other examples: <cmath>, <string>, etc.
2. Namespace:
o
using namespace std;: Allows access to
standard C++ library without using std:: prefix.
3. main() Function:
o Entry point of every C++ program.
o
Returns an integer value (return
0;) to indicate successful execution.
4. Input/Output:
o
cout: Used for output.
o
cin: Used for input.
Example:
int age;cout << "Enter your age: ";cin >> age;5. Variables and Data Types:
o
Data Types: int, float, char, double, bool, string
o Example:
int a = 10;float pi = 3.14;char ch = 'A';
6. Operators:
o
Arithmetic: +, -, *, /, %
o
Relational: ==, !=, >, <, >=, <=
o
Logical: &&, ||, !
7. Control Structures:
o
Conditional: if, else, switch
o
Loops: for, while, do...while
o Example:
for(int i = 0; i < 5; i++) { cout << i << endl;}8. Functions:
o Reusable blocks of code.
o Syntax:
int add(int a, int b) { return a + b;}9. Class and Object Example:
class Student {public: string name; int age; void display() { cout << "Name: " << name << ", Age: " << age << endl; }}; int main() { Student s1; s1.name = "Anil"; s1.age = 20; s1.display(); return 0;}
11.2 Object and Class, Overloading Operators, Inheritance, and Virtual Function
1. Object and Class
Class:
A class is a user-defined data type that acts as a blueprint for
creating objects. It defines attributes (data members) and behaviors (member
functions).
class Student {public: string name; int age; void display() { cout << "Name: " << name << ", Age: " << age << endl; }};Object:
An object is an instance of a class. It
occupies memory and can access the class members using the dot (.) operator.
Student s1;s1.name = "Anil";s1.age = 20;s1.display();2. Operator Overloading
Operator overloading allows you to redefine how operators work for user-defined types (like classes). It provides a way to perform operations on objects using traditional operators.
Syntax:
class Complex { int real, imag;public: Complex(int r = 0, int i = 0) : real(r), imag(i) {} // Overloading + Complex operator + (const Complex& c) { return Complex(real + c.real, imag + c.imag); } void display() { cout << real << " + " << imag << "i" << endl; }};Usage:
Complex c1(3, 4), c2(1, 2);Complex c3 = c1 + c2;c3.display(); // Output: 4 + 6i
3. Inheritance
Inheritance allows a class (child or derived class) to inherit properties and behaviors from another class (parent or base class). It promotes code reuse.
Types of Inheritance:
· Single Inheritance
· Multiple Inheritance
· Multilevel Inheritance
· Hierarchical Inheritance
· Hybrid Inheritance
Syntax Example:
class Person {public: string name; void display() { cout << "Name: " << name << endl; }}; class Student : public Person {public: int roll; void show() { cout << "Roll: " << roll << endl; }};Usage:
Student s;s.name = "Anil";s.roll = 101;s.display();s.show();4. Virtual Function
A virtual function is a member function in the base class that you expect to override in derived classes. It supports runtime polymorphism, i.e., the correct function is called for an object depending on its runtime type.
Syntax:
class Base {public: virtual void show() { cout << "Base class show()" << endl; }}; class Derived : public Base {public: void show() override { cout << "Derived class show()" << endl; }};Usage:
Base* bptr;Derived d;bptr = &d;bptr->show(); // Output: Derived class show()Without virtual, it would call Base::show() even if the
object is of Derived type.
11.3 Object Oriented Analysis and Design (OOAD), UML
Object-Oriented Analysis and Design (OOAD)
OOAD is a technical approach for analyzing and designing a system by visualizing it as a group of interacting objects, each defined by its class, data, and behavior.
It has two main phases:
· Object-Oriented Analysis (OOA)
· Object-Oriented Design (OOD)
1. Object-Oriented Analysis (OOA)
Purpose:
· Understand the problem domain
· Identify what the system must do
· Focuses on gathering requirements and modeling them using objects
Activities:
· Identify actors (users/systems)
· Define use cases (actions/functions)
· Identify classes, objects, and their relationships
· Describe system behavior using UML diagrams
2. Object-Oriented Design (OOD)
Purpose:
· Provide a solution to the problem using object-oriented principles
· Focuses on how the system will work
Activities:
· Define class structures and interfaces
· Use design principles (like encapsulation, abstraction)
· Plan interactions between objects
· Choose algorithms and data structures
Benefits of OOAD:
· Better understanding of the system
· Promotes modularity and reusability
· Easier maintenance and testing
· Clear mapping from real-world problems to software
UML – Unified Modeling Language
UML is a standardized modeling language used to visualize, specify, construct, and document the components of object-oriented software systems.
It helps software engineers and stakeholders to understand, design, and communicate software architecture.
Common UML Diagrams (Divided into Two Categories):
1. Structural Diagrams
|
Diagram Type |
Purpose |
|
Class Diagram |
Shows classes, attributes, methods, and relationships |
|
Object Diagram |
Snapshot of class diagram at a specific time |
|
Component Diagram |
Represents components/modules of system |
|
Deployment Diagram |
Shows hardware and software deployment |
2. Behavioral Diagrams
|
Diagram Type |
Purpose |
|
Use Case Diagram |
Shows interactions between users and system |
|
Sequence Diagram |
Shows how objects interact over time |
|
Activity Diagram |
Represents workflows or business processes |
|
State Diagram |
Shows states of an object and transitions |
Example: Use Case Diagram
Example: Class Diagram
11.4 Stack and Queue, Linked List as an ADT, Recursion
1. Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
Operations:
· Push: Insert an element on top
· Pop: Remove the top element
· Peek/Top: View the top element without removing
· IsEmpty: Check if the stack is empty
Real-life Examples:
· Undo functionality in editors
· Backtracking in games
· Function call stack in programming
Example in C++:
#include <stack>stack<int> s;s.push(10);s.push(20);s.pop(); // Removes 20int top = s.top(); // top = 10
2. Queue
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
Operations:
· Enqueue: Insert element at rear
· Dequeue: Remove element from front
· Front: View the front element
· IsEmpty: Check if empty
Real-life Examples:
· Waiting line
· CPU scheduling
· Printer job queue
Example in C++:
#include <queue>queue<int> q;q.push(10);q.push(20);q.pop(); // Removes 10int front = q.front(); // front = 20
3. Linked List as an ADT (Abstract Data Type)
A linked list is a linear data structure where each element (node) contains:
· Data
· Pointer to the next node
Types:
· Singly Linked List
· Doubly Linked List
· Circular Linked List
Abstract Data Type Features:
· Dynamic memory allocation
· Efficient insertion/deletion (compared to arrays)
· No memory wastage
Singly Linked List Node Example:
struct Node { int data; Node* next;};Operations:
· Insert at beginning/end
· Delete node
· Traverse list
4. Recursion
Recursion is a programming technique where a function calls itself to solve a smaller instance of the problem.
Concepts:
· Base Case: Condition to stop recursion
· Recursive Case: Function calling itself
Real-life Examples:
· Factorial calculation
· Fibonacci series
· Tower of Hanoi
· Tree traversal
Example: Factorial Using Recursion
int factorial(int n) { if (n == 0) return 1; // Base case else return n * factorial(n - 1); // Recursive case}Example: Fibonacci
int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2);}
11.5 Trees, Sorting, Search, and Graph
1. Trees
A tree is a hierarchical data structure consisting of nodes, with one node as the root and others as children, forming a parent-child relationship.
Terminology:
· Root: Topmost node
· Leaf: Node with no children
· Parent/Child: Direct relationship
· Subtree: Descendants of a node
· Height: Longest path from root to a leaf
Types of Trees:
1. Binary Tree: Each node has at most 2 children
2. Binary Search Tree (BST): Left child < root < right child
3. Balanced Tree: Height difference of left and right subtrees is minimal
4. Heap Tree: Used in priority queues
Binary Tree Example:
struct Node { int data; Node* left; Node* right;};
2. Sorting Algorithms
Sorting is the process of arranging elements in ascending or descending order.
|
Algorithm |
Time Complexity |
Method |
Stable |
|
Bubble Sort |
O(n²) |
Compare & swap |
Yes |
|
Selection Sort |
O(n²) |
Find min & place |
No |
|
Insertion Sort |
O(n²) |
Insert in right position |
Yes |
|
Merge Sort |
O(n log n) |
Divide & merge |
Yes |
|
Quick Sort |
O(n log n) avg, O(n²) worst |
Partitioning |
No |
Bubble Sort Example:
void bubbleSort(int arr[], int n) { for(int i = 0; i < n-1; i++) for(int j = 0; j < n-i-1; j++) if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);}3. Searching Algorithms
Searching is the process of finding an element in a list or structure.
|
Method |
Time Complexity |
Type |
|
Linear Search |
O(n) |
Sequential |
|
Binary Search |
O(log n) |
Divide & conquer (requires sorted list) |
Linear Search Example:
int linearSearch(int arr[], int n, int key) { for(int i = 0; i < n; i++) if(arr[i] == key) return i; return -1;}Binary Search Example:
int binarySearch(int arr[], int left, int right, int key) { while(left <= right) { int mid = left + (right - left) / 2; if(arr[mid] == key) return mid; else if(arr[mid] < key) left = mid + 1; else right = mid - 1; } return -1;}4. Graph
A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections).
Types of Graphs:
· Undirected Graph: Edges have no direction
· Directed Graph (Digraph): Edges have direction
· Weighted Graph: Edges have weights (cost/distance)
· Unweighted Graph: No weight assigned
Representations:
1. Adjacency Matrix
o
2D array where matrix[i][j] = 1 if edge exists
2. Adjacency List
o Array of lists showing neighbors of each vertex
Applications:
· Social networks
· Routing and GPS
· Web page link analysis
Example (Adjacency List in C++):
vector<int> adj[5];adj[0].push_back(1);adj[0].push_back(4);Graph Traversal:
· DFS (Depth First Search)
· BFS (Breadth First Search)