B97 : C, Pointers and Data Structures

                                                Nested Structure with Pointers
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    char subname[20];
    int marks;
}SUBDETAIL;

typedef struct
{
    char studname[30];
    int class;
    int rollno;
    SUBDETAIL *psubdetail;
}STUDENT;


int main()
{
    int i, noofstudent,j,noofsub;
    STUDENT *pstudent =  NULL;
    printf("\n ================*** STUDENT RECORDS *** ================\n");    
    printf("\n\tEnter no of students: ");
    scanf("%d",&noofstudent);
    pstudent = (STUDENT *)malloc(noofstudent * sizeof(STUDENT));//mem allocation for STUDENT structure pointer
    if(!pstudent)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    for(i=0;i<noofstudent;i++)
    {
        printf("\n\tEnter Student(%02d) Name: ",i+1);
        scanf(" %s",((pstudent+i)->studname));
        printf("\n\tPlease enter class int: ");
        scanf(" %d",&((pstudent+i)->class));
    
        printf("\n\tEnter No of Sub:");
        scanf("%d",&noofsub);
        (pstudent+i)->psubdetail = (SUBDETAIL *)malloc(noofsub *sizeof(SUBDETAIL));//memory allocation for pointer inside structure
        if(!(pstudent+i)->psubdetail)
        {
            perror("malloc");
            exit(EXIT_FAILURE);
        }
        for(j=0;j<noofsub;j++)    
        {
            printf("\n\t\tEnter Subject(%02d) Name: ",j+1);
            scanf("%s",pstudent[i].psubdetail[j].subname);            
            printf("\n\t\tEnter Marks:");
            scanf("%d",&pstudent[i].psubdetail[j].marks); // we can access like this
           //scanf("%d",&(pstudent+i)->psubdetail[j].marks); //we can also use this
    //        scanf("%d",&(pstudent+i)->(psubdetail+j)->marks); //but not like that
            
        }
    }
    printf("\t\t******* ** * RESULT * **  *****\n");
    for(i=0;i<noofstudent;i++)
    {
        printf("\n\tStudent-> [%s]:",(pstudent+i)->studname);                    
        for(j=0;j<noofsub;j++)    
        {        
            printf("\tRESULT :-> (%s) :(%02d)",pstudent[i].psubdetail[j].subname,pstudent[i].psubdetail[j].marks);    
        }
    }    
    printf("\n");
    free(pstudent);
}

                                 Solving getchar issue using terminals

Issue with getChar can also be resolved by controlling terminals. By default our shell works in canonical mode(icanon), however we can use non-canonical mode (-icanon) and limit the user to give only one character(no enter required). The moment user presses any key it is immediately sent to the input stream.

We can control our terminals accordingly by setting non canonical modes where such features are required and resetting the terminal once our requirement is fulfilled by using stty sane.

Demonstration::
Consider a code where you need to take one single character as input -->

#include<stdio.h>
int main()
{
         char choice;
         int k=5;
         while(k)
         {
               choice=getchar();
               printf("you entered %c as your choice\n",choice);
               k--;
         }
}
Now write a script to control terminal as follows -->

#! /bin/bash
1.stty  -icanon min 1 time 0 #Entering non canonical mode and allowing only 1 input as minimum without time delay.

2../file.c #Basically your executable code where you are taking choice

3.stty sane #To change your terminal setting to default (i.e canonical mode)

Now whenever you will execute the script your terminal will work in non-canonical mode until code execution is finished and the settings are reverted back once you are done.

                               Checking Memory Leaks Using Valgrind

Understanding void pointers (void*)

A void pointer is a pointer that has no associated data type with
it. A void pointer can hold address of any type and can be typecasted to
any type.

• malloc() and calloc() return void * type and this
  allows these functions to be used to allocate memory of any data type.

  Some Interesting Facts

• void pointers cannot be dereferenced, we will get the following compiler error: 'void*' is not a pointer-to-object type
  

• The C Standard doesn’t allow pointer arithmetic with void pointers. However, in GNU C it is allowed by considering the size of void is 1.
  

                                                              merge sort work

RCS file: decleration.h,v
Working file: decleration.h
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 15:57:43;  author: root;  state: Exp;
Initial revision
=============================================================================

RCS file: getele.c,v
Working file: getele.c
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 15:57:48;  author: root;  state: Exp;
Initial revision
=============================================================================

RCS file: header.h,v
Working file: header.h
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 15:57:46;  author: root;  state: Exp;
Initial revision
=============================================================================

RCS file: merge.c,v
Working file: merge.c
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 16:31:20;  author: root;  state: Exp;
Initial revision
=============================================================================

RCS file: mergeon.c,v
Working file: mergeon.c
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 15:57:50;  author: root;  state: Exp;
Initial revision
=============================================================================

RCS file: mergesort.c,v
Working file: mergesort.c
head: 1.1
branch:
locks: strict
    root: 1.1
access list:
symbolic names:
keyword substitution: kv
total revisions: 1;    selected revisions: 1
description:
----------------------------
revision 1.1    locked by: root;
date: 2017/07/03 16:30:41;  author: root;  state: Exp;
Initial revision
=============================================================================

Difference between array and pointer declaration of a string in C:

        char *arr = "Hello world";              //      being treated as constant string
        printf("%s\n", arr);
        *(arr + 3) = 'X';                       //      segmentation fault
        printf("%s\n", arr);

        However,
       
        char arr[] = "Hello world";             //      being treated as mutable string
        printf("%s\n", arr);
        *(arr + 3) = 'X';                               //      this is ok,  no segmentation fault
        printf("%s\n", arr);                          //       will print "HelXo world"

Reason :

