UNIT-5
Strings
Character Array: String
• The string can be defined as the one-dimensional array of characters terminated
by a null character ('\0').
char msg[6] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
OR char msg[ ] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
OR char msg[ ] = “Hello”;
• There are two ways to declare a string in c language.
1. By char array
To hold the null character at the end of the array, the size of the character array
containing the string is one more than the number of characters in the word
“Hello”.
char msg[6] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
OR char msg[ ] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
2. By string literal:
In such case, '\0' will be appended at the end of the string by the compiler.
char msg[ ] = “Hello”;
Difference between char array and string literal
• There are two main differences between char array and literal.
• We need to explicitly add the null character '\0' at the end of the
array. whereas, it is appended implicitly by the compiler in the
case of the string literals.
• The string literal cannot be reassigned to another set of
characters whereas, we can reassign the characters of the array.
NOTE: The “%s” is used as a format specifier for the string in c
language.
Example : String
Example : String
Accepting string as the input
• Till now, we have used scanf to accept the input from the user.
However, it can also be used in the case of strings but with a
different scenario.
Accepting string as the input (including spaces)
• Code (previous slide) does not work for space separated strings.
• To make this code working for the space separated strings, the minor changed
required in the scanf function, i.e., instead of writing scanf("%s",s), we must
write: scanf("%[^\n]s",s) which instructs the compiler to store the string s while
the new line (\n) is encountered.
Notice that we do not need to
use address of (&) operator in
scanf to store a string since
string s is an array of
characters and the name of the
array, i.e., s indicates the base
address of the string
(character array) therefore we
need not use & with it.
Some important points
• Points to remember while entering the strings by using scanf:
The compiler doesn't perform bounds checking on the character
array. Hence, there can be a case where the length of the string can
exceed the dimension of the character array which may always
overwrite some important data.
Instead of using scanf, we may use gets() which is an inbuilt
function defined in a header file string.h. The gets() is capable of
receiving only one string at a time.
gets() and puts() functions
• The gets() function enables the user to enter some characters
followed by the enter key. All the characters entered by the user get
stored in a character array. The null character is added to the array
to make it a string. The gets() allows the user to enter the space-
separated strings. It returns the string entered by the user.
• The puts() function is very much similar to printf() function. The
puts() function is used to print the string on the console which is
previously read by using gets() or scanf() function. The puts()
function returns an integer value representing the number of
characters being printed on the console. Since, it prints an
additional newline character with the string, which moves the
cursor to the new line on the console, the integer value returned by
puts() will always be equal to the number of characters present in
the string plus 1.
gets() and puts() functions: (Example)
C String Functions
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Structure (A User Defined Data Types)
• In C programming, a struct (or structure)
is a collection of variables (can be of
different types) under a single name,
providing a convenient means of keeping
related information together.
• The keyword struct is used to declare a
structure.
• A structure declaration forms a template
that can be used to create structure objects
(that is, instances of a structure). Example
• Structure declaration does not occupy any
memory.
• The variables that make up the structure
are called members. (Structure members
are also commonly referred to as elements
or fields.)
Structure (A User Defined Data Types)
• Notice that the declaration is terminated
by a semicolon. This is because a
structure declaration is
a statement.
• The structure tag Person identifies this
particular data structure and is its type
specifier.
• When you declare a structure and no
variable is created, only the form of the
data gets defined. So, no memory is Variable Creation
allocated to structure declaration.
• When a structure variable is declared,
the compiler automatically allocates
Sufficient memory to accommodate all
of its members.
Create struct variables
• When a struct type is declared, no
storage or memory is allocated. To Variable Creation-1
allocate memory of a given structure
type and work with it, we need to create
variables.
Variable Creation-2
Memory allocation for a structure variable
Access members of a structure
• There are two types of operators used for accessing
members of a structure.
• . Membership operator
• --> Structure pointer operator (will be discussed in the next
unit)
• Suppose, you want to access the salary of person2.
Here's how you can do it.
[Link]
Structure Example
Structure Example
Structure Assignments
• The information contained in one structure can be assigned to
another structure of the same type using a single assignment
statement.
You do not need to
assign the value of
each member
separately.
(Although, you can
do this.)
Array of a structure
• Arrays of Structures: To declare an array of structures, you must
first define a structure and then declare an array variable of that
type. For example, to declare a 100-element array of structures of
type Person defined earlier, write struct Person p[100];
• This creates 100 sets of variables that are organized as defined in
the structure Person. To access a specific structure, index the array
name. For example, to print the salary of structure 3, write
printf("%d", p[2].salary);
Passing a structure to a function
• Passing Structure Members to Functions
• Passing Entire structure
typedef
• typedef can be used to give a type a new name. Following is an
example to define a term BYTE for one-byte numbers:
typedef unsigned char BYTE;
• After this type definition, the identifier BYTE can be used
as an abbreviation for the type unsigned char, for
example.
BYTE b1, b2;
• You can use typedef to give a name to your user defined
data types as well. (see example in next slide)
Typedef (Example)
UNION
• Union can be defined as a user-defined data type which is a collection of
different variables of different data types in the same memory location.
• The union can also be defined as many members, but only one member
can contain a value at a particular point in time.
• The declaration of union and different operation performed on union
elements are very much similar to structures.
Differences between Structure and Union
Enum in C
• The enum in C is also known as the enumerated type.
• It is a user-defined data type that consists of integer values, and it provides
meaningful names to these values.
• The use of enum in C makes the program easy to understand and maintain.
• The enum is defined by using the enum keyword.
• The following is the way to define the enum in C:
enum flag{integer_const1, integer_const2,.....integter_constN};
• The default value of integer_const1 is 0, integer_const2 is 1, and so on. We can also
change the default value of the integer constants at the time of the declaration.
• For example:
enum fruits{mango, apple, strawberry, papaya};
The default value of mango is 0, apple is 1, strawberry is 2, and papaya is 3.
• We can also change these default values. Even, the set of enumeration constant may
contain a duplicate value.
enum fruits{mango=5, apple=2, strawberry=6, papaya=2};
Enum in C (Example)
• In the above code, we create an enum type named as weekdays,
and it contains the name of all the seven days. We have assigned 1
value to the Sunday, and all other names will be given a value as
the previous value plus one.
Enum in C (Example)
Why Enum?
• The enum is used when we want our variable to have only a set of
values.
For example, we create a direction variable. As we know that four
directions exist (North, South, East, West), so this direction variable
will have four possible values. But the variable can hold only one
value at a time. If we try to provide some different value to this
variable, then it will throw the compilation error.
• The enum is also used in a switch case statement in which we pass
the enum variable in a switch parenthesis. It ensures that the value
of the case block should be defined in an enum.
Searching and Sorting Algorithms
• Searching is the process of finding some particular element in the
list.
• We will discuss following searching algoritms:
• Linear search
• Binary search
• Sorting means to put numbers into right places, according to their
type.
• We will discuss following sorting algoritms:
• Bubble sort
• Insertion sort
• Selection sort
Linear Search
• Linear search is the simplest search algorithm and often called sequential search.
• In this type of searching, we simply traverse the list completely and match each
element of the list with the item whose location is to be found. If the match found
then location of the item is returned otherwise the algorithm return NULL.
• Linear search is mostly used to search an unordered list in which the items are not
sorted. The algorithm of linear search is given as follows.
• Worst case complexity of linear serach is O(n).
Linear Search
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Binary Search
• Binary search is the search technique which works efficiently on the
sorted lists. Hence, in order to search an element into some list by
using binary search technique, we must ensure that the list is sorted.
• Binary search follows divide and conquer approach in which, the
list is divided into two halves and the item is compared with the
middle element of the list.
• If the match is found then, the location of middle element is
returned otherwise, we search into either of the halves depending
upon the result produced through the match.
• Worst case complexity of linear serach is O(log n).
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Binary Search (Algorithm)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Binary Search (Recursive Source Code)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Binary Search (Non-Recursive Source Code)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Bubble Sort
• Bubble sort is a sorting algorithm that compares two adjacent elements
and swaps them if they are not in the intended order.
• Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
Starting from the first index, compare the first and the second elements.
If the first element is greater than the second element, they are swapped.
Now, compare the second and the third elements. Swap them if they are
not in order.
The above process goes on until the last element.
2. Remaining Iteration
The same process goes on for the remaining iterations.
After each iteration, the largest element among the unsorted elements is
placed at the end.
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Bubble Sort
• In each iteration, the comparison takes place up to the last unsorted
element.
• The array is sorted when all the unsorted elements are placed at
their correct positions.
• Worst case complexity of Bubble sort is O(n2).
• ALGORITHM
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Bubble Sort (Source Code)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Bubble Sort (Flowchart)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Insertion Sort
• Insertion sort is a sorting algorithm that places an unsorted
element at its suitable place in each iteration.
• Insertion sort works similarly as we sort cards in our hand
in a card game.
• We assume that the first card is already sorted then, we
select an unsorted card. If the unsorted card is greater than
the card in hand, it is placed on the right otherwise, to the
left. In the same way, other unsorted cards are taken and
put in their right place.
• A similar approach is used by insertion sort.
• Worst case complexity of insertion sort is O(n 2).
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Working of Insertion Sort
1. The first element in the array is assumed to be sorted.
Take the second element and store it separately in key.
Compare key with the first element. If the first element
is greater than key, then key is placed in front of the first
element.
2. Now, the first two elements are sorted.
3. Take the third element and compare it with the
elements on the left of it. Placed it just behind the
element smaller than it. If there is no element smaller
than it, then place it at the beginning of the array.
4. Similarly, place every unsorted element at its correct
position.
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Insertion Sort Algorithm
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Insertion Sort (Source Code)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Insertion Sort (Flowchart)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Selection Sort
• Selection sort is a sorting algorithm that selects the smallest element from
an unsorted list in each iteration and places that element at the beginning
of the unsorted list.
• Worst case complexity of selection sort is O(n2).
• Working of Selection Sort
1. Set the first element as minimum.
2. Compare minimum with the second element. If the second element is
smaller than minimum, assign the second element
as [Link] minimum with the third element. Again, if the
third element is smaller, then assign minimum to the third element
otherwise do nothing. The process goes on until the last element.
3. After each iteration, minimum is placed in the front of the unsorted list.
4. For each iteration, indexing starts from the first unsorted element. Step
1 to 3 are repeated until all the elements are placed at their correct
positions.
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Selection Sort Algorithm
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)
Selection Sort (Source Code)
PROGRAMMING FOR PROBLEM SOLVING (KCS-201T)
(Mr Deepak Vishwakarma, Assistant Professor, IT Department, KIET
Ghaziabad)