C Code

File Main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include “list.c”

void main()
{
int i,megethos,id,num_arx,*arx,*temp,j,vrethike,k,messages,p,q,random_num,allagi;
char state[5];
int **link;
typos_deikti prodeiktis,arxi;
typos_deikti *riza;

        printf(“Doste to megethos tou daktiliou:\n”);
scanf(“%d”,&megethos);

        riza=malloc(megethos*sizeof(typos_deikti));

        //—————-Desmeusi pinaka 2-diastaseon gia ta links
link = (int **) malloc(megethos*sizeof(int));
for(i=0;i < megethos;i++)
{
link[i] = malloc(megethos*sizeof(int));
}
//——————-Arxikopoiisi tou pinaka ton links me 0
//—————— link[p][q] = epomenos = 1
//——————-link[p][q] = proigoumenos = 0
for(i=0;i < megethos;i++)
{
for(j=0;j < megethos;j++)
{
link[i][j] = 0;
}
}

        dimiourgia(riza);
prodeiktis=NULL;

        sprintf(state,”recei”);
id = 1;
eisagogi(riza,state,id,prodeiktis);
prodeiktis = *riza;

        for(i=0;i<megethos-1;i++)
{
id++;
eisagogi(riza,state,id,prodeiktis);
proxorise(&prodeiktis);
}

        printf(“\nEpilextikan tixaia oi parakato komvoi senders:\n”);
num_arx=fmod(rand(),megethos);
arx=malloc(num_arx*sizeof(int));
temp=malloc(num_arx*sizeof(int));
for(i=0;i<num_arx;i++)
{
arx[i] = fmod(rand(),megethos);
for(j=0;j<num_arx;j++)
{
if(temp[j]==arx[i])
{
vrethike=1;
break;
}
else
{
vrethike=0;
}
}

            if(vrethike==0)
{
temp[i] = arx[i];
printf(“%d\n”,arx[i]);

                prodeiktis = *riza;
for(k=0;k<arx[i];k++)
{
proxorise(&prodeiktis);
}
sprintf(prodeiktis->state,”sende”);

                //—————-Enimerosi ton links gia tin kateuthnisi ton senders——————//
if(arx[i]!=0 && arx[i]!=megethos-1)
{
p=arx[i];
q=arx[i]+1;
random_num = fmod(rand(),2);
if (random_num ==0)
{
link[p][q] = 1;
}
else
{
link[p][q-2] = 1;
}
}
else if(arx[i]==0)
{
p=0;
q=1;
link[p][q] = 1;
}
else
{
p=megethos-1;
q=0;
link[p][q] = 1;
}

            }
else
{
i–;
}
}

        //————–SET SUCC-PRED TO RECEIVERS————//
prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
if(strcmp(prodeiktis->state,”recei”)==0)
{
//Receiver = Node 0
if(i==0)
{
link[i][1]=1;
link[i][megethos-1]=0;
}
//Receiver = Last Node
if(i==megethos-1)
{
link[i][0]=1;
link[i][i-1]=0;
}
else
{
link[i][i+1]=1;
link[i][i-1]=0;
}
}
proxorise(&prodeiktis);
}

        //———Tipose arxiki katastasi———-//
printf(“Katastasi Komvon Daktiliou\n”);
printf(“————————–\n”);
prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
printf(“Komvos %d : “,i);
printf(“ID = %d “,node_id(prodeiktis));
printf(“State = %s\n”,periexomeno(prodeiktis));
proxorise(&prodeiktis);
}

        //———-Tipose ta links—————–//
printf(“Pinakas Zeukseon Succ kai Pred metaksi komvon\n”);
printf(“———————————————\n”);
for(i=0;i < megethos;i++)
{
for(j=0;j < megethos;j++)
{
printf(“%d “,link[i][j]);
}
printf(“\n”);
}
printf(“Kateuthinseis zeukseon metaksi komvon\n”);
printf(“————————————-\n”);
for(i=0;i < megethos;i++)
{
for(j=0;j < megethos;j++)
{
if(link[i][j] == 1)
{
printf(“%d->%d\n”,i,j);
}
}
}

        //———–Ring Orientation—————-//
