| |
|
If this is your first visit, be sure to check out the FAQ by clicking the link above.
You may have to register before you can post: click the register link above to proceed.
To start viewing messages, select the forum that you want to visit from the selection below.
|
 |

11-27-02, 15:53
|
|
Registered User
|
|
Join Date: Nov 2002
Posts: 50
|
|
|
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
|
|

11-27-02, 15:56
|
|
Registered User
|
|
Join Date: Nov 2002
Posts: 50
|
|
|
Re: Changing C Code
Quote:
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");
}
|
__________________
Deep
|
|
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|