Results 1 to 2 of 2

Thread: Changing C Code

  1. #1
    Join Date
    Nov 2002
    Posts
    50

    Unanswered: Changing C Code

    Hi Can anyone change this code to a different code? but it should do the same thing

    Thanks in Advance

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

    int arraywidth = 0, arrayheight = -1, uniquesets, unioncalls=0,
    recursivefindcalls=0;

    struct DisjSet {
    int sets;
    char data;
    };

    //function prototypes
    void SetUnion(DisjSet *, int, int);
    int Find(DisjSet *, int);
    void Merge ( DisjSet **, DisjSet **, int , int , int );
    void MergeSort ( DisjSet **, int );
    void MSort ( DisjSet **, DisjSet **, int, int);

    void main ()
    {
    FILE *fil;
    fil = fopen ("data.txt", "r");

    char temp[200];
    while (fgets(temp, 200, fil)) {
    if (arrayheight == -1) arraywidth=strlen(temp)-2;
    arrayheight++;
    }

    DisjSet *MySet = (DisjSet *) malloc( sizeof(struct DisjSet) * arraywidth *
    arrayheight);
    uniquesets = arraywidth*arrayheight;
    fclose(fil);

    fil = fopen ("data.txt", "r");
    char ch;
    int i, j, vl=0;
    for ( j=0; j<arrayheight; j++)
    for ( i=0; i<arraywidth; i++)
    {
    ch = fgetc(fil);
    while ((ch<'A') || (ch>'z')) ch=fgetc(fil);
    MySet[vl].data = ch;
    MySet[vl++].sets = 0;
    }
    fclose(fil);

    vl=0;
    for ( j=0; j<arrayheight; j++)
    for ( i=0; i<arraywidth; i++, vl++)
    {
    if (i>0)
    if (MySet[vl - 1].data == MySet[vl].data)
    SetUnion(MySet, vl, Find(MySet, vl - 1) );
    if (j>0)
    if (MySet[vl - arraywidth].data == MySet[vl].data)
    SetUnion(MySet, Find(MySet, vl), Find(MySet, vl - arraywidth) );
    }

    DisjSet **Rep = (DisjSet **) malloc( uniquesets * sizeof(DisjSet *) );

    vl = arraywidth*arrayheight;
    j=0;
    for ( i=0; i<vl; i++) {
    MySet[ Find(MySet, i) ].sets--;
    if (MySet[i].sets <= 0)
    Rep[j++] = &MySet[i];
    }

    MergeSort (Rep, uniquesets);

    printf(" There are %d sets (connected components) \n", uniquesets);
    printf(" SetUnion was called %d times but unions were performed only %d
    times.\n", unioncalls, arraywidth*arrayheight - uniquesets);
    printf(" (To verify) Total elements in Report sets: %d \n Times Find(...)
    called : %d\n", -vl, recursivefindcalls);
    vl=0;
    for (i=0; i<uniquesets; i++) {
    printf ("%3d. Type: %c Num elements: %d \n", i+1, Rep[i]->data,
    -Rep[i]->sets);
    vl += Rep[i]->sets;
    }

    free (Rep);
    free (MySet);
    }

    void SetUnion(DisjSet *S, int root1, int root2)
    {
    unioncalls++;
    if ( S[root1].sets > S[root2].sets )
    S[root1].sets = root2;
    else
    {
    if ( S[root1].sets == S[root2].sets )
    S[root1].sets--;
    S[root2].sets = root1;
    }
    uniquesets--;
    }

    int Find(DisjSet *S, int num)
    {
    recursivefindcalls++;
    if (S[num].sets <= 0)
    return num;
    else
    return S[num].sets = Find(S, S[num].sets);
    }

    void Merge ( DisjSet *A[], DisjSet *TmpArray[], int Lpos, int Rpos, int RightEnd
    )
    {
    int i, LeftEnd, NumElements, TmpPos;

    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;

    while ( Lpos <= LeftEnd && Rpos <= RightEnd )
    if ( A[Lpos]->sets >= A[Rpos]->sets )
    TmpArray[ TmpPos++ ] = A[Lpos++];
    else
    TmpArray[ TmpPos++ ] = A[Rpos++];

    while (Lpos <= LeftEnd )
    TmpArray [ TmpPos++ ] = A[Lpos++];
    while (Rpos <= RightEnd )
    TmpArray [ TmpPos++ ] = A[Rpos++];

    for ( i=0; i<NumElements; i++, RightEnd--)
    A[RightEnd] = TmpArray[ RightEnd ];
    }

    void MSort ( DisjSet *A[], DisjSet *TmpArray[], int Left, int Right)
    {
    int Center;
    if (Left < Right)
    {
    Center = (Left + Right)/2;
    MSort ( A, TmpArray, Left, Center);
    MSort ( A, TmpArray, Center + 1, Right);
    Merge ( A, TmpArray, Left, Center + 1, Right);
    }
    }

    void MergeSort ( DisjSet *A[], int N)
    {
    DisjSet **TmpArray;

    TmpArray = (DisjSet **) malloc( N * sizeof( DisjSet *));
    if (TmpArray)
    {
    MSort (A, TmpArray, 0, N-1);
    free(TmpArray);
    }
    else
    printf (" ERROR: Cannot sort. No more memory.\n");
    }
    Deep

  2. #2
    Join Date
    Nov 2002
    Posts
    50

    Re: Changing C Code

    Originally posted by Programmer
    Hi Can anyone change this code to a different code? but it should do the same thing
    im also attaching the input file with it data.txt


    Thanks in Advance

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

    int arraywidth = 0, arrayheight = -1, uniquesets, unioncalls=0,
    recursivefindcalls=0;

    struct DisjSet {
    int sets;
    char data;
    };

    //function prototypes
    void SetUnion(DisjSet *, int, int);
    int Find(DisjSet *, int);
    void Merge ( DisjSet **, DisjSet **, int , int , int );
    void MergeSort ( DisjSet **, int );
    void MSort ( DisjSet **, DisjSet **, int, int);

    void main ()
    {
    FILE *fil;
    fil = fopen ("data.txt", "r");

    char temp[200];
    while (fgets(temp, 200, fil)) {
    if (arrayheight == -1) arraywidth=strlen(temp)-2;
    arrayheight++;
    }

    DisjSet *MySet = (DisjSet *) malloc( sizeof(struct DisjSet) * arraywidth *
    arrayheight);
    uniquesets = arraywidth*arrayheight;
    fclose(fil);

    fil = fopen ("data.txt", "r");
    char ch;
    int i, j, vl=0;
    for ( j=0; j<arrayheight; j++)
    for ( i=0; i<arraywidth; i++)
    {
    ch = fgetc(fil);
    while ((ch<'A') || (ch>'z')) ch=fgetc(fil);
    MySet[vl].data = ch;
    MySet[vl++].sets = 0;
    }
    fclose(fil);

    vl=0;
    for ( j=0; j<arrayheight; j++)
    for ( i=0; i<arraywidth; i++, vl++)
    {
    if (i>0)
    if (MySet[vl - 1].data == MySet[vl].data)
    SetUnion(MySet, vl, Find(MySet, vl - 1) );
    if (j>0)
    if (MySet[vl - arraywidth].data == MySet[vl].data)
    SetUnion(MySet, Find(MySet, vl), Find(MySet, vl - arraywidth) );
    }

    DisjSet **Rep = (DisjSet **) malloc( uniquesets * sizeof(DisjSet *) );

    vl = arraywidth*arrayheight;
    j=0;
    for ( i=0; i<vl; i++) {
    MySet[ Find(MySet, i) ].sets--;
    if (MySet[i].sets <= 0)
    Rep[j++] = &MySet[i];
    }

    MergeSort (Rep, uniquesets);

    printf(" There are %d sets (connected components) \n", uniquesets);
    printf(" SetUnion was called %d times but unions were performed only %d
    times.\n", unioncalls, arraywidth*arrayheight - uniquesets);
    printf(" (To verify) Total elements in Report sets: %d \n Times Find(...)
    called : %d\n", -vl, recursivefindcalls);
    vl=0;
    for (i=0; i<uniquesets; i++) {
    printf ("%3d. Type: %c Num elements: %d \n", i+1, Rep[i]->data,
    -Rep[i]->sets);
    vl += Rep[i]->sets;
    }

    free (Rep);
    free (MySet);
    }

    void SetUnion(DisjSet *S, int root1, int root2)
    {
    unioncalls++;
    if ( S[root1].sets > S[root2].sets )
    S[root1].sets = root2;
    else
    {
    if ( S[root1].sets == S[root2].sets )
    S[root1].sets--;
    S[root2].sets = root1;
    }
    uniquesets--;
    }

    int Find(DisjSet *S, int num)
    {
    recursivefindcalls++;
    if (S[num].sets <= 0)
    return num;
    else
    return S[num].sets = Find(S, S[num].sets);
    }

    void Merge ( DisjSet *A[], DisjSet *TmpArray[], int Lpos, int Rpos, int RightEnd
    )
    {
    int i, LeftEnd, NumElements, TmpPos;

    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;

    while ( Lpos <= LeftEnd && Rpos <= RightEnd )
    if ( A[Lpos]->sets >= A[Rpos]->sets )
    TmpArray[ TmpPos++ ] = A[Lpos++];
    else
    TmpArray[ TmpPos++ ] = A[Rpos++];

    while (Lpos <= LeftEnd )
    TmpArray [ TmpPos++ ] = A[Lpos++];
    while (Rpos <= RightEnd )
    TmpArray [ TmpPos++ ] = A[Rpos++];

    for ( i=0; i<NumElements; i++, RightEnd--)
    A[RightEnd] = TmpArray[ RightEnd ];
    }

    void MSort ( DisjSet *A[], DisjSet *TmpArray[], int Left, int Right)
    {
    int Center;
    if (Left < Right)
    {
    Center = (Left + Right)/2;
    MSort ( A, TmpArray, Left, Center);
    MSort ( A, TmpArray, Center + 1, Right);
    Merge ( A, TmpArray, Left, Center + 1, Right);
    }
    }

    void MergeSort ( DisjSet *A[], int N)
    {
    DisjSet **TmpArray;

    TmpArray = (DisjSet **) malloc( N * sizeof( DisjSet *));
    if (TmpArray)
    {
    MSort (A, TmpArray, 0, N-1);
    free(TmpArray);
    }
    else
    printf (" ERROR: Cannot sort. No more memory.\n");
    }
    Attached Files Attached Files
    Deep

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •