codelab

Doubly-linked list is a more sophisticated form of linked list data structure. Each node contains two fields, called links that are references to the previous and to the next node in the sequence of nodes. The two node links allow traversal of the list in either direction. The previous link of the first node and the next link of the last node points to NULL. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified. Example: A doubly linked list whose nodes contain three fields of integer value, the link to the next node, and the link to the previous node.

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node contains one or more data fields and a reference to the next node. The last node points to a null reference to indicate the end of the list.  The entry point into a linked list is the head of the list. Head is not a separate node, but a reference to the first Node in the list. If the list is empty, then the head has the value null. Linked list allows for efficient insertion, deletion, and traversal of elements in the sequence. Example: A singly linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Quick sort is an efficient sorting algorithm. It is even two or three times faster than mergesort and heapsort in some particular cases. The sorting method compares n items in O(nlogn) time in average and best cases, while it is O(n^2) in worst case. Quick sort comes under divide and conquer algorithm which divides the large set of array in small by picking up a pivot element as a reference element, and do sorting. Algorithm: (1) Make a list of items that need to be sorted, let’s apply in an array. (2)  Choose a suitable element as pivot element from the array list, because complexity largely depends on choosing the pivot element. (3) Rearrange the array list so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position. (4) Apply recursively the third step to the sub array of the element with smaller values and s...

Merge sort is based on divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is sorted. The two lists of size 1 are then merged. Best case : When the array is already sorted O(nlogn). Worst case : When the array is sorted in reverse order O(nlogn). Average case : O(nlogn). Space Complexity: Extra space is required, because space complexity is O(n) for arrays and O(logn) for linked lists. 

A program can show incorrect output when the input is not validated to see whether it is correct or not. The best way of avoiding such situation is that treat all input as a sequence of characters, and then perform the necessary data conversion. We can use getchar() to read all input as a string, and afterward convert the string to the correct data type. #include<stdio.h> #include<ctype.h> #include<stdlib.h> #define MAXBUFFERSIZE 80 void cleartoendofline(void);          /* ANSI function prototype */ void cleartoendofline(void) { char ch; ch = getchar(); while(ch != '\n') ch = getchar(); }

Insertion sort is a simple algorithm that sorts an array one item at a time. When people manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort. The algorithm is efficient for small data sets. How insertion sort works:  The second element of an array is compared with the elements that appear before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array are sorted. The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the pos...

Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn't swap the element.  Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort. If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to get required result. But, for better performance, in second step, last and second last elements are not compared as the element is automatically placed at last after first step.  In the third step, last and second last, second last and third last elements are not compared and so on. Graphical representation of bubble sort: ...

Stack is an area of memory that holds all local variables and parameters used by any function. It also remembers the order in which functions are called so that function returns occur correctly. Stack is a LIFO data structure. Stack operations are PUSH (insert operation), POP (Delete operation), and Display (stack). Each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns, these locals and parameters are “popped”. #include <stdio.h> #define MAXSIZE 25 struct stack { int stk[MAXSIZE]; int top; }; typedef struct stack STACK; STACK s;

In Fibonacci series, each number is the sum of the two preceding numbers. For example: 0, 1, 1, 2, 3, 5, 8, ….., ∞ (infinity). The following programs return the nth number entered by user residing in the Fibonacci series. Method 1 (Using recursion): Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential, i.e. this implementation does a lot of repeated work. Extra Space: O(n) if we consider the function call stack size, otherwise O(1). #include<stdio.h> int fib(int n) { if ( n <= 1 ) return n; return fib(n-1) + fib(n-2); } int main () { int n ; printf(" Enter Number to Compute nth Fibonacci Series: "); scanf("%d",&n); printf("\n\n %dth term of Fibonacci Series is %d\n",n, fib(n)); return 0; }

The Towers of Hanoi is a mathematical game or puzzle. The objective is to move the all of the discs one at a time from an arbitrary peg to another. Putting a larger disc over a smaller one must be avoided at all times and the transfer must be made in the least possible moves, which is 2^n - 1, where n is the number of disks. For example, the minimum number of moves required to move three discs are 2^3 - 1 = 7. #include <stdio.h> void towers(int, char, char, char); int main() { int num; printf("Enter the number of disks: "); scanf("%d", &num);

The following program asks user an arithmetic operator (+,-,*,/) and two operands and perform the corresponding calculation on the operands. # include <stdio.h> int main() { char o; float num1,num2; printf("Enter an operator: either + or - or * or /\n\n=> "); scanf("%c",&o); printf("\nEnter two numbers:\n"); scanf("%f%f",&num1,&num2);

A struct is a complex data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory.   #include <stdio.h> #include <string.h> struct Books  { char title[50]; char author[50]; char subject[100]; int book_id;   }; int main( )  { struct Books Book1; struct Books Book2;

Method 1: The following program generates a multiplication table for a given integer to a given range. #include <stdio.h> int main()  { int n, range, i; printf("Enter the value of n: "); scanf("%d",&n); printf("\nEnter the range: "); scanf("%d",&range); for(i=1;i<=range;++i)  { printf("%2d X %2d = %3d\n", n, i, n*i); } return 0; }