Learning Tutorial

30.Heap Sort

2011-01-21T02:04:00.001-08:00

Heapsort algorithm is a comparison-based sorting algorithm. The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

Worst case performance	$O (n log n)$
Best case performance	$O (n log n)$ ^[1]
Average case performance	$O (n log n)$
Worst case space complexity	$O (n)$ total, $O (1)$ auxiliary

Heap Sort Program

#include <stdio.h> 
#include <conio.h> 
void main() 
 { 
   int i,v,p,l[100],n,k,t,j; 
   clrscr(); 
   printf("enter the number"); 
   scaf("%d",&n); 
   for(i=1;i<=n;i++) 
     { 
      scanf("%d",&l[i]); 
     } 
   printf("\nentered list are as follows"); 
   for(i=1;i<=n;i++) 
     { 
       printf("\t%d",l[i]); 
     } 
/*creation of heap*/ 
   for(k=2;k<=n;k++) 
     { 
       i=k; 
       t=l[k]; 
       j=i/2; 
         while((i>1)&&(t > l[j])) 
         { 
          l[i]=l[j]; 
          i=j; 
          j=i/2; 
          if(j<1) 
          j=1; 
         } 
       l[i]=t; 
      } 

    printf("\nHEAP"); 

    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
      printf("\n"); 
  //heapsort 
    for(k=n;k>=2;--k) 
   { 
     t=l[1]; 
     l[1]=l[k]; 
     l[k]=t; 
     i=1; 
     v=l[1]; 
     j=2; 
     if(j+1) 
       if(l[j+1]>l[j]) 
         j++; 
     while((j<=(k-1))&&(l[j]>v)) 
      { 
       l[i]=l[j]; 
       i=j; 
       j=2*i; 
       if(j+1) 
          if(l[j+1]>l[j]) 
             j++; 
     else 
        if(j>n) 
          j=n; 
          l[i]=v; 
      } 
     for(p=1;p<=n;p++) 
      { 
       printf("\t%d",l[p]); 
      } 
       printf("\n"); 
     } 
    printf("\nthe sorted list "); 
    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
getch(); 

}

Output:

enter the number
5
8
6
2
4
45

entered list are as follows     8       6       2       4       45
HEAP    45      8       2       4       6
8       6       2       4       45
6       4       2       8       45
2       4       6       8       45
4       2       6       8       45

the sorted list         4       2       6       8       45

30.Heap Sort

2011-01-21T02:00:00.000-08:00

Worst case performance	$O (n log n)$
Best case performance	$O (n log n)$ ^[1]
Average case performance	$O (n log n)$
Worst case space complexity	$O (n)$ total, $O (1)$ auxiliary

Heap Sort Program

#include <stdio.h> 
#include <conio.h> 
void main() 
 { 
   int i,v,p,l[100],n,k,t,j; 
   clrscr(); 
   printf("enter the number"); 
   scaf("%d",&n); 
   for(i=1;i<=n;i++) 
     { 
      scanf("%d",&l[i]); 
     } 
   printf("\nentered list are as follows"); 
   for(i=1;i<=n;i++) 
     { 
       printf("\t%d",l[i]); 
     } 
/*creation of heap*/ 
   for(k=2;k<=n;k++) 
     { 
       i=k; 
       t=l[k]; 
       j=i/2; 
         while((i>1)&&(t > l[j])) 
         { 
          l[i]=l[j]; 
          i=j; 
          j=i/2; 
          if(j<1) 
          j=1; 
         } 
       l[i]=t; 
      } 

    printf("\nHEAP"); 

    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
      printf("\n"); 
  //heapsort 
    for(k=n;k>=2;--k) 
   { 
     t=l[1]; 
     l[1]=l[k]; 
     l[k]=t; 
     i=1; 
     v=l[1]; 
     j=2; 
     if(j+1) 
       if(l[j+1]>l[j]) 
         j++; 
     while((j<=(k-1))&&(l[j]>v)) 
      { 
       l[i]=l[j]; 
       i=j; 
       j=2*i; 
       if(j+1) 
          if(l[j+1]>l[j]) 
             j++; 
     else 
        if(j>n) 
          j=n; 
          l[i]=v; 
      } 
     for(p=1;p<=n;p++) 
      { 
       printf("\t%d",l[p]); 
      } 
       printf("\n"); 
     } 
    printf("\nthe sorted list "); 
    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
getch(); 

}

Output:

enter the number
5
8
6
2
4
45

entered list are as follows 8 6 2 4 45
HEAP 45 8 2 4 6
8 6 2 4 45
6 4 2 8 45
2 4 6 8 45
4 2 6 8 45

the sorted list 4 2 6 8 45

29.Quick Sort

2011-01-21T01:43:00.000-08:00

Quicksort sorts a list based on the divide and conquer strategy. In quicksort algorithm we divide the list into two sub-lists, sort these sub-lists and recursively until the list is sorted; The basic steps of quicksort algorithm are as follows:

Choose a key element in the list which is called a pivot.
Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Worst case performance	O(n²)
Best case performance	O(n log n)
Average case performance	O(n log n)
Worst case space complexity	O(n)

Quick Sort Program

#include<stdio.h>
int main(){
int x[20],size,i;
printf("\nEnter size of the array :");
scanf("%d",&size);
printf("\nEnter %d elements :",size);
for(i=0;i<size;i++)
    scanf("%d",&x[i]);
quicksort(x,0,size-1);
printf("\nSorted elements :");
for(i=0;i<size;i++)
    printf(" %d",x[i]);
return 0;
}

quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;
     if(first<last){
         pivot=first;
         i=first;
         j=last;
         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }
         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);
    }
}

Output of the Program:

Enter the size of the array:5

Enter 5 elements:6 8 5 9 3

Sorted elements:3 5 6 8 9

29.Quick Sort

2011-01-21T01:41:00.000-08:00

Choose a key element in the list which is called a pivot.
Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Quick Sort Program

#include<stdio.h>
int main(){
int x[20],size,i;
printf("\nEnter size of the array :");
scanf("%d",&size);
printf("\nEnter %d elements :",size);
for(i=0;i<size;i++)
    scanf("%d",&x[i]);
quicksort(x,0,size-1);
printf("\nSorted elements :");
for(i=0;i<size;i++)
    printf(" %d",x[i]);
return 0;
}

quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;
     if(first<last){
         pivot=first;
         i=first;
         j=last;
         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }
         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);
    }
}

Output of the Program:

Enter the size of the array:5

Enter 5 elements:6 8 5 9 3

Sorted elements:3 5 6 8 9

28.Selection Sort

2011-01-21T00:57:00.000-08:00

Selection Sort Program
Selection sort is a simplicity sorting algorithm. It works as its name as it is. Here are basic steps of selection sort algorithm:
1. Find the minimum element in the list
2. Swap it with the element in the first position of the list
3. Repeat the steps above for all remainder elements of the list starting at the second position.

#include <stdio.h>
#include <conio.h>

#define MAXSIZE 500
void selection(int elements[], int maxsize);
int elements[MAXSIZE],maxsize;
int main()
{
  int i;
  printf("\nHow many elements you want to sort:" );
  scanf("%d",&maxsize);
  printf("\nEnter the values one by one: ");
  for (i = 0; i < maxsize; i++)
   {
     printf ("\nEnter element %i :",i);
     scanf("%d",&elements[i]);
   }
  printf("\nArray before sorting:\n");
  for (i = 0; i < maxsize; i++)
  printf("[%i], ",elements[i]);
  printf ("\n");
  selection(elements, maxsize);
  printf("\nArray after sorting:\n");
  for (i = 0; i < maxsize; i++)
      printf("[%i], ", elements[i]);
 }

void selection(int elements[], int array_size)
{
  int i, j, k;
  int min, temp;
  for (i = 0; i < maxsize-1; i++)
   {
     min = i;
     for (j = i+1; j < maxsize; j++)
       {
         if (elements[j] < elements[min])
         min = j;
       }
  temp = elements[i];
  elements[i] = elements[min];
  elements[min] = temp;
  }
}

OUTPUT:

How many elements you want to sort:5

Enter the values one by one:
Enter element 0:8
Enter element 1:5
Enter element 2:6
Enter element 3:4
Enter element 4:2

Array before sorting:
[8],[5],[7],[4],[2].

Array after sorting:
[2],[4],[5],[6],[8].

27.Insertion Sort

2011-01-21T00:38:00.000-08:00

Logic : Here, sorting takes place by inserting a particular element at the appropriate position, that’s why the name- insertion sorting. In the First iteration, second element A[1] is compared with the first element A[0]. In the second iteration third element is compared with first and second element. In general, in every iteration an element is compared with all the elements before it. While comparing if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position up and inserts the desired element at the suitable position. This procedure is repeated for all the elements in the list.

If we complement the if condition in this program, it will give out the sorted array in descending order. Sorting can also be done in other methods, like selection sorting and bubble sorting, which follows in the next pages.

Insertion Sort Program

#include<stdio.h>  
#include<conio.h>  
  
   void insertion(int a[],int n)  
   {  
  
    int i,j,x,k;  
  
           for(i=1;i<=n-1;i++)  
    
                {  
                       j=i;  
  
                       x=a[i];  
  
  
                       while(a[j-1]>x && j>0)  
  
                                 {  
  
                                   a[j]=a[j-1];  
                                    j=j-1;  
  
                                 }  
  
                        a[j]=x;  
  
  
                       printf("\n\n The array after pass no.%d: ",i);  
                       for(k=0;k<=n-1;k++)  
                      printf("%4d",a[k]);  
  
  
                 }//end for.  
  
  
   } //end function.  
  
   void main()  
  
   {  
  
     int a[1000],n,i;  
  
     clrscr();  
  
     printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");  
     scanf("%3d",&n);  
  
     for(i=0;i<=n-1;i++)  
  
          {  
  
            printf("\n\nEnter an integer value for element no.%d: ",i+1);  
            scanf("%4d",&a[i]);  
  
          }  
  
  
     insertion(a,n);  
  
  
     printf("\n\n\nFinally sorted array is : ");  
     for(i=0;i<=n-1;i++)  
     printf("%4d",a[i]);  
  
  
   }//end program.  
  
