PDA

Visualizza la versione completa : [C]Operazione su lista


dennis87
16-07-2014, 15:07
Ciao a tutti,
ho una lista di interi doppiamente concatenata. Non capisco come spezzare questa lista e crearne due, la prima conterrà i primi x valori, l'altra conterrà i restanti.
Ad esempio se ho una lista contenente [3 4 5 7 9 6 3] e inserisco x=2, devo stampare la lista [3 4] e la lista [5 7 9 6 3].
Sono riuscito a spezzare la lista secondo il valore dato in input, settando il next dell'elemento uguale all'indice a NULL, quello che non capisco è come creare la nuova lista con gli elementi restanti.

Grazie a tutti

Aggiungo un po' di codice

Strutture.h

struct node{
int iData;//elemento della lista
struct node *prev; //puntatore all'elemento precedente della lista;
struct node *next; //puntatore all'elemento successivo della lista;
};

struct list {
char cNomeLista[10]; //array contenente il nome della lista
int iNumeroElementi; //numero elementi della lista
struct node *header; //puntatore al primo elemento della lista
struct node *tail; //puntatore all'ultimo elemento della lista
struct list *next; //puntatore alla successiva lista
//struct list *; //puntatore alla prima lista
};

operation_on_list.c

#include "header.h"
#include "strutture.h"
/**
* Funzione che mi permette di stampare
* la lista passata come argomento.
*/
void print_list(struct list* list){
struct node* tempNode;
tempNode = list -> header;
int i;

printf("\n%s [", list -> cNomeLista);
if(list -> iNumeroElementi == 0){
printf("Nil");
}else{
for(i = 0; i < list -> iNumeroElementi; i++){
printf(" %d ", tempNode->iData);
tempNode = tempNode -> next;
}
}
printf("]");
}

/**
* Funzione che stampa tutte le liste
* che sono state create e che sono
* presenti in memoria. Ogni lista
* presente in memoria viene passata come
* argomento alla funzione print_list
* che si occupa di stamparla.
*/
void print_allList(struct list* list, int numListe){
int i;

for(i = 1; i <= numListe; i++){
print_list(list->next);
list = list -> next;
}
}

/**
* Funzione che stampa tutti i nomi
* delle liste presenti in memoria.
*/
void printNameOfAllList(struct list *list, int temp){
int i;
for(i=0;i<temp;i++){
list = list -> next;
printf("\n%s", list -> cNomeLista);
}
}

void testSplit(struct list* list, int k, int contList){
int x = (list -> iNumeroElementi)/k;
int i;
struct node* tempNode;int temp;
//struct list* tempL = init_list();
struct list* newList;// = list;// = tempL;

tempNode = list -> header;
if(list -> iNumeroElementi == 0){
printf("Split non applicabile ad una lista vuota!\n");
}else{
//list -> iNumeroElementi = x;
for(i=0; i < list -> iNumeroElementi; i++){
if(i == (x-1)){
temp = tempNode -> iData;
printf("Elemento %d\n ", temp);
printf("Numero di elementi della lista %s: %d\n", list -> cNomeLista, list -> iNumeroElementi);
tempNode = tempNode -> next = NULL;
list -> iNumeroElementi = x;
printf("Numero di elementi della lista %s: %d\n", list -> cNomeLista, list -> iNumeroElementi);
printf("contList vale %d: ", ++contList);
newList = insert_list(newList, contList);
printf("Arrivo qui");
insert_node(newList, 123456);insert_node(newList, 23);
printf("Arrivo anche qui");
printf("Numero di elementi della nuova lista %d ", newList -> iNumeroElementi);
printf("Nome della nuova lista %s ", newList -> cNomeLista);
break;
}
tempNode = tempNode -> next;
}
}
}


