Appunti e funzioni su liste ed array

VALORE PER CUI LA SOMMA DEI SUOI PRESENTE ANCHE NELL’ARRAY B.

ELEMENTI PRECEDENTI È UGUALE

ALLA SOMMA DEI SUOI ELEMENTI int member (int array[], int

SUCCESSIVI dim, int el)

{

/*divido il problema. 1) int i=0; int trovato=0;

scrivo la funzione che fa la while (trovato==0 && i<dim-1)

somma degli elementi da un if(array[i]==el)

indice inizio ad un indice trovato=1;

fine. */ else i++;

int somma (int a[], int return trovato;

inizio, int fine) }

{ int verifica(int a[], int b[],

int i; int s=0; int dima,int dimb)

for (i=inizio; i<fine; i++) {

s=s+a[i]; int i=dima; int presente=0;

return s; while (i<dima && !presente)

} if(member(b,dimb,a[i])

presente=1;

//adesso scrivo la funzione else i++;

che cerca l’indice che return presente;

verifica la condizione }

int somma2 (int a[], int dim) main()

{ {

int i= ; int a[10];

int b[5];

int controllo;

if(verifica(a,b,10,5))

printf(“Esiste almeno un

elemento che compare in

entrambi i vettori”); else

printf (“Nessun elemento

uguale”);

return;

}

PROCEDURA CHE ORDINA I VALORI DI UN ARRAY (Algoritmo Bubble Sort)

#include <stdio.h>

void swap (int* a, int* b)

{ int temp=*b;

*b=*a;

*a=temp;

}

void bubble (int a[ ],int fine)

{

//porto il più grande in fondo

int i;

for (i=0;i<fine;i++)

if (a[i]>a[i+1])

swap(&a[i],&a[i+1]);

}

void sort(int a[ ],int dim)

{ int i;

for (i=dim; i>1; i--)

bubble(a,i);

}

FUNZIONE CHE RESTITUISCE L’INDICE DELLA PRIMA OCCORRENZA DEL VALORE

MASSIMO IN UN ARRAY

int indicemax (int a[ ], int dim)

{ int i, max=a[0], index=-1;

for (i=1; i<dim; i++)

if(a[i]>max)

{ max=a[i];

index=i;

}

return index;

//Avessi messo >= avrei trovato l’indice dell’ultima occ.

}

FUNZIONE CHE SALVA L’INDICE DELLA PRIMA OCCORRENZA DI ZERO NELL’ARRAY

int izero (int a[ ], int dim)

{ int i=0,indice=-1; //se non trovo 0

int trovato=0;

while(!trovato && i<dim)

if (a[i]==0)

{ indice=i;

trovato=1;

}

return indice;

}

DATI 2 ARRAY A,B DI DIMENSIONI DIM A E DIM B CONTROLLARE CHE ABBIANO GLI

STESSI VALORI (ANCHE SE CON OCCORRENZE DIVERSE)

int member (int a[ ],int dim, int el) {...}

int stessivalori (int a[ ],int b[ ], int dima, int dimb)

{ int i=0,ok=1;

while(i<dima && ok)

if(member(b,dimb,a[i])

ok=0;

else i++;

//controllo che gli elem. di a siano in b

if (ok)

{

//controllo che gli elem. di b siano in a solo se il precedente

controllo era OK

i=0; //resetto l’index

while(i<dimb && ok)

if(!member(a,dimb,b[i])

ok=0;

else i++;

}

return ok;

}

CONTROLLARE CHE I VALORI DI 2 ARRAY SIANO UGUALI E CON LA STESSA

MOLTEPLICITÀ

int conta (int el, int a[ ],int dim)

{ int i, num=0; //contatore

for (i=0; i<dim; i++)

if (a[i]==el) num++;

return num;

}

int stesseoccorrenze( int a[ ],int b[ ],int dim)

{ int i=0,ok=1;

while (i<dim && ok)

if (conta(a[i],a,dim)==conta(a[i],b,dim)

i++;

else ok=0;

return ok;

} LE STRUTTURE DINAMICHE IN C

Una struttura dinamica è una struttura dati che può modificare la sua dimensione

durante l’esecuzione del programma. La struttura dato ARRAY/MATRICE è una

struttura statica mentre una struttura dinamica è rappresentata dalla LISTA. La

LISTA è una struttura omogenea (tutti gli elementi sono dello stesso tipo)

dinamica (posso aggiungere e togliere elementi).

Le strutture dinamiche non possono essere gestite sulla memoria a pila infatti

vengono gestite su una memoria dinamica detta HEAP.

Per capire come vengono trattate le strutture dinamiche, dobbiamo aggiungere

allo stato astratto ambiente-memoria, la memoria Heap. In concreto una parte

della memoria del calcolatore a disposizione del programma in esecuzione viene

gestita come una pila di frame mentre una parte come memoria dinamica. La

memoria dinamica è indipendente dalla gestione a blocchi e viene allocata

(riservata) e deallocata (liberata) in modo esplicito, cioè attraverso funzioni e

procedure predefinite. La memoria dinamica è gestita come una sequenza di

parole di memoria senza struttura.

Allocazione Esplicita

Funzione ​ malloc​ () che ha per argomento lo spazio da allocare in memoria heap e

che restituisce l’indirizzo della prima parola di memoria riservata. Per effettuare

l’allocazione dobbiamo sapere prima quanto spazio necessitiamo per quel tipo di

struttura, per questo ci serviamo della funzione ​ Sizeof()​ che, dato per parametro

un tipo, ci restituisce lo spazio che occupa in memoria un oggetto del tipo

passato.

In C è presente un costruttore di tipo, che permette di definire nuovi tipi a partire

da tipi conosciuti, che si chiama S

​ truct. ​ La struct permette di prendere oggetti di

tipo diverso e di costruire con essi un nuovo tipo.

Es.

struct el

{ int a;

int b;

float c;

}

main()

{ struct el* p;

struct el x;

p=malloc(Sizeof(struct el));

//malloc restituisce indirizzo

x.a=18; x.c=7.61;

// Notazione x.a significa

//l’elemento di nome a della //struttura associata ad x

}

Alla chiusura del blocco main si effettua un pop su ambiente e memoria mentre

la mem H rimane riservata perché indipendente dalla gestione a blocchi. La

parola di memoria Hn rimane riservata e quindi non accessibile; si definisce

infatti “

​ garbage”​ perché non più liberabile se si è perso il puntatore a quella

parola di memoria.

Esiste una procedura​ free() ​ che permette di liberare la parola di memoria

riservata; come parametro deve essere passata la variabile che punta allo spazio

da liberare.

Es.

struct el {...};

struct el* p=malloc(Sizeof(struct el));

free(p);

COME COSTRUIRE UNA LISTA NEL MAIN

typedef

struct edl {

int info;

struct edl* next;

}edl; //elemento di lista

int main()

{ edl* l=malloc(sizeof(edl));

edl* corr;

l->info=1;

corr=l;

for(i=2;i<=10;i++)

{ corr->next=malloc(sizeof(edl));

corr->info=i;

corr=corr->next;

//scorro il corr

}

corr->next=NULL;

//termino la lista con un puntatore che non punta a nulla

}

COME COSTRUIRE UNA LISTA CON UNA PROCEDURA

typedef

struct edl {

int info;

struct edl* next;

}edl; //elemento di lista

void crealista(int n,edl**l)

{ *l=NULL;//Creo la lista vuota

int i; edl* corr;

if (n>0)

{ *l=malloc(sizeof(edl));

(*l)->info=1;

corr=(*l); //definisco l’elemento corrente

for (i=2; i<=n;i++)

{ corr->next=malloc(sizeof(edl));

corr=corr->next;

​

corr->info=i oppure​ scanf(“%d”,&corr->info)

}

corr->next=NULL;//per chiudere la lista

}

}

AGGIUNGERE AD UNA LISTA UN ELEMENTO V DOPO LA PRIMA OCCORRENZA DEL

VALORE EL. SE NON ESISTE LA LISTA RIMANE INVARIATA.

void addafter(edl*l,int v,int el)

{ int trovato=0;

edl* corr=l;

while(!trovato && corr!=null)

/*Metto corr diverso da null perchè se scrivessi corr->next!=null

non mi considererebbe l’ultimo elemento della lista*/

{ if(corr->info==el)

trovato=1;

else corr=corr->next;

if (trovato)

{ edl* aus;

aus=malloc(sizeof(edl);

aus->info=v;

aus->next=corr->next

corr->next=aus;

}

}

}

AGGIUNGERE UN NUOVO EDL CONTENENTE V AD UNA LISTA PRIMA DELLA PRIMA

OCCORRENZA DEL VALORE EL

void addbefore(edl** l,int v,int el){

{ int trovato=0;

edl* prec=NULL;//puntatore all’elemento precedente

edl* corr=*l;//puntatore elemento corrente

while(!trovato && corr!=NULL)

{ if(corr->info==el)trovato=1;

else {

prec=corr;

//no prec=prec->next perchè inizializzato a NULL

corr=corr->next;

}

if (trovato)

{ edl* aus;

aus=malloc(sizeof(edl));

aus->info=v;

//Devo distinguere se attaccare in testa o no

if(prec==NULL)//Primo elemento

{ aus->next=*l;

*l=aus;

}

else

{ aus->next=corr;

prec->next=aus;

}

}

}