[Δομημένος Προγραμματισμός]Εργασια Ε

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Γιώργος]

και το οποιο γινεται με καποιον τροπο......

Ε προφανώς.

Πχ υλοποιείς μια στοίβα σε πίνακα.

[ΡΕΣΑΛΤΟ]

η στοιβα πως υλοποιεται;
με κλησεις συναρτησεων;
η στοιβα εχει στανταρ μεγεθος;

[Merlin]

Γιατί ρε παιδιά στοίβες?I dont get it...
Όχι δεν ρωτάμε τον χρήστη με ποια συνδέεται,η δομή του binary tree είναι κάτι standard,άλλωστε γιατί να μας δώσει το σχήμα ο Κορτέσης?Εξάλλου στο λινκ που παρέθεσα ο τύπος είναι κι' αυτός standard ,δεν ρωτάει κανέναν χρήστη

[Captain Mixos]

Όμως στοιβα δεν εχουμε μαθει...κ δεν νομιζω να μας εβαζε ασκηση που θα πρεπει να χρησιμοποιήσουμε κατι που δεν μαθαμε.....αρα λογικα θα υπαρχει κι αλλοσ τροπος....

[ΡΕΣΑΛΤΟ]

δλδ Merlin εσυ πως το κανες;
το δεντρο του Κορτεση ειναι ενδεικτικο, αφου μπορεις πχ να εχεις 100 σταθμους....

[Merlin]

E τα ίδια θα ισχύουν και εκεί απλά θα έχεις περισσότερους σταθμούς.Ρε παιδιά ο τύπος (i-1)/2 ισχύει για 15 αλλά και για 100 σταθμούς.Απλά κάνετε μια typecasting μπροστά:i=(int)((i-1)/2) για να ισχύει και για το αριστερό αλλά και για το δεξύ "παιδάκι" και μετά καλείται αναδρομικά την συνάρτηση με όρισμα i.

[Γιώργος]

Όμως στοιβα δεν εχουμε μαθει...

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


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

Πχ στο παράδειγμα: (ΑΓΝΟΕΙΣΤΕ ότι ο 1 έχει 3 "παιδιά", απλά ξεχάστε ότι υπάρχει ο κόμβος 7).



Έστω ότι το σήμα πάει από τον 1 >> 5.

Ξεκινάς από τον 1: δεν είναι ο 5, άρα κοιτάς αριστερά και αν χρειαστεί μετά δεξιά.
Πας στον 2: δεν είναι ο 5, άρα κοιτάς αριστερά και αν χρειαστεί μετά δεξιά.
Πας στον 3: δεν είναι ο 5, άρα κοιτάς αριστερά και αν χρειαστεί μετά δεξιά.
Πας στον 4: δεν είναι ο 5, άρα κοιτάς αριστερά και αν χρειαστεί μετά δεξιά.

ΟΜΩΣ ο 4 είναι φύλλο, οπότε κάνεις backtracking στον 3 και κοιτάς δεξιά.
Είναι ο 5!!! Άρα σε έναν πίνακα αποθηκεύεις τους ενδιάμεσους κόμβους, κάνοντας τα backtrackings:

5 - 3 - 2 - 1

Κάπου πρέπει να τα αποθηκεύσεις αυτά, προφανώς σε πίνακα. Μετά θα τα εκτυπώσετε προφανώς ανάποδα, δηλαδή 1 >> 2 >> 3 >> 5. Απλά αυτή η λειτουργία λέγεται "στοίβα", γι' αυτό το λέω.

[Merlin]

Για το δέντρο ας πούμε :
                          0
                      /       \
                  1             2
                 /  \           /  \
               3    4        5    6
ο κόμβος 3 θα έχει προηγούμενο κόμβο τον (3-1)/2=1
αλλά και ο 4 θα έχει τον 1 επειδή (int)(4-1)/2=1

[Captain Mixos]

ομως το μεγεθος του πινακα με τους ενδιαμεσους δεν το ξερουμε εξ αρχης...πως τον δηλωνουμε?

[ΡΕΣΑΛΤΟ]

τι εννοεις κοιτας δεξια-αριστερα...
αυτη η διαδικασια πως υλοποιηται;

[Γιώργος]

ομως το μεγεθος του πινακα με τους ενδιαμεσους δεν το ξερουμε εξ αρχης...πως τον δηλωνουμε?

Κοίτα, εγώ θα τον έκανα με λίστες μάλλον.
Αλλά όσον αφορά τον πίνακα, πράγματι δεν ξέρεις το μέγεθός του, οπότε θα δηλώσεις παραπάνω. Η καλύτερη περίπτωση μεγέθους είναι , για ένα τέλειο balanced δέντρο, ενώ η χειρότερη θα είναι N, όταν δηλαδή δεν έχεις πρακτικά δέντρο, αλλά:

1 -> 2 -> 3 -> 4 κοκ

Και ο κόμβος-προορισμός είναι ο τελευταίος. Ε, εγώ θα δήλωνα μέγεθος N για να 'χω το κεφάλι μου ήσυχο.

τι εννοεις κοιτας δεξια-αριστερα...

Κάθε κόμβος δεν στέλνει μήνυμα σε άλλους δύο;
Τους οποίους τους κρατάς σε ένα πίνακα Nx2...



Επίσης να προσθέσω ότι δεν θα χρειαζόταν να κρατήσουμε κάπου την διαδρομή αν μπορούσαν οι recur να υπολογίσουν συνολικό χρόνο καθυστέρησης και να τυπώσουν την διαδρομή, αλλά αφού θέλει ο αρχιπρογραμματιστής Κορτέσης να τα κάνει η main(), θα πρέπει κάπου να τα αποθηκεύσουμε.




Α, για να μην ξεχαστώ: DISCLAIMER: μετά την απομάκρυνση απ' το ταμείο ουδέν λάθος αναγνωρίζεται
Ό,τι γράφω είναι πώς θα το υλοποιούσα εγώ, όποιος θέλει να ακολουθήσει αυτή τη λογική it's ok, but I do not guarantee anything

[ΡΕΣΑΛΤΟ]

μου ρθε φλασια με το δεντρακι και μαλλον θα το βγαλω
ευχαριστω.

μια αλλη απορια....
πως δηλωνουμε δυναμικα δυσδιαστατο πινακα με τη μια διασταση σταθερη και την αλλη μεταβλητη;
κατι ειδα αλλα εχει pointers των pointers... αν καποιος μπορει να το πει με δυο λογια 8)

και αλλη μια bonus
ειπαμε το δεντρο δημιουργειται στη main και το φτιαχνω οπως θελω εγω;

[Merlin]

Ναι για την δυναμική δέσμευση στην ansi C δουλεύεις με pointers των pointers ω pointers.Η διαδικασία έχει ως εξής:

int i,**table,stathmoi;
table=(int **)malloc(stathmoi*sizeof(int));
for(i=0;i<stathmoi;i++){
    table[ i ]=(int *)malloc(2*sizeof(int));
}
Δες και προηγούμενες σελίδες βρε .Τα χουμε πει αυτά.Ναι,το δέντρο το φτιάχνεις εσύ αλλά όχι όπως θέλεις,είναι δυαδικό δέντρο και έχει standard δομή.For the shake of God δείτε λινκς και προηγούμενα ποστς.

[jimant]

Συγνώμη που το ρωτάω αλλα διαβασα τα προηγούμενα σχόλια και δεν το κατάλαβα. Οι 2 σταθμοί που θα διαβιβάζει τις εντολές καποιοσ σταθμος ειναι συγκεκριμένοι ή θα τους δινει ο χρήστης?

[Αιμιλία η φτερωτή χελώνα]

φαινονται στον πινακα στο ethmmy 8)