/**
* Funzione che controlla se il nome di lista
* inserito corrisponde con un nome di lista
* presente in memoria.
*/
void listPresentOrNotPresent(struct list* list, char *sEnteredName, int contList){
//printf("Sono dentro la funzione listPresentOrNotPresent\n");
int i; int k;
//printf("sEnteredName vale: %s\n", sEnteredName);
for(i=0; i < contList; i++){
list = list -> next;
if(strcmp(list -> cNomeLista, sEnteredName)==0){ //verifico che il nome della lista corrisponde a quello da me inserito
printf("Uguali\n");
printf("La lista %s e' composta da %d elementi.\n", list -> cNomeLista, list -> iNumeroElementi);
do{ //Se la lista esiste richiedo di inserire il valore di k, controllando di inserire un valore >1.
printf("Inserisci un valore intero positivo(maggiore di 1): ");
scanf("%d", &k);
}while(k<=1);
testSplit(list, k, contList);
break;
}else{
printf("Non uguali\n");
}
}
}



/**
* Funzione che, se richiamata, mi permette di
* di inizilizzare la lista.
*/
struct list* init_list (){
printf("Inizializzo la struttura delle liste\n");
struct list *temp;

temp = malloc(sizeof(struct list));

temp -> iNumeroElementi=0;
temp -> header = NULL;
temp -> tail = NULL;
temp -> next = NULL;

return temp;
}

/**
* Funzione che nserisce una nuova lista in memoria
* con nome nel formato List-contList (che è progressivo).
*/
struct list* insert_list(struct list* list, int contList){ //modifica
//creo una nuova lista
struct list *new_list;
//alloco spazio per la nuova lista
new_list = malloc(sizeof(struct list));

sprintf(new_list->cNomeLista, "List-%d", contList);
//new_list -> cNomeLista;
new_list -> iNumeroElementi = 0;
new_list -> header = NULL;
new_list -> tail = NULL;
list -> next = new_list;

new_list -> next = NULL;

return new_list;
}

operation_on_node.c

#include "strutture.h"
#include "header.h"

void insert_node(struct list *list, int iElemento){
//creo un nuovo nodo
struct node *new_node;
//alloco spazio per il nuovo nodo
new_node = malloc(sizeof(struct node));

new_node -> iData = iElemento;

new_node -> next = NULL;

if(list -> iNumeroElementi==0){
new_node -> prev = NULL;

list -> header = new_node;
}else{
new_node -> prev = list -> tail;
list -> tail -> next = new_node;


}

list -> tail = new_node;

list -> iNumeroElementi++;
}

int scan_node(struct list* list, int indice){

indice--;
if(indice >= list -> iNumeroElementi){
printf("Errore: hai inserito un indice che supera le dimensioni della lista");
return 0;
}
int i;
int iElemento;
struct node* tempNode;
tempNode = list -> header;
for(i = 0; i < list -> iNumeroElementi; i++){
if(i == indice){
iElemento = tempNode -> iData;
return iElemento;
}
tempNode = tempNode -> next;
}
return 0;
}

main.c

int main (void){
char cScelta;
struct list* first = init_list();
int contList=0;
int iElementoDellaLista;
int iRestituito;
int k;
char aczNameOfList[100];
struct list* last_list = first;
/*Ciclo while che gira fino a quando e' verificata la condizione 1.
Dentro al ciclo faccio la chiamata alla funzione stampaMenu e salvo
il valore restituito in una variabile di tipo char che mi permette
di scegliere uno dei case corrispondenti.*/
while(1){
cScelta=stampaMenu();
switch (cScelta){
case 'a':
printf("Inserisci gli elementi della lista.\n 0 per terminare l'inserimento\n\n");
contList++;

last_list = insert_list(last_list, contList);

printf("Elemento: ");
scanf("%d", &iElementoDellaLista);

while(iElementoDellaLista!=0){
insert_node(last_list, iElementoDellaLista);
printf("Elemento: ");
scanf("%d", &iElementoDellaLista);
}
break;
case 'v':
if(contList==0){
printf("Non ci sono liste da stampare\n");
break;
}else{
print_allList(first, contList);
}
break;
case 'b':
printf("Inserisci il nome di una lista (nel formato List-i) a cui applicare lo split: ");
scanf("%s", aczNameOfList);

listPresentOrNotPresent(first, aczNameOfList, contList);
break;
}
}
}


