Introduction of C++ Text book UNIT-1 .ppt

C++ basics

1. Data:
Data is nothing but a piece of information.
Data input, data manipulation (or data
processing), and data output are the
functions of computers.
It can be a number, a string, or a set of
many numbers and strings

2. Data Type
Data type is a term that specifies
the type of data, variable may store.

3. Built-in Data Types
Languages have their built-in data types.
Using the built-in data types, C/C++ languages
having int, float, and char are built-in data types.
It allows the user to define his or her own data
types called user-defined data types.
Using these built-in data types, we can design
(define) our own data types by means of
structures, unions, and classes.

4. Abstract Data Type:
An Abstract Data Type includes declaration
of data, implementation of operations, and
encapsulation of data and operations.

5. Data structure: It is a mechanism to organize the
data in different ways and perform possible
operations on these structures.
The data structure operations include insertion,
deletion, modification, searching e.t.c., data structure
also measures the efficiency of the algorithm and
time complexity of the program.

6. Data structures are classified into two
types.
Linear : Linked lists
Non –Linear: Trees and graphs

7. TYPES OF DATA STRUCTURES
We defined a data structure as a way of
organizing data that specifies
1. A set of data elements, i.e., a data object
2. A set of operations that are applied to this data
object.
These two sets form a mathematical construct
that may be implemented using a particular
Programming language. The data structure is
independent of their implementation.

8. The various types of data structures are as
follows:
1. Primitive and Non-primitive
2. Linear and Non-linear
3. Static and Dynamic
4. Persistent and Ephemeral
5. Sequential and direct access

9. Primitive and Non-Primitive Data Structures
Primitive data structures define a set of primitive
elements that do not involve any other elements
as its subparts.
Example:Data structures defined for integers
and characters. These are generally primary or
built-in data types in programming languages.

10. Non-primitivedata structures are those define a
set of derived elements such as arrays, classes
and structures.
Arrays in C++ consist of a set of similar type of
elements.
Class and Structure are consisting of a set of
elements that may be of different data types and
functions to operate on.

11. Linear and Non-linear Data Structures
Data structures are classified as Linear and Non-linear.
A data structure is said to be linear if its elements form a
sequence or a linear list.
In a linear data structure, every data element has a unique
successor and predecessor.
There are two basic ways of representing linear structures in
memory.
One way is to have the relationship between the elements by
means of pointers (links), called linked lists.
The other way is using sequential organization, that is,
arrays.

12. Non-linear data structures are used to represent the
data containing hierarchical ornetwork relationship
among the elements
Trees and graphs are examples of non-linear data
structures.
In non-linear data structures, every data element may
have more than one predecessor as well as successor

13. Static and Dynamic:
Static
A data structure is referred to as a static data
structure if it is created before program
execution begins (also called during compilation
time).
The variables of static data structure have user-
specified names. An array is a static data
structure

14. Dynamic Data Structures
A data structure that is created at run-time is called
dynamic data structure. The variables of this type
are not always referenced by a user-defined name.
These are accessed indirectly using their addresses
through pointers.
Non-linear data structures are generally
implemented in the same way as linked lists. Hence,
trees and graphs can be implemented as dynamic
data structures.

15. Persistent and Ephemeral Data Structures
A persistent data structure is partially persistent if
any version can be accessed but only the most
recent one can be updated, it is fully persistent if
any version can be both accessed and updated.
An ephemeral data structure is one that supports
operations only on the most recent version.

16. Sequential Access and Direct Access Data
Structures
This classification is with respect to the access
operations associated with data structures.
Sequential access means that to access the nth
element, we must access the preceding (n -1) data
elements. A linked list is a sequential access data
structure.
Direct access means that any element can be
accessed without accessing its predecessor or
successor, we can directly access the nth element.
An array is an example of a direct access data
structure.

17. Algorithms
A programmer should first solve the problem in a
step-by-step manner and then try to find the
appropriate instruction or series of instructions that
solves the problem. This step-by-step solution is
called an algorithm.
An algorithm is independent of the computer system
and the programming language.
Each algorithm includes steps for
1. Input,
2. Processing, and
3. Output.

18. An algorithm is a well-defined computational
procedure that transforms inputs into outputs
achieving the desired input–output relationship.
A computational problem is a specification of
the desired input–output relationship.
An instance of a problem is all the inputs
needed to compute a solution to the problem.
A correct algorithm halts with the correct
output for every input instance

19. Pseudocode
A pseudocode is an English-like presentation of
the code required for an algorithm.
It is partly English and partly computer language
structure code.
The structure code is nothing but syntax
constructs of a programming language (in a
slightly modified format).

20. Implementation of Data Structures
Implementation of data structures can be viewed in
terms of two phases:
Specification
Implementation
SpecificationAt the first stage, a data structure
should be designed so that we know what it does
and not necessarily how it will do it.

