Knowledge in UPSC- CSE

Introduction to Data Structures

Data structure is a representation of logical relationship existing between individual elements of data.In other words, a data structure defines a way of organizing all data items that considers not only theelements stored but also their relationship to each other. The term data structure is used to describethe way data is stored.To develop a program of an algorithm we should select an appropriate data structure for thatalgorithm. Therefore, data structure is represented as: Algorithm + Data structure = ProgramA data structure is said to be linear if its elements form a sequence or a linear list. The linear datastructures like an array, stacks, queues and linked lists organize data in linear order. A data structureis said to be non linear if its elements form a hierarchical classification where, data items appear atvarious levels.Trees and Graphs are widely used non-linear data structures. Tree and graph structures representhierarchical relationship between individual data elements. Graphs are nothing but trees with certainrestrictions removed.Data structures are divided into two types:• Primitive data structures.• Non-primitive data structures.Primitive Data Structures are the basic data structures that directly operate upon the machineinstructions. They have different representations on different computers. Integers, floating pointnumbers, character constants, string constants and pointers come under this category.Non-primitive data structures are more complicated data structures and are derived from primitivedata structures. They emphasize on grouping same or different data items with relationship betweeneach data item. Arrays, lists and files come under this category. Figure 1.1 shows the classification ofdata structures.Data Structures Operations:1. Traversing2. Searching3. Inserting4. Deleting5. Sorting6. Merging1. Traversing- It is used to access each data item exactly once so that it can be processed.2. Searching- It is used to find out the location of the data item if it exists in the given collectionof data items.3. Inserting- It is used to add a new data item in the given collection of data items.4. Deleting- It is used to delete an existing data item from the given collection of data items.5. Sorting- It is used to arrange the data items in some order i.e. in ascending or descendingorder in case of numerical data and in dictionary order in case of alphanumeric data.6. Merging- It is used to combine the data items of two sorted files into single file in the sortedform.Review of ArraysThe simplest type of data structure is a linear array. This is also called one dimensional array.Definition:Array is a data structure that can store a fixed-size sequential collection of elements of the same type.An array is used to store a collection of data, but it is often more useful to think of an array as acollection of variables of the same type. An array holds several values of the same kind. Accessingthe elements is very fast. It may not be possible to add more values than defined at the start, withoutcopying all values into a new array. An array is stored so that the position of each element can becomputed from its index.For example, an array of 10 integer variables, with indices 0 through 9, may be stored as 10 words atmemory addresses 2000, 2004, 2008, 2036, so that the element with index i has the address 2000 + 4× i.Address Calculation in single (one) Dimension Array:Array of an element of an array say “A[ I ]” is calculated using the following formula:Address of A [ I ] = B + W * ( I – LB )Where,B = Base addressW = Storage Size of one element stored in the array (in byte)I = Subscript of element whose address is to be foundLB = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)Example:Given the base address of an array B[1300.....1900] as 1020 and size of each element is 2 bytes in thememory. Find the address of B[1700].Solution:The given values are: B = 1020, LB = 1300, W = 2, I = 1700Address of A [ I ] = B + W * ( I – LB )= 1020 + 2 * (1700 – 1300)= 1020 + 2 * 400= 1020 + 800= 1820 [Ans]Address Calculation in Double (Two) Dimensional Array:While storing the elements of a 2-D array in memory, these are allocated contiguous memorylocations. Therefore, a 2-D array must be linearized so as to enable their storage. There are twoalternatives to achieve linearization: Row-Major and Column-Major.C allows for arrays of two or more dimensions. A two-dimensional (2D) array is an array of arrays. Athree-dimensional (3D) array is an array of arrays of arrays.In C programming an array can have two, three, or even ten or more dimensions. The maximumdimensions a C program can have depends on which compiler is being used.More dimensions in an array means more data be held, but also means greater difficulty in managingand understanding arrays.How to Declare a Multidimensional Array in CA multidimensional array is declared using the following syntax:type array_name[d1][d2][d3][d4].........[dn];Where each d is a dimension, and dn is the size of final dimension.Examples:1. int table[5][5][20];2. float arr[5][6][5][6][5];In Example 1: int designates the array type integer. table is the name of our 3D array. Our array can hold 500 integer-type elements. This number is reached by multiplying thevalue of each dimension. In this case: 5x5x20=500.In Example 2: Array arr is a five-dimensional array. It can hold 4500 floating-point elements (5x6x5x6x5=4500).When it comes to holding multiple values, we would need to declare several variables. But a singlearray can hold thousands of values.Explanation of a 3D ArrayA 3D array is essentially an array of arrays of arrays: it's an array or collection of 2D arrays, and a 2Darray is an array of 1D array.Example to show reading and printing a 3D array#include<stdio.h>#include<conio.h>void main(){int i, j, k;int arr[3][3][3]={{{11, 12, 13},{14, 15, 16},{17, 18, 19}},{{21, 22, 23},{24, 25, 26},{27, 28, 29}},{{31, 32, 33},{34, 35, 36},{37, 38, 39}},};clrscr();printf(":::3D Array Elements:::\n\n");for(i=0;i<3;i++){for(j=0;j<3;j++){for(k=0;k<3;k++){printf("%d\t",arr[i][j][k]);}printf("\n");}printf("\n");}}Note: refer notes for dynamic 1D & 2D arrays and also for pointers.StructuresStructure is a user defined data type that can hold data items of different data types.Structure Declarationstruct tag { member 1; member 2;-----------------------member m; }In this declaration, struct is a required keyword ,tag is a name that identifies structures of this type.The individual members can be ordinary variables, pointers, arrays or other structures. The membernames within a particular structure must be distinct from one another, though a member name can besame as the name of a variable defined outside of the structure and individual members cannot beinitialized within a structure-type declaration. For example:struct student{ char name [80];int roll_no;float marks;}s1,s2;we can now declare the structure variable s1 and s2 as follows: struct student s1, s2; wheres1 and s2 are structure type variables whose composition is identified by the tag student.Nested StructureIt is possible to combine the declaration of the structure composition with that of the structurevariable .It is then called a nested structure.struct dob{ int month;int day;int year;};struct student{ char name [80];int roll_no;float marks;struct dob d1;}st;The member of the nested structure can be accessed by using the dot operator twice.(ie)st.d1.yearArray of structuresIt is also possible to define an array of structures that is an array in which each element is a structure.The procedure is shown in the following example:struct student{char name [80];int roll_no ;float marks ;} st [100];In this declaration st is a 100- element array of structures.It means each element of st represents an individual student record.Accessing members of a structure using the dot operatorThe members of a structure are usually processed individually, as separate entities. Therefore, wemust be able to access the individual structure members. A structure member can be accessed bywritingstructurevariable. member name.This period (.) is an operator, it is a member of the highest precedence group, and its associativity isleft-to-right.e.g. if we want to print the detail of a member of a structure then we can write asprintf(“%s”,; or printf(“%d”, st.roll_no) and so on. More complex expressions involving therepeated use of the period operator may also be written. For example, if a structure member is itself astructure, then a member of the embedded structure can be accessed by writing.variable.member.submember.Thus in the case of student and dob structure, to access the month of date of birth of a student, wewould writest.d1.month // accessing member of nested structureThe use of the period operator can be extended to arrays of structure, by writingarray [expression]. memberStructures members can be processed in the same manner as ordinary variables of the same data type.Single-valued structure members can appear in expressions. They can be passed to functions and theycan be returned from functions, as though they were ordinary single-valued variables.e.g. suppose that s1 and s2 are structure variables having the same composition as described earlier. Itis possible to copy the values of s1 to s2 simply by writings2=s1; //copying one structure to another which are of the same typeUSER-DEFINED DATA TYPES (typedef)The typedef feature allows users to define new data types that are equivalent to existing data types.Once a user-defined data type has been established, then new variables, arrays, structure and so on,can be declared in terms of this new data type. In general terms, a new data type is defined astypedef type new- type;Where type refers to an existing data type and new-type refers to the new user-defined data type.e.g. typedef int age;In this declaration, age is user- defined data type equivalent to type int. Hence, the variabledeclarationage male, female;is equivalent to writingint age, male, female;The typedef feature is particularly convenient when defining structures, since it eliminates the need torepeatedly write struct tag whenever a structure is referenced. As a result, the structure can bereferenced more concisely.In general terms, a user-defined structure type can be written astypedef struct { member 1; member 2: - - - - - - member m; }new-type;The typedef feature can be used repeatedly, to define one data type in terms of other user-defined datatypes.STRUCTURES AND POINTERSThe beginning address of a structure can be accessed in the same manner as any other address,through the use of the address (&) operator.Thus, if variable represents a structure type variable, then & variable represents the starting address ofthat variable. A pointer to a structure can be defined as follows:struct student *ptr;ptr represents the name of the pointer variable of type student. We can then assign the beginningaddress of a structure variable to this pointer by writingptr= &variable; //pointer initialisationLet us take the following example:typedef struct {char name [ 40];int roll_no;float marks;}student;student s1,*ps;In this example, s1 is a structure variable of type student, and ps is a pointer variable whose object isa structure variable of type student. Thus, the beginning address of s1 can be assigned to ps = &s1;An individual structure member can be accessed in terms of its corresponding pointer variable byusing the -> operator (arrow operator)ptr →memberWhere ptr refers to a structure- type pointer variable and the operator → is comparable to the period(.) operator. The associativity of this operator is also left-to-right.The operator → can be combined with the period operator (.) to access a submember within astructure. Hence, a submember can be accessed by writingptr → member.submemberPASSING STRUCTURES TO A FUNCTIONThere are several different ways to pass structure–type information to or from a function. Structuremember can be transferred individually , or entire structure can be transferred. The individualstructures members can be passed to a function as arguments in the function call; and a singlestructure member can be returned via the return statement. To do so, each structure member is treatedthe same way as an ordinary, single- valued variable.A complete structure can be transferred to a function by passing a structure type pointer as anargument. It should be understood that a structure passed in this manner will be passed by referencerather than by value. So, if any of the structure members are altered within the function, thealterations will be recognized outside the function. Let us consider the following example:# include <stdio.h>typedef struct{char name[10];int roll_no;float marks ;} record student={“Param”, 2,99.9};void adj(record*ptr){ptr → name=”Tanishq”;ptr → roll_no=3;ptr → marks=98.0;return;}main ( ){printf(“%s%d%f\n”,, student.roll_no,student.marks);adj(&student);printf(“%s%d%f\n”,, student.roll_no,student.marks);}Let us consider an example of transferring a complete structure, rather than a structure-type pointer,to the function.# include <stdio.h>typedef struct{char name[10];int roll_no;float marks;}record student={“Param,” 2,99.9};void adj(record stud) /*function definition */{”Tanishq”;stud.roll_no=3;stud.marks=98.0;return;}main(){printf(“%s%d%f\n”,,student.roll_no,student.marks);adj(student);printf(“%s%d%f\n”,,student.roll_no,student.marks);}Union is a derived datatype , like structure, i.e. collection of elements of different data types whichare grouped together. Each element in a union is called member. Union and structure in C are same in concepts, except allocating memory for their members. Structure allocates storage space for all its members separately. Whereas, Union allocates one common storage space for all its members, or memory space isshared between its members. Only one member of union can be accessed at a time. All member values cannot be accessedat the same time in union. But, structure can access all member values at the same time. Thisis because, Union allocates one common storage space for all its members, where as Structureallocates storage space for all its members separately. Many union variables can be created in a program and memory will be allocated for eachunion variable separately. The table below will help you how to form a C union, declare a union, initializing andaccessing the members of the union.Type Using normal variable Using pointer variableSyntaxunion tag_name{data type var_name1;data type var_name2;data type var_name3;};union tag_name{data type var_name1;data type var_name2;data type var_name3;};Exampleunion student{int mark;char name[10];float average;};union student{int mark;char name[10];float average;};Declaringunion variable union student report; union student *report, rep;Initializingunion variableunion student report = {100,“Mani”, 99.5};union student rep = {100, “Mani”,99.5};report = &rep;Accessingunion membersreport.markreport.namereport.averagereport -> markreport -> namereport -> averageExample program for C union:#include <stdio.h>#include <string.h>union student{char name[20];char subject[20];float percentage;};int main(){union student record1;union student record2;// assigning values to record1 union variablestrcpy(, "Raju");strcpy(record1.subject, "Maths");record1.percentage = 86.50;printf("Union record1 values example\n");printf(" Name : %s \n",;printf(" Subject : %s \n", record1.subject);printf(" Percentage : %f \n\n", record1.percentage);// assigning values to record2 union variableprintf("Union record2 values example\n");strcpy(, "Mani");printf(" Name : %s \n",;strcpy(record2.subject, "Physics");printf(" Subject : %s \n", record2.subject);record2.percentage = 99.50;printf(" Percentage : %f \n", record2.percentage);return 0;}Output:Union record1 values exampleName :Subject :Percentage : 86.500000;Union record2 values exampleName : ManiSubject : PhysicsPercentage : 99.500000Explanation for above C union program:There are 2 union variables declared in this program to understand the difference in accessingvalues of union members.Record1 union variable: “Raju” is assigned to union member “” . The memory location name is“” and the value stored in this location is “Raju”. Then, “Maths” is assigned to union member “record1.subject”. Now, memory location nameis changed to “record1.subject” with the value “Maths” (Union can hold only one member at atime). Then, “86.50” is assigned to union member “record1.percentage”. Now, memory locationname is changed to “record1.percentage” with value “86.50”. Like this, name and value of union member is replaced every time on the common storagespace. So, we can always access only one union member for which value is assigned at last. We can‟taccess other member values. So, only “record1.percentage” value is displayed in output. “” and“record1.percentage” are empty.Record2 union variable: If we want to access all member values using union, we have to access the member beforeassigning values to other members as shown in record2 union variable in this program. Each union members are accessed in record2 example immediately after assigning values tothem. If we don‟t access them before assigning values to other member, member name and valuewill be over written by other member as all members are using same memory. We can‟t access all members in union at same time but structure can do that.Example program – Another way of declaring C union:In this program, union variable “record” is declared while declaring union itself as shown in thebelow program.#include <stdio.h>#include <string.h>union student{char name[20];char subject[20];float percentage;}record;int main(){strcpy(, "Raju");strcpy(record.subject, "Maths");record.percentage = 86.50;printf(" Name : %s \n",;printf(" Subject : %s \n", record.subject);printf(" Percentage : %f \n", record.percentage);return 0;}Output:Name :Subject :Percentage : 86.500000We can access only one member of union at a time. We can‟t access all member values at thesame time in union. But, structure can access all member values at the same time. This isbecause, Union allocates one common storage space for all its members. Where as Structure allocatesstorage space for all its members separately.Difference between structure and union in C Structure C Union1Structure allocates storagespace for all its membersseparately.Union allocates one common storage space for all its members.Union finds that which of its member needs high storage spaceover other members and allocates that much space2Structure occupies largermemory space.Union occupies lower memory space over structure.3We can access all members ofstructure at a time. We can access only one member of union at a time.4Structure example:struct student{int mark;double average;};Union example:union student{int mark;double average;};5For above structure, memoryallocation will be like mark – 2Bdouble average – 8BTotal memory allocation = 2+8= 10 BytesFor above union, only 8 bytes of memory will be allocatedsince double data type will occupy maximum space of memoryover other data types.Total memory allocation = 8 BytesPOINTERS & DYNAMIC MEMORY ALLOCATION FUNCTIONS:When a variable is defined the compiler (linker/loader actually) allocates a real memory address forthe variable.– int x; will allocate 4 bytes in the main memory, which will be used to store aninteger value.When a value is assigned to a variable, the value is actually placed to the memory that was allocated.– x=3; will store integer 3 in the 4 bytes of memory.The process of allocating memory during program execution is called dynamic memoryallocation.C language offers 4 dynamic memory allocation functions. They are,1. malloc() : malloc (number * sizeof(int));2. calloc() : calloc (number, sizeof(int));3. realloc() : realloc (pointer_name, number * sizeof(int));4. free() : free (pointer_name);1. MALLOC(): is used to allocate space in memory during the execution of the program.does not initialize the memory allocated during execution. It carries garbage value.returns null pointer if it couldn‟t able to allocate requested amount of memory.2. CALLOC(): calloc () function is also like malloc () function. But calloc () initializes the allocated memoryto zero. But, malloc() doesn‟t.3. REALLOC(): Realloc () function modifies the allocated memory size by malloc () and calloc () functionsto new size.If enough space doesn‟t exist in memory of current block to extend, new block is allocated forthe full size of reallocation, then copies the existing data to new block and then frees the oldblock.4. FREE():free () function frees the allocated memory by malloc (), calloc (), realloc () functions andreturns the memory to the system.DIFFERENCE BETWEEN STATIC MEMORY ALLOCATION AND DYNAMIC MEMORYALLOCATION IN C:Static memory allocation Dynamic memory allocationIn static memory allocation, memoryis allocated while writing the Cprogram. Actually, user requestedmemory will be allocated at compiletime.In dynamic memoryallocation, memory isallocated while executing theprogram. That means at runtime.Memory size can‟t be modified whileexecution.Example: arrayMemory size can be modifiedwhile execution.Example: Linked listDIFFERENCE BETWEEN MALLOC() AND CALLOC() FUNCTIONS IN C:malloc() calloc()It allocates only single block ofrequested memoryIt allocates multiple blocks ofrequested memoryint *ptr;ptr = malloc( 20 * sizeof(int));For the above, 20*4 bytes of memoryonly allocated in one block.Total = 80 bytesint *ptr;Ptr = calloc( 20, 20 *sizeof(int) );For the above, 20blocks of memory will becreated and each contains20*4 bytes of memory.Total = 1600 bytesmalloc () doesn‟t initializes theallocated memory. It contains garbagevaluescalloc () initializes theallocated memory to zerotype cast must be done since thisfunction returns void pointer int*ptr;ptr = (int*)malloc(sizeof(int)*20);Same as malloc () functionint *ptr;ptr = (int*)calloc( 20,20 * sizeof(int) );Array Operations:All operations remain same as mentioned above for data structures operations.Note:  Refer 1st lab program for the operations.SORTING:Sorting takes an unordered collection and makes it an ordered one.In bubble sort method the list is divided into two sub-lists sorted and unsorted. The smallest element is bubbledfrom unsorted sub-list. After moving the smallest element the imaginary wall moves one element ahead. Thebubble sort was originally written to bubble up the highest element in the list. But there is no differencewhether highest / lowest element is bubbled. This method is easy to understand but time consuming. In thistype, two successive elements are compared and swapping is done. Thus, step-by-step entire array elements arechecked. Given a list of „n‟ elements the bubble sort requires up to n-1 passes to sort the data.Algorithm for Bubble sort: Bubble_Sort( A[], N)Step1 : Repeat for p = 1 to N-1BeginStep2 : Repeat for j = 1 to N-pBeginStep3 : if (A[j] < A[j-1])Swap ( A[j], A[j-1]);End forEnd forExitExample:Ex:- A list of unsorted elements are: 10 47 12 54 19 23 (Bubble up for highest value shown here)/* bubble sort implementation */#include<stdio.h>#include<conio.h>void main(){int i,n,temp,j,arr[25];printf("Enter the number of elements in the Array: ");scanf("%d",&n);printf("\nEnter the elements:\n\n");for(i=0 ; i<n ; i++)scanf("%d",&arr[i]);for(i=0 ; i<n ; i++){for(j=0 ; j<n-i-1 ; j++){if(arr[j]>arr[j+1]) //Swapping Condition is Checked{temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}printf("\nThe Sorted Array is:\n\n");for(i=0 ; i<n ; i++)printf(" %4d",arr[i]);}SEARCHING TECHNIQUE1. LINEAR SEARCHLinear search or sequential search is a method for finding a target value within a list. It sequentiallychecks each element of the list for the target value until a match is found or until all the elements havebeen searched.Linear search runs in at worst linear time and makes at most n comparisons, where n is the length ofthe list. If each element is equally likely to be searched, then linear search has an average case of n/2comparisons, but the average case can be affected if the search probabilities for each element vary.Linear search is rarely practical because other search algorithms and schemes, such as the binarysearch algorithm and hash tables, allow significantly faster searching for all but short linear_search(int *list, int size, int key, int* rec ){// Basic Linear searchint found = 0;int i;for ( i = 0; i < size; i++ ){if ( key == list[i] )found = 1;return found;}Return found;}2. BINARY SEARCHWe always get a sorted list before doing the binary search. Now suppose we have anascending order record. At the time of search it takes the middle record/element, if the searchingelement is greater than middle element then the element mush be located in the second part else it isin the first half. In this way this search algorithm divides the records in the two parts in each iterationand thus called binary search.In binary search, we first compare the key with the item in the middle position of the array. If there'sa match, we can return immediately. If the key is less than the middle key, then the item must lie inthe lower half of the array; if it's greater then the item must lie in the upper half of the array. So werepeat the procedure on the lower or upper half of the array depending on the BinarySearch(int *array, int N, int key){int low = 0, high = N-1, mid;while(low <= high){mid = (low + high)/2;if(array[mid] < key)low = mid + 1;else if(array[mid] == key)return mid;else if(array[mid] > key)high = mid-1;}return -1;}SPARSE MATRICESA sparse matrix is a matrix in which most of the elements are zero. By contrast, if most of theelements are nonzero, then the matrix is considered dense. When storing and manipulating sparsematrices on a computer, it is beneficial and often necessary to use specialized algorithms and datastructures that take advantage of the sparse structure of the matrix. Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices asprocessing and memory are wasted on the zeroes. Sparse data is by nature more easily compressedand thus require significantly less storage. Some very large sparse matrices are infeasible tomanipulate using standard dense-matrix algorithms.Storing a sparse matrixA matrix is typically stored as a two-dimensional array. Each entry in the array represents an elementai,j of the matrix and is accessed by the two indices i and j. Conventionally, i is the row index,numbered from top to bottom, and j is the column index, numbered from left to right. For an m × nmatrix, the amount of memory required to store the matrix in this format is proportional to m × nIn the case of a sparse matrix, substantial memory requirement reductions can be realized by storingonly the non-zero entries.Sparse Matrix RepresentationsA sparse matrix can be represented by using TWO representations...1. Triplet Representation2. Linked Representation1. Triplet RepresentationIn this representation, we consider only non-zero values along with their row and column indexvalues. Each non zero value is a triplet of the form <R,C,Value) where R represents the row in whichthe value appears, C represents the column in which the value appears and Value represents the non-zero value itself. In this representation, the 0th row stores total rows, total columns and total non-zerovalues in the matrix.For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values. This matrix canbe represented as shown in the image...In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrixsize is 5 X 6. We represent this matrix as shown in the above image. Here the first row in the rightside table is filled with values 5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6columns & 6 non-zero values. Second row is filled with 0, 4, & 9 which indicates the value in thematrix at 0th row, 4th column is 9. In the same way the remaining non-zero values also follows thesimilar pattern.2. Linked RepresentationIn linked representation, we use linked list data structure to represent a sparse matrix. In this linkedlist, we use two different nodes namely header node and element node. Header node consists ofthree fields and element node consists of five fields as shown in the image...Consider the above same sparse matrix used in the Triplet representation. This sparse matrix can berepresented using linked representation as shown in the below image...In above representation, H0, H1,...,H5 indicates the header nodes which are used to represent indexes.Remaining nodes are used to represent non-zero elements in the matrix, except the very first nodewhich is used to represent abstract information of the sparse matrix (i.e., It is a matrix of 5 X 6 with 6non-zero elements).In this representation, in each row and column, the last node right field points to it's respective headernode.Basic operations on Sparse Matrix Reading a sparse matrix Displaying a sparse matrix Searching for a non zero element in a sparse matrixNote :Refer class notes for implementation of basic operations of sparse matricesPOLYNOMIALSA polynomial object is a homogeneous ordered list of pairs < exponent,coefficient>, where eachcoefficient is unique.Operations include returning the degree, extracting the coefficient for a given exponent, addition,multiplication, evaluation for a given inputPolynomial operations Representation Addition MultiplicationRepresentation of a Polynomial: A polynomial is an expression that contains more than two terms.A term is made up of coefficient and exponent. An example of polynomial isP(x) = 4x3+6x2+7x+9A polynomial thus may be represented using arrays or linked lists. Array representation assumes thatthe exponents of the given expression are arranged from 0 to the highest value (degree), which isrepresented by the subscript of the array beginning with 0. The coefficients of the respectiveexponent are placed at an appropriate index in the array. The array representation for the abovepolynomial expression is given below:A polynomial may also be represented using a linked list. A structure may be defined such that itcontains two parts- one is the coefficient and second is the corresponding exponent. The structuredefinition may be given as shown below:struct polynomial{int coefficient;int exponent;struct polynomial *next;};Thus the above polynomial may be represented using linked list as shown below:Addition of two Polynomials:For adding two polynomials using arrays is straightforward method, since both the arrays maybe added up element wise beginning from 0 to n-1, resulting in addition of two polynomials.Addition of two polynomials using linked list requires comparing the exponents, andwherever the exponents are found to be same, the coefficients are added up. For terms withdifferent exponents, the complete term is simply added to the result thereby making it a part ofaddition result.STRINGS Strings are Character ArraysStrings in C are simply array of characters.– Example: char s [10]; This is a ten (10) element array that can hold a characterstring consisting of  9 characters. This is because C does not know where the end ofan array is at run time. By convention, C uses a NULL character '\0' to terminate allstrings in its library functions– For example: char str [10] = {'u', 'n', 'I', 'x', '\0'};It‟s the string terminator (not the size of the array) that determines the length of thestring. Accessing Individual CharactersThe first element of any array in C is at index 0. The second is at index 1, and so on...char s[10];s[0] = 'h'; s [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]s[1] = 'i‟;s[2] = '!';s[3] = '\0';This notation can be used in all kinds of statements and expressions in C:For example:c = s[1];if (s[0] == '-') ...switch (s[1]) ...H i ! \0 String LiteralsString literals are given as a string quoted by double quotes.– printf("Long long ago.");Initializing char array ...– char s[10]="unix"; /* s[4] is '\0'; */– char s[ ]="unix"; /* s has five elements */– Printing with ptintf()Example:Char str[ ] = "A message to display";printf ("%s\n", str);printf expects to receive a string as an additional parameter when it sees %s in the formatstring– Can be from a character array.– Can be another literal string.– Can be from a character pointer (more on this later).– printf knows how much to print out because of the NULL character at the end of allstrings.– When it finds a \0, it knows to stop. Printing with puts( )The puts function is a much simpler output function than printf for string printing.– Prototype of puts is defined in stdio.hint puts(const char * str). This is more efficient than printf because your programdoesn't need to analyze the format string at run-time.For example:char sentence[] = "The quick brown fox\n";puts(sentence);Prints out: The quick brown fox Inputting Strings with gets( )gets( ) gets a line from the standard input.The prototype is defined in stdio.hchar *gets(char *str)– str is a pointer to the space where gets will store the line to, or a character array.– Returns NULL upon failure. Otherwise, it returns str.char your_line[100];printf("Enter a line:\n");gets(your_line);puts("Your input follows:\n");puts(your_line);You can overflow your string buffer, so be careful! Inputting Strings with scanf ( )To read a string include:– %s scans up to but not including the “next” white space character– %ns scans the next n characters or up to the next white space character, whichevercomes firstExample:scanf ("%s%s%s", s1, s2, s3);scanf ("%2s%2s%2s", s1, s2, s3);– Note: No ampersand(&) when inputting strings into character arrays! (We‟ll explainwhy later ...)Difference between gets– gets( ) read a line– scanf("%s",...) read up to the next spaceExample:#include <stdio.h>int main () {char lname[81], fname[81];int count, id_num;puts ("Enter the last name, firstname, ID number separated");puts ("by spaces, then press Enter \n");count = scanf ("%s%s%d", lname, fname,&id_num);printf ("%d items entered: %s %s %d\n",count,fname,lname,id_num);return 0;} The C String LibraryString functions are provided in an ANSI standard string library.– Access this through the include file:#include <string.h> Includes functions such as: Computing length of string Copying strings Concatenating stringsThis library is guaranteed to be there in any ANSI standard implementation of C. strlen() returns the length of a NULL terminated character string:strlen (char * str) ; Defined in string.hA type defined in string.h that is equivalent to an unsigned intchar *strPoints to a series of characters or is a character array ending with '\0' strcpy() copying a string comes in the form:char *strcpy (char * destination, char * source);A copy of source is made at destination. Source should be NULL terminatedand destination should have enough room (its length should be at least thesize of source). The return value also points at the destination. strcat() comes in the form:char * strcat (char * str1, char * str2);Appends a copy of str2 to the end of str1 & a pointer equal to str1 is returned.Ensure that str1 has sufficient space for the concatenated string!Array index out of range will be the most popular bug in your C programmingcareer.Example:#include <string.h>#include <stdio.h>int main() {char str1[27] = "abc";char str2[100];printf("%d\n",strlen(str1));strcpy(str2,str1);puts(str2);puts("\n");strcat(str2,str1);puts(str2);} strcmp() can be compared for equality or inequalityIf they are equal - they are ASCII identicalIf they are unequal the comparison function will return an int that is interpretedas:< 0 : str1 is less than str20 : str1 is equal to str2> 0 : str1 is greater than str2Four basic comparison functions:int strcmp (char *str1, char *str2) ; Does an ASCII comparison one char at a time until a difference is foundbetween two chars– Return value is as stated before

Current Affairs Compequiz 1- 15 June 2019 by Dr Kumar Punit Goel

ssc gk bank , railway , upsc etc as SSC BANK AND RAILWAYS.UPSC CSAT, Prelims, Mains, CDS,NDA, CAPF,SSC CGL, MPSI, MPPSC,BPSC,RAS/RTS, DMRC, DELHI POLICE, UP POLICE, etc competitive examination preparation to memorize Gk and Current Affairs, Police/Security Forces, SSC - CHSL (10+2 / LDC / Bank etc.) , SSC - GD , SSC - JE ,SSC – CGL, SSC – CPO , UPSC , UPSC- CAPF, UPSC- CDS, UPSC- CSE, UPSC- IES/ISS, UPSC- NDA , UPSC- SCRA, upsc, Other,others, After Graduation, After Higher Education (10th Class) , After Post Graduation, After Secondary Education (12th Class) , No Criteria,ibps,gre,gmat,Bank po ,railways,maths,mathematics, general Studies,reasoning,general knowledge,

CS Unit-2 Probablity B-Tech (Cse) IP University

These are the notes of the subject: Communication System(CS) in B-tech (Computer science) 4th Semester. These are the handwritten notes of topics in unit-4, These are easy to understand and includes all the contents covered in unit 2. They are prepared very carefully and are very clear, and will help you to achieve good marks in the exams.

Trees Notes B-Tech(CSE) IP University

These are the handwritten notes of the topic trees. It is very helpful in the beginning also it is very useful in the latter time as it contains all the logic and formulas of the language. It also offers detailed answers to the questions.

TOC notes B-TECH(2019) CSE IP University

These are the notes of the subject: Theory of Computation (TOC) in B-tech (Computer science) 4th Semester. These are the handwritten notes . These are easy to understand and include all the topics covered . They are prepared very carefully and are very clear, and will help you to achieve good marks in the exams.

Computer Organisation

Computer organization is concerned with the way the hardware components operate and the way they are connected together to form the computer system. The various components are assumed to be in place and the task is to investigate the organizational structure to verify that the computer parts operate as intended.