Se ad esempio al punto a creo una lista (che si chiamerà List-1) con gli elementi [1 2 3 4 5] quando chiamo il punto b sulla lista List-1 e inserendo successivamente k=2, la funzione listPresentOrNotPresent mi chiama la funzione testSplit passando la lista interessata il valore di k e il contList (che forse è inutile). Nella funzione testSplit entra nel ramo else e quando i è uguale a x-1 prendo l'elemento corrispondente e setto il suo next a NULL in modo da modificare la lista, che quindi adesso dovrebbe essere nel formato [1 2], e infatti se richiamo la funzione per stampare le liste la stampa in quel formato. Il problema è che non capisco come creare una nuova lista con gli elementi rimanenti.

Grazie ancora.

torn24
16-07-2014, 16:12
Non conosco cosa debba fare il tuo programma esattamente , ma mi risulta evidente un errore logico ,

se devi dividere una lista , non puoi avere un unico puntatore struct list.
Ma se dividi la lista in due sottoliste A e B , dovrai avere un puntatore list per A e un puntatore list per B .
A livello di codice ORA tu scorri la lista A fino al nodo voluto , e imposti il puntatore next a NULL , diciamo che cosi tronchi la lista , quello che dovrai fare per dividere la lista , è scorrere la lista A fino al nodo voluto , il puntatore next di A assegnarlo al puntatore head di B , e solo alla fine impostarlo a NULL .

La cosa per via dei campi di struct list , può risultare più complessa , ma il succo è quello che ti ho descritto :D


Ora se il tuo programma deve ricevere un unica lista e dividerla in due sottoliste , basterebbe dichiarare due puntatori list nel main , mentre se non sai in numero di liste e quindi di sottoliste , che verranno create , la cosa diventa molto più complessa , una soluzione potrebbe essere di creare un array dinamico di struct list , nel main , e ogni volta che si crea una lista o una sottolista , allocare memoria , quindi ogni elemento dell'array , sarebbe una lista o sottolista.
Non so se quello che ho detto ti può essere di aiuto , ma il mio aiuto si limita a questo :)

dennis87
16-07-2014, 16:31
Non conosco cosa debba fare il tuo programma esattamente , ma mi risulta evidente un errore logico ,

se devi dividere una lista , non puoi avere un unico puntatore struct list.
Ma se dividi la lista in due sottoliste A e B , dovrai avere un puntatore list per A e un puntatore list per B .
A livello di codice ORA tu scorri la lista A fino al nodo voluto , e imposti il puntatore next a NULL , diciamo che cosi tronchi la lista , quello che dovrai fare per dividere la lista , è scorrere la lista A fino al nodo voluto , il puntatore next di A assegnarlo al puntatore head di B , e solo alla fine impostarlo a NULL .

La cosa per via dei campi di struct list , può risultare più complessa , ma il succo è quello che ti ho descritto :D


Ora se il tuo programma deve ricevere un unica lista e dividerla in due sottoliste , basterebbe dichiarare due puntatori list nel main , mentre se non sai in numero di liste e quindi di sottoliste , che verranno create , la cosa diventa molto più complessa , una soluzione potrebbe essere di creare un array dinamico di struct list , nel main , e ogni volta che si crea una lista o una sottolista , allocare memoria , quindi ogni elemento dell'array , sarebbe una lista o sottolista.
Non so se quello che ho detto ti può essere di aiuto , ma il mio aiuto si limita a questo :)



Cioè dovrei fare una cosa del genere?


newList = insert_list(newList, ++contList);
newList -> header = tempNode -> next;
tempNode = tempNode -> next=NULL;
list -> iNumeroElementi = x;


EDIT: Non funziona :dhò:

dennis87
18-07-2014, 22:43
Qualcuno mi aiuta per favore?

Loading