Showing posts with label Dynamic memory. Show all posts
Showing posts with label Dynamic memory. Show all posts

Monday, 16 September 2013

Saturday, 7 September 2013

Showing posts with label Dynamic memory. Show all posts
Showing posts with label Dynamic memory. Show all posts

Monday, 16 September 2013

Dynamic memory allocation




Allocate a dynamic array of a stated size.Load numbers into the array and then sum the numbers in the array.

#include <stdio.h>

#include <stdlib.h>


int main()
{
int retval;   /* value returned from scanf */
long *nums;   /* pointer to arrray of numbers to sum */
short how_many;/* number of numbers to input and sum */
short inum;   /* counter to index into nums array */
long sum;     /* sum of numbers in nums array */
    /*
    *    input number of elements to allocate
    */
    printf("\nHow many numbers to sum? ");
    scanf("%hd",&how_many);
    /*
    *    dynamically allocate memory for how_manay 
    *    long's
    */
 nums = (long *)calloc(how_many, sizeof(long) );

    if(nums == (long *)NULL)
    {
         fprintf(stderr,"\nCould not allocate memory");
         return 1;
    }
    /*
    *    input numbers to store in array
    */
    for( inum =0; inum < how_many; ++inum)
    {
         printf("\nEnter #%d: ", inum + 1);
         retval = scanf("%ld",&nums[inum] );
    }
    /*
    *    sum the numbers in the array
    */
    for( sum = inum = 0; inum < how_many; ++inum )
    {
         /*
         *    add number to sum
         */
         sum += nums[inum];
         /*
         *    show running total
         */
         printf("\n%3d: %10ld %10ld",
              inum+1,nums[inum],sum);
    }
    /*
    *    print the final total
    */
    printf("\nThe sum of the %d numbers",how_many);
    printf(" entered is %ld\n",sum);
    /*
    *    free the memory back to the heap
    */
    free( (char *)nums );
    return 0;

}

Executing the program....
$demo
How many numbers to sum? 
Enter #1: 
Enter #2: 
  1:         21         21
  2:          3         24
The sum of the 2 numbers entered is 24

Saturday, 7 September 2013

Delete N nodes after M nodes of a linked list




Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same till end of the linked list.
Difficulty Level: Rookie
Examples:
Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

Input:
M = 3, N = 2
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->2->3->6->7->8

Input:
M = 1, N = 1
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:  
Linked List: 1->3->5->7->9
The main part of the problem is to maintain proper links between nodes, make sure that all corner cases are handled. Following is C implementation of function skipMdeleteN() that skips M nodes and delete N nodes till end of list. It is assumed that M cannot be 0.
// C program to delete N nodes after M nodes of a linked list
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct node
{
    int data;
    struct node *next;
};
/* Function to insert a node at the beginning */
void push(struct node ** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    /* put in the data  */
    new_node->data  = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref)  = new_node;
}
/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
// Function to skip M nodes and then delete N nodes of the linked list.
void skipMdeleteN(struct node  *head, int M, int N)
{
    struct node *curr = head, *t;
    int count;
    // The main loop that traverses through the whole list
    while (curr)
    {
        // Skip M nodes
        for (count = 1; count<M && curr!= NULL; count++)
            curr = curr->next;
        // If we reached end of list, then return
        if (curr == NULL)
            return;
        // Start from next node and delete N nodes
        t = curr->next;
        for (count = 1; count<=N && t!= NULL; count++)
        {
            struct node *temp = t;
            t = t->next;
            free(temp);
        }
        curr->next = t; // Link the previous list with remaining nodes
        // Set current pointer for next iteration
        curr = t;
    }
}
// Driver program to test above functions
int main()
{
    /* Create following linked list
      1->2->3->4->5->6->7->8->9->10 */
    struct node* head = NULL;
    int M=2, N=3;
    push(&head, 10);
    push(&head, 9);
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);
    printList(head);
    skipMdeleteN(head, M, N);
    printf("\nLinked list after deletion is :\n");
    printList(head);
    return 0;
}
Output:
M = 2, N = 3
Given Linked list is :
1 2 3 4 5 6 7 8 9 10

Linked list after deletion is :
1 2 6 7
Time Complexity: O(n) where n is number of nodes in linked list.