implementation of selection sorting algorithm in C

Implementation of selection sorting algorithm in C

 

/*
* implementation of selection sorting algorithm in C
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL;

struct NODE;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef int DataType;

struct NODE{ // single link list node
    DataType data;
    PtrNode next;
};

PtrNode NewList() // returns the List's header
{
    PtrNode tempNode =  malloc(sizeof(Node));
    tempNode->next = NULL;
    return tempNode;
}
Position NewNode() // creates a new node
{
    return malloc(sizeof(Node));
}

void Delete(PtrNode node)// deletes the node
{
    free(node);
}
BOOL IsLast(List L, Position pos) // checks id the given position is last in the list
{
    return (pos->next == NULL);
}
void Insert ( List L, DataType data, Position pos)// inserts a data field in a particular position
{
    Position tempPos;
    tempPos = NewNode(); // 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;
    pos->next = tempPos;
}

void DisplayElement(DataType element) // displays an individual element
{
    printf("%d\n", element);
}
void Display (List L) // this function displays the list's contents linearly
{
    Position pos = L->next;
    if(pos == NULL)
        return;
    while (pos != NULL)
        {
            DisplayElement(pos->data);
            pos = pos->next;
        }
}

void SwapNodes(PtrNode preNode1, PtrNode preNode2) // swap the nodes connected to the passed on nodes
{
    Position temp;
    temp = preNode1->next; // first swaps the nodes as such
    preNode1->next = preNode2->next;
    preNode2->next = temp;

    temp = preNode1->next->next; // now alter the swapped node's pointer links
    preNode1->next->next = preNode2->next->next;
    preNode2->next->next = temp;
}
void selectionSort(List L)
{
    if(L->next == NULL || L->next->next == NULL)
        return;
    Position pos = L;
    Position preMaxNode, preTempNode;
    while(pos != NULL)
    {
        preTempNode = pos;
        preMaxNode = pos;
        while(!IsLast(L, preTempNode))
        {
            if(preMaxNode->next->data < preTempNode->next->data)
                preMaxNode = preTempNode;
            preTempNode = preTempNode->next;
        }
        if(!IsLast(L, pos)) // if the top is the last data field, no swapping is needed
            SwapNodes(pos, preMaxNode);
        pos = pos->next;
    }

}

int main()
{
    List L = NewList(); // creates a new list
    int n, i, data;
    Position top = L;
    printf("enter size of list");
    scanf("%d", &n);
    if(n < 2 )
    {
        fprintf(stderr,"invalid list size. The size cannot be lesser than 2");
        getch();
        return -1;
    }
    printf("enter elements: ");
    for(i=0; i<n; i++)
    {
        scanf("%d", &data); // creates the list
        Insert(L, data, top);
        top = top->next;
    }
    selectionSort(L); // sorts the list
    printf("\nthe sorted elements:\n");
    Display(L);
    getch();
    return 0;
}




copyright (c) 2015 K Sreram.
About my blog
 

Implementation of insertion sorting algorithm

Implementation of insertion sorting algorithm

 

/*
* implementation of insertion sorting algorithm in C
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL;

struct NODE;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef int DataType;

struct NODE{ // single link list node
    DataType data;
    PtrNode next;
};
// vital ones>>>>>>>>>>>>>>>>>>>>>>>>>
PtrNode NewList() // returns the List's header
{
    PtrNode tempNode =  malloc(sizeof(Node));
    tempNode->next = NULL;
    return tempNode;
}
Position NewNode() // creates a new node
{
    return malloc(sizeof(Node));
}

void Delete(PtrNode node)// deletes the node
{
    free(node);
}
BOOL IsLast(List L, Position pos) // checks id the given position is last in the list
{
    return (pos->next == NULL);
}
void Insert ( List L, DataType data, Position pos)// inserts a data field in a particular position
{
    Position tempPos;
    tempPos = NewNode(); // 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;
    pos->next = tempPos;
}
Position FindEnd(List L) // finds the end of the list
{
    Position tempPos=L;
    while(!IsLast(L, tempPos))
        tempPos = tempPos->next;
    return tempPos;
}

void DisplayElement(DataType element) // displays an individual element
{
    printf("%d\n", element);
}
void Display (List L) // this function displays the list's contents linearly
{
    Position pos = L->next;
    if(pos == NULL)
        return;
    while (pos != NULL)
        {
            DisplayElement(pos->data);
            pos = pos->next;
        }
}
void inseartionSort(List L) //sorts the list
{
   if(L->next == NULL || L->next->next == NULL)
        return; // if the list contains 0 or 1 element
   Position posTop = L->next->next, tempPos, delPos;
   Position topPrev = L->next;
   DataType data1;
   while(posTop != NULL)
   {
       tempPos = L;
       while(tempPos != posTop)
       {
            data1 = posTop->data;
            if(tempPos->next->data < posTop->data )
                {
                    Insert(L, data1, tempPos);
                    delPos = posTop;
                    posTop = posTop->next;
                    Delete(delPos);
                    topPrev->next = posTop;
                    break;
                }
            tempPos = tempPos->next;
       }
       if(tempPos == posTop)
            {
                topPrev = topPrev->next;
                posTop = posTop->next;
            }
   }

}
int main()
{
    List L = NewList(); // creates a new list
    int n, i, data;
    Position top = L;
    printf("enter size of list");
    scanf("%d", &n);
    if(n < 2 )
    {
        fprintf(stderr,"invalid list size. The size cannot be lesser than 2");
        getch();
        return -1;
    }
    printf("enter elements: ");
    for(i=0; i<n; i++)
    {
        scanf("%d", &data);
        Insert(L, data, top);
        top = top->next;
    }
    inseartionSort(L); // sorts the list
    printf("\nsorted list:\n");
    Display(L);
    getch();
    return 0;
}



copyright (c) 2015 K Sreram.
About my blog
 

polynomial linked list implementation

Polynomial linked list implementation

/*
   polynomial multiplication and addition general functions
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL; // the more obvious choice would be char, but int is more
                  // time efficient as it uses a basic memory unit optimal for the
                  // particular processor design, by default

struct NODE;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef List Polynomial;
struct polyTerm {
    int degree; // the power of the taken term
    int coeff; // the coefficient of the term
};
typedef struct polyTerm DataType; // this is a default data type

struct NODE{ // single link list node
    DataType data;
    PtrNode next;
};
// vital ones>>>>>>>>>>>>>>>>>>>>>>>>>
PtrNode NewPoly() // returns the List's header
{
    PtrNode tempNode =  malloc(sizeof(Node));
    tempNode->next = NULL;
    return tempNode;
}
Position NewNode()
{
    // to do: add code to create the other parts of
    // the memory to be allocated.
    return malloc(sizeof(Node)); // for old compilers,
    // explicit type conversion like (Node) is needed to be
    //used.
}

void Delete(PtrNode node)
{
    // to do: add code to clear the other parts of
    // the dynamically allocated memory
    free(node);
}
//***************************************************
/*
* Basic single link list operations :: pointer implementation
*/
Position PrePos(List L, Position pos) /// finds previous position
{
    Position retPos = L;
    if(pos == retPos)
        return NULL;
    while (retPos->next != NULL)
        {
            if(retPos->next == pos)
                return retPos;
            retPos = retPos->next;
        }
    return NULL;

}

