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.

 
Go Back  dBforums > Data Access, Manipulation & Batch Languages > Delphi, C etc > Changing C Code

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old 11-27-02, 15:53
Programmer Programmer is offline
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
Reply With Quote
  #2 (permalink)  
Old 11-27-02, 15:56
Programmer Programmer is offline
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");
}
Attached Files
File Type: txt data.txt (1.0 KB, 77 views)
__________________
Deep
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On