Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Altri Linguaggi - [ASSEMBLY MIPS]Cancellazione di elementi in una lista collegata con puntatori
Forum - Altri Linguaggi - [ASSEMBLY MIPS]Cancellazione di elementi in una lista collegata con puntatori

Avatar
dennis87 (Normal User)
Newbie


Messaggi: 5
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 16:54
Mercoledì, 06/03/2013
Ciao a tutti,
devo fare un esercizio che mi chiede

    a) Inserimenti di interi in lista. Se la lista è vuota si crea dinamicamente una lista puntata degli interi inseriti             dall’utente (0 per terminare l’inserimento). Se la lista non è vuota i nuovi elementi inseriti dall’utente vengono inseriti a partire dalla coda della lista già esistente. In seguito si visualizzano su console gli elementi della lista risultante (dopo l’inserimento) separati da spazi e si ritorna al menù (visualizzare su console la stringa “Nil” nel caso di lista vuota).
    b) Eliminazione di interi pari. Si eliminano dalla lista tutti gli elementi con valore intero pari. In
    seguito si visualizzano su console gli elementi della lista risultante (dopo l’eliminazione) separati
    da spazi e si ritorna al menù (visualizzare su console la stringa “Nil” nel caso di lista vuota).

Ora per il primo punto penso di essere arrivato a conclusione, il secondo ho fatto l'eliminazione al caso se il numero si trova in testa, e si elimina senza problemi, e se il numero si trova in coda, e si elimina senza problemi.
Quando però il numero da eliminare è in coda, esso si elimina, ma se inserisco altri elementi, questi non vengono stampati.
Alltra domanda quale è il metodo per eliminare i numeri che si trovano nel mezzo, cioè non in testa o in coda?
Cioè so che basta modificare il puntatore, ma non capisco come scriverlo.
Questo è il codice che ho scritto fino ad adesso.
Codice sorgente - presumibilmente Altri Linguaggi

  1. # Title: Esercizio 6                   
  2. # Author: Dennis Aleandro Boanini                      
  3. # Description: Esercizio di progetto n°6
  4. ################# Data segment menù ###########
  5. .data
  6. menu1:  .asciiz "\n\n1 - Inserimenti di interi in lista. 0 per terminare l'inserimento.\n\n"
  7. menu2:  .asciiz "2 - Eliminazione di interi dispari.\n\n"    
  8. ################# Data segment generale ###########
  9.         end:    .asciiz "\nFine del programma!\n"
  10.         nil:    .asciiz "\nNil\n\n"
  11.         space:  .asciiz " "
  12.         insert: .asciiz "\nInserisci elemento -> "
  13.         elinsert:       .asciiz "\nElementi inseriti -> "
  14.         inserimento:    .asciiz "\nEffettua una scelta -> "
  15.         test:   .asciiz " -- Di test -- "
  16.         error:  .asciiz "\nScelta sbagliata, rieffettua la scelta per favore "
  17.         creator:        .asciiz " \n\n Created by Dennis Aleandro Boanini "
  18.         coda:   .asciiz "\n coda"
  19.         .align 4
  20.         jump_table: .space 8 # jump table array a 4 word che verra' instanziata dal main con gli indirizzi delle label che chiameranno le corrispondenti procedure
  21.        
  22. ################# Code segment #####################
  23.        
  24. .text  
  25. .globl main    
  26.  
  27. main:
  28. la $s1, jump_table #assegnazione ad $s1 dell'indirizzo base della jump_table
  29. la $t0, juno #assegnazione a $t0 l'indirizzo della case action juno              
  30. sw $t0, 0($s1)  
  31. la $t0, jdue #assegnazione a $t0 l'indirizzo della case action juno      
  32. sw $t0, 4($s1) #scrittura nella locazione di memoria di indirizzo $s1+4 del valore contenuto in $t0      
  33.  
  34. move $t8 $zero                  # s0 (= Testa) = 0
  35. move $t9 $zero                  # s1 (= Coda ) = 0
  36. li $s2, 2       #per controllo se numero pari o dispari
  37.          
  38. menu:
  39. #Stampa del menu di selezione
  40.  la $a0, menu1 #carico l'indirizzo della stringa menu1 in $a0  
  41. li $v0, 4 #assegno il codice 4 (print string) a $v0    
  42. syscall #stampo la stringa menu1
  43. la $a0, menu2
  44. li $v0, 4
  45. syscall
  46.        
  47. choice:
  48. # scelta della procedura o dell'uscita
  49.           li $v0, 4  # $v0 =codice della print_string
  50.       la $a0, inserimento # $a0 =  indirizzo della stringa
  51.           syscall # stampa la stringa prompt     
  52.          
  53. # legge la scelta
  54.       li $v0, 5
  55.           syscall
  56.           move $s0, $v0   # $s0=scelta 1, 2, 3 o 4
  57.          
  58.           sle  $t0, $s0, $zero  # $t0=1 se $s0 <= 0
  59.           bne  $t0, $zero, choice_err # errore se scelta <=0
  60.           li   $t0,4
  61.           sle  $t0, $s0, $t0
  62.           beq  $t0, $zero, choice_err # errore se scelta >4
  63.  
  64. branch_case:
  65.           la $s1, jump_table
  66.           addi $s0, $s0, -1 # tolgo 1 da scelta perche' prima azione nella jump table (in posizione 0) corrisponde alla prima scelta del case
  67.           add $t0, $s0, $s0
  68.           add $t0, $t0, $t0 # ho calcolato (scelta-1) * 4
  69.           add $t0, $t0, $s1 # sommo all'indirizzo della prima case action l'offset calcolato sopra
  70.           lw $t0, 0($t0)    # $t0 = indirizzo a cui devo saltare
  71.  
  72.           jr $t0 # salto all'indirizzo calcolato
  73.  
  74. choice_err:
  75.       li $v0, 4  
  76.       la $a0, error
  77.       syscall # stampa la stringa errore               
  78.                                                                                  
  79.       j choice # ritorna alla richiesta di inserimento di un numero tra 1 e 4
  80.        
  81. # prima case action
  82. juno:
  83.         #move $t8 $zero                 # s0 (= Testa) = 0
  84.         #move $t9 $zero                 # s1 (= Coda ) = 0
  85.         bne $t8, $zero, inputloop
  86.         li $v0, 4
  87.         la $a0, nil
  88.         syscall
  89. inputloop:                    # inizio loop di input;
  90.         li $v0, 4
  91.         la $a0, insert
  92.         syscall                       # stampa messaggio
  93.  
  94.         li $v0, 5
  95.         syscall                       # legge un intero
  96.         beq $v0, $zero, print           # se l'intero letto e' zero, salta all'etichetta print (stampa)
  97.         move $t1 $v0                  # altrimenti t1=input
  98.  
  99. # inizio inserzione nuovo elemento
  100.         li $v0, 9
  101.         li $a0, 8                       #8 byte, 1 per l'intero e uno per il puntatore.
  102.         syscall                         # chiamata sbrk: restituisce un blocco di 8 byte, puntato da v0: il nuovo record
  103.                                                 # vegono riempiti i due campi del nuovo record:
  104.         sw $t1, 0($v0)                  # campo intero = t1
  105.         sw $zero, 4($v0)                # campo elemento-successivo = nil
  106.         bne $t8, $zero, link_last               # se s0!=nil (coda non vuota) vai a link_last
  107.         move $t8, $v0                   # altrimenti (prima inserzione)  Testa=Coda=v0
  108.         move $t9, $v0
  109.  
  110.         j inputloop                     # torna all'inizio del loop di input
  111.  
  112.  
  113. link_last:                    # se la coda e' non vuota, collega l'ultimo elemento della lista,
  114.                                         # puntato da Coda (s1) al nuovo record; dopodiche' modifica Coda
  115.                                         # per farlo puntare al nuovo record
  116.         sw $v0, 4($t9)                  # il campo elemento successivo dell'ultimo del record prende v0
  117.         move $t9, $v0                   # Coda = v0
  118.         j inputloop
  119.  
  120. print:                          # loop di stampa di tutti gli elementi della coda, separati da spazi
  121.         move $t0, $t8           # t0 = Testa. t0 verra' usato come puntatore per scorrere gli elementi della lista
  122.        
  123.         li $v0, 4
  124.         la $a0, elinsert
  125.         syscall
  126.        
  127. loop_print:
  128.         beq $t0, $zero, menu            # se  t0 == 0 si e' raggiunta la fine della lista e si esce
  129.         li $v0, 1                               # altrimenti si stampa l'elemento corrente. Cioe':
  130.         lw $a0, 0($t0)                  # a0 = valore del campo intero dell'elemento corrente (puntato da t0)
  131.         syscall                         # stampa valore intero dell'elemento corrente
  132.         li $v0, 4
  133.         la $a0, space                  
  134.         syscall                         # stampa spazio
  135.         lw $t0, 4($t0)                  # t0 = valore del campo elemento-successivo dell'elemento corrente (puntato da t0)
  136.         j loop_print                    # salta all'inizio del ciclo di stampa 
  137.        
  138.         j menu
  139. jdue:
  140.         beq $t8, $zero, empty
  141.         move $t0, $t8
  142. trova:
  143.         lw $s0, 0($t0)
  144.         div $s0, $s2
  145.         mfhi $s1
  146.         beq $s1, $zero, checkTC
  147.         lw $t0, 4($t0)
  148.         j trova
  149. checkTC:
  150.         beq $t0, $t8, eliminaT
  151.         beq $t0, $t9, eliminaC
  152. eliminaT:
  153.         lw $t8, 4($t0)
  154.         lw $t0, 4($t0)
  155.         j trova
  156. eliminaC:
  157.         sw $zero, -4($t9)
  158.         lw $t0, 4($t0)
  159.         beq $t0, $zero, print
  160.         j trova
  161.        
  162. empty:
  163.         li $v0, 4
  164.         la $a0, nil
  165.         syscall
  166.         j menu


EDIT del codice: adesso sembra funzionare, per l'eliminazione di elementi in testa in coda, non se è proprio la soluzione ottimale, ma almeno va. Aspetto consigli su una soluzione meglio...
Codice Editato:
Codice sorgente - presumibilmente Altri Linguaggi

  1. # Title: Esercizio 6                   
  2. # Author: Dennis Aleandro Boanini                      
  3. # Description: Esercizio di progetto n°6
  4. ################# Data segment menù ###########
  5. .data
  6. menu1:  .asciiz "\n\n1 - Inserimenti di interi in lista. 0 per terminare l'inserimento.\n\n"
  7. menu2:  .asciiz "2 - Eliminazione di interi dispari.\n\n"    
  8. ################# Data segment generale ###########
  9. end:    .asciiz "\nFine del programma!\n"
  10. nil:    .asciiz "\nNil\n\n"
  11. space:  .asciiz " "
  12. insert: .asciiz "\nInserisci elemento -> "
  13. elinsert:       .asciiz "\nElementi inseriti -> "
  14. inserimento:    .asciiz "\nEffettua una scelta -> "
  15. test:   .asciiz " -- Di test -- "
  16. error:  .asciiz "\nScelta sbagliata, rieffettua la scelta per favore "
  17. creator:        .asciiz " \n\n Created by Dennis Aleandro Boanini "
  18. mezzo:  .asciiz "\n mezzo"
  19. .align 4
  20. jump_table: .space 8 # jump table array a 4 word che verra' instanziata dal main con gli indirizzi delle label che chiameranno le corrispondenti procedure
  21.        
  22. ################# Code segment #####################
  23. .text  
  24. .globl main    
  25.  
  26. main:
  27. la $s1, jump_table #assegnazione ad $s1 dell'indirizzo base della jump_table
  28. la $t0, juno #assegnazione a $t0 l'indirizzo della case action juno              
  29. sw $t0, 0($s1)  
  30. la $t0, jdue #assegnazione a $t0 l'indirizzo della case action juno      
  31. sw $t0, 4($s1) #scrittura nella locazione di memoria di indirizzo $s1+4 del valore contenuto in $t0      
  32.  
  33. move $t8 $zero                  # s0 (= Testa) = 0
  34. move $t9 $zero                  # s1 (= Coda ) = 0
  35. li $s2, 2       #per controllo se numero pari o dispari
  36.          
  37. menu:
  38. #Stampa del menu di selezione
  39.  la $a0, menu1 #carico l'indirizzo della stringa menu1 in $a0  
  40. li $v0, 4 #assegno il codice 4 (print string) a $v0    
  41. syscall #stampo la stringa menu1
  42. la $a0, menu2
  43. li $v0, 4
  44. syscall
  45.        
  46. choice:
  47. # scelta della procedura o dell'uscita
  48.           li $v0, 4  # $v0 =codice della print_string
  49.       la $a0, inserimento # $a0 =  indirizzo della stringa
  50.           syscall # stampa la stringa prompt     
  51.          
  52. # legge la scelta
  53.       li $v0, 5
  54.           syscall
  55.           move $s0, $v0   # $s0=scelta 1, 2, 3 o 4
  56.          
  57.           sle  $t0, $s0, $zero  # $t0=1 se $s0 <= 0
  58.           bne  $t0, $zero, choice_err # errore se scelta <=0
  59.           li   $t0,4
  60.           sle  $t0, $s0, $t0
  61.           beq  $t0, $zero, choice_err # errore se scelta >4
  62.  
  63. branch_case:
  64.           la $s1, jump_table
  65.           addi $s0, $s0, -1 # tolgo 1 da scelta perche' prima azione nella jump table (in posizione 0) corrisponde alla prima scelta del case
  66.           add $t0, $s0, $s0
  67.           add $t0, $t0, $t0 # ho calcolato (scelta-1) * 4
  68.           add $t0, $t0, $s1 # sommo all'indirizzo della prima case action l'offset calcolato sopra
  69.           lw $t0, 0($t0)    # $t0 = indirizzo a cui devo saltare
  70.  
  71.           jr $t0 # salto all'indirizzo calcolato
  72.  
  73. choice_err:
  74.       li $v0, 4  
  75.       la $a0, error
  76.       syscall # stampa la stringa errore               
  77.                                                                                  
  78.       j choice # ritorna alla richiesta di inserimento di un numero tra 1 e 4
  79.        
  80. # prima case action
  81. juno:
  82.         #move $t8 $zero                 # s0 (= Testa) = 0
  83.         #move $t9 $zero                 # s1 (= Coda ) = 0
  84.         bne $t8, $zero, inputloop
  85.         li $v0, 4
  86.         la $a0, nil
  87.         syscall
  88. inputloop:                    # inizio loop di input;
  89.         li $v0, 4
  90.         la $a0, insert
  91.         syscall                       # stampa messaggio
  92.  
  93.         li $v0, 5
  94.         syscall                       # legge un intero
  95.         beq $v0, $zero, print           # se l'intero letto e' zero, salta all'etichetta print (stampa)
  96.         move $t1 $v0                  # altrimenti t1=input
  97.  
  98. # inizio inserzione nuovo elemento
  99.         li $v0, 9
  100.         li $a0, 8                       #8 byte, 1 per l'intero e uno per il puntatore.
  101.         syscall                         # chiamata sbrk: restituisce un blocco di 8 byte, puntato da v0: il nuovo record
  102.                                                 # vegono riempiti i due campi del nuovo record:
  103.         sw $t1, 0($v0)                  # campo intero = t1
  104.         sw $zero, 4($v0)                # campo elemento-successivo = nil
  105.         bne $t8, $zero, link_last               # se s0!=nil (coda non vuota) vai a link_last
  106.         move $t8, $v0                   # altrimenti (prima inserzione)  Testa=Coda=v0
  107.         move $t9, $v0
  108.  
  109.         j inputloop                     # torna all'inizio del loop di input
  110.  
  111.  
  112. link_last:                    # se la coda e' non vuota, collega l'ultimo elemento della lista,
  113.                                         # puntato da Coda (s1) al nuovo record; dopodiche' modifica Coda
  114.                                         # per farlo puntare al nuovo record
  115.         sw $v0, 4($t9)                  # il campo elemento successivo dell'ultimo del record prende v0
  116.         move $t9, $v0                   # Coda = v0
  117.         j inputloop
  118.  
  119. print:                          # loop di stampa di tutti gli elementi della coda, separati da spazi
  120.         move $t0, $t8           # t0 = Testa. t0 verra' usato come puntatore per scorrere gli elementi della lista
  121.        
  122.         li $v0, 4
  123.         la $a0, elinsert
  124.         syscall
  125.        
  126. loop_print:
  127.         beq $t0, $zero, menu            # se  t0 == 0 si e' raggiunta la fine della lista e si esce
  128.         li $v0, 1                               # altrimenti si stampa l'elemento corrente. Cioe':
  129.         lw $a0, 0($t0)                  # a0 = valore del campo intero dell'elemento corrente (puntato da t0)
  130.         syscall                         # stampa valore intero dell'elemento corrente
  131.         li $v0, 4
  132.         la $a0, space                  
  133.         syscall                         # stampa spazio
  134.         lw $t0, 4($t0)                  # t0 = valore del campo elemento-successivo dell'elemento corrente (puntato da t0)
  135.         j loop_print                    # salta all'inizio del ciclo di stampa 
  136.        
  137.         j menu
  138. jdue:
  139.         beq $t8, $zero, empty
  140.         move $t0, $t8
  141. trova:
  142.         lw $s0, 0($t0)
  143.         div $s0, $s2
  144.         mfhi $s1
  145.         beq $s1, $zero, checkTC
  146.         lw $t0, 4($t0)
  147.         beq $t0, $zero, print
  148.         j trova
  149. checkTC:
  150.         beq $t0, $t8, eliminaT
  151.         beq $t0, $t9, eliminaC
  152.         j eliminaM
  153. eliminaT:
  154.         lw $t8, 4($t0)
  155.         lw $t0, 4($t0)
  156.         j trova
  157. eliminaC:
  158.         sw $zero, -4($t0)
  159.         #lw $t9, -4($t0)
  160.         addi $t9, $t9, -8
  161.         #move $s5, $t0
  162.         lw $t0, 4($t0)
  163.         beq $t0, $zero, print
  164.         j trova
  165. eliminaM:
  166.         lw $t0, 4($t0)
  167.         sw $t0, -12($t0)
  168.         j trova
  169. empty:
  170.         li $v0, 4
  171.         la $a0, nil
  172.         syscall
  173.         j menu


