LINUX AVANZATO 2007

/* ****************************************
Scrivere un progrmma che costruisce una lista bidirezionale di N elementi del seguente tipo:

Elemento {
struct list_head lh;
int valore;
};

N è passato tramite riga di comando. L'area di memoria richiesta per contenere un nuovo elemento è ottenuta facendo uso
della funzione malloc(); I puntatori della lista bidirezionale sono realizzati dalla seguente struttura:

struct list_head {
struct list_head *next;
struct list_head *prev;
};

Il valore di ogni elemento della lista è un numero casuale compreso tra 1 e 100. Dopo aver costruito la lista, il programma
stampa i valori degli elementi a partire dall'inizio della lista. Il programma effettua quindi un riordinamento per valori crescenti degli elementi della lista e stampa a partire dall'inizio della lista i valori degli elemnenti della lista ordinata.
******************************************* */

#include<stdio.h>
#include<stdlib.h>

struct head_li {
	struct head_li *next;
	struct head_li *prev;
};

struct elem {
	struct head_li li;
	int val;
};

typedef struct elem Elem;
typedef struct head_li Head;

Elem* list_add(Elem* list) {
	Elem* temp;
	if(list == NULL) {
		list = (Elem*)malloc(sizeof(Elem));
		list->li.prev = NULL;
		list->val = rand()%100;
		list->li.next = NULL;
		
		return list;
	}
	
	list->li.next = malloc(sizeof(Elem));
	temp = list;
	list = (Elem*)list->li.next;
	list->val = rand()%100;
	list->li.prev = (Head*)temp;
	list->li.next = NULL;
	temp = (Elem*)list->li.prev;
	
	return list;
}

Elem* list_add_e(Elem* list,Elem* e) {
	Elem* temp;
	if(list == NULL) {
		list = malloc(sizeof(Elem));
		list->li.prev = NULL;
		list->val = e->val;
		list->li.next = NULL;
		
		return list;
	}
	
	list->li.next = malloc(sizeof(Elem));
	temp = list;
	list = (Elem*)list->li.next;
	list->val = e->val;
	list->li.prev = (Head*)temp;
	list->li.next = NULL;
	temp = (Elem*)list->li.prev;
	
	return list;
}

Elem* minimo(Elem* list, int N) {
	Elem* min = list;
	Elem* f = (Elem*)list->li.next;
	int m = list->val;
	int i;
	
	for(i=1; i<N; i++) {
		if(f->val <= m && f->val>0 || m == -1) {
			m = f->val;
			min = f;
		}
		f = (Elem*)f->li.next;
	}

	return min;
}

Elem* ordina_lista(Elem* list, int N) {
	Elem *ordinata, *f;
	Elem *min;
	int i;
	for(i=0; i<N; i++) {
		min = minimo(list,N);
		printf("min: %i\n",min->val);
		
		ordinata = list_add_e(ordinata,min);
		if(i==0) {
			f = ordinata;
		}
		min->val = -1;
	}
	f->li.prev = (Head*)ordinata;
	ordinata->li.next = (Head*)f;
	
	/* stampa lista ordinata */
	i=0;
	while(i<N) {
		Elem* t;
		t = (Elem*)f->li.prev;
		printf("[O] %i\t%i\n",f->val,(t==NULL)?-3:t->val);
		f = (Elem*)(f->li.next);
		i++;
	}
	
}

int main(int args, char* argv[]) {
	
	Elem *e,*f,*l;
	int i;
	int N;
	if(args<2) {
		printf("Usage: %s <N>\n",argv[0]);
		exit(0);
	}
	
	N = atoi(argv[1]);
	if(N<1) {
		printf("Inserire un valore di N > 1\n");
		exit(1);
	}
	
	e = NULL;
	
	for(i=0;i<N;i++) {
		e = list_add(e);
		if(i==0)
			f = e;
	}
	f->li.prev = (Head*)e;
	e->li.next = (Head*)f;
	
	i=0;
	while(i<N) {
		Elem* t;
		t = (Elem*)f->li.prev;
		printf("[L] %i\t%i\n",f->val,(t==NULL)?-1:t->val);
		f = (Elem*)(f->li.next);
		i++;
	}
	
	ordina_lista(f,N);
}

