Έλεγχος καρκινικών String - Java

[Wise_One]

Καλησπέρα σας φίλτατοι. Είμαστε πριν την εξεταστική, και στις ασκήσεις επανάληψης έχουμε να γράψουμε ένα πρόγραμμα που θα ελέγχει αν το String που δόθηκε είναι καρκινικό με χρήση της κατάλληλης δομής δεδομένων. Καρκινικά είναι τα String τύπου a, aa, aaa, anna, abba, lol, 1991 κλπ.

 

Θεωρώ ότι η καταλληλότερη δομή δεδομένων είναι η διπλά συνδεδεμένη λίστα. Εξηγώ την προς το παρόν σκέψη μου.

 

Χωρίζω το String σε χαρακτήρες και τους εισάγω στη δ.σ.λ. ώστε να μπορώ να πηγαινοέρχομαι μπρος-πίσω εύκολα (δε χρησιμοποιώ πίνακα γιατί το ζητούμενο είναι να δουλέψουμε με άλλες δομές).

 

Θα διατρέχω τη λίστα απ' την αρχή ως το μισό size της, κι απ' το τέλος ως το μισό size της και θα ελέγχω κάθε φορά αν το στοιχείο απ' το πρώτο μισό είναι ίσο με το άλλο.

 

Θα προσπαθήσω να το κάνω πρώτα στο χαρτί και μετά να γράψω κώδικα. Αν έχετε πάντως κάποια ιδέα ή αν υπάρχει στάνταρ μεθοδολογία γι' αυτό, θα ήθελα να τη μάθω. Στο Ιντερνετ δε μου έβγαλε κάτι (ίσως γιατί δεν έβαζα σωστά keywords).

[lewis68]

Κατασκεύασε ένα ArrayList

ArrayList<String> myList=new ArrayList<String>();

Εισάγεις όσα στοιχεία θέλεις με την εντολη add()

π.χ myList.add("a");

 

O δείκτης στο 1ο στοιχείο της λίστας ξεκινάει από το μηδέν

ενώ ο δείκτης στο τελευταίο στοιχείο έχει τιμή κατά ένα λιγότερο

από τα στοιχεία της λίστας

int first=0

int last=myList.size()-1

 

Με τη μέθοδο myList.get(index) παίρνεις μια αναφορά για κάθε

στοιχείο που βρίσκεται στη θέση index και μετά μπορείς να συγκρίνεις

το περιεχόμενο των αναφορών με τη μέθοδο equals.

 

Σκέψου πως θα κάνεις την επανάληψη κι εδώ είμαστε.

[drmetal]

Τα παιδί λέει δεν θέλει να χρησιμοποιήσει πίνακα γιατί πρέπει να χρησιμοποιήσει κάποια δομή δεδομένων ...

 

νομίζω το point είναι να προγραμματίσει τη λίστα όχι να χρησιμοποιήσει την έτοιμη της java

[parsifal]

Push τους N/2 πρώτους χαρακτήρες σε μία στοίβα. Στη συνέχεια, για τον κάθε έναν από τους επόμενους N/2 χαρακτήρες, κάνεις Pop από τη στοίβα και συγκρίνεις με τον τρέχοντα...

[warchief]

Αν το δεδομένο της άσκησης δεν είναι η εξοικείωσή με κάποια δομή δεδομένων, και απλά η αλγοριθμική νοοτροπία τότε μπορεί να λυθεί απλά με ένα for (i=0; i< lower_int(string.size() / 2))

[Wise_One]

Πιάστηκα με Δένδρα χθες και ξέχασα εντελώς αυτό το πρόγραμμα.

 

@drmetal: H ArrayList δε μας πειράζει. Άλλωστε κι εμείς χρησιμοποιούμε τους πίνακες για να φτιάξουμε τις δομές. Βέβαια αν μάθεις πώς υλοποιείται κανονικά μια λίστα είναι ακόμα καλύτερα, και τώρα επιτέλους δεν έχουμε (virtual) overflows.

 

@lewis68: Όντως, κι εγώ σκεφτόμουν ότι θα χρησιμοποιήσω λίστα. Προτιμώ να χρησιμοποιήσω (γι' αρχή τουλάχιστον) τις δικές μας υλοποιήσεις γιατί ξέρω ακριβώς τί έχουμε γράψει. Θα τσεκάρω βέβαια και αυτές του ΑΡΙ.

 

@parsifal: Κι αυτή η ιδέα είναι καλή και νομίζω πιο γρήγορα υλοποιήσιμη. Βέβαια θα πρέπει να πετάω το τελευταίο char (αν έχω περιττό String) αλλά δε παίζει ρόλο...

 

Λοιπόν πολύ ωραία. Σας ευχαριστώ πολύ. Θα γράψω αργότερα τα προκαταρκτικά και θα σας πώ το βράδυ τί κατάφερα...

[parsifal]

@parsifal: Κι αυτή η ιδέα είναι καλή και νομίζω πιο γρήγορα υλοποιήσιμη. Βέβαια θα πρέπει να πετάω το τελευταίο char (αν έχω περιττό String) αλλά δε παίζει ρόλο...

 

Όχι τον τελευταίο. Τον (N div 2) + 1 (για αρίθμηση που ξεκινά από το 1)...

[Wise_One]

Ναι δε το εξήγησα καλά. Τον μεσαίο εννοούσα.

 

Πάντως είμαι απίστευτος. Ούτε σήμερα πρόλαβα να τα δοκιμάσω. Αλλά έχουμε και τ' άλλα μαθήματα που να πάρει... Αύριο ελπίζω.