Ultima modifica effettuata da dennis87 il 07/03/2013 alle 17:53
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6223
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 18:08
Mercoledì, 06/03/2013
Intanto correggi qui:

Codice sorgente - presumibilmente Plain Text

  1. menu2:  .asciiz "2 - Eliminazione di interi dispari.\n\n"



Con:

Codice sorgente - presumibilmente Plain Text

  1. menu2:  .asciiz "2 - Eliminazione di interi pari.\n\n"



Con un test input 1,2,3,4

Codice sorgente - presumibilmente Plain Text

  1. checkTC:
  2.         beq $t0, $t8, eliminaT
  3.         beq $t0, $t9, eliminaC
  4. eliminaT:
  5.         lw $t8, 4($t0)
  6.         lw $t0, 4($t0)
  7.         j trova



Al momento di eliminare 2 il programma dovrebbe branciare su eliminaC, ma non lo fa. I valori di $t0 e $t9 sono:

$t0    0x10040008
$t9    0x10040018

Il codice esegue la parte eliminaT per un elemento che non e' la testa, quindi non funziona.

Ti consiglio di scaricare questo http://courses.missouristate.edu/KenVollmar/MARS/download.htm e di fare un po' di debugging (tenendo d'occhio le registers, il segmento heap e passo per passo guardare cosa fa il programma).