• char arr[] is a normal array (including '\0' character atlast), so all sort of array/ pointer operations are supported, hence no issue, as each character is stored as an individual element in the array.
• but char *arr = "Hello world" is a string literal (constant), its value cannot be modified after initialization, as this stored in the read-only section of code memory.
• So altering a string literal is undefined behavior, thus this caused segmentation, it may have other effects on other systems.
  

Writing array in 2 different ways :

If we replace arr[0] with 0[arr], the output would be same. Because compiler converts the array operation in pointers before accessing the array elements.

e.g. arr[0] would be *(arr + 0) and therefore 0[arr] would be *(0 + arr) and you know that both *(arr + 0) and *(0 + arr) are same.

@mvr250679

'\n' is required in order to flush the buffer, hence '\n' is a must, however the program will itself flush, implicitly, the buffer once the main function ends.
Moreover, statements like scanf(), getchar() shall also do the same before taking the input.

For better understanding, please post the code as well.

My algorithm for quick sort :

quicksort(int *ptr, int beg, int end) // func. begins
{
    Loop (iterate from beg -> end)
    {

1. Keep parsing the elements till we find an element larger than pivot.
2. When that is found, store the index for boundary value, set some flag in order to prevent from entering this if() again.
3. Now check for next element that is smaller than pivot.
4. When found swap this element with the value at the last staored boundary location, saved earlier.
5. Increment the boundary to point to the first larger element.
   

    }

// Out of loop

• Now we need to check for a condition, if no element was found to be larger than pivot then, set "last = end", else "last = fence - 1"
• Now swap for the final time value at pivot and value at "last".
• This way we get one array, in which the pivot element is at the correct location, we just need to sort the remain array.
• The array is send recursively twice to itself, with changed boundaries.

        quicksort(ptr, beg, last - 1);
        quicksort(ptr, last + 1, end);

}              // func ends

• Recursion ends when formal parameters recieved by quicksort are such that "beg >= end"
• In this case quick_sort() returns the pointer value, as received.
  

Operator precedence and associativity facts :

• Associativity is only used when there are two or more operators of same precedence.
• All operators with same precedence have same associativity
• Precedence and associativity of postfix ++ and prefix ++ are different
• Comma has the least precedence among all operators and should be used carefully

Some facts about Macros in C

• When we use include directive,  the contents of included header file (after preprocessing) are copied to the current file.
• When we use define for a constant, the
  preprocessor produces a C program where the defined constant is searched
  and matching tokens are replaced with the given expression.
• The macros can take function like arguments, the arguments are not checked for data type.
• The macro arguments are not evaluated before macro expansion.
• The tokens passed to macros can be concatenated using operator ## called Token-Pasting operator.
• A token passed to macro can be converted to a sting literal by using # before it.

                                                 C Compilation Process

Step 1: Preprocessor
Preprocessor will include header files in a source code
replace all the micro name by its values
preprocessor will search '#' (preprocessor directive) in a source code from there it will decide which file is to be included 
Preprocessor will convert high level language (HLL) to pure HLL

Step 2: Compiler
Compiler will convert pure HLL to assembly language
in complier symbol table  generation, code optimisation, syntax error checking and target code generation is done
 
Step 3: Assembler
Convert assembly code into machine language
generates object or .o file   

Step 4: Loader/linker
linker will covert machine code to absolute code
generates .elf (in Linux) or .exe (in windows).

function pointers
Syntax:- void (*foo)(int);
foo is a pointer to a funtion taking one argument an integer and that returns void
example:
void my_func(int n)
{
  printf("%d",n);
}
int main()
{
 void (*foo) (int n);
foo = my_func /// or foo = &my_func
foo(10); /// or (*foo)(10)
return 0;
}

Static and dynamic linking of libraries :

• Static Linking and Static Libraries
• It is the result of the linker making copy of all used library functions to the executable file.
• Static Linking creates larger binary files, and need more space
  on disk and main memory.
• Examples of static libraries (libraries which
  are statically linked) are, .a files in Linux and .lib files in Windows.

• Dynamic linking and Dynamic Libraries
• Dynamic Linking doesn’t require the code to be copied, it is done by just placing name of the library in the binary file.
• The actual linking happens when the program is run, when both the binary file and the library are in memory.
• Examples of Dynamic libraries (libraries which are linked at run-time)
  are, .so in Linux and .dll in Windows.

"const" keyword qualifier :

• This is used to make a value to be stored in the read only area
• Changing the value of this can result in errors
• const int *ptr --> value pointed to by ptr cannot be changed
• int *const ptr --> address pointed to by ptr cannot be changed
• Up qualification : "int *" can be up qualified "const int *"
• Down qualification : "const int *" cannot be down qualified "int *"

Arrays are treated as pointers internally !!!

• Arrays are treated as pointers internally because it is efficient this way
• Copying and storing an entire new array becomes tedious
• While receiving an array as a parameter in functions, we should not use sizeof() operator as the accepted value is just an address
• It would always return a value equivalent to size of an address depending upon machine architecture
• Hence in case of passing arrays we must always pass its length as explicit argument to the function
  

Merge sort Algorithm

1) Dividing Array

merge_sort(int a[])
{
n <- length(a);
if(n<2) return;
mid = n/2;
left <- of size mid;
right <- of size n-mid;
for i = 0 to mid
          left[i] = a[i];
for i = 0 to n-mid
         right[i] = a[mid+i];
merge_sort(left);
merge_sort(right);
merging(a,left,right)
}

2) Merging
 
merging(a,left,right)
{
while(j<length(left) && k<length(right))
{
if(left[j]<right[k])
{
    a[i] = left[j];
     j++;
}
else
{
   a[i] = right[k];
   k++;
}
i++;
}
while(j<length(left))
{
a[i] = left[j];
     j++;i++;
}
while(k<length(right))
{
a[i] = right[k];
     k++;i++;
}
}