void DeleteNode(List L, Position pos)
{
    if(pos == NULL)
    {
        fprintf(stderr, "error: in function DeleteNode, value of pos is NULL");
        return;
    }
    PrePos(L, pos)->next = pos->next;
    Delete(pos);
}

void DeleteList(List L)
{
    PtrNode tempNode = L->next, tempNode2;
    while (tempNode != NULL)
    {
        tempNode2 = tempNode->next;
        Delete(tempNode);
        tempNode = tempNode2;
    }
    L->next = NULL;
}

void FreeList(List L)
{
    DeleteList(L);
    free(L);
}
// standard operations*******************************
BOOL IsLast(List L, Position pos)
{
    return (pos->next == NULL);
}
BOOL IsEmpty(List L)
{
    return (L->next == NULL);
}

void Insert ( List L, DataType data, Position pos)
{
    Position tempPos;
    tempPos = NewNode(); // 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;
    pos->next = tempPos;
}

Position FindPrevious(List L, int degree) // by default, this function does not check for the
{                                   // header node which never gets initialised

    Position tempPos = L;
    while(tempPos->next != NULL && tempPos->next->data.degree != degree) /// searches for the first occurrence of value 'element'
        tempPos = tempPos->next;
    return tempPos; // returns the node preceding the node containing the value 'element'
}

void DeleteElement(List L, DataType data)
{
    Position tempPos = FindPrevious(L, data.degree); // by all chances, this cannot delete the list
    PtrNode tempNode;
    if(IsLast(L, tempPos)) // element not found
            return;

    tempNode = tempPos->next;
    tempPos->next = tempNode->next;
    Delete(tempNode);

}

