[C] coda

[giannimesa]

Ciao a tutti, sto lavorando ad un progetto di un simulatore che necessita di una struttura come la Coda con priorità.
L'idea innanzitutto è di crearmi una Linked List e poi eventualmente affiancarla ad una struttura tipo Heap.
Sto facendo delle prove nella realizzazione di questa "Linked list" semplicemente creando diversi elementi collegando e stampando su console per ogni elemento:

Identificativo Elemento, Identificativo elemento precedente, Identificativo elemento successivo.

Ogni elemento della coda ha all'interno un elemento "job".
Il problema è che nel momento in cui vado a stampare l'elemento precedente o successivo con l'istruzione:

printf("PREC = %d , SUCC = %d \n", p->prev->jobElement.idJob, p->next->jobElement.idJob);

l'esecuzione di questa istruzione e in particolare il fatto di accedere agli elementi "jobElement" mi blocca inaspettatamente il programma (uso eclipse) senza alcun messaggio di errore (almeno un ubuntu).

Ecco i file:

FILE JOB.H

typedef struct job{
int idJob;
int priority;
int releaseTime;
int exeTime;
int endTime; // variable used only by periodic jobs
int numProc;
int processorOwner;
}job;

FILE QUEUEELEMENT.H

#include "job.h"
typedef struct queueElement{
job jobElement;
struct queueElement* next;
struct queueElement* prev;
}queueElement;

FILE MAIN.C

#include "job.h"
#include "queueElement.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <malloc.h>

int main(){
int i;
printf("simulazione di coda");
queueElement* p;
queueElement* temp;
p=(queueElement *)malloc(sizeof(queueElement));
p->jobElement.idJob=0;
for(i =10; i>0; i--){
p->next = (queueElement *)malloc(sizeof(queueElement));
temp = p->next;
temp->jobElement.idJob=i;
printf("inserito elemento %d ",p->jobElement.idJob);
if(i<10){
printf("PREC = %d , SUCC = %d \n", p->prev->jobElement.idJob, p->next->jobElement.idJob);
}
p=temp;
}
}

Chi mi riesce a dare una mano? Grazie mille a tutti!

[CaMbA]

// ATTENTO: job.h è già stato incluso in queueElement.h
//#include "job.h"
#include "queueElement.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <malloc.h>

int main(){
int i;
printf("simulazione di coda");
queueElement* p;
queueElement* temp;
p=(queueElement *)malloc(sizeof(queueElement));
p->jobElement.idJob=0;
for(i =10; i>0; i--){
p->next = (queueElement *)malloc(sizeof(queueElement));
temp = p->next;
// ti mancava questo
temp->prev = p;
temp->jobElement.idJob=i;
printf("inserito elemento %d ",p->jobElement.idJob);
if(i<10){
printf("PREC = %d , SUCC = %d \n", p->prev->jobElement.idJob, p->next->jobElement.idJob);
}
p=temp;
}
}

In pratica dimenticavi di assegnare il campo prev di temp.

Ciao!

[giannimesa]

ora provo a vedere, grazie mille!! :-)

[giannimesa]

Ora funziona almeno il codice scritto fin'ora, grazie mille!
Però nel momento in cui ad esempio voglio andarmi a stampare la situazione della coda con un ciclo for mi da lo stesso problema:


for(i=10; i>0;i--){
printf("ELEMENTO = %d , PRECEDENTE = %d , SUCCESSIVO = %d \n", p->jobElement.idJob, p->prev->jobElement.idJob, p->next->jobElement.idJob);
p = p->prev;
}

che sbaglio?

[Kenger]

La butto lì. Stai partendo dall'ultimo elemento e stai cercando di accedere ad un campo di next, che non esiste.

[CaMbA]

La butto lì. Stai partendo dall'ultimo elemento e stai cercando di accedere ad un campo di next, che non esiste.
Ed è esattamente così.
Ti consiglio di impostare a NULL la memoria che non allochi, così quando vai a scorrere la coda puoi effettuare dei controlli sul valore del puntatore e regolarti di conseguenza.

[cionci]

Per creare una coda non serve una lista doppiamente linkata, ma basta una lista singolarmente linkata. Però bisogna mantere sia un puntatore alla testa che uno alla coda.

[giannimesa]

grazie a tutti ragazzi per i consigli! Ho fatto tutto e ora funziona ... bene sembra. Ora il primo elemento ha come prev = NULL e l'ultimo ha come next = NULL. Ioltre ho aggiornato il tutto creandomi una struttura di tipo queue che posto qui:

typedef struct queue{
queueElement* first;
queueElement* last;
queueElement* pointer;
int numberOfElements;

}queue;

queue* createQueue();
queueElement* deleteLast(queue* q);
queueElement* insertElement(queue* q, queueElement* J);
queueElement* deleteElement(queue* q, job* J);
queueElement* findElement(queue* q, queueElement F);
queueElement* findJob(queue* q, job* J);
void deleteQueue(queue* q);
int getJob(queueElement* e);
queueElement* findMinPrio(queue* q);
queueElement* findMaxPrio(queue* q);
void swapElements(queue* q, queueElement* s1, queueElement* s2);
queue* prioritySort(queue* q);
void printQueue(queue* q);


@cionci
Lo so che servirebbe solo una lista singolarmente linkata, non sono sceso in dettagli sulle specifiche, ma mi serve per ogni elemento della lista conoscere successore e predecessore, per questo ho optato ad una doppiamente connessa.


Vi sottopongo ad un altro problema a cui per ora non riesco a trovare soluzione, forse sono stanco.
Ho provato a crearmi un metodo che mi scambia due elementi della coda doppiamente linkata, ovviamente mantenendo integra la coda.
Dai test che effettuo qualcosa sembra non andare, e ovviamente C non aiuta in debug... :-\
Provo a postar il codice della funzione, magari sarà qualche macro svista!


void swapElements(queue* q, queueElement* s1, queueElement* s2){
if(s1!=s2){
queueElement* prev;
queueElement* next;
//save s1 pointers
next=s1->next;
prev=s1->prev;
//update new s1 location
s1->next=s2->next;
s1->prev=s2->prev;
if(s2->prev!=NULL)
s2->prev->next=s1;
else q->first=s1;
if(s2->next!=NULL)
s2->next->prev=s1;
else q->last=s1;
//update new s2 location
s2->next=next;
s2->prev=prev;
if(prev!=NULL)
prev->next=s2;
else q->first=s2;
if(next!= NULL)
next->prev=s2;
else q->last=s2;
}
}


grazie mille ancora.

P.S.
ovviamente il campo "first" dell'elemento coda è il primo elemento e il campo "last" è l'ultimo.

[giannimesa]

up... :-\

[cionci]

Parti da questo ragionamento. Per lo scambio di due elementi puoi:
- scambiare le informazioni
- scambiare tutti i puntatori
Se le informazioni sono piccole, scambiare le informazioni è più semplice ;) E nel tuo caso mi sembra la cosa più semplice.