Scribd
Upload
11 views19 pages

CPS Module III

The document provides an overview of arrays and strings, focusing on the definition, types, and operations of arrays in programming. It details single-dimensional and multi-dimensional arrays, their declaration, initialization methods, and algorithms for searching and sorting such as binary search, linear search, bubble sort, and selection sort. Additionally, it compares different search and sort algorithms, highlighting their characteristics and efficiency.

Uploaded by

Thara DRTTIT
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
11 views19 pages

CPS Module III

The document provides an overview of arrays and strings, focusing on the definition, types, and operations of arrays in programming. It details single-dimensional and multi-dimensional arrays, their declaration, initialization methods, and algorithms for searching and sorting such as binary search, linear search, bubble sort, and selection sort. Additionally, it compares different search and sort algorithms, highlighting their characteristics and efficiency.

Uploaded by

Thara DRTTIT
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
MODULE Il Arrays and Strings ARRAY Array is a collection of elements of same data type. ‘The elements are stored sequentially one afier the other in memory. Array is a derived data type. ‘Any element can be accessed by using name of the array and position of element in the array, Each value in an array is reference by a single name, which is the name of the array, and a subscript or index, which indicates the position of the value in the array. The subscript is always a positive integer number, which is enclosed in a pair of square brackets, Example: int age[5]; v vovyy ~W Arrays are classified into 2 types: 1. Single dimensional array (ID) 2. Multi-dimensional array (2D) SINGLE DIMENSIONAL ARRAY (1D) > A single dimensional array is a linear list consisting of related elements of same type. > In memory, all the elements are stored in continuous memory-location one after the other. Declaration of one Dimensional Arrays: A one dimensional array can be declared using the following syntax: data_type array_namefarray_size]; > Where data_type can be int, float or char. > array_name is name of the array which has taken by following the rules of identifier. > ize indicates number of elements in the array which is always a positive Example: int age [5]; ‘The above code can be pictorially represented as shown below: > Here, the size of array “age” is 5 times the size of int because there are 5 elements. > Total amount of memory = size * [sizeof(data_type)] > Using this formula, for int age[5], The total amount of memory =20 bytes. (54). age[0] age{1] age[2] age[3] age[4] Array Elements Initialization of One-Dimensional Array: > The values can be stored in array using following methods: Initializing all specified memory locations (compile time initialization). 2. Initializing individual elements (compile time initialization). 3. Partial array initialization, 4, Initialization during program execution. (Run time initialization). 1. Initializing all specified memory locations: > The syntax to initialize all the elements of a one-dimensional array at a same time is as follows: data_type array_namefarray_size] = (v1 , v2, v3}; > where data_type can be int, float or cl > name is name of the array which has taken by following the rules of identifier. > array_size indicates number of elements in the array which is always a positive number > v1, v2, v3 are values of same data type. > The elements values in the right hand side of the preceding syntax must be enclosed in curly braces and must be separated by comma. > These values are assigned to the array elements in the same order as the order of these values. Example: int age[5]=(2,4,34,3,4}; age{0} age[1] age[2} age[3] age[4) 2 3 34 3 \4 ‘Array elements 2. Initializing individual elements: The syntax for initializing an individual element of a one-dimensional array is as follows: array_name[index] = value; > Where array_name represents the name of the array. > index represents the position of the array element in the array. > value represents the value being assigned to the array element. Example: int age[5]; age[0] //value 2 stored in array “age” at position 0 age[1]=: //value 4 stored in array “age”at position 1 age[2] //value 34 stored in array “age” at position 2 age[3] //value 3 stored in array “ age”at position 3 age[4]=4; //value 4 stored in array “age” at position 4 age(0] age{1] age[2] age[3} age[4) 2 3 34 3 4 ‘Array elements 3. Partial array initialization: Itis allowed in C language, if the number of values to be initialized is less than size of array, then the remaining locations will be initialized to zero automatically by compiler Example: int age[5]={2,3}; age(0]_age{3] age[2]-age[3] age[4} 2 [3 f 0 | 0 0 ~ Armay elements 4, Initialization during program execution: In this type the initialization is done during program execution. Example: int age[5]; for (i=0;i<5;itt) age[i]=it1; Reading and writing one dimensional array ‘The following shows the reading and writing to the one dimensional array: Example: int age[5]; Reading: for (i=0;i<5; itt) scanf ("$d”, 6age[i]); Writing: for(. js i<5; i++) printf ("8d”, age[i]); Program to find the sum and average of N numbers using one- dimensional array. #include void main() { int num[100], sum=0, avg; int n, i; printf ("enter N value: “); scanf("sd", &n); printf ("enter elements one by one: ” for (i picn;itt) t seanf("sd", énum[i]); sum+snum[i]; 0 avg=sum/n; printf ("The numbers are”); for (i=0;i void main() t int num[10]; int n, key, i, low, high, mid, success: printf£("\n Enter number elements\n scanf ("td", én) ; print£("\n Enter elements one by one in increasing order \n for (i=0;icn; i++) scanf("%d", gnum[i]); printf("\n Enter the element to be searched"); scanf ("td", key); low=0; //binary search begins high=(n-1); while (low<=high) f mid= (lowthigh) /2; if (key==num[mid]) t success=1; break; 2 else if (key>num[mid]) low=mid#1; else high=mid-1; }//end of binary search Af (success==1) print£("\n Successful search.d found at 8d position", key, (mid+1)); else print£("\n Unsuccessful search. td is not found", key); , Linear search > Linear search is a very simple search algorithm. > Inthis type of search, a sequential search is made over all iten > Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection. > Here is simple approach is to do Linear Search: 0 through these positions, until element found and then stop index ‘Stop of: ee Fle rf are) re] ers) aes are] ere] erf7} ae] Element to search : 5 program to illustrate the use of linear search #include void main() t int num[10]; int n, key, i, low, high, mid, succes: print£("\n Enter number elements\n") scanf("$d", én) ; printf("\n Enter elements one by one in increasing order \n"); for (i=0;icn; i++) scanf ("¢d", énum[i]) ; print£("\n Enter the element to be searched"); scant ("td", 6key) ; for (i=0; i Binary Search requires the input data to be sorted; Linear Search doesn’t. > Binary Search requires an ordering comparison; Linear Search only requires equality comparisons, > Binary Search requires random access to the data; Linear Search only requires sequential access Bubble sort > Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. > Bubble Sort compares the entire element one by one and sort them based on their values. > If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on. > Ifwe have total n elements, then we need to repeat this process for n-1 times. > Itis known as bubble sort, because with every complete iteration the largest element, in the given array, bubbles up towards the last place or the highest index, just like a ‘water bubble rises up to the water surface. > Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required Let's consider an array with values {5, 1, 6, 2, 4, 3 Below, we have a pictorial representation of how bubble sort will sort the given array. bs sointerennge sotneercange ‘Tse st insertion iterator he ay ‘oo sored sotierange Finally after N iterations array will behaying (2, 2, 3, 4, 5, 6) program to sort the given numbers using bubble sort #include void main() t aint num[25]; int ni, j, temp; printé("\n Enter number of elements\n"); scant ("$d", 6n); print£("\n Enter elements one by one\n"); for (i=0;i numbers will be ordered in descending order {//swap numbers temp=num[j]; num [j]=num[j+1] ; num [F+1]=temp; 2 , , print£("\n Sorted elements are"); } for (1 print£("\n8d", num[iJ) ; picnzitt) Selection sort > Selection sort is conceptually the simplest sorting algorithm, > This algorithm will first find the smallest element in the array and swap it with the element in the first position, then it will find the second smallest element and swap it with the element in the second position, and it will keep on doing this until the entire array is sorted. > It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the right place. Let's consider an array with values (3, 6, 1, 8, 4, 5) Below, we have a pictorial representation of how selection sort will sort the given array. pababobal=)| (=bsLatsbe) | babe sia) 2 iolsbels eh oe 7EE isle) | Zeb: pel) | 2 bolapshe woofialis]a) | (2 [ra po)5]10) t 7 t 7 wisIL=) TREES > In the first pass, the smallest element will be 1, so it will be placed at the first position. Then leaving the first element, next smallest element will be searched, from the remaining elements. We will get 3 as the smallest, so it will be then placed at the second position. Then leaving 1 and 3(because they are at the correct position), we will search for the next smallest element from the rest of the elements and put it at third position and keep doing this until array is sorted. v v Program to sort the given numbers using Selection sort #include void main() { int num[25]; int n, i,j, temp; print£("\n Enter number of elements\n"); seanf ("$d", én); print£("\n Enter elements one by one\n"); for (i=0;i numbers will be ordered in descending order {//swap numbers temp=num[i]; num [4 ]=num[3]; num[j]=temp; 2 } , printf("\n Sorted elements are"); for (i=0;i In the bubble sort, each element and its adjacent element is compared and swapped if required. > On the other hand, selection sort works by selecting the element and swapping that particular element with the last element. > The selected element could be largest or smallest depending on the order ie., ascending or descending. > Bubble sort is a stable algorithm; in contrast, selection sort is unstable. % Selection sort algorithm is fast and efficient as compared to bubble sort. MULTI DIMENSIONAL ARRAYS. Arrays with two or more dimensions are called multi-dimensional arrays. Example: aint matrix[2] [3]; The above code can be pictorially represented as shown below: [cota [coz | cos row 2 |af0J(0} afo}[2} | afo}t2} vow 2 [ecastos | acaacaa | =ca3t23 ‘Multidimensional array > Atwo dimensional array is used when elements are arranged in a tabular fashion, > Here, to identify a particular element, we have to specify 2 indices: > First index identifies the row number of the element and > Second index identifies the column number of the element. Declaration of Two Dimensional Array: ‘The syntax is shown below: data_type array_name[sizel|[size2]; Where data_type represents the data type of the array to be declared, array_name represents the name of the array, size] represents the number or rows, size2 represents the number of columns Example: int matrix(2] [3]; ‘The above code can be pictorially represented as shown below: cota | coz | cols Initialization of Two Dimensional Arrays: Similar to one-dimensional array, the elements of a two-dimensional array can be initialized either one at a time or all at once. The syntax is: data_type array_name|sizeL|[size2] = fvaluel, value2, .....-. value n}; Example: ant matrix[2][3]= {1, 23, 11, 44, 5, 67}; Initialization of the array elements in the preceding line of code is equivalent to initializing each array element separately as follows: matrix[0] [0] a; matrix [0][1] = 23; matrix [0] [2] 1; matrix [1] [0] 44; matrix [1] [1] = 5; matrix [1] [2] 67; The above code can be pictorially represented as shown below: [= [ee Se rwr| a | 23 | 12 row2 | 44 | 5 67 Partial array initialization: If the number of values to be initialized is less than the size of the array, then the remaining locations will be initialized to 0 automatically Example: int matrix(2][3]= (1, 23, 44, 5 }; cott | cot2 | cols rowa| 1. [za | row2| 44 | 5 0 Reading and Writing Two Dimensional Array In general, to read 6 values, we can write: for (i=0;i<2;itt) for (j=0; J<3; j++) seanf("$d", smatrix[i] [j]); Similarly to display 6 elements stored in the matrix, we can write: for (i=0;i<2;it+) for (j=0; j<3; 5+4) printf ("8d ", matrix[i][]); Limitations of Arrays: > Although arrays provide an easy way to store multiple values of the same type together, they have certain limitations. The size of an array that you specify at the time of creation cannot be altered later. In other words, you cannot add more elements t0-an array than specified in its size It is very difficult to insert an element between two existing elements. If you want to insert a new element between two existing elements, you first need to make space for the new element by moving all the existing elements up by one index. > Shortage of Memory, if we don’t know the size of memory in advance. > Wastage of Memory, if array of large size is defined. vw v Advantages of Array: 1. Tris used to represent multiple data items of same type by using only single name. 2. It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc. 3. 2D arrays are used to represent matrices. Program to multiply two matrixes #include void main() t int a[10] [10], [10] [10], c[10] [10]; int m,n,p,q,4, j,k; print£("\n Enter the order of matrix A"); scant ("$dtd", &m, én) ; print£("\nEnter the order of matrix B") scant ("$d8d", &p, &q) ; t printf("\n Multipliction is not possible\n"); return; , print£("\n Enter the element of matrix A one by one’ for (. |; i There is no separate data type for strings in'C., > They are treated as arrays of type “char”. > So, a variable which is used to store an array of characters is called a string variable. Declaration of String Strings are declared in C in similar manner as arrays. Only difference is that, strings are of “char” type. a character array or a string is declared as follows: char variable_namefarray_length]; Example: char s[5]; //string variable name can hold maximum of 5 characters including NULL character The above code can be pictorially represented as shown below: {0} sft} s{2) s3}_ sta) \\o Ini ization of String When you initialize a string variable by assigning character constants individually, use single quotes *” Example: char e(5] = {'r', ‘a', "m’, ‘a' J; When we initialize a string variable by assigning all the characters collectively, we use double quotes “”. Example: char s[9] = {"rama"}; The above code can be pictorially represented as shown below: sf] sf11 sf2) 513) a) \o Reading & Printing Strings 1. Using Formatted input output function: (scanf and printf): The strings can be read from the keyboard and can be displayed onto the monitor using following 2 formatted functions: > Formatted input function: scanft ) > Formatted output function: printf) > The scanf( ) function reads strings from the keyboard and stores them in variables by using %s format specifier. > scanf( ) function read strings which do not have any white spaces, that is, a white space or a blank space in the string will terminate the reading of a string. To read a string with white space gets( ) function is used. > scant: (seanformat) > %s is the format string/ contiol stfing for string. > Gs removes all white spaces present before the string is removed. > Copied string is terminated by “\0”. > The printf( ) function along with the %s format specifier prints a string stored in character array to the console. > We can use the printf( ) function to display the string data with the help of two ways. Either we can pass the string data directly within the printf( ) function or we can store the string data in a character array. Example: printf(“Test string”); Or char str{ ] = {“Test string”}; printf(%s”, str); 2. Using unformatted INPUT/OUTPUT FUNCTIONS: gets ( ), puts () The strings can be read from the keyboard and can be displayed onto the monitor using following 2 unformatted functions > Unformatted input function: gets( ) > Unformatted output function: puts( ) > The gets( ) function reads a string from keyboard. This function stops reading the string only when we press the Enter key from the keyboard. > The gets( ) function is similar to the scanf ) function. > The difference between the gets( ) and scanf{ ) functions is that the gets( ) function can read the whole sentence, which is a combination of multiple words; while the scanf( ) function can read the characters until a space or a newline character is encountered. > The puts( ) function, on the other hand, prints a string or a value stored in a variable to the console in the next fine. Program to read and display string. #include void main() t char name[10]; printf ("enter your name: \n”); gets (name) ; print£("welcome: ”); puts (name) ; output: enter your name: canara welcome: canara String operations 1 tring length: To find the length of string use a counter to count until char str[100]; int i, len=0; gets (str); for (i=0; str[i] !="\0';i+#) lent+; Variable len has total number of characters of str. 2. String copy: char stz[100], copy[100]; ant 4; gets (str); for(i=0;str[i]!='\0' copy [i]=stz [i]; Variable copy has copy of str. i++) 3. String Reverse: char str[100], rev[100]; int i,j, len=0; gets (str); for (i=0; str[i]!='\0';it+) lent+; for(i=0, j=len-1;i Strings are often needed to be manipulated by programmer according to the need of a problem. Al string manipulation can be done manually by the programmer but, this makes programming complex and large. To solve this, the C supports a large number of string handling functions. ‘There are numerous functions defined in header file. S.N. Function & Purpose 1 2 strepy(st, s2); Copies string $2 into string $1. streat(st, $2}; Coneatenates string s2 onto the end of string s1. strien(st); Retums the length of string s1. stremp(st, $2); Retums 0 1 and s2 are the same: less than 0 if s1s2_ strchr{st, ch); Retums a pointer to the frst occurrence of character ch in string st. strstr(st, $2); Retums a pointer to the first occurrence of string s2 in string s1. Additional String Manipulation/Handling Functions: Function Purpose ‘Example Result strupr() | To convert all alphabets ina Sirupre-Deihi") “DELE string to upper case letters. sishwr() | To convert all alphabets in a sulci) string to lower case letters. sirew) To reverse a sting Wie SACHIN) simemp() | To compare the frst | m=stmemp(DELHT” characters of to strings. es ‘irempi() | To compare two strings with | m= strempiDELHT’, | m=O case insensitive(neglecting apa upper/lower case) Delhi"); stmeai() | Tojoin specific number of | char sI[10] ST will be letters to another string, | char s2[10]= atte stmeat(s1.s2.3): Question Bank What is an array? Explain the declaration and initialization of single dimensional array with example. 2. Write a C program to concatenate two strings without using built in function streat(). 3. List string manipulation library functions and explain any two of them with example. 4, Write a C program to find greatest number from two dimensional arrays. 5. Define an array. Write a syntax for declaring two dimensional array and initialize the same with suitable example 6. Explain bubble sort and Write a C program to sort the elements of a given array using bubble sort. 7. Explain selection sort and Write a C program to sort the elements of a given array using selection sort. 8. Explain binary search and Write a C program to search for a key element using binary search. 9, Explain linear search and Write a C program to search for a key element using linear search. 10. Discuss the difference between Bubble sort and selection sort. 11. Discuss the difference between Binary search and linear search. 12. Write a C program to concatenate two strings without using built-in function streat( ) 13, Define the array. How one and two dit nal arrays are declared and initialized? Explain, 14. Explain string input/ Output fundtions with example 15. Explain how strings are declared and initialized with syntax and example 16. Write a C program to find the additional of two matrices. 17. Write aC program to multiply two matric 18, Write a C program to implement stringlenth, concatenate, compare, copy, reverse operations without using Library function. 19, What is string? Write a C program that read a sentence and prints the frequency of each of the vowels and total count of consonants Reference: 1. E Balaguruswamy, Programming in ANSI C, 7th Edition, Tata McGraw-Hill For more Program Examples refer my websit Education, hitps://[Link]/view/dksbin/subjects/e-programming-for-problem- solving

You might also like