Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Day 1 Introduction To Data Structures: Vritika Naik Twitter: @naikvritika Linkedin: Vritika Naik

    Uploaded by

    manthan
    The document provides an introduction to data structures and algorithms. It discusses data types, data structures, arrays, pointers, dynamic memory allocation, structures, and recursion. Key topics covered include integers, floats, lists, stacks, efficiency, insertion, deletion, traversal, search, greedy algorithms, divide and conquer algorithms, backtracking, randomized algorithms, 1D and 2D arrays, function pointers, malloc(), calloc(), realloc(), free(), structures, and examples of recursion such as calculating sums, factorials, displaying numbers in reverse order, power functions, greatest common divisors, Fibonacci sequences, and the differences between tail and head recursion.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Day 1 Introduction To Data Structures: Vritika Naik Twitter: @naikvritika Linkedin: Vritika Naik

    Uploaded by

    manthan
    31 views28 pages
    The document provides an introduction to data structures and algorithms. It discusses data types, data structures, arrays, pointers, dynamic memory allocation, structures, and recursion. Key topics covered include integers, floats, lists, stacks, efficiency, insertion, deletion, traversal, search, greedy algorithms, divide and conquer algorithms, backtracking, randomized algorithms, 1D and 2D arrays, function pointers, malloc(), calloc(), realloc(), free(), structures, and examples of recursion such as calculating sums, factorials, displaying numbers in reverse order, power functions, greatest common divisors, Fibonacci sequences, and the differences between tail and head recursion.

    Original Description:

    DS

    Original Title

    465932178-DSA-DAY-1-Introduction-to-Data-Structures

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides an introduction to data structures and algorithms. It discusses data types, data structures, arrays, pointers, dynamic memory allocation, structures, and recursion. Key topics covered include integers, floats, lists, stacks, efficiency, insertion, deletion, traversal, search, greedy algorithms, divide and conquer algorithms, backtracking, randomized algorithms, 1D and 2D arrays, function pointers, malloc(), calloc(), realloc(), free(), structures, and examples of recursion such as calculating sums, factorials, displaying numbers in reverse order, power functions, greatest common divisors, Fibonacci sequences, and the differences between tail and head recursion.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views28 pages

    Day 1 Introduction To Data Structures: Vritika Naik Twitter: @naikvritika Linkedin: Vritika Naik

    Uploaded by

    manthan
    The document provides an introduction to data structures and algorithms. It discusses data types, data structures, arrays, pointers, dynamic memory allocation, structures, and recursion. Key topics covered include integers, floats, lists, stacks, efficiency, insertion, deletion, traversal, search, greedy algorithms, divide and conquer algorithms, backtracking, randomized algorithms, 1D and 2D arrays, function pointers, malloc(), calloc(), realloc(), free(), structures, and examples of recursion such as calculating sums, factorials, displaying numbers in reverse order, power functions, greatest common divisors, Fibonacci sequences, and the differences between tail and head recursion.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 28

    DAY 1

    INTRODUCTION TO DATA
    STRUCTURES
    VRITIKA NAIK
    Twitter: @NaikVritika
    LinkedIn: Vritika Naik
    • Data Types
    • Data Structures
    • Algorithms
    TOPICS TO • Arrays
    • Pointers
    BE • Dynamic Memory Allocation
    COVERED • Structures
    • Recursion
    Data Type

    • Defines amount of allowed


    values and the operations that
    can be performed on those
    values. Eg: float, int, bool,
    double
    • Can be built-in or user-defined.
    • Abstract Data type – defines a
    data type logically. Eg: List
    ADT, Stack ADT
    Data Structures

    • Used to physically implement ADT.


    ADT is the logical view of it.
    • Can be nested.
    • Advantages:
    1. Efficiency
    2. Reusability
    3. Abstraction
    • Operations: Insertion, Deletion,
    Traversal, Search
    Algorithms

    Procedure with well-defined steps intended to solve a problem


    • Greedy Algorithms - Believes in NOW
    • Divide and Conquer Algorithms – modularize
    • Backtracking – reverse engineering
    • Randomized Algorithms – uses random numbers to take decisions
    1D Arrays
    An array is a collection of items
    stored at contiguous memory
    locations. The idea is to store
    multiple items of the same type
    together. Eg:
    int age [100]
    float salary[15]
    2D Arrays

    • Declaration: int x[10][20];


    • Initialization:
    1. int x[3][4] = {0, 1 ,2 ,3 ,4 , 5 , 6
    , 7 , 8 , 9 , 10 , 11};
    2. int x[3][4] = {{0,1,2,3},
    {4,5,6,7}, {8,9,10,11}};
    • Access: int x[2][1];
    Pointers
    A pointer is a variable whose value is the address of another variable, i.e., direct
    address of the memory location. Like any variable or constant, you must declare
    a pointer before using it to store any variable address. The general form of a
    pointer variable declaration is −

    type *var-name;
    Function Pointers
    • Like normal data pointers(int *, char *, etc), we can have pointers to functions.
    #include <stdio.h>
    // A normal function with an int parameter
    // and void return type
    void fun(int a)
    {
    printf("Value of a is %d\n", a);
    }

    int main()
    {
    // fun_ptr is a pointer to function fun()
    void (*fun_ptr)(int) = &fun;
    (*fun_ptr)(10);
    return 0;
    }
    What is so special about function pointers?

    1) A function pointer points to code, not data. Typically a function


    pointer stores the start of executable code.
    2) We do not allocate de-allocate memory using function pointers.
    3) A function’s name can also be used to get functions’ address.
    4) We can have an array of function pointers.
    5) Function pointer can be used in place of switch case.
    Dynamic Memory Allocation
    malloc() function
    Allocates N bytes in memory and return pointer to allocated memory.
    Syntax
    void * malloc(number_of_bytes);

    calloc() function
    calloc() function allocates memory contiguously.
    Syntax
    void* calloc(number_of_blocks, number_of_bytes);

    realloc() function
    Alters/update the size of an existing allocated memory blocks (which has been created by either malloc() or calloc()).
    Syntax
    void* realloc(ptr, updated_memory_size);

    free() function
    Clears the pointer (assigns NULL to the pointer) to clear the dynamically allocated memory.
    Syntax
    free(ptr);
    Structures
    A structure creates a data type that can be used to group items of possibly different types into a single type.
    #include<stdio.h>

    struct Point
    {
    int x, y;
    };
    int main()
    {
    struct Point p1 = {0, 1}; p1.x = 20;
    printf ("x = %d, y = %d", p1.x, p1.y);
    return 0;
    }
    Recursion
    PROCESS OF CALLING ITSELF
    Sum of n natural
    numbers
    int sum(int n)
    {
    if (n != 0) // sum() function calls
    itself
    return n + sum(n-1);
    else return n;
    }
    Factorial

    long int fact(int n)


    {
    if(n == 0)
    return(1);
    return(n * fact(n-1));
    }/*End of fact()*/
    Displaying numbers in reverse

    void display1(int n)
    {
    if( n==0 )
    return;
    printf("%d ",n);
    display1(n-1);
    }/*End of display1()*/
    Displaying numbers

    void display2(int n)
    {
    if( n==0 )
    return;
    display2(n-1);
    printf("%d ",n);
    }/*End of display2()*/
    Power

    float power(float a , int n)


    {
    if(n == 0)
    return(1);
    else
    return(a * power(a,n-1));
    }/*End of power()*/
    GCD

    int GCD(int a, int b)


    {
    if(b==0)
    return a;
    return GCD(b, a%b);
    }/*End of GCD()*/
    Fibonacci

    int fib(int n)
    {
    if(n==0 || n==1)
    return(1);
    return(fib(n-1) + fib(n-2));
    }
    Tail Recursion: A call is tail-recursive if Head Recursion: A call is head-recursive
    nothing has to be done after the call returns i.e. when the first statement of the function is the
    when the call returns, the returned value is recursive call.
    immediately returned from the calling function

    int countDown(int number) int countDown( int number)


    {
    {
    if( number == 0 ) if( n > 0 )
    return 0; return countDown( number - 1 );
    return countDown(number - 1); return 0;
    }
    QUESTIONS?
    THANK
    YOU!
    VRITIKA NAIK
    Twitter: @NaikVritika
    LinkedIn: Vritika Naik

    You might also like