/*

OUTPUT:

Enter an integer value for total no.s of elements to be sorted: 6

Enter an integer value for element no.1: 67

Enter an integer value for element no.2: 34

Enter an integer value for element no.3: -23

Enter an integer value for element no.4: 100

Enter an integer value for element no.5: 0

Enter an integer value for element no.6: -68

The array after pass no.1: 34 67 -23 100 0 -68

The array after pass no.2: -23 34 67 100 0 -68

The array after pass no.3: -23 34 67 100 0 -68

The array after pass no.4: -23 0 34 67 100 -68

The array after pass no.5: -68 -23 0 34 67 100

Finally sorted array is : -68 -23 0 34 67 100

2.C Data Types

2011-01-21T00:33:00.000-08:00

Data types are used to store various types of data that is processed by program. Data type attaches with variable to determine the number of bytes to be allocate to variable and valid operations which can be performed on that variable. C supports various data types such as character, integer and floating-point types.

Character Data Type

C stores character type internally as an integer. Each character has 8 bits so we can have 256 different characters values (0-255).

Character set is used to map between an integer value and a character. The most common character set is ASCII.

Let take a look at example of using a variable which hold character 'A'.

01#include <stdio.h>
02  
03void main()
04{
05    char ch = 'A';
06    printf("%c\n",ch);
07    ch = 65;// using integer representation
08    printf("%c\n",ch);
09    ch = '\x41';   // using hexadecimal representation
10    printf("%c\n",ch);
11    ch = '\101';   // using octal representation
12    printf("%c\n",ch);
13}

Here is the output

A
A
A
A

Integer Data Type

Integer data types are used to store numbers and characters. Here is the table of integer data type in various forms:

Data Type	Memory Allocation	Range
signed `char`	1 byte	−2⁷ to 2⁷−1 (−128 to 127)
Unsigned `char`	1 byte	0 to 2⁸−1 (0 to 255)
`short`	2 bytes	−2¹⁵ to 2¹⁵ −1 (−32768 to 32767)
Unsigned `short`	2 bytes	0 to 2¹⁶ −1 (0 to 65535)
`long int`	4 bytes	2³¹ to 2³¹−1 (2,147,483,648 to 2,147,483,647)
`int`	2 or 4 bytes depending on implementation	Range for 2 or 4 bytes as given above

Floating-point Data Type

The floating-point data types are used to represent floating-point numbers. Floating-point data types come in three sizes: float (single precision), double (double precision), and long double (extended precision). The exact meaning of single, double, and extended precision is based on implementation defined. Choosing the right precision for a problem where the choice matters requires understanding of floating point computation.

Floating-point literal

Floating-point literal is double by default. You can use the suffix f or F to get a floating-point literal 3.14f or 3.14F

Type Conversion

Type conversion occurs when an expression has a mixed data types. At this time, the compiler will try to convert from lower to higher type, because converting from higher to lower may cause loss of precision and value.C has following rules for type conversion.

Integer types are lower than floating-point types.
Signed types are lower than unsigned types.
Short whole-number types are lower than longer types.
The hierarchy of data types is as follows: double, float, long, int, short, char.

So based on those rules, we have general rules for type conversion:

Character and short data are promoted to integer.
Unsigned char and unsigned short are converted to unsigned integer.
If the expression includes unsigned integer and any other data type, the other data type is converted to an unsigned integer and the result will be unsigned integer.
If the expression contains long and any other data type, that data type is converted to long and the result will be long.
Float is promoted to double.
If the expression includes long and unsigned integer data types, the unsigned integer is converted to unsigned long and the result will be unsigned long.
If the mixed expression is of the double data type, the other operand is also converted to double and the result will be double.
If the mixed expression is of the unsigned long data type, then the other operand is also converted to double and the result will be double.

Conversion Type Casting

When we want to convert the value of a variable from one type to another we can use type casting. Type casting does not change the actual value of variable. It can be done using a cast operator (unary operator).

26.Bubble Sort

2011-01-21T00:27:00.000-08:00

Bubble sorting is a simple sorting technique in sorting algorithm. In bubble sorting algorithm, we arrange the elements of the list by forming pairs of adjacent elements. It means we repeatedly step through the list which we want to sort, compare two items at a time and swap them if they are not in the right order. Another way to visualize the bubble sort algorithm is as its name, the smaller element bubble to the top. Here is the source code implements bubble sorting algorithm in C which sorts an unordered list of integer.

Step-by-step example

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

First Pass:

( 5 1 4 2 8 ) ->( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.

( 1 5 4 2 8 ) ->( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Finally, the array is sorted, and the algorithm can terminate.

Worst case performance= O(n2)

Best case performance =O(n)

Average case performance =O(n2)

Worst case space complexity =O(1) auxiliary

Bubble Sort Program:

#include<stdio.h> 
#include<conio.h> 
 
  void bubble(int a[],int n) 
  { 
        int i,j,t; 
         for(i=n-2;i>=0;i--) 
         { 
            for(j=0;j<=i;j++) 
 
                  { 
                    if(a[j]>a[j+1]) 
                                    { 
                                      t=a[j]; 
                                     a[j]=a[j+1]; 
                                     a[j+1]=t; 
                                    } 
                   } 
        
 
           }//end for 1. 
 
  }//end function. 
 
 
  void main() 
  { 
 
      int a[100],n,i; 
 
      clrscr(); 
 
      printf("\n\n Enter integer value for total no.s of elements to be sorted: "); 
      scanf("%d",&n); 
 
      for( i=0;i<=n-1;i++) 
            { 
              printf("\n\n Enter integer value for element no.%d : ",i+1); 
              scanf("%d",&a[i]); 
            } 
 
       bubble(a,n); 
 
       printf("\n\n Finally sorted array is: "); 
       for( i=0;i<=n-1;i++) 
       printf("%3d",a[i]); 
 
  } //end program

OUTPUT:

Enter integer value for total no.s of elements to be sorted: 6

Enter integer value for element no.1 : 89

Enter integer value for element no.2 : -4

Enter integer value for element no.3 : -67

Enter integer value for element no.4 : 5

Enter integer value for element no.5 : 78

Enter integer value for element no.6 : 11

Finally sorted array is: -67 -4 5 11 78 89

24.Queue Data Structure

2011-01-20T23:38:00.000-08:00

Queue is a data structure which works based on the principle first in - first out (FIFO)

Introduce to Queue and Array Implementation of Queue

Queue is a data structure which works based on the principle first in - first out (FIFO)

25.Queue Implementation with Array

2011-01-20T23:34:00.000-08:00

Queue is a data structure which works based on the principle first in - first out (FIFO)


	queue.c (0.7 KB) queue.c
	queue.h (177 B) Header file of queue
	testqueue.c (0.8 KB) testqueue.c

void enqueue(int *q,int *tail, int element);

int dequeue(int *q,int *head);

int full(int tail,const int size);

int empty(int head,int tail);

void init(int *head, int *tail);

/*initialize queue pointer*/

