Appunti+Esercizi di esame di Fondamenti di Informatica svolti

IMMAGINE SBAGLIATA

L'inserimento suffisso può dovere modificare il puntatore di testa della lista (nel caso in cui la lista sia

vuota). Per questo la funzione suf_insert() deve ricevere l’indirizzo del puntatore stesso.

[7.1] Implementazioni

lunedì 22 dicembre 2014

01:54

Rappresentazione sequenziale

1. struct list{

2. float * buffer;

3. int size;

4. int head;

5. int tail;

6. };

7.

8. /* alloca il buffer su cui sono memorizzati i valori della lista e

9. asserisce l’invariante della rappresentazione:

10. se head==tail la lista è vuota;

11. altrimenti head è l'indice dell'elemento di testa e

12. tail è l'indice della prima posizione successiva all’elemento di coda

13. */

14. void init(struct list * ptr, int size){

15. ptr->buffer = (float *) malloc(size*sizeof(float));

16. ptr->size = size;

17. ptr->head = 0;

18. ptr->tail = 0;

19. }

20.

21. //inserimento in coda: aumenta tail

22. Boolean suf_insert(struct list * ptr, float value){

23. if((ptr->tail+1)%ptr->size != ptr->head){

24. ptr->buffer[ptr->tail] = value;

25. ptr->tail = (ptr->tail+1)%ptr->size;

26. return TRUE;

27. }

28. else

29. return FALSE;

30. }

31.

32. //inserimento in testa: riduce head

33. Boolean pre_insert(struct list * ptr, float value){

34. if((ptr->tail+1)%ptr->size != ptr->head){

35. ptr->head = (ptr->head + ptr->size-1)%ptr->size;

36. ptr->buffer[ptr->head] = value:

37. return TRUE;

38. }

39. else

40. return FALSE;

41. }

42.

43. //visita di stampa

44. void visit(struct list * ptr){

45. int index;

46. for(index=ptr->head; index!=ptr->tail; index=(index+1)%ptr->size){

47. printf("%d", ptr->buffer[index]);

48. }

49. }

50.

51. //ricerca: restituisce TRUE se il valore è contenuto nella lista

52. Boolean search(struct list * ptr, float value){

53. Boolean found = FALSE;

54. int index=ptr->head;

55. while(found == FALSE && index!=ptr->tail){

56. if(ptr->buffer[index]==value)

57. found=TRUE;

58. else

59. index = (index+1)%ptr->size);

60. }

61. return found;

62. }

Osservazioni:

Le operazioni di inserimento e cancellazione restituiscono un Booleano per trattare le eccezioni in

• cui la lista è piena o vuota.

Nell'operazione di inserimento in testa per decrementare head di 1 si usa l'espressione

• head=(head+size-1)%size che include senza eccezione il caso in cui head vale 0.

Nelle operazioni di visita e di ricerca potrebbe essere passata la lista piuttosto che il suo indirizzo

• (i.e. il prototipo della funzione potrebbe avere la forma void visit(struct list);) visto che l’operazione

non modifica il valore di alcun membro della struttura.

Nella implementazione, si è invece passato l'indirizzo per la ragione dell’efficienza, in modo da

ridurre il numero dei parametri copiati sullo stack.

Rappresentazione collegata con array e indici

struct record{

• float value;

• int next;

• };

•

• struct list{

• int first;

• int free;

• int size;

• struct record * buffer;

• };

•

• /* Inizializzazione - alloca il buffer e asserisce l'invariante della lista:

• first ha il valore illegale che indica che non ci sono elementi memorizzati;

• free indirizza il primo record;

• tutti i records sono concatenati a partire dal primo

• per averli disponibili come records liberi.

• */

•

19. void init(struct list * ptr, int size){

20. int count;

21.

22. ptr->buffer=(struct record *)malloc(size*sizeof(struct record));

23. ptr->size = size;

24. ptr->first = ptr->size; //first = valore illegale

25. ptr->free = 0; //il primo elemento disponibile è il primo elemento dell'array

26.

27. for(count=0; count<ptr->size; count++) //ogni record viene collegato a quello successivo

28. ptr->buffer[count].next = count+1; //l'ultimo sarà collegato a un valore illegale

29. }

30.

31. //visita

32. void visit(struct list * ptr){

33. int position = ptr->first; // la prima posizione da visitare è il primo elemento

34. while(position != ptr->size){

35. printf("%f", ptr->buffer[position].value);

36. position = ptr->buffer[position].next;

37. }

38. }

39.

40. //ricerca

41. Boolean search(struct list * ptr, float value){

42. int position;

43. Boolean found;

44.

45. position = ptr->first;

46. found = FALSE;

47.

48. while(position != ptr->size && found == FALSE){

49. if(ptr->buffer[position].value == value)

50. found == TRUE;

51. else

52. position = ptr->buffer[position].next;

53. }

54. }

55.

56. /* Inserimento in testa - se la lista non è vuota, ne sgancia il primo elemento,

57. lo aggancia in testa alla lista dei valori e ci memorizza il valore da inserire.

58. In pratica il nuovo valore viene fisicamente inserito alla fine dell'array,

59. dopodiché esso punterà a quello che era il primo elemento prima del suo inserimento,

60. alla fine l'indice del primo elemento "first" assume il valore dell'indice

61. dell'elemetno che volevamo inserire in testa, così da renderlo il primo in visita.

62. */

63. Boolean pre_insert(struct list * ptr, int value){

64. int moved;

65.

66. if(ptr->free != ptr->size){ //se free=size allora che la lista è piena

67. moved = ptr->free;

68. ptr->free = ((ptr->buffer)[ptr->free]).next;

69.

70. ptr->buffer[moved].value = value;

71. ptr->buffer[moved].next = ptr->first;

72. ptr->first = moved;

73.

74. return TRUE;

75. }

76. else

77. return FALSE;

78. }

79.

80. /* Inserimento in coda - se la lista non è vuota, ne sgancia l'ultimo elemento

81. e lo aggancia in coda alla lista dei valori, ci copia sopra il valore da

82. inserire e attribuisce il valore illegale al successore. Altrimenti return FALSE

83. */

84. Boolean suf_insert(struct list * ptr, float value){

85. int moved;

86. int * position_ptr;

87.

88. if(ptr->free != ptr->size){

89. moved = ptr->free;

90. ptr->free = ((ptr->buffer)[ptr->free]).next;

91.

92. position_ptr = &ptr->first;

93.

94. while(*position_ptr != ptr->size)

95. position_ptr = &(ptr->buffer)[*position_ptr].next;

96.

97. *position_ptr = moved; // Non è sbagliato, i puntatori funzionano così. essendo un

98. ptr->buffer[moved].value = value; // indirizzo, è come se scrivessimo un valore su

99. ptr->buffer[moved].next = ptr->size; // tale indirizzo (quindi sul campo .next

dell'ultimo)

100. return TRUE;

101. }

102. else

103. return FALSE;

104. }

105.

106. /* Inserimento ordinato - Assume che la lista sia ordinata.

107. inserisce il nuovo elemento in ordine, rispetto alla funzione precedente vi è

108. l'introduzione di una seconda condizione sul while e uno swap nell'inserimento

finale

109. */

110. Boolean ord_insert(struct list * ptr, float value){

111. in moved;

112. int * position_ptr;

113.

114. if(ptr->free != ptr->size){

115. moved = ptr->free;

116. ptr->free = ptr->buffer[ptr->free].next;

117.

118. position_ptr = &ptr->first;

119. while(*position_ptr != ptr->size && ptr->buffer[*position_ptr].value < value)

120. position_ptr = &((ptr->buffer[*position_ptr]).next);

121. ptr->buffer[moved].value = value;

122. ptr->buffer[moved].next = *position_ptr;

123. *position_ptr = moved;

124. return TRUE;

125. }

126. else

127. return FALSE;

128. }

Osservazioni:

Nel corpo della funzione viene definito un puntatore position_ptr che attraversò il ciclo while viene

• manipolato fino ad indirizzare il record sul quale deve essere operato l'inserimento.

Se la lista è inizialmente vuota, l’indice del record su cui operare l'inserimento è quello contenuto

• nel campo first della lista; se invece la lista è non vuota allora l’indice dei record su cui operare

l'inserimento è contenuto nel campo next di uno dei record che stanno nel buffe r.

L'uso del puntatore position_ptr permette di unificare i due casi.

Rappresentazione collegata con i puntatori

struct list{

• float value;

• struct list * next_ptr,

• };

•

• //inizializzazione

•

7. void init(struct list ** ptrptr){

8. *ptrptr = NULL;

9. }

10.

11. //visita - si passa l'intera lista

12. void visit(struct list * ptr){

13. while(ptr != NULL){

14. print("%f", ptr->value);

15. ptr = ptr->next_ptr;

16. }

17. }

18.

19. /* ricerca - se il valore è contenuto restituisce TRUE e scrive

20. in *ptrptr il puntatore all'elemento che lo contiene.

21. restituisce FALSE altrimenti.

22. */

23. Boolean search(struct list * ptr, float value, struct list ** ptrptr){

24. Boolean found;

25.

26. found = FALSE;

27. while(ptr != NULL && found == FALSE){

28. if(ptr->value == value){

29. found = TRUE;

30. *ptrptr = ptr;

31. }

32. else

33. ptr = ptr->next_ptr;

34. }

35. return found;

36. }

37.

38. //inserimento in testa

39. void pre_insert(struct list ** ptrptr, float value){

40. struct list * tmp_ptr;

41. tmp_ptr = *ptrptr;

42. *ptrptr = (struct list *) malloc(sizeof(struct list));

43. (*ptrptr)->value = value;

44. (*ptrptr)->next_ptr = tmp_ptr;

45. }

46.

47. /* Preleva il primo elemento - se la lista è vuota restituisce FALSE

48. altrimenti restituisce TRUE, scrive in *value_ptr il valore

49. nell'elemento in testa e lo cancella dalla lista.

50. */

51. Boolean consume_first(struct list ** ptrptr, float * value_ptr){

52. if(*ptrptr !=NULL){

53. *value_ptr = (*ptrptr)->value;

54. *ptrptr = (*ptrptr)->next_ptr;

55. return TRUE;

56. }

57. else

58. return FALSE;

59. }

60.

61. /* inserimento in coda - scorre il doppio puntatore fino a che questo

62. non punta un puntatore nullo (ovvero il campo .next_ptr dell'ultimo)

63. ovvero il puntatore su cui applicare malloc.

64. poi applica un inserimento in testa sulla sottolista puntata dal

65. doppio puntatore.

66. */

67. void suf_insert(struct list ** ptrptr, float value){

68. while(*ptrptr != NULL)

69. ptrptr = &((*ptrptr)->next_ptr