/*
 Prova di programmazione del 14/09/2007:
 
 Scrivere un programma che costruisce una lista bidirezionale di N elementi del seguente tipo:
 
 struct elemento {
	 struct list_head lh;
	 int valore;
 };
 
 N è passato tramite riga di comando. L'area di memoria richiesta per contenere un nuovo elemento è ottenuta facendo uso
 della funzione malloc(); I puntatori della lista bidirezionale sono realizzati dalla seguente struttura:
 
 struct list_head {
	 struct list_head *next;
	 struct list_head *prev;
 };
 
 Il valore di ogni elemento della lista è un numero casuale compreso tra 1 e 100. Dopo aver costruito la lista, il programma
 stampa i valori degli elementi a partire dall'inizio della lista. Il programma effettua quindi un riordinamento per valori crescenti degli elementi della lista e stampa a partire dall'inizio della lista i valori degli elemnenti della lista ordinata.
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>

struct list_head {
	struct list_head *next;
	struct list_head *prev;
};

struct elemento {
	struct list_head lh;
	int valore;
};


struct list_head* genera_lista(int N);
void stampa_lista(struct list_head *lista, int N);
struct list_head* ordina_lista(struct list_head *lista);


/* MAIN */
int main(int argc, char* argv[]) {
	if (argc < 2) {
		printf("Usage: %s <N>", argv[0]);
		exit(1);
	}
	
	int N = atoi(argv[1]);
	struct list_head *lista = NULL;
	
	srand(time(NULL));
	
	/* costruisco la lista */
	lista = genera_lista(N);
	
	/* stampa lista */
	stampa_lista(lista, N);

	/* ordina lista */
	lista = ordina_lista(lista);
	
	/* stampa lista */
	stampa_lista(lista, N);
	
	return 0;
}

/* genera la lista bidirezionale circolare lunga N con valori random */
struct list_head* genera_lista(int N) {
	struct list_head* last = NULL;
	struct list_head* first = NULL;
	struct elemento* elem = NULL;
	
	if (N == 0) return NULL;
	
	elem = (struct elemento*)malloc(sizeof(struct elemento));
	elem->valore = rand()%100 + 1;
	last = (struct list_head*)elem;
	first = last;
	(elem->lh).next = first;
	(elem->lh).prev = last;
	N--;
	
	while (N > 0) {
		elem = (struct elemento*)malloc(sizeof(struct elemento));
		elem->valore = rand()%100 + 1;
		(elem->lh).next = first;
		(elem->lh).prev = last;
		last->next = (struct list_head*)elem;
		last = last->next;
		N--;
	}
	
	return first;
}

/* stampa la lista circolare lunga N */
void stampa_lista(struct list_head *lista, int N) {
	struct list_head* l = lista;

	if (l == NULL) return;
	
	while (N > 0) {
		printf("%d -> ", ((struct elemento*)l)->valore);
		l = l->next;
		N--;
	}
	printf("\n\n");
}

/* una sorta di selection sort */
struct list_head* ordina_lista(struct list_head *lista) {
	struct list_head* l = lista;
	struct elemento* elem1 = NULL;
	struct elemento* elem2 = NULL;
	int numswap = 0;
	int temp;
	
	while(1) {
		elem1 = (struct elemento*)l;
		elem2 = (struct elemento*)(l->next);
		if (elem1->valore > elem2->valore) {	/* scambio solo il valore */
			temp = elem1->valore;
			elem1->valore = elem2->valore;
			elem2->valore = temp;
			numswap++;
		}
		l = l->next;
		
		if (l->next == lista) {
			if (numswap == 0) break; /* lista ordinata */
			numswap = 0;
			l = l->next;
		}
	}
	
	return lista;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN_VAL 1
#define MAX_VAL 100

typedef struct list_head {
	struct list_head *next, *prev;
} list_head;

typedef struct elemento {
	list_head lh;
	int valore;
} elemento;

void add(elemento **lista, int elem)
{
	elemento *new, *app1, *app2;
	list_head *temp;
	
	new = (elemento *) malloc(sizeof(elemento));

	new->valore = elem;
	new->lh.next = NULL;
	new->lh.prev = NULL;

	if(*lista == NULL)
	{
		*lista = new;
	}
	else
	{
		app1 = app2 = *lista;
	
		while(app1->lh.next != NULL)
		{
			temp = app1->lh.next;

			app1 = (elemento *) ((char *) temp - ((size_t)&((elemento *)0)->lh));

			app2 = app1;
		}

		app1 = new;

		app2->lh.next = &(new->lh);

 		app1->lh.prev = &(app2->lh);
	}
}

void stampa(char *label, elemento *lista)
{
	printf("%s -> : ", label);

	if(lista != NULL)
	{
		printf("%d ", lista->valore);

		while(lista->lh.next != NULL)
		{
			lista = (elemento *) ((char *) lista->lh.next - ((size_t)&((elemento *)0)->lh));
			printf("%d ", lista->valore);
		}
	
		printf("\n");
	}

	
	printf("%s <- : ", label);

	if(lista != NULL)
	{
		printf("%d ", lista->valore);

		while(lista->lh.prev != NULL)
		{
			lista = (elemento *) ((char *) lista->lh.prev - ((size_t)&((elemento *)0)->lh));
			printf("%d ", lista->valore);
		}

		printf("\n");
	}
}

void sort(elemento **lista, int N)
{
	elemento *temp, *elem1, *elem2;
	int i, app;

	for(i = 0; i < (N-1); i++)
	{
		temp = *lista;

		while(temp->lh.next != NULL)
		{
			elem1 = (elemento *) ((char *) &(temp->lh) - ((size_t)&((elemento *)0)->lh));
			elem2 = (elemento *) ((char *) temp->lh.next - ((size_t)&((elemento *)0)->lh));

			if (elem1->valore > elem2->valore) {
				app = elem1->valore;
				elem1->valore = elem2->valore;
				elem2->valore = app;
			}

			temp = (elemento *) ((char *) temp->lh.next - ((size_t)&((elemento *)0)->lh));
		}
	}
}

int main(int argc, char *argv[])
{
	elemento *lista = NULL;
	char *label;
	int i, N, r;

	if(argc != 2)
	{
		fprintf(stderr, "Uso: %s <N>\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	N = atoi(argv[1]);
	
	if(N < 1) {
		fprintf(stderr, "Inserire un valore di N maggiore (o uguale) a 1\n");
		exit(EXIT_FAILURE);
	}

	srand(time(0));

	for(i = 0; i < N; i++)
	{
		r = rand() % MAX_VAL + MIN_VAL;

		printf("Genero il numero casuale %d\n", r);
		
		add(&lista, r);
	}
	
	label = "Lista";
	
	stampa(label, lista);

	sort(&lista, N);

	label = "Lista ordinata";

	stampa(label, lista);

	return 0;
}

#include <stdio.h>
#include <stdlib.h>


struct list_head {
	struct list_head *next;
	struct list_head *prev;
}typedef list_head;

struct elemento {
	struct list_head lh;
	int valore;
}typedef elemento;


elemento *crealista(int);
void stampalista(elemento *);
void ordinalista(elemento *	);

int main (int argc, char const* argv[]){
	int n;
	if(argc < 2 ){
		printf("errore nel passaggio dei parametri\n");
		exit(1);
	}
	n = atoi(argv[1]);	
	elemento *testa;
	testa = crealista(n);
	stampalista(testa);
	ordinalista(testa);
	stampalista(testa);
	return 0;
}
elemento *crealista(int n){
	int i;
	elemento *r,*p,*q;
	r=(elemento *)malloc(sizeof(elemento));
	r->valore=-1;
	r->lh.prev=NULL;
	p=r;
	for( i = 0; i < n; i += 1 ){
		p->lh.next = (list_head*)malloc(sizeof(elemento));
	    q =(elemento*) p->lh.next;
		q->valore = rand() % n;
	    q->lh.prev =(list_head*) p;
	    p = q;
	}
	q->lh.next =NULL;
	return r;
}

void stampalista(elemento *r){
	elemento *p;
	int i ;
	p=r;
	printf("stampa della lista\n");
	while( p != NULL){
		printf("->  %d\n", p->valore );
		p=(elemento*)p->lh.next;
	}
}

void ordinalista(elemento *r){
	elemento *p,*q;
	int tmp;
	int flag = 0 ;
	p=r;
	while(p!=NULL){
		q=(elemento*)p->lh.next;
		if( (q!=NULL) && (p->valore > q->valore) ){
			tmp = q->valore;
			q->valore = p->valore;
			p->valore = tmp;
			flag=1;
		}
		p=(elemento*)p->lh.next;
	}
	if(flag)
		ordinalista(r);
}