21. Implementation
At this stage, we define all functions with
respect to the description of how to manipulate
data. This can be done with algorithms so that
the details of the operation can be understood
easily and the reader can implement them
easily and effectively with the help of any
programming language.
Either of the design tools, that is, an algorithm
or a flowchart, can be used at this phase.

22. Analysis of algorithms
Algorithms heavily depend on the organization
of data. There can be several ways to organize
data and / or write algorithms for a given
problem.
The difficulty lies in deciding which algorithm is
the best.

23. Complexity of Algorithms
Algorithms are measured in terms of time
and space complexity.
The time complexity of an algorithm is a
measure of how much time is required to
execute an algorithm for a given number of
inputs and is measured by its rate of growth
relative to standard functions.

24. Space Complexity
Space complexity is the amount of
computer memory required during program
execution as a function of the input size.
Space complexity measurement, which is
the space requirement of an algorithm, can
be performed at two different times:
1. Compile time
2. Run time

25. Compile Time Space Complexity
Compile time space complexity is defined as the storage
requirement of a program at compile time.
This storage requirement can be computed during
compile time.
The storage needed by the program at compile time can
be determined by summing up the storage size of each
variable using declaration statements.
For example,the space complexity of a non-recursive
function of calculating the factorial of number n
depends on the number n itself.
Space complexity = Space needed at compile time
This includes memory requirement before execution
starts.

26. Run-time Space Complexity
If the program is recursive or uses dynamic
variables or dynamic data structures, then there
is a need to determine space complexity at run-
time.

27. Computing Time Complexity of an Algorithm
Time complexity T (P) is the time taken by a program P, i.e.,
the sum of its compile and execution times.
The time required by each statement depends on the following:
Fundamental concepts
1. The time required for executing it once
2. The number of times the statement is executed
The product of these two parameters gives the time required
for that particular statement.
Compute the execution time of all executable statements. The
summation of all the execution times is the total time required
for that algorithm or program.

28. Stack:
A stack is defined as a restricted list where all
insertions and deletions are made only at one end,
the top.
Stack is a LIFOstructure. (Last in First out).

29. EXAMPLES OF STACK:

30. QUEUE:
Queue is an abstract data type or a linear
data structure.
The first element is inserted from one end
called REAR(also called tail)
The deletion of existing element takes place
from the other end called as FRONT(also
called head).
This makes queue as FIFO data structure, which
means that element inserted first will also be
removed first.

31. Queue Operations:
The process to add an element into queue is called Enqueue
The process of removal of an element from queue is called
Dequeue.

32. Stack Operations:
There are two basic operations
Push and Pop that can be performed on a stack.
Insertion of an element in the stack is called
Push
Deletion of an element from the stack is called
Pop.
In stacks, we cannot access data elements from
any intermediate positions other than the top
position

33. Stack ADT (Abstract Data Type):
An ADT is defined by the operations you can perform
on it.
constructor-Create a new, empty stack.
push -Add a new item to the stack.
pop -Remove an item from the stack. The item that
is removed is always the last one that was added.
Top-Return an item from the stack. The item that is
returned is always the last one that was added.
empty-Check whether the stack is empty.
A stack is sometimes called a "last in, first out," or
LIFO data structure, because the last item added is the
first to be removed.

34. Operations that can be performed on STACK:
PUSH.
POP.

35. Features of Stack
Stack is an ordered list of similar data type.
Stack is a LIFOstructure. (Last in First out).
Push()function is used to insert new elements into the
Stack
Pop()is used to delete an element from the stack.
Both insertion and deletion are allowed at only one
end of Stack called Top.
Stack is said to be in Overflowstate when it is
completely full and is said to be in Underflowstate if
it is completely empty.

36. PUSH: It is used to insert items into the stack.
POP:It is used to delete items from stack.
TOP:It represents the current location of data in stack.

37. Representation of Stacks using Sequential Organization
(Arrays)
A stack implemented using an array is also called a contiguous
stack.
An array is used to store an ordered list of elements.
A stack is an ordered collection of elements.
It would be very simple to manage a stack when represented using
an array.
The only difficulty with an array is its static memory allocation.
Once declared, the size cannot be modified during run-time.

38. 0 1 2 n-1
Top
Let Stack[n] be a one-dimensional array.
When the stack is implemented using arrays, one of the two sides of the
array can be considered as the top (upper) side and the other as the bottom
(lower) side.
Let us discuss the top side, which is most commonly used.
The elements are stored in the stack from the first location onwards.
The first element is stored at the 0th location of the array Stack, which
means at Stack[0].
The second element at Stack[1].
The ithelement at Stack[i-1].
The nth element at Stack[n -1].
A B C …

