View difference between Paste ID: Jznn60Wi and P1n1x4Ru

-#include <stdio.h>
+#include <stdio.h>
-#include <stdlib.h>
+#include <stdlib.h>
-//#include <time.h>
+//#include <time.h>
-#define DIM 100
+#define DIM 100
-#include "list.h"
+#include "list.h"
-
+
-
+
-/*Rappresentazione di liste con array */
+/*Rappresentazione di liste con array */
-typedef struct{
+typedef struct{
-  int key[DIM];
+  int key[DIM];
-  int next[DIM];
+  int next[DIM];
-  int prev[DIM];
+  int prev[DIM];
-} Spazio;
+} Spazio;
-
+
-/* Variabili globali*/
+/* Variabili globali*/
-List freeList;  /*Testa della free List che e' una lista DOPPIAMENTE concatenata*/
+List freeList;  /*Testa della free List che e' una lista DOPPIAMENTE concatenata*/
-Spazio space; /*Spazio utilizzato per memorizzare le liste*/
+Spazio space; /*Spazio utilizzato per memorizzare le liste*/
-
+
-
+
-/*Post: inizializza space in modo che tutti gli elementi siano nella lista libera. La testa della lista libera sara' 0 */
+/*Post: inizializza space in modo che tutti gli elementi siano nella lista libera. La testa della lista libera sara' 0 */
-void initFreelist(){
+void initFreelist(){
-	int i;
+	int i;
-	for(i=0;i<DIM;i++)space.prev[i]=(i-1);
+	for(i=0;i<DIM;i++){space.prev[i]=(i-1); space.key[i]=0; space.next[i]=(i+1);}
-	for(i=0;i<DIM;i++)space.next[i]=(i+1);
+	space.next[DIM-1]=-1; //indico ultimo elem.
-	space.next[DIM-1]=-1; //indico ultimo elem.
+	freeList=0;
-	freeList=0;
+}
 
-
+/*Post: restituisce un oggetto libero. Se lo spazio e' esaurito stampa un messaggio di errore  */
-/*Post: restituisce un oggetto libero. Se lo spazio e' esaurito stampa un messaggio di errore  */
+List allocateObject(){
-List allocateObject(){
+if(freeList>=0)
-	if(freeList<0){printf("Errore: spazio esaurito!"); return -2;}
+{
-	else return freeList;
+	int aux=freeList;
 	/*Ho ancora posizioni libere*/
-
+	if(space.next[freeList]!=-1)
-/* Post: restituisce il numero di elementi contenuti nella lista */
+		{
-int lunghezza(List l){
+			freeList=space.next[freeList];
-	int counter=0;
+			space.prev[freeList]=-1;
-	if(l<0)return 0;
+			space.next[aux]=-1;
-	if(space.next[l]<0)return 1;
+		}
-	else return 1+lunghezza(space.next[l]);
+	else
 		{
-
+		/*Sono sull'ultima posizione libera*/
-
+			freeList=-1;
-/*Post: stampa il contenuto della lista. Deve essere una funzione RICORSIVA */
+	}
-void stampa(List l){
+	return aux;
-	if(l<0){printf("LISTA VUOTA."); return;}
+}
-	printf("%d ",space.key[l]);
+else
-	if(space.next[l]<0)printf(".");
+	{
-	else stampa(space.next[l]);
+		printf("\nSpazio esaurito\n");
 		return freeList;
-
+	}
-
+}
-
+
-/*Post: legge una sequenza di interi inseriti dall'utente e restituisce una lista contenente tale sequenza*/
+
-List caricamento(){
+
-
+/* Post: restituisce il numero di elementi contenuti nella lista */
-	int i,n,temp;
+int lunghezza(List l){
-	List l,pointer;
+	int counter=0;
-	l=allocateObject();
+	if(l<0)return 0;
-	pointer=l;
+	if(space.next[l]<0)return 1;
-	printf("Lunghezza Lista: ");
+	else return 1+lunghezza(space.next[l]);
-	scanf("%d",&i);
+}
-
+
-	if(i>=lunghezza(l)){printf("Non c'e' spazio a sufficienza! ERRORE!\n"); return -2;}
+
-	if(i==0)return -1; //lista vuota
+/*Post: stampa il contenuto della lista. Deve essere una funzione RICORSIVA */
-	if(i<0){printf("Valore ERRATO!\n"); return -2;}
+void stampa(List l){
-
+	if(l<0){printf("LISTA VUOTA."); return;}
-	space.prev[l]=-1;
+	printf("%d ",space.key[l]);
-
+	if(space.next[l]<0)printf(".");
-	//inserimento valori
+	else stampa(space.next[l]);
-	for (n=0;n<i;n++)
+}
-  {
+
-    printf ("Inserisci il valore #%d: ",n+1);
+/*Post: rende libero l'oggetto x  */
-    scanf ("%d",&(space.key[l]));
+void freeObject(List x){
-    temp=l;
+	int temp=x;
-    l=space.next[l];//l++
+	space.prev[x]=-1;
-  }
+	space.key[x]=0;
-  space.next[temp]=-1;
+	space.next[x]=freeList; /* lo butto in testa alla freelist */
-
+	space.prev[freeList]=x;
-  space.prev[l]=-1;
+	freeList=temp;
-  freeList=l;
+}
-
+
-return pointer;
+/*Post: dealloca gli elementi contenuti nella lista */
 void rimuovi(List l){
-
+	int temp;
-/* Stampa la situazione globale */
+	while(l>=0)
-void debug(){
+	{
-	int i,j;
+		temp=space.next[l];
-	int charperrow=8;
+		freeObject(l);
-	printf("freeList: %d\n",freeList);
+		l=temp;
-	for(i=0;i<DIM/charperrow;i++){
+	}
-		printf("N:\t");
+	l=-1;
-		for(j=0;j<charperrow;j++)printf("%d\t",space.next[i*charperrow+j]);
+	return;
-		printf("\nK:\t");
+}
-		for(j=0;j<charperrow;j++)printf("%d\t",space.key[i*charperrow+j]);
+
-		printf("\nP:\t");
+/*Post: legge una sequenza di interi inseriti dall'utente e restituisce una lista contenente tale sequenza*/
-		for(j=0;j<charperrow;j++)printf("%d\t",space.prev[i*charperrow+j]);
+List caricamento(){
-		printf("\n\n");
+
-	}
+	int temp,value,first,next;
-
+	List l, pointer;
 
-
+	temp=-1; first=1; value=1;/*valore positivo insignificante solo x entrare nel ciclo*/
-
+	printf("Caricamento nuova lista, inserisci 0 per terminare.\n");
-/*Post: rende libero l'oggetto x  */
+
-void freeObject(List x){
+	while(value){
-	int temp=x;
+		l=allocateObject();
-	space.prev[x]=-1;
+		printf("l vale %d\n",l);
-	while(space.next[x]>0)x=space.next[x];//scorro a fine lista x per attaccarci la freeList
+		printf("Inserisci valore: ");
-	space.next[x]=freeList;
+   	scanf("%d",&value);
-	space.prev[freeList]=x;
+		if(first){pointer=l;/* puntatore alla testa, NON AGGIORNARE */ first=0;
-	freeList=temp;
+			if(!value){freeObject(l); return -1; }
 		}
-
+
-
+   	space.next[l]=-1;
-/*Post: dealloca gli elementi contenuti nella lista */
+   	space.key[l]=value;
-void rimuovi(List l){
+   	space.prev[l]=temp;
-return;
+   	temp=l;
    }
-
+   temp=space.prev[l];//ultimo elemento
-
+   printf("temp vale=%d\n",temp);
-
+   freeObject(l);
-
+   value=-1;
-
+   //scorro all'indietro lista e assegno i next
-
+   while(temp>=0){
-/*Pre: Si assuma che space abbia m elementi, l sia una lista di n elementi e i rimanenti elementi di space (m -n) siano nella lista libera.
+   	space.next[temp]=value;
-  Post: sposta gli elementi in l in modo che occupino le posizioni 0, 1, ..., n-1 di space e aggiusta la lista libera in modo che essa resti corretta, occupando le posizioni di space n, n+1, ...., m - 1. La funzione restituisce la lista l con gli elementi nelle posizioni specificate.
+   	value=temp;
-  Il tempo di esecuzione della funzione e' theta(n) e deve utilizzare SOLO una quantita' costante di spazio extra. */
+   	temp=space.prev[temp];
-List compatifyList(List l){
+   }
-	//BOOOOOOH
+return pointer;
-	return -7;
+}
 
-
+/* Stampa la situazione globale */
-
+void debug(){
-
+	int i,j;
-
+	int charperrow=10;
-List caricaListaStronza(){
+	printf("Spazio Libero: %d (da %d in poi).\n",lunghezza(freeList),freeList);
-
+	for(i=0;i<DIM/charperrow;i++){
-	space.next[8]=17;
+		printf("N:\t");
-	space.key[8]=1;
+		for(j=0;j<charperrow;j++)printf("%d\t",space.next[i*charperrow+j]);
-	space.prev[8]=-1;
+		printf("\nK:\t");
-
+		for(j=0;j<charperrow;j++)printf("%d\t",space.key[i*charperrow+j]);
-	space.next[17]=1;
+		printf("\nP:\t");
-	space.key[17]=2;
+		for(j=0;j<charperrow;j++)printf("%d\t",space.prev[i*charperrow+j]);
-	space.prev[17]=8;
+		printf("\n\n");
-
+	}
-	space.next[1]=73;
+
-	space.key[1]=3;
+}
-	space.prev[1]=17;
+
-
+
-	space.next[73]=51;
+void auxcompat(List l, int pointerList, int pointerFree,int lunghezza){
-	space.key[73]=4;
+	int temp;
-	space.prev[73]=1;
+	if((pointerList<0)||(pointerFree<0))return;
-
+	else{
-	space.next[51]=50;
+		if(pointerFree>lunghezza){
-	space.key[51]=5;
+			auxcompat(l,pointerList,space.next[pointerFree],lunghezza);
-	space.prev[51]=73;
+			return;
-
+		}
-	space.next[50]=63;
+		if(pointerList<=lunghezza){
-	space.key[50]=6;
+			auxcompat(l,space.next[pointerList],pointerFree,lunghezza);
-	space.prev[50]=51;
+			return;
-
+		}
-	space.next[63]=7;
+
-	space.key[63]=7;
+		temp=space.next[pointerFree];
-	space.prev[63]=50;
+		space.next[pointerFree]=space.next[pointerList];
-
+		space.next[pointerList]=temp;
-	space.next[7]=-1;
+		temp=space.prev[pointerFree];
-	space.key[7]=8;
+		space.prev[pointerFree]=space.prev[pointerList];
-	space.prev[7]=63;
+		space.prev[pointerList]=temp;
-
+		temp=space.key[pointerFree];
-space.next[0]=2;
+		space.key[pointerFree]=space.key[pointerList];
-space.prev[2]=0;
+		space.key[pointerList]=temp;
-
+
-space.next[6]=9;
+		if(freeList==pointerFree)freeList=pointerList;
-space.prev[9]=6;
+		if(l==pointerList)l=pointerFree;
-
+
-space.next[16]=18;
+		if(space.prev[pointerList]>=0)space.next[space.prev[pointerList]] = pointerList;
-space.prev[18]=16;
+		if(space.next[pointerList]>=0)space.prev[space.next[pointerList]] = pointerList;
-
+		if(space.prev[pointerFree]>=0)space.next[space.prev[pointerFree]] = pointerFree;
-space.next[49]=52;
+		if(space.next[pointerFree]>=0)space.prev[space.next[pointerFree]] = pointerFree;
-space.prev[52]=49;
+
-
+		auxcompat(l,space.next[pointerFree],space.next[pointerList],lunghezza);
-space.next[62]=64;
+		return;
-space.prev[64]=62;
+	}
-
+}
-space.next[72]=74;
+
-space.prev[74]=72;
+
-
+/*Pre: Si assuma che space abbia m elementi, l sia una lista di n elementi e i rimanenti elementi di space (m -n) siano nella lista libera.
-return 8;
+
   Post: sposta gli elementi in l in modo che occupino le posizioni 0, 1, ..., n-1 di space e aggiusta la lista libera in modo che essa resti corretta, occupando le posizioni di space n, n+1, ...., m - 1. La funzione restituisce la lista l con gli elementi nelle posizioni specificate.
   Il tempo di esecuzione della funzione e' theta(n) e deve utilizzare SOLO una quantita' costante di spazio extra. */
 
 List compatifyList(List l){
 	int lunghez;
 	lunghez=lunghezza(l)-1;
 	auxcompat(l,l,freeList,lunghez);
 	return l;
 }