void init(int *head, int *tail)

{

*head = *tail = 0;

}

/* enqueue an element

precondition: the queue is not full

void enqueue(int *q,int *tail, int element)

{

q[(*tail)++] = element;

}

/* dequeue an element

precondition: queue is not empty*/

int dequeue(int *q,int *head)

{

return q[(*head)++];

}

/* report queue is full nor not

return 1 if queue is full, otherwise return 0*/

int full(int tail,const int size)

{

return tail == size ? 1 : 0;

}

/* report queue is empty or not

return 1 if the queue is empty, otherwise return 0*/

int empty(int head, int tail)

{

return head == tail ? 1 : 0;

}

#include <stdio.h>

#include <stdlib.h>

#include "queue.h"

#define size 3

void main(){

int head,tail,element;

int queue[size];

// initialize queue

init(&head,&tail);

// enqueue elements

while(full(tail,size) != 1){

element = rand();

printf("enqueue element

%d\n",element);

enqueue(queue,&tail,element);

printf("head=%d,tail=%d\n",head,tail);

//press enter to enqueue more

getchar();

}

printf("queue is full\n");

// dequeue elements from

while(!empty(head,tail)){

element = dequeue(queue,&head);

printf("dequeue element %d \n",element)

//press enter to pop more

getchar();

}

printf("queue is empty\n");

getchar();}

21.Stack Data Structure

2011-01-20T23:10:00.000-08:00

Stack and Implementing Stack using Array

Stack is a data structure which works based on principle of LIFO (last in first out).

Implementing a Stack using Link Representation

This is a another version of stack data structure implementation; with this version the stack size is dynamic and determined at run-time.

23.Implementing a Stack using Link Representation

2011-01-20T10:13:00.000-08:00

This is a another version of stack data structure implementation using link representation. With this version the stack size is dynamic and determined at run-time.


	linkedstack.c (0.5 KB) linkedstack.c
	linkedstack.h (0.5 KB) Header file of linked stack
	testlinkedstack.c (0.7 KB) testlinkedstack.c

linkedstack.h

int empty(struct node *s);
struct node* push(struct node *s,int data);
struct node* pop(struct node *s,int *data);
void init(struct node* s);

linkedstack.c

#include<stdlib.h>

struct node{
        int data;
        struct node* next;
};

void init(struct node* s){
        s = NULL;
}

struct node* push(struct node* s,int data)
{
        struct node* tmp = (struct node*)malloc(sizeof(struct node));
        if(tmp == NULL){
               // no memory available
               exit(0);
        }
        tmp->data = data;
        tmp->next = s;
        s = tmp;
        return s;
}
struct node* pop(struct node *s,int *element)
{
        struct node* tmp = s;
        *element = s->data;
        s = s->next;
        free(tmp);
        return s;
}

int empty(struct node* s){
        return s == NULL ? 1 : 0;
}

test

linkedstack.c

#include <stdio.h>

#include <stdlib.h>

#include "linkedstack.h"

void main()

{

struct node* head = NULL;

int size,element,counter = 0;

/* stack size is dynamic and

specified at runtime */

printf("Enter stack size:");

scanf("%d",&size);

printf("Push elements to stack\n");

init(head);

while(counter < size)

{

getchar();

element = rand();

printf("push element %d into stack\n",element);

head = push(head,element);

counter++;

}

printf("Pop elements from stack\n");

while(0 == empty(head))

{

head = pop(head,&element);

printf("pop element %d from stack\n",element);

getchar();

}

getchar();

}

22.Stack and Implementing Stack using Array

2011-01-20T10:02:00.000-08:00

Introduce to stack data structure

Stack is a data structure which works based on principle of last in first out (LIFO). In computing world, stack data structure can be applied in many applications such as parsing syntax of expressions, run-time memory management (used in Java virutal machine) and solving search problem.

Stack operations

Push and pop are the operations that are provided for insertion of an element into the stack and the removal of an element from the stack.

Array Implementation of a Stack using C

Here is source code of c which demonstrate stack data structure. You can also download them to your local PC and start practicing.

	stack.c (0.6 KB) stack implementation file: stack.c
	stack.h (149 B) Header file of stack: stack.h
	teststack.c (0.6 KB) Stack test file: teststack.c

Stack.h

void push(int *s,int* top, int element);
int pop(int *s,int *top);
int full(int *top,const int size);
int empty(int *top);
void init(int *top);

Stack.c

/*initialize stack pointer*/

void init(int *top)
{
               *top = 0;
}

/*push an element into stack
precondition: the stack is not full */

void push(int *s,int* top, int element)
{
               s[(*top)++] = element;
}

/*      pop an element from stack
        precondition: stack is not empty */

int pop(int *s,int *top)
{
               return s[--(*top)];
}

/*      report stack is full nor not
        return 1 if stack is full, otherwise return 0 */

int full(int *top,const int size)
{
               return *top == size ? 1 : 0;
}

/*      report a stack is empty or not
        return 1 if the stack is empty, otherwise return 0 */

int empty(int *top)
{
               return *top == 0 ? 1 : 0;
}

teststack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

#define size 3

void main()
{
               int top,element;
               int stack[size];

        // initialize stack
               init(&top);

        // push elements into stack
               while(!full(&top,size)){
                               element = rand();
                               printf("push element %d into stack\n",element);
                               push(stack,&top,element);
                               //press enter to push more
                               getchar();

               }
               printf("stack is full\n");

        // pop elements from stack
               while(!empty(&top)){
                  element = pop(stack,&top);
                  printf("pop element %d from stack\n",element);
           //press enter to pop more
                               getchar();
               }
               printf("stack is empty\n");

               getchar();
}

20.Strings

2011-01-20T09:26:00.001-08:00

Introducing to C structure

In some programming contexts, you need to access multiple data types under a single name for easier data manipulation; for example you want to refer to address with multiple data like house number, street, zip code, country. C supports structure which allows you to wrap one or more variables with different data types. A structure can contain any valid data types like int, char, float even arrays or even other structures. Each variable in structure is called a structure member.

Defining structure

To define a structure, you use struct keyword. Here is the common syntax of structure definition:

struct struct_name{ structure_member };

The name of structure follows the rule of variable name. Here is an example of defining address structure:

struct address{
   unsigned int house_number;
   char street_name[50];
   int zip_code;
   char country[50];
 };

The address structure contains house number as an positive integer, street name as a string, zip code as an integer and country as a string.

Declaring structure

The above example only defines an address structure without creating any structure instance. To create or declare a structure instance, you can do it in two ways:

The first way is to declare a structure followed by structure definition like this :

struct struct_name {
   structure_member;
   ...
 } instance_1,instance_2 instance_n;

In the second way, you can declare the structure instance at a different location in your source code after structure definition. Here is structure declaration syntax :

struct struct_name instance_1,instance_2 instance_n;

Complex structure

If a structure contains arrays or other structures, it is called complex structure. For example address structure is a structure. We can define a complex structure called customer which contains address structure as follows:

struct customer{
   char name[50];
   structure address billing_addr;
   structure address shipping_addr;
 };

Accessing structure member

To access structure members we can use dot operator (.) between structure name and structure member name as follows:

structure_name.structure_member

For example to access street name of structure address we do as follows:

struct address billing_addr; 
billing_addr.country = "US";

If the structure contains another structure, we can use dot operator to access nested structure and use dot operator again to access variables of nested structure.

struct customer jack;
jack.billing_addr.country = "US";

Initializing structure

C programming language treats a structure as a custom data type therefore you can initialize a structure like a variable. Here is an example of initialize product structure:

struct product{
   char name[50];
   double price;
 } book = { "C programming language",40.5};

In above example, we define product structure, then we declare and initialize book structure with its name and price.

Structure and pointer

A structure can contain pointers as structure members and we can create a pointer to a structure as follows:

struct invoice{
  char* code;
  char date[20];
 };
  
 struct address billing_addr;
 struct address *pa = &billing_addr;

Shorthand structure with typedef keyword

To make your source code more concise, you can use typedef keyword to create a synonym for a structure. This is an example of using typedef keyword to define address structure so when you want to create an instance of it you can omit the keyword struct

typedef struct{
    unsigned int house_number;
    char street_name[50];
    int zip_code;
    char country[50];
 } address;
  
 address billing_addr;
 address shipping_addr;

Copy a structure into another structure

One of major advantage of structure is you can copy it with = operator. The syntax as follows

struct_intance1 = struct_intance2

be noted that some old C compilers may not supports structure assignment so you have to assign each member variables one by one.

Structure and sizeof function

sizeof is used to get the size of any data types even with any structures. Let's take a look at simple program:

#include <stdio.h>
 
typedef struct __address{
    int house_number;// 4 bytes
    char street[50]; // 50 bytes
    int zip_code; // 4 bytes
    char country[20];// 20 bytes
 
} address;//78 bytes in total
 
void main()
{
    // it returns 80 bytes
    printf("size of address is %d bytes\n",sizeof(address));
}

You will never get the size of a structure exactly as you think it must be. The sizeof function returns the size of structure larger than it is because the compiler pads struct members so that each one can be accessed faster without delays. So you should be careful when you read the whole structure from file which were written from other programs.

Source code example of using C structure

In this example, we will show you how to use structure to wrap student information and manipulate it by reading information to an array of student structure and print them on to console screen.

#include <stdio.h>
 
typedef struct _student{
    char name[50];
    unsigned int mark;
} student;
 
 
 
void print_list(student list[], int size);
void read_list(student list[], int size);
 
 
 
void main(){
 
    const int size = 3;
    student list[size];
    
    read_list(list,size);
 
    print_list(list,size);
 
 
}

void read_list(student list[], int size)
{
    printf("Please enter the student information:\n");
 
    for(int i = 0; i < size;i++){
        printf("\nname:");
        scanf("%S",&list[i].name);
 
        printf("\nmark:");
        scanf("%U",&list[i].mark);
    }
 
}

void print_list(student list[], int size){
    printf("Students' information:\n");
    
    for(int i = 0; i < size;i++){
        printf("\nname: %s, mark: %u",list[i].name,list[i].mark);
    }
}

Here is program's output

Please enter the student information:
 
name:Jack
 
mark:5
 
name:Anna
 
mark:7
 
name:Harry
 
mark:8
Students' information:
 
name: J, mark: 5
name: A, mark: 7
name: H, mark: 8

19.Structures

2011-01-20T09:25:00.000-08:00

Introducing to C structure

Defining structure

To define a structure, you use struct keyword. Here is the common syntax of structure definition:

struct struct_name{ structure_member };

The name of structure follows the rule of variable name. Here is an example of defining address structure:

struct address{

          unsigned int house_number;

          char street_name[50];

          int zip_code;

          char country[50];

};

The address structure contains house number as an positive integer, street name as a string, zip code as an integer and country as a string.

Declaring structure

The above example only defines an address structure without creating any structure instance. To create or declare a structure instance, you can do it in two ways:

The first way is to declare a structure followed by structure definition like this :

struct struct_name {

          structure_member;

...

        } instance_1,instance_2 instance_n;

In the second way, you can declare the structure instance at a different location in your source code after structure definition. Here is structure declaration syntax :

struct struct_name instance_1,instance_2 instance_n;

Complex structure

If a structure contains arrays or other structures, it is called complex structure. For example address structure is a structure. We can define a complex structure called customer which contains address structure as follows:

struct customer{

          char name[50];

          structure address billing_addr;

          structure address shipping_addr;

};

Accessing structure member

To access structure members we can use dot operator (.) between structure name and structure member name as follows:

structure_name.structure_member

For example to access street name of structure address we do as follows:

struct address billing_addr;

billing_addr.country = "US";

If the structure contains another structure, we can use dot operator to access nested structure and use dot operator again to access variables of nested structure.

struct customer jack;

jack.billing_addr.country = "US";

Initializing structure

C programming language treats a structure as a custom data type therefore you can initialize a structure like a variable. Here is an example of initialize product structure:

struct product{

          char name[50];

          double price;

        } book = { "C programming language",40.5};

In above example, we define product structure, then we declare and initialize book structure with its name and price.

Structure and pointer

A structure can contain pointers as structure members and we can create a pointer to a structure as follows:

struct invoice{

               char* code;

               char date[20];

};

        struct address billing_addr;

        struct address *pa = &billing_addr;

Shorthand structure with typedef keyword

typedef struct{

                 unsigned int house_number;

                 char street_name[50];

                 int zip_code;

                 char country[50];

        } address;

        address billing_addr;

        address shipping_addr;

Copy a structure into another structure

One of major advantage of structure is you can copy it with = operator. The syntax as follows

struct_intance1 = struct_intance2

be noted that some old C compilers may not supports structure assignment so you have to assign each member variables one by one.

Structure and sizeof function

sizeof is used to get the size of any data types even with any structures. Let's take a look at simple program:

#include <stdio.h>

typedef struct __address{

    int house_number;// 4 bytes

    char street[50]; // 50 bytes

    int zip_code; // 4 bytes

    char country[20];// 20 bytes

} address;//78 bytes in total

void main()

    // it returns 80 bytes

    printf("size of address is %d bytes\n",sizeof(address));

Source code example of using C structure

In this example, we will show you how to use structure to wrap student information and manipulate it by reading information to an array of student structure and print them on to console screen.

#include <stdio.h>

typedef struct _student{

    char name[50];

    unsigned int mark;

} student;

void print_list(student list[], int size);

void read_list(student list[], int size);

void main(){

    const int size = 3;

    student list[size];

    read_list(list,size);

    print_list(list,size);

void read_list(student list[], int size)

    printf("Please enter the student information:\n");

    for(int i = 0; i < size;i++){

        printf("\nname:");

        scanf("%S",&list[i].name);

        printf("\nmark:");

        scanf("%U",&list[i].mark);

void print_list(student list[], int size){

    printf("Students' information:\n");

    for(int i = 0; i < size;i++){

        printf("\nname: %s, mark: %u",list[i].name,list[i].mark);

Here is program's output

Please enter the student information:

 

name:Jack

 

mark:5

 

name:Anna

 

mark:7

 

name:Harry

 

mark:8

Students' information:

 

name: J, mark: 5

name: A, mark: 7

name: H, mark: 8

13.Functions

2011-01-20T09:22:00.000-08:00

Introduce to C function

C function is a block of source code which does one or some tasks with specificed purpose.

Passing Arguments to Function

C supports a wide range of mechanisms to allow you to program functions effectively.

C Recursive Function

Recursive function is a function which contains a call to itself. Here you will learn how to implement C recursive function.

15.Passing Arguments to Function

2011-01-20T09:21:00.000-08:00

In order to write correct function you should know how to pass arguments to it. C supports a wide range of mechanisms to allow you to program functions effectively.

Pass by value

With this mechanism, all arguments you pass to function are copied into copy versions and your function work in that copy versions. So parameters does not affects after the function finished.

Pass by pointer

In some programming contexts, you want to change arguments you pass to function. In this case, you can use pass by pointer mechanism. Remember that a pointer is a memory address of a variable. So when you pass a pointer to a function, the function makes a copy of it and changes the content of that memory address, after function finish the parameter is changed with the changes in function body.

Pass an array to function

C allows you pass an array to a function, in this case the array is not copied. The name of array is a pointer which points to the first entry of it. And this pointer is passed to the function when you pass an array to a function.

#include<stdio.h>
 
/* functions declaration */
 
/* demonstrate pass by pointer */
void swap(int *x, int *y);

/* demonstrate pass by value */
void swap(int x, int y); 

/* demonstrate pass an array to the function */
void bubble_sort(int a[], int size);
 
void print_array(int a[],int size);
 
void main()
{
    int x = 10;
    int y = 20;
 
    
    printf("x,y before swapping\n");
    printf("x = %d\n",x);
    printf("y = %d\n",y);
    
    // pass by value
    swap(x,y);
 
    printf("x,y after swapping using pass by value\n");
    printf("x = %d\n",x);
    printf("y = %d\n",y);
 
    // pass by pointer
    swap(&x,&y);
 
    printf("x,y after swapping using pass by pointer\n");
    printf("x = %d\n",x);
    printf("y = %d\n",y);
 
    // declare an array
    const int size = 5;
    int a[size] = {1,3,2,5,4};
 
    printf("array before sorting\n");
    print_array(a,size);
    
    bubble_sort(a,size);
 
    printf("array after sorting\n");
    print_array(a,size);
 
 
}
 
 
/* functions implementation */
 
void swap(int *x, int *y){
    int temp = *x;
        *x = *y;
        *y = temp;
}
 
void swap(int x, int y){
    int temp = x;
        x = y;
        y = temp;
}
 
void bubble_sort(int a[], int size)
{
   int i,j;
   for(i=0;i<(size-1);i++)
      for(j=0;j<(size-(i+1));j++)
             if(a[j] > a[j+1])
                    swap(&a[j],&a[j+1]);
}
 
void print_array(int a[],int size)
{
 
    for(int i = 0;i < size; i++)
    {
        printf("%d\t",a[i]);
        printf("\n");
    }
}

Here is the output

x,y before swapping
x = 10
y = 20
x,y after swapping using pass by value
x = 10
y = 20
x,y after swapping using pass by pointer
x = 20
y = 10
array before sorting
1
3
2
5
4
array after sorting
1
2
3
4
5

18.Arrays

2011-01-20T08:49:00.000-08:00

Array definition

Array by definition is a variable that hold multiple elements which has the same data type.

Declaring Arrays

We can declare an array by specify its data type, name and the number of elements the array holds between square brackets immediately following the array name. Here is the syntax:

1data_type array_name[size];

For example, to declare an integer array which contains 100 elements we can do as follows:

1int a[100];

There are some rules on array declaration. The data type can be any valid C data types including structure and union. The array name has to follow the rule of variable and the size of array has to be a positive constant integer.

We can access array elements via indexes array_name[index]. Indexes of array starts from 0 not 1 so the highest elements of an array is array_name[size-1].

Initializing Arrays

It is like a variable, an array can be initialized. To initialize an array, you provide initializing values which are enclosed within curly braces in the declaration and placed following an equals sign after the array name. Here is an example of initializing an integer array.

1int list[5] = {2,1,3,7,8};

Array and Pointer

Each array element occupies consecutive memory locations and array name is a pointer that points to the first element. Beside accessing array via index we can use pointer to manipulate array. This program helps you visualize the memory address each array elements and how to access array element using pointer.

01#include <stdio.h>
02  
03void main()
04{
05     
06    const int size = 5;
07     
08    int list[size] = {2,1,3,7,8};
09     
10    int* plist = list;
11  
12    // print memory address of array elements
13    for(int i = 0; i < size;i++)
14    {
15        printf("list[%d] is in %d\n",i,&list[i]);
16     
17    }
18  
19    // accessing array elements using pointer
20    for(i = 0; i < size;i++)
21    {
22        printf("list[%d] = %d\n",i,*plist);
23         
24        /* increase memory address of pointer so it go to the next
25           element of the array */
26        plist++;
27    }
28  
29}

Here is the output

list[0] is in 1310568
list[1] is in 1310572
list[2] is in 1310576
list[3] is in 1310580
list[4] is in 1310584
list[0] = 2
list[1] = 1
list[2] = 3
list[3] = 7
list[4] = 8

You can store pointers in an array and in this case we have an array of pointers. This code snippet use an array to store integer pointer.

1int *ap[10];

Multidimensional Arrays

An array with more than one index value is called a multidimensional array. All the array above is called single-dimensional array. To declare a multidimensional array you can do follow syntax

1data_type array_name[][][];

The number of square brackets specifies the dimension of the array. For example to declare two dimensions integer array we can do as follows:

1int matrix[3][3];

Initializing Multidimensional Arrays

You can initialize an array as a single-dimension array. Here is an example of initialize an two dimensions integer array:

1int matrix[3][3] =
2{
3  {11,12,13},
4  {21,22,23},
5  {32,31,33},
6};

17.Pointers

2011-01-20T08:37:00.000-08:00

C pointer is a memory address. When you define a variable for example:

1int x = 10;

You specify variable name (x), its data type (integer in this example) and its value is 10. The variable x resides in memory with a specified memory address. To get the memory address of variable x, you use operator & before it. This code snippet print memory address of x

1printf("memory address of x is %d\n",&x);

and in my PC the output is

memory address of x is 1310588

Now you want to access memory address of variable x you have to use pointer. After that you can access and modify the content of memory address which pointer point to. In this case the memory address of x is 1310588 and its content is 10. To declare pointer you use asterisk notation (*) after pointer's data type and before pointer name as follows:

1int *px;

Now if you want pointer px to points to memory address of variable x, you can use address-of operator (&) as follows:

1int *px = &x;

After that you can change the content of variable x for example you can increase, decrease x value :

1*px += 10;
2printf("value of x is %d\n",x);
3*px -= 5;
4printf("value of x is %d\n",x);

and the output indicates that x variable has been change via pointer px.

value of x is 20
value of x is 15

It is noted that the operator (*) is used to dereference and return content of memory address.

In some programming contexts, you need a pointer which you can only change memory address of it but value or change the value of it but memory address. In this cases, you can use const keyword to define a pointer points to a constant integer or a constant pointer points to an integer as follows:

01int c = 10;
02int c2 = 20;
03
04/* define a pointer and points to an constant integer.
05pc can point to another integer but you cannot change the
06content of it */
07
08const int *pc = &c;
09
10/* pc++; */ /* cause error */
11
12printf("value of pc is %d\n",pc);
13
14pc = &c2;
15
16printf("value of pc is %d\n",pc);
17
18/* define a constant pointer and points to an integer.
19py only can point to y and its memory address cannot be changed
20you can change its content */
21
22int y = 10;
23int y2 = 20;
24
25int const *py = &y;
26
27*py++;/* it is ok */
28printf("value of y is %d\n",y);
29
30/* py = &y2; */ /* cause error */

Here is the output for code snippet

value of pc is 1310580
value of pc is 1310576
value of y is 10

16.Recursive Function

2011-01-20T07:50:00.000-08:00

Definition

Recursive function is a function which contains a call to itself.

Why recursive function

Recursive function allows you to divide your complex problem into identical single simple cases which can handle easily. This is also a well-known computer programming technique: divide and conquer.

Warning of using recursive function

Recursive function must have at least one exit condition that can be satisfied. Otherwise, the recursive function will call itself repeatly until the runtime stack overflows.

Example of using recursive function

Recursive function is closely related to definitions of functions in mathematics so we can solving factorial problems using recursive function

All you know in mathematics the factorial of a positive integer N is defined as follows:

N! = N*(N-1)*(N-2)…2*1;

Or in a recursive way:

N! = 1 if N <=1 and N*(N-1)! if N > 1

The recursive function to calculate factorial

01# include<stdio.h>
02  
03int factorial(unsigned int number)
04{
05    if(number <= 1)
06        return 1;
07    return number * factorial(number - 1);
08}
09void main()
10{
11    int x = 5;
12    printf("factorial of %d is %d",x,factorial(x));
13}

The output of program

factorial of 5 is 120

In theory, all recursive functions can be rewritten by using iteration. In case number of recursive calls exceeded, the runtime stack can be overflow, you have to implement your recursive function using iteration. for example we can rewrite the factorial calculation using iteration as follows:

1int factorial(unsigned int number){

2    int f = 1;

3    while(number < 0)

4        f *= number--;

5    return f

6}

14. Introduction to Functions

2011-01-20T07:38:00.001-08:00

Define function

Function is a block of source code which does one or some tasks with specified purpose.

Benefit of using function

C programming language supports function to provide modularity to the software.

One of major advantage of function is it can be executed as many time as necessary from different points in your program so it helps you avoid duplication of work.

By using function, you can divide complex tasks into smaller manageable tasks and test them independently before using them together.

In software development, function allows sharing responsibility between team members in software development team. The whole team can define a set of standard function interface and implement it effectively.

Structure of function

Function header

The general form of function header is:

1return_type function_name(parameter_list)

Function header consists of three parts:

Data type of return value of function; it can be any legal data type such as int, char, pointer… if the function does not return a value, the return type has to be specified by keyword void.

Function name; function name is a sequence of letters and digits, the first of which is a letter, and where an underscore counts as a letter. The name of a function should meaningful and express what it does, for example bubble_sort,

And a parameter list; parameter passed to function have to be separated by a semicolon, and each parameter has to indicate it data type and parameter name. Function does not require formal parameter so if you don’t pass any parameter to function you can use keyword void.

Here are some examples of function header:

1/* sort the array of integer a with the
2specified size and return nothing */
3void sort(int a[], int size);
4
5/* authenticate user by username and password and return true
6if user is authenticated */
7bool authenticate(char*username,char*password)

Function body

Function body is the place you write your own source code. All variables declare in function body and parameters in parameter list are local to function or in other word have function scope.

Return statement

Return statement returns a value to where it was called. A copy of return value being return is made automatically. A function can have multiple return statements. If the void keyword used, the function don’t need a return statement or using return; the syntax of return statement is return expression;

Using function

How to use the function

Before using a function we should declare the function so the compiler has information of function to check and use it correctly. The function implementation has to match the function declaration for all part return data type, function name and parameter list. When you pass the parameter to function, they have to match data type, the order of parameter.

Source code example

Here is an example of using function.

01#include<stdio.h>
02  
03/* functions declaration */
04  
05void swap(int *x, int *y);
06  
07  
08  
09void main()
10{
11    int x = 10;
12    int y = 20;
13  
14    printf("x,y before swapping\n");
15    printf("x = %d\n",x);
16    printf("y = %d\n",y);
17     
18    // using function swap
19    swap(&x,&y);
20  
21    printf("x,y after swapping\n");
22    printf("x = %d\n",x);
23    printf("y = %d\n",y);
24  
25}
26  
27  
28/* functions implementation */
29  
30void swap(int *x, int *y){
31    int temp = *x;
32        *x = *y;
33        *y = temp;
34}

Here is the output

x,y before swappingx = 10
y = 20
ping
x = 20
y = 10x,y after swa
p
ess any key to continueP
r