Position Find(List L, int degree)
{
    Position tempPos = L;
    while(tempPos!=NULL && tempPos->data.degree!=degree)
        tempPos = tempPos->next;
    return tempPos; // this return NULL by default when it fails to find the
                    // element
}
Position FindEnd(List L)
{

    Position tempPos=L;
    while(!IsLast(L, tempPos))
        tempPos = tempPos->next;
    return tempPos;
}
Position moveForward(Position pos)
{
    return pos->next;
}
DataType returnElement(Position pos)
{
    return pos->data;
}
//*****************************************************
void DisplayElement(DataType element)
{

    // to do: add display code here
    printf("%dx^%d", element.coeff, element.degree);
}
void Display (List L)
{

    Position pos = L->next;
    if(pos == NULL)
        return;
    while (pos != NULL)
        {
            DisplayElement(pos->data);
            if(pos->next != NULL)
                printf(" + ");
            pos = pos->next;
        }
}

Polynomial AddPolynomial(const Polynomial p1, const Polynomial p2)
{
    Polynomial retPoly = NewPoly();
    Position p_1 = p1->next, p_2 = p2->next, top = retPoly;
    DataType tempTerm;
    while (p_1 && p_2)
    {
        if(p_1->data.degree > p_2->data.degree)
            {
                Insert(retPoly, p_1->data, top);
                p_1 = p_1->next;
            }
        else if(p_1->data.degree < p_2->data.degree)
            {
                Insert(retPoly, p_2->data, top);
                p_2 = p_2->next;
            }
        else if(p_1->data.degree == p_2->data.degree)
            {
                tempTerm.degree = p_1->data.degree;
                tempTerm.coeff = p_1->data.coeff + p_2->data.coeff;
                Insert(retPoly, tempTerm, top);
                p_1 = p_1->next;
                p_2 = p_2->next;
            }
        top = top->next;
    }
    if(p_1 != NULL)
        for(;p_1; p_1 = p_1->next, top = top->next)
            Insert(retPoly, p_1->data, top);
    else if (p_2 != NULL)
        for(;p_2; p_2 = p_2->next, top= top->next)
            Insert(retPoly, p_2->data, top);
    return retPoly;

}
DataType multyplyTerms(DataType t1, DataType t2)
{
    DataType t3;
    t3.coeff  = t1.coeff * t2.coeff;
    t3.degree = t1.degree + t2.degree;
    return t3;
}

Polynomial PolyMultiply(const Polynomial p1, const Polynomial p2)
{ /// the runtime of this function is O(M^2 + MN)
    Polynomial retPol = NewPoly();
    Polynomial P_1 = p1->next, P_2 = p2->next, top = retPol;
    DataType tempData;
    while(P_1)
    {
        top = retPol;
        P_2 = p2->next;
        while (P_2)
        {
            tempData = multyplyTerms(P_1->data, P_2->data);
            while(top->next && top->next->data.degree > tempData.degree)
                    top = top->next;// this loop terminates when the data field in the next iteration
                    // is either equal to or lesser the the current

            if(top->next == NULL) // if top->next is null, terms just get inserted at the top
            { // this does not occur when P_1 != p1->next. but for that condition being false,
              // insertion happens consecutively
                Insert(retPol, tempData, top);
                top = top->next;
            }
            else if(top->next->data.degree != tempData.degree)
                { // checks for the equality of degree. If they are not equal, the term just gets inserted
                    Insert(retPol, tempData, top);
                    top = top->next;
                }
            else // this condition is executed when top->next->data.degree == tempData.degree
                top->next->data.coeff = tempData.coeff + top->next->data.coeff; // just add terms of same power
            P_2 = P_2->next;
        }
        P_1 = P_1->next;
    }
    return retPol;
}
Polynomial GetPoly(const char* txt)
{
    Polynomial p = NewPoly();
    Polynomial top = p;
    char ch = '\0';
    DataType temp;
    printf(txt);
    while (ch != 'n' && ch != 'N')
    {
        printf("\n enter coefficient");
        scanf("%d", &temp.coeff);
        printf("\n enter power");
        scanf("%d", &temp.degree);
        Insert(p, temp, top);
        top = top->next;
        printf("\n do you want to add another term (Y/N)?");
        ch = getch();
    }
    return p;
}
int main()
{
   Polynomial P1 = GetPoly("\nenter the terms of the first polynomial:\n");
   Polynomial P2 = GetPoly("\nenter the terms of the second polynomial:\n");
   Polynomial P_mult = PolyMultiply(P1, P2);
   Polynomial P_add = AddPolynomial(P1, P2);
   printf("\nthe first polynomial:\n");
   Display(P1);
   printf("\nthe second polynomial:\n");
   Display(P2);
   printf("\n\nthe sum of the two polynomial:\n");
   Display(P_add);
   printf("\n\nthe product of the two polynomials:\n");
   Display(P_mult);
   FreeList(P1);
   FreeList(P2);
   FreeList(P_add);
   FreeList(P_mult);
   getch();
    return 0;
}



copyright (c) 2015 K Sreram.
About my blog