Il mio blog: https://piero.dev
PM Quote
Avatar
dennis87 (Normal User)
Newbie


Messaggi: 5
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 9:08
Giovedì, 07/03/2013
Grazie pierotofy per la risposta.
Per quanto riguarda il menù era soltanto un copia e incolla per fare un test, per quanto riguarda il codice, al momento attuale, funziona solamente se do in input
4 7 7
7 7 4
7 7
4 7 7 4
ovvero riesce ad eliminare solo gli elementi in testa, in coda e contemporaneamente in testa e in coda e in tutti e 4 i casi restituisce sempre i valori 7 7.  Se faccio l'esempio tuo 1 2 3 4 il codice darà errore perche il 2 non è ne in testa ne in coda e quindi il programma va in crash.
Adesso mi iniziano le lezioni, dopo provo a dare un occhiata al tuo link e in caso di altri problemi magari riposto qui.
Grazie ancora per la risposta.

PM Quote
Avatar
dennis87 (Normal User)
Newbie


Messaggi: 5
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 15:58
Giovedì, 07/03/2013
MARS programma molto meglio di QtSpim e debugging ottimo, ma ancora non ho capito come fare per eliminare un elemento che non è la testa o la coda, ma elemento di mezzo.
Quando arrivo all'elemento da cancellare, come modifico il puntatore dell'elemento precedente per farlo puntare all'elemento successivo a quello da cancellare?

