[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]

Originariamente inviato da Kenger

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.