An error occurred while loading the file. Please try again.
-
Abdul-Malik Elmurzaev authored25fe2ce8
relations.c 12.63 KiB
// relations.c : definit le point d'entree pour l'application .
//
typedef int bool;
#define false 0
#define true -1
#include "stdlib.h"
#include "memory.h"
#include "stdio.h"
#include "string.h"
////////////////////////////////////////
// Exercice 1: Classement des Relations
typedef enum{
FRERE = 2, COUSIN, PARENT, ONCLE, EPOUX, AMI, VIT, CONNAIT,
CHEF, COLLEGUE, LOCATAIRE, TRAVAILLE, PROPRIETAIRE, SITUE, DECOUVERT
}rtype;
bool est_lien_parente(rtype id){
return (id == FRERE || id == COUSIN || id == PARENT || id == ONCLE);
}
bool est_lien_professionel(rtype id){
return (id == CHEF || id == COLLEGUE);
}
bool est_lien_connaissance(rtype id){
return (id == EPOUX || id == AMI || id == CONNAIT || id == VIT);
}
static char* RelationsTable[] = {
[2] = "frère ou soeur de", [3] = "cousin ou cousine de", [4] = "père ou mère",
[5] = "oncle ou tante de", [6] = "époux ou épouse de", [7] = "ami de",
[8] = "vit avec", [9] = "connait", [10] = "supérieur de",
[11] = "collègue de", [12] = "locataire de", [13] = "travaille à",
[14] = "propriétaire de", [15] = "situé à", [16] = "découvert à"
};
// PRE CONDITION: id > 1
char* toStringRelation(rtype id){
return RelationsTable[id];
}
////////////////////////////////////////
// Exercice 2: Liste de pointeurs
typedef struct s_node{
void *val; // pointeur vers objet quelconque
struct s_node *suiv;
}*listeg;
listeg listegnouv(){
return NULL;
}
listeg adjtete(listeg lst, void *x){
listeg new = malloc(sizeof(struct s_node));
if (new == NULL) {
fprintf(stderr, " malloc == NULL fonction adjtete(lst,x) \n");
exit(EXIT_FAILURE);
}
new->val = x;
new->suiv = lst;
return new;
}
listeg adjqueue(listeg lst, void *x){
listeg new = malloc(sizeof(struct s_node));
if (new == NULL) {
fprintf(stderr, " malloc == NULL fonction adjqueue(lst,x) \n");
exit(EXIT_FAILURE);
}
new->val = x; new->suiv = NULL;
if( lst != NULL ){
listeg copy = lst;
while(copy->suiv != NULL){
copy = copy->suiv;
}
copy->suiv = new;
return lst;
}else
return new;
}
listeg suptete(listeg lst){
listeg deuxieme = lst->suiv;
free(lst);
return deuxieme;
}
void *tete(listeg lst){
return lst->val;
}
int longueur(listeg lst){
int res = 0;
if( lst == NULL )
return res;
res++;
listeg copy = lst;
while(copy->suiv != NULL){
copy = copy->suiv;
res++;
}
return res;
}
bool estvide(listeg lst){
return lst == NULL;
}
void detruire(listeg lst){
if( estvide(lst) )
return;
if(lst->suiv == NULL){
free(lst);
return;
}
listeg copy = lst;
while(copy != NULL){
copy = copy->suiv;
free(lst);
lst = copy;
}
}
listeg rech(listeg lst, void *x, int(*comp)(void *, void *)){
listeg copy = lst;
while(copy != NULL){
if( comp(x, copy->val) ){
return lst;
}else{
copy = copy->suiv;
}
}
return NULL;
}
////////////////////////////////////////
// Exercice 3: Construction du graphe
#define LONG_NOM_MAX 64
typedef enum{
PERSONNE=1, OBJET, ADRESSE, VILLE
}etype;
typedef struct s_entite{
char nom[LONG_NOM_MAX]; // le nom de l entite p.ex " Peugeot 106 " etype ident; // l identifiant associe, p.ex OBJET
}*Entite;
//3.1 les structures de donnees
typedef struct s_sommet{
struct s_node* larcs;
Entite x;
}*Sommet;
typedef struct s_arc{
rtype t;
struct s_entite* x;
}*Arc;
typedef struct s_relations{
listeg listDeRelations;
}*Relations;
//3.2 les constructeurs
Entite creerEntite(char *s, etype e){
Entite newEntity = malloc(sizeof(struct s_entite));
if (newEntity == NULL) {
fprintf(stderr, " malloc == NULL fonction creerEntite(s,e) \n");
exit(EXIT_FAILURE);
}
strcpy(newEntity->nom, s);
newEntity->ident = e;
return newEntity;
}
Sommet nouvSommet(Entite e){
if(e == NULL){
fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvSommet(e) \n");
exit(EXIT_FAILURE);
}
Sommet s = malloc(sizeof(struct s_sommet));
if (s == NULL) {
fprintf(stderr, " malloc == NULL fonction nouvSommet(e) \n");
exit(EXIT_FAILURE);
}
s->x = e;
s->larcs = listegnouv();
return s;
}
Arc nouvArc(Entite e, rtype type){
if(e == NULL){
fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvArc(e,type) \n");
exit(EXIT_FAILURE);
}
Arc bow = malloc(sizeof(struct s_arc));
if (bow == NULL) {
fprintf(stderr, " malloc == NULL fonction nouvArc(e,type) \n");
exit(EXIT_FAILURE);
}
bow->t = type;
bow->x = e;
return bow;
}
void relationInit(Relations *g){
*g = malloc(sizeof(struct s_relations));
if(*g == NULL){
fprintf(stderr, " malloc == NULL function relationInit(*g) \n");
exit(EXIT_FAILURE);
}
(*g)->listDeRelations = listegnouv();
}
void relationFree(Relations *g){
// il faut free g, il faut aussi free g->listeDeRelations (qui est un listeg),
// 999 et il faut free g->listeDeRelations->val (qui est un sommet),
// 999 et il faut free g->listeDeRelations->val->x (qui est une entite),
// 999 et il faut free g->listeDeRelations->val->larcs (qui est un listeg),
// 999 et il faut free tous les g->listeDeRelations->val->larcs->val (qui sont des arcs), // 999 et il faut free tous les g->listeDeRelations->val->larcs->val->x (qui sont des entites)
// commençont par tous les g->listeDeRelations->val->larcs->val->x et du val qui va avec
free( ((Sommet)((*g)->listDeRelations->val))->x );
listeg tete = (*g)->listDeRelations;
printf("check 0 \n");
while( tete != NULL ){
listeg LarcsDuSommet = ((Sommet)(tete->val))->larcs;
listeg LarcTete = LarcsDuSommet;
while( LarcsDuSommet != NULL ){
printf("check 1 \n");
free( ((Arc)( LarcsDuSommet->val ))->x );
printf("check 2 \n");
free( ((Arc)( LarcsDuSommet->val )) );
LarcsDuSommet = LarcsDuSommet->suiv;
}
printf("check 3 \n");
detruire(LarcTete);
printf("check 4 \n");
free( ((Sommet)(tete->val)) );
printf("check 5 \n");
tete = tete->suiv;
}
detruire( (*g)->listDeRelations );
free(*g);
}
//3.3 les comparaisons
int compEntite(void *e, void *string){
if (e == NULL || string == NULL) {
return 0;
}
if( strcmp( ((Entite)e)->nom, string ) == 0 ){
return 1;
}
return 0;
}
int compSommet(void *s, void *string){
if (s == NULL || string == NULL) {
return 0;
}
if( strcmp( ((Sommet)s)->x->nom, string ) == 0 ){
return 1;
}
return 0;
}
int compArc(void *a, void *string){
if (a == NULL || string == NULL) {
return 0;
}
if( strcmp( ((Arc)a)->x->nom, string ) == 0 ){
return 1;
}
return 0;
}
//3.4 ajout d'entites et de relations
void adjEntite(Relations g, char *nom, etype t){
g->listDeRelations = adjqueue(g->listDeRelations, nouvSommet(creerEntite(nom, t)));
}
// PRE CONDITION: id doit etre coherent avec les types des sommets correspondants a x et y
// p.ex si x est de type OBJET, id ne peut pas etre une relation de parente
// PRE CONDITION: strcmp(nom1,nom2)!=0
void adjRelation(Relations g, char *nom1, char *nom2, rtype id){
Sommet sommet1 = NULL;
Sommet sommet2 = NULL;
Entite deuxiemeEntite = NULL;
listeg copy = g->listDeRelations;
while( copy != NULL ){
if( strcmp(((Sommet)(copy->val))->x->nom, nom1)==0 ){ sommet1 = (Sommet)(copy->val);
}
if( strcmp(((Sommet)(copy->val))->x->nom, nom2)==0 ){
sommet2 = (Sommet)(copy->val);
}
copy = copy->suiv;
}
sommet1->larcs = adjqueue(sommet1->larcs, (Arc)nouvArc(sommet2->x, id));
}
////////////////////////////////////////
// Exercice 4: Explorer les relations entre personnes
// 4.1 listes de relations
listeg en_relation(Relations g, char *x){
return NULL;
}
listeg chemin2(Relations g, char *x, char *y){
return NULL;
}
// 4.2 verifier un lien de parente
// PRE CONDITION: strcmp(x,y)!=0
bool ont_lien_parente(Relations g, char *x, char *y){
return false;
}
// 4.3 tester connaissances
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent(Relations g, char *x, char *y){
return false;
}
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_proba(Relations g, char *x, char *y){
return false;
}
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_peutetre(Relations g, char *x, char *y){
return false;
}
////////////////////////////////////////
// Exercice 5: Affichages
static char* etype_string[] = { [PERSONNE] = "personne", [OBJET] = "objet", [ADRESSE] = "adresse",
[VILLE] = "ville"};
void affichelg(listeg l, void(*aff)(void *)){
while( l != NULL ){
aff(l->val);
l = l->suiv;
}
}
void afficheEntite(void *x){
printf("%s :%s\n", ((Entite)x)->nom, etype_string[ ((Entite)x)->ident] );
}
void afficheArc(void *x){
printf(" --%s-->", toStringRelation(((Arc)x)->t));
afficheEntite( ((Arc)(x))->x );
}
////////////////////////////////////////
// Exercice 6: Parcours
void affiche_degre_relations(Relations r, char *x){
}
int main(){
int i,j;
printf("test toStringRelation(16) == %s \n", toStringRelation(16));
printf("test est_lien_parente : %d %d %d \n",est_lien_parente(COUSIN),est_lien_parente(LOCATAIRE),
est_lien_parente(EPOUX));
printf("test est_lien_professionel : %d %d %d \n", est_lien_professionel(LOCATAIRE),
est_lien_professionel(CHEF), est_lien_professionel(COLLEGUE));
printf("test est_lien_connaissance : %d %d %d \n", est_lien_connaissance(AMI),
est_lien_connaissance(CONNAIT), est_lien_connaissance(COLLEGUE));
listeg liste = listegnouv();
int x5 = 5, x4 = 4, x19 = 19, x3 = 3, x33 = 33;
int *px5, *px4, *px19, *px3, *px33;
px5 = &x5; px4 = &x4; px19 = &x19; px3 = &x3; px33 = &x33;
int x0 = 0; int* px0 = &x0;
liste = adjqueue(liste, &px5);
liste = adjtete(liste, &px4);
liste = adjqueue(liste, &px19);
liste = adjtete(liste, &px3);
liste = adjqueue(liste, &px33);
liste = adjtete(liste, &px0);
liste = suptete(liste);
listeg copy = liste;
for(int i=0; i<4; i++){
printf("liste->val == %d \n", **(int**)copy->val);
copy = copy->suiv;
}
printf("tete(liste) == %d \n", **(int**)tete(liste));
detruire(liste);
Relations r; relationInit(&r);
// ajouter les entites de l'exemple
char *tabe[] ={"KARL","LUDOVIC","CELINE","CHLOE","GILDAS","CEDRIC","SEVERINE",
"PEUGEOT 106" ,"1, RUE DE LA RUE","STRASBOURG" };
for (i = 0; i < 7; i++)
adjEntite(r, tabe[i], PERSONNE);
adjEntite(r, tabe[7], OBJET);
adjEntite(r, tabe[8], ADRESSE);
adjEntite(r, tabe[9], VILLE);
// ajouter les relations de l'exemple
adjRelation(r, tabe[0], tabe[1], FRERE);
adjRelation(r, tabe[0], tabe[2], AMI);
adjRelation(r, tabe[0], tabe[3], CONNAIT);
adjRelation(r, tabe[0], tabe[5], COUSIN);
adjRelation(r, tabe[0], tabe[7], PROPRIETAIRE);
adjRelation(r, tabe[0], tabe[8], PROPRIETAIRE);
adjRelation(r, tabe[3], tabe[4], VIT);
adjRelation(r, tabe[5], tabe[6], EPOUX);
adjRelation(r, tabe[5], tabe[8], LOCATAIRE);
adjRelation(r, tabe[7], tabe[8], DECOUVERT);
adjRelation(r, tabe[8], tabe[9], SITUE);
affichelg( ((Sommet)(r->listDeRelations->val))->larcs, afficheArc );
printf("\n %s \n", ((Arc)(((Sommet)(r->listDeRelations->val))->larcs->val))->x->nom );
//relationFree(&r);
return 0;
// explorer les relations
printf("%s est en relation avec:\n", tabe[0]);
affichelg(en_relation(r, tabe[0]),afficheArc);
printf("\n");
for (i = 0; i < 7; i++) for (j = i + 1; j < 10; j++)
{
printf("<%s> et <%s> ont les relations communes:\n", tabe[i], tabe[j]);
listeg ch = chemin2(r, tabe[i], tabe[j]);
affichelg(ch, afficheEntite);
printf("\n"); detruire(ch);
}
printf("\n\n");
for (i = 0; i < 10; i++) for (j = i + 1; j < 10; j++)
{
printf("<%s> et <%s> ont lien de parente: %s\n",
tabe[i], tabe[j], ont_lien_parente(r, tabe[i], tabe[j]) ? "vrai" : "faux");
}
printf("\n");
for (i = 0; i < 7; i++)
{
for (j = i + 1; j < 7; j++)
{
printf("<%s> et <%s> se connaissent: %s\n",
tabe[i], tabe[j], se_connaissent(r, tabe[i], tabe[j]) ? "vrai" : "faux");
printf("<%s> et <%s> se connaissent tres probablement: %s\n",
tabe[i], tabe[j], se_connaissent_proba(r, tabe[i], tabe[j]) ? "vrai" : "faux");
printf("<%s> et <%s> se connaissent peut etre: %s\n",
tabe[i], tabe[j], se_connaissent_peutetre(r, tabe[i], tabe[j]) ? "vrai" : "faux");
}
printf("\n");
}
affiche_degre_relations(r, tabe[3]);
relationFree(&r);
printf("\nPRESS RETURN\n");
char buff[64]; fscanf(stdin, "%s", buff);
return 0;
}