allagi =1;
messages=0;
prodeiktis = *riza;
while(allagi==1)
{
allagi=0;

            for(i=0;i<megethos-2;i++)
{
////////Kainouria fasi – allagi katastaseon////////

                if (prodeiktis->temp == 1)
{
sprintf(prodeiktis->state,”sende”);
}
if (prodeiktis->temp == 2)
{
sprintf(prodeiktis->state,”recei”);
}
if (prodeiktis->temp == 3)
{
sprintf(prodeiktis->state,”inter”);
}

                ///////////////
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”inter”)==0) && link[i][i+1]==1)
{
prodeiktis->epomenos->temp = 2;
link[i+1][i+2]=1;
link[i+1][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”recei”)==0) && (link[i][i+1]==1) && (link[i+1][i]==0))
{
prodeiktis->temp = 3;
prodeiktis->epomenos->temp =1;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”sende”)==0) && (link[i][i+1]==1) && (link[i+1][i]==1))
{
prodeiktis->epomenos->temp =2;
link[i+1][i+2]=1;
link[i+1][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”inter”)==0) && (strcmp(prodeiktis->epomenos->state,”inter”)==0) && (link[i][i+1]==1) && (link[i+1][i]==1))
{
prodeiktis->temp =1;
allagi=1;
}
proxorise(&prodeiktis);
}

            //——————-Kikliki Lista -> Proteleutaios komvos——————//
if (prodeiktis->temp == 1)
{
sprintf(prodeiktis->state,”sende”);
}
if (prodeiktis->temp == 2)
{
sprintf(prodeiktis->state,”recei”);
}
if (prodeiktis->temp == 3)
{
sprintf(prodeiktis->state,”inter”);
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”inter”)==0) && link[i][i+1]==1)
{
prodeiktis->epomenos->temp = 2;
link[i+1][0]=1; //——-
link[i+1][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”recei”)==0) && (link[i][i+1]==1) && (link[i+1][i]==0))
{
prodeiktis->temp = 3;
prodeiktis->epomenos->temp =1;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(prodeiktis->epomenos->state,”sende”)==0) && (link[i][i+1]==1) && (link[i+1][i]==1))
{
prodeiktis->epomenos->temp =2;
link[i+1][0]=1; //——
link[i+1][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”inter”)==0) && (strcmp(prodeiktis->epomenos->state,”inter”)==0) && (link[i][i+1]==1) && (link[i+1][i]==1))
{
prodeiktis->temp =1;
allagi=1;
}
proxorise(&prodeiktis);

                //——————-Kikliki Lista -> Teleutaios komvos——————//
arxi = *riza;

                if (prodeiktis->temp == 1)
{
sprintf(prodeiktis->state,”sende”);
}
if (prodeiktis->temp == 2)
{
sprintf(prodeiktis->state,”recei”);
}
if (prodeiktis->temp == 3)
{
sprintf(prodeiktis->state,”inter”);
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(arxi->state,”inter”)==0) && link[i][0]==1)
{
arxi->temp = 2;
link[0][1]=1;
link[0][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(arxi->state,”recei”)==0) && (link[i][0]==1) && (link[0][i]==0))
{
prodeiktis->temp = 3;
arxi->temp =1;
allagi=1;
}
if((strcmp(prodeiktis->state,”sende”)==0) && (strcmp(arxi->state,”sende”)==0) && (link[i][0]==1) && (link[0][i]==1))
{
arxi->temp =2;
link[0][1]=1;
link[0][i]=0;
allagi=1;
}
if((strcmp(prodeiktis->state,”inter”)==0) && (strcmp(arxi->state,”inter”)==0) && (link[i][0]==1) && (link[0][i]==1))
{
prodeiktis->temp =1;
allagi=1;
}
prodeiktis = *riza;

        }

        //////////////////APOTELESMATA////////////////////////////
printf(“\n\n****************Apotelesmata*****************\n\n”);
printf(“Katastasi Komvon Daktiliou\n”);
printf(“————————–\n”);
prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
printf(“Komvos %d : “,i);
printf(“ID = %d “,node_id(prodeiktis));
printf(“State = %s\n”,periexomeno(prodeiktis));
proxorise(&prodeiktis);
}

        /////////Tipose ta links//////////////
printf(“Pinakas Zeukseon Succ kai Pred metaksi komvon\n”);
printf(“———————————————\n”);
for(i=0;i < megethos;i++)
{
for(j=0;j < megethos;j++)
{
printf(“%d “,link[i][j]);
}
printf(“\n”);
}
printf(“Kateuthinseis zeukseon metaksi komvon\n”);
printf(“————————————-\n”);
for(i=0;i < megethos;i++)
{
for(j=0;j < megethos;j++)
{
if(link[i][j] == 1)
{
printf(“%d->%d\n”,i,j);
}
}
}
//////////////////APOTELESMATA////////////////////////////
}

File List.c