EDIT:
Ho editato il secondo codice del primo post.
Adesso sembra quasi funzionare.
Ho provato a dare in input queste seguenze di numeri: 4777, 7774, 4774, 7477, 4747, 7474, 47474, 4477, 7744, 74472, 7447, 123456789, funziona su tutti tranne che su 7744 che stampa 774, 74472 e 7447 che stampano 747.
Continuo a lavorarci.

Ultima modifica effettuata da dennis87 il 07/03/2013 alle 17:57
PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 14:18
Sabato, 09/03/2013
Devi scorrere la lista, elemento per elemento, se l' elemento successivo è pari lo elimini e modifichi il puntatore

PM Quote
Avatar
dennis87 (Normal User)
Newbie


Messaggi: 5
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 16:07
Sabato, 09/03/2013
Si lo so ma il problema mi si presenta quando ho piu interi da eliminare consecutivamente, come nel caso 7 4 4 7...che mi rende 7 4 7 anzichè 7 7

PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 18:28
Sabato, 09/03/2013
Perchè sbagli il metodo di scorrimento, tu devi rimanere a cancellare l' elemento successivo, finchè l' elmento successivo è spari

Ultima modifica effettuata da il 09/03/2013 alle 18:36
PM Quote
Avatar
dennis87 (Normal User)
Newbie


Messaggi: 5
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 19:38
Sabato, 09/03/2013
non è che potresti farmi vedere come si fa?
sono giorni che ci sto impazzendo ma non ne vengo mai a capo...

PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 22:53
Sabato, 09/03/2013
No, perchè non conosco l' assembly MIPS, mi spiace molto lo farei è che non so come si faccia.........

PM Quote