7-Compound Data Structures

Compound Data Structures

  • Complex structures like array of array (2D Array), arrays of lists, arrays of strings, and so forth are also possible.

  • 2D Array is just notation convenience because ultimately its stored as one-dimensional array

  • Two-dimensional array allocation

    This function dynamically allocates the memory for a Two-dimensional array, as an array of arrays. We first allocate an array of pointers, then allocate memory for each row. With this function, the statement

    int **a = malloc2d(M,N); // allocates an MxN array of integers
int **malloc2d(int r , int c)
{
    int **t = new int*[r];
    for(int i =0 ; i<r ; i++)
        t[i] = new int[c];
    return t;
}

  • String Sort

    When processing string we normally use pointers because they are easy to manipulate

    image-20200709074033915

    #include <iostream.h>
#include <stdlib.h>
#include <string.h>

int compare ( const void *i , const void *j)
	{return strcmp(*(char **)i , *(char **)j);} //dereferanced strings for comparisions
int main()
{
    const int Nmax = 1000;
    const int Mmax = 10000;
    char* a[Nmax]; int N; // This is pointer to each string
    char buf[Mmac]; int M =0;
    for ( N=0 ; N< Nmax ; N++){
        a[N] = &buf[M];			//Stores address of buffer
        if((cin>>a[N])) break;
        M+=strlen(a[N])+1;
    }
    qsort(a,N,sizeof(char*),compare); //quicksort
    for(int i =0; i<N ;i++)
        cout<< a[i] << endl;
}

  • A graph is a fundamental combinatorial object that is defined simply as a set of objects (called vertices) and a set of connections among the vertices (called edges).

  • Adjacency - matrix graph representation

    Its just a simple Undirected graph represented using matrix

    image-20200709075755185

    #include <iostream.h>
int main()
{
    int i,j, adj[V][V];
    for (i =0; i<V;i++)
        for (j=0; j<V;j++)
            adj[i][j]=0;
    for(i=0;i<V;i++) adj[i][i]=1; //self connection
    while(cin>>i>>j){
        adj[i][j]=1; adj[j][i]=1;
    }
}

  • Adjacency-lists representation of a graph

    image-20200709075829259.png

    #include <iostream.h>
stuct node {
    item v; node* next;
    node(int x, node* t)
    {
        v=x; next=t;
    }
};
typedef node *link;
int main(){
    int i,j; link adj[V];
    for(i=0;i<V; i++) adj[i]=0;
    while(cin>> i >>j){
        adj[j] = new node(i,adj[j]);
        adj[i] = new node(j, adj[i]);
    }
}