Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<stdbool.h>
- typedef struct _item{
- char *key;
- int val;
- struct _item *next;
- } item;
- typedef struct _oggetto{
- char *nome;
- int vale;
- } oggetto;
- //Funzione che crea una lista.
- item* create(char *input, int valore){
- item *list=(item*) malloc(sizeof(item));
- list->key=(char*) malloc((strlen(input)+1)*sizeof(char));
- strcpy(list->key, input);
- list->val=valore;
- list->next=NULL;
- return list;
- }
- //Funzione che, data una lista, inserisce un elemento in coda.
- void insert(item *list, char *input, int valore){
- item *t=list;
- while(t->next!=NULL) t=t->next;
- t->next=(item*) malloc(sizeof(item));
- t=t->next;
- t->key=(char*) malloc((strlen(input)+1)*sizeof(char));
- strcpy(t->key, input);
- t->val=valore;
- t->next=NULL;
- }
- //Funzione che cerca un dato elemento in una lista.
- item* search(item *list, char *input){
- item *l=list; bool trovato=false;
- while(l!=NULL && !trovato){
- if(strcmp(input, l->key)==0){
- trovato=true;
- }
- else{
- l=l->next;
- }
- }
- if(!trovato) l=NULL;
- return l;
- }
- //Funzione per calcolare l'indice della tabella hash.
- int hash(char *input, int n){
- int h=0, i;
- for(i=0; input[i]!='\0'; i++){
- h=h+(unsigned int) input[i];
- }
- h=h%n;
- return h;
- }
- int compare(const void *a, const void *b){
- oggetto x=(*(oggetto*) a);
- oggetto y=(*(oggetto*) b);
- int valabs=(x.vale)-(y.vale);
- if(valabs>0) return -1;
- if(valabs<0) return 1;
- if(valabs==0){
- int cmp=strcmp(x.nome, y.nome);
- if(cmp>0) return 1;
- if(cmp<0) return -1;
- if(cmp==0) return 0;
- }
- }
- int main(){
- int n, dim, valore, ind; item **tab, *elem; char *input;
- input=(char*) malloc(101*sizeof(char));
- scanf("%d", &n);
- if(n==0) return 0;
- dim=2*n;
- tab=(item**) malloc(dim*sizeof(item*));
- scanf("%s", input);
- scanf("%d", &valore);
- ind=hash(input, dim);
- tab[ind]=create(input, valore);
- n--;
- while(n>0){
- scanf("%s", input);
- scanf("%d", &valore);
- ind=hash(input, dim);
- //Caso in cui la tabella hash, alla cella di indice ind, sia NULL.
- if(tab[ind]==NULL){
- tab[ind]=create(input, valore);
- }
- else{
- elem=search(tab[ind], input);
- /*Caso in cui l'elemento non sia presente nella lista,
- alla cella di indice ind. */
- if(elem==NULL) insert(tab[ind], input, valore);
- else{
- //Caso in cui devo aggiornare il valore di un elemento.
- if(elem->val < valore) elem->val=valore;
- }
- }
- n--;
- }
- //Conto quanti elementi sono memorizzati nella tabella hash.
- int count=0, i;
- for(i=0; i<dim; i++){
- if(tab[i]!=NULL){
- while(tab[i]!=NULL){
- count++;
- tab[i]=tab[i]->next;
- }
- }
- }
- printf("%d\n", count);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement