Απορία κατανόησης άσκησης σε C

[lion2486]

Επειδή σε αυτό το θέμα παραθέτω απορία μου για μια άσκηση στη σχολή μου, αν νομίζεται πως δεν ειναι "σωστό"-"καλό" πείτε το μου. Η άσκηση αναφέρεται σε μια παραλαγή του αλγορίθμου συμπίεσης-αποσυμπίεσης αρχείων lzw. Το πρόβλημά μου το βασικό είναι ότι από την εκφώνηση δεν κατάφερα να καταλάβω πολλά για την υλοποίηση του προγράμματός μου. Αν μπορεί κάποος να μου δώσει κάποιες υποδείξεις/επεξηγήσεις/βοήθεια. Η εκφώνηση της άσκησης βρίσκεται εδώ.

Ευχαριστώ.

[nikolaos_]

Πότε είναι η προθεσμία;

[virxen75]

δες και εδώ

 

http://www.perlmonks.org/?node_id=270016

[Blondeamon]

Φαίνεται πολύ μανίκι.

[yourse.gr]

Λοιπόν, η εργασία δεν είναι μικρή οπότε λογικό είναι να μην περιμένεις κώδικα από εμάς. Αν ήταν σε C++ θα είχες και την βοήθεια της STL αλλά ...

 

Για να μην φλυαρώ,

 

http://marknelson.us/1989/10/01/lzw-data-compression/ για τον αλγόριθμο.

 

http://cprogramminglanguage.net/avl-tree.aspx για ένα binary search tree για να υλοποιήσεις το λεξικό. Οποιαδήποτε συγκεκριμένη απορία έχεις ρώτα.

[lion2486]

Πότε είναι η προθεσμία;

Η τελική προθεσμία μετά την παράταση που δόθηκε ορίστηκε στις Παρασκευή 26/2/2010, παρ' όλο που δώσαμε το Σάββατο που πέρασε τα γραπτά.

 

Φαίνεται πολύ μανίκι.

Ναι και εμένα ρε Δημήτρη ξέρεις πως μου φάνηκε για πρωτοετής; Το φυσάω και δεν κρυώνει, αλλά αν δεν τα περάσουμε πως θα μάθουμε...

 

Γενικά θέλω να μην μου δώσετε καθόλου κώδικα... Απλά θέλω να συζητήσω με πιο έμπειρους για αυτό. Δεν έχω μεγάλο πρόβλημα στην υλοποίηση δέντρων... αλλά περισσότερο στη λογική του αλγορίθμου. Σκέφτηκα να μην χρησιμοποιήσω δυαδικό δέντρο, αλλά μια δομή με έναν πίνακα δεικτών 256 θέσεων, οι οποίοι θα είναι όλοι οι γνωστοί χαρακτήρες. Ελπίζω έτσι να γλιτώσω αρκετό χρόνο, σπαταλώντας περισσότερη μνήμη, αλλά πιστεύω τελικά να αξίζει τον κόπο.

Το πρόβλημά μου είναι πως δεν έχω καταλάβει σωστά ένα σημείο του αλγορίθμου. Πείτε ότι βρίσκω τελικά μία σειρά ψηφίων τα οποία τελικά θέλω να τα προσθέσω στο λεξικό μου, θα τα προσθέσω ονομάζοντάς τα ως τον επόμενο διαθέσιμο αριθμό λεξικού; Αν ναι, μετά πως θα τα βρίσκω; (έστω σε δυαδικό, στο 256δικό θα έχω ένα υποδέντρο για κάθε ακολουθία). Επίσης μπερδεύομαι με την ύπαρξη και τη χρήση του περίφημου κωδικού εκκαθάρισης, τί θα αλλάξει για να μας κάτσει καλύτερα όταν ξαναδοκιμάσεις; Πότε μπορείς να τον χρησιμοποιήσεις; Σβήνει όλο το λεξικό και γίνεται σαν να συνεχίζει νέο συμπιεσμένο αρχείο; Τελικά στο ακόλουθο αρχείο που ξέρουμε αν κάναμε καλά που τον χρησιμοποιήσαμε;

[virxen75]

Σκέφτηκα να μην χρησιμοποιήσω δυαδικό δέντρο, αλλά μια δομή με έναν πίνακα δεικτών 256 θέσεων

 

256 θα είναι στην αρχή,αλλά θα αυξάνει συνέχεια δεν θα είναι σταθερό.

[npapak]

Συγνώμη αυτό είναι άσκηση για πρωτοετείς??

Αυτά που ζητάει τα έχετε διδαχτεί ή τώρα πρέπει να τα μάθετε???

 

btw, σε ποια σχολή σπουδάζεις???

[lion2486]

256 θα είναι στην αρχή,αλλά θα αυξάνει συνέχεια δεν θα είναι σταθερό.

Ναί, αλλά τα υποδέντρα θα έχουν και αυτά 256 υποδέντρα, χωρίς να χρησιμοποιούνται όλα, αλλά μόνο όποιο η ακολουθία υπάρχει στο λεξικό. Επίσης σκέφτηκα πως αν έχω μια μεταβλητή, με την οποία χρησιμοποιώντας τη θέση μνήμης η οποία βρίσκεται, να εννοώ ότι υπάρχει ναι μεν το δέντρο που έχουμε, αλλά είναι το τελευταίο υποδέντρο, αποτέλεσμα να εξοικονομήσουμε λίγη μνήμη. Το όλο σκεπτικό μου για αυτό το δέντρο είναι να μην γίνεται μια αναζήτηση σε ένα δυαδικό δέντρο, αλλά άμεση προσπέλαση και έλεγχος, αφού αν τελικά υπάρχει στο λεξικό, τότε ξέρουμε ακριβώς που θα βρίσκεται.

 

Συγνώμη αυτό είναι άσκηση για πρωτοετείς??

Αυτά που ζητάει τα έχετε διδαχτεί ή τώρα πρέπει να τα μάθετε???

 

btw, σε ποια σχολή σπουδάζεις???

Γενικά έχουμε διδαχτεί δείκτες, δομές, δέντρα, λίστες, αρχεία... μερικά βέβαια χωρίς πολλές περιγραφές και εξάσκηση. Η σχολή λέγεται ολοκληρωμένα Πληροφορικής και Τηλεπικοινωνιών Εθνικού και Καποδιστριακού Πανεπιστημίου Αθήνας.

[npapak]

Πόσο γενικά τα κάνατε όλα αυτά??

 

Τεσπα, εμένα αυτό μου θυμίζει αρκετά ένα πίνακα επεκτάσιμου κατακερματισμού (χωρίς να είναι και απόλυτα σωστό γιατί βαρέθηκα να την διαβάσω όλη την άσκηση).

Αν θέλεις μπορείς να δεις και αυτήν την περίπτωση.

 

Υ.Γ.:Τελικά δεν είναι μόνο στην δική μου σχολή τόσο κομπλεξικοί οι καθηγητές..