/*************************************************************************
Αρχείο Υλoπoίησης    : list.c
Σκοπός                : Υλοποίηση με δείκτες ΑΤΔ, κυκλικά Συνδεδεμένη Λίστα
**************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef char   typos_stoixeiou;
typedef struct typos_komvou *typos_deikti;
typedef struct typos_komvou
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
};
typos_deikti lista;

void dimiourgia(typos_deikti *lista);
int keni(typos_deikti lista);
void proxorise(typos_deikti *p);
typos_stoixeiou *periexomeno(typos_deikti p);
void diagrafi(typos_deikti *lista, typos_deikti prodeiktis);

void eisagogi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id,typos_deikti prodeiktis);
void eisagogi_arxi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id);
void eisagogi_meta(typos_deikti prodeiktis,typos_stoixeiou *stoixeio,int id);

int node_id(typos_deikti p);
int send(int tok,typos_deikti p);

void dimiourgia(typos_deikti *lista)
{
/*
*    Πρo:         καμία
*    Μέτά:         Δημιoυργία κενής συνδεδεμένης λίστα
*/
*lista = NULL;
}

int keni(typos_deikti lista)
{
/*
*    Πρo:         Δημιoυργία λίστας
*    Μέτά:        επιστρέφει 1 αν η λίστα είναι κενή, διαφoρετικά 0
*/
return ( lista == NULL );
}

void proxorise(typos_deikti *p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        Ο δείκτης p δείχνει στον επόμενο κόμβο στην λίστα
*/
*p = (*p)->epomenos;
}

typos_stoixeiou *periexomeno(typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
return (p->state);
}

int node_id(typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
return (p->id);
}

int send(int tok,typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
if(p->id == tok)
{
sprintf(p->state,”leade”);
return 1;
}
p->temp = tok;

    return 0;

}

void eisagogi_meta(typos_deikti prodeiktis,typos_stoixeiou *stoixeio,int id)
{
/*
*    Πρo:         Δημιoυργία λίστα
*    Μέτά:         Ο κόμβος με τα δεδομένα stoixeio έχει εισαχθεί
*                μετά τον κόμβο που δείχνει ο prodeiktis
*/    int i;
typedef struct
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
}typos_komvou;
typos_deikti prosorinos; /*Δείχνει τον νέο κόμβο που πρόκειτε να εισαχθεί*/

    prosorinos = (typos_deikti)malloc(sizeof(typos_komvou));
if ( prosorinos == NULL )
{
fprintf(stderr,”Η μνήμη είναι γεμάτη\n”);
exit(-1);
}
for(i=0;i<5;i++)
prosorinos->state[i] = stoixeio[i];
prosorinos->state[i] = ‘\0’;
prosorinos->id = id;
prosorinos->tok = id;
prosorinos->temp = 0;
prosorinos->epomenos = prodeiktis->epomenos;
prodeiktis->epomenos = prosorinos;
}

void eisagogi_arxi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id)
{
/*
*    Πρo:         O δείκτης p δείχνει ττην αρχή της λίστας
*    Μέτά:         Ο κόμβος με τα δεδομένα stoixeio έχει εισαχθεί
*                πριν τον κόμβο που εδείχνει ο p, ο p δείχνει πλέον την νέα αρχή της λίστας
*/
int i;
typedef struct
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
}typos_komvou;
typos_deikti prosorinos; /*Δείχνει τον νέο κόμβο που πρόκειτε να εισαχθεί*/

    prosorinos = (typos_deikti)malloc(sizeof(typos_komvou));
if ( prosorinos == NULL )
{
fprintf(stderr,”Η μνήμη είναι γεμάτη\n”);
exit(-1);
}
for(i=0;i<5;i++)
prosorinos->state[i] = stoixeio[i];
prosorinos->state[i] = ‘\0’;
prosorinos->id = id;
prosorinos->tok = id;
prosorinos->temp = 0;
prosorinos->epomenos = *lista;
*lista = prosorinos;
}

void eisagogi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id,typos_deikti prodeiktis)
{
/*
*    Πρo:         Ο prodeiktis δείχνει ένα κόμβο στην λίστα ή είναι NULL
*    Μέτά:         Αν ο prodeiktis είναι NULL τοτε ο κόμβος με τα δεδομένα
*                stoixeio έχει εισαχθεί στην αρχή της λίστας αλλιώς ο εισάγεται μετά
*                τον κόμβο που δείχνει ο prodeiktis
*/
if (keni(prodeiktis)) /*εισαγωγή στην αρχή της λίστας*/
eisagogi_arxi(lista,stoixeio,id);
else
eisagogi_meta(prodeiktis,stoixeio,id);
}