39. ALGORITHM OF INSERTION IN STACK: (PUSH)
•stack()
•{
•top=-1;
•}
•void push(intx)
•{
•if(top > 4)
• {
•cout<<"stack over flow";
• return;
• }
•stk[++top]=x;
•cout<<"inserted" <<x;
•}

40. ALGORITHM OF DELETION IN STACK: (POP)
•void pop()
•{
•if(top <0)
•{
•cout<<"stack under flow";
•return;
•}
•cout<<"deleted" <<stk[top--];
•}

41. ALGORITHM OF DISPLAY IN STACK: (DISPLAY)
•void display()
• {
• if(top<0)
• {
• cout<<" stack empty";
• return;
• }
• for(inti=top;i>=0;i--)
• cout<<stk[i] <<" ";
• }

42. Multiple Stacks
The contiguous stack (stack using an array) uses
separate arrays for more than one stack, if needed.
The use of a contiguous stack when more than one
stack is needed is not a space-efficient approach,
because many locations in the stacks are often left
unused.
An efficient solution to this problem is to use a single
array to store more than one stack.

43. Stack1 Stack2
0 1 2 3 n-2 n-1
Top1 = 2 Top2=n-2
Multiplestackscanbeimplementedbysequentially
mappingthesestacksintoA[0],...,A[n−1].
Thesolutionissimpleifweimplementonlytwo
stacks.
ThefirststackgrowstowardsA[n-1]fromA[0]and
ThesecondstackgrowstowardsA[0]fromA[n−1].
123…….. BA

44. APPLICATIONS OF STACK:
Converting infix expression to postfix and prefix expressions
Evaluating the postfix expression
Checking well-formed (nested) parenthesis
Reversing a string
Processing function calls
Parsing (analyze the structure) of computer programs
Simulating recursion
In computations such as decimal to binary conversion
In backtracking algorithms (often used in optimizations and in
games)

45. Expression Evaluation and Conversion:
The most frequent application of stacks is in the evaluation
of arithmetic expressions. An arithmetic expression is made
of operands, operators, and delimiters.
The following operators are written in descending order of
their precedence:
1. Exponentiation (^), Unary (+), Unary (-), and not (~)
2. Multiplication (\) and division (/)
3. Addition (+) and subtraction (-)
4. Relational operators <, <, =, ≥, >
5. Logical AND
6. Logical OR

46. Consider the following expression:
X = a/b \c -d
Let a = 1, b = 2, c = 3, and d = 4.
One of the meanings that can be drawn from this
expression could be
X = (1/2) \(3 -4) = -1/2

47. Polish Notation and Expression Conversion
The Polish Mathematician Han Lukasiewicz suggested a notation
called Polish notation, which gives two alternatives to represent an
arithmetic expression, namely the postfix and prefix notations.
The fundamental property of Polish notation is that the order in
which the operations are to be performed is determined by the
positions of the operators and operands in the expression.
Hence, the advantage is that parentheses is not required while
writing expressions in Polish notation.
The conventional way of writing the expression is called infix,
because the binary operators occur between the operands, and
unary operators precede their operand.

48. Expression (A+B)*C is an Infix expression
Infix Expression : LOperand Operator ROperand
Prefix Expression : Operator LOperand ROperand
*+ABC
Postfix Expression : LOperand ROperand Operator
AB+C*

49. REVERSING A STRING WITH A STACK
Suppose a sequence of elements is presented and it is desired
to reverse the sequence.
A conceptually simple solution, however, is based on using a
stack.
The LIFO property of the stack access guarantees the
reversal.
Suppose the sequence ABCDEF is to be reversed. With a
stack, one simply scans the sequence, pushing each element
onto the stack as it is encountered, until the end of the
sequence is reached. The stack is then popped repeatedly,
with each popped element sent to the output, until the stack
is empty.

50. Input Action Stack Display
ABCDEF PushA A ¨top of stack –
BCDEF PushB AB ¨top of stack –
CDEF PushC ABC ¨top of stack –
DEF PushD ABCD ¨top of stack –
EF PushE ABCDE ¨top of stack –
F PushF ABCDEF ¨top of stack –
End displayandPop ABCDE ¨top of stack F
displayandPop ABCD ¨top of stack FE
displayandPop ABC ¨top of stack FED
displayandPop AB ¨top of stack FEDC
displayandPop A ¨top of stack FEDCB
displayandPop Stack empty FEDCBA
Stop

51. Recursion:
In C/C++, a function can call itself, that is, one of the statements of the
function is a call to itself. Such functions are called recursive functions
and can be used to implement recursive problems in an elegant manner.
Consider the recursive implementation of factorial given that
1! = 1 and n! = n \(n -1)!
The recursive function in C++ is given by the following statement:
long intfactorial (unsigned intn)
{
if(n <= 1)
return(1);
else
return(n * factorial(n − 1));
}