Advertisement
riccac

Untitled

Jan 31st, 2015
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<stdbool.h>
  5.  
  6. typedef struct _item{
  7.  
  8. char *key;
  9.  
  10. int val;
  11.  
  12. struct _item *next;
  13.  
  14. } item;
  15.  
  16. typedef struct _oggetto{
  17.  
  18. char *nome;
  19.  
  20. int vale;
  21.  
  22. } oggetto;
  23.  
  24.  
  25. //Funzione che crea una lista.
  26.  
  27.  
  28. item* create(char *input, int valore){
  29.  
  30. item *list=(item*) malloc(sizeof(item));
  31.  
  32. list->key=(char*) malloc((strlen(input)+1)*sizeof(char));
  33.  
  34. strcpy(list->key, input);
  35.  
  36. list->val=valore;
  37.  
  38. list->next=NULL;
  39.  
  40. return list;
  41.  
  42. }
  43.  
  44.  
  45. //Funzione che, data una lista, inserisce un elemento in coda.
  46.  
  47. void insert(item *list, char *input, int valore){
  48.  
  49. item *t=list;
  50.  
  51. while(t->next!=NULL) t=t->next;
  52.  
  53. t->next=(item*) malloc(sizeof(item));
  54.  
  55. t=t->next;
  56.  
  57. t->key=(char*) malloc((strlen(input)+1)*sizeof(char));
  58.  
  59. strcpy(t->key, input);
  60.  
  61. t->val=valore;
  62.  
  63. t->next=NULL;
  64.  
  65. }
  66.  
  67.  
  68. //Funzione che cerca un dato elemento in una lista.
  69.  
  70. item* search(item *list, char *input){
  71.  
  72. item *l=list; bool trovato=false;
  73.  
  74. while(l!=NULL && !trovato){
  75.  
  76. if(strcmp(input, l->key)==0){
  77.  
  78. trovato=true;
  79.  
  80. }
  81.  
  82. else{
  83.  
  84. l=l->next;
  85.  
  86. }
  87.  
  88. }
  89.  
  90. if(!trovato) l=NULL;
  91.  
  92. return l;
  93.  
  94. }
  95.  
  96.  
  97. //Funzione per calcolare l'indice della tabella hash.
  98.  
  99. int hash(char *input, int n){
  100.  
  101. int h=0, i;
  102.  
  103. for(i=0; input[i]!='\0'; i++){
  104.  
  105. h=h+(unsigned int) input[i];
  106.  
  107. }
  108.  
  109. h=h%n;
  110.  
  111. return h;
  112.  
  113. }
  114.  
  115.  
  116.  
  117. int compare(const void *a, const void *b){
  118.  
  119. oggetto x=(*(oggetto*) a);
  120.  
  121. oggetto y=(*(oggetto*) b);
  122.  
  123. int valabs=(x.vale)-(y.vale);
  124.  
  125. if(valabs>0) return -1;
  126.  
  127. if(valabs<0) return 1;
  128.  
  129. if(valabs==0){
  130.  
  131. int cmp=strcmp(x.nome, y.nome);
  132.  
  133. if(cmp>0) return 1;
  134.  
  135. if(cmp<0) return -1;
  136.  
  137. if(cmp==0) return 0;
  138.  
  139. }
  140.  
  141. }
  142.  
  143.  
  144.  
  145. int main(){
  146.  
  147. int n, dim, valore, ind; item **tab, *elem; char *input;
  148.  
  149. input=(char*) malloc(101*sizeof(char));
  150.  
  151. scanf("%d", &n);
  152.  
  153. if(n==0) return 0;
  154.  
  155. dim=2*n;
  156.  
  157. tab=(item**) malloc(dim*sizeof(item*));
  158.  
  159. scanf("%s", input);
  160.  
  161. scanf("%d", &valore);
  162.  
  163. ind=hash(input, dim);
  164.  
  165. tab[ind]=create(input, valore);
  166.  
  167. n--;
  168.  
  169. while(n>0){
  170.  
  171. scanf("%s", input);
  172.  
  173. scanf("%d", &valore);
  174.  
  175. ind=hash(input, dim);
  176.  
  177. //Caso in cui la tabella hash, alla cella di indice ind, sia NULL.
  178.  
  179. if(tab[ind]==NULL){
  180.  
  181. tab[ind]=create(input, valore);
  182.  
  183. }
  184.  
  185. else{
  186.  
  187. elem=search(tab[ind], input);
  188.  
  189. /*Caso in cui l'elemento non sia presente nella lista,
  190.  
  191. alla cella di indice ind. */
  192.  
  193. if(elem==NULL) insert(tab[ind], input, valore);
  194.  
  195. else{
  196.  
  197. //Caso in cui devo aggiornare il valore di un elemento.
  198.  
  199. if(elem->val < valore) elem->val=valore;
  200.  
  201. }
  202.  
  203. }
  204.  
  205. n--;
  206.  
  207. }
  208.  
  209. //Conto quanti elementi sono memorizzati nella tabella hash.
  210.  
  211. int count=0, i;
  212.  
  213. for(i=0; i<dim; i++){
  214.  
  215. if(tab[i]!=NULL){
  216.  
  217. while(tab[i]!=NULL){
  218.  
  219. count++;
  220.  
  221. tab[i]=tab[i]->next;
  222.  
  223. }
  224.  
  225. }
  226.  
  227. }
  228.  
  229. printf("%d\n", count);
  230.  
  231. return 0;
  232.  
  233. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement