implementation example of double linked list (set union and intersection operations)

Implementation example of double linked list (set union and intersection operations)

 

/*
* implementation example of double linked list (set union and intersection operations)
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

enum BOOL {FALSE, TRUE};
typedef int BOOL;
struct NODE_d;
typedef struct NODE_d Node_d;
typedef Node_d* PtrNode_d;
typedef PtrNode_d List_d;
typedef PtrNode_d Position_d;
typedef int DataType; // this is a default data type

struct NODE_d{ // single link list node
    DataType data;
    PtrNode_d next;
    PtrNode_d previous;
};

PtrNode_d NewList_d() // returns the List's header
{
    PtrNode_d tempNode =  malloc(sizeof(Node_d));
    tempNode->next = NULL;
    tempNode->previous = NULL;
    return tempNode;
}
Position_d NewNode_d()
{
    return malloc(sizeof(Node_d)); // for old compilers,
    // explicit type conversion like (Node) is needed to be
    //used.
}

void Delete_d(PtrNode_d node)
{
    free(node);
}

BOOL IsLast_d(List_d L, Position_d pos)
{
    return (pos->next == NULL);
}

BOOL IsEmpty_d(List_d L)
{
    return (L->next == NULL);
}

void Insert_d ( List_d L, DataType data, Position_d pos)
{
    Position_d tempPos;
    tempPos = NewNode_d(); // creates and allocates memory space
    if(tempPos == NULL)
    {
        fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
        return;
    }
    tempPos->data = data;
    tempPos->next = pos->next;
    tempPos->previous = pos;
    pos->next = tempPos;
    if(!IsLast_d(L, tempPos))
        tempPos->next->previous = tempPos;
}


Position_d Find_d(List_d L, DataType element)
{
    Position_d tempPos = L->next;
    while(tempPos!=NULL && tempPos->data!=element)
        tempPos = tempPos->next;
    return tempPos; // this return NULL by default when it fails to find the
                    // element
}

void DisplayElement_d(DataType element)
{
    printf("%d\n", element);
}
void Display_d (List_d L)
{

    Position_d pos = L->next;
    if(IsEmpty_d(L))
        return;
    while (pos != NULL)
        {
            DisplayElement_d(pos->data);
            pos = pos->next;
        }
}

List_d setIntersect(List_d L1, List_d L2) // this function runs at O(N^2) or to be more precise O(MN)
{
    Position_d pos_top, tempPos;
    List_d L = NewList_d();
    pos_top = L;
    tempPos = L1->next;
    while(tempPos != NULL)
    {
        if(Find_d(L, tempPos->data)==NULL && Find_d(L2, tempPos->data) != NULL)
        {
            Insert_d(L, tempPos->data, pos_top);
            pos_top = pos_top->next;
        }
        tempPos = tempPos->next;
    }

    return L;
}

List_d setUnion(List_d L1, List_d L2) // this function runs at O(N^2) or to be more precise O(MN)
{
    Position_d pos_top, tempPos;
    List_d L = NewList_d();
    pos_top = L;
    tempPos = L1->next;
    while (tempPos != NULL)
    {
        if(Find_d(L, tempPos->data) == NULL)
            { // there is a possibility that an element can be repeated in the same list
                Insert_d(L, tempPos->data, pos_top);
                pos_top = pos_top->next;
            }
        tempPos = tempPos->next;
    }
    tempPos = L2->next;
    while(tempPos != NULL)
    {
        if(Find_d(L, tempPos->data) == NULL)
            { // incrementation takes place only if the data record is not found
                Insert_d(L, tempPos->data, pos_top);
                pos_top = pos_top->next;
            }
        tempPos = tempPos->next;
    }
    return L;
}
void getElements(List_d L, const char* A)
{
    unsigned int i, n;
    int data; Position_d top = L;
    printf("enter the number of elements for %s", A);
    scanf("%d", &n);
    printf("enter the elements of the set %s:", A);
    for(i=0; i<n; i++)
    {
        scanf("%d", &data);
        Insert_d(L, data, top);
        top = top->next;
    }
}
int main()
{
    List_d L1 = NewList_d();
    List_d L2 = NewList_d();
    List_d L_union, L_intersection;
    getElements(L1, "A");
    getElements(L2, "B");
    L_union = setUnion(L1, L2);
    printf("\nunion of A and B:\n");
    Display_d(L_union);
    getch();
    L_intersection = setIntersect(L1, L2);
    printf("\nintersection of A and B:\n");
    Display_d(L_intersection);

    getch();
    return 0;
}




 copyright (c) 2